Programovani 2 Matematici, 
03.04.2024 st - teoreticke a cviceni
04.04.2024 ct - prakticke cviceni

04.04.2024 ct - teoreticke a prakticke cviceni


Teoreticke cviceni 

1. Heap
- definition
- insert, extract, height, time complexity, build heap in linear time (data random dle studentu u tabule)
- BT vs array implementation
- visualgo: https://visualgo.net/en/heap
-- studenti: vytvorte haldu z posloupnosti (tu, kterou jsme zvolili) čísel přímo v poli (v čase: a) O(nlogn), b) O(n))
(create nlogn vs n; extract; BinTree form vs Array form)

2. BST
- definition
- find, insert, delete, time complexity
- height, degeneration, balance, 
- visualgo: https://visualgo.net/en/bst

3. Graph algos 
DFS + BFS: T -> BT (BST) -> n-arni T -> connected Graph -> unconnected Graph -> oriented Graph -> State Space

Jak se změní DFS a BFS algoritmu změníme-li průchod BT na obecný n-arní strom?
Jak se změní DFS a BFS algoritmu změníme-li průchod obecným n-arním stromem na souvislý graf?
Jak se změní DFS a BFS algoritmu změníme-li průchod souvislým grafem na obecný i nesouvislý graf?
Jak se změní DFS a BFS algoritmu změníme-li průchod souvislým grafem na obecný (i nesouvislý) orientovaný graf?


Jak reprezentovat grafy?
Převody reprezentací grafů


Prakticke cvičení
4.	Upravte DFS z verze pro BT na verzi pro souvislý graf zadaný seznamem sousedů

4.2 	Napiste rekurzivni funkci dfs_recursive(g, v), ktera projde
	souvisly graf g (zadany seznamem sousedu) z vrcholu v do hloubky

4.2.1	Co vypíše dfs_recursive(g, v) pro PREorder/POSTorder průchod pro případy:
		dfs_recursive(g01, 0) PREorder vs POSTorder
		dfs_recursive(g01, 2)
		dfs_recursive(g02, 0) jine komponenty
		dfs_recursive(g02, 6) jine komponenty
	note: v jakem poradi jsou razeny (prochazeny) potomci?   


4.3 	Napiste NErekurzivní funkci dfs(g, v), ktera projde 
	souvisly graf g (zadany seznamem sousedu)do hloubky z vrcholu v   

4.3.1	Co vypíše dfs_recursive(g, v) pro preorder průchod pro případy:
		dfs_recursive(g01, 0)
		dfs_recursive(g01, 2)
		dfs_recursive(g02, 0)
		dfs_recursive(g02, 6)



5 	Napiste funkci pocet_kompoment(g), ktera pro zadany graf (seznamem sousedu) vrati pocet kompoment grafu

7.	Vytvořte funkci, která rozhodne, zdali je zadaný graf souvislý 
8.	Vytvořte funkci, která spocita pocet kompoment grafu a jednotlive komponenty vypíše

9.	Vytvořte funkci, která rozhodne, zdali zadaný souvislý graf obsahuje kružnici
10.	Upravte BFS z verze pro BT na verzi pro souvislý graf zadaný seznamem sousedů


12.	Vytvořte funkci, která rozhodne, zdali je zadaný graf bipartivní
13. 	Vytvořte funkci, která vypiše všechny kružnice v grafu procházející zadaným vrcholem V (každou kružnici právě jednou)
14. 	Vytvořte funkci, která vypiše všechny kružnice v grafu (každou kružnici právě jednou)
16.	Vytvořte funkci, která pro zadany vrchol A urci nejdelsi cestu z vrcholu A do libovolného vrcholu v souvislém grafu
(17.	Vytvořte funkci, která pro zadany vrchol A urci nejdelsi cesty do libovolných vrcholů souvislého grafu)

18.	Vytvořte funkci, která pro zadany výchozí vrchol A určí nejkratsi cestu (mereno poctem hran) do zadaného cílového vrcholu V

20.	Dijkstra, centralita, silně vs. slabě souvislý graf, topologické uspořádání, kostra, minimalni