Základy algoritmizace, cvičení

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

12. domácí úkol (ze cvičení středa 13.5.2020, čtvrtek 14.5.2020, pondělí 18.5.2020) : Aritmetické výrazy II

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 20.5.2020
• skupina čtvrtek 9:30: do 21.5.2020
• skupina pondělí 9:30: do 25.5.2020
• Pokračování minulé domácí úlohy. Doimplementujte některé nebo všechny následující metody třídy Strom (a funkce):
• void Strom::postavZInfixu(std::istream &f); (0,8 bodu)
• Načte řetězec v infixové notaci a postaví strom daného aritmetického výrazu.
• Řešení s využítím dvou zásobníků, algoritmus ze slidů
• void vyhodnotInfix(const Promenne &p); (0,8 bodu)
• Vyhodnotí aritmetický výraz zadaný jako řetězec v infixové notaci
• Řešení s využítím dvou zásobníků, bez mezikroku postavení stromu, algoritmus ze slidů
• void infixNaPostfix(std::istream &f); (0,5 bodu)
• Načte řetězec v infixové notaci a vypíše ho na konzoli v postfixové notaci.
• Řešení s využítím zásobníku, algoritmus ze slidů
• Jednoduchá funkce pro načítání tokenů z konzole nebo ze souboru je již implementovaná v přiloženém zdrojovém souboru (viz main.cpp).
• Detaily a příloha viz minulý domácí úkol
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

11. domácí úkol (ze cvičení středa 6.5.2020, čtvrtek 7.5.2020 a pondělí 11.5.2020) : Aritmetické výrazy I

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 13.5.2020
• skupina čtvrtek 9:30: do 14.5.2020
• skupina pondělí 9:30: do 18.5.2020
• Maximálně lze za tento domácí úkol v součtu získat 3 body. Nemusíte samozřejmě implementovat vše, ale jen některé z funkcí či metod.
• Uvažujeme jednoduchý aritmetický výraz, který se skládá z proměnných (proměnná je ř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.
• Na cvičení jsme definovali reprezentaci aritmetického výrazu pomocí (binárního) stromu (viz Strom.h)
• Úkol: implementujte některé nebo všechny z následujících metody třídy Strom (a funkce):
• double Strom::vyhodnot(const Promenne &p); (0,4 bodu)
• Vrátí hodnotu aritmetického výrazu uloženého ve stromě.
• Řešení rekurzivně nebo s využitím zásobníku.
• double Strom::vypisPrefix(); double Strom::vypisInfix(); double Strom::vypisPostfix(); (0,45 bodu)
• Vypíše aritmetický výraz uložený ve stromě na konzoli v dané notaci.
• Řešení rekurzivně nebo s využitím zásobníku.
• void Strom::postavZPostfixu(std::istream &f); (0,5 bodu)
• Načte řetězec v postfixové notaci a postaví strom daného aritmetického výrazu.
• Řešení s využítím zásobníku, algoritmus ze slidů
• void vyhodnotPostfix(const Promenne &p); (0,5 bodu)
• Vyhodnotí aritmetický výraz zadaný jako řetězec v postfixové notaci
• Řešení s využítím zásobníku, bez mezikroku postavení stromu, algoritmus ze slidů
• void Strom::postavZPrefixu(std::istream &f); (0,5 bodu)
• Načte řetězec v prefixové notaci a postaví strom daného aritmetického výrazu
• Řešení s využítím zásobníku, algoritmus ze slidů
• void vyhodnotPrefix(const Promenne &p); (0,5 bodu)
• Vyhodnotí aritmetický výraz zadaný jako řetězec v prefixové notaci
• Řešení s využítím zásobníku, bez mezikroku postavení stromu, algoritmus ze slidů
• pomocné metody a třídy: Promenne, konstruktory, destruktory ap. (až 0,5 bodu, jen společně s ostatními metodami)
• Jednoduchá funkce pro načítání tokenů z konzole nebo ze souboru je již implementovaná v přiloženém zdrojovém souboru (viz main.cpp).
• Příloha:
• Strom.h
• main.cpp
• vstup.txt
• vystup.txt
• V souboru main.cpp (a vstup.txt) jsou testovací příklady.
• Strom.h je zhuštěný hlavičkový soubor (pro všechny třídy, lze rozdělit do více souborů)
• Zachovejte názvy a celkově rozhraní metod (kvůli testování). Vnitřky tříd (soukromé složky) si upravte podle sebe (při zachování dané složitosti).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

10. domácí úkol (ze cvičení středa 29.4.2020, čtvrtek 30.4.2020 a pondělí 4.5.2020) : Dynamické programování

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 6.5.2020
• skupina čtvrtek 9:30: do 7.5.2020
• skupina pondělí 9:30: do 11.5.2020
• Implementujte všechny nebo jen některé z následujících algoritmů:
• Automat na mince (1 bod)
• 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]). Počet mincí s danou hodnotou není omezen.
• Úlohu řešte pomocí dynamického programování v čase O(nm) s prostorovou složitostí O(n) (viz poznámky ke cvičení).
• Pro dané n by pak měl program vypsat na obrazovku minimální počet mincí a jejich výčet (např. "2: 3 3"). Detaily viz přiložené soubory.
• Nejdelší (vybraná) rostoucí podposloupnost (1 bod)
• Cílem úlohy je vypsat na obrazovku nejdelší rostoucí (vybranou) podposloupnost posloupnosti celých čísel délky n (uložené v poli x).
• Úlohu řešte pomocí dynamického programování v čase O(n2) s prostorovou složitostí O(n) (viz poznámky ze cvičení).
• Příloha:
• ReseniMince.h
• ReseniNRP.h
• main.cpp
• priklad.txt
• 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ů).
• Vnitřek tříd si upravte dle potřeby (při zachování rozumné časové a prostorové složitosti), ale zachovejte rozhraní a vypisované informace (kvůli testování).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

