ADS - Seznam otazek a materialu
📚 Algoritmy a datové struktury
1. ADS 1 a 2
2. ⏳ Časová a prostorová složitost algoritmů
- Odkaz 📄46
- Čas a prostor výpočtu pro konkrétní vstup
- Časová a prostorová složitost algoritmu
- Měření velikosti dat
- Složitost v nejlepším, nejhorším a průměrném případě
- Asymptotická notace
- 📄50
3. 🧠 Třídy složitosti
- Odkaz 1 📄476
- Odkaz 2
- Třídy P a NP - 🎥 YouTube video
- Převoditelnost problémů, NP-těžkost a NP-úplnost
- Příklady NP-úplných problémů a převodů mezi nimi
- 📄468
4. ⚔️ Metoda "rozděl a panuj" (⚠️ Bylo minule)
- Odkaz
- Princip rekurzivního dělení problému na podproblémy
- Výpočet složitosti pomocí rekurentních rovnic
- Master theorem (kuchařková věta)
- Aplikace:
- Mergesort
- Násobení dlouhých čísel
5. 🌳 Binární vyhledávací stromy
- Odkaz 📄185
- Definice vyhledávacího stromu
- Operace s nevyvažovanými stromy
- 📄188
- AVL stromy (definice) 📄191
6. 🌀 Třídící algoritmy
Mergesort by asi taky bylo dobry umet
- Odkaz
- Primitivní třídicí algoritmy (Bubblesort, Insertsort)
- Quicksort
- Dolní odhad složitosti porovnávacích třídicích algoritmů