Kurz navazuje na základy programování ALG119000 a pracuje teoretickými aspekty programování, seznámení se s různými algoritmy a jejich složitostí.
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
The course is a follow-up to the programming introductory course ALG119000. The aim is to look into the theoretical aspects of programming, learn about various well-known algorithms and data organization methods and evaluate their complexity in practice.
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
Cíl předmětu -
Základy programování Psaní jednoduchých algoritmů, opakování z přednášky ALG119000.
Lineární datové struktury Schéma operační paměti. Reprezentace pole, spojový seznam. Fronta a zásobník a příklady.
Nelineární datové struktury Definice stromu. Halda a k čemu je. Graf a základní pojmy.
Program a programovací techniky Definice funkce. Rekurze. Převod mezi rekurzivním programem a sekvenčním výpočtem. Algoritmy podle metody.
Složitost Měření velikosti problému a třída složitosti. Příklad odhadu složitosti na vybraném algoritmu. Paměťová složitost algoritmu.
Vyčíslitelnost Turingův stroj. Základní pojmy vyčíslitelnosti a rozhodnutelnosti. Co je vyřešení a ověření problému.
Třídicí algoritmy Třídicí algoritmy s kvadratickou složitostí. Optimalizované třídicí algoritmy. Důkaz, že třídicí algoritmus má složitost minimálně N log N.
Grafy Graf a základní pojmy. Reprezentace grafu v algoritmu. Prohledávání do hloubky. Prohledávání do šířky. Nejkratší cesta. Hledání mostů. Minimální kostra. Důkaz obarvení rovinného grafu 5 barvami.
Poslední úprava: Podolník Aleš, Mgr., Ph.D. (29.05.2025)
Programming basics Simple algorithms, review of knowledge from ALG119000.
Linear data structures Memory addressing, values and pointers. Arrays, lists representation, linked list. Queue, stack and examples.
Nonlinear data structures Tree definition. Heap and applications. Basics of graph nomenclature.
Program and programming techniques Function definition. Recursion. Rewriting recursion to sequential algoritm. Algorithms defined by a method.
Complexity Problem size and complexity class. Determination of complexity class on a simple algorithm. Complexity in space.
Computatibility Turing machine. Basics of computability. Difference between solution and validation.
Sorting algorithm Quadratic sorting. Optimized sorting. Proof of N log N sorting complexity.
Graphs Graphs and basic definition. How to represent a graph. Depth-first search. Breadth-first search. Shortest path. Bridges. Minimal spanning tree. 5-color theorem proof.
Poslední úprava: Podolník Aleš, Mgr., Ph.D. (29.05.2025)
Literatura -
Töpfer, P.: Algoritmy a programovací techniky, Prometheus 1995
Wirth, N.: Algorithms + Data Structures = Programs, Prentice-Hall 1975 (slov. překlad: Algoritmy a štruktúry údajov, Alfa 1988)
Knuth, D. E.: The Art of Computer Programming, Vol 1,2,3
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
Wirth, N.: Algorithms + Data Structures = Programs, Prentice-Hall 1975
Knuth, D. E.: The Art of Computer Programming, Vol 1,2,3
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
Metody výuky
Pravidelné přednášky a praktická programovací cvičení.
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
Vstupní požadavky -
Součástí kurzu jsou programovací úlohy, proto je třeba umět programovat v Pythonu (viz. předcházející kurz ALG119000).
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
The course contains programming exercises and assumes at least basic knowledge of Python (see the preceding course ALG119000).
Poslední úprava: Švarný Petr, Mgr., Ph.D. (20.01.2021)
