od Dr. Eddy » 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:
Kód: Vybrat vše
int total = 0;
int count = 1;
int compute()
{
int result = main_computation();
total = total + result;
count = count + 1;
}
c) Odhadnete, v kolika vlaknech je omptimalni takovou funkci spustit, pokud vite, ze funkce main_computation() je velmi narocna na vypocet?
Vysvetlete svuj odhad. Jak se Vas odhad zmeni, pokud bude funkce hodne pristupovat na disk? Vysvetlete.
Dnes relativne snadne zadani:
[list]
[*]1) [b]Grafy:[/b]
a) Def. kostru grafu.
b) Pro ktera [i]n[/i] existuje graf s prave [i]n[/i] ruznymi kostrami?
[*]2) [b]Lingebra:[/b]
Mame lin. zobrazeni f: R[sup]3[/sup] -> R[sup]3[/sup], (a+b,b+c,c+a) -> (a-b,b-c,c-a).
a) je zobrazeni dobre definovane na celem R[sup]3[/sup]?
b) je na?
c) je proste?
[*]3) [b]Analyza:[/b]
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) [b]Grupy:[/b]
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) [b]Vyr. logika:[/b]
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) [b]Automaty:[/b]
a) Definujte jazyk.
b) Napiste gramatiku, ktera prijme jazyk {a[sup]n[/sup]b[sup]n[/sup]; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri?
c) Napiste gramatiku, ktera prijme jazyk {a[sup]n[/sup]b[sup]n[/sup]c[sup]n[/sup]; n prirozene, >= 1}. Do jake kategorie Chomskeho hierarchie patri?
[*]7) [b]Heapsort:[/b]
a) V pseudokodu napiste algoritmus pro Heapsort. Napiste jeho slozitost.
b) Slozitost Heapsortu srovnejte s Quicksortem.
[*]8) [b]Vlakna:[/b]
a) Def. vlakno.
b) Nasledujici kod opravte tak, aby bylo bezpecne jej spustit ve vice vlaknech:
[code]
int total = 0;
int count = 1;
int compute()
{
int result = main_computation();
total = total + result;
count = count + 1;
}
[/code]
c) Odhadnete, v kolika vlaknech je omptimalni takovou funkci spustit, pokud vite, ze funkce main_computation() je velmi narocna na vypocet?
Vysvetlete svuj odhad. Jak se Vas odhad zmeni, pokud bude funkce hodne pristupovat na disk? Vysvetlete.[/list]