Curs
Algoritmi
Gândirea algoritmică permite inginerilor să analizeze și să rezolve probleme computaționale cu un grad de abstractizare ce depășește orice limbaj de programare.
Conținutul cursului
Cursul 1
Introducere
Î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.
Cursul 2
Structuri de date
Î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.
Cursul 3
Analiza algoritmilor
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 arăta cum se pot aplica diferite tehnici, în funcție de tipul algoritmului analizat.
Cursul 4
Greedy
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ă.
Cursul 5
Divide et Impera
Divide et impera este o tehnică de elaborare 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.
Cursul 6
Programarea dinamică
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ă.
Cursul 7
Căutări în șiruri
Căutarea tuturor aparițiilor unui șablon într-un text este o problemă ce apare frecvent, mai ales într-un editor de texte. Algoritmii de căutare în șiruri pot fi folosiți și la căutarea de exemplu a unor șabloane în secvențe ADN.
Cursul 8
Branch and Bound
Această metodă, similară metodei backtracking, 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.
Cursul 9
Algoritmi randomizați
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ă. În acest capitol ne propunem să discutăm despre câteva aplicații ale randomizării.
Cursul 10
Probleme de NP-completitudine
O problemă poate fi rezolvată, reducând problema la alte sub-probleme a căror soluție este cunoscută. Cu toate acestea, metoda funcționează dacă reducerea poate fi făcută în timp polinomial. În caz contrar, problema devine NP-grea adică nu se poate rezolva în timp polinomial.