9. domácí úkol (ze cvičení středa 22.4.2020, čtvrtek 23.4.2020 a pondělí 24.4.2020) : Třídění I

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 29.4.2020
• skupina čtvrtek 9:30: do 30.4.2020
• skupina pondělí 9:30: do 4.5.2020
• Maximálně lze za tento domácí úkol v součtu získat 3 body. Nemusíte samozřejmě implementovat vše, ale jen některé z funkcí či metod.
• Implementujte všechny nebo jen některé z následujících algoritmů pro třídění pole (pole čísel může obsahovat duplicity):
• void quickSort(double *a, int n); (0,5 bodu)
• Funkce vzestupně setřídí pole a délky n metodou rychlého třídění. Implementujte metodu s využitím rekurze nebo bez rekurze (s využitím zásobníku)
• void heapSort(double *a, int n); (0,6 bodu)
• Funkce vzestupně setřídí pole a délky n metodou třídění haldou ("na místě").
• void radixSort(double *a, int n, int k); (0,6 bodu)
• Funkce částečně vzestupně setřídí pole a délky n metodou třídění podle základu. Třídí se jen podle k "nejbližších" cifer nad desetinnou čárkou (vyšší a nižší cifry se neberou v úvahu), čísla mohou být i záporná.
• double ktyPrvek(double *a, int n, int k); (0,5 bodu)
• Funkce najde a vrátí k-tý nejmenší prvek v poli a délky n. Řešení Hoarovým algoritmem (jen částečně setřídí pole). Bez rekurze.
• Implementujte všechny nebo jen některé z následujících metod pro třídění lineárního spojového seznamu (jednosměrný seznam čísel, může obsahovat duplicity):
• void Seznam::quickSort(); (0,6 bodu)
• void Seznam::heapSort(); (0,8 bodu)
• se seznamem nepracujte jako s polem (k prvkům nepřistupujte přes indexy, není třeba počítat délku seznamu ap.)
• Příloha:
• Seznam.h
• main.cpp
• Zachovejte názvy a celkově rozhraní funkcí a metod (kvůli testování).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

