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 [...] notevolmente più difficili. Per esempio, i fatti fondamentali riguardanti i linguaggi razionali, come la chiusura rispetto alle operazionibooleane, nel caso infinito diventano un risultato molto delicato, dovuto a Büchi, che fa uso del teorema di ...
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, [...] variabili intere, la soddisfattibilità di un'espressione booleana, la possibilità di sequenziare un insieme di di Σ) e F è un insieme di simboli di funzione f₁,…,fm (detti operazioni di Σ) dotati di tipo (corrispondenza tra i simboli in F e l' ...
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, [...] falso' e 'vero'), e sulle quali sono ammesse le operazioni di negazione logica, rappresentata da una barra sulla variabile (x prodotto logico (x ∙ y = l se e solo se x=y= 1). Esempi di proposizioni booleane sono F =x1 ∙ (x̅2 +x1 ∙ x3) e F = (x̅1 + x2) ...
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, [...] detti K-SAT, consistenti nel trovare valori di quantità booleane che soddisfino simultaneamente molte 'clausole' di lunghezza K di spin un po' più nel dettaglio. I neuroni possono operare a diverse velocità e quando lo fanno inviano, attraverso le ...
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 è in ordine di grandezza O(n+tE), ove n è proporzionale al numero di operazioni per generare una n-pla e tE è il tempo per calcolare il valore di 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, [...] -SAT, che consistono nel trovare valori di quantità booleane che soddisfino simultaneamente molte clausole di lunghezza K; con i vetri di spin. I neuroni sono in grado di operare a diverse velocità e inviare ad altri neuroni, attraverso le sinapsi, ...
Leggi Tutto