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)
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
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]])
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]])
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.