8. domácí úkol (ze cvičení středa 15.4.2020, čtvrtek 16.4.2020 a pondělí 20.4.2020) : Třídění I

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 22.4.2020
• skupina čtvrtek 9:30: do 23.4.2020
• skupina pondělí 9:30: do 27.4.2020
• Maximálně lze za tento domácí úkol v součtu získat 3 body.
• Implementujte všechny nebo jen některé z následujících metod pro třídění pole (pole čísel může obsahovat duplicity):
• void selectionSort(double *a, int n); (0,25 bodu)
• Funkce vzestupně 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 nejmenším počtem operací porovnání a přiřazení.
• void insertionSort(double *a, int n); (0,25 bodu)
• Funkce vzestupně 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 nejmenším počtem operací porovnání a přiřazení.
• void bubbleSort(double *a, int n); (0,25 bodu)
• Funkce vzestupně setřídí pole a délky n metodou bublinkového třídění ("na místě"). Z probíraných metod implementujte variantu s nejmenším počtem operací porovnání a přiřazení, popř. třídění přetřásáním.
• void mergeSort(double *a, int n); (0,5 bodu)
• Funkce vzestupně setřídí pole a délky n metodou třídění sléváním (s využitím pomocného pole). Implementujte metodu s využitím rekurze nebo bez rekurze (s využitím zásobníku).
• Implementujte všechny nebo jen některé z následujících metod pro třídění lineárního spojového seznamu (jednosměrný seznam čísel, může obsahovat duplicity, seznam setřiďte vzestupně):
• void Seznam::selectionSort(); (0,35 bodu)
• void Seznam::insertionSort(); (0,35 bodu)
• void Seznam::bubbleSort(); (0,35 bodu)
• void Seznam::mergeSort(); (0,6 bodu)
• Implementujte metodu s využitím rekurze nebo bez rekurze.
• se seznamem nepracujte jako s polem (k prvkům nepřistupujte přes indexy, není třeba počítat délku seznamu ap.)
• implementace základních metod seznamu podle souboru Seznam.h (konstruktor, destruktor, vloz, vypis) je za 0,3 bodů (samozřejmě pouze za předpokladu, že implementujete i metody pro třídění :-).
• Příloha:
• Seznam.h
• main.cpp
• Zachovejte názvy a celkově rozhraní funkcí a metod (kvůli testování).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

7. domácí úkol (ze cvičení středa 8.4.2020, čtvrtek 9.4.2020 a pondělí 13.4.2020) : Stavový prostor

