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
Sudan
Sudan Madhu (Madras 1966) informatico indiano. Dopo la laurea a Delhi e il dottorato in informatica alla università della California a Berkeley, è divenuto professore di scienze informatiche presso [...] il Massachusetts Institute of Technology (mit). Notevoli sono i suoi contributi a vari settori dell’informaticateorica, tra cui la teoria delle dimostrazioni verificabili probabilisticamente e la teoria dei codici. Nel 2002 gli è stato assegnato il ...
Leggi Tutto
grafi, teoria dei
grafi, teoria dei settore della matematica che studia in modo formalizzato i grafi, riconducendo a un’unica teoria diversi problemi classici: dal problema dei → ponti di Königsberg [...] ai sistemi esperti e alle reti neurali. Lo sviluppo della metodologia dei grafi è proceduto di pari passo con l’informaticateorica e la crescita dei mezzi di elaborazione: i sistemi digitali di calcolo, i circuiti logici e le strutture di dati ...
Leggi Tutto
Szemeredi
Szemerédi Endre (Budapest 1940) matematico ungherese naturalizzato statunitense. Dopo gli studi universitari a Budapest, ha conseguito il dottorato all’università statale di Mosca. Prima di [...] , dopo altri importanti riconoscimenti, il Premio Abel nel 2012 «per il suo contributo fondamentale alla matematica discreta e all’informaticateorica, e per l’impatto profondo e duraturo che la sua opera ha avuto sulla teoria additiva dei numeri e ...
Leggi Tutto
Valiant
Valiant Leslie Gabriel (Budapest 1949) teorico dell’informatica inglese. Di madre ungherese, si trasferì ben presto in Inghilterra, dove frequentò il King’s College di Cambridge e l’Imperial [...] e matematica applicata presso la Harvard University. Le sue ricerche riguardano diversi settori dell’informaticateorica, quali la teoria della complessità e dell’apprendimento computazionale, la neuroscienza computazionale e l’intelligenza ...
Leggi Tutto
La grande scienza. Cronologia scientifica: 1941-1950
1941-1950
1941
Le successioni esatte. Introdotte in una nota sui gruppi di coomologia (priva di dimostrazioni) dal polacco Witold Hurewicz ed estensivamente [...] e dimostrando i teoremi fondamentali. La teoria avrà un'influenza decisiva sullo sviluppo di altre discipline, quali l'informaticateorica e la teoria dei codici correttori di errori, definendo in modo matematicamente utile concetti come quello di ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] possono gettare in generale sullo studio dei modelli finiti. Si tratta di un tema di grande importanza anche per l'informaticateorica ma soprattutto in sé, come mostrano per esempio le ricerche di Ax (1968) sui campi pseudofiniti, e che ha portato ...
Leggi Tutto
Discreto e continuo
Paolo Zellini
Matematica e intuizione
La matematica ha sempre cercato di stabilire un nesso tra il continuo e il discreto, il primo esemplificato, tipicamente, nelle figure dello [...] gli strumenti dell’algebra, e lo studio della difficoltà di calcolo di una funzione richiede alcuni dei tipici presupposti dell’informaticateorica, come lo studio dei modelli di calcolo e la teoria dei grafi. In un importante articolo del 1989 (On a ...
Leggi Tutto
logica intuizionista
logica intuizionista teoria logica nata nel contesto dell’→ intuizionismo, filosofia della matematica elaborata da L.E.J. Brouwer nel 1907. Secondo Brouwer in matematica sono da [...] della → calcolabilità. Per questo motivo la logica intuizionista è stata recuperata nelle applicazioni della logica all’informaticateorica. In particolare, grazie all’isomorfismo di → Curry-Howard, è possibile affermare che ogni dimostrazione della ...
Leggi Tutto
definibilita
definibilità termine che designa uno dei principali oggetti di studio della logica matematica, insieme con la dimostrabilità e la calcolabilità; consiste in una riflessione sul concetto [...] contigue, quali per esempio la teoria della calcolabilità, la teoria degli insiemi e lʼinformaticateorica. Per quanto riguarda lʼinformaticateorica, il concetto di definibilità è alla base dello studio matematico dei linguaggi formali e diventa ...
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...