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
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] di tale tipo sono la risolubilità di un sistema di equazioni lineari a variabili intere, la soddisfattibilità di un'espressionebooleana, la possibilità di sequenziare un insieme di lavori su più macchine in modo da rispettare una data scadenza, la ...
Leggi Tutto
Imparare a generalizzare
Manfred Opper
(Neural Computing Research Group, Aston University Birmingham, Gran Bretagna)
Questo saggio fornisce un'introduzione alle teorie che mirano alla comprensione della [...] un perceptron che calcola output a valori binari dal segno dell'espressione [1].
Come studente scegliamo una rete con una funzione di P. Carnevali e S. Patarnello nelle cosiddette reti booleane, che possiedono unità elementari di calcolo diverse da ...
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
Automi e linguaggi formali
Dominique Perrin
La teoria degli automi e dei linguaggi formali ha lo scopo di descrivere le proprietà delle successioni di simboli. Tali successioni si presentano in situazioni [...] Kleene, questo insieme di parole si può anche descrivere con un'espressione razionale, e cioè: (ab+b)*(ε+a), dove ε . Un tipico problema della classe PSPAZIO è la soddisfacibilità delle formule booleane con quantificatori, per esempio:
[2] ∀ x ∀ y(x ...
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