Complessità algoritmica
Fabrizio Luccio
Gli studi di complessità di calcolo si sono sviluppati essenzialmente nella seconda metà del ventesimo secolo. Basati sulla formalizzazione del concetto di algoritmo, [...] polinomiale con una macchina di Turing non deterministica si riducono all'unico problema della soddisfattibilità di espressionibooleane. Negli anni seguenti si riconobbe che numerosissimi problemi ben posti e praticamente rilevanti sono equivalenti ...
Leggi Tutto
Premessa. - Gli sviluppi dell'a. nel quindicennio 1960-75 sono stati assai notevoli, sia dal punto di vista quantitativo sia da quello qualitativo. Prima di esaminare alcuni progressi in direzioni particolari, [...] creazione e allo studio di nuove strutture algebriche (a. booleane, reticoli; a. cilindriche, poliadiche, ecc.).
Mutamento della finito e ben determinato) per decidere se due espressioni polinomiali costruite applicando le operazioni F di una ...
Leggi Tutto
Logica matematica
Abraham Robinson
*La voce enciclopedica Logica matematica è stata ripubblicata da Treccani Libri, arricchita e aggiornata da un’introduzione di Gabriele Lolli e un saggio di Beppo [...] a⋂1=a, a⋃a′=1, a⋂a′=0.
Un esempio tipico di algebra booleana è l'insieme di tutti i sottoinsiemi di un dato insieme V, dove i (denotazione) in ciascuna di esse. Se X è un'espressione valida in tutti i modelli di un insieme di proposizioni S ...
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. [...] di Kleene questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε denota la problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:
[2] ∀x∀y ...
Leggi Tutto
Informatica teorica
Giorgio Ausiello
Con l'espressione informatica teorica ci si riferisce a un complesso di discipline scientifiche aventi per oggetto lo studio formale degli strumenti, dei metodi [...] di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfacibilità di un'espressionebooleana, il problema dello scheduling (decidere se si può allocare un insieme di lavori su più macchine in modo da ...
Leggi Tutto