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. [...] 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
Computer. Hardware
Gianfranco Bilardi
Raffaele Tripiccione
Obiettivo dei sistemi informatici è la soluzione automatica di problemi computazionali. Un problema computazionale è un insieme di domande [...] funzionamento del sistema scandita da un segnale periodico, chiamato clock. Durante ciascun passo, l’applicazione di appropriati operatoribooleani all’insieme di bit che caratterizzano lo stato attuale del processore produce un nuovo insieme di bit ...
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 [...] 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
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
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 [...] assegnazioni di valori di verità alle variabili della formula booleana) è esponenziale, mentre la verifica del fatto che è stata sviluppata e formalizzata, a metà degli anni Settanta, per opera di John V. Guttag, Barbara Liskov, Stephen N. Zilles e ...
Leggi Tutto