# Zkouska 101 u prof. Kuceru - 24.04.2007

<{ForumPost(poster="neoangin", timestamp=2007-04-24 10:44:00)}>
Dnes som sa ako jediny dostavil na skusku. Chystali sme sa dvaja :).  
  
Prvy dolezity (motivacny) moment bol zapisanie zapoctu, ktory mi po prelozeni dvoch clankov z anglickej wikipedie do ceskej wikipedie udelil Jan Jakubuv. Ked vam cvicici zapise zapocet a zazela vela uspechu na skuske, je to pre studenta vzdy velka vzpruha. To bolo o 8:58.  
  
V labe som si este na chviklu sadol a pozrel sa na Aho-Corasickovu (co robia algoritmy 2 a 3). Po desiatich minutach som vsatal a siel na skusku. V ruke som mal knihu 'Uvod do teoreticke informatiky', v ktorej som mal index. Cestou ma napadlo, ze to moze byt mala psychologicka finta na principe hry Asociacie - ked pan profesor uvidi tuto knihu, pride mu na um Vyhladavanie v texte (to je jedina tema v tejto knihe, ktora sa na ADS 2 hodi) a zada mi to.  
  
O 9:10 som zaklopal panovi profesorovi na dvere pracovne, posadil som sa u neho a dal mi vyhladavanie v texte  :o  :shock:  8)  :lol:  :D  :P  :wink:   
  
Na jednu A4 som napisala toto:

 > Najefektivnejsia metoda vyhladavania v texte pre abecedu EPSILON a mnozinu vzorov K=(y1,...,yk) je metoda AHO-CORASICKOVE, kt. pracuje v casovej zlozitosti O(l+n). (pricom l je dlzka vzorov a, n je dlzka prehladavaneho textu.)  
 > SCHEMA METODY  
 > Vzorky->Prekladac(Alg 2->Alg 3)->Vyhladavaci stroj  
 > Vyhladavaci stroj+text->Interpret(Alg 1)->Vyskyty  
 > VYHLADAVACI AUTOMAT pro abecedu EPSILON a mnozinu vzorov K  
 > M(Q,g,f,out), kde  
 > Q = {0,...,q} je mnozina stavov  
 > g: Q x EPSILON -> Q u {otocene T} je prechodova funkcia  
 > f: Q -> Q je fail funkcia ( f(0)=0 )  
 > out: Q -> PK je vystupna funkcia  
 > Pre korektnost vyhladavacieho stroja musia byt splnene tieto podmienky:  
 > A) Ak spojime pre Q a sigma z EPSILON stav s so stavom g(s, sigma) hranou, dostaneme strom, ktoreho koren je 0.  
 > B) A)+ak pre stav s a pismenko sigma je g otocene T, potom automat prejde na stav reprezentujuci najdlhsiu predponu, kt. bola v povodnom stave pripona (KOREKTNA FAIL FUNKCIA)  
 > C) A)+KOREKTNA VYSTUPNA FUKCIA  
 > ALGORITMUS 1  
 > vstup: x=sigma1sigma2..sigman, K=(y1,...,yk)  
 > vystup dvojice <i> i z <1>, j z <1>  
 > BEGIN  
 >  stav := 0  
 >  FOR i := 1 to n DO  
 >    while g(stav,sigmai)=otocene T DO f(stav, sigmai);  
 >    stav = g(stav,sigmai);  
 >    FOR y z out(stav) DO REPORT(i,y);  
 >  END;   LEMMA: ALG 1 pracuje s vynechanim REPORT v O(n).  
 > END.  
 > {velda ALGORITMU 1}  
 > ALG 2 ->  
 > ->zo vzorov vypracuje   
 > g(prechodovu funkciu),  
 > f(fail funkciu) a  
 > "polotovar" o, ktoru  
 > ALG 3 ->  
 > ->spracuje do funkcie  
 > out(vystupovej funkcie)

Pravdaze, roztiahol som to na celu A4, pricom tu schemu som nakresil uspornejsie, aby ten zamer roztiahnut text na celu A4 nebol okaty  :wink: .  
  
Oznamil som, ze by som to uz mohol mat a pan profesor si sadol ku stolu. Cital velmi rychlo, skoro ma to zdesilo. Ani neviem ako k tomu doslo, vysvetlil som mu, preco je v algoritme 1 while namiesto if. Opytal sa ma, ako by som reprezentoval vyhladavaci automat, trepol som, ze pole, potom som mu nakreslil strom pre vzory {AB,AC} a po kratkej spolupraci mi som sa poopravil na zoznam, na co mi pan profesor povedal, nech sa nebojim povedat strom. Ten som vylucil po tom, ked svoju otazku sformuloval s vyrazom: "Akou matematickou strukturou by ste reprezentovali vyhladavaci stroj?"  
  
Potom zakruzkoval l v O(l+n) a chcel to dokazat, na co som bol minutku dve ticho, potom som mu povedal, ze na to existuje netrivialny dokaz, na co zareagoval: "Stacila by vam trojka? Napisali ste toho dost." Snazil som sa brzdit prejavy nadsenia.  
  
O 9:58 som uz sedel dole v labe.  
  
Dufam, ze Vas tento prispevok povzbudil a ukazal, ze Kucera je dobrak a staci mu naozaj malo. Niekedy o tyzden chce za nim ist Viki, ads este nema a chce ist ku Kucerovi aj Gabo, Noro, Euzen, Marek Stalmasek... Tak sa drzte, vela zdaru!
<{/ForumPost}>

<{ForumPost(poster="univerz", timestamp=2007-05-01 14:51:53)}>
no to je pekne. ale aby ste sa ozvali na vyzvu koordinacie terminu, to nic. skuste dat dopredu vediet, kedy sa racite na skusku, ked sa to uz dohodne.
<{/ForumPost}>