# Zkouska 2009-05-25

<{ForumPost(poster="kukmuk", timestamp=2009-05-26 13:12:24)}>
Tak na zkousce  
**Prolog**  
1. Prevest permutaci zadanou ve tvaru "v(7,\[4,3,5,6,2,7,1])" (tedy prvni cifra udava rozsah hodnot v permutaci, zde od 1 do 7, pak nasleduje seznam, kde prvek na pozici *i* se zobrazi na cislo na te pozici) do zapisu ve tvaru cyklu "c(7,\[\[1,4,6,7],\[2,3,4]])" , tedy nepsat jednoprvkove cykly.  
  
2. Vytvorit predikat, ktery   
    a) prijme 2 permutace v zapisu cyklu a vrati jejich soucin (tedy slozeni permutaci)  
    b) prijme permutaci a vrati jeji druhou mocninu (slozeni 2 stejnych permutaci, zde se melo postupovat pres NSN/LCM delek cyklu)  
  
**Haskell**  
1. Reprezentovat BVS a pak funkci na vypousteni vsech vrcholu s hodnotou mezi Min a Max  
2. Soucin a podil dlouhych cisel - dlouhe cislo je trojice Znamenko, \[Int], Pozice desetinne carky od prvni cifry
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-06-12 13:13:22)}>
Umite nekdo ten Prolog 1) rychleji nez v O(n^2)?   
Já si to zkoušel a myšlenka sice jednoduchá, nicméně je to hrozně dlouhé ... [http://martinvseticka.eu/index.php?sekc ... e&page=204](http://martinvseticka.eu/index.php?sekce=browse&page=204)
<{/ForumPost}>

<{ForumPost(poster="Martin T.", timestamp=2009-06-12 19:43:57)}>
V prologu ne :)  
  
Když jsem si to zkoušel já, tak jsem udělal řešení O(n^2), hodně podobné tvému (netřídil jsem, ale přes member vyhledával padnoucí díl). Pokud používáš model:  
Ohodnoť = O(n) - přidání pozice pro každý prvek  
Setřiď  
Spoj = O(n) - vytvoření cyklů  
  
Tak všechno záleží na třídícím algoritmu. Na tento typ úlohy by šlo použít přihrádkové třídění (O(n)), avšak v prologu bych ho asi nedokázal udělat (protože přístup k prvku "pole" není konstantní). A po pravdě nevidím moc slibně ani prznění algoritmů jako quicksort, jelikož prvek nemá hodnotu jednu, ale dvě (jednu zleva, druhou zprava). Takže byť použiješ nějaké třídění, podle mě to nebude o moc efektivnější než kombinace last (na co chci napojovat), member (co budu napojovat), append (napoj), remove (odstraň napojený). Dá se optimalizovat, last si mohu pamatovat (změním strukturu "párů"), member a remove mohu spojit do jednoho průchodu a append mohu dělat přes rozdílové seznamy. I tak to bude O(n^2). Možná se tu ale někdo najde, kdo má (pravděpodobně naprosto rozdílný) postup s lepší asymptotickou složitostí.
<{/ForumPost}>

<{ForumPost(poster="Martin T.", timestamp=2009-06-12 20:01:53)}>
Pro úplnost:  

    preved(v(L, P), c(L, CP)) :-ohodnot(1, P, O),spoj(O, CP),!.
    
    ohodnot(X, [X|T], Z) :-L1 is X + 1,ohodnot(L1, T, Z).
    ohodnot(L, [H|T], [[L,H]|Z]) :-L1 is L + 1,ohodnot(L1, T, Z).
    ohodnot(_, [], []).
    
    spoj([H|Z], O) :-last(H, Last),member([Last|X], Z),append(H,X,V),delete(Z, [Last|X], Z1),spoj([V|Z1], O).
    spoj([H|Z], [X|O]) :-append(X, [_], H), % odstrani posledni prvekspoj(Z, O).
    spoj([], []).
    


<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-06-17 11:27:10)}>
Nevite nekdo, jak se dela ten prolog 2.b?
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-06-17 17:59:57)}>
Nedelal jste nahodou nekdo Haskell prvni otazku - vypousteni z BVS? Neco je na socketce, ale je to nejake popletene...
<{/ForumPost}>

<{ForumPost(poster="Him", timestamp=2009-06-17 18:04:25)}>
Vyprosil jsem si na matousecovi original, tady je: [http://martinvseticka.eu/temp/male-ulohy-haskell.txt](http://martinvseticka.eu/temp/male-ulohy-haskell.txt) -- tady je to spravne (na s0cketce je to taky dobre, jen se nektere casti ztratily do html tagu a nejsou videt)
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-06-17 18:07:40)}>
Dekuji ti dobra vilo! Vidim, ze se na zkousku pripravujes pilne :)
<{/ForumPost}>