Zkouska 2009-05-25

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

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

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í.

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([], []).

Nevite nekdo, jak se dela ten prolog 2.b?

Nedelal jste nahodou nekdo Haskell prvni otazku - vypousteni z BVS? Neco je na socketce, ale je to nejake popletene...

Vyprosil jsem si na matousecovi original, tady je: 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)

Dekuji ti dobra vilo! Vidim, ze se na zkousku pripravujes pilne :)