PA163 ­ VZOR PÍSEMNÉ PRÁCE
1. Jaké znáte konzistenční algoritmy? Rozlište je dle typu konzistence.
2. Jaký je rozdíl mezi kontrolou dopředu (forward checking) a opravdovým úplným po-
hledem dopředu (real full look ahead)?
3. Co to je šířka grafu a jaký je její význam?
4. 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í?
5. 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ředpo-
klady:
(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ů), každá třída může
mít vždy nejvýše jeden předmět
Jednotlivé předměty by měly být do rozvrhu umístěny tak, aby z celkového pohledu
skončila výuka všech předmětů každý den co nejdříve.
Napište model pro tento problém. Především uved'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.
Poznámka: Ve všech příkladech uvádějte vedle zkratek i úplné názvy.