Zkouska 101 u prof. Kuceru - 24.04.2007
Napsal: 24. 4. 2007 10:44
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
Na jednu A4 som napisala toto: .
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!
.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
Na jednu A4 som napisala toto:
Pravdaze, roztiahol som to na celu A4, pricom tu schemu som nakresil uspornejsie, aby ten zamer roztiahnut text na celu A4 nebol okatyNajefektivnejsia 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)
.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!