Algoritmi si Structuri de Date
FISA DISCIPLINEI

  Department Home

Cod: I1103
Titular curs: asist.univ.dr.M.Colhon
Forma de invatamant: la distanta
Ciclul 1 Anul I
Semestrul 1, Curs: 8h
Nr. credite: 5
Profil: informatica
Specializare: informatica
Tip disciplina: obligatorie
Categoria formativa: de specialitate
Obiective:
  • Formarea deprinderilor de utilizare a calculatoarelor.
  • Formarea deprinderilor de scriere a unui algoritm si de analiza a unei probleme.
  • Insusirea tehnicii de elaborare a unui algoritm.
Continutul cursului:
  1. Introducere în algoritmi.
    • Limbaj algoritmic
    • Tipuri de date elementare
    • Instructiuni
    • Subprograme
      • Proceduri
      • Functii
  2. Elemente de analiza algoritmilor
    • Masurarea performantelor unui algoritm
    • Calculul asimptotic
    • Complexitatea problemelor
  3. Algoritmi de sortare
    • Algoritmi de sortare. Enunt
    • Sortarea prin metoda bulelor
    • Sortarea prin insertie
    • Sortarea prin numarare
  4. Algoritmi recursivi
    • Metoda Divide et Impera
      • Problema Turnurilor din Hanoi
    • Cautarea binara
    • Quicksort
  5. Metoda Backtracking
    • Explicarea numelui. Algoritmi cu revenire
    • Principii ale metodei
    • Caracteristici ale metodei
    • Rutina Backtracking
  6. Metoda Greedy
    • Explicarea numelui
    • Descrierea metodei
    • Metoda Greedy. Strategii
      • Strategia 1
      • Strategia 2
    • Probleme pentru care metoda Greedy determina solutia optima
    • Probleme pentru care metoda Greedy nu determina solutia optima
  7. Structuri de date
    • Lista liniara
    • Liste simplu inlantuite
      • Crearea unei liste simplu inlantuite
      • Accesul la un nod al unei liste simplu inlantuite
      • Inserarea unui nod intr-o lista simplu inlantuita
      • Stergerea unui nod dintr-o lista simplu inlantuita
      • Stergerea unei liste simplu inlantuite
    • Stiva
    • Coada
  8. Tabele de dispersie
    • Consideratii teoretice. Tipuri de tabele
    • Functia de dispersie (hashing)
    • Tabela de dispersie
  9. Metoda programarii dinamice
    • Descrierea metodei
    • Cele trei principii fundamentale ale programarii dinamice
    • Aplicatii. Inmultirea optima a unui sir de matrice
  10. Elemente de teoria grafurilor
    • Grafuri neorientate si grafuri orientate
    • Reprezentarea grafurilor neorientate
      • Matricea de adiacenta
      • Listele vecinilor
      • Vectorul muchiilor
    • Graf complet si graf bipartit
    • Parcurgerea grafurilor
      • Metoda de parcurgere in latime BF
      • Metoda de parcurgere in adancime DF
    • Conexitate
  11. Algoritmi pentru prelucrarea grafurilor
    • Caile de cost minim dintr-un varf
    • Caile de cost minim din oricare varf
  12. Arbori
    • Definitii
    • Arborele de acoperire de cost minim
      • Algoritmul lui Prim
      • Algoritmul Kruskal
  13. Arbori binari
    • Definire. Reprezentare
    • Metode de implementare a arborilor binari
    • Operatii cu arbori binari
  14. Arbori binari de cautare
    • Inserarea intr-un arbore binar de cautare
    • Cautarea unui nod de cheie data intr-un arbore binar de cautare
    • Stergerea unui nod de cheie data dintr-un arbore binar de cautare
    • Traversarea unui arbore binar de cautare
Forma de evaluare: examen
Bibliografie:
  1. M. Colhon: Algoritmi si Structuri de date, Editura Sitech, Cod CNCSIS 411, ISBN 978-606-530-585-4, Craiova 2009, 108 pagini
  2. R.D. Vatavu, Proiectarea algoritmilor, www.eed.usv.ro/~vatavu, 2008
  3. C. Bereanu, Complexitatea Calculului, Ed. Sitech, 2000
  4. T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introducere in Algoritmi, Computer Libris Agora, 2000
  5. Tudor S., Cerchez E., Serban M., Informatica, Varianta C++, manual pentru clasa a IX-a, Ed L&S Infomat, Bucuresti, 1999
  6. V. Cristea, I. Athanasiu, E. Kalisz, V. Iorga, Tehnici de programare, Ed. Teora, 1998
  7. Negrescu L., Limbajul C si C++, Ed. Libris, Cluj, 1997
  8. T. Sorin, Tehnici de programare, L & S INFOMAT, 1996
  9. Ivasc C., Pruna M., Bazele informaticii, Ed. Petrion, 1995
  10. R. Graham, D. Knut, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994
  11. Georgescu H., Livovschi L., Analiza si sinteza algoritmilor, Ed. Stiintifica si Enciclopedica, Bucuresti, 1986
  12. Ionescu C., Zsako I., Structuri arborescente, Ed. Tehnica, Bucuresti,1990
  13. Horowitz E., Fundamentals of Programming Languages, Springer Verlag, 1983
  14. Knuth D. E., Tratat de programarea calculatoarelor, vol. I, II, III, Ed. Tehnica, Bucuresti, 1973

Ultima actualizare: Octombrie 2008