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
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
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
Matematica
Manipolazione algebrica
Metodica, basata su algoritmi impiegati negli elaboratori elettronici, che permette il trattamento automatico di espressioni matematiche (per es., polinomi, funzioni [...] razionali e funzioni trascendenti), per generare nuove espressioni più semplici, oppure per ottenere altre espressioni mediante trasformazioni algebriche e analitiche che operino su simboli e non solo ...
Leggi Tutto
Parte dell’analisi matematica che si occupa della ricerca di algoritmi per la risoluzione numerica di problemi quali l’approssimazione di funzioni e l’integrazione di equazioni differenziali ordinarie [...] applicare un elegante metodo iterativo. Come si dimostra facilmente, il valore del polinomio caratteristico in un dato λ può essere ottenuto con il seguente algoritmo:
fk(λ) = (λ−ak)fk–1(λ) −b2k–1 fk–2(λ); f–1 = 0, f0 = 1,
dove (a1, a2, …, an) è la ...
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 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
Matematico e logico russo (Pietroburgo 1903 - Mosca 1979), figlio del precedente. Il suo nome è legato agli algoritmi normali o di M., alla computabilità secondo M., che è equivalente alla ricorsività, [...] in un alfabeto A sono pienamente equivalenti, relativamente ad A, a qualche algoritmo normale su A". Nella sua teoria degli algoritmi M. usa la logica intuizionista con l'aggiunta di una regola di esistenza potenziale (regola di M.). M. ha anche ...
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
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
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...