Zkouška 26.6.2014 (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ů.
Twister

Zkouška 26.6.2014 (Dvořák + Hric)

Příspěvek od Twister »

Prolog
1. To spamati asi nenapisem, napiste to niekto iny :/

2. Mame dany nedokonaly BVS, mame vypisat dvojice vrcholov, ktore porusuju podmienky BVS. Kazdy vrchol a list ma nejaku hodnotu, co je unikatne cele cislo. Uz to tu par krat bolo.
Datova struktura:

Kód: Vybrat vše

data BVS a = N nil | NT (BVS a) a (BVS a)
(alebo nieco podobne)

Haskell
3. HTML serializer. Mame dany obecny strom, ktory ma vo vrcholoch a listoch nazvy HTML tagov, napr. "html", "body", "a", atd. Cielom bolo:
a) napisat typ konstruktoru tej datovej struktury
b) vypisat tagy do stringu podla DFS priechodu stromom zlava - teda vlastne tak, aby to bolo validne HTML.
Signatura:

Kód: Vybrat vše

 vypis (Num a, Ord a):: NTree a -> String
Priklad:

Kód: Vybrat vše

Strom:         html
              /    \
            head   body
                  /    \
                 a     h2

Vypis: <html><head></head><body><a></a><h2></h2></body></html>


4. Mame body v niekolkodimenzionalnom priestore. Vzdialenost medzi bodmi je urcena pomcou Manhattanskej metriky. Funkcia dostane zadanu dvojicu bodov (prihradok), a zoznam dalsich bodov. Singatura funkcie bola:

Kód: Vybrat vše

zarad :: (Num a, Ord a) => ([a], [a]) -> [[a]] -> ([[a]], [[a]])
Kazdy bod zo zoznamu bolo treba zaradit do tej blizsej z tych 2 prihradok, teda do tej, ktora je blizsie podla Manhattanskej metriky.
Napriklad:

Kód: Vybrat vše

> zarad ([0,0] [5,5]) [[1,2], [6,4], [0,-1]]
([[0,0], [1,2], [0,-1]], [[5,5], [6,4]])
Big One
Je dany pocet strojov n, a zoznam vyrobkov (kazdy vyrobok ma dane cislo, dobu kolko trva jeho vyrobenie, cas odkedy je mozne ho vyrobit, a cas dokedy musi jeho vyroba skoncit). Mozeme predpokladat, ze doba vyrobenia sa vojde do tohoto intervalu od-do (teda kazdy vyrobok je vyrobitelny). Stroje su navzajom zamenitelne, vyrobky tiez. Kazdy stroj moze samozrejme naraz vyrabat len jeden vyrobok.

Ulohou bolo vratit rozvrh vyroby (teda zoznam zaznamov typu [cislo vyrobku, cas zacatia vyroby, cislo stroja]), tak aby sa maximalizoval pocet vyrobenych vyrobkov. Nemusia sa dat vyrobit vsetky. Malo sa to riesit s heuristikou. Dvorak nam poradil, aby sme to pisali zhora, teda pomocne funkcie az nakoniec, pre pripad, ze by sme to nestihli.

Uloha bola velmi necakane NP uplna :)

Podla mna bol na to ovela lepsi Prolog, ale viem, ze to par ludi robilo aj v Haskelli.

Ja som to robila tak, ze som sa najprv pokusila najst rozvrh, ktory vyrobi vsetky vyrobky (teda m vyrobkov), ak sa to nepodari, skusi vyrobit m-1... atd., az po skusi vyrobit jeden vyrobok. Ak sa mu nepodari ani jeden, zlyha.
Rozvrh som sa snazila vyrobit pomocou predikatov between a kontrolovania podmienok.
Bolo treba splnit podmienky:
- jeden stroj nikdy nevyraba viac veci naraz
- vyroba kazdeho vyrobku prebieha v jeho povolenom intervale

Este neviem, ci moje riesenie bolo aj spravne, na ustnu cast idem az zajtra. Ale prislo mi to ako jedna z lahsich uloh.
jira
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 29. 6. 2011 10:43
Typ studia: Informatika Bc.

Re: Zkouška 26.6.2014 (Dvořák + Hric)

Příspěvek od jira »

Twister píše:Prolog
1. To spamati asi nenapisem, napiste to niekto iny :/
Byl dán seznam objektů, kde každý objekt obsahuje dvojice klíč-hodnota. Úkolem bylo pro každý klíč vypsat jakých hodnot nabývá.
Pokud nějaký objekt klíč neobsahuje, tak je hodnota undefined. Objekty jsou prostě seznamy.

Kód: Vybrat vše

[
 [ jmeno-"xy", vek-30, vaha-90],
 [ jmeno-"xyz", vek-35, vaha-80]
 [ jmeno-"ab",  vaha-80]
]

[ jmeno-["xy", "xyz", "ab"], vek-[30, 35, undefined], vaha-[90, 80, 80]]

Ten velký příklad, jsem dělal tak, že jsem přednostně plánoval úlohy s nejkratší dobou zhotovení a vždy když byl nějaký výrobek hotov, tak jsem naplánoval další.
Bylo mi řečeno, že heuristika je trochu moc jednoduchá a dostal jsem za dvě.
Odpovědět

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