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
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
programmazione lineare
Mauro Cappelli
Insieme dei metodi di ottimizzazione di un criterio lineare con vincoli lineari di uguaglianza o disuguaglianza. Rappresenta un caso particolare del problema più [...] lineari interi (cioè a variabili intere) l’algoritmo più noto è detto branch and bound. Per problemi lineari misti si impiega l’algoritmo branch and cut. Tutti e tre gli algoritmi rappresentano metodi di risoluzione esatti.
→ Informaticateorica ...
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...
computabile
computàbile agg. [dal lat. computabĭlis]. – Che si può computare; di cui si può o si deve tener conto: periodo di servizio militare c. ai fini della pensione. In logica matematica e in informatica teorica, detto di una funzione...