Kvíz 3

Kvízy jsou dobrovolné, ale doporučené. Umožňují ověřit porozumění pojmům před programovacími projekty. Promysli každou otázku a potom odkryj odpověď. Pokud jsi neodpověděla správně, zvaž, proč jsi jí nerozuměla!

Otázka 1

Který z následujících postupů vždy najde stejné řešení, i když algoritmus spustíš vícekrát?

Předpokládej úlohu minimalizace nákladové funkce, kde každý stav má jiný náklad.

• Hill climbing s nejstrmějším výstupem, pokaždé z jiného počátečního stavu.
• Hill climbing s nejstrmějším výstupem, pokaždé ze stejného počátečního stavu.
• Stochastický hill climbing, pokaždé z jiného počátečního stavu.
• Stochastický hill climbing, pokaždé ze stejného počátečního stavu.
• Oba, nejstrmější i stochastický hill climbing, pokud pokaždé začínáš ze stejného stavu.
• Oba, nejstrmější i stochastický hill climbing, pokaždé z jiného počátečního stavu.
• Žádná varianta hill climbing nezaručuje pokaždé stejné řešení.

Otázka 2

Uvažuj tuto optimalizační úlohu:

Farmář chce vysadit plodiny 1 a 2 a maximalizovat zisk. Každý akr plodiny 1 mu přinese zisk 500 dolarů, každý akr plodiny 2 zisk 400 dolarů.

Všechno však musí vysadit dnes během 12 hodin mezi 7. a 19. hodinou. Výsadba akru plodiny 1 trvá 3 hodiny, plodiny 2 trvá 2 hodiny.

Omezené jsou také zásoby: vystačí na 10 akrů plodiny 1 a 4 akry plodiny 2.

Proměnná C1 označuje počet akrů plodiny 1 k výsadbě a C2 počet akrů plodiny 2.

Jaká účelová funkce je pro tuto úlohu správná?

• 500 * C1 + 400 * C2
• 500 * 10 * C1 + 400 * 4 * C2
• 10 * C1 + 4 * C2
• -3 * C1 - 2 * C2
• C1 + C2

Otázka 3

Uvažuj stejnou optimalizační úlohu jako v otázce 2. Jaká jsou její omezení?

• 3 * C1 + 2 * C2 <= 12; C1 <= 10; C2 <= 4
• 3 * C1 + 2 * C2 <= 12; C1 + C2 <= 14
• 3 * C1 <= 10; 2 * C2 <= 4
• C1 + C2 <= 12; C1 + C2 <= 14

Otázka 4

Uvažuj následující graf splňování podmínek pro plánování zkoušek. Každý uzel je předmět s počáteční doménou možných dnů zkoušky. U většiny je to pondělí, úterý či středa, některé už mají jediný den. Hrana mezi uzly znamená, že zkoušky těchto předmětů musejí být v různé dny.

Jaké budou domény proměnných C, D a E po prosazení hranové konzistence celého problému?

• Doména C je {Mon}, D je {Mon, Wed}, E je {Tue, Wed}.
• Doména C je {Mon}, D je {Tue}, E je {Wed}.
• Doména C je {Mon}, D je {Wed}, E je {Tue}.
• Doména C je {Mon, Tue}, D je {Wed}, E je {Mon}.
• Doména C je {Mon, Tue, Wed}, D je {Mon, Wed}, E je {Mon, Tue, Wed}.
• Doména C je {Mon}, D je {Mon, Wed}, E je {Mon, Tue, Wed}.