# Zkouška 26.5.2014 (Dvořák + Hric)

<{ForumPost(poster="Sharduk", timestamp=2014-05-26 18:18:58)}>
Dnešní zadání bylo následující:  
  
**Prolog:**  
  
1) Definujte predikát orez(+Strom,+D,+H,-VStrom), který ve Stromu ponechá pouze uzly V, že D <= V <= H. Už bylo min 2x.  
  
2) Máme neorientovaný graf bez smyček, reprezentovaný pomocí seznamu sousedů. Napište predikát trojuhelniky(G,V), který ve V vrátí seznam všech trojúhelníků (třech vrcholů, které mezi sebou všechny mají hrany). Trojúhelníky by se v seznamu neměly opakovat.  
  
Př:

    troj([a->[b,c,d],b->[c,a],c->[b,d,a],d->[a,c],e->[]],V).
    V = [troj(a,b,c),troj(a,c,d)]
    

**Haskell:**  
  
1) Násobení řídkých polynomů -> mějme řídké polynomy reprezentované pomocí \[(nenulový koeficient,exponent)]. Definujte pro ně datový typ (nezapomeňte na nulový polynom) a napište funkci mult (i její datovou signaturu), která bude řídké polynomy násobit.  
Kdo neví (jako já jsem nevěděl  :D ) co je řídký polynom -> u spousty exponentů je nulový koeficient (exponenty prostě nejdou po 1, ale skáčou), ty samozřejmě nejsou v dané reprezentaci.  

    data Ridky a = Ridky [(Int,Int)] | Void
    Postup: vynásobit všechno se všim, posčítat závorky se stejným exponentem.
    

2) Definujte funkci fold a listy, bla bla, to byl hnus! Viz zde příklad 3: [http://forum.matfyz.info/viewtopic.php? ... tem#p33954](http://forum.matfyz.info/viewtopic.php?f=169&t=8281&p=33954&hilit=item#p33954)  
  
**Big One:**  
  
Mějme x1..xn, y1..yn posloupnosti, P cenu vyškrtnutí, I a J maximální počet po sobě jdoucích vyškrtnutí (pro posloupnost x resp y). Představte si, že jsou posloupnosti pod sebou a nyní máte prvky z x spárovat s y přímkami tak, že se nikde nic nekříží. V posloupnostech můžete vyškrtávat prvky, abyste je nemuseli párovat. Pro spárované xi s yi je cena abs(xi - yi). Pro celé možné spárování je tedy cena součet cen párů + (počet vyškrtnutých znaků * P). Najděte spárování s nejmenší cenou.  
  
Můj postup: vygeneruju si všechny možnosti vyškrtnutí pro x a y -> zazipuju \[zip a b | a <- moznosti x \[argumenty], y <- moznosti y \[argumenty] ]. Doporučuju si v generovaných možnostech v posledním prvku držet penalizaci za vyškrtávání. Pak zjistím nejnižší cenu takových spárování a vyhodím všechny (oni chtěli jen jedno), které tuto cenu má.  
  
Snad je to srozumitelný, kdybyste měli nějakej dotaz, tak napište.  
  
  
  
Celkově slušný, až na ten fold příklad. Dvořák byl v pohodě, Hric prý taky, a celkově to šlo :) O dvou vím, že neprošli malou písemku, ale jinak snad všichni v cajku.
<{/ForumPost}>