Některé příklady ve zkoušce z loňska

univ

Některé příklady ve zkoušce z loňska

Příspěvek od univ »

únor 08, 2006. Předmět: Zkouška 8. 2.

Prolog:

kód:
Je dán n-ární strom. Pro dané k vraťte všechny listy, které jsou dosažitelné po cestě, na které součet pořadových čísel vybíraných synů (zleva od 0) se rovná právě k.

kód:
Je dán graf. Zjistěte, zda je bipartitní a vydejte dotvrzující třídy tozkladu vrcholů.

Haskell:

kód:
Je dán seznam vektorů. Vyberte z něho ty prvky, které nejsou dominovány jiným vektorem. (u je dominován v, pokud všechny složky v jsou větší (>=) než přísl. složky u)

kód:
Jsou dány ceny a objem předmětů a objem batohu. Najděte nejcennější naplnění batohu. Vydejte jeho cenu a objem.

***

únor 03, 2006. Předmět: Zkouska 3.2.2006

Prolog:

kód:
1. 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 (zleva).

kód:
2. Hladovým algoritmem sestrojte v daném grafu nezávislou množinu vrcholů, která nejde zvětšit přidáním vrcholu.

Haskell:

kód:
3. 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 úrovní (od vrcholu ke kořeni), na kterých ho porušují.

kód:
4. Je dán orientovaný graf a rozklad jeho vrcholů do tříd ekvivalence. Sestrojte nový graf, ve kterém spojíte všechny vrcholy z jedné třídy do jednoho vrcholu-reprezentanta.

Velký (Prolog/Haskell):
kód:
Alokace registrů:
Hradlová síť je množina hradel, kde každé hradlo má jediný výstup, svoje jedinečné jméno a seznam vstupů (s daným pořadím). Vstupy jsou buď jména jiných hradel nebo jméno vstupních bodů sítě. Síť je acyklická, tzn. žádné hradlo není závislé na svém výstupu. Vstup programu je hradlová síť. Úloha je
a) uspořádat hradla tak, aby každé hradlo bylo až za hradly, které počítají jeho vstupy
b) Přiřadit vstupním bodům sítě a výstupům hradel "registry CPU". Registr můžete použít pro výsledek dalšího hradla, pokud hodnota z něho již nebude potřeba pro vstup žádného hradla.
Výstupní registr je vždy různý od všech vstupních registrů (pro každé hradlo). Počet registrů není omezený, ale snažte se heuristicky použít jich co nejmenší počet. Tj. vyhněte se triviálnímu řešení kdy výsledku každého hradla je přiřazený jiný registr.
Odpovědět

Zpět na „2006“