Zkouska 2009-05-25
-
- Matfyz(ák|ačka) level I
- Příspěvky: 10
- Registrován: 2. 2. 2009 20:20
- Typ studia: Informatika Bc.
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
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
Re: Zkouska 2009-05-25
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
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
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zkouska 2009-05-25
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í.
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í.
Re: Zkouska 2009-05-25
Pro úplnost:
Kód: Vybrat vše
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 prvek
spoj(Z, O).
spoj([], []).
Re: Zkouska 2009-05-25
Nevite nekdo, jak se dela ten prolog 2.b?
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zkouska 2009-05-25
Nedelal jste nahodou nekdo Haskell prvni otazku - vypousteni z BVS? Neco je na socketce, ale je to nejake popletene...
Re: Zkouska 2009-05-25
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)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW
Re: Zkouska 2009-05-25
Dekuji ti dobra vilo! Vidim, ze se na zkousku pripravujes pilne