Základy algoritmizace, cvičení
13. cvičení 15-23.5.2018
- Zpracování aritmetických výrazů - pokračování
- Převod infixové notace na postfixovou nebo na strom + složitost
- Vyhodnocení aritmetického výrazu zadaného v infixové notaci.
12. cvičení 9-10.5.2018
- Zpracování aritmetických výrazů
- Reprezentace aritmetického výrazu pomocí stromu nebo pomocí řetězce v infixové, prefixové či postfixové notaci.
- Výpis stromu v postfixé, infixové nebo prefixové notaci + složitost
- Převod postfixové notace na strom + složitost
- Vyhodnocení aritmetického výrazu uloženého ve stromě + složitost
- Vyhodnocení aritmetického výrazu zadaného v postfixové notaci + složitost
11. cvičení 2-3.5.2018
- Dynamické programování - pokračování
- dokončení z minulého cvičení: Úloha výpočtu editační vzdálenosti dvou řetězců - různé způsoby + složitost (v některých skupinách)
- Úloha sestrojení optimálního binárního vyhledávacího stromu - různé způsoby + složitost
10. cvičení 24-26.4.2018
- Dynamické programování
- Výpočet n-tého Fibonacciho čísla - různé způsoby + složitost
- Výpočet největšího společného dělitele dvou celých čísel - různé způsoby + složitost
- Úloha automatu na mince - různé způsoby + složitost
- Úloha výpočtu editační vzdálenosti dvou řetězců - různé způsoby + složitost (v některých skupinách)
9. cvičení 17-19.4.2018
- Pokročilejší metody třídění pole
- Metoda třídění haldou + složitost (v některých skupinách)
- Metoda třídění sléváním + složitost (v některých skupinách)
- Metoda rychlého třídění (quickSort) + složitost
- s využitím rekurze
- s využitím zásobníku
- Metoda vyhledání k-tého nejmenšího prvku (v některých skupinách)
- Metoda přihrádkového třídění - princip a příklad (v některých skupinách i kód)
8. cvičení 10-12.4.2018
- Diskuse minulého domácího úkolu (Prohledávání stavového prostoru)
- Doplnění: Procházka šachovým koněm po šachovnici (aby navštívil každé pole právě jednou)- pseudokód a složitost (v některých skupinách).
- Přímé metody třídění pole (a spojového seznamu)
- Metoda přímého výběru minima (různé varianty) + složitost
- Metoda přímého vkládání (různé varianty) + složitost
- Metoda bublinkového třídění (různé varianty, třídění třesením) + složitost
- Pokročilejší metody třídění pole (nebo spojového seznamu)
- Metoda třídění binárním vyhledávacím stromem (postup + složitost)
- Metoda třídění haldou + složitost (v některých skupinách)
- Metoda třídění sléváním (postup + složitost) (v některých skupinách)
7. cvičení 3-5.4.2018
- Diskuse minulého domácího úkolu (Dijkstrův algoritmus).
- Prohledávání stavového prostoru
- Stavový prostor, jeho reprezentace, příklady.
- Prohledávání do hloubky pomocí rekurzivní metody (backtracking)
- Obecně: pseudokód.
- Úloha N dam (a její složitost).
- Procházka šachovým koněm po šachovnici (aby navštívil každé pole právě jednou)- pseudokód (v některých skupinách).
- Vlk, koza a zelí, Misionáři a lidožrouti - myšlenka (v některých skupinách).
- Prohledávání do šířky pomocí fronty
- Obecně: pseudokód.
- Úloha hledání nejkratší cesty koněm po šachovnici ze startovního pole do všech ostatních polí.
6. cvičení 17-29.3.2018
- Diskuse minulého domácího úkolu.
- Graf a jeho reprezentace v programu.
- Prohledávání grafu do šířky pomocí fronty a jeho aplikace na hledání komponent souvislosti grafu - pseudokód (v některých skupinách).
- Dijkstrův algoritmus pro hledání nejkratší cesty v hranově ohodnoceném grafu.
5. cvičení 20-22.3.2018
- Diskuse minulého domácího úkolu.
- Metoda rozděl a panuj: obecný princip a příklady.
- Postavení binárního vyhledávacího stromu na základě uspořádaného pole klíčů.
- Vyhledávání půlením intervalů (binární vyhledávání)
- Hanojské věže
4. cvičení 13-15.3.2018
- Diskuse minulého domácího úkolu (binární vyhledávací strom).
- Příklady implementace vybraných metod (destruktor, vypisOdsazene ap.).
- Binární vyhledávací strom
- Další pojmy: Prohledávání stromu (nebo grafu) do hloubky (backtracking) a prohledávání do šířky.
- Varianty:
- Prohledávání do hloubky pomocí rekurzivní funkce (zpracování preorder, inorder, postorder) + jeho složitost.
- Prohledávání do hloubky bez rekurze - pomocí zásobníku + jeho složitost. Pseudokód metody.
- Prohledávání do šířky postupným prohledáváním do hloubky + jeho složitost.
- Prohledávání do šířky bez rekurze - pomocí fronty + jeho složitost. Pseudokód metody.
- Fronta a zásobník a jejich implementace. Na cvičení implementace pomocí spojového seznamu.
- Metoda pro výpis stromu po vrstvách a hezky odsazeně (obě varianty průchodu stromem do šířky).
- Metoda pro smazání uzlu (nerekurzivní varianta).
3. cvičení 6-8.3.2018
- Diskuse minulého domácího úkolu (uspořádaný spojový seznam).
- Příklady implementace vybraných metod (najdiPrvek, smazPrvek, vypis, konstruktor, destruktor ap.).
- Složitost jednotlivých metod v průměrném, nejhorším a nejlepším případě ve srovnání s neuspořádaným spojovým seznamem.
- Binární vyhledávací strom
- Základní pojmy, hloubka v nejlepším, nejhorším a průměrném případě
- Definovali jsme třídu Strom a implementovali metody najdiPrvek a vlozPrvek (diskuse nerekurzivní a rekurzivní varianty).
- Rekurzivní metoda pro průchod stromem a její využití pro výpis prvků ve stromě v pořadí preorder, inorder a postorder a pro smazání všech uzlů.
- Výpis stromu po vrstvách (v některých skupinách, jinde zbylo na příště).
- Složitost jednotlivých metod v průměrném, nejhorším a nejlepším případě (ve skupinách B, D)
2. cvičení 27-29.2.2018
- Diskuse minulého domácího úkolu. Shrnutí, jak lze pracovat se souborem (v některých skupinách).
- Složitost programu - jednoduché příklady, řešení rekurentních vztahů pomocí matematické indukce a pomocí kuchařky.
- Připomínáme si, jak se pracuje se strukturami, třídami a ukazateli.
- Uspořádaný seznam prvků a vybrané metody nad ním:
- vlozPrvek, vypis, konstruktor, destruktor
- najdiPrvek, smazPrvek - zbylo za domácí úkol
1. cvičení 20-22.2.2018
- O cvičení, podmínky zápočtu...
- Složitost algoritmu - opakování základních pojmů.
- Požadavky na program (příklad softwarové firmy).
- Příklad na programování shora dolů (kvadratická rovnice).
- Vypůjčené slidy ke cvičení.