PA163 VZOR PÍSEMNÉ PRÁCE I.
Poznámka: Ve všech příkladech uvádějte vedle zkratek i úplné názvy.
1. Jaké znáte konzistenční algoritmy (uveďte pouze názvy)? Rozlište je dle typu konzistence.
2. Ukažte, jak vypadají propagační pravidla konzistence mezí pro omezení Xj^ = Z — Y. Ukažte postupný průběh propagací (včetně aplikace Vámi navržených propagačních pravidel) při použití konzistence mezí v následujícím příkladu.
Xinl.,10,    y in 2..10,   X#=8-Y,   X #> 2,    Y #\= 3
Nastal by v příkladu nějaký rozdíl, pokud bychom místo konzistence mezí použili hranovou konzistenci ?
3. Jaký je rozdíl mezi kontrolou dopředu (forward checking) a opravdovým úplným pohledem dopředu (real full look ahead)?
4. Jaký je rozdíl mezi výběrem proměnných left afirst-fail? Demonstrujte tento rozdíl na příkladu.
5. Co to je šířka grafu a jaký je její význam?
6. Napište (nebo alespoň slovně popište) algoritmus prohledávání s tabu seznamem. Je Váš algoritmus kombinován s nějakou další metodou lokálního prohledávání?
7. Napište kód pro uvedený problém v OPL. Problém: školní rozvrh.
Určete čas a místo výuky pro množinu předmětů, jestliže platí následující předpoklady:
(a) rozvrh je na 5 školních dnů a každý den má 10 hodin
(b) u každého předmětu je určena doba jeho trvání; výuka předmětu musí probíhat bez přerušení (tj. nesmí např. začínat jeden den večer a končit druhý den ráno)
(c) v každé místnosti je nejvýše jeden předmět v danou dobu
(d) každý předmět je vyučován pro konkrétní třídu (skupinu žáků), tj. pro každou třídu je zadána množina jejích předmětů; každá třída může mít vždy nejvýše jeden předmět v danou dobu
Jednotlivé předměty by měly být do rozvrhu umístěny tak, aby výuka v rámci celého týdne skončila co nejdříve (např. v pátek dopoledne).