PA163 VZOR PÍSEMNÉ PRÁCE II.
Poznámka: Ve všech příkladech uvádějte vedle zkratek i úplné názvy.
1. Jaké znáte algoritmy stromového prohledávání? Rozčleňte algorimy do skupin podle jejich typu (stejně jako byly uvedeny na přednášce). U každého algoritmu uveďte pouze jeho název a zkratku.
2. Popište rozdíl mezi algoritmy AC-1 a AC-3 a ukažte podrobně, jak tyto algoritmy pracují na následujícím příkladu.
AinL.lO,   BinL.10,    Cin-5..5,   B#<A,    A#=<C + 4
3. Uveďte definici konzistentní cesty. Ukažte příklad konzistentní cesty délky 2 a příklad cesty délky 2, která konzistentní není.
4. Napište algoritmus směrové hranové konzistence. Můžete předpokládat, že máte k dispozici proceduru pro revizi hrany.
5. Princip náhodné procházky je využíván v kombinaci s dalšími algoritmy, uveďte příklad alespoň dvou z nich. Jak se tento princip používá a k čemu se používá?
6. Na příkladu vysvětlete princip algoritmu AC* pro zlepšení kvality dolní meze.
7. Napište kód pro uvedený problém v OPL. Problém: plánování schůzek
Určete čas a místo konání ./V schůzek. Schůzky proběhnou v době od 10 do 19 hodin a každá schůzka má předem určenu svoji dobu trvání (doba trvání je celočíselná kladná hodnota). Schůzky se budou konat v M místnostech.
(a) V každém čase se v každé místnosti smí konat nejvýše jedna schůzka.
(b) První schůzka se musí konat před druhou schůzkou.
(c) Třetí schůzka musí končit stejně jako čtvrtá schůzka.
(d) Páté, šesté, sedmé a osmé schůzky se účastní stejní lidé, a tak nesmí probíhat ve stejném čase.