Matfiz : Neprocedurální Programování / Zkouška ZS 2007

Toto je stará verze stránky NeprocedurálníProgramování/ZkouškaZS2007-8 z 2008-01-25 19:27:17..

Průběh

5 malých příkladů (75min) – 2 na Prolog, 2 na Haskell a jedna teoretická otázka (vše po 5 bodech)
1 větší příklad (90min) – jazyk je možné zvolit, ale je to spíše na Prolog
pak pan Hric opraví malé příklady, velký prohlíží až při ústní (a chce ho nejdřív popsat slovně, potom prochází kód)

Pár postřehů

těch 75min se jeví jako krátká doba, ale stihnout to jde, protože jakmile si člověk uvědomí, co vlastně po něm zadání chce, tak je kód na pár řádků (doslova)
(skoro) vůbec není nutné řešit efektivitu (historka ze života: u velké úlohy (z 21.1.) jsem nedokázal vymyslet nějaké smysluplné ukládání mezivýsledků, takže jsem nakonec vygeneroval všechny cesty a ty potom ověřoval – sice mi řekl, že je to fakt neefektivní, ale další poznámku k tomu neměl)
vyplatí se podívat se i na tu teorii (seznam pojmů jsem viděl na stránkách přednášejícího), protože je za to taky 5 bodů

Řešené příklady

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

Zadání zkoušek

21.1.2008

http://forum.matfyz.info/viewtopic.php?f=169&t=4049

25.1.2008

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.

Teorie:

Negace v Prologu. Vysvětlete, jak je definována a popište vlastnosti a nevýhody této definice.