IOI 30.1.2014
Napsal: 30. 1. 2014 17:16
Dnes relativne snadne zadani:
- 1) Grafy:
a) Def. kostru grafu.
b) Pro ktera n existuje graf s prave n ruznymi kostrami? - 2) Lingebra:
Mame lin. zobrazeni f: R3 -> R3, (a+b,b+c,c+a) -> (a-b,b-c,c-a).
a) je zobrazeni dobre definovane na celem R3?
b) je na?
c) je proste? - 3) Analyza:
a) Def. parc. derivace.
b) Napiste nutnou podminku lok. extremu funkce vice promennych.
c) Naleznete lokalni a globalni extremy funkce f(x,y) = xy + 12/x + 18/y na intervalu (0, +nekonecno) - 4) Grupy:
a) Def. grupu.
b) Mame algebry A({0,1,2,3,4,5}, +(mod 6)) a B({1,2,3,4,5,6}, * (mod 7)). Ukazte, ze jsou to grupy.
c) ???
d) Jsou A, B izomorfni? - 5) Vyr. logika:
a) Definujte dukaz a vysvetlete, co znamena |--- (symbol "dokazuje, je dokazatelne").
b) Co je to spor? Co je nezavisla formule?
c) Dokazte A->A pomoci zakladnich axiomu A->(B->A) a (A->(B->C))->((A->B)->(A->C)). - 6) Automaty:
a) Definujte jazyk.
b) Napiste gramatiku, ktera prijme jazyk {anbn; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri?
c) Napiste gramatiku, ktera prijme jazyk {anbncn; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri? - 7) Heapsort:
a) V pseudokodu napiste algoritmus pro Heapsort. Napiste jeho slozitost.
b) Slozitost Heapsortu srovnejte s Quicksortem. - Vlakna:
a) Def. vlakno.
b) Nasledujici kod opravte tak, aby bylo bezpecne jej spustit ve vice vlaknech:c) Odhadnete, v kolika vlaknech je omptimalni takovou funkci spustit, pokud vite, ze funkce main_computation() je velmi narocna na vypocet?Kód: Vybrat vše
int total = 0; int count = 1; int compute() { int result = main_computation(); total = total + result; count = count + 1; }
Vysvetlete svuj odhad. Jak se Vas odhad zmeni, pokud bude funkce hodne pristupovat na disk? Vysvetlete.