termín v letním semetruhttp://s0cketka.php5.cz/skola/prolog.php – řešené malé úlohy ze zkoušky z Prologu
http://s0cketka.php5.cz/skola/haskell.php – řešené malé úlohy ze zkoušky z Haskellu
http://mff.modry.cz/programko/index.html – řešený mix ze zkoušky
http://forum.matfyz.info/viewtopic.php?f=364&t=1486 – řešený mix ze zkoušky 2005
http://forum.matfyz.info/viewtopic.php?f=169&t=4049
Prolog 1: Máme zadán acyklický orientovaný graf a na vstupu dva vrcholy U a V. Najděte nejbližšího předka obou vrcholů. Tj. takový vrchol P, že je předkem vrcholů U i V (tzn. existuje z něj orientovaná cesta do U i V) a součet délek těchto cest je minimální možný. Reprezentaci grafu na vstupu si můžete libovolně upravit tak, jak se vám to hodí.
Prolog 2: Je dána matice A. Najděte souřadnice sedlového bodu matice A, pokud takový bod existuje. Sedlový bod je takový prvek SB matice A, pro který platí, že SB = min_i (max_j A(i,j) ) = max_j (min_i A(i,j) )
Haskell 1: Máme binární strom bez hodnot v uzlech stromu. Hodnoty jsou pouze v listech. Převeďte takový strom na binární strom s hodnotami i v uzlech. Přičemž hodnota v uzlu bude definována jako minimum z hodnot v podstromech tohoto uzlu. Nadefinujte si i vlastní reprezentace obou stromů a před každou vaši funkci připište deklarace typů.
Haskell 2: Orientovaný graf je zadán jako seznam vrcholů se seznamy sousedů, tj. např [(v,[u,w]),(w,[v]),(u,[w])]. Přičemž pořadí sousedů v seznamech sousedů i pořadí vrcholů v seznamu může být pro stejný graf různé. Vytvořte funkci, která pro dva takto reprezentované grafy zjistí, zda se jedná o ten samý graf. Pozor! Nejedná se o izomorfismus grafů, ale skutečně o identitu – tj. vrcholy se musí i stejně jmenovat. Opět uveďte typové deklarace funkcí a použité datové typy.
Teorie: Negace v Prologu (alias neúspěch). Vysvětlete, jak je definována a popište vlastnosti a nevýhody této definice.
Velký příklad – plánování procesoru Máme dán seznam instrukcí. Dále máme zadány závislosti mezi instrukcemi, a to takto: dvě instrukce na sobě buď nezávisejí, a potom mohou proběhnout v libovolném pořadí a nebo I2 závisí na I1 (případně vice versa) a R_(I1,I2) je nějaké celé číslo. To potom znamená, že I2 může být vykonána až po I1, a to nejdříve za R_(I1,I2) taktů procesoru. Dále platí, že v jednom taktu může začít pouze jedna instrukce. Jinak máme v podstatě ideální paralelismus, tj. na délku provádění instrukcí nehledíme, klidně může v 10 taktech za sebou začít deset rozdílných instrukcí (samozřejmě, pokud to dovolí závislosti). Úkolem je nalézt optimální rozvržení instrukcí vzhledem k počtu taktů, tj. takové rozvržení, které zabere nejméně taktů. Vstup opět dostaneme v libovolné formě a můžeme předpokládat, že je korektní (žádné cykly v závislostech, atd...) (http://forum.matfyz.info/viewtopic.php?f=169&t=4099)
Pár poznámek k termínu a ke zkoušce: Malé příklady docela zapeklité, zasekl jsem se na čtyrce (nejprve jsem dělal Haskell) a potom už mi nezbyl čas na triviální dvojku. Jinak písemná část docela masíko – 3 hodiny v kuse něco psát, a ještě k tomu pod tlakem, není zrovna nejpříjemnější zážitek. Hric je příjemnej, na ústní dostanete i čas na opravu svých chyb v malých příkladech. Dá se ale říct, že na velkém příkladu záleží podstatně víc. Měl jsem zhruba tři malé příklady a velký prý «pekně» a dostal jsem dvojku, takže pohoda. Ještě poznámka k teorii – rozhodně se ji naučte. Neni jí tolik a není tak těžká. A 5 vs. 0 bodů je docela rozdíl. A ještě jedna poznámka ke Scheme – sice jsem na něj koukal, ale zatím to vypadá, že se nezkouší. I tak bych ale doporučoval – nezanedbat...
Čestmír
Malé příklady (75 minut):
1. Prolog: Přidejte ke každému vrcholu v n-árním stromě dvě přirozená čísla. První je číslo pořadí vrcholu při průchodu preorder, druhé při průchodu postorder.
2. Prolog: Najděte nezávislou množinu v grafu takovou, že ji nelze zvětšit přidáním vrcholu. (Použijte hladový algoritmus.)
3. Haskell: V binárním stromě některé prvky porušují podmínky uspořádání na binární vyhledávací strom. Vydejte seznam vrcholů, které uspořádání porušují a počet předchůdcu, ve kterých ho porušují.
4. Haskell: Dán typ data HTML a = Elm String [(HTML a)] | Txt a a úkolem je
5. Teorie – Prolog: Popište unifikační algoritmus.
Velký příklad (90 minut):
Požadavková ekvivalence: Na vstupu dostanete seznam prvků množiny a seznam požadavků. Požadavek říká, že nějaké dva prvky množiny mají patřit do stejné třídy ekvivalence, nebo že mají patřit do různých tříd ekvivalence. Každý požadavek má danou prioritu. Cílem je vytvořit program, který ze zadané množiny vytvoří třídy ekvivalence tak, aby uspokojily co nejvíce požadavků. Navíc přednost mají požadavky s větší prioritou (pokud mají stejnou prioritu, pak má přednost požadavek, který dává 2 prvky do stejné třídy). Program má také vrátit seznam splňených požadavků a nejvyšší prioritu, na které došlo ke kolizi požadavků.
Malé příklady mi přišly poměrně jednoduché, když člověk ví, jak na to, není problém je stihnout, protože řešení je většinou na pár řádků. Vzhledem k tomu, že na velký byla hodina a půl, tak se to taky dalo zvládnout. Hric kontroluje nejdřív malé příklady, pokud je v nich nějaká menší chyba, tak je ještě vrátí opravit. Velký příklad si pročítal až těsně před ústním a případné nejasnosti si nechává vysvětlit.
Zdeněk
Ústní probíhají odpoledne, až do večera (podle toho, na kdy se zapíšete). Moje zkušenost: Malý příklad mi jeden chyběl (nestihl jsem), ale ostatní byly bez připomínek a jeden se mu myslím dokonce zvlášť líbil (měl u něj smajlíka). Velký příklad jsem neměl úplně doimplementovaný a měl také komentáře k neefektivitě a nevhodnosti některých (jinak syntakticky správných) konstrukcí. Ale nijak mě u ústní nemučil a bez velkého váhání mi dokonce (k mému nemalému údivu) dal jedničku. Takže neztrácejte naději (ať už na jakoukoli známku), pokud nestihnete všechno.
— Adam
Ty hajzle! Ale asi to bude tim, ze u me pripominky u malych prikladu mel skoro vsude :)
— Cestmir
Koukám, že tady je to skoro, jak nějakej realtime chat;). BTW tady je to «hezké» řešení příkladu 3.:
Deprecated: Assigning the return value of new by reference is deprecated in /DISK2/WWW/lokiware.info/mff/formatters/highlight/java.php on line 5
data Tree a = Leaf a | Tree (Tree a) a (Tree a) getBad :: Ord a => (Tree a) -> [(a,Int)] getBad t = filter (\(x, n) -> n/=0) (getBad0 [] t) where countBad conds x = foldr (+) 0 [ if c x then 0 else 1 | c <- conds ] getBad0 conds (Leaf x) = [(x, countBad conds x)]
Prolog
1) Najít kliku v grafu.
2) Z orientovaného grafu obsahujícího cykly (orient. hrany: AB, AC, BC) poodstraňovat hrany AB.
Haskell
3) Multimnožinu rozdělit na dvě tak, aby se jejich součty rovnaly.
4) Daný seznam s a seznam dvojic (a,b) a máme vypsat všechny permutace pro které platí, že a je v permutaci před b.
5) Něco o typových třídách a instancích ;)
Velký příklad:
Na vstupu v termu aritmeticky vyraz (+,-,*,/,sin, cos), ten prevest na hradlovou sit (vystup ma byt seznam hradel). Hradlo ma nazev, typ, vystup a seznam vstupu.
Navic hradla + a * mohou mit libovolny pocet vstupu (ostatni jen 2 nebo 1) a na jejich vstupu nesmi byt hradla stejneho typu.
— Pepa
Prolog:
1) vygenerovat *seznam* všech neklesajicich posloupnosti prorozenych cisel, ktere daji soucet N, (bez setof, bagof, findall)
2) projit acyklicky orientovany graf do hloubky a do kazdeho vrcholu pridat cas prichodu a odchodu
Haskell:
3) definovat binarni strom s hodnotami pouze v listech, napsat fci, ktera listy stromu rozdeli do mnozin podle poctu hran vedoucich do prava na ceste z korene
4) jsem to psal dneska a uz jsem to zapomnel.... po ustni doplnim
Teorie nebyla
Velky priklad: Je zadan pocet procesoru N, seznam uloh, kazda trva cas T a zabere K procesoru, potom jsou jeste zavislosti, pokud uloha J zavisi na uloze I, musi J zacit az pote, co skonci I. Najdete pomoci nejake heuristiky reseni, ktere rozvrhne ulohy(tak aby kazda uloha mela k dispozici cas, pocet procesoru ktere potrebuje a aby byly splneny zavislosti)