Základy algoritmizace, cvičení

• Domů
• O cvičení
• Zápočty
• Poznámky ze cvičení
• Domácí úlohy
• Přihlášení studenti

Konzultační hodiny během zkouškového období květen-červen

• úterý, čtvrtek, pátek 8-11:30 (po předchozí domluvě emailem), Trojanova, místnost 44

Poslední domácí úloha (plus bonusové úlohy)

• Někteří studenti splnili podmínku na účast, ale chybí jim větší počet bodů za domácí úlohy. Poslední (12-13) domácí úloha (zpracování aritmetického výrazu) je určena hlavně pro tyto opozdilce, a je proto většího rozsahu. Termín pro její odevzdání je až 14.9.2018. Pokud by Vám i tak nestačil počet bodů, individálně se dohodneme na dalším postupu.
• Alternativně můžete (po domluvě) odevzdat do 14.9.2018 i libovolné starší domácí úlohy (popř. opravy programů, které jste již odevzdávali), ale půjde za ně získat oproti původnímu termínu jen poloviční počet bodů.

12. a 13. domácí úkol: Zpracování aritmetického výrazu (bude doplněno)

• Opět příklady ze cvičení: Reprezentace aritmetického výrazu pomocí stromu
• Na cvičení jsme definovali reprezentaci aritmetického výrazu pomocí binárního stromu (viz Strom.h)
• Uvažujeme aritmetický výraz, který se skládá z proměnných (řetězec písmen nebo čísel, který začíná písmenem), čísel (reálná čísla), kulatých závorek, binárních operátorů (+ pro sčítání, - pro odečítání, * pro násobení, / pro dělení) a operátoru ~, který reprezentuje unární mínus.
• Úkol: implementujte následující metody třídy Strom:
• Strom(); ~Strom(); void nastavPromenne(string *_promenne, double *_hodnoty, int *_n); double hodnotaPromenne(string p); (0,4 bodu)
  Pomocné metody.
• double vyhodnot(); (0,25 bodu)
  Vrátí hodnotu aritmetického výrazu uloženého ve stromě.
• double vypisPrefix(); vypisInfix(); vypisPostfix(); (0,35 bodu)
  Vypíše aritmetický výraz uložený ve stromě na standardní výstup v dané notaci.
• void postavZPostfixu(); (0,25 bodu + 0,2 bodu za Zásobník)
  Načte řetězec v postfixové notaci a postaví strom daného aritmetického výrazu (s využítím zásobníku).
• void vyhodnotPostfix(); (0,3 bodu)
  Vyhodnotí aritmetický výraz zadaný jako řetězec v postfixové notaci (s využitím zásobníku, bez mezikroku postavení stromu).
• Jednoduché funkce pro načítání elementů (tokenů) ze standardního vstupu nebo ze souboru jsou již implementované v přiloženém zdrojovém souboru (viz main.cpp).
• 13. domácí úloha:
• void infixNaPostfix(); (0,3 bodu)
  Načte řetězec v infixové notaci a vypíše ho v postfixové notaci (s využítím zásobníku).
• void postavZInfixu(); (0,7 bodu)
  Načte řetězec v infixové notaci a postaví strom daného aritmetického výrazu (s využítím dvou zásobníků).
• void vyhodnotInfix(); (0,6 bodu)
  Vyhodnotí aritmetický výraz zadaný jako řetězec v infixové notaci (s využitím dvou zásobníků, bez mezikroku postavení stromu).
• Šablony pro hlavičkové nebo zdrojové soubory: Strom.h, pomocné funkce a testovací příklady:main.cpp, zadání a okomentovaná řešení příkladů (pro porovnání Vašich výsledků): vstup.txt, vystup.txt.
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 14.9.2018. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 12" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Program by měl být odladěný. Kdo mi pošle program, který nebude fungovat správně, můžete poslat opravu, pokud ji stihnete poslat v termínu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).

11. domácí úkol 2.5.2018 : Dynamické programování: Optimální binární vyhledávací strom

