Dneska bylo pomerne hodne odlisne zadani. Vypadalo velmi zhruba takhle: - krizenim dostaneme genotyp neodpovidajici reseni. co s tim? napsat 3 moznosti - intensifikace u tabu search - napsat kostru genetickeho algoritmu s explicitnim pouzivanim stavebnich bloku (nebo tak nejak :) ) - zadanej graf s ohodnocenejma uzlama a u toho napsano, ze to ohodnoceni je hodnota ceny pro danej stav. zadano, ze algoritmus zacne v uzlu A a projde postupne uzly A E F a tam skonci. z tech hodnot se ma vycist, co to je za heuristiku (best-first to myslim bylo) - bisekce grafu: dokazat ze je NP...klasika pres certifikat - co jsou u bisekce grafu vst. promenny, konf. prom. a preformulovat na optimalizacni problem, ve finale jeste prevest na 0,1 linearni programovani (wtf?) - co umoznuje Karpova redukce - odpoved byla jen prevod mezi rozhodovacimi problemy - co umoznuje Turingova redukce - prevod mezi rozhodovacimi, optimalizacnimi a konstruktivnimi problemy + dukaz ze problem je NPH - globalni metody - dekompozice, nepotrebujou stavovy prostor, rekurze, polynomialni - neco s APX To je snad zhruba vsechno. Ustni byla bleskova, jen prosel pisemku a SAT a i kdyz jsem mel blbe ty geneticky algoritmy, vubec jsem nemel prevod na linearni programovani, tak skoro uvazoval o jednicce, ale jeste jsem mel blbe tu Karpovu redukci a navic jsem to zmotal i kdyz to po mne chtel ustne, takze rekl: "Bohuzel za 2" :). Rekl bych ze to je vcelku pohodova zkouska. Ucil jsem se na to vlastne jen necelej jeden den. Clovek se hodne nauci pri tech ulohach. =================================================================================================== Ahoj, tak co si tak matne vzpominam ze me prekvapilo (doufam ze svym volnym podanim otazek nekoho nezmatnu:)) - Turingova redukce - k cemu vsemu se pouziva - Dynamicke programovani - pribylo spravnych moznosti (ze je pseudopolynomialni napr u batohu, ze muze zaviset i na jinych instancich, atd) - je celociselne lin.programovani komb. problem?? pribyla kolonka "proc?":-) - diversifikace u tabu search - dokazat ze problem je NP (zadan problem "bit packing", ovsem jevil se mi spise jako NPO:-), klasicky pres certifikat a je..) - jak zajistit odolnost GA vuci statistickym vlastnostem ci tak nejak [ranking, scaling] Pokud si nekdo jeste neco pamatujete, doplnte me.. Jinak mohu potvrdit prijemny dojem z teto zkousky i z predmetu celkove. =================================================================================================== Písemka podobná jako u předešlých příspěvků-3 strany A4, něco zaškrtávací, něco doplňovací, 1.příkald trochu obšírnější - dnes tento: máme n elementů množiny e1...en a m množin s1..sm, každá množina obsahuje nějaké z těch elementů. Dokázat, že algoritmus hledající minimální úplné pokrytí, tj. takovou podmnožinu množin s1..sm, aby platilo, že každý element je aspoň v jedné množině a že počet množin je minimální, je NP. Pozn: ani většina studentů, ani Schmidt si neuvědomila, že to není NP, ale NPO - optimalizace na minimum. Ale protože to tak napsal, nevadilo mu, když jsme si z toho udělali virtuálně rozhodovací problém. Důkaz pak byl klasický přes certifikát, stačilo ověřit že kontrola nějakého certifikátu X (každý prvek xi je 0 či 1 dle toho zda množina i do řešení patří) je polynomiální. Dále chtěl napsat co je certifikátem (to zvolené x), jaké jsou konfig.proměnné (právě vektor X e {0;1}^m ). Nakonec to chtěl převést na vhodný typ lineárního programování, tj. napsat lin.rovnice-jde o minimalizační problém, tj.jsou ve tvaru cx MIN!, Ax >= b, x>=0. Z dalších témat písemky: -Turingova redukce-zaškrtnout co je správně (správně je např. že slouží k důkazu že problém je NPH či NPC-na to stačí i Karpova, která je ale spec.případem Turingovy) -chceme dokázat že alg. patří do tř. FPTAS (existuje plně polynomiální aprox.schéma)-dotaz je co musíme hlavně dokázat. Postačující odpověď: jeho čas výpočtu polyn.závisí na 1/epsilon, kde epsilon je relat.chyba -jaké údaje u sekvenční paměti v tabu search (hledal v odpovědi hlavně klíčové slovo atributy) -další věci podobné jako u zde zveřejněného termínu z 17.9.2005 jako: náznak algoritmu pro zvolení vých.teploty sim.ochlazování v závislosti na velikosti instance (tj. stručně popsat zpětnovazební řízení ze slidů), PN problém-zaškrtnout správné vlastnosti (klasický propadák-NP neznamená že je NEpolynomiální atd., platí že jeho certifikát lze ověřit v P čase...) Písemka byla na 35minut, na stihnutí je to tak akorát, nad ničím ale dlouho nepřemýšlejte, jinak to moc nestihnete. -----ÚSTNÍ:------ U ústní to pak s vámi prochází a na chybu podá vysvětlení, případně ho chce po vás, tj. vyplatí se po písemce podívat např.do slidů, jak to mělo správně být. SAT úlohu se snaží číst, pokud mu však během čtení sami začnete vysvětlovat, jak jste to dělali a sami ho navigovat po grafech atd. jako já, tak rád bude místo čtení poslouchat, případně se pozeptá. Nerozhodnost známky řeší tak, že znova kukne do testu, a u tématu, kde jste chybovali, se zeptá např. na definici, porovnání. U mě např. u Turingovy redukce-jak je definovaná, jak souvisí s Karpovou. Jinak statistika známek z termínu 14.6., na kterém bylo 12 lidí: 3x za 1,7x za 2,1x za 3 a 1x za 4. takže celkem OK. Tak hodně úspěchů. =================================================================================================== Snazil jsem se co nejvic priblizit originalu.... Podtrzitka znamenaji misto pro vasi vlastni odpoved, tedy neplati jako driv, ze byla vetsina otazek testoveho typu (a,b,c....) Tech je tedy opravdu minimum..... 1.)Problem linearniho programovani je charakterizovan: vyst. promennymy, ktere nabyvaji hodnoty z mnoziny :_____________ vst. promennymy, ktere nabyvaji hodnoty z mnoziny :______________ omezujicimy podminkami, ve tvaru : ______________________________ optimalizacnim kriteriem ve tvaru: ______________________________ // nemel jsem, ale pak jsem ty pruniky mnozin nasel v sesite s poznamkami :-{ // je to docela easy 2.)linearni programovani je : a) kombinatoricky problem b) neni kombinator. problem // odp. b urcite , ale lze prevest na komb. problem. Pokud to tam napisete, // bude spokojen ale zepta se jak to stim prevodem je... Takze v mem pripade // docela komedie... 3.) Turnaj. vyber rodicu : celk. populace=100, turnaje se vzdy ucastni 15 ucastniku , mutace =40%, reseni tohoto gen. alg je nekvalitni. navrhnete zlepseni. ________________________________________________________________________ //odpovedel jsem :Snizeni poctu ucastniku v turnaji, aby se zmensil tlak na vyber a bylo to OK 4.) Gen alg pouziva ruletovy vyber, pouziva se vyber rodicu pomoci fitness funkce podle zdatnosti. ...a ted neco ke konvergenci toho reseni, ve smyslu ,ze bud to reseni konverguje pred optimem nebo az za optimalnim reseni a meli jsme navrhnout opet zlepseni... _______________________________________________________________________ //odpoved byla ranking, a jeste neco kolem ty rulety , a ja mel naky ne uplne nesmysl, // rikajici asi toto : Ze jeden z rodicu se tedy vybere podle fintness fce a druhy // nahodne , aby se zvysila ruznorodost a u ustni brblal ze : // "To tady rika kazdy a nevim kde to berou... Rika vam neco ranking?? Ano ? No slava. :-)) 5.) vlastnost kterou musi splnovat operator krizeni gen. algoritmu v TSP (travelling sales person) _____________________________________________________________________ // nemel jsem.... Ale kolega rikal cosi o schematech, ze by ten // operator nemel nabouravat schemata jednotlivych algoritmu..no nevim, zni to // logicky. . 6. )Druhy informaci , ktere pri behu uschovava a pouziva k modifikaci behu metoda tabu 1. _______________________________ 2. ____________________________________ // ja napsal ty atributy vychoziho a koncoveho stavu ale spis clovek mel vedet //jak je to svazane s tou historii, tedy sekvencni a frekvencni historie a jak to //na sobe zavisi....:-) 7.) strucne popiste alg. kterym simul. ochlazovani nastavi pocatecni teplotu v zavisloti na velikosti instance // Tady bylo cca 5 cm mista na ten alg - ja to tedy nechal prazdne :-) 8.) hlavni vlastnost sim. ochlazovani: __________________________________________________________ // ja napsal ze pripousti mirne zhorseni a bylo to OK 9.) Dana instance kombinatorickeho problemu nema reseni. Prohleda metoda "NEJLEPSI NEJDRIVE" cely stavovy prostor ? ______________ // odp. ze ANO, a dobra je i zminka o prioritni fronte resp ono to z toho // vychazi a kdyz tam mate NE, jako ja... tak se pta proc ne a jak je to //implementovane..no a je tam nejak prioritni fronta a aby ji naplnil tak // asi musi prolezt vsechno... 10. ) jednoduchy systematicky aloritmus prohledavani je zalozen na strukture open jako fronta, o jake prohledavani jde? ___________________________________________________________________ // odp. ja napsal ze iterativni, ale chtel vedet jestli do sirky nabo do // hloubky a myslim, ze kdy jsem rekl ze do sirky tak spokojene zabrucel... 11. ) Na cem zavisi slozitost pseudopolynomialniho alg. ? ________________________________________________________ // tezko rict.....:-))))) 12.)Dynamicke programovani a.) poskytne vsechna existujici reseni instance NP-tezkeho problemu (NPH) b.) poskytne 1 reseni optimalni, NPH problemu, jestlize existuje c.) jeho vypopcetni slozitost je polynom. s velikosti instance // ted uz fakt nevim, co tam melo byt myslim ze b.) protoze pri dyn. prg se prochazi // cely stavovy prostor, sice dekompozici, ale prochazi se a tak by se melo ve // vysledku objevit to nejlepsi reseni, tedy kdyz existuje..Ale je top jen moje // teorie a priznam se ze ani nevim jestli to bylo OK 13.) mame problem Pi a mame dokazat, ze patri do tridy NPH, pouzijeme: a.) dukaz ze kazdy problem z NP lze prevest na Pi b.) dukaz ze problem Pi lze prevest na kazdy problem z NP c.) dukaz ze lze kazdy znamy problem z NPC prevest na Pi d.) dukaz ze lze Pi prevest na znamy NPC // urcite bylo a pac jsem ho nemel....A myslim ze c 14.) K tomuto dukazu pouzijeme a.)karpovu redukci b.)turingovu redukci // tady bylo tutove b 15.)trida NPC je trida problemu, ktere a.) nemohou mit polynom. algoritmus b.) jsou nejstezsimi z NP c.) jsou na sebe navzajem prevoditelne Karpovou redukci 16. ) problem kliky a.) dokazat, ze patri do NP - opet asi 5 cm mista na dukaz... // ted uz nevim presne, nejak jsem se v tom zamotal.... b.) jake jsou konfiguracni promenne kliky ? ???_________________________ // prazdno c.) Co je certifikatem kliky ? ________________________________________ // tady stacilo ze certifikatem je vysledny graf, resp podgraf V' , ja to napsal // jinak , tedy svymi slovy a pak jsem to u ustni casti upresnil...a nastesti OK 17.) Minimalizacni problem Q(s)- optimalizacni krtiterium reseni S - instance I. Mame dokazat ze Alg. A je aproximacni.Jak provedeme dukaz? (sorry, tady to ted po sobe skoro neprectu, je mi fakt lito kdyz to nebude davat smysl, me to tedy moc smysl nedavalo ani pri pisemce ) a.) pro kazdou instanci I v kazde iteraci A optim. kriteria Q(S) v tom kroku se blizi optim. hodnote a alg. skonci v polynom. poctu kroku... b.) pro kazdou instanci I alg. skonci v polynom. poctu kroku, dale pro hodnotu opt. kriteria poskytnuteho reseni S a opt. reseni T plati, ze Q(T)/Q(S)<=K, kde K je konstanta . // tady si myslim, ze bylo ok varianta b, ale ruku do ohne za to nedam =================================================================================================== 1. kombinatorický problém PI je charakterizován souhrnem násl. objektů a výstupní proměnné b konfigurační proměnné c vstupní proměnné d ohodnocení výstupních proměnných e ohodnocení vstupních proměnných f ohodnocení pomocných proměnných g podmínkami omezujícími hodnoty vsupních proměnných h podmínkami omezujícími hodnoty konfiguračních proměnných i v případě optimalizačního problému optimalizační kritéria f v případě rozhodovacího problému certifikát (abcgh) 2. nech fce f(n) je 2^n pro n < 256, 3n^2 pro ostatní a O(n^2) b O(2^n) c O(3n^2) (ac) 3. nech je dáno plně polynomiální aproximační schéma A řešící optimalizační problém PI, pro libovolné 0