Matfyz Wiki

Zk 30.6.

Ganef at 2011-07-01 20:46:50

První písemka:

PROLOG:

  1. Rozhodnout, zda logická formule je tautologií. Mohla obsahovat proměné &, (or), =>, závorky. Operátory měly klasické priority.

  2. Třídění sléváním. Pozor nebyl na mysli MergeSort, ale jeho modifikace, která se normálně používá pro vnější třídění.

HASKELL:
3) Máme dán binární strom, kde v každém listu je ještě nějaká hodnota. Naprogramujte relaci ~, pokud A~B <=> existují vrchol a(A), b(B), že b je v podstromu a.

  1. Hledání mostů v orientovaném grafu. (Dělal jsem to pomocí BFS a ukázalo se, že Kryl tento algoritmus nezná... A úplně ho ode mě nepochopil. Takže se to asi mělo dělat jednoduše kvadraticky.)

Druhá písemka:
Je dán multigraf. Měli jsme ho rozložit na hranově disjunktní kružnice. -- Za tuto úlohu jsem hrozně rád, nebyla těžká a má to i velmi jednoduchou implementaci.