Zkouska 18.06.2012

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ů.
eldros

Zkouska 18.06.2012

Příspěvek od eldros »

Prolog:
1) Mate dva seznamy a v kazdem maximalne 1 hvezdicku. Ukolem je zjistit zda jsou seznamy ekvivalentni. Hacek je v tom, ze hvezdicku lze nahradit za libovolnou posloupnost cisel.
[1,2,*,7,5] a [1,2,*,7,7,5] jsou ekvivalentni

2) Mate seznam prvku [X->Y] napr [a->b,a->c,e->f] pricemz toto dava nejake nelinearni usporadani. Mate najit vsechny neporovnatelne dvojice. V predchozim prikladu je to napr [a-e,a-f,b-c,b-e,b-f] idea je snad jasna, pozor na pohlidani tranzitivity.

Haskell:
3)Multimnožina (prvky se mohou opakovat) je definována
type Multim = [(Int,a)]

například [(2,'c'),(1,'d')] odpovídá množině ['c','c','d']
Řekneme, že M1<M2, pokud v M2 existuje prvek, který není v M1 a je větší než všechny prvky v M1, které nejsou v M2 (pismena josu klasicky usporadana a<b<...). Naším úkolem bylo definovat funkci (<).

4) Prevest obecny strom na binarni.

Velka uloha:
Mate reklamni bloky b1,..,bn a kazdy ma urcitou delku. Dale mame nejake zakazniky z1,...,zm a ti maji nejake nabidky. Nabizeji napr ze by chteli blok b7 a z neho by chteli 3 minuty a jsou ochotni zaplatit 200 000 Kc. Zaroven kazdy zakaznik ma omezeny kapital a nechce ho prekrocit (ale muze chtit napr reklamy za 2 000 000 Kc pricemz ma jen 700 000 Kc, to je na nas nabidnout mu bloky abychom neprekrocili jeho kapital). Ukolem je vytvorit pro dane bloky jake zakazniky chceme v blocich obsluhovat, pricemz musime vyhovet podminkam (neprekrocit kapital, logicky nenaplanovat 12 min na 10 min blok).
Prijatelne reseni je bud nejaka heuristika (nemusi byt chytra, staci hladove obsazovat intervaly) nebo presne reseni (tadyu asi mysli generovani vsech permutaci). Hodnoti se zda dokazeme napsat vetsi program v Haskellu/Prologu nez zda umime algoritmy.
Premun
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 6. 6. 2011 22:52
Typ studia: Informatika Mgr.

Re: Zkouska 18.06.2012

Příspěvek od Premun »

Malá poznámka: asi záleží na zkoušejícím (já byl u Hrice), ale velkou úlohu jsem měl stylem vygenerování všech možností a výběr optimální (jak jsi psal ty permutace, ikdyž to přesně permutace nejsou). Měl jsem ji dodělanou až do konce a vlastně bez chyb (tzn. větší ucelené řešení, ale bez složitějšího algoritmu) a on mi za to stejně snížil známku o stupeň.

Takže to asi nechce udělat úplně hloupě, ale Dvořák si na zkoušce docela protiřečil. Nejdřív řekl, že chce neprimitvní heuristiku a za 2 minuty říkal, že zkouší ze schopnosti napsat něco v těch jazycích a ne z algoritmů. Tak nevim, jestli dělat algoritmus a heuristiku nebo jazyk, prostě jsem to úplně nepochopil... Zkouškou jsem prošel, tak si nestěžuju, jen upozorňuju.

Ponaučení: prostě to udělejte co nejlíp a spíš to řešení dokončete než mít napůl hotovej ultra-algoritmus. Nebo to aspon byl můj pocit.
fishead1

Re: Zkouska 18.06.2012

Příspěvek od fishead1 »

len by som chcel poopravit dvojku. spravny vysledok pre zadany vstup je [a-e, c-e, b-e, a-f, c-f, b-f, b-c]
Odpovědět

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