• Termín vypracování (za plný počet bodů)
• skupina středa 9:30: do 15.4.2020
• skupina čtvrtek 9:30: do 16.4.2020
• skupina pondělí 9:30: do 20.4.2020
• Úkolem je implementovat (všechny nebo některé) příklady, které jsme měli probírat na cvičení.
• Úloha n dam (1 b)
• 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šte pomocí backtrackingu (procházení do hloubky s navracením), s využitím rekurzivní funkce nebo zásobníku (rekurzivní algoritmus je na slidech).
• Program by měl nalézt a vypsat na obrazovku jedno nebo všechna z možných řešení úlohy (pro zadané n, počáteční a cílovou pozici).
• Implementační detaily viz přiložený hlavičkový soubor ReseniDamy.h, kde najdete i stručný popis, co znamenají jednotlivé parametry a co by jednotlivé metody měly dělat.
• Úloha nejkratší cesty koněm po šachovnici n x n (1 b)
• 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 pomocí vlny (ve svém řešení můžete využít frontu, algoritmus je na slidech).
• Program by měl nalézt a vypsat na obrazovku jedno z možných řešení úlohy (pro zadané n, počáteční a cílovou pozici).
• Hlavičkový soubor: ReseniKun.h. V hlavičkovém souboru najdete i stručný popis, co znamenají jednotlivé parametry a co by jednotlivé metody měly dělat.
• Úloha procházky koněm po šachovnici n x n (1 b)
• Do třídy ReseniKun doplňte metodu void vyresDFS(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 průchodem do hloubky s navracením (backtracking) pomocí rekurzivní metody nebo s využitím zásobníku (rekurzivní algoritmus je na slidech).
• Program by měl nalézt a vypsat na obrazovku jedno z možných řešení úlohy nebo všechna řešení (pro zadané n a počáteční stav).
• Hlavičkový soubor: ReseniKun.h.
• Příloha:
• ReseniDamy.h
• ReseniKun.h
• main.cpp
• priklad1.txt
• V souboru main.cpp jsou testovací příklady. V souboru priklad1.txt jsou okomentovaná řešení těchto příkladů (pro porovnání Vašich výsledků).
• Vnitřek tříd ReseniDamy a ReseniKun si upravte dle potřeby (při zachování rozumné časové a prostorové složitosti), ale zachovejte rozhraní a vypisované informace (kvůli testování).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

6. domácí úkol (ze cvičení středa 1.4.2020, čtvrtek 2.4.2020 a pondělí 6.4.2020) : Grafy

• Termín vypracování (za plný počet bodů)
• skupina pondělí 9:30: do 13.4.2020
• skupina středa 9:30: do 8.4.2020
• skupina čtvrtek 9:30: do 9.4.2020
• Úkolem je implementovat (všechny nebo některé) příklady, které jsme měli probírat na cvičení.
• Orientovaný hranově ohodnocený graf (0.5 b)
• Vyberte si jednu z probíraných reprezentací grafu (matice vzdáleností, seznam následníků nebo jeho komprimovaná verze) a implementujte pro ni metody deklarované v souboru 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. (1,2 b)
• Nad implementovanou datovou strukturou pro graf implementujte Dijkstrův algoritmus (verze ze slidů).
• Hlavičkový soubor: ReseniDijkstra.h. V hlavičkovém souboru najdete i stručný popis, co znamenají jednotlivé parametry a co by jednotlivé metody měly dělat.
• Algoritmus pro vyhledání komponent souvislosti neorientovaného grafu. (1 b)
• Nad implementovanou datovou strukturou pro graf implementujte algoritmus pro rozklad grafu na komponenty souvislosti (verze ze slidů).
• Řešení pomocí vlastní implementace zásobníku nebo pomocí knihovní verze.
• Hlavičkový soubor: ReseniKomponenty.h. V hlavičkovém souboru najdete i stručný popis, co znamenají jednotlivé parametry a co by jednotlivé metody měly dělat.
• Příloha:
• Graf.h
• ReseniDijkstra.h
• ReseniKomponenty.h
• main.cpp
• priklad1.txt
• V souboru main.cpp jsou testovací příklady. V souboru priklad1.txt jsou okomentovaná řešení těchto příkladů (pro porovnání Vašich výsledků).
• Vnitřek tříd Graf, ReseniDijkstra, popř. ReseniKomponenty si upravte dle potřeby (při zachování rozumné časové a prostorové složitosti), ale zachovejte rozhraní a vypisované informace (kvůli testování).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s úlohou nebo s moodlem mi napište email.

5. domácí úkol (ze cvičení středa 25.3.2020, čtvrtek 26.3.2020 a pondělí 30.3.2020) : Rozděl a panuj

• Termín vypracování (za plný počet bodů)
• skupina pondělí 9:30: do 6.4.2020
• skupina středa 9:30: do 1.4.2020
• skupina čtvrtek 9:30: do 2.4.2020
• Úkolem je implementovat (všechny nebo některé) příklady, které jsme měli probírat na cvičení.
• Vyhledávání půlením intervalů (binární vyhledávání)
• int vyhledej(int *kde, int co, int n) (0.5 b)
• 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šte metodou rozděl a panuj bez rekurze v čase O(log n). Viz algoritmus na slidech, snímky 4-5.
• Doimplementujte do třídy BinarniStrom konstruktor BinarniStrom(int* klice, const string* hodnoty, int n) (0.5 b)
• Postaví binární vyhledávací strom (s n vrcholy) o optimální hloubce. Klíče a hodnoty vrcholů 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šte metodou rozděl a panuj v čase O(n). Viz algoritmus na slidech, snímky 6-7.
• Deklaraci metody najdete v souboru BinarniStrom.h u zadání minulého domácího úkolu.
• Hanojské věže (1 bod)
  
• Program vyřeší úlohu Hanojských věží (pro zadaný počet kotoučů n) a postup řešení vypíše na obrazovku ve tvaru (např. pro n=5):
  54321 : _____ : _____
  5432_ : 1____ : _____
  543__ : 1____ : 2____
  ...
  _____ : 54321 : _____
• Implementujte funkci void vyres(int n) nebo řešte objektově:
  HanojskeVeze h(n);
  h.vyres();
• Přesné zadání úlohy je na slidech, snímky 8-11. 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) (viz slidy).
• Příklady volání funkcí najdete v příloze tohoto zadání:
• main.cpp
• HanojskeVeze.h
• Přesně dodržte rozhraní funkcí a veřejných metod (stejné parametry a návratové hodnoty) podle souboru main.cpp. Hanojské věže můžete implementovat buď objektově nebo neobjektově (soubor HanojskeVeze.h berte jako návod, ne dogma).
• BONUS: Příklad na počítání (až 0.5 bodu)
• Vyřešte příklady na kuchařku na slidech, snímek 17
• Řešení odevzdávejte včetně stručného postupu podle vzoru na slidech (v elektronické podobě, popř. ručně psané a ofocené)
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s moodlem mi napište email.

