Analiza si proiectarea algoritmilor - Analiza si Proiectarea Algoritmilor

Extras din document

1. Preliminarii 1.1 Ce este un algoritm? 1.2 Eficienta algoritmilor 1.3 Cazul mediu si cazul cel mai nefavorabil 1.4 Operatie elementara 1.5 De ce avem nevoie de algoritmi eficienti? 1.6 Exemple 1.7 Exercitii Abu Ja`far Mohammed ibn Musa al-Khowarizmi (autor persan, sec. VIII-IX), a scris o carte de matematica cunoscuta in traducere latina ca “Algorithmi de numero indorum”, iar apoi ca “Liber algorithmi”, unde “algorithm” provine de la “al-Khowarizmi”, ceea ce literal inseamna “din orasul Khowarizm”. In prezent, acest oras se numeste Khiva si se afla in Uzbechistan. Atat al-Khowarizmi, cat si alti matematicieni din Evul Mediu, intelegeau prin algoritm o regula pe baza careia se efectuau calcule aritmetice. Astfel, in timpul lui Adam Riese (sec. XVI), algoritmii foloseau la: dublari, injumatatiri, inmultiri de numere. Alti algoritmi apar in lucrarile lui Stifer (“Arithmetica integra”, Nürnberg, 1544) si Cardano (“Ars magna sive de reguli algebraicis”, Nürnberg, 1545). Chiar si Leibniz vorbeste de “algoritmi de inmultire”. Termenul a ramas totusi multa vreme cu o intrebuintare destul de restransa, chiar si in domeniul matematicii. Kronecker (in 1886) si Dedekind (in 1888) semneaza actul de nastere al teoriei functiilor recursive. Conceptul de recursivitate devine indisolubil legat de cel de algoritm. Dar abia in deceniile al treilea si al patrulea ale secolului nostru, teoria recursivitatii si algoritmilor incepe sa se constituie ca atare, prin lucrarile lui Skolem, Ackermann, Sudan, Gödel, Church, Kleene, Turing, Peter si altii. Este surprinzatoare transformarea gandirii algoritmice, dintr-un instrument matematic particular, intr-o modalitate fundamentala de abordare a problemelor in domenii care aparent nu au nimic comun cu matematica. Aceasta universalitate a gandirii algoritmice este rezultatul conexiunii dintre algoritm si calculator. Astazi, intelegem prin algoritm o metoda generala de rezolvare a unui anumit tip de problema, metoda care se poate implementa pe calculator. In acest context, un algoritm este esenta absoluta a unei rutine. ...