19.06.2015 - Dvořák, Hric

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ů.
Katami
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Ph.D.

19.06.2015 - Dvořák, Hric

Příspěvek od Katami »

Malé příklady (80min, potřeba alespoň 4b z prologu, alespoň 4b z haskellu, dohromady alespoň 12b)
  1. (Prolog, 5b) Napište predikát splay(+Hodnota, +Strom, -Vystup) provede operaci splay nad binárním vyhledávacím stromem Strom, která pomocí rotací přesune uzel s hodnotou Hodnota (pokud ve stromu není tak jejího přímého předchůdce či následníka) do kořene stromu a vrátí nový strom ve Vystup.
  2. (Prolog, 5b) Napište predikát zlepsirez(+Graf, +Vrcholy1, +Vrcholy2, -OutV), který pro zadaný ohodnocený neorientovaný graf Graf a řez (definovaný pomocí dvou disjunktních množin vrcholů Vrcholy1 a Vrcholy2) najde vrchol, který když přesuneme do opačné skupiny vrcholů řezu, tak dostaneme řez s lepší cenou. Graf byl zadaný šikovně a bylo možné si ho případně upravit aby vyhovoval více.
  3. (Haskell, 5b) Máme zadanou matici (jako list listů), napište funkci, která pro danou matici vrátí všechny dvojice indexů (x,y) takových, že podmatice (1,1) (x,y) je kladná (každý prvek je kladný) a zároveň x i y je největší možné. Výstupem mají být všechny takovéto dvojce

    \begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & -8 & 9\end{pmatrix}

    První řádek (chápáno jako matice) nesplňuje zadání, protože rozšířením na první dva řádky dostaneme větší matici, která je pořád kladná. Naopak první sloupec jej splňuje, protože y-ově rozšířit nejde (OutOfBoundsException) a x-ově taky ne, protože (kvůli -8) by nebyla matice kladná. [(1,3), (3,2)] je řešení v tomto případě.
  4. (Haskell, 5b) Je dán strom (ne nutně binární) a máme očíslovat jeho vrcholy v pre-order pořadí (viz. prologovský příklad z kázkové písemky na webu předmětu), Strom je data NT a = N a [NT a]
Velký příklad (90min, jazyk si volíte sami)
Máte orientovaný graf a ke každé hraně máte seznam dvojic reálních čísel. Cílem je nějak ohodnotit vrcholy libovolnými čísly a hrany jednou dvojící ze seznamu tak, aby odchylka byla co nejmenší. Odchylka je součet odchylek všech hran. Odchylka hrany s hodnotou počátečního vrcholu v_1, hodnotou koncového vrcholu v_2 a ohodnocením hrany (e_1, e_2) je |v_1 - e_1| + |v_2 - e_2|. Máte zvolit vhodnou heuristiku.


U všech příkladů můžete počítat s tím, že vstup je zadaný korektně.
Odpovědět

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