Tehnici de programare

Acest curs se adreseaza studentilor de anul I, semestrul II ai Sectiei de Calculatoare cu predare in limba engleza.

Se prezinta elemente de proiectarea algoritmilor fundamentali cu implementari in limbajul C standard.

• Manual principal:
  Thomas H.Cormen et al, Introduction to Algorithms, MIT Press, 1990. Traducere in limba romana prin Editura Computer Libris Agora.

• 1: Introducere.
  Capitolele 1 si 2 din manualul cursului.
  Conceptul de algoritm. Exemplu: sortarea prin insertie. Probleme in studiul algoritmilor. Notatia pseudocod. Analiza algoritmilor. Exemplu: analiza sortarii prin insertie. Conceptul de recursivitate. Metoda "divide et impera". Sortarea prin interclasare. Analiza sortarii prin interclasre.
  
• 2: Tehnici de rezolvare a recurentelor. Exemple de algoritmi.
  Capitolul 4 din manualul cursului.
  Notatii pentru cresterea functiilor. Metoda susbstitutiei. Exemplu: analiza sortarii prin interclasare. Metoda iteratiei. Exemplu: analiza sortarii prin interclasare. Metoda master. Algoritm eficient de calculul al puterii. Varianta recursiva si iterativa. Cautare binara. Interclasare. Problema 1.3-7 din manual. Sortare prin interclasare. Varianta iterativa.
  
• 3: Corectitudinea algoritmilor. Sortare rapida. Testarea algoritmilor.
  Capitolul 8 din manualul cursului.
  Corectitudinea algoritmului lui Euclid. Corectitudinea algoritmului eficient de calcul al puterii. Corectitudinea algoritmului de evaluare a polinoamelor. Turnurile din Hanoi. Sortare rapida. Algoritmul de baza. Operatia de partitionare. Analiza sortarii rapide. Versiuni aleatoare ale sortarii rapide. Problema selectiei. Testarea algoritmilor. Exemplu: algoritmul lui Euclid si cautarea binara.
  
• 4: Tipuri de date. Liste inlantuite.
  Multimi dinamice (pag.168-170 din manual). Paragraful 11.2.
  Tipuri de date. Clasificare. Tipuri de date abstracte. Exemplu: tipul logic. Implementarea tipurilor abstracte de date. Multimi dinamice. Liste. Cautarea intr-o lista. Inserarea intr-o lista. Stergerea dintr-o lista. Folosirea santinelelor. Implementarea listelor.
  
• 5: Stive si cozi. Alocarea memoriei dinamice.
  Paragrafele 11.1 si 11.3 din manual.
  Definirea stivelor. Algoritmi pentru stive. Definirea cozilor. Algoritmi pentru cozi. Implementarea stivelor. Alocarea dinamica a memoriei. Algoritmi de alocare dinamica a memoriei. Implementarea alocarii dinmice a memoriei.
  
• 6: Definirea grafurilor si arborilor. Reprezentarea arborilor.
  Paragrafele 5.4, 5.5 si 11.4 din manual.
  Definirea grafurilor. Cai in grafuri. Grafuri conexe. Subgrafuri. Arbori liberi. Proprietati. Arbori cu radacina. Arbori binari. Arbori pozitionali. Reprezentarea arborilor binari. Reprezentarea arborilor cu radacina. Traversarea arborilor binari. Implementarea arborilor binari.
  
• 7: Metoda programarii dinamice.
  Capitolul 16 din manual.
  Definirea programarii dinamice. Pasii de aplicare ai programarii dinamice. Problema inmultirii unui sir de matrici. Contorizarea numarului de modalitati de alocare a parantezelor. Rezolvarea problemei inmultirii unui sir de matrici. Afisarea solutiei optime. Implementarea algoritmului de rezolvre a problemei inmultirii unui sir de matrici. Alte probleme. Problema celui mai lung subsir comun.
  
• 8: Metoda "greedy".
  Capitolul 17 din manual (fara paragrafele 17.4 si 17.5).
  Conceptul de algoritm "greedy". Problema selectiei activitatilor. Algoritm "greedy" pentru problema selectiei activitatilor. Corectitudine. Caracteristici ale algoritmilor "greedy". Problema rucsacului. Corectitudinea strategiei "greedy" pentru varianta continua a problemei rucsacului. Implementarea algoritmilor "greedy" pentru problema activitatilor si varianta continua a problemei rucsacului.
  
• 9: Reprezentarea si parcurgerea grafurilor.
  Capitolul 23 din manual (fara paragrafele 23.4 si 23.5).
  Definirea grafurilor. Matrice de adiacenta. Liste de adiacenta. Parcurgerea intai in latime: concepte si algoritm. Drumuri minime. Arbori de parcurgere in latime. Parcurgerea intai in adancime: concepte si algoritm. Proprietati ale parcurgerii intai in adancime. Implementarea parcurgerii intai in adancime.
  
• 10: Metoda cautarii cu revenire ("backtracking").
  Conceptul de cautare cu revenire. Algoritm iterativ de cautare cu revenire. Rafinarea algoritmului iterativ de cautare cu revenire. Algoritm recursiv de cautare cu revenire. Problema reginelor. Rezolvarea prin cautare cu revenire iterativa a problemei reginelor. Varianta discreta a problemei rucsacului. Rezolvarea prin cautare cu revenire recursiva a variantei discrete a problemei rucsacului. Compararea cautarii cu revenire cu cautarea in grafuri. Imbunatatirea rezolvarii variantei discrete a problemei rucsacului. Eficienta cautarii cu revenire.