http://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