Zkouška 1.2.2010
Napsal: 2. 2. 2010 10:25
Skúška bola naraz AI a CSP. AI dostali test: 15 otázok, na každú práve jedna správna odpoveď. Potrebné mať 11 správnych. Potom dostali problém a mali na jeho riešení demonštrovať niektorú z techník, ktoré sa preberali.
Na CSP sa dostal papier so zadaním - zadania boli približne: Lokálne prehľadávanie, nebinárne podmienky, hranové a podobné konzistencie... - jedna téma na jedného človeka.
Moja téma: Algoritmy lokálneho prehľadávania, základné definície a vlastnosti, HC, MC, RW, Tabu, GSAT, GENET.
Čo som nevedel (a neviem, či to bolo v slidoch):
Pri Tabu: miesto ukladania stavov tam ukladáme smer, ktorým sme prišli: ktorú premennú a na čo sme ju zmenili. Tento krok opakujeme iba v prípade, že zlepšíme ohodnotenie na lepšie, ako sme doteraz niekedy mali. Keyword: aspirační kritérium (asi)
Pri GSATe: Dva rozdiely proti HC: 1) Pri nájdení lokálneho extrému (keď sa GSAT pláca na mieste), si zapamätáme, ktoré klauzule sme nezistili a tie prehlásime za ťažké a po resete im zvýšime váhu (nie v každom kroku). 2) pri resete sa pozrieme na dve predchádzajúce lok. extrémy (tam, kde sa GSAT zasekol) a premenné, na ktorých sa zhodovali ohodnotíme tak, ako boli tam.
Pri GENETE: váhy hrán zvyšujeme zasa až keď sa algoritmus stratí v lokálnom extréme (teda nie v každom kroku).
Na CSP sa dostal papier so zadaním - zadania boli približne: Lokálne prehľadávanie, nebinárne podmienky, hranové a podobné konzistencie... - jedna téma na jedného človeka.
Moja téma: Algoritmy lokálneho prehľadávania, základné definície a vlastnosti, HC, MC, RW, Tabu, GSAT, GENET.
Čo som nevedel (a neviem, či to bolo v slidoch):
Pri Tabu: miesto ukladania stavov tam ukladáme smer, ktorým sme prišli: ktorú premennú a na čo sme ju zmenili. Tento krok opakujeme iba v prípade, že zlepšíme ohodnotenie na lepšie, ako sme doteraz niekedy mali. Keyword: aspirační kritérium (asi)
Pri GSATe: Dva rozdiely proti HC: 1) Pri nájdení lokálneho extrému (keď sa GSAT pláca na mieste), si zapamätáme, ktoré klauzule sme nezistili a tie prehlásime za ťažké a po resete im zvýšime váhu (nie v každom kroku). 2) pri resete sa pozrieme na dve predchádzajúce lok. extrémy (tam, kde sa GSAT zasekol) a premenné, na ktorých sa zhodovali ohodnotíme tak, ako boli tam.
Pri GENETE: váhy hrán zvyšujeme zasa až keď sa algoritmus stratí v lokálnom extréme (teda nie v každom kroku).