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
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
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
ricorsivo
ricorsivo [agg. Der. di ricorrere: (→ ricorrente)] [LSF] Sinon. di ricorrente. ◆ [ALG] [INF] Algoritmo, o procedimento o procedura, r.: algoritmo che è formulato con esplicito riferimento a [...] intero positivo n, è r. la procedura: n!=n✄(n-1)!; ...; 5!=5✄4!; ...; 2!=2✄1!; 1!=1; si contrapp. ad algoritmo iterativo (v. fig.). ◆ [ELT] Filtro non r.: v. immagini, elaborazione di: III 167 e. ◆ [ALG] [INF] Funzioni r. primitive: nella teoria ...
Leggi Tutto
Numeri che appaiono come derivanti da un campionamento casuale di una distribuzione uniforme, ma che sono in realtà generati da un algoritmo deterministico. Lo sviluppo dei calcolatori ha comportato un [...] dalle n cifre che occupano nel quadrato le posizioni che vanno dalla ((n/2)+1)-esima alla (3/2)n-esima. Questo algoritmo, pur nella sua semplicità, è per quasi tutti i semi abbastanza affidabile, anche se per ogni n si possono trovare alcuni cicli ...
Leggi Tutto
parser
parser 〈pàazë〉 [s.ingl. Der. di (to) parse "analizzare grammaticalmente", usato in it. come s.m.] [ELT] [INF] Algoritmo di un programma applicativo che, sulla base della grammatica e del lessico [...] automatica della struttura morfologica delle parole, per permetterne, per es., il richiamo dal dizionario di macchina; algoritmi di questo genere, ma di struttura più complessa, trovano un'applicazione anche nella linguistica in quanto permettono ...
Leggi Tutto
Markov Andrej Andreevic junior
Markov 〈màrkëf〉 Andrej Andreevič junior [STF] (Pietroburgo 1903 - Mosca 1979) Figlio di Andrej Andreevič; prof. di matematica nell'univ. di Leningrado (1935). ◆ [INF] Algoritmo [...] stesso alfabeto (eventualmente coincidente con quella di partenza); tale sostituzione si effettua secondo regole che precisano l'algoritmo medesimo (si tratta di effettuare ben determinate sostituzioni ripetute di lettere in base a un programma di ...
Leggi Tutto
ricorsività La proprietà di essere ricorsivo, cioè ricorrente. Teoria della r., o della ricorsione, o computabilità, la disciplina che si occupa di fornire una caratterizzazione matematica del concetto [...] da L. Löwenheim nel 1915 e D. Hilbert nel 1918), cioè il problema se, per una data teoria formale T, esista un algoritmo per determinare se una formula A sia o non sia un teorema di T. Per studiare tale problema occorreva trovare un corrispettivo ...
Leggi Tutto
complessità Caratteristica di un sistema (perciò detto complesso), concepito come un aggregato organico e strutturato di parti tra loro interagenti, in base alla quale il comportamento globale del sistema [...] polinomiale. 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 ...
Leggi Tutto
Berlekamp Elwyn Ralph
Berlekamp 〈bèrlëkemp〉 Elwyn Ralph [STF] (n. Dover, Ohio, 1940) Prof. di matematica e scienza dei calcolatori nell'univ. di Berkeley (1971). ◆ [ANM] [INF] Algoritmo di B.: v. manipolazione [...] algebrica: III 616 b ...
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....