Cvičení probíhají každé úterý od 11:00 v učebně 1342 (budova A).
Body lze získat za:
Zápočet je za
Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229 (prvočíslo!).
kontakt: tomas.valla@fit.cvut.cz
K dispozici je vývojová verze studijních textů, které pokrývají některé kapitoly z předmětu. K něčemu se mohou hodit tyto texty.
Kdo si chce trénovat své algoritmické myšlení nad rámec cvičení (nebo zkrátka jen řešit pěkné úlohy ve volném čase), má možnost.
Doporučuji následující dva zdroje:
Předchozí zdroje obsahují takřka nekonečnou zásobu zajímavých algoritmických úloh, od lehkých po brutální, včetně vzorového řešení, u KSP i s rozsáhlou sadou studijních materiálů.
Podmínky na zápočet. Lze se zbavit záporných hran přičtením konstanty? Dijkstra pro váhy i na vrcholech. Hrany váženy pravděpodobnostmi, hledání nejpravděpodobnější cesty start-cíl.
Modifikace Bellman-Forda pro detekci záporných cyklů. Dokažte, že když v G mezi nějakými dvěma vrcholu u,v existuje sled z u do v i z v do u, potom G obsahuje cyklus. Relace "mezi vrcholy u a v vede cesta" je ekvivalence na vrcholech grafu G a třídy této ekvivalence jsou přesně komponenty souvislosti grafu G. Každý vrcholově 2-souvislý graf je hranově 2-souvislý, opačně to neplatí. Každý vrcholově 2-souvislý graf obsahuje kružnici. Aplikace Havlovy věty na soubory stupňů.
Suploval Ondra Suchý.
Jaké grafy G splňují, ze jejich kondenzace je izomorfní G? Příklad grafu s 5 SSK, kde změma orientace jedné hrany vytvoří jedinou SSK. Jak najít vrchol, který vidí celý zbytek grafu.
Hledání max.toku v zadané síti. Dokazování a vyvracení skutečností ohledně toků. Protipříklad na to, proč nelze volit zlepšující cesty orientované. Hranová i vrcholová míra souvislosti je nejvýše minimální stupeň grafu (a příklady, kdy je tam ostrá nerovnost).
Jak určit hranovou souvislost grafu? PP v 3-reg. grafu obsahuje všechny mosty. Na louce svišti a díry, svišť uběhne d metrů než zaútočí orel, do díry se vleze 1 (nebo k) svišť, kolik se jich zachrání. Šachovnice s dírami, lze kompletně pokrýt dominovými kostkami? Šachovnice s dírami, kolik lze umístit věží, aby se neohrožovaly (přes díru se ohrožují/neohrožují).
Optimální alokace zákazníků na poště k přepážkám. Relace obloukové souvislosti je ekvivalence (zbývá ještě rozmyslet, co když při důkazu tranzitivity mají oba oblouky nekonečně průniků). Nakreslení K_5, K_6 bez křížení na toroid a Möbiovu pásku. Graf je rovinný, právě když jde bez křížení nakreslit na sféru.
V rovinném grafu bez trojúhelníku platí m≤2n-4 a existuje v něm vrchol stupně nejvýše 3. Určení nezávislosti, klikovosti a barevnosti pro několik grafů. Kolik hran má pravidelný dvacetistěn na 12 vrcholech? Jaká platónská tělesa existují (několik výsledků). FirstFit na K_{n,n} dá pro libovolné pořadí vždy 2 barvy. Konstrukce stromu a pořadí, že FirstFit použije hodně barev.
Ukažte, že barevnost rovinného grafu bez trojúhelníku je nejvýše 4. Ukažte, že CNF formule, která má v každé klauzuli právě n proměnných a každá proměnná se vyskytuje nejvýše n-krát, je vždy splnitelná. Výpis nejkratší cesty ve Floyd-Warshallovi. Floyd-Warshallovi stačí jen jedna matice. Součet Fibonacciho čísel a jejich exponenciální růst.