Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (23.09.2019)
Algoritmy a jejich efektivita.
- Algoritmus - vlastnosti, důkaz správnosti, porovnávání kvality algoritmů.
- Časová a paměťová složitost algoritmů, asymptotická složitost, notace „velké O“.
- Složitost algoritmu v nejhorším, nejlepším a průměrném případě.
Základní algoritmy a techniky.
- Dělitelnost - Eukleidův algoritmus, prvočíselný rozklad.
- Prvočísla - test prvočíselnosti, Eratosthenovo síto.
- Rozklad čísla na cifry, převody mezi číselnými soustavami.
- „Dlouhá čísla“ - uložení, operace.
- Hornerovo schéma, rychlé umocňování.
Základní datové struktury.
- Vyhledávání v poli - sekvenční, binární.
- Abstraktní datové typy: zásobník, fronta, prioritní fronta, slovník.
- Hešovací tabulky - princip, řešení kolizí.
- Halda. Binární vyhledávací strom, princip vyvažování.
Třídění.
- Třídění čísel v poli - přímé metody (SelectSort, InsertSort, BubbleSort).
- Haldové třídění (HeapSort), QuickSort.
- Složitost problému vnitřního třídění.
- Přihrádkové třídění (CountingSort, BucketSort, RadixSort).
- Poznámka o vnějším třídění.
Rekurze.
- Rekurze - princip, příklady, efektivita.
- Binární strom - reprezentace, prohledávání, použití.
- Reprezentace aritmetického výrazu binárním stromem.
- Notace aritmetického výrazu (infix, prefix, postfix) - vyhodnocení, převody.
- Obecný strom - reprezentace, průchod, použití.
Prohledávání stavového prostoru.
- Rekurzivní algoritmy založené na zkoušení všech možností - backtracking.
- Prohledávání do hloubky a do šířky - princip, použití, realizace.
- Zrychlení pomocí ořezávání a heuristik.
- Strom hry, algoritmus minimaxu, alfa-beta prořezávání.
Základní grafové algoritmy.
- Prohledávání grafů do hloubky a do šířky a jejich aplikace.
Obecné metody návrhu algoritmů.
Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (23.09.2019)
Algorithms and their efficiency.
- Algorithm - properties, correctness, efficiency comparison.
- Time and space complexity, asymptotic complexity, Big O notation.
- Worst case, best case and average case analysis.
Basic algorithms and techniques.
- Divisibility - Euclid's algorithm, prime factorization.
- Prime numbers - primality testing, the sieve of Eratosthenes.
- Decomposing numbers into digits, numeral systems conversion.
- Higher-precision arithmetic ("long numbers").
- Horner's scheme, fast exponentiation.
Basic data structures.
- Array searching - sequential, binary.
- Abstract data types: stack, queue, priority queue, dictionary.
- Hash tables - principle, resolving collisions.
- Heap. Binary search tree, balancing principle.
Sorting.
- Internal sorting - direct methods (SelectSort, InsertSort, BubbleSort).
- Lower bounds for sorting.
- Sorting in linear time (CountingSort, BucketSort, RadixSort).
- Note about external sorting.
Recursion.
- Recursion - principle, examples, efficiency.
- Binary tree - representation, searching, applications.
- Representing arithmetic expressions through binary trees.
- Infix, prefix and postfix notations - evaluation, conversion.
- General trees - representation, traversal, applications.
State space search.
- Depth first search (DFS) and breadth first search (BFS) - principle, applications, implementation.
- Improving performace through pruning and heuristics.
- Game tree, minimax, alpha-beta pruning.
Basic graph algorithms.
- Representation of graphs.
- DFS, BFS and their applications.
General methods of algorithms design.
- Speeding by precomputation.
|