În primul curs vom ne vom familiariza cu principiile, notaţiile folosite de-a lungul întregului curs. Vom începe printr-o plasare a conceptului de algoritm în raport cu problemele de calcul utilizând un exemplu clasic. Vom prezenta conceptul de pseudocod și de asemenea vom exemplifica. Vom analiza timpul de execuţie al unui anume algoritm prezentând notaţiile generale ce vor fi utilizate în continuare.
În acest curs vom vorbi despre reprezentarea mulţimilor dinamice, folosind structuri de date. Vom începe prin a descrie listele, cu prezentarea unor aplicații practice ale stivelor/cozilor. Vom continua cu o scurtă introducere în teoria grafurilor cu exemple pe cazuri particulare: arbori.
Vom studia diferitele metode matematice pentru analiza eficienţei unui algoritm. Aceasta este mai curând o chestiune de raţionament, intuiţie și experienţă. Pe baza exemplelor alese, vom arata cum se pot aplica diferite tehnici, în funcție de tipul algortimului analizat.
Un algoritm greedy este potrivit atunci când trebuie să luăm o serie de decizii, și anume pe cea
mai convenientă la fiecare moment succesiv. Această alegere este un optim local, iar speranţa este ca, într-un
final să fie obţinută soluţia optim globală.
Pentru algoritmii studiați în acest capitol, va
trebui să determinăm dacă soluţia este sau nu optimă.
Divide et impera este o tehnică de elaborarea a algoritmilor ce constă în:
- Descompunerea problemei ce trebuie rezolvată într-o serie de subprobleme mai mici.
- Rezolvarea succesivă și independentă a fiecăreia din aceste probleme și găsirea unei serii de
subsoluţii.
- Recompunerea subsoluţiilor pentru a găsi soluţia cazului iniţial.
Vom studia o serie de algoritmi ce optimizează timpul de execuție, în comparație cu algoritmii clasici ce rezolvă aceleași probleme.
Programarea dinamică, ca și metoda divide et impera, rezolvă problemele combinând soluţiile subproblemelor. După cum am văzut, algoritmii de divide et impera, partiţionează problemele în subprobleme independente, rezolvă subproblemele în mod recursiv, iar apoi combină soluţiile lor pentru a rezolva problema iniţială. Dacă subproblemele conţin subprobleme comune, în acest caz, este mai bine să folosim tehnica programării dinamice.
Căutarea tuturor aparițiilor unui șablon într-un text este o problemă ce apare frecvent, mai ales într-un editor de texte. În mod obișnuit, un document este tipărit, și un cuvânt sau o succesiune de caractere este căutat la un moment dat de către utilizator. Alt exemplu este următorul: un utilizator
primește un șir de lungime considerabilă din baza de date, și dorește să afle contextul în care apare un
anume cuvânt. Algoritmii de căutare în șiruri pot fi folosiți și la cătarea de exemplu a unor șabloane în
secvențe ADN.
Această metodă, similară metodei backtracking (pe care o vom descrie pe scurt), folosește un arbore pentru stocarea potențialelor soluții pentru o problemă dată. Totuși, metoda oferă flexibilitate în parcurgerea arborelui în sensul că acesta poate fi parcurs în mai multe moduri.
Totodată, metoda permite ierarhizarea nodurilor parcurse, criteriul fiind: cât de promițator (că poate conduce la soluția optimă) este un nod.
Factorul aleatoriu este parte din viața reală. Conceptul este folosit în teoria jocurilor, algoritmi genetici, rețele neurale, etc. La o primă vedere, folosirea numerelor generate aleatoriu poate părea bizară, chiar ilogică. Uneori anumite metode nici nu iși au explicația în modele matematice simple. Dar, teoria probabilităților, a numerelor mari, poate explica majoritatea lucrurilor de neînțeles, precum variațiile vremii, migrarea păsărilor, sau evoluția Planetei. În acest capitol ne propunem să discutăm despre câteva aplicații ale randomizării
O problemă poate fi rezolvată, reducând problema la alte sub-probleme a căror soluție este cunoscută. Cu toate aceasta, metoda funcționează dacă reducerea poate fi făcută în timp polinomial. În caz contrar, problema devin NP-grea adică nu se poate rezolva în timp polinomial. În acest capitol, vom studia câteva cazuri de probleme de tip NP și posibile rezolvări ale acestor.
Tim Roughgarden
Thomas H. Cormen
Răzvan Andonie
Ilie Gârbacea