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
L'Ottocento: matematica. Algebra della logica
Massimo Mugnai
Algebra della logica
Logica e matematica: pensare e calcolare
Sia nell'Antichità sia durante il Medioevo, la logica e la matematica si configurano [...] esempio, ponendo l=amante, b=benefattore e i, j essendo variabili su individui nell'ambito degli esseri umani, gli enunciati 'i è Hailperin 1981: Hailperin, Theodore, Boole's algebra isn't Boolean algebra, "Mathematics magazine", 54, 1981, pp. 172-184 ...
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
funzione (in un linguaggio di programmazione)
funzione (in un linguaggio di programmazione) parola riservata di un linguaggio di programmazione indicante una particolare procedura operativa, disponibile [...] il suo nuovo valore; oppure con sqrt(a) la radice quadrata della variabile a. Altre funzioni agiscono su tipi di dato non numerico, quali per esempio le funzioni booleane o le funzioni che operano con stringhe; per esempio la funzione conc(a ...
Leggi Tutto
funzione booleana
funzione booleana funzione binaria a variabili binarie. È una funzione che è applicata a un insieme di variabili binarie che assumono ciascuna uno di due possibili valori, per esempio [...] e 1, e dà come risultato 0 o 1. Per esempio, se x e y sono variabili binarie che possono assumere solo i valori 0 e 1, allora la funzione binaria definita da ƒ(x, y) = x ⋅ y è una funzione booleana i cui valori sono ƒ(0, 0) = 0, ƒ(0, 1) = 0 , ƒ(1, 0 ...
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 [...] l'insieme delle soluzioni possibili (per es., l'insieme di tutte le assegnazioni di valori di verità alle variabili della formula booleana) è esponenziale, mentre la verifica del fatto che una data soluzione soddisfi la proprietà richiesta (per es ...
Leggi Tutto
Bioinformatica
Sergio Nasi
La bioinformatica, che ha per oggetto la gestione e l’analisi dell’informazione biomedica attraverso i computer, si è sviluppata grandemente sotto l’impulso del Programma [...] W’. Molto usati sono anche le reti probabilistiche booleane e i modelli di teoria dell’informazione. In quest per immagazzinarla. L’informazione mutua misura l’interdipendenza tra due variabili, nel nostro caso l’espressione di due geni, ed è ...
Leggi Tutto
Modelli, Teoria dei
Silvio Bozzi
Malgrado le modeste origini che ne hanno segnato la nascita, la teoria dei modelli ha sviluppato nel corso del tempo idee e metodi che l'hanno resa uno dei settori più [...] la quantificazione esistenziale corrisponde alla proiezione parallela all'asse della variabile quantificata e quindi ogni proiezione di un insieme algebrico sarà una combinazione booleana di insieme algebrici di dimensione affine più bassa. È questo ...
Leggi Tutto