Základy algoritmizace, cvičení

• Domů
• O cvičení
• Zápočty
• Poznámky ze cvičení
• Domácí úlohy

Témata zápočtových programů

Protože už se blíží konec semestru, je na čase si vybrat téma zápočtového programu. Zde naleznete návrhy témat zápočtových programů. Můžete si ale vybrat i vlastní téma. Vybrané téma mi buď pošlete emailem, nebo napište do komentáře k zápočtovému programu v moodle. Každé téma smí mít jen jeden student. Do 23.4.2020 mají přednostní možnost výběru ti studenti, kteří už získali potřebný počet bodů za účast a úlohy (tj. 20). Od 23.4.2020 si mohou téma vybrat i ostatní. Přednost bude mít ten student, kdo se k tématu přihlásí dříve. Termín pro výběr tématu je do 1.5.2020 (v odůvodněných případech do 15.5.2020).

13. cvičení (středa 13.5.2020, čtvrtek 14.5.2020 a pondělí 18.5.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Zpracování aritmetických výrazů II
  • Poznámky ke cvičení
  • Infixová notace:
  • Převod infixové notace na postfixovou + složitost
  • Převod infixové notace na strom + složitost
  • Přímé vyhodnocení aritmetického výrazu zadaného jako řetězec v infixové notaci + složitost
• Domácí úkol do příštího týdne:
• Úloha č.12 (Aritmetické výrazy II)

12. cvičení (středa 6.5.2020, čtvrtek 7.5.2020 a pondělí 11.5.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Zpracování aritmetických výrazů I
  • Poznámky ke cvičení
  • Reprezentace aritmetického výrazu pomocí stromu nebo pomocí řetězce v infixové, prefixové či postfixové notaci
  • Strom:
  • Vyhodnocení aritmetického výrazu uloženého ve stromě + složitost
  • Převod stromu na řetězec v postfixové, infixové nebo prefixové notaci + složitost
  • Postfixová notace:
  • Převod postfixové notace na strom + složitost
  • Přímé vyhodnocení aritmetického výrazu zadaného jako řetězec v postfixové notaci + složitost
  • Prefixová notace
  • Převod prefixové notace na strom + složitost
  • Přímé vyhodnocení aritmetického výrazu zadaného jako řetězec v prefixové notaci + složitost
• Domácí úkol do příštího týdne:
• Úloha č.11 (Aritmetické výrazy I)

11. cvičení (středa 29.4.2020, čtvrtek 30.4.2020 a pondělí 4.5.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Dynamické programování
• Poznámky ke cvičení (aktualizace 1.5.2020)
• Dynamické programování
  • Výpočet faktoriálu - různé způsoby a složitost
  • Výpočet největšího společného dělitele dvou přirozených čísel - různé způsoby + složitost
  • Výpočet n-tého Fibonacciho čísla - různé způsoby + složitost
  • Úloha automatu na mince - různé způsoby + složitost
  • Úloha výpočtu nejkratší rostoucí podposloupnosti - různé způsoby + složitost
  • Úloha sestrojení optimálního binárního vyhledávacího stromu - různé způsoby + složitost
• Domácí úkol do příštího týdne:
• Úloha č.10 (Dynamické programování)

10. cvičení (středa 22.4.2020, čtvrtek 23.4.2020 a pondělí 27.4.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Třídění II
• Poznámky ke cvičení
• Sofistikovanější třídící algoritmy a jejich složitost (pokračování):
1. Třídění haldou (heap sort)
2. Rychlé třídění (quick sort)
• s využitím rekurze
• s využitím zásobníku
3. Metoda vyhledání k-tého nejmenšího prvku v poli (Hoarův algoritmus)
4. Metoda přihrádkového třídění (bucketSort, radixSort)
• Domácí úkol do příštího týdne:
• Úloha č.9 (Třídění II)

9. cvičení (středa 15.4.2020, čtvrtek 16.4.2020 a pondělí 20.4.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Třídění I
• Poznámky ke cvičení
• Přímé metody třídění pole (a spojového seznamu):
1. Třídění přímým výběrem minima (selection sort)
2. Třídění vkládáním (insertion sort), shell sort
3. Bublinkové třídění (bubble sort), třídění přetřásáním
   ... různé varianty metod a jejich složitost
• Sofistikovanější třídící algoritmy (část):
1. Třídění binárním vyhledávacím stromem
2. Třídění přímým slučováním (merge sort)
• s využitím rekurze
• s využitím zásobníku
• Domácí úkol do příštího týdne:
• Úloha č.8 (Třídění I)

8. cvičení (středa 8.4.2020, čtvrtek 9.4.2020 a pondělí 13.4.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Stavový prostor problému a jeho procházení
• Poznámky ke cvičení
• Procházení stavovým prostorem do hloubky s navracením (backtracking):
1. obecně (řešení pomocí rekurze a s využitím zásobníku)
2. Vlk, koza a zelí
3. Problém n dam
4. Procházka šachovým koněm po šachovnici (aby navštívil každé pole právě jednou)
• Procházení stavovým prostorem do šířky (algoritmus vlny)
1. Úloha hledání nejkratších cest šachovým koněm po šachovnici ze startovního pole do všech ostatních polí
• Domácí úkol do příštího týdne:
• Úloha č.7 (Stavový prostor)

7. cvičení (středa 1.4.2020, čtvrtek 2.4.2020 a pondělí 6.4.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Graf
• Poznámky ke cvičení
• Graf a jeho reprezentace v programu
• Procházení grafem do hloubky a jeho aplikace:
1. Rozklad grafu na komponenty souvislosti
• Procházení grafem do šířky a jeho aplikace:
1. Hledání nejkratší cesty v hranově neohodnoceném grafu
• Ukázka hladového algoritmu:
1. Dijkstrův algoritmus pro hledání nejkratší cesty v hranově ohodnoceném grafu
• Složitost jednotlivých metod pro různé datové reprezentace
• Domácí úkol do příštího týdne:
• Úloha č.6 (Graf)

6. cvičení (středa 25.3.2020, čtvrtek 26.3.2020 a pondělí 30.3.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Metoda rozděl a panuj
• Poznámky ke cvičení
• Obecný princip
• Příklady:
1. Vyhledávání v uspořádaném poli hodnot půlením intervalů (binární vyhledávání)
2. Postavení binárního vyhledávacího stromu na základě uspořádaného pole klíčů.
3. Hanojské věže
• Časová složitost jednotlivých algoritmů
• Substituční metoda a metoda ,,kuchařka'' (Master Theorem) pro výpočet složitosti rekurentních metod
• Na příkladech
• Další příklady k procvičení
• Domácí úkol do příštího týdne:
• Úloha č.5 (Rozděl a panuj)

5. cvičení (středa 18.3.2020, čtvrtek 19.3.2020 a pondělí 23.3.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu (binární vyhledávací strom) ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• do slidů k minulému cvičení jsem doplnila návod pro řešení bonusové úlohy (20.3.2020 jsem doplnila i vysvětlující obrázky)
• Binární vyhledávací strom - pokračování ... SAMOSTUDIUM
• Poznámky ke cvičení aktualizace 21.3.2020 (doplněny stručné návody k domácím úlohám)
• Procházení stromu do hloubky a do šířky pomocí rekurze - časová a prostorová složitost.
• Fronta a zásobník a jejich implementace (pole / spojový seznam).
• Procházení stromu do hloubky bez rekurze - pomocí zásobníku + jeho časová a prostorová složitost. Pseudokód metody.
• Procházení stromu do šířky bez rekurze - pomocí fronty + jeho časová a prostorová. Pseudokód metody.
• Domácí úkol do příštího týdne:
• Úloha č.4 (Binární vyhledávací strom)

4. cvičení (středa 11.3.2020, čtvrtek 12.3.2020 a pondělí 16.3.2020) ... SAMOSTUDIUM

• Diskuse minulého domácího úkolu (binární vyhledávací strom) ... individuálně (emailem)
• pomoc s implementací vybraných metod (individuálně podle zájmu studentů)
• Složitost jednotlivých metod v průměrném, nejhorším a nejlepším případě aktualizace 17.3.2020
• Binární vyhledávací strom - pokračování ... SAMOSTUDIUM
• Poznámky ke cvičení aktualizace 20.3.2020 (doplněn návod pro výpis stromu po vrstvách hezky odsazeně včetně obrázků)
• Metoda pro smazání vrcholu (nerekurzivní varianta) (snímek 2-3)
• Procházení stromu do hloubky (backtracking) a do šířky (po jednotlivých vrstvách) (snímek 4-12)
• Opakování z minulého cvičení: Procházení do hloubky pomocí rekurzivní funkce (zpracování preorder, inorder, postorder) + jeho složitost. Pseudokód metody (snímek 4, už jsme dělali minule).
• Procházení do šířky postupným prohledáváním do hloubky + jeho složitost. Pseudokód metody (snímek 5-8).
• Metoda pro výpis stromu po vrstvách a hezky odsazeně (od snímku 9).
• Domácí úkol do příštího týdne:
• Úloha č.3 (Binární vyhledávací strom)

3. cvičení (pondělí 2.3.2020, středa 4.3.2020, čtvrtek 5.3.2020 a pondělí 9.3.2020

• Skupina pondělí 9.3.2020
• Binární vyhledávací strom
• Základní pojmy, hloubka v nejlepším, nejhorším a průměrném případě
• Definice třídy BinarniStrom a vybraných metod:
  
• najdiPrvek, 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 vrcholů.
• Pokud stihneme
• Složitost jednotlivých metod v průměrném, nejhorším a nejlepším případě
• Reprezentace stromu pomocí pole, uložení struktury stromu do řetězce/souboru a její opětovné načtení (různé způsoby)
• Domácí úkol do příště:
• Úloha č.2 (Binární vyhledávací strom)
• Skupina pondělí 2.3.2020
• Uspořádaný lineární spojový seznam
  • Probrali jsme podrobně metody: konstruktor, destruktor, vlozPrvek, vypis
  • Metoda smazPrvek: jen myšlenka, implementace zbyla na doma
  • 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 začneme probírat až na příštím cvičení)
• Domácí úkol do příště:
• dokončit úlohu č.1 (Uspořádaný lineární spojový seznam)
• Zbylé skupiny (středa a čtvrtek):
• Dokončení minulé úlohy (uspořádaný lineární spojový seznam).
  • Implementace vybraných metod: vlozPrvek,...
  • 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ě
• Definice třídy BinarniStrom a vybraných metod:
  
• najdiPrvek (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 vrcholů.
• Na rozmyšlenou
• vlozPrvek
• reprezentace stromu pomocí pole, uložení struktury stromu do řetězce/souboru a její opětovné načtení (různé způsoby)
• Domácí úkol do příště:
• Úloha č.2 (Binární vyhledávací strom)

2. cvičení 24-27.2.2020

• Složitost algoritmů
• Opakování základních pojmů
• Prezentace
• Jednoduchý příklad na počítání hvězdiček
• hvezdicky.cpp
• Pro uvedené příklady zkusíme spočítat počet vypsaných hvězdiček (v závislosti na n) a asymptotickou složitost příslušných algoritmů
• Poznámky ke 2. a 3. cvičení
• nějaké definice a užitečné vzorečky
• řešení příkladu s hvězdičkami
• pokud byste nalezli v souboru chyby nebo překlepy, dejte mi prosím vědět
• Uspořádaný lineární spojový seznam prvků a vybrané metody nad ním:
• konstruktor, destruktor, najdiPrvek, vlozPrvek, smazPrvek, vypis
• 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.
• Připomenutí, jak se pracuje s třídami a ukazateli.
• skupina pondělí 9:30: stihli jsme najdiPrvek, částečně vlozPrvek (zbylé metody můžete zkusit sami, příště se k nim vrátíme)
• skupiny středa 9:30, čtvrtek 9:30: stihli jsme konstruktor, destruktor, najdiPrvek (zbylé metody můžete zkusit sami, příště se k nim vrátíme)
• Složitost jednotlivých metod v průměrném, nejhorším a nejlepším případě
• Příklad ze cvičení

1. cvičení 17-20.2.2020

• O cvičení, podmínky zápočtu...
• Softwarový projekt a jeho životní cyklus.
• Úvodní prezentace