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]