Kde: Budova E na Karlově Náměstí, místnosti ještě upřesníme, probíhají stavební úpravy. |
---|
.
Výchozí program, může se měnit podle přání a potřeb účastníků: |
---|
Den | Dopoledne 9:00-11:30, odpoledne 12:30 – 17:00 s přestávkou podle potřeby. Průběžně se střídá výklad a programování cca po 60-90 minutách. |
---|---|
Po 18.9. | Graf, grafové pojmy a grafové vlastnosti, reprezentace grafu v paměti. Přehled hlavních grafových úloh. Neformální výklad asymptotické složitosti, ukázky na kódech, O/Θ/Ω notace. |
Út 19.9. | BFS, DFS, fronta, zásobník, jednoduché prohledávání grafu. Prioritní fronta, halda. Seznámení s Graphviz. |
St 20.9. | Dijkstra s prioritní frontou. Porovnání efektivity probraných postupů. Přehled řešitelných a neřešitelných úloh |
Celkem | Napište nám své připomínky a komentáře: Reakce účastníků LASO |
Slidy: Úvodní grafový přehled ( pdf).
Úloha 1.
Načtěte nevážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.
Úloha 2.
Načtěte vážený graf ze souboru a vypište k každému uzlu jeho seznam hran. Stáhněte si data s obrázky.
Úloha 3.
V daném grafu zjistěte pro každý možný stupeň uzlu D, kolik je takových hran, jejichž oba koncové uzly mají tento stupeň D. Pro každý stupeň tento počet hran vypište. Porovnejte své výsledky s ukázkovými. Stáhněte si data s obrázky.
Úloha 4.
Jindra vyrazí z uzlu A, který má určitý stupeň D. Pak jde do některého jeho sousedního uzlu B a nezajímá se o stupeň uzlu B. Z uzlu B se přesune do uzlu C, který je sousedem B a není to A. Jindra trvá na tom, že stupeň D startovního uzlu A i stupeň cílového uzlu C musejí být stejné. Určete, kolik je v daném grafu možností procházek podle Jindrových pravidel. Vypište toto jediné číslo na výstup. Stáhněte si data s obrázky.
Úloha 5.
Řekneme, že hrana H je lokálně minimální, pokud její váha je striktně menší než váha kterékoli hrany, která s H sdíli jeden uzel. Najděte v daném váženém grafu všechny lokálně minimální hrany a vypište je v rostoucím lexikografickém pořadí jejich krajních uzlů. Stáhněte si data s obrázky.
Úloha 6.
Určete, kolik je trojúhelníků v každém grafu úlohy 4. Trojúhelník je trojice uzlů, v níž každý uzel sousedí se zbylými dvěma uzly.
Úloha 7.
Určete, kolik je kružnic délky 4 v každém grafu úlohy 4. Kružnice nesmí obsahovat příčku, tj. první a třetí uzel v kružnici nesmí spolu sousedit a druhý a čtvrtý uzel v kružnici spolu nesmí sousedit.
Slidy: Prohledávání grafu, halda
Úlohy na odpoledne:
seq.txt
. Na každém řádku máte jeden z příkazů insert <number>
a remove
. Příkaz insert <number>
vloží číslo <number>
do zásobníku. Příkaz remove
odstraní prvek ze zásobníku a vypíše ho na standardní výstup.
graph.txt
jako neorientovaný graf. Ten je definovaný ve stejném formátu jako včera.
graph.txt
jako orientovaný graf.
remove
chápejte jako extract-min
.
extract-min
hledejte minimum naivně pomocí procházení celého pole.
seq.txt
, operace remove
ignorujte.
Graphviz:
Slidy: Dijkstrův algoritmus
Data pro testování Dijkstry: txt, výsledek, implementace (složka src/day3)