4. domácí úkol (ze cvičení středa 18.3.2020, čtvrtek 19.3.2020 a pondělí 23.3.2020) : Binární vyhledávací strom (pokračování)

• Termín vypracování (za plný počet bodů)
• skupina pondělí 9:30: do 30.3.2020
• skupina středa 9:30: do 25.3.2020
• skupina čtvrtek 9:30: do 26.3.2020
• Úkolem je implementovat příklady, které jsme měli probírat na cvičení.
• Doimplementujte další metody třídy BinarniStrom (nemusíte implementovat všechny metody, stačí jen některé):
• void vypisPoVrstváchF(); (0.5 b + 0.5 b + 0.5 b)
  • Vypíše klíče vrcholů ve stromě na konzoli po vrstvách (každá vrstva na jeden řádek).
  • Použijte metodu procházení do šířky pomocí fronty (0.5 b). Viz algoritmus na slidech, snímky 10 a 11.
  • Za vlastní implementaci fronty získáte dalších 0.5 bodu. Komu se nebude chtít implementovat vlastní frontu, můžete alternativně použít třídu queue ze standardní knihovny
  • BONUS až 0.5 bodu: pokud budou klíče ve výpisu odsazené tak, aby byla zřejmá struktura stromu (viz snímek 13). Např. ve tvaru:
    

    				10
    	6						18
    4		7						24

    Pro jednoduchost můžete předpokládat, že každý klíč ,,se vejde'' do 3 znaků.
• void vypisOdsazeneZ(); (0.5 b + 0.5 b + 0.3b )
  • Vypíše klíče vrcholů ve stromě v pořadí PREORDER na konzoli tak, že každý vrchol bude na jednom řádku.
  • Použijte metodu procházení do hloubky pomocí zásobníku (0.5 b). (viz algoritmus na slidech, varianta PREORDER, snímek 8 a 12)
  • Za vlastní implementaci zásobníku získáte dalších 0.5 bodu. Komu se nebude chtít implementovat vlastní zásobník, můžete alternativně použít třídu stack ze standardní knihovny
  • BONUS až 0.3 bodu: pokud budou klíče odsazené podle hladiny, ve které se příslušný vrchol nachází (stejně jako u metody vypisOdsazene, viz snímek 13)
