ZK 4.6.2009

PROLOG:

1. Máte k dispozici predikát modry/1, který uspěje, pokud argument je modry. Sestavte prodikát na5tiny(+Seznam,-Seznam5tin), který rozdělí efektivním způsobem vstupní seznam na 5 seznamů obsahujících přibližně stejně modrých prvků. Výstupní parametr Seznam5in obsahuje právě 5 prvků. Jsou to seznamy, jejichž zřetězením by vznikl seznam Seznam a počty modrých prvků v libovolných dvou prvcích seznamu Seznam5in se liší nejvýše o 1.
   Při konstrukci predikátu nesmíte používat žádnou aritmetiku (ani predikát length)

2. Sestavte proceduru-y, pro kódování a dekódování (dlouhého) seznamu pomocí šifry "Monte Christo".
   Text se zakóduje do čtvercové matice 4x4. Kódovacím klíčem je čtvercová mřížka stejných rozměrů s vhodně vyřezanými otvory. Text se vypisuje do otvorů ve mřížce postupně po řádcích, vždy do každého otvoru jedno písmeno. Pak se mřížka otočí o 90° doprava a další text es opět vypisuje do otvorů. Toto se opakuje celkem čtyřikrát. Po zaplnění celé matice se mřížka odstraní a obsah matice se vypíše po řádcích na výstup. Je-li šifrovaná zpráva delší než jeden čtverec (tj. delší než 4x4 písmen), rozdělí se na více úseků, každý o délce jednoho čtverce. Napište kódovací a dekódovací proceduru, musíte otestovat, zda je mřížka přípustná.

HASKELL
3) Definujte přirozenou reprezentaci binárního stromu, v jehož uzlech je uložena informace nějakého typu (podtřídy Eq). Každý stakový strom T určuje relaci mezi prvky onoho typu: A ~ B, jestliže ve stromě T existují uzly a(v němž je uložena informace A) a b (v němž je uložena informace B) takové, že uzel a leží ve stromě T nad uzlem b.
Sestavte funkci, která pro dva stromy rozohdne o tom, zda reprezentují stejnou relaci.
4) Definujte typ vhodný k reprezentaci multimnožiny desítkových cifer (každá z cifer se v ní může vyskytovat vícekrát). Uvažme čísla, která lze sestavit z cifer takové multimnožiny (nemusíme použít všechny). Naprogramujte dvě funkce:
a) první, která nalezne k číslu N a multimnožině M N-té takové číslo
b) druhou "inverzní", která k takovému číslu X spočítá jeho pořadové číslo

Na vypracování jako obvykle 3 hodiny času.

Průběh zkoušky:
Na ústní části byly projity všechny přáklady, u 1. příkladu jsem hloupě tvořil, kolik bude mít 5pite modrých prvků a zamotal jsem se do toho, díky tomu, že jsem si nenapsal hlavičky nedefinovaných predikátů. Druhý příklad je dobré si udělat všechny čtyři matice pro rychlé šifrování. Třetí příklad stačí dělat přes vygenerování všech relací a kontrole oproti stromu. V posledním příkladu je dobré hloupě negenerovat všechny možnosti ale přes faktoriály si spočítat kolik je jednociferných, dvouciferných, atd. ...
První příklad jsem neměl vůbec, 2. mi pouze šifroval, 3. byl OK a poslední byl hodně neefektivkní, dostal jsem za 3 bez otázek dalších. Co se jiných týče, bylo přede mnou asi 6 lidí a všem to dal, navíc jsem viděl, že to dal, ikdyž neměl třeba první 2 příklady.

Na ústní jsem šel jako první. Oba příklady z prologu jsem měl správně. Čtvrtý příklad jsem neměl vůbec. Třetí příklad jsem měl myšlenkově správně, syntakticky úplně špatně. Tak se mě zeptal ještě na datové typy v haskellu a nakonec mi dal dvojku s tím, že jsem tam měl dobré programátorské nápady, ale že jedničku mi dát nemůže.

BTW na zkoušku jsem se připravoval všecho všudy 10 minut.

Chci se zeptat, jak jste resili ten druhy, s tou mrizkou? porad nad tim premyslim a nemuzu prijit na zadne reseni, co je efektivni...

