PA163 - VZOR PÍSEMNÉ PRÁCE
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.
15 bodů
2.  Ukažte, jak vypadají propagační pravidla konzistence mezí pro omezení X^ = 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,     Fin2..10,     X#=8-F,     X#>2,     F#\=3
Nastal by v příkladu nějaký rozdíl, pokud bychom místo konzistence mezí použili hranovou konzistenci ?                                                                                      22 bodů
3.  Jaký je rozdíl mezi kontrolou dopředu (forward checking) a opravdovým úplným pohledem dopředu (real full look ahead)?
10 bodů
4.  Co to je šířka grafu a jaký je její význam?                                                           10 bodů
5.  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í?
15 bodů
6.  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).
Napište model pro tento problém. Především uveďte: jaké se v problému vyskytují proměnné, jaký je jejich význam a jejich doména, a jaká jsou potřeba omezení. U každého z bodů napište, jak je jeho řešení realizováno v modelu.
28 bodů
Celkem bodů:
100 bodů