Scopul disciplinei

Sinteza si analiza de algoritmi cu aplicatii in tehnica de calcul; combinatorica, arbori, grafuri; complexitate a algoritmilor.

Programa analitica a activitatilor didactice

CURS

Algoritmi: istoric, definitii, clasificari, complexitate.

Algoritmi liniari. Algoritm Strassen pentru inmultirea a doua matrici. Algoritm de inversare a unei matrici.

Algoritm de triunghiularizare matrici. Rezolvare de sisteme de ecuatii liniare. Algoritm pentru Transformata Fourier Rapida.

Transformata Fourier Rapida generalizata la reprezentarea numerelor. Algoritmul de imnultire Schonhage-Strassen.

Aritmetica modulara. Calculul resturilor. Teorema chineza a resturilor. Algoritmi de trecere.

Cautare secventiala si ordonata. Sortare.

Sortare pe structuri statice: sortare prin numarare, sortare prin metoda bubblesort, sortare prin insertie, sortare prin selectie, quicksort.

Sortare pe structuri dinamice: functii si algoritmi de hash-aj. Arbori: definitii, explorari; arbori de cautare, heapsort.

Sortare topologica, algoritm Dijkstra, arbore minim de acoperire, algoritmul Prim si algoritmul Kruskal.

Strategii in sinteza de algoritmi.

LABORATOR

Transformata Fourier discretã.
Cãutare si sortare pe structuri de date statice.
Cãutare si sortare pe structuri de date dinamice.
Reprezentare de arbori si prelucrãri pe arbori.
Reprezentare de grafuri si prelucrãri pe grafuri

Relatia cu alte cursuri

Este necesara legatura cu materii ca Tehnica Programarii Calculatoarelor, Teoria Transmisiunii Informatiilor si Ingineria Software.

Bibliografie :

Leon Livovschi, Horia Georgescu – "Sinteza si analiza algoritmilor" Editura Stiintifica Bucuresti 1986

Alfred Aho, John Hopcroft, Jeffrez Ullman – "Data Structures and Algorithms, Addison-Wesley 1983

Stefan Stãncescu, Marinel Alangiu, Tiberiu Seceleanu –"Teoria algoritmilor" îndrumar de laborator, UPB 1997