Efektivni reseni spociva v tom, ze si predpocitas 4 seznamy, kde seznam bude vypadat napr. [3,4,8,9], coz znamena, ze pro toto natoceni sifry pridej do vysledku 3. , 4. , 8. a 9. pismeno z 16-tice znaku. Takto se posle ten vstupnich 16 znaku na ty 4 seznamy a dostanes z toho zakodovanych 16 znaku. Ja jsem to osobne resil hloupe, ze jsem matici otacel a dival se na jaka mista je treba pridat, ale vzal mi to, az na to, ze jsem mel jenom kodovani, nikoliv dekodovani.

Díky, no já moc nevidím rozdíl v tom, jestli je tam seznam s čísly nebo ta matice, stejně se vždycky projde v jednom kroku ta celá 16tice právě jednou...

Ja jsem to resil tak, ze ten ctverec 4x4 je seznam o 16 prvcich obsahujici 1, pokud je na tom miste dira, 0 jinak. Pak jsem mel definovany predikat, ktery vezme tento seznam a otoci ho (slo jenom o zprehazeni 16 prvku seznamu). No a pak jsem 4x zopakoval nasledujici: vyber pismena, otoc. Kde "vyber pismena" dostavala dva seznamy, tabulku a 16 znaku vstupu. Procedura se podivala na hlavu v tabulce, pokud nasla jednicku, pridala hlavu ze vstupu do vystupu a zavolala sama sebe na zbytky obou seznamu, pokud nasla nulu, pak hlavu ze vstupu zahodila a zavolala sama sebe na zbytky obou seznamu.

Pozn.: Procedura "otoc" byla zapsana jedinym radkem. Prvni parametr byl zapsan jako seznam promennych X1 az X16. Druhy parametr byl zapsan jako seznam tech samych promennych, akorat prohazenych mezi sebou tak, aby to vyslo jako matice otocena doprava. Vysledne poradi se da jednoduse zjistit, kdyz si nakreslite obrazek.

Me by spis zajimal ten posledni priklad.

Jsou na zkoušce povolené nějaké materiály a jsou nějaká omezení na vestavěné predikáty/funkce?

Martin T. wrote:Jsou na zkoušce povolené nějaké materiály a jsou nějaká omezení na vestavěné predikáty/funkce?

Materialy povolene zadne nejsou, omezeni na vestavene predikaty a funkce neni snad zadne, ale asi by mel clovek vedet, jak by je programoval (Kryl se na tomuze pri ustni zeptat).

hm, tak jsem se teď pustil do toho posledního příkladu, i s GHCi před sebou mi trvalo docela dlouho, než jsem to vymyslel

na zkoušce jsem byl, dostal jsem za 4, ale naprosto oprávněně (ze 4 příkladů jsem měl dobře jeden)

nemám to hotové až úplně do konce, ale nejspíš by už to šlo rychle (ale už se mi to nechce dělat).

základní je rychle zjistit, kolik je N-tic, splňující ty kritéria. Kryl po zkoušce říkal něco o kombinačních číslech, ty se mi tam napasovat nepovedly - udělal jsem to poměrně hloupou rekurzí, ale šikovně ořezanou tak, že je velmi rychlá.

Pokud potřebujeme všechny n-tice, "stačí" vzít jednu z 10 číslic - na začítku ignorovat nulu - a spočítat počet (n-1)-tic, začínajících na to číslo, co se dá složit ze soustavy cifer, kde ta jedna cifra chybí. 0-tice je vždycky jedna, 1-tic je tolik, kolik je cifer s nenulovým množstvím. Nulu nesmíme vzít na začátku. (n-1)-tice spočítáme rekurzivně.

(Mimochodem, tady už vznikne funkce, kterou lze spočítat množství n-tic s libovolným začátkem - to se pak dá použít i k počítání pořadového čísla daného čísla.)

Tohle je samo o sobě funkční, ale dost neefektivní. První ořez, co se mi povedl, je ten, že pokud máme jenom cifry, co jsou tam buď 0-krát nebo naopak víc nebo stejně jak n-krát, stačí to spočítat jako p^n, kde p = počet cifer, kterých není nula. Nula jako cifra tady nevadí, ta je na úplném začátku začátku extra ošetřená, ale dál už je mi putna.