• V rámci testování doporučuji rozšířit přiložené testovací příklady, aby co nejlépe pokryly různé situace.
• Hlavičkové soubory jednotlivých tříd a příklad testovací funkce test() najdete v příloze tohoto zadání:
• Zjednodušená varianta pro studenty, kteří zatím moc neovládají objektové programování (Vrchol je struktura, BinarniStrom je třída)
• main.cpp
• BinarniStrom.h
• BinarniStrom.cpp
• Zasobnik.h
• Fronta.h
• Varianta pro studenty, kteří objektové programování zvládají, tj. např. ASI (Vrchol i BinarniStrom jsou třídy)
• main.cpp
• Vrchol.h
• BinarniStrom.h
• Zasobnik.h
• Fronta.h
• Přesně zachovejte rozhraní třídy BinarniStrom (název třídy a její veřejné metody).  Můžete samozřejmě přidat další atributy a pomocné metody (např. pro rekurzivní volání na podstrom).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s moodlem mi napište email.

3. domácí úkol (ze cvičení středa 11.3.2020, čtvrtek 12.3.2020 a pondělí 16.3.2020) : Binární vyhledávací strom (pokračování)

• Termín vypracování (za plný počet bodů) ! pozor, termín pro vypracování platí, i když bude výuka přerušena
• skupina pondělí 9:30: do 23.3.2020
• skupina středa 9:30: do 18.3.2020
• skupina čtvrtek 9:30: do 19.3.2020
• Úkolem je implementovat příklady, které jsme měli probírat na cvičení.
• Vlastnosti binárního vyhledávacího stromu:
  • Prvek stromu (Vrchol) obsahuje klíč (int) a hodnotu (string) (a ukazatele na levého a pravého následovníka).
  • Pro každý vrchol ve stromě platí, že všechny vrcholy v jeho levém podstromu mají menší hodnotu klíče a všechny vrcholy v jeho pravém podstromu mají větší hodnotu klíče.
  • Strom obsahuje maximálně jeden vrchol s daným klíčem.
• Doimplementujte další metody třídy BinarniStrom (nemusíte implementovat všechny metody, stačí jen některé):
• bool smazPrvek(int klic); (0.8 b)
• Smaže ze stromu vrchol s daným klíčem (vrátí true p.k. takový vrchol ve stromě byl).
• Řešte bez využití rekurze (viz snímky 2-3 v souboru cv4.pdf).
• void vypisPoVrstvách(); (0.5 b)
  • Vypíše klíče vrcholů ve stromě na konzoli po vrstvách (každá vrstva na jeden řádek).
  • Použijte metodu postupného procházení do hloubky (výpis vrstev v cyklu, výpis jedné vrstvy rekurzivní metodou, viz snímky 5-8 v souboru cv4.pdf ).
  • BONUS až 0.5 bodu: pokud budou klíče ve výpisu odsazené tak, aby byla zřejmá struktura stromu. Např. ve tvaru:
    

    				10
    	6						18
    4		7						24

    Pro jednoduchost můžete předpokládat, že každý klíč ,,se vejde'' do 3 znaků.
• BinarniStrom(const BinarniStrom &s); (0.4 bodu)
• tzv. kopírovací konstruktor, vytvoří nový strom (this) jako kopii existujícího stromu s
• lze použít pomocnou rekurzivní metodu pro průchod stromem (PREORDER), viz snímek 4 v souboru cv4.pdf
• V rámci testování doporučuji rozšířit přiložené testovací příklady, aby co nejlépe pokryly různé situace.
• Hlavičkové soubory jednotlivých tříd a příklad testovací funkce test() najdete v příloze tohoto zadání:
• Zjednodušená varianta pro studenty, kteří zatím moc neovládají objektové programování (Vrchol je struktura, BinarniStrom je třída)
• main.cpp
• BinarniStrom.h
• BinarniStrom.cpp
• Varianta pro studenty, kteří objektové programování zvládají, tj. např. ASI (Vrchol i BinarniStrom jsou třídy)
• main.cpp
• Vrchol.h
• BinarniStrom.h
• Přesně zachovejte rozhraní třídy BinarniStrom (název třídy a její veřejné metody).  Můžete samozřejmě přidat další atributy a pomocné metody (např. pro rekurzivní volání na podstrom).
• Pokyny k vypracování:
• Řešení nahrajte do moodle. V případě problémů s moodlem mi napište email.
• Řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 3 " + den Vašeho cvičení (např. "pondělí") + případně vaše jméno.
• Posílejte pouze zdrojové a hlavičkové soubory (ne celý projekt).

