Matfyz Wiki

Zkouska 4.2.

Control at 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)

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

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

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

  1. Teorie: vysvetlete deklarativni a proceduralni vyznam programu.

  2. 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!