Matematica
Termine, derivato dall’appellativo al-Khuwārizmī («originario della Corasmia») del matematico Muḥammad ibn Mūsa del 9° sec., che designa qualunque schema o procedimento sistematico di calcolo [...] dei dati in uscita (output) che, in questo caso, sono le cifre 0 o 1.
Proprietà fondamentali di un algoritmo
Effettività. Un a. deve essere effettivamente eseguibile da un esecutore, che diciamo automa; l’automa deve poter riconoscere cioè le ...
Leggi Tutto
La scienza in Cina: dai Qin-Han ai Tang. La matematica
Alexei Volkov
Karine Chemla
Qu Anjing
La matematica
Le bacchette
di Alexei Volkov
Il sistema di numerazione cinese, sistema decimale e principio [...] alla II o alla III, a seconda del problema.
Questo fatto si riflette nel modo in cui un problema si collega all'algoritmo. La 'regola della doppia falsa posizione' richiede quattro termini che chiameremo a, a′, b, b′; per i problemi del primo tipo, a ...
Leggi Tutto
Programmazione, algoritmi di
Alessandro Panconesi
Il termine algoritmo denota un procedimento sistematico ed esplicitato nei suoi passi elementari per l’esecuzione di un calcolo, inteso nella sua accezione [...] per la determinazione del massimo comun divisore tra due numeri e il cosidetto setaccio di Eratostene: si tratta di un algoritmo che, dato un numero N, calcola tutti i numeri primi minori di N. Un altro esempio piuttosto noto, tipicamente insegnato ...
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
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
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
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
Sigla di fast Fourier transform che, nella tecnica della elaborazione numerica del segnale, indica un algoritmo finalizzato a calcolare la trasformata di Fourier di un segnale, permettendo così di ridurre [...] in modo sostanziale il numero delle operazioni richieste ...
Leggi Tutto
Macchina di Turing
Mauro Cappelli
Modello di agente di calcolo adatto a simulare la logica di qualsiasi algoritmo computazionale. La macchina formale fu proposta nel 1936 dal logico e matematico britannico [...] ammettono nessuna soluzione generale calcolabile. La tesi o congettura di Church-Turing afferma infatti che, se esiste un algoritmo per eseguire un compito che manipola simboli, allora esiste una macchina di Turing in grado di eseguire quel compito ...
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
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....