2. domácí úkol (ze cvičení středa 4.3.2020, čtvrtek 5.3.2020 a pondělí 9.3.2020) : Binární vyhledávací strom

• Termín vypracování (za plný počet bodů)
• pozor, termín pro vypracování platí, i když bude výuka přerušena
• skupina pondělí 9:30: do 16.3.2020
• skupina středa 9:30: do 11.3.2020
• skupina čtvrtek 9:30: do 12.3.2020
• (2 body) Úkolem je dokončit a odladit příklad ze cvičení.
• Vlastnosti binárního vyhledávacího stromu:
  • Prvek stromu (Vrchol) obsahuje klíč (int) a hodnotu (string) (a ukazatele na levého a pravého následovníka).
  • Pro každý vrchol ve stromě platí, že všechny vrcholy v jeho levém podstromu mají menší hodnotu klíče a všechny vrcholy v jeho pravém podstromu mají větší hodnotu klíče.
  • Strom obsahuje maximálně jeden vrchol s daným klíčem.
• Implementujte následující metody třídy BinarniStrom:
• Konstruktor a destruktor(0.4 b)
• konstruktor inicializuje třídu, destruktor by měl smazat všechny vrcholy (např. rekurzivně).
• void vlozPrvek(int klic, const string& hodnota);(0.5 b)
• Vloží prvek do stromu na správné místo podle klíče (pokud už vrchol s daným klíčem ve stromu je, jen změní jeho hodnotu na novou).
• Vrchol* najdiPrvek(int klic); (0.5 b)
• Vrátí vrchol s daným klíčem (nebo nullptr).
• void vypisInOrder(); (0,3 b)
  • Vypíše prvky stromu jeden po druhém od nejmenšího po největší (zleva doprava) na konzoli. Např. ve tvaru: (2,"stul") (8,"zidle") (10,"vaza")
