algoritmoalgoritmo [Der. del lat. mediev. algorithmus o algorismus, dal nome d'origine al-Huwa-rizmī- del matematico arabo Muhammad ibn Mu-sa, del 9° sec.] [ALG] [INF] Qualunque schema o procedimento [...] → Markov, Andrej AndreevicŠ Senior. ◆ [ALG] [FAF] A. ricorsivo: → ricorsivo. ◆ [INF] Teoria degli a.: è una delle basi teoriche dell'informatica, che ha trovato una sistemazione nell'ambito della logica solo nel 20° sec.: v. algoritmi, teoria degli. ...
Leggi Tutto
mappe autoorganizzanti
Fabio Catino
Algoritmi di calcolo per la rappresentazione di sistemi neurali artificiali non supervisionati (autoorganizzati in base alla competizione dei nodi prossimali). Tali [...] algoritmi, sviluppati da Teuvo Kohonen nei primi anni Ottanta del XX sec. e successivamente implementati, sono utilizzati come strumento analitico in varie discipline scientifiche: medicina e biologia (per es. nella rappresentazione delle funzioni ...
Leggi Tutto
algoritmizzazione
algoritmizzazióne [Der. di algoritmizzare "tradurre in algoritmi"] [FAF] [INF] Processo di traduzione in algoritmi di un fenomeno naturale o artificiale, a scopo conoscitivo o normativo. [...] di queste rappresentazioni si ha in discipline nuove, prive di un linguaggio formale proprio, che adottano gli algoritmi come strumento di ricerca e di conoscenza, come nel caso della psicologia cognitiva, della linguistica computazionale, ecc ...
Leggi Tutto
riduzione polinomiale
Fabrizio Luccio
Nello studio della complessità di algoritmi combinatori l’attenzione è focalizzata sulla classificazione dei problemi come polinomiali o esponenziali. L’esame si [...] f relativa alla coppia P1, P2, si può risolvere P1 trasformando ogni dato X di P1 in un dato f(X) di P2 e applicando l’algoritmo A a f(X). Ne segue che se P2 appartiene a P anche P1 appartiene a P. I problemi ‘più difficili’ in NP sono pertanto così ...
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, [...] metodo ha un costo O(n²) nel caso peggiore e O(n logn) nel caso medio. L'analisi del costo nel caso medio per questo algoritmo porta alla relazione di ricorrenza C(n)=n+1+2/n Σj≤nC(j−1), molto più complessa della precedente, e la cui soluzione si ...
Leggi Tutto
casualizzazione
casualizzazióne [Atto ed effetto del casualizzare "rendere casuale"] [INF] [PRB] L'effetto di algoritmi, processi e sim., che introducono in un procedimento o in un'operazione un elemento [...] aleatorio. ◆ [ELT]2 [INF] Schema di c. (o, meglio, di distribuzione casuale): nei calcolatori elettronici, tecnica di distribuzione dei record in una memoria che ne assicura un'occupazione e un tempo 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
vettoriale
vettoriale [agg. Der. di vettore "inerente a vettori"] [ANM] Analisi, o calcolo, v.: la parte della matematica che s'occupa degli algoritmi con i quali si opera sui vettori (a questi si applicano, [...] con opportuni adattamenti, tutti i concetti dell'analisi infinitesimale, quali quelli di continuità, limite, derivata, integrale, ecc.). ◆ [EMG] [MCC] Campo v.: un campo la cui grandezza ha carattere vettoriale: ...
Leggi Tutto
INFORMAZIONE, SCIENZA DELLA
Roman Tirler
Pierluigi Ridolfi
Stefano Ceri e Alfonso Fuggetta
Tecnologie della comunicazione di Roman Tirler
Sommario: 1. Introduzione. 2. Tecniche di comunicazione dati: [...] dimensione di un problema viene espressa tramite un numero n che misura la cardinalità dell'insieme dei valori su cui l'algoritmo deve operare; la complessità viene espressa come una funzione f (n). Se f è una funzione polinomiale, il problema viene ...
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...