Fisico e informatico italiano (n. Napoli 1936). Conseguita la laurea in Fisica, ha sviluppato un grande interesse per la cibernetica e nel 1970 ha concluso il dottorato in Computer and Communication Sciences [...] straordinario presso la Facoltà di Scienze Matematiche, Fisiche e Naturali dell’Università di Palermo, T. insegna Informaticateorica e Calcolabilità e complessità all’Università Federico II di Napoli. Accanto agli impegni didattici ha portato avanti ...
Leggi Tutto
ricorsivita
ricorsività in logica, caratteristica di un procedimento che riduce la complessità di un problema riportandolo a problemi via via più semplici cui il procedimento stesso viene applicato. [...] . Quanto alla teoria della → complessità, essa è stata stimolata dall’esigenza di applicazioni pratiche nell’ambito dell’informaticateorica o computer science e consiste in un tentativo di classificare le funzioni ricorsive in base al grado di ...
Leggi Tutto
Visione artificiale
Pietro Parodi
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
Vincent Torre
(Scuola Internazionale di Studi Superiori Avanzati, Trieste, Italia)
La visione artificiale, [...] maggior parte degli esperti sospettano - è un problema aperto di notevole importanza (per molti, il problema aperto dell'informaticateorica). Molti sforzi sono stati dedicati alla soluzione di questo problema fin dall'introduzione del concetto di NP ...
Leggi Tutto
La grande scienza. Automi e linguaggi formali
Dominique Perrin
Automi e linguaggi formali
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. [...] parole. L'Handbook of theoretical computer science di Leeuwen (1990a e b) tratta tutti i campi dell'informaticateorica. Il volume B contiene capitoli di rassegna sugli automi finiti, parole infinite, grammatiche context-free, computabilità, ecc ...
Leggi Tutto
Dimostrazione, teoria della
Jean-Yves Girard
La teoria della dimostrazione nasce negli anni Venti del Novecento come strumento di realizzazione del programma di David Hilbert per la fondazione della [...] il programma nelle sue forme più estreme, dall'altra per i sempre più frequenti contatti con discipline vicine come l'informaticateorica, che ne hanno allargato gli orizzonti.
Alla base del programma di Hilbert sta l'idea che ‒ ai fini dell'analisi ...
Leggi Tutto
La seconda rivoluzione scientifica: matematica e logica. Algebra
Claudio Procesi
Algebra
Per comprendere la storia dell'algebra del XX sec. è necessario fare un breve quadro dello sviluppo della disciplina [...] a strutture a essi associate (gli edifici di Bruhat-Tits).
L'algebra dei codici e dei linguaggi, nell'ambito dell'informaticateorica, può in parte essere considerata legata agli aspetti combinatori dell'algebra. Per esempio la teoria di Marcel Paul ...
Leggi Tutto
crittografia
crittografia o criptografia (dal greco kryptós, nascosto, e graphía, scrittura) sistema di scrittura e trasmissione cifrata delle informazioni interpretabile solo da chi conosca il particolare [...] la cui disposizione iniziale costituiva la chiave segreta. Per forzare Enigma, il matematico A. Turing, tra i fondatori dell’informaticateorica, anche grazie agli studi di un gruppo di matematici polacchi guidato da Marian Rejewski e alle coraggiose ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Maria Conforti
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
I teoremi d’incompletezza di Gödel del 1931 sono i risultati più profondi e spettacolari [...] di una variante del teorema di Kruskal, un risultato fondamentale di combinatoria, ricco di importanti applicazioni anche in informaticateorica (per esempio, si applica al problema della terminazione di sistemi di riscrittura). Ma il primo esempio ...
Leggi Tutto
taglio, regola del
taglio, regola del (in inglese cut rule) una delle regole di derivazione del calcolo dei → sequenti che può essere esplicitata come segue: se da una premessa A è possibile trarre una [...] stabilisce, infatti, che le deduzioni del calcolo dei sequenti sono paragonabili a procedure algoritmiche e crea pertanto un legame fra la teoria della dimostrazione e l’informaticateorica. Questo legame è sancito dall’isomorfismo di → Curry-Howard. ...
Leggi Tutto
Nassi-Shneiderman, diagramma di
Nassi-Shneiderman, diagramma di metodo grafico di rappresentazione di un algoritmo impiegato in particolare qualora si voglia esprimere l’algoritmo in un linguaggio di [...] programmazione procedurale. Il metodo è dovuto a due esperti statunitensi di informatica, teorica e applicata, I. Nassi e B. Shneiderman. Esso prevede una descrizione del flusso di istruzione in blocchi che possono essere contenuti uno nell’altro. I ...
Leggi Tutto
complessita
complessità s. f. [der. di complesso1]. – 1. L’esser complesso (nelle varie accezioni dei sign. 1 e 2 di quest’agg.): c. di una questione, di un ragionamento, di una costruzione teorica; c. di un atto giuridico; esaminare una situazione...
tecnico
tècnico agg. e s. m. (f. -a) [dal lat. technĭcus, gr. τεχνικός, der. di τέχνη «arte»] (pl. m. -ci). – 1. agg. a. Relativo alle applicazioni e realizzazioni pratiche di un’arte, di una scienza o di una disciplina, di un’attività: nozioni...