Anul II, AA - Analiza Algoritmilor
Curs: Cristian Giumale
Materiale de curs:
- Introducere in analiza algoritmilor [pdf]
- Analiza amortizata [pdf]
- Calculabilitate [pdf]
- Decidabilitate [pdf]
- Clase de probleme [pdf]
- Scurte exemple de algoritmi [pdf]
- Demonstrarea decidabilității [pdf]
- Determinism [pdf]
- Determinarea complexității [pdf]
- Notații de complexitate [pdf]
- Reduceri polinomiale [pdf]
- Teorema lui Cook [pdf]
- Demonstrații de corectitudine [pdf]
- Inducție structurală [pdf]
- Abstract Data Types [pdf]
- Amortized Analyis [pdf]
- Asymptotic Notations [pdf]
- Common types of recurrences [pdf]
- Complexity classes and polynomial reductions [pdf]
- Problema lui Dr. Who [pdf]
- Loop Invariants [pdf]
- Computing amortized costs for tables with expansion and contraction [pdf]
- Propositional logic, SAT, NP-complete problems [pdf]
- Turing machines [pdf]
- Undecidability [pdf]
Laboratoare:
- Laborator 1 - Algoritmi [doc]
- Laborator 2 - Determinarea complexității unui algoritm [doc]
- Laborator 2 - Complexitatea algoritmilor [pdf]
- Laborator 3 - Corectitudinea algoritmilor [doc]
- Laborator 3 - Metode de rezolvare a recurențelor de complexitate [pdf]
- Laborator 4 - Tipuri de date abstracte [doc]
- Laborator 4 - Metoda Master [pdf]
- Laborator 6 - Metode de demonstrare a corectitudinii parțiale a algoritmilor [pdf]
- Laborator 7 - Inducție structurală [pdf]
- Laborator 8 - Clase de probleme [pdf]
Alte materiale:
- Algoritmi de analizat [pdf]
- Metode de a demonstra (ne)decidabilitatea unor probleme [pdf]
- AA problem pool [pdf]
- Metode de determinare a complexității algoritmilor [pdf]
- Notații de complexitate, complexitatea algoritmilor [pdf]
- Tema 2 AA [pdf]
- Tema de recuperare AA [pdf]
- Test 2 AA [pdf]
- Test 1 AA [pdf]
- Test 2 AA [pdf]
- Tema detectare obstacole C# (rar)
- Exemplu subiect examen (1) [pdf]
- Exemplu subiect examen (2) [pdf]
- Exemplu subiect examen (3) [pdf]
- Exemplu subiect examen (4) [pdf]
- Lista exercitii [pdf]
- Exerciții complexitate și recursivitate [pdf]
- Exerciții recurențe [pdf]
- Exerciții teorema master [pdf]
- Exemplu tema 1 [pdf]
- Exemplu tema 2 [pdf]
- Cod backtracking recursiv [c]
- Notatii asimptotice [zip]
- Exemplu cod mergesort [pdf]