[Zk] 13.2.2008

Prolog

Na vstupe je N-árny strom (reprezentácia akú si kto zvolí) a externá podmienka p(C), kde C je cesta z koreňa k danému vrcholu. Pre každý vrchol v strome treba skontrolovať podmienku p() a ak nie je splnená, celý podstrom, vrátane vrchola, pre ktorý testujeme, vypustiť zo stromu.

Na vstupe je orientovaný graf G (reprezentovaný ako chceme). Nájdite všetky cesty P={v_1,v_2,v_3} dĺžky dva a vložte do grafu hrany (v_1, v_3). 

Haskell

Je daný orientovaný graf G reprezentovaný zoznamov susedov. Pre každý vrchol typu Vrchol je daný zoznam susedov spolu s ohodnotením hrany:
type Vrchol a = (a,[Susedia a])
type Susedia a = (a, Int)
Vytvorte nový graf taký, že všetky hrany budú orientované opačne a zachovajú si svoje ohodnotenie.


Je daný zoznam nezáporných čísel xs a cena n. Vyberte postupnosť čísel, ktorých cena bude zhora najbližšie cene n.

Veľký príklad

Škoda reči, osobne som na zadanie najskôr robil :shock: potom :o a nakoniec :evil: a :|. Ak ho budem schopný sformulovať nejak rozumne (originálne zadanie by nikto nepochopil bez vysvetlenia) tak ho sem pridám, ak nazbieram odvahu...

Pokusím se nastínit velký příklad:

Na vstupu máte dvě časové posloupnosti (zaznamenávající např. akcie, teplotu, či co). Máte je tzv. sesynchronizovat. Úkolem bylo najít heuristicky co nejlepší řešení, tj. s nejmenší penalizací.

Prakticky jste měli přiřazovat hodnoty z jedné posloupnosti k hodnotám z druhé posloupnosti. Dovolené bylo nějaké hodnoty z posloupností vynechat, vynechávat ale můžete vždy jen pouze z jedné posloupnosti. Př.: máte posloupnost p a q, přiřadíte p1 a q1, dále vidíte, že podobné hodnoty mají p2 a q3, tak je přiřadíte spolu, můžete třeba i p2 a q4, nebo q5 (analogicky q2 : p3 nebo p4 nebo p5), nelze však obě druhé hodnoty vynechat a přiřadit až p3 ke q3. Je stanovená časová mez, kterou nesmíte překročit, tj. kolik hodnot můžete vynechat.

Penalizuje se jak rozdíl hodnot v přiřazených hodnotách, tak i velikost vynechání (1:1 se nepenalizuje).

Výsledkem měla být posloupnost dvojic přiřacených indexů prvků posloupností a celková hodnota penlizece.

Snad se to dá pochopit. Když se nad tím zamyslíte, tak to není těžké jak pochopit, tak naprogramovat. Jakékoliv otázky případně zodpovím.