Alg a Prg

Náhradní výuka
kdy: úterý 07.01.2025 10:00 (hlasovaním ve třídě)
jak: onlajn (hlasovaním ve třídě)
kde: Teams, link zaslan emailem


ALGORITMIZACE 

2. QuickSort
- demonstrace quicksortu 
- vliv a metody vyberu pivota

2.5 využití QuickSortu k hledání k-nejmenšího prvku

3. MergeSort


PRUCHODY GRAFEM a GRAFOVE ALGORITMY

0. meli jsme pruchod stromem, tedy souvislym grafem bez kruznic
presneji prochazeli jsme binarni strom

take jsem si vyzkouseli ruzne druhy pruchodu:
  a] do hloubky (rekurzi i zasobnikem)
  b] do sirky frontou

a pro pruchod do hloubky jsme meli pre-, in- a post- order poradi

Nyni rozsirime prochazeni stromu na obecny graf:
  a] souvisly graf - resime cykly resp. navstivene vrcholy
  b] nesouvisly graf - navic resime kompomenty grafu

a nasleduje pruchod stavovym prostorem (soused stavu neni "pevne zadratovan jako v pripade grafu", ale je generovan dle pravidel


Reprezentace grafů: 
a] matice sousednosti
b] matice incidence 
c] seznam sousedu
d] seznam vrcholu a hran
- jak se zmeni reprezentace grafu pro orientovany graf?
- jak se zmeni reprezentace grafu pro ohodnoceny graf?

3. Naimlementujte DFS průchod souvislým grafem
3.5 Naimlementujte DFS průchod NEsouvislým grafem
- pruchod grafem vs pruchod grafem z vrcholu
- pre in post order

5. Naimlementujte BFS průchod souvislým grafem
5.5 Naimlementujte BFS průchod NEsouvislým grafem
- pruchod grafem vs pruchod grafem z vrcholu

7. Napiste program, ktery rozhodne, zdali zadany graf G je bipartitni
8. Napiste program, urci topologicke usporadani grafu, pokud existuje a pokud neexistuje vrati hodnotu -1

11. Algoriumus vsech korektnich uzavorkovani 
- 2 podminky


5. VYHODNOCENI ARITMETICKEHO VYRAZU

PREfix, INfix, POSTfix format zapisu

Mejme aritmeticky vyraz ((6/3)+2)*(4-1)

1. Sestrojte odpovidajici strom aritmetickeho vyrazu
2.0 Vhodnym pruchodem stromu urcete prefix zapis (jsou nutne zavorky?)
2.1 Vhodnym pruchodem stromu urcete postfix zapis (jsou nutne zavorky?)
2.2 Vhodnym pruchodem stromu urcete infix zapis? (jsou nutne zavorky?)

3.0 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou stromem
3.1 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou prefixovym zapisem 
3.2 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou postfixovym zapisem

4.0 Prevedte postfix zapis na prefix (bez vyuziti stromu vyrazu)
4.1 Prevedte prefix zapis na postfix (bez vyuziti stromu vyrazu)
4.2 Prevedte infix zapis na postfix (bez vyuziti stromu vyrazu)
4.3 Prevedte infix zapis na prefix (bez vyuziti stromu vyrazu)

5.1 Vyhodnotte vyslednou hodnotu aritmetickeho vyrazu zadanou infixovym zapisem

6.1 Postavte strom vyrazu z prefix notace
6.2 Postavte strom vyrazu z postfix notace