Yao, Andrew
Yao, Andrew. – Informatico e teorico della computazione statunitense (n. Shanghai 1946), ideatore di algoritmi efficienti e studioso della teoria della complessità. Dopo la laurea a Taiwan, [...] ha conseguito un dottorato in fisica ad Harvard e uno in informatica alla University of Illinois. Ha insegnato alla Stanford University (1982-86), alla Princeton University (fino al 2004) e infine all’università ...
Leggi Tutto
metodo iterativo
metodo iterativo particolare metodo numerico usato per l’implementazione della maggior parte degli algoritmi di calcolo e basato sulla → iterazione di un insieme di operazioni. È caratterizzato, [...] , il metodo di → bisezione, il metodo delle → secanti, il metodo di → Newton (o delle tangenti). Qualora per un dato algoritmo convergente l’errore commesso a un passo di iterazione sia proporzionale a quello commesso al passo precedente, si parla di ...
Leggi Tutto
enumerazione
enumerazióne [Der. del lat. enumeratio -onis, da enumerare "enunciare ordinatamente"] [INF] Paradigma di e.: v. algoritmi, teoria degli: I 102 d. ...
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, [...] P2 e i relativi linguaggi L1, L2 , una riduzione polinomiale da P1 a P2 è una funzione f da Σ* su Σ* tale che: 1) esiste un algoritmo polinomiale deterministico F che calcola f; 2) per ogni v∈Σ*, si ha v∈L1 se e solo se f(v)∈L2. Si dice allora che P1 ...
Leggi Tutto
metodo bottom-up
metodo bottom-up (ingl., letteralmente «dal basso verso l’alto») metodo di progettazione degli algoritmi che procede analizzando il problema da risolvere dai casi particolari al caso [...] più generale. In particolare, nell’analisi delle espressioni di un linguaggio, un metodo bottom-up muove dalle espressioni formali date verso categorie sintattiche sempre più ampie attraverso l’applicazione ...
Leggi Tutto
controllo, schema di
controllo, schema di espressione che indica gli schemi costruttivi che sono alla base degli algoritmi. Ogni algoritmo, infatti, può essere costruito utilizzando delle strutture di [...] fino a ... fai e il ciclo ripeti ... finché ... (→ ciclo).
Il teorema di → Böhm-Jacopini stabilisce che ogni algoritmo può essere scritto utilizzando unicamente tre schemi di controllo: sequenza, alternativa e ciclo; questi tre schemi sono alla base ...
Leggi Tutto
metodo top-down
metodo top-down (ingl., letteralmente «dall’alto verso il basso») metodo di progettazione degli algoritmi che procede analizzando il problema da risolvere dal caso generale al caso particolare; [...] più dettagliati, giungendo a quelli con cui si ha già familiarità e che si è in grado di risolvere. La struttura dell’algoritmo che si costruisce sulla base di una metodologia top-down è quella di albero ordinato, in cui la radice rappresenta il ...
Leggi Tutto
Markov, algoritmo di
Markov, algoritmo di sistema di riscrittura di stringhe costruito sulla base di una lista di regole. Gli algoritmi di Markov possono rappresentare ogni espressione matematica calcolabile [...] a partire dalla prima, quella che contiene come pattern una parte dell’input dato. Se essa non viene trovata l’algoritmo termina, altrimenti viene rimpiazzato il pattern trovato più a sinistra nella stringa e la procedura continua. Per esempio, il ...
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 [...] stato X1 allo stato X2, e b12 è la probabilità che lo stato nascosto X1 causi l’evento y2.
Dove trovare gli algoritmi
Le tecniche statistiche e matematiche utili per l’esplorazione di dati biologici possono essere eseguite per mezzo di vari pacchetti ...
Leggi Tutto
ALGOL
ALGOL 〈àlgol〉 [ELT] [INF] Sigla dell'ingl. ALGOrythmic Language "linguaggio algoritmico" con cui s'indica un linguaggio di programmazione simbolico di tipo numerico per calcolatori elettronici, [...] atto alla trattazione di problemi matematici e scientifici in genere, basato sull'uso di insiemi compiuti di istruzioni (algoritmi). ...
Leggi Tutto
algoritmista
s. m. [der. di algoritmo] (pl. -i). – Nome con cui sono indicati i seguaci, nell’Europa occidentale dei secoli 12°-13°, delle nuove regole di calcolo contenute nel trattato di al-Khuwārizmī: si distinguevano per l’abbandono dell’abaco...