# Zkouska 4.2.

<{ForumPost(poster="Control", timestamp=2008-02-04 20:31:20)}>
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

                  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]

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

    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!
<{/ForumPost}>