# [Zk] 13.2.2008

<{ForumPost(poster="Vinc", timestamp=2008-02-13 23:52:42)}>
**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...
<{/ForumPost}>

<{ForumPost(poster="hroh", timestamp=2008-02-14 08:05:38)}>
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.
<{/ForumPost}>