Zkouska 2009-05-25

Přednáška je věnována neprocedurálnímu programování. Většina semestru je věnována programování v jazyku Prolog, ve kterém studenti i ladí zápočtové programy. Informativně se studenti seznámí i s jazykem LISP a neprocedurálními částmi programovacích systémů.
kukmuk
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

Příspěvek od kukmuk »

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
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zkouska 2009-05-25

Příspěvek od Him »

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
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 ;)
Martin T.

Re: Zkouska 2009-05-25

Příspěvek od Martin T. »

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

Re: Zkouska 2009-05-25

Příspěvek od Martin T. »

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([], []).
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zkouska 2009-05-25

Příspěvek od Him »

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 ;)
Návštěvník

Re: Zkouska 2009-05-25

Příspěvek od Návštěvník »

Nedelal jste nahodou nekdo Haskell prvni otazku - vypousteni z BVS? Neco je na socketce, ale je to nejake popletene...
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Zkouska 2009-05-25

Příspěvek od Him »

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 ;)
Návštěvník

Re: Zkouska 2009-05-25

Příspěvek od Návštěvník »

Dekuji ti dobra vilo! Vidim, ze se na zkousku pripravujes pilne :)
Odpovědět

Zpět na „PRG005 Neprocedurální programování“