# 14.09.2016 Informatika (IPSS)

<{ForumPost(poster="Katami", timestamp=2016-09-14 12:18:07)}>
Formát vizte blog kolegy Petra Hudečka.  
Až na jednu změnu:  
Otázky byly pouze tři a student musel řešit všehcny tři, na které měl dohromady 90 minut. Nicméně i nic na jednom papíře neznamenalo, že vyletíte. Každá otázka měla čtyři pod-otázky se stupňující se náročností. Kolega Tůma tvrdil, že obtížnost zkoušky by měla být stejná jako u předchozího termínu (čtyři otázky, student řeší pouze tři z nich). Mi to přišlo jednodušší, nicméně to usuzuji pouze podle svých otázek.  
  
**Informatika (zaměření systémové programování)**  
1 Synchronizační mechanizmy  
1.1 Vysvětlete pojem zámek (mutex), napište jeho rozhraní a vysvětlete sémantiku jednotlivých funkcí.  
1.2 Načrtněte implementaci metod mutex-u. Stačí minimální funkční řešení.  
1.3 Vysvětlete pojem podminková proměnná (condition variable), napište rozhraní a vysvětlete sémantiku jendotlivých funkcí.  
1.4 Proč některé z metod rozhraní condition variable přijímají jako argument mutex.  
  
2 Vyhledávací stromy  
2.1 Definujte binární vyhledávací strom  
2.2 Definujte AVL strom  
2.3 Spočtete kolik minimálně a maximálně vrcholů obsahuje binární vyhledávací strom a AVL strom v přípdě, že ve stromě existuje cesta délky 3 (myšleno počet hran na cestě z kořene do listu). Načrtněte takové stromy.  
2.4 Pokud v binárním vyhledávacím stromu dostanu prvek, jak najdu jeho následníka (následník definovaný jako nejmenší z vrcholů s vyšší hodnotou)  
  
3 Neprocedurální programování  
3.1 Mějme v prologu predikáty

    muz(hugo).
    muz(adam).
    zena(eva).
    rodic(adam, hugo).
    rodic(eva, hugo).
    ...
    

Implementujte v prologu predikáty:

    otec(Ot, Di) :-
    dedecek(De, Di) :-
    

(bylo *definované* co dělají predikáty muz, zena, rodix a co mají dělat predikáty otec, dedecek)  
  
3.2 Jak jsou v prologu definované seznamy?  
3.3 Mějme predikát concat(S1, S2, L), který spojí seznamy S1 a S2 a vrátí je v seznamu L. Tedy

    
    
    concat([], L, L).
    concat([X|Xs], S2, [X|L]) :- concat(Xs, S2, L).
    

Jaký význam má predikát definovaný jako

    r([], []).
    r([X|Xs], L) :- r(Xs, L1), concat(L1, [X], L).
    

3.4 Je nějaký rozdíl mezi následujícími dvěmi predikáty v prologu?

    X = 1 + 3.
    X is 1 + 3.
    

Po nějaké chvíli si komise přišla pro mě a dalších několik kolegů, po cestě nám řekla že to máme v pohodě a že budou řešit jen drobnosti. Po chvíli, co vyřešili ostatní kolegy mi řekli, že ani nemusím chodit dovnitř, že to mám všechno dobře a že mám jedničku, pak se radili na výsledné známce ze státnic (chyběla mi jen tahle zkouška). Na papíře jsem toho neměl moc napsaného, jenom základní věci na které se ptali a nic navíc.  
  
Komentáře k řešení, aneb kolik toho asi tak bylo třeba  
1.1 Rozhraní mutex jsem definoval jen jako dvě metody lock(), unlock() a zminil jsem se, že by se nám mohlo hodit i try_lock().  
1.2 Mutex jsem triviálně naimplementoval pomocí binárního semaforu.  
1.3 Rozhraní condition variable jsem popsal zjednodušené z C++: wait(mutex, predicate) a notify() a zmínil jsem se, že wait by mohl mít i nějaký timeout a notify by mohlo mít notify_one a notify_all. Nezmiňoval jsem se ani o spurious wakeup.  
1.4 Akorát jsem napsal, že by uživatel měl problém, kdyby musel volat wait(m, f); *; m.lock(); protože v * by mohl někdo změnit výsledek f().  
  
2.3 Jsem první namaloval a pak k tomu napsal počet. U min BST jsem napsal že to je cesta, u max BST jako $\textstyle \sum_{i=1}^n{2^n} = 2^{n+1} - 1$. U min AVL jsem naznačil jak rekurzivně spočítám počet vrcholů z výšky.  
2.4 Slovně jsem popsal algoritmus, nepsal jsem ani žádný pseudokód.  
  
3.2 Možná by stačilo jedno slovo "rekurzivně". Já jsem k tomu měl ještě stromový obrázek rozložení seznamu \[1,2,3,4].  
3.3 Otáčí seznam a napsal jsem proč to funguje.  
  
Až na popis sémantiky synchronizačních primitiv jsem odpovídal pár větama na 2-3 řádky a nebyl s tím problém.
<{/ForumPost}>