• void vypisOdsazene(); (0,3 bodu)
• Vypíše prvky stromu na konzoli (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 inorder ve tvaru:
  

  		(4,"ctyri")
  	(6,"sest")
  		(7,"sedm")
  (10,"deset")
  	(18,"deset")
  		(24,"deset")

• Jednotlivé metody můžete, ale nemusíte, implementovat s využitím rekurze.
• V rámci testování doporučuji rozšířit přiložené testovací příklady, aby co nejlépe pokryly různé situace.
• Hlavičkové soubory jednotlivých tříd a příklad testovací funkce test() najdete v příloze tohoto zadání:
• Zjednodušená varianta pro studenty, kteří zatím moc neovládají objektové programování (Vrchol je struktura, BinarniStrom je třída)
• main.cpp
• BinarniStrom.h
• BinarniStrom.cpp
• Varianta pro studenty, kteří objektové programování zvládají, tj. např. ASI (Vrchol i BinarniStrom jsou třídy)
• main.cpp
• Vrchol.h
• BinarniStrom.h
• Přesně zachovejte rozhraní třídy BinarniStrom (název třídy a její veřejné metody).  Můžete samozřejmě přidat další atributy a pomocné metody (např. pro rekurzivní volání na podstrom).
• K zamyšlení:
• Jaká bude maximální, minimální a průměrná složitost jednotlivých metod?
• Zamyslete se nad (rekurzivní) metodou, která by převedla strom včetně jeho struktury např. na řetězec/do pole/zapíše ho do souboru a druhou metodou, která strom (včetně jeho původního tvaru) opět načte
• Pokyny k vypracování:
• Protože stále nefunguje moodle, řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 2 " + den Vašeho cvičení (např. "pondělí") + příp. vaše jméno.
• Posílejte pouze zdrojové a hlavičkové soubory (ne celý projekt).

1. domácí úkol (ze cvičení středa 26.2.2020, čtvrtek 27.2.2020 a pondělí 2.3.2020) : Uspořádaný lineární spojový seznam

• Termín vypracování (za plný počet bodů)
• skupina pondělí 9:30: do cvičení 9.3.2020
• skupina středa 9:30: do cvičení 11.3.2020 (aspoň část metod do cvičení 4.3.2020)
• skupina čtvrtek 9:30: do cvičení 12.3.2020 (aspoň část metod do cvičení 5.3.2020)
• (2 body) Úkolem je dokončit a odladit příklad ze cvičení.
• Vlastnosti seznamu:
• Jedna se lineární spojový seznam se zarážkou.
• Prvek seznamu obsahuje klíč (int), hodnotu (string) 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 následující metody třídy UsporadanySeznam:
• konstruktor, destruktor (0.4 bodu)
• konstruktor inicializuje seznam, destruktor by měl smazat všechny prvky seznamu.
• void vlozPrvek(int klic, const string& hodnota); (0.4 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).
• Prvek* najdiPrvek(int klic); (0.2 bodu)
• Zamyslete se nad efektivnějším algoritmem než známe pro běžný spojový seznam. Využijte toho, že prvky jsou seřazené podle klíče, není třeba procházet celý seznam.
• void smazPrvek(int klic); (0.4 bodu)
• Opět lze využít toho, že prvky jsou seřazené podle klíče, není třeba procházet celý seznam.
• void vypis(); (0.2 bodu)
  
  • Vypíše prvky seznamu jeden po druhém na konzoli (na jeden řádek). Např. ve tvaru: (2,"skrin") (8,"zidle") (10,"stul")
• Možná bude potřeba implementovat i nějaké metody třídy Prvek (např. konstruktor(y)) (0.2 bodu) .
• Rozšířte přiložené testovací příklady pro metody vlozPrvek, najdiPrvek a smazPrvek, aby co nejlépe pokryly možné situace. (0.2 bodu)
• Hlavičkové soubory jednotlivých tříd a příklad testovací funkce test() najdete v příloze tohoto zadání:
• Zjednodušená varianta pro studenty, kteří zatím moc neovládají objektové programování (Prvek je struktura, UsporadanySeznam je třída)
• main.cpp
• UsporadanySeznam.h
• UsporadanySeznam.cpp
• Varianta pro studenty, kteří objektové programování zvládají (Prvek i UsporadanySeznam jsou třídy) (varianta povinná pro studenty ASI)
• main.cpp
• Prvek.h
• UsporadanySeznam.h
• Metody třídy Prvek můžete buď použít tak, jak jsou navržené, nebo si je můžete upravit tak, aby se Vám s třídou dobře pracovalo (nemusíte implementovat metody, které sice jsou deklarované ve vzorovém hlavičkovém souboru, ale nebudete je používat, naopak můžete přidat jiné metody).
• Přesně zachovejte rozhraní třídy UsporadanySeznam (název třídy, její veřejné metody a jejich parametry a návratové hodnoty).
• K zamyšlení: jaká bude maximální, minimální a průměrná složitost jednotlivých metod?
• Pokyny k vypracování:
• Protože stále nefunguje moodle, řešení mi pošlete emailem. Do předmětu zprávy prosím napište "ZALG DU 1 " + den Vašeho cvičení (např. "pondělí") + příp. vaše jméno.
• Posílejte pouze zdrojové a hlavičkové soubory (ne celý projekt).