• Opět příklady ze cvičení:
• Editační vzdálenost (0,6 bodu) (pouze skupina středa 7:30):
• Detaily viz. zadání minulého domácího úkolu.
• Šablona pro hlavičkový nebo zdrojový soubor: ReseniEdit.h, testovací příklady: main.cpp a jejich okomentovaná řešení (pro porovnání Vašich výsledků): priklad.txt.
• Optimální binární vyhledávací strom (0,75 bodu)
• Vstup:
• pole čísel x délky n (čísla setříděná od nejmenšího po největší, x[0] < x[1] < ... < x[n-1])
• pole čísel p délky n (p[i] je váha (pravděpodobnost nebo četnost) dotazu na x[i])
• pole čísel q délky n+1 (q[i] je váha (pravděpodobnost nebo četnost) dotazu na y, x[i-1] < y < x[i]), kde x[-1]= - ∞, x[n]= + ∞
• Cílem úlohy je spočítat cenu optimálního binárního vyhledávacího stromu a sestrojit příslušný strom. Cena binárního stromu je definovaná jako průměrný počet navštívených uzlů (tj. iterací while cyklu) v metodě stromu najdiPrvek (ze 3.cvičení). Detaily viz přiložené soubory.
• BinarniStrom(int* x, char** hodnoty, int **pk, int n);
  Doimplementujte do třídy BinarniStrom konstruktor, který postaví příslušný optimální binární vyhledávací strom na základě matice pk (kde jsou uloženy indexy kořenů optimálních podstromů). Klíče a hodnoty uzlů jsou uloženy v polích "x" a "hodnoty", při stavbě stromu se využije prvních n prvků obou polí. Pole x je uspořádané od nejmenšího prvku po největší. pk[i][j] = index kořene optimálního stromu postaveného z úseku x[i],x[i+1],...,x[j-1].
  Definice datové struktury BinarniStrom odpovídá zadání z 2-4.cvičení.
• Šablony pro hlavičkové nebo zdrojové soubory: ReseniStrom.h, BinarniStrom.h, testovací příklady: main1.cpp a jejich okomentovaná řešení (pro porovnání Vašich výsledků): priklad1.txt.
• Úlohu řeště pomocí dynamického programování v čase O(n^3) s prostorovou složitostí O(n^2) (jak bylo na cvičení).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 11" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Program by měl být odladěný. Kdo mi pošle program, který nebude fungovat správně, bude mít čas dalších 7 dní na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).

10. domácí úkol 24.4.2018 : Dynamické programování

• Opět příklady ze cvičení:
• int fib(int n); (0,1 bodu)
  Funkce vrátí n-té Fibonacciho číslo. Řešení metodou dynamického programování (iterativně) v čase O(n) s prostorovou složitostí O(n) nebo O(1).
• int nsd(int a, int b); (0,1 bodu)
  Funkce vrátí největšího společného dělitele celých čísel a a b. Řešení iterativně v čase O(a+b) nebo O(log ab).
• Automat na mince (0,5 bodu)
• Cílem úlohy je rozměnit danou cílovou částku pomocí minimálního počtu mincí. Vstupem algoritmu je cílová částka (např. 6) a pole s hodnotami mincí (např. [1,3,4]) (můžeme předpokládat, že počet mincí s danou hodnotou není omezen).
• Program by měl pro dané n vypsat na obrazovku minimální počet mincí a jejich výčet (např. "2: 3 3"). Detaily viz přiložené soubory (bude doplněno).
• Úlohu řeště pomocí dynamického programování v čase O(n m) s prostorovou složitostí O(n) (jak bylo na cvičení).
• Šablona pro hlavičkový nebo zdrojový soubor: ReseniMince.h.
• Editační vzdálenost (0,6 bodu) (pro skupinu středa 7:30, kde jsme úlohu nestihli, jako bonusová úloha):
• Cílem úlohy je spočítat a vypsat na obrazovku editační vzdálenost dvou řetězců (x a y) a vypsat překlepy, kterými z řetězce x dostaneme řetězec y. Editační vzdálenost je definovaná jako minimální počet překlepů, kterými z řetězce x dostaneme řetězec y. Možné překlepy jsou vložení písmenka, smazání písmenka nebo nahrazení jednoho písmenka jiným. Detaily viz přiložené soubory.
• Šablona pro hlavičkový nebo zdrojový soubor: ReseniEdit.h.
• Úlohu řeště pomocí dynamického programování v čase O(n^2) s prostorovou složitostí O(n^2) (jak bylo na cvičení).
• V souboru main.cpp jsou testovací příklady. V souboru priklad.txt jsou okomentovaná řešení těchto příkladů (pro porovnání Vašich výsledků).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 10" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Program by měl být odladěný. Kdo mi pošle program, který nebude fungovat správně, bude mít čas dalších 7 dní na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).

