Skuska 8.2.2008

[Návštěvník]

Tuna je moja interpretacia zadani Hricovej pisomky.

1. Prolog: Je dany zoznam bodov v n-rozmernom priestore. Najdite najmensi kvader ktory tieto body obsahuje.

2. Prolog: Je dany orientovany acyklicky graf. Vytvorte jeho tranzitivny uzaver. (Tranzitivní uzávěr orientovaného grafu je orientovaný graf s původními vrcholy a platí, že existuje hrana z uzlu u do uzlu v právě tehdy, když v původním orientovaném grafu existuje libovolná orientovaná cesta z uzlu u do uzlu v)

3. Haskell: Je dany zoznam hodnot a zoznam tzv. "fitness" funkcii. (Kazda z tychto funkcii je aplikovatelna na typ prvku zoznamu a vracia nejake ohodnotenie tohto prvku). Teda aplikovanim zoznamu funkcii na prvok zoznamu dostaneme vektor. Vyberte z povodneho zoznamu tie prvky ktorych "fitness vektory" nie su dominovane "fitness vektormy" ostatnych prvkov zoznamu.

4. Haskell: Ty Vole, uz si nemozem spomenut, snad ma niekto menej skleroticky doplni...

5. Vysvetlite klucove slova type, data, newtype. Vysvetlite datove a typove konstruktory a ich typy.

A nasleduje hyper:-) priklad

Na vstupe je dany hypergraf a ku kazdemu jeho vrcholu je dany zoznam dovolenych farieb pre tento vrchol. Dalej je na vstupe zadany maximalny pocet farieb ktore mozme pouzit.
Ulohou bolo najst vsetky korektne ciastocne maximalne ofarbenia grafu.Pricom korektne znamena ze nemozu byt 2 vrcholy vedla seba s rovnakou farbou. A ciastocne znamena ze sme obmedzeny poctom farieb ktore mozme pouzit a zvysok grafu potom nechame neofarbeny. Maximalne znamena ze pri danom pocte povolenych farieb uz toto ofarbenie nemozeme zvacit pridanim dalsieho vrcholu. (Hypergraf je graf ktoreho hrany mozu spajat 2 a viac vrcholov)

A este si dovolim napisat malu poznamku k hodnoteniu. Velky priklad som riesil tak ze som k vstupnemu grafu hladal ofarbenie prehladavanim do hlbky. Vsetky ofarbenia som potom pozbieral pomocou setof. K tomu mal Hric poznamku ze to je mierne neefektivne. Vo velkom priklade som nemal doriesene situacie ked som nejakemu vrcholu zamerne vybral farbu ze je neofarbeny. V malych prikladoch som mal asi v kazdom priklade nieco vytknute (v 2 prikladoch neefektivita a v oboch haskellovskych sa mi niekde primiesala typova nekompatibilita) Vysledok 2

[Santhos]

zajimalo by me jak si treba resil tu 1), ted jsem to resil a neprijde mi to tezky ale je to voser a na asi 20 radku

[Black_Hand]

me treba napada v kazdy jedny slozce najit nejmensi a nejmensi velikost a prohlasit ji za souradnici v dane jedne dimenzi za vrchol toho kvadru. a pak to nakombinovat

Kód: Vybrat vše

%najdi_kvadr(+B, -Kvadr)
najdi_kvadr(B, Kvadr) :- najdi_kvadr_int(B, [Start|TKvadr]), najdi_kombinace(Start, TKvadr, Kvadr).

%najdi_kvadr_int(+B, -Kvadr) - B je seznam vrcholu
najdi_kvadr_int(B, [(Min, Max)|Kvadr]) :- vyber_prvni_souradnice(B, [X|Sour], OB), najdi_min_max(Sour, X, X, Min, Max), najdi_kvadr_int(OB, Kvadr).
najdi_kvadr_int(B, []) :- forall(member(X, B), X = []). %fikane selze pri spatnym zadani

%vyber_prvni_souradnice(+B, -Sour, -OB) - OB je oklestene B o prvni sour - slo by to i findallem, ale todle je prehlednejsi
vyber_prvni_souradnice([ [X|Zbytek] | B ], [X|Sour], [Zbytek|OB]) :- vyber_prvni_souradnice(B, Sour, OB).
vyber_prvni_souradnice([], [], []).

%najdi_min_max(+B, +IMin, +IMax, -Min, -Max)
najdi_min_max([X|B], IMin, IMax, Min, Max) :- najdi_min_max(B, IMin, IMax, NMin, NMax), Min is min(X, NMin), Max is max(X, NMax).
najdi_min_max([], Min, Max, Min, Max).

%najdi_kombinace(+DimInt, +TKvadr, -Kvadr)
najdi_kombinace((Min, Max), TKvadr, Kvadr) :- findall(Komb1, kombinuj(Min, TKvadr, Komb1), Kombs1),
                      findall(Komb2, kombinuj(Max, TKvadr, Komb2), Kombs2),
                      append(Kombs1, Kombs2, Kvadr).
%kombinuj(+Val, +Pairs, -Nudle)
kombinuj(Val, [(Min, Max) | Pairs], [Val|Nudle]) :- kombinuj(Min, Pairs, Nudle) ; %pozor, protoze findall tak se probacktrackuje pres obe moznosti
              kombinuj(Max, Pairs, Nudle).
kombinuj(Val, [], [Val]).

%test: najdi_kvadr([ [1,1,1], [2,2,2], [-1, -1, -1], [ 5, -5, 5 ]], Kvadr).
%Kvadr = [ [-1, -5, -1],  [-1, -5, 5],  [-1, 2, -1],  [-1, 2, 5],  [5, -5, -1],  [5, -5, 5],  [5, 2, -1],  [5, 2, 5] ]
%odpovida pravde :))

[Yawgmoth]

předpokládám, že to takhle bylo myšlené, ale čistě teoreticky tímhle způsobem zrovna nejmenší kvádr nenajdeš - nikde se neřeklo, že musí mít hrany rovnoběžné s osami, například v uvedeném vzorovém seznamu bodů máš 3 na přímce -> lze udělat "velmi tenký" kvádřík mezi nimi a posledním bodem mimo a jsou i hezčí příklady kde by ti podobným natočením mohla vzniknout třeba i pěkná krychle podstatně menších rozměrů

[Black_Hand]

ja cekal jestli si toho nekdo vsimne ). ale todle by byla asi prvni vec na kterou bych se ohledne zadani zeptal

[Santhos]

no ja sem to delal stejne jako black_hand, ale prislo mi to dost jako zrout casu na to ze to byl malej priklad...