Titular curs: Lect.univ.Dr. M. Colhon
Forma de invatamant: cursuri de zi
Ciclul 1 Anul III
Semestrul 1, Curs: 28h, Laborator: 28h
Nr. credite: 5
Profil: informatica
Specializare: informatica
Tip disciplina: obligatorie
Categoria formativa: de specialitate
Fisa disciplinei
Continutul cursului
- Introducere în proiectarea algoritmilor (2 ore)
- Obiectul cursului
- Notiunea de algoritm. Caracteristici
- Masina Turing.(4 ore)
- Variante ale modelului de masina Turing
- Masini Turing deterministe si nedeterministe
- Masinile Turing si Limbajele formale
- Verificarea corectitudinii algoritmilor (2 ore)
- Etapele verficarii corectitudinii algoritmilor.
- Analiza complexitatii algoritmilor (2 ore)
- Scopul analizei complexitatii.
- Timpi de executie. Ordin de crestere.
- Analiza algoritmilor nerecursivi (2 ore)
- Estimarea timpului de executie (cazul cel mai favorabil, cazul cel mai defavorabil, cazul mediu)
- Notatii asimptotice (4 ore)
- Notatii o, O, Ω, ω, Θ. Proprietati
- Analiza asimptotica a algoritmilor
- Clase de complexitate
- Analiza algoritmilor recursivi (4 ore)
- Metoda substitutiei înainte/înapoi
- Metoda iteratiei
- Metoda Master
- Arbori de recurenta
- Studiu de caz. Algoritmul mergesort
- Analiza a algoritmilor. Studiu de caz (2 ore)
- Turnurile din Hanoi. Verificarea corectitudinii. Analiza complexitatii
- Ineficienta si necalculabilitate (2 ore)
- Probleme NP-complete (4 ore)
- Algoritmi nedeterministi
- Clase P si NP
- Probleme NP-complete
Curs MAA
Discipline anterioare cerute:
- Algoritmi si Structuri de date
- Programare Procedurala
Forma de evaluare: examen si activitatea din timpul anului
Bibliografie:
- Dumitru Dan Burdescu, Analiza Complexitatii Algoritmilor, Editura Albastra, Cluj Napoca, 1998.
- Mihaela Colhon, Algoritmi si Structuri de date, Editura Sitech, Craiova, Cod CNCSIS 411, ISBN 978-606-530-585-4, Craiova 2009
- Dorel Lucanu, Mitica Craus, Proiectarea algoritmilor, Editura Polirom, Bucuresti, 2008
|
|
