- 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.
IOI 30.1.2014
IOI 30.1.2014
Dnes relativne snadne zadani:
Re: IOI 30.1.2014
chybějící otázka u grup je:
c) Jsou A a B cyklické? Pokud ano, najděte alespoň jeden generátor.
v IP verzi byla místo automatů otázka na objektové programování:
Objektové programování:
a) Co znamená, že je třída abstraktní, a k čemu se používá?
b) K čemu slouží konstruktor a destruktor?
c) Který z následujících výstupů "" (prázdný), "A", "B", "AB", "BA", může vypsat následující kód:d) Může konstruktor selhat?
jaké je řešení toho 1b? tedy, pro která n existuje graf s právě n různými kostrami?
já jsem si myslel, že se ptají na úplné grafy, tak jsem tam napsal pokud n = k^(k-2), ale u ústního mi řekli, že tak to nebylo myšleno. doteď vlastně nevím, jakým způsobem by se to řešilo
c) Jsou A a B cyklické? Pokud ano, najděte alespoň jeden generátor.
v IP verzi byla místo automatů otázka na objektové programování:
Objektové programování:
a) Co znamená, že je třída abstraktní, a k čemu se používá?
b) K čemu slouží konstruktor a destruktor?
c) Který z následujících výstupů "" (prázdný), "A", "B", "AB", "BA", může vypsat následující kód:
Kód: Vybrat vše
public class A {
public A() {
System.out.print("A");
}
}
public class B extends A {
public B() {
System.out.print("B");
}
}
Object o = new B();
jaké je řešení toho 1b? tedy, pro která n existuje graf s právě n různými kostrami?
já jsem si myslel, že se ptají na úplné grafy, tak jsem tam napsal pokud n = k^(k-2), ale u ústního mi řekli, že tak to nebylo myšleno. doteď vlastně nevím, jakým způsobem by se to řešilo
Re: IOI 30.1.2014
no, odpoved na 1b taky nevim, napsal jsem tam peknou blbost...
Jinak vsem v budoucnu statnicujicim velmi doporucuji donest si vlastni svacinu. Budete tam od pul devaty treba az do jedny nebo i dele, v kuse, moc vas nikam nepusti. A take doporucuji, aby svacina obsahovala nejen jidlo, ktere vas zasyti, ale i nakrmi mozek (tedy hlavne cukr, ale ne hroznovy, ale normalni!).
Jinak vsem v budoucnu statnicujicim velmi doporucuji donest si vlastni svacinu. Budete tam od pul devaty treba az do jedny nebo i dele, v kuse, moc vas nikam nepusti. A take doporucuji, aby svacina obsahovala nejen jidlo, ktere vas zasyti, ale i nakrmi mozek (tedy hlavne cukr, ale ne hroznovy, ale normalni!).
-
- Matfyz(ák|ačka) level I
- Příspěvky: 12
- Registrován: 26. 1. 2012 18:50
- Typ studia: Informatika Bc.
- Login do SIS: 62601319
Re: IOI 30.1.2014
1b) n = 0 platí pro nesouvislé grafy, n=1 pro libovolný strom. Pro n >= 3 je to kružnice o n vrcholech, vždycky odebereme právě jednu hranu a to můžeme udělat n způsoby. Jediná zapeklitost je s n = 2. Takový graf nemůže obsahovat kružnici, protože při její existenci bude mít alespoň 3 kostry, pokud je souvislý. Ale pokud neexistuje kružnice, je to strom, který má jen jednu kostru. Čili odpověď zní pro libovolné přirozené n kromě dvou.