Další ořez je, že pokud je součet všech cifer menší než n, tak už to dá automaticky počet 0.

Co to ale hlavně zrychlí vyplyne z pozorování, že když máme třeba tři dvojky, pětky a jedničky, je jedno, jestli drapnu tu dvojku, pětku nebo jedničku a začnu počítat (n-1)tice se "systémem", kde je třeba dvojek o jedna méně, protože počet (n-1)-tic, začínající na ty další dvě, je úplně stejný. Pokud tedy máme nějakých cifer stejný počet, stačí rekurzivně spočítat (n-1)tice jednu a vynásobit to počtem cifer, co je jich tam stejně. Počet "větší nebo rovno než n" je vlastně pro naše účely taky rovný (pokud je cifry >=n, tak po sebrání jedné takové cifry je jich zase >= n-1).

Tahle poslední věc, spolu s tou první (p^n) mi tu rekurzi zrychlila strašně. Nevymyslel jsem, jak to ještě zrychlit, a ani jsem nepřišel na žádný "jiný pohled" na to, jak to řešit (jinak, než přes tuhle rekurzi přes délku počítaných n-tic).

Zbytek by měl jít už tak nějak sám (jenom už mě ten haskell vytáčí) - máme fci, co spočítá počet n-tic pro všechna n a k tomu "mimochodem" i počet n-tic s nějakým pevným začátkem.

Upřímně řečeno, psal jsem to docela dlouho (v řádu hodin) a nechápu, jak mám něco podobnýho vymyslet na tý zkoušce. Ale to je jedno.

V ramci pripravy jsem si vyzkousel kodovani Monte Cristo ve zjednodusene verzi napsat - predpoklada vstup Text o delce 16, nejake rozdelovani delsiho textu neresim.

zasifruj(Text, Klic1, Sifra):-
  len(Text, Len), Len=16,
  take4(Text,T1, Zb1), works(T1,Klic1, Sifra),
  otoc(Klic1, Klic2), take4(Zb1,T2, Zb2), works(T2, Klic2, Sifra),
  otoc(Klic2, Klic3), take4(Zb2,T3, Zb3), works(T3, Klic3, Sifra),
  otoc(Klic3, Klic4), works(Zb3, Klic4, Sifra).
  
works([],_,_).
works([HP|TP], [HK|TK], [HS|TS]):-
  HK=1,!,HP=HS,works(TP, TK, TS);
  works([HP|TP], TK, TS).
  
otoc([A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16],[A13,A9,A5,A1,A14,A10,A6,A2,A15,A11,A7,A3,A16,A12,A8,A4]).

zkontroluj(Klic1):-
  otoc(Klic1, Klic2), otoc(Klic2, Klic3), otoc(Klic3, Klic4),
  zkontroluj(Klic1, Klic2, Klic3, Klic4).

zkontroluj([],[],[],[]).
zkontroluj([H1|T1], [H2|T2], [H3|T3], [H4|T4]):-
  (H1=:=1,H2=:=0,H3=:=0,H4=:=0;
  H1=:=0,H2=:=1,H3=:=0,H4=:=0;
  H1=:=0,H2=:=0,H3=:=1,H4=:=0;
  H1=:=0,H2=:=0,H3=:=0,H4=:=1),
  zkontroluj(T1,T2,T3,T4).
  
take4(Text,Ctyri,Zbytek):-
  takeN(4, Text, Ctyri, Zbytek).
  
takeN(0, L, [], L).
takeN(_, [], [],[]).
takeN(N, [H|L], [H|Zb], Rest):- 
  N > 0, N1 is N -1,
  takeN(N1, L, Zb, Rest).
                                      
len([],0).
len([H|T], N):-
  len(T,N1), N is N1+1.

Predikat zasifruj funguje oboustranne - tedy koduje i dekoduje (kvuli dekodovani je tam podminka na delku 16). Snad to tedy odpovida, kdyztak komentujte. Hodne veci je tam tedy napevno (otaceni atd.), ale kdyz uz bylo takove zadani...

Jinak pokud vam SWI-Prolog zkracuje dlouhe seznamy, zadejte:

set_prolog_flag(toplevel_print_options, [quoted(true), portray(true), max_depth(0), attributes(portray)]).