Zkouska 4.2.

Control · Příspěvek od **Control** » 4. 2. 2008 20:31

Zdarec! Toz dneska to byla vcelku řezanice - z puvodne plneho terminu pro 20 lidi prislo na zkousku lidi 10.

Zadani:
1) Prolog:
Ukolem bylo zrekonstruovat n-arni strom ze seznamu tvaru VrcholPocetSynu. Pricemz listy mely pocet synu 0.
Tedy seznamu: A3 B2 C0 D0 E0 F1 G0 odpovidal stromu

Kód: Vybrat vše

              A
       /     |     \
     B       E        F 
   /  \              /
 C     D           G

A tomu vsemu muze odpovidat Prologovsky zapis napr.: t(A, [ t(B , [ t(C) , t(D) ]) , t(E), t( F, t(G) ) ] ale mohli jste zvolit lib. jiny. Bylo take mozne vyslovit si dodatecne predpoklady napr. ze v uvodnim seznamu nejsou hodnoty nalepene na sobe, ale jsou to dvojice A-3, B-2, C-0... nebo ze seznam vrcholu nejak zacina, nejak konci. (nicmene zadano to bylo, jak pisu)

2) Prolog:
Je dan acyklicky orientovany graf. Vasim ukolem je ho projit DO HLOUBKY a do kazdeho vrcholu strcit "cas" jeho PRVNIHO navstiveni a "cas jeho POSLEDNIHO opusteni.

Vse vysvetli obrazek [vlevo od hodnoty uzlu je cas prvni navstevy, vpravo cas posledniho odchodu]

Kód: Vybrat vše

              1A14
       /     |     \
    2B7   8E9   10F13 
   /  \              /
 3C4     5D6 11G12

opravte me nekdo, pokud to nerikam dobre.
Opet podotykam. Graf je reprezentovan jak je studentovi libo. Taktez mozno vyslovit predpoklad existence rozumnych predikatu hrana(A,B)... apod. A bacha orientovany acyklicky graf NENI OBECNE STROM [ list muze byt potomkem vice rodicu, diky orientaci hran - napr. graf slunicko (jeden vrchol do ktereho miri spousta paprsku) ] a take NEMUSI BYT SOUVISLY.

3) Haskell
Dan orientovany graf (obecne i nesouvisly )
Rozdelte vrcholy grafu do mnozin takovym zpusobem, aby hrany z vrcholu v jedne mnozine vedly pouze do vrcholu v mnozine s nizsim cislem. Navic plati, ze vrcholy jsou v mnozine s nejnizsim moznym cislem [tj. nestaci topologicke serazeni].

4) Haskell
Na vstupu dostanene seznam.
Vyberte z neho souvislou cast, tu otocte, prvkum v ni zmente znamenko a strcte zpatky na misto.
Vystupem ma byt seznam vsech takovych seznamu. Tj. vsemi zpusoby vybrat souvislou cast, kterou otocite a vynasobite *(-1).

Kód: Vybrat vše

Aby nedoslo k nedorozumeni:
1 - seznam
2 - vyberu z nej souvislou oblast
3 tu otocim, vynasobim -1 a vratim zpet do puvodniho: [zmenena cast reprezentovana X-kama]

1] _________________________________
2] _____________a______________b____
3] _____________aXXXXXXXXXXXXXXb____

Volbu a,b provedu vsemi zpusoby.

5) Teorie: vysvetlete deklarativni a proceduralni vyznam programu.

6) Velky priklad - rozvrhovani instrukci pro procesor. [vzhledem k tomu, ze pote, co p.Hric napsal 2slova ze zadani se nekteri zacali chytat za hlavu, asi je to "stary znamy". Jinak zadani na 3dlouhe odstavce]

Dalo se v tom uvidet, ze jde [jak byva na neprocku zvykem] ze jde o NP uplny problem [nebo prinejmensim stejne tezky podproblem - hledani minimalni hamiltonovske kruznice ]- tj. maji smysl 2 pristupy, vybruteforcovat vsechny permutace a z nich vybrat tu nejhezci [nehledime na cas ani efektivitu]. [v pohode uznavano]

Anebo se snazit hledat nejake heuristiky pro vyse uvedeny postup a smirit se s tim, ze v nejakem pripade budou proste stejne nejfan jako bruteforce. [v pohode uznavane reseni]

Mluvil jsem asi s 5 lidmi a vsichni tito dali jen 2 (nektere) priklady - nejcasteji 1. a 4. [podle velkeho prikladu odchazeli bud s 2 nebo 3].
Zaludny pohled p. Hricovi pres rameno pri zapisovani znamek odhalil 2ctyrky, asi 4-5 trojek a zbytek dvojky,jednicky.
Za kazdy priklad bylo 5 bodu a reknu Vam, tech 5 za teorii tentokrat fakt bodlo...

Good luck vsem!