Algoritmy a datové struktury
Šimon Mandlík
Senior Researcher v AVAST (nově Gen Digital)
Připravujeme
Zapoj se do kurzu a odnes si základní algoritmický toolbox kvalitního programátora. Obsah kurzu je navíc vysoce nadčasový, takže se ti bude dlouhodobě hodit ve stále se rozvíjejícím světě informačních technologií.
kteří se zaměřují na design, konstrukci a údržbu systémů a chtějí pochopit a naučit se použít existující implementace různých nástrojů, knihoven a frameworků.
kteří chtějí psát rychlé, efektivní a stručné programy pro zpracování dat, a zároveň potřebují umět vyřešit komplexní algoritmické problémy.
kteří se zabývají přímým programováním produktu, potřebují umět odhadnout efektivitu algoritmu i jeho složitost a zároveň získat nezbytný skillset k řešení obtížnějších problémů.
kteří chtějí získat praktické znalosti nad rámec studia nebo se o problematiku aktivně zajímají a aspirují na pozici programátora, ve které jsou vyžadovány znalosti efektivních algoritmů.
Pronikneš do práce s různými datovými strukturami a zjistíš, jak umí zefektivnit počítačové programy. Zároveň se naučíš implementovat klasické algoritmy a dokážeš snadno vyhodnotit jejich složitost. Naučíš se ladit svoje implementace jak z hlediska korektnosti, tak z hlediska efektivity. Seznámíš se například s řadícími algoritmy, hladovými algoritmy, grafy, dynamickým programováním anebo hashovacími technikami.
Osvoj si nezbytné znalosti, které ti pomohou nastartovat tvoji programátorskou kariéru.
Získáš základy algoritmizace a její nejdůležitější paradigmata. Čeká tě jak analýza asymptotické složitosti, tak rekurzivní algoritmy, binární vyhledávání a třídící algoritmy. Pochopíš, jak fungují základní datové struktury a naučíš se principy efektivní manipulace s daty.
Získáš užitečné znalosti o stromových strukturách a grafech, jejich taxonomii, vlastnostech a jejich praktickém využití. Dozvíš se, jak najít nejkratší cestu v grafu, anebo jak fungují binární haldy.
Praktické ukázky tě naučí implementovat řešení s využitím dynamického programování pomocí top-down a bottom-up přístupu. Dozvíš se o možnostech optimalizování vyhledávání, jak se orientovat v acyklických grafech a další užitečné algoritmické přístupy, které se vyplatí znát.
- Prerekvizity kurzu
- Proč se učit algoritmy?
- Osnova
- Komunikace: dotazy, feedback, materiály
- Podmínky splnění kurzu
- Domácí úlohy
- Ukázka odevzdávacího systému
- Odevzdání zkušební úlohy ve dvou jazycích, čtení vstupu
Úkol: Zřízení účtu v odevzdávacím systému a zkušební úloha
Zjistíš, co tě v kurzu čeká a proč je dobré se tématu kurzu věnovat. Získáš přístup k učebním materiálům a založíš si účet v odevzdávacím systému.
- Motivace — Úsek s největším součtem
- Výpočetní model
- Zavedení pojmu (časové) asymptotické složitosti, Big O, Theta, Omega
- Třídy složitosti, praktické porovnávání, konstanty
- Cvičení odhadování složitosti u různých jednoduchých algoritmů
- Rozšíření na paměťovou složitost
Úkol:
1. Procvičení ad-hoc řešení praktického problému.
2. Úloha procvičující manipulaci s jednorozměrným polem.
Zjistíš, co jsou to asymptotické časové a paměťové složitosti, dokážeš se orientovat v Big-O notaci a snadno odhadneš složitost algoritmu.
- Příklady použití v reálném světě
- Detaily a live implementace
- Časová složitost binárního vyhledávání
- Amortizovaná složitost a real-time systémy
- Příklad s nafukováním pole
- Průměrná složitost
Úkol: Procvičení binárního vyhledávání na praktické úloze.
Seznámíš se s binárním vyhledáváním, jeho výhodami a detaily implementace. Cizí ti už nebudou ani pojmy amortizované a průměrné složitosti.
- Definice problému
- Bubble sort
- Selection sort
- Insertion sort (live implementace)
- Stabilita třídicího algoritmu
- Neporovnávací varianty Counting sort a Radix sort
Úkol: Procvičení specifik řadících algoritmů na praktické úloze.
Už víš, jak je definován řadící problem a zároveň znáš jednoduché řadící algoritmy a zvládneš je naimplementovat. Dokážeš specifické případy řešit za pomocí rychlejších řadících algoritmů.
- Úvod do rekurze
- Rozděl a panuj
- Příklad: Karatsubův algoritmus pro násobení
- Příklad: Hanojské věže
- Merge sort
- Quick sort (live implementace)
- Quickselect
- Porovnání řadicích algoritmů a jejich praktické použití
- Odhad složitosti rekurzivních algoritmů a Master theorem
- Dolní odhad složitosti porovnávacího třídění
Už víš, co je to rekurzivní paradigma “rozděl a panuj”. Dokážeš určit, jak mají efektivně fungovat třídicí algoritmy Merge sort a Quick sort a zvládneš je naimplementovat.
- Abstraktní datová struktura
- Jednoduché příklady datových struktur: průměr, prefixové součty
- Spojový seznam a porovnání s polem (live implementace)
- Fronta a zásobník, rozdíly mezi nimi
- Implementace v poli a spojovým seznamem
- Zásobník a rekurze, role zásobníku v počítačovém programu
Úkol: Procvičení konceptů fronty a zásobníku na praktické úloze.
Seznámíš se s abstraktní datovou strukturou a jejím rozhraním, poznáš spojové seznamy a dokážeš využít jejich výhody oproti klasickým polím. Budeš se orientovat v základních datových strukturách, frontě a zásobníku a budeš vědět, jaké operace nabízí.
- Příklady z reálného světa
- Definice stromu a názvosloví
- Taxonomie, slovník pojmů
- Matematické vlastnosti stromů
- Reprezentace stromu v paměti
- Průchody stromem — inorder, preorder, postorder, levelorder (live implementace)
- Backtracking a hry
Úkol: Procvičení stromových struktur na praktické úloze.
Teď už víš, co to znamená strom a jaké jsou jeho varianty a vlastnosti. Dokážeš ho použít v problémech z praxe a znáš techniky, které ti pomohou s jeho implementací.
- Binární vyhledávací strom, definice a základní operace, složitosti
- Implementace BST (live)
- TreeSort
- Vyvážené stromy
- AVL tree
- Ostatní příklady vyhledávacích stromů: B stromy, Red-Black Tree, (a-b), Splay, Treap, a další
Už víš, jaké jsou nejznámější vyhledávací stromy a jejich vlastnosti. Chápeš využití vyhledávacích stromů v praxi a proč je důležité, aby byl vyhledávací strom vyvážený.
- Motivace, definice binární haldy
- Implementace (live coding)
- Odvození složitosti
- Heap sort
- Pokročilé haldy: d-ary, binomial, Fibonacci
Úkol: Procvičení prioritní fronty na praktické úloze.
Víš, jak funguje binární halda, jak ji implementovat a znáš její časovou a paměťovou složitost. Znáš vylepšené verze hald a procvičíš si prioritní fronty na praktické úloze.
- Příklady z reálného světa
- Definice grafu a názvosloví
- Taxonomie a speciální příklady
- Základní vlastnosti grafů
- Reprezentace grafu v paměti
Chápeš pojem grafu, jeho definici i využití v reálném světě. Dokážeš rozlišit různé typy grafů, znáš názvosloví a víš, jak efektivně graf uložit do paměti.
- Průchod grafu do šířky (BFS), implementace a složitost
- Dosažitelnost
- Hledání (slabých) komponent souvislosti
- Sled, tah, cesta
- Nejkratší cesta v neváženém grafu
- Průchod grafu do hloubky (DFS), implementace a složitost
- Hledání cyklu v grafu
- (Ne)aplikovatelnost na předchozí úlohy
Úkol: Procvičení průchodů grafu na praktické úloze.
Už znáš dva různé přístupy k průchodu grafu i jejich specifika. Dokážeš implementovat prohledávání do hloubky i do šířky a dobře víš, k čemu jsou tyto algoritmy vhodné.
- Definice hladového algoritmu, optimalita
- Příklady hladových algoritmů
- Minimální kostra grafu, definice a motivace
- Primův algoritmus (live implementace)
- Kruskalův algoritmus
- Union-find datová struktura a implementace Kruskalova algoritmu
Úkol: Procvičení nalezení minimální kostry na praktické úloze.
Rozšíříš své povědomí o „hladových“ algoritmech a víš, jaké jsou jejich vlastnosti. Zároveň dokážeš najít minimální kostru grafu a tuto znalost využít i v praxi.
- Vážený graf
- Nejkratší sled, nejkratší cesta
- Varianty úlohy
- Dijkstrův algoritmus, implementace, složitost
- A* algoritmus
- Floyd-Warshallův algoritmus, implementace, složitost
- Bellman-Fordův algoritmus, implementace, složitost
Úkol: Procvičení nalezení nejkratší cesty v grafu na praktické úloze.
Máš představu o tom, co obnáší úloha nejkratší cesty v grafu, znáš nejdůležitější algoritmy s tím spojené i jejich složitosti a předpoklady. Vše pak dokážeš implementovat do reálného příkladu.
- Motivace a definice
- Ukázka jednodušších úloh: Fibonacciho posloupnost, kombinatorická čísla, vyvážená binární matice (live coding)
- Implementace top-down, bottom-up
- Optimální vyhledávací strom
- Příklady, které už známe
Úkol: Procvičení dynamického programování na praktické úloze.
Seznámil*a ses s dynamickým programováním a víš, kde ti pomůže, a znáš dva přístupy k implementaci a jejich (ne)výhody.
- Acyklické grafy, definice a motivace
- Detekce cyklů
- Topologické uspořádání pomocí DFS, Kahnův algoritmus
- Dynamické programování na DAG
- Nejdelší rostoucí podposloupnost
Úkol: Procvičení nalezení topologického uspořádání na praktické úloze.
Pronikneš do speciálních tříd acyklicky orientovaných grafů, vyznáš se v jejich typologickém uspořádání a v tom, jak jej vytvořit.
- Úloha batohu (knapsack): verze s nekonečnými předměty a binární verze, interpretace jako DAG
- Nejdelší společná podposloupnost
- Rozšíření na edit distance
Znáš komplexní případy, kdy se používá dynamické programování.
- Motivace, asociativní vs. adresní vyhledávání
- Datové struktury slovník a množina, příklady v programovacích jazycích
- Definice a vlastnosti hashovací funkce
- Perfect hashing
- Řešení kolizí: chaining, 2-choice hashing, open-address: linear probing, double hashing, hybrids
- Rozšiřování kapacity: inkrementální hashování, rozšiřitelné hashování
- Univerzální hashování
Poznáš, jak se liší asocitativní a adresní vyhledávací struktury. Zároveň chápeš, jaké jsou důležité vlastnosti hashovací funkce a jakou to hraje roli v implementaci slovníku a dalších struktur. Poradíš si s dalšími praktickými aspekty při implementaci slovníku a vyřešíš případné kolize i rozšiřování kapacity.
- Definice a motivace
- Odhad náležitosti: Bloom Filter
- Odhad velikosti množiny: Linear counting, k-minimum value
- Odhad frekvence: Count-Min Sketch
Dozvíš se, jak používat hashovací techniky i mimo nejrozšířenější slovníky a budeš chápat, jak pravděpodobnostní datové struktury šetří paměť i čas s ohledem na přesnost výsledků.
- Teorie výpočetní složitosti
- NP-úplná úloha
- Převody úloh
- Příklady NP-úplných úloh
- Řešení hrubou silou (bruteforce)
- Hladové (greedy) algoritmy
- Heuristické algoritmy
- Aproximační algoritmy
Úkol: Procvičení bruteforce řešení a backtrackingu na praktické úloze.
Víš, že existují úlohy, které nemají rychlé řešení. Zároveň budeš znát základní představitele třídy NP-úplných úloh, budeš mít základní povědomí o převodech úloh a také se dozvíš o přístupech k praktickým řešením NP-úplných úloh.
- Příprava na praktickou část přijímacích pohovorů
- Dobré zdroje na procvičování
- Společné řešení vybraných úloh na přijímacích pohovorech
- QA session
Budeš vědět, co očekávat od praktické části programovacího interview, které často zahrnuje live-coding a řešení algoritmických problémů. Zjistíš, kde se dají najít další informace, abys dokázal*a výběrovým řízením úspěšně projít.
Vyplň registrační formulář a připoj se k nám!
Náš tým konzultantů z robot_dreams Czech se s tebou spojí co nejdříve,
abys získal všechny potřebné detaily o obsahu kurzu a jeho ceně.