9. domácí úkol 17.4.2018 : Další metody třídění pole.

• Úkolem je opět dokončit a odladit příklady ze cvičení:
• (kromě skupiny úterý 9:30): void heapSort(double *a, int n); (0,3 bodu)
  Funkce setřídí pole a délky n metodou třídění haldou ("na místě").
• void quickSort(double *a, int n); (0,25 bodu)
  Funkce setřídí pole a délky n metodou rychlého třídění (pomocí rekurzivně volané funkce).
• void quickSort1(double *a, int n); (0,4 bodu)
  Funkce setřídí pole a délky n metodou rychlého třídění (bez rekurze, za použití zásobníku (pro implementaci zásobníku lze lehce modifikovat fronta z úlohy Koně ze 7. domácího úkolu). Šablona pro zásobník: Zasobnik.h,.
• double ktyPrvek(double *a, int n, int k); (až 0,15 bodu)
  Funkce najde a vrátí k-tý prvek v poli a délky n. Řešení drobnou modifikací algoritmu quickSort (tzv. Hoarův algoritmus).
• (pouze skupina úterý 9:30): int mergeSort(double *a, int n); (až 0,25 bodu)
  Funkce setřídí pole a délky n metodou třídění sléváním.
• BONUS: void bucketSort(double *a, int n, int c) (0,3 bodu)
• Pokud by se Vám zdálo, že úloh (a bodů za ně) je málo, můžete poslat řešení bonusové úlohy (na cvičení jsme ve většině skupin kód nestihli dokončit).
• Funkce částečně setřídí pole a délky n metodou přihrádkového třídění (klíčem bude nejnižší cifra celé části čísla, např. 123,45 má klíč 3; 45 má klíč 5, tj. klíč získáme jako zbytek po dělení 10 (x % 10).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 9" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Program by měl být odladěný. Kdo mi pošle program, který nebude fungovat správně, bude mít čas dalších 7 dní na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).

8. domácí úkol 10.4.2018 : Přímé metody třídění pole.

• Úkolem je opět dokončit a odladit příklady ze cvičení:
• void selectionSort(double *a, int n); (až 0,15 bodu)
  Funkce setřídí pole a délky n metodou přímého výběru minima ("na místě"). Z probíraných metod implementujte variantu s co nejmenším počtem operací porovnání a přiřazení.
• void insertionSort(double *a, int n); (až 0,15 bodu)
  Funkce setřídí pole a délky n metodou přímého vkládání ("na místě"). Z probíraných metod implementujte variantu s co nejmenším počtem operací porovnání a přiřazení.
• void bubbleSort(double *a, int n); (až 0,15 bodu)
  Funkce setřídí pole a délky n metodou bublinkového třídění ("na místě"). Z probíraných metod implementujte variantu s co nejmenším počtem operací porovnání a přiřazení.
• (pouze skupina úterý 9:30): void heapSort(double *a, int n); (až 0,3 bodu)
  Funkce setřídí pole a délky n metodou třídění haldou ("na místě").
• BONUS: Úloha procházky koněm po šachovnici n x n (0,3 bodu)
• Pokud by se Vám zdálo, že úloh (a bodů za ně) je málo, můžete poslat řešení bonusové úlohy.
• Do implementace minulého domácho úkolu (třída ReseniKun) doplňte metodu void vyresProchazku(int sx, int sy).
• Cílem úlohy je nalézt cestu koněm po šachovnici n x n z počátečního pole tak, aby kůň prošel každým polem šachovnice právě jednou.
• Úlohu řešte pomocí rekurzivní metody procházení do hloubky (viz pseudokód ze cvičení).
• Program by měl nalézt a vypsat na obrazovku jedno z možných řešení úlohy (pro zadané n a počáteční stav).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 8" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Program by měl být odladěný. Kdo mi pošle program, který nebude fungovat správně, bude mít čas do přespříštího cvičení (23.4.2018) na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).

7. domácí úkol 3.4.2018 : Prohledávání stavového prostoru.

• Úkolem je opět dokončit a odladit příklady ze cvičení:
• Úloha n dam (0,5 bodu)
• Cílem úlohy je položit n dam na šachovnici n x n tak, aby se vzájemně neohrožovaly. Dvě dámy se ohrožují, pokud jsou položeny ve stejném řádku, sloupci nebo na stejné horní nebo dolní diagonále.
• Úlohu řeště pomocí backtrackingu (procházení do hloubky) s využitím rekurzivní funkce (jak bylo na cvičení).
• Program by měl nalézt a vypsat na obrazovku všechna řešení úlohy (pro zadané n). Detaily viz. hlavičkové soubory.
• Úloha nejkratší cesty koněm po šachovnici n x n (0,5 bodu+ 0,3 bodu za implementaci fronty)
• Cílem úlohy je nalézt nejkratší cestu koněm na šachovnici n x n z počátečního pole do všech ostatních.
• Úlohu řešte pomocí procházení do šířky s využitím fronty (jak bylo na cvičení).
• Program by měl nalézt a vypsat na obrazovku jedno z možných řešení úlohy (pro zadané n, počáteční stav a příp. koncový stav). Detaily viz. hlavičkové soubory.
• Šablony pro hlavičkové a zdrojové soubory: ReseniDamy.h, ReseniKun.h, Fronta.h, Souradnice.h
• V souboru main.cpp jsou testovací příklady. V souboru priklad.txt jsou okomentovaná řešení těchto příkladů (pro porovnání Vašich výsledků). Nezapomeňte, že nejkratší cesta koněm není jednoznačná (pole p ve Vašem řešení se tak může od vzorového lišit).
• Pokyny k vypracování:
• Pokud možno dodržte rozhraní metod (stejné parametry a návratové hodnoty).
• Program by měl být odladěný.
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 7" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Důležité: Vzhledem k tomu, že už je za námi polovina semestru, bylo by fajn, kdyby už Vaše programy byly funkční, přeložitelné a odladěné. Kdo mi pošle program, který nebude fungovat správně, obzvláště pokud bude "padat", tomu pošlu poznámky (v závislosti na srozumitelnosti programu i rady, jak program zprovoznit) a bude mít čas do přespříštího cvičení (16.4.2018) na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).

6. domácí úkol 27.3.2018 : Graf a Dijkstrův algoritmus.

• Úkolem je opět dokončit a odladit příklady ze cvičení:
• Orientovaný hranově ohodnocený graf (0,55 bodu)
• Vyberte si jednu z probíraných reprezentací grafu (např. pomocí matice sousednosti) a implementujte pro ni metody deklarované v Graf.h.
• V souboru Graf.h najdete i popis, co by jednotlivé metody měly dělat.
• Dijkstrův algoritmus pro hledání nejkratší cesty v (hranově ohodnoceném orientovaném) grafu. (0,75 bodu)
• Nad implementovanou datovou strukturou pro graf implementujte Dijkstrův algoritmus.
• Šablona pro hlavičkový soubor: ReseniDijkstra.h (objektová varianta, neobjektové řešení je naznačeno v komentáři). V hlavičkovém souboru najdete i stručný popis, co znamenají jednotlivé proměnné a co by jednotlivé metody měly dělat.
• V souboru main.cpp jsou testovací příklady. V souboru priklad.txt jsou okomentovaná řešení těchto příkladů (pro porovnání Vašich výsledků).
• Pokyny k vypracování:
• Zejména v případě grafu dodržte rozhraní metod (stejné parametry a návratové hodnoty).
• Program by měl být odladěný.
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 6" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Důležité: Vzhledem k tomu, že už je za námi polovina semestru, bylo by fajn, kdyby už Vaše programy byly funkční, přeložitelné a odladěné. Kdo mi pošle program, který nebude fungovat správně, obzvláště pokud bude "padat", tomu pošlu poznámky (v závislosti na srozumitelnosti programu i rady, jak program zprovoznit) a bude mít čas do přespříštího cvičení (9.4.2018) na opravu. Body se započtou až za funkční verzi (s případnými malými nedostatky).
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).

5. domácí úkol 20.3.2018 : Metoda rozděl a panuj

• Úkolem je opět dokončit a odladit příklady ze cvičení:
• Binární vyhledávací strom - dokončení
• BinarniStrom(int klice[], char** hodnoty, int n); (0,2 bodu)
  Konstruktor, který postaví binární vyhledávací strom (s n uzly) o optimální hloubce. Klíče a hodnoty uzlů jsou uloženy v polích "klice" a "hodnoty", při stavbě stromu se využije prvních n prvků obou polí. Pole klice je uspořádané od nejmenšího prvku po největší. Řešení metodou rozděl a panuj v čase O(n).
  Definice datové struktury byla popsaná v zadání minulého a předminulého domácího úkolu. Tam najdete i šablony pro hlavičkový a zrojový soubor.
• Vyhledávání půlením intervalů (Binární vyhledávání)
• int vyhledej(int kde[], int co, int n); (0,2 bodu)
  Funkce vrátí index prvku "co" v poli "kde". Prohledává se pouze prvních n prvků pole "kde". Pokud prvek "co" v poli není, vrátí funkce hodnotu -1. Řešení metodou rozděl a panuj v čase O(log n).
• Hanojské věže
• void vyres(int n); (0,5 bodu)
  Funkce vyřeší úlohu Hanojských věží (n je počet kotoučů) a postup řešení vypíše na obrazovku ve tvaru (např. pro n=5):
  54321 : _____ : _____
  5432_ : 1____ : _____
  543__ : 1____ : 2____
  ...
  _____ : 54321 : _____
  Řešení metodou rozděl a panuj v čase O(2^n).
• Přesné zadání úlohy bylo na cvičení. Stručně: máme 3 věže A, B, C, n kotoučů o poloměrech 1,...,n, na začátku jsou všechny kotouče na věži A, cílem je přesunout všechny kotouče na věž B, přesouvání se řídí danými pravidly (vždy přesouváme jen jeden kotouč, není povoleno odložit kotouč mimo věže, ani větší kotouč na menší).
  Řešení metodou rozděl a panuj v čase O(2^n).
• Pokyny k vypracování:
• Dodržte rozhraní funkcí a metody (stejné parametry a návratové hodnoty).
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 5" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Program by měl být odladěný.

4. domácí úkol 13.3.2018 : Binární vyhledávací strom - pokračování

• Úkolem je opět dokončit a odladit příklad ze cvičení: doimplementujte další metody třídy BinarniStrom (všechny nebo některé). Definice datové struktury byla popsaná v zadání minulého domácího úkolu.
• void smazPrvek(int klic); (0,4 bodu)
  Smaže ze stromu uzel s danou hodnotou klíče.
• void vypisPoVrstvách(); (0,3 bodu)
  Vypíše klíče uzlů ve stromu na standardní výstup po vrstvách (každá vrstva na jeden řádek). Prvky budou odsazené tak, aby byla zřejmá struktura stromu. Např. ve tvaru:
  

  				10
  	6						18
  4		7						24

  Zjednodušená varianta, kdy prvky budou vypsané po vrstvách, ale nebudou hezky odsazené, je za 0,2 bodu. Použijte metodu postupného procházení do hloubky (výpis vrstev v cyklu, výpis jedné vrstvy rekurzivní metodou).
  Pro zjednodušení můžete jako předpoklad hezkého odsazení vzít, že klíče jsou maximálně dvojciferná čísla a hloubka stromu maximálně 5.
• void vypisPoVrstváchF(); (0,3 + 0,3 bodu)
  Totéž, co předchozí metoda, ale metodou bez rekurze, s využitím fronty. Frontu implementujte pomocí spojového seznamu. Za zjednodušenou variantu, kdy prvky budou vypsané po vrstvách, ale nebudou hezky odsazené, bude o 0,1 bodu méně. Pokud využijete knihovní verzi fronty místo vlastní implementace, získáte o 0,3 bodu méně.
• Příklady volání těchto metod najdete v šabloně main.cpp ve funkci main(). Doporučuji v rámci ladění programu dopsat další testovací příklady, aby co nejlépe pokryly (hlavně krajní) případy, které mohou nastat.
• Šablony pro hlavičkové a zdrojové soubory: BinarniStrom.h, Fronta.h, BinarniStrom.cpp a main.cpp.
• Pro snadné testování dejte pozor na to, aby Vámi implementované metody odpovídaly zadání (tj. měly stejné parametry a návratové hodnoty). Můžete samozřejmě implementovat další pomocné metody.
• Pokud jste vypracovali minulý úkol, doporučuji nové metody doimplementovat do Vašeho řešení minulého domácího úkolu (ideálně do fungující, opravené verze).
• Pro výpis po vrstvách jsou body za domácí úkol svázané s minulým domácím úkolem (body se započítávají jen jednou). Je možné poslat opravu / rozšíření a získat tak za příslušnou metodu více bodů.
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 4" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Program by měl být odladěný.

3. domácí úkol 6.3.2018 : Binární vyhledávací strom

• Úkolem je dokončit a odladit příklad ze cvičení.
• Vlastnosti stromu:
• Prvek stromu (Uzel) obsahuje klíč (int) a hodnotu (řetězec) (a ukazatele na levého a pravého následovníka).
• Pro každý uzel ve stromě platí, že všechny uzly v jeho levém podstromu mají menší hodnotu klíče a všechny uzly v jeho pravém podstromu mají větší hodnotu klíče.
• Strom obsahuje maximálně jeden uzel s daným klíčem.
• Implementujte všechny nebo některé metody třídy BinarniStrom:
• BinarniStrom(), ~BinarniStrom() (povinně, 0,1 bodu )
  Destruktor ~BinarniStrom() by měl smazat všechny uzly stromu.
• Uzel* najdiPrvek(int klic); (0,2 bodu)
  Vrátí uzel s daným klíčem (nebo nullptr).
• void vlozPrvek(int klic, char* hodnota); (0,2 bodu)
  Vloží uzel do stromu na správné místo podle klíče (pokud už uzel s daným klíčem ve stromu je, jen změní jeho hodnotu na novou).
• void vypisInOrder(); (0,1 bodu)
  Vypíše prvky stromu jeden po druhém od nejmenšího po největší (zleva doprava) na standardní výstup. Např. ve tvaru:
  (2,"dva"),(8,"osm"),(10,"deset")
• void vypisOdsazene(); (0,1 bodu)
  Vypíše prvky stromu na standardní výstup (každý na jeden řádek) odsazené tak, aby byla zřejmá struktura stromu. Pořadí průchodu stromem (prerder, inorder nebo postorer) nechám na Vás. Např. pro preorder ve tvaru:
  

  (10,"deset")
  	(6,"deset")
  		(4,"deset")
  		(7,"deset")
  	(18,"deset")
  		(24,"deset")

• void vypisPoVrstvách(); (0,2 bodu)
  Vypíše klíče prvků stromu na standardní výstup po vrstvách (každá vrstva na jeden řádek). Prvky budou odsazené tak, aby byla zřejmá struktura stromu. Např. ve tvaru:
  

  				10
  	6						18
  4		7						24

Zjednodušená varianta, kdy prvky budou vypsané po vrstvách, ale nebudou hezky odsazené, je za 0,1 bodu. U některých paralelek jsme tuto metodu a její postup nestihli probrat. Pokud byste si nevěděli rady, klidně ji vynechejte, postup probereme na příštím cvičení.
• Příklady volání těchto metod najdete v šabloně main.cpp ve funkci main(). Doporučuji v rámci ladění programu dopsat další testovací příklady, aby co nejlépe pokryly (hlavně krajní) případy, které mohou nastat.
• Doporučuji využít následující šablony pro hlavičkové a zdrojové soubory: BinarniStrom.h, BinarniStrom.cpp a main.cpp.
• Pro snadné testování dejte pozor na to, aby Vámi implementované metody odpovídaly zadání (tj. měly stejné parametry a návratové hodnoty). Můžete samozřejmě implementovat další pomocné metody (např. pro rekurzivní volání na podstrom).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 3" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Program by měl být odladěný.
• Pokud byste tápali v tom, jak pracovat s ukazateli, strukturami a třídami v C++, doporučuji nahlédnout do skript ze Základů programování v C++ (a ze Základů algoritmizace v C++) a přpadně si stáhnout z webu doprovodný kód. Možná k pochopení pomůže i tento jednoduchý příklad (který ale nesouvisí s domácím úkolem).
• K zamyšlení: jaká bude maximální, minimální a průměrná složitost jednotlivých metod? Jak byste implementovali mazání prvku?

2. domácí úkol 27.2.2018 : Seznam (Uspořádaný spojový seznam)

• Úkolem je dokončit a odladit příklad ze cvičení.
• Vlastnosti seznamu:
• Prvek seznamu obsahuje klíč (int) a hodnotu (řetězec) (a ukazatel na následující prvek seznamu).
• Prvky jsou uspořádané vzestupně podle klíče.
• Seznam obsahuje maximálně jeden prvek s daným klíčem.
• Implementujte všechny nebo některé metody třídy Seznam:
• Seznam(), ~Seznam() (povinně, 0,1 bodu )
  Destruktor ~Seznam() by měl smazat všechny prvky seznamu.
• void vlozPrvek(int klic, char* hodnota); (0,2 bodu)
  Vloží prvek do seznamu na správné místo podle klíče (pokud už prvek s daným klíčem v seznamu je, jen změní jeho hodnotu na novou).
• void vypis(); (0,2 bodu)
  Vypíše prvky seznamu jeden po druhém na standardní výstup. Např. ve tvaru:
  (2,"dva"),(8,"osm"),(10,"deset")
• Prvek* najdiPrvek(int klic); (0,2 bodu)
• void smazPrvek(int klic); (0,2 bodu)
• Příklady volání těchto metod najdete v šabloně Seznam.cpp ve funkci main(). Bonus až 0,2 bodu, pokud implementujete všechny výše zmíněné metody a doplníte testovací příklady, aby co nejlépe pokryly možné situace (alternativně lze využít formu unit testů).
• Pokyny k vypracování:
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 2" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Posílejte pouze zdrojový a hlavičkový soubor / soubory (ne celý projekt).
• Program by měl být odladěný.
• Můžete využít následující šablonu pro hlavičkový a zdrojový soubor: Seznam.h a Seznam.cpp
• Pokud byste tápali v tom, jak pracovat s ukazateli, strukturami a třídami v C++, doporučuji nahlédnout do skript ze Základů programování v C++ (a ze Základů algoritmizace v C++) a přpadně si stáhnout z webu doprovodný kód. Možná k pochopení pomůže i tento jednoduchý příklad (který ale nesouvisí s domácím úkolem).
• K zamyšlení: jaká bude maximální, minimální a průměrná složitost jednotlivých metod?

1. domácí úkol 20.2.2018 : Kvadratická rovnice (řešení kvadratické rovnice jako tahák pro žáka základní školy)

• (0.75 bodu) Úkolem je dokončit a odladit příklad ze cvičení. Program by měl pracovat ve dvou módech:
• Načítání vstupů ze standardního vstupu a vypisování výsledku na standardní výstup (v cyklu).
• Načítání vstupů a vypisování výsledků ze a do souboru.
• Pokyny k vypracování:
• O módu práce a o názvech souborů pro čtení a zápis by měl nějakým způsobem rozhodnout uživatel. Jedna možnost je, že se ho program po spuštění zeptá. Jiná možnost je, že mód a cesty k souborům budou parametry funkce main.
• Zde najdete příklad, jak by mohl vypadat vzorový soubor se vstupy.
• Termín pro vypracování domácího úkolu je 24 hodin před následujícím cvičením. Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 1" + paralelka (např. " úterý 7:30 ") + příp. vaše jméno.
• Posílejte pouze zdrojový soubor / soubory (ne celý projekt).
• Program by měl být stručně, ale výstižně okomentovaný.
• Program by měl detekovat a nějakým vhodným způsobem ošetřovat situace, kdy nastala chyba, obzvláště u knihovních funkcí pro práci se vstupy a výstupy od uživatele (cin, fopen, fscanf apod.). Samozřejmostí je testovat návratové hodnoty knihovních funkcí. Následně pro naše účely plně postačí líné řešení, kdy program při zjištění chyby vypíše na standardní chybový výstup (cerr) stručný popis a příp. lokalizaci problému (např. "Nepodařilo se otevřít soubor xyz") a ukončí se.
• Nápady na další hrátky s programem nad rámec zadání domácí úlohy:
• Ukazatele a reference: Na cvičení jsme všechny proměnné (a,b,c,...) definovali jako globální. Zkuste pozměnit funkce tak, aby si je funkce předávaly jako parametry (pomocí ukazatelů nebo referencí).
• Pro pokročilejší znalce C++:
• Výjimky: Vyzkoušejte nějaké inteligentnější řešení chybových situací, např. pomocí výjimek.
• Objektové řešení: Zamyslete se nad tím, jak úlohu řešit objektově (objekt pro řešení s metodami pro načtení a výpis), případně s využitím dědičnosti.