Sturm, teorema di
Sturm, teorema di o regola di Sturm, algoritmo per la determinazione del numero di zeri reali di un polinomio a coefficienti reali p(x) compresi tra due dati valori a e b che non siano [...] Budan-Fourier) il numero di radici reali di un polinomio a coefficienti reali che cadono in un intervallo. A tal fine si applica l’algoritmo di → Euclide per il calcolo del massimo comune divisore tra il polinomio p(x) e la sua derivata p′(x), con l ...
Leggi Tutto
Kowalski, notazione di
Kowalski, notazione di espressione con cui si indica la formula: algoritmo = logica + controllo. Tale formula esprime sinteticamente la teoria di R. Kowalski sugli algoritmi dei [...] o con il metodo bottom-up. La scelta del metodo con cui utilizzare la definizione costituisce la componente di controllo dell’algoritmo. Il metodo top-down («dall’alto verso il basso») consiste nel ridurre la complessità del calcolo di (n + 1)! al ...
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 [...] è O(f(n)) se esistono due costanti c ed n′ tali che per ogni n>n′, per ogni dato di dimensione n, l'algoritmo esegue un numero di passi limitato da cf(n) e che i logaritmi utilizzati in questo ambito sono logaritmi in base 2, se non diversamente ...
Leggi Tutto
problemi NP-completi
Mauro Cappelli
I problemi di decisione possono essere classificati prescindendo dall’algoritmo usato per risolverli. Sono state individuate le classi di problemi P, NP e NP-completi. [...] contiene. Dati ora due problemi R e Q, si dice che R si riduce a Q (e si indica con R μQ) se esiste un algoritmo polinomiale che associa a ogni istanza di R un’istanza di Q in modo tale che la soluzione dell’istanza di Q fornisce la soluzione della ...
Leggi Tutto
insieme decidibile
insieme decidibile in logica, insieme per cui esiste un algoritmo di calcolo che permette di stabilire in un tempo finito se, dato un elemento a, l’elemento appartiene o non appartiene [...] a esso. Qualora invece l’algoritmo sia in grado di identificare tutti gli elementi che appartengono all’insieme, ma non quelli che non gli appartengono, l’insieme è detto semidecidibile. Gli insiemi finiti sono decidibili, mentre un insieme infinito ...
Leggi Tutto
funzione calcolabile
funzione calcolabile funzione per la quale esiste una procedura di calcolo (→ algoritmo) che permette di determinarne, in un numero finito di passi, il valore in corrispondenza di [...] che la definisce è finita in alcuni casi e non lo è in altri. Nel caso della divisione è comunque possibile modificare l’algoritmo in maniera tale da renderlo finito, imponendo che si fermi a una data cifra decimale. Esistono tuttavia casi in cui la ...
Leggi Tutto
Bohm-Jacopini, teorema di
Böhm-Jacopini, teorema di stabilisce che ogni algoritmo può essere costruito utilizzando unicamente tre strutture (o schemi di controllo), cioè tre schemi aggregativi di istruzioni [...] elementari o di altri algoritmi già costruiti:
a) la sequenza di istruzioni, la cui espressione è:
b) l’alternativa tra due possibili percorsi, la cui espressione è:
c) il ciclo, cioè una espressione del tipo:
Ogni altro tipo di istruzione può ...
Leggi Tutto
problema dell’arresto
Fabrizio Luccio
Primo esempio di problema indecidibile, cioè che non ammette alcun algoritmo di risoluzione. Il problema dell’arresto nacque nel 1936, sulla base di studi sugli [...] (A, A)=true se A(A) termina;
ARR(A, A)=false se A(A) non termina.
L’esistenza di ARR consentirebbe di definire il seguente algoritmo NEW che invoca ARR al suo interno:
NEW(A):
p=true;
while (p=true) do p=ARR (A, A);
la cui computazione termina se e ...
Leggi Tutto
Littlewood D.E.
Littlewood 〈lìtluud〉 D.E. [ALG] Regola di L.-Robinson: algoritmo per calcolare i polinomi di Schur relativi a prodotti tensoriali tra gruppi finiti. ...
Leggi Tutto
algoritmo
(ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. – 1....