14.09.2016 Informatika (IPSS)

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: 14.09.2016 Informatika (IPSS)

14.09.2016 Informatika (IPSS)

od Katami » 14. 9. 2016 12:18

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

Kód: Vybrat vše

muz(hugo).
muz(adam).
zena(eva).
rodic(adam, hugo).
rodic(eva, hugo).
...
Implementujte v prologu predikáty:

Kód: Vybrat vše

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

Kód: Vybrat vše



concat([], L, L).
concat([X|Xs], S2, [X|L]) :- concat(Xs, S2, L).
Jaký význam má predikát definovaný jako

Kód: Vybrat vše

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?

Kód: Vybrat vše

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.

Nahoru