Matfyz Wiki
Prolog
To spamati asi nenapisem, napiste to niekto iny :/
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: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:
vypis (Num a, Ord a):: NTree a -> String
Priklad:
Strom: html
/ \
head body
/ \
a h2
Vypis: <html><head></head><body><a></a><h2></h2></body></html>
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:
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:
> 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.