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, [...] delle soluzioni possibili (per es., l'insieme di tutte le possibili assegnazioni di valori di verità alle variabili della formula booleana o l'insieme di tutti i percorsi diversi che possono essere seguiti dal commesso viaggiatore) è esponenziale ...
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, [...] x1 + x̅2). La proposizione si dice soddisfacibile se e solo se esiste un assegnamento di valori 0 o 1 alle variabili x1, .. xn tale che la proposizione booleana valga 1. Per esempio F = x1 ∙ (x̅2 + x1 ∙ x3) può essere soddisfatta (tra gli altri) dall ...
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 [...] appartenga alla classe P della complessità ordinaria.
Complessità di un circuito
Il calcolo del valore di una funzione booleana di n variabili dà luogo a un circuito: si tratta semplicemente di un grafo orientato aciclico, con 2n nodi sorgente, nel ...
Leggi Tutto
La grande scienza. Sistemi disordinati
David Sherrington
Sistemi disordinati
I sistemi disordinati sono estremamente comuni e appaiono con svariate forme e componenti in discipline molto differenti, [...] SAT, consistenti nel trovare valori di quantità booleane che soddisfino simultaneamente molte 'clausole' di controllo è il rapporto tra il numero di clausole e quello di variabili; dove, nel limite di molte clausole, la soddisfazione è possibile ...
Leggi Tutto
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, [...] 'unico problema della soddisfattibilità di espressioni booleane. Negli anni seguenti si riconobbe che complesse proprietà dei numeri primi che non è qui il caso di esporre. Le variabili in gioco sono il numero N di cui si deve stabilire la natura e ...
Leggi Tutto
Sistemi disordinati
David Sherrington
I sistemi disordinati possono trovarsi ovunque e apparire con svariate forme e componenti in discipline molto differenti, fra cui la fisica dello stato solido, [...] che consistono nel trovare valori di quantità booleane che soddisfino simultaneamente molte clausole di lunghezza K è il rapporto tra il numero di clausole e quello di variabili, dove, nel limite di molte clausole, la soddisfazione è possibile ...
Leggi Tutto