Zk. 29. 05. 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ů.
jans

Zk. 29. 05. 2012

Příspěvek od jans »

Zdravím,

dnešní zadání zkoušky bylo takovéto:
Prolog 1: Definovat predikát, který obdrží ohodnocení výrokových proměnných, tj. asociativní seznam a vrátí všechna ohodnocení těchto proměnných, která se liší alespoň ve dvou hodnotách.
Nástin řešení: vytáhnout si z předaného ohodnocení názvy proměnných, vygenerovat si všechna možná ohodnocení a z nich vyházet ta, která se od zadaného ohodnocení buď neliší nebo se liší právě v hodnotě jedné proměnné.

Prolog 2: Na vstupu máme orientovaný graf bez smyček a multihran. Graf je zadán jako seznam ve tvaru vrchol-hrany, kde hrany je seznam sousedů vrcholu. Dále máme zadán seznam ekvivalentních vrcholů a máme provést kontrakci těchto vrcholů do jednoho, tj. hrana povede z tohoto vrcholu do nějakého vrcholu mimo tento seznam pouze pokud vedla alespoň z jednoho vrcholu v tomto seznamu a naopak. Je třeba dát pozor, aby nevznikly smyčky a multihrany, případně je poté odstranit.

Haskell 3: Máme zadaný datový typ (Bag a = Item a | Items [a]) a typ funkce fold, která má tuto strukturu procházet. Máme definovat tuto funkci a poté ještě funkci listy, která vrátí seznam všech položek v Item a v této datové struktuře.

Haskell 4: Dostaneme číslo n a máme vygenerovat nekonečný seznam posloupností délky n, které jsou uspořádány maximo-lexikograficky, někde to tu již na fóru je, nicméně přikládám řešení těchto posledních dvou příkladů.

Kód: Vybrat vše

-- Zkouskovy priklad cislo 3:
data Bag a = Item a | Items [Bag a]

-- a) Definovat funkci fold pro obecny pruchod datovou strukturou.
fold :: (a -> b) -> ([b] -> b) -> Bag a -> b
fold func listFunc (Item x) = func x
fold func listFunc (Items xs) = listFunc [fold func listFunc bag | bag <- xs]

-- b) Definovat funkci listy, ktera vrati seznam polozek s datovymi konstruktory Item.
listy :: Bag a -> [a]
listy bag = fold makeList joinLists bag

makeList :: a -> [a]
makeList x = [x]

joinLists :: [[a]] -> [a]
joinLists [] = []
joinLists (x:xs) = x ++ joinLists xs

-- > listy (Items [Item 1, Item 2, Items [Item 3, Item 4], Item 5])
-- [1,2,3,4,5]

-------------------------------------------------------------------

-- Zkouskovy priklad cislo 4 - vygenerovat nekonecny seznam posloupnosti
-- delky n usporadanych v maximolexikografickem usporadani.
gen :: Int -> [[Int]]
gen n = genWithMax n 1

genWithMax :: Int -> Int -> [[Int]]
genWithMax n max = [xs | xs <- var n max, max `elem` xs] ++ genWithMax n (max + 1)

var :: Int -> Int -> [[Int]]
var 0 _ = [[]]
var k n = [x:xs | x <- [1..n], xs <- var (k - 1) n]

-- > take 10 (gen 2)
-- [[1,1],[1,2],[2,1],[2,2],[1,3],[2,3],[3,1],[3,2],[3,3],[1,4]]
Uživatelský avatar
kolage
Matfyz(ák|ačka) level I
Příspěvky: 32
Registrován: 27. 1. 2011 18:10
Typ studia: Informatika Mgr.

Re: Zk. 29. 05. 2012

Příspěvek od kolage »

Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?
Shigi
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 29. 1. 2009 02:12
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Zk. 29. 05. 2012

Příspěvek od Shigi »

kolage píše:Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?
Budú aj veľké úlohy.

Viď http://ksvi.mff.cuni.cz/~dvorak/vyuka/NPRG005/
jans
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 31. 5. 2012 12:29
Typ studia: Informatika Bc.

Re: Zk. 29. 05. 2012

Příspěvek od jans »

kolage píše:Nevíte, jestli letos nebudou velké úlohy nebo je to jen výjimečnost 1. termínu?
Velká úloha byla samozřejmě i na prvním termínu, pouze jsem to sem zapomněl napsat - měli jsme najít ve slovníku se vzorky slov slovo, které nejvíce odpovídá zadanému vzorku. Vzdálenost slov se určovala pomocí metriky, kterou nám zadali, je to tu již někde popsáno v jiném vlákně.
Odpovědět

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