Zkouška 1.2.2010

Přednáška podává přehled o technikách programování s omezujícími podmínkami. Zaměřena je na algoritmy splňování podmínek a na problematiku řešení příliš omezených systémů podmínek. Zabývá se také praktickým využitím omezujících podmínek při řešení reálných problémů.
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Zkouška 1.2.2010

Příspěvek od Stevko »

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).
Odpovědět

Zpět na „OPT042 Programování s omezujícími podmínkami“