Obor IOI, zaměření diskrétní struktury a algoritmy.
Matematika:
1 Vlastní čísla (škrtal jsem)
1) Definovat charakteristický polynom čtvercové matice.
2) Dokázat, že determinant A je roven násobku vlastních čísel A.
3) Najít matici 2x2, která má vlastní čísla 1 a 2 a nemá na žádném místě 0.
2 Kombinatorika
1) Vyslovit a dokázat binomickou větu.
2) Máme 15 modrých, 35 červených, 25 zelených a 25 růžových koulí (čísla a barvy nejspíš nesouhlasí přesně). Desetkrát udělám to, že vyberu náhodně kouli a dám ji zpět. Jaká je pravděpodobnsost, že právě sedmkrát vyberu modrou kouli.
3) Kolika možnými způsoby můžeme zvolit počty modrých, červených, zelených a růžových koulí tak, aby od každé barvy bylo nejvíce 50 koulí a celkem jich bylo 100.
3 Funkce více proměnných
1) Definice parciální derivace
2) Vyslovit větu o lagrangeových multiplikátorech.
3) Spočítat extrémy funkce
pro body takové, že
a
.
4 Kostry
1) Definovat kostru souvislého grafu.
2) Spočítat počet koster nějakého konkrétního nakresleného grafu.
3) Máme d-regulární graf G na n vrcholech, který má právě k koster. Navíc každá hrana je obsažena ve stejném počtu koster jako každá jiná hrana. Spočítejte, kolik koster bude mít graf G-e pro nějakou hranu e.
Komentář: Mno, docela hard to bylo. Nečekal jsem moc důkazy, nečekal jsem lagrangeovy multiplikátory a nečekal jsem vytvořující funkce (na ty je napasovaná úloha 2.3). Na druhou stranu důkaz binomické věty lze vymyslet čistě kombinatoricky. Pokud někdo neuměl lagrangeovy multiplikátory, tak vůbec neměl jednu otázku, já měl jenom štěstí, že jsem zrovna v létě měl diskrétní a spojitou optimalizaci, kde se ty multiplikátory zobecňovali, takže jsem si je ještě pamatoval.No a pěkný příklad je 4.3, ale takový trošku na přemýšlení, nevím jestli úplně vhodné ke státnicím. Jo a ty vlastní čísla jsem škrtal protože u důkazu jsem nevěděl jak se vypořádat s
, když do charakteristického polynomu dosadím 0. A nějak jsem úplně nevěděl, jak vůbec přistoupit k vymejšlení tý matice.
Nástin řešení:
2.2 Pokud si označím X náhodnou proměnnou značící počet modrých koulí, pak X má binomické rozdělí Bi(10,15/100). Takže je to
.
2.3 Jak jsem řekl, vytvořující funkce. Označím si polynom
. Pak hledané číslo je koeficient u
v polynomu
. Což si teda můžu explicitně vyjádřit nějakýma trikama s kombinačními čísly (které jsou v Kapitolách). Já to celé nedopočítal, protože jsem si ty triky už nepamatoval, ale zřejmě byli plně spokojeni s tím, že vím jak to řešit.
3.3 No prostě aplikuju ty lagrangeovy multiplikátory, vyjde mi docela divný systém čtyř rovnic o čtyřech neznámých, ale když do toho člověk chvíli kouká a vezme v úvahu to, že
, tak mu vyjde, že
. Ale nic hezkýho.
4.3 Potřebuju spočítat v kolika kostrách je obsažena jedna hrana. Tento si počet si označím x. Když pak odeberu jednu libovolnou hranu, pak mi zmizí přesně ten počet koster. Počítám dvěma způsoby počet dvojic (K,e), kde K je kostra G a e je hrana z K. Na jednu stranu mám k koster a v každé je n-1 hran, takže je to k(n-1). Na druhou stranu mám |E(G)| hran a každá je v x kostrách. Takže dostanu
. Teď už si jenom spočítám, že
díky d-regularitě G a dostanu
. Takže počet koster G-e je právě k-x.
Informatika
1 Databáze (škrtal jsem)
...netuším, ani jsem to pořádně nečetl...
2 Přihrádkové třídění
1) Napsat pseudokód přihrádkového třídění.
2) Jaká je časová složitost přihrádkového třídění (stačí bez důkazu).
3) Jak použít přihrádkové třídění na mazání duplicitní hran z grafu. Mám graf na n vrcholech s m hranami, každá hrana je neuspořádaná dvojice vrcholů. Chci rychlý algoritmus jak se zbavit duplicitních hran.
3 Jazyky
1) Napsat Myhill-Nerovodu větu.
2) Popsat deterministické a nedeterministické zásobníkové automaty.
3) Zařadit do Chomského hierarchie následující jazyk:
.
4 Teorie grafů (otázka mého zaměření)
1) Definovat hranovou barevnost.
2) Vyslovit Vizingovu větu.
3) Bez Vizingovy věty dokázat, že hranová barevnost libovolného grafu je nejvýše
, kde
je nejvyšší stupeň grafu.
Komentář: No vůbec si nejsem jistej, jaké řešení chtěli u 2.3. A ten jazyk na zařazení je pěkně hard, zatím nevim jak to vyřešit. Ale zase otázka mého zaměření fakt easy, přišla mi lehčí než otázka Kostry v matematice.
Nějaký nástin řešení:
2.3 Já to řešil prostě tak, že jsem si každou hranu seřadil do uspořádané dvojice (i,j) takové, že i<j. No a pak jsem na množiny hran pustil přihrádkové třídění nejdřív na první komponentu a potom na druhou komponentu (takže vlastně radix sort). To mi setřídí hrany v čase O(n+m) a zároveň to potřebuje jenom n přihrádek, takže ne moc prostoru. A pak už jenom smažu duplicity. Ale nezdá se mi, že tohle je chtěné řešení, docela by mě zajímalo, jak to mysleli autoři.
3.2 "Popsat" není zrovna jasné zadaní. No asi hlavně chtěli slyšet, jak se deterministický zásobníkový automat liší od nedeterministického. Já to tam tak nějak definoval a už moc navíc neokecával.
3.3 Já jsem jenom pomocí Myhill-Neroda dokázal, že není regulární: Mějme pravou kongruenci ~ konečného indexu k takovou, že L je sjednocení nějakých rozkladových tříd ~. Uvažme slova
, těch je k+1, takže existují indexy i<j takové, že
a
jsou ve stejné rozkladové třídě ~. Ale potom když k oběma přidám
dostanu, že
ale
, což je spor s tím, že ~ je pravá kongurence. Ten jazyk je nejspíš bezkontextový, ale zásobníkový automat jsem nevymyslel.
4.3 Prostě v jakémkoli pořadí barvím hrany G vždy nejmenší možnou přípustnou barvou.
No já měl tu "poněkud přísnější" komisi Sgall, Bulej, Fink a ještě někdo. Ani jednou se mě na nic neptali a rovnou řekli známku. U toho byli hodní
.
Celkový pocit je, že matematika byla překvapivě hard. Třeba oproti ukázkovým testům fakt znatelně. Myslel jsem, že u analýzy bude nějaká lehká limita nebo derivace, a ne lagrangeovy multiplikátory. A kombinatorika taky ne zrovna lehká. Docela lituju méně matematicky zaměřené kolegy, kteří matiku nevidí každý den, ty tohle mohlo pěkně zdrtit. Což taky zřejmě nastalo -- speciálně z matiky se vyhazovalo v nemalé míře. Informatika byla tak nějak adekvátní, možná až na ten těžkej jazyk (nebo je to easy a já to nevidím?)
Obor IOI, zaměření diskrétní struktury a algoritmy.
[b][u]Matematika:[/u][/b]
1 Vlastní čísla (škrtal jsem)
1) Definovat charakteristický polynom čtvercové matice.
2) Dokázat, že determinant A je roven násobku vlastních čísel A.
3) Najít matici 2x2, která má vlastní čísla 1 a 2 a nemá na žádném místě 0.
2 Kombinatorika
1) Vyslovit a dokázat binomickou větu.
2) Máme 15 modrých, 35 červených, 25 zelených a 25 růžových koulí (čísla a barvy nejspíš nesouhlasí přesně). Desetkrát udělám to, že vyberu náhodně kouli a dám ji zpět. Jaká je pravděpodobnsost, že právě sedmkrát vyberu modrou kouli.
3) Kolika možnými způsoby můžeme zvolit počty modrých, červených, zelených a růžových koulí tak, aby od každé barvy bylo nejvíce 50 koulí a celkem jich bylo 100.
3 Funkce více proměnných
1) Definice parciální derivace
2) Vyslovit větu o lagrangeových multiplikátorech.
3) Spočítat extrémy funkce [latex]f(x,y,z)=\sin(x)\sin(y)\sin(z)[/latex] pro body takové, že [latex]x+y+z=\pi/2[/latex] a [latex]x,y,z>0[/latex].
4 Kostry
1) Definovat kostru souvislého grafu.
2) Spočítat počet koster nějakého konkrétního nakresleného grafu.
3) Máme d-regulární graf G na n vrcholech, který má právě k koster. Navíc každá hrana je obsažena ve stejném počtu koster jako každá jiná hrana. Spočítejte, kolik koster bude mít graf G-e pro nějakou hranu e.
Komentář: Mno, docela hard to bylo. Nečekal jsem moc důkazy, nečekal jsem lagrangeovy multiplikátory a nečekal jsem vytvořující funkce (na ty je napasovaná úloha 2.3). Na druhou stranu důkaz binomické věty lze vymyslet čistě kombinatoricky. Pokud někdo neuměl lagrangeovy multiplikátory, tak vůbec neměl jednu otázku, já měl jenom štěstí, že jsem zrovna v létě měl diskrétní a spojitou optimalizaci, kde se ty multiplikátory zobecňovali, takže jsem si je ještě pamatoval.No a pěkný příklad je 4.3, ale takový trošku na přemýšlení, nevím jestli úplně vhodné ke státnicím. Jo a ty vlastní čísla jsem škrtal protože u důkazu jsem nevěděl jak se vypořádat s [latex](-1)^n[/latex], když do charakteristického polynomu dosadím 0. A nějak jsem úplně nevěděl, jak vůbec přistoupit k vymejšlení tý matice.
Nástin řešení:
2.2 Pokud si označím X náhodnou proměnnou značící počet modrých koulí, pak X má binomické rozdělí Bi(10,15/100). Takže je to [latex]\binom{10}{7}(15/100)^7 (85/100)^3[/latex].
2.3 Jak jsem řekl, vytvořující funkce. Označím si polynom [latex]p(x)=1+x+x^2+\cdots+x^{50}[/latex]. Pak hledané číslo je koeficient u [latex]x^{100}[/latex] v polynomu [latex](p(x))^4[/latex]. Což si teda můžu explicitně vyjádřit nějakýma trikama s kombinačními čísly (které jsou v Kapitolách). Já to celé nedopočítal, protože jsem si ty triky už nepamatoval, ale zřejmě byli plně spokojeni s tím, že vím jak to řešit.
3.3 No prostě aplikuju ty lagrangeovy multiplikátory, vyjde mi docela divný systém čtyř rovnic o čtyřech neznámých, ale když do toho člověk chvíli kouká a vezme v úvahu to, že [latex]0<x,y,z<\pi/2[/latex], tak mu vyjde, že [latex]x=y=z=\pi/6[/latex]. Ale nic hezkýho.
4.3 Potřebuju spočítat v kolika kostrách je obsažena jedna hrana. Tento si počet si označím x. Když pak odeberu jednu libovolnou hranu, pak mi zmizí přesně ten počet koster. Počítám dvěma způsoby počet dvojic (K,e), kde K je kostra G a e je hrana z K. Na jednu stranu mám k koster a v každé je n-1 hran, takže je to k(n-1). Na druhou stranu mám |E(G)| hran a každá je v x kostrách. Takže dostanu [latex]x=\frac{k(n-1)}{|E(G)|}[/latex]. Teď už si jenom spočítám, že [latex]|E(G)|=\frac{nd}{2}[/latex] díky d-regularitě G a dostanu [latex]x=\frac{2k(n-1)}{nd}[/latex]. Takže počet koster G-e je právě k-x.
[b][u]Informatika[/u][/b]
1 Databáze (škrtal jsem)
...netuším, ani jsem to pořádně nečetl...
2 Přihrádkové třídění
1) Napsat pseudokód přihrádkového třídění.
2) Jaká je časová složitost přihrádkového třídění (stačí bez důkazu).
3) Jak použít přihrádkové třídění na mazání duplicitní hran z grafu. Mám graf na n vrcholech s m hranami, každá hrana je neuspořádaná dvojice vrcholů. Chci rychlý algoritmus jak se zbavit duplicitních hran.
3 Jazyky
1) Napsat Myhill-Nerovodu větu.
2) Popsat deterministické a nedeterministické zásobníkové automaty.
3) Zařadit do Chomského hierarchie následující jazyk: [latex]L=\{ucv\mid u,v\in\{a,b\}^*,u
eq v\}[/latex].
4 Teorie grafů (otázka mého zaměření)
1) Definovat hranovou barevnost.
2) Vyslovit Vizingovu větu.
3) Bez Vizingovy věty dokázat, že hranová barevnost libovolného grafu je nejvýše [latex]2\Delta -1[/latex], kde [latex]\Delta[/latex] je nejvyšší stupeň grafu.
Komentář: No vůbec si nejsem jistej, jaké řešení chtěli u 2.3. A ten jazyk na zařazení je pěkně hard, zatím nevim jak to vyřešit. Ale zase otázka mého zaměření fakt easy, přišla mi lehčí než otázka Kostry v matematice.
Nějaký nástin řešení:
2.3 Já to řešil prostě tak, že jsem si každou hranu seřadil do uspořádané dvojice (i,j) takové, že i<j. No a pak jsem na množiny hran pustil přihrádkové třídění nejdřív na první komponentu a potom na druhou komponentu (takže vlastně radix sort). To mi setřídí hrany v čase O(n+m) a zároveň to potřebuje jenom n přihrádek, takže ne moc prostoru. A pak už jenom smažu duplicity. Ale nezdá se mi, že tohle je chtěné řešení, docela by mě zajímalo, jak to mysleli autoři.
3.2 "Popsat" není zrovna jasné zadaní. No asi hlavně chtěli slyšet, jak se deterministický zásobníkový automat liší od nedeterministického. Já to tam tak nějak definoval a už moc navíc neokecával.
3.3 Já jsem jenom pomocí Myhill-Neroda dokázal, že není regulární: Mějme pravou kongruenci ~ konečného indexu k takovou, že L je sjednocení nějakých rozkladových tříd ~. Uvažme slova [latex]a^{k+1}ca^0,a^{k+1}ca^1,a^{k+1}ca^2,\ldots,a^{k+1}ca^k[/latex], těch je k+1, takže existují indexy i<j takové, že [latex]a^{k+1}ca^i[/latex] a [latex]a^{k+1}ca^j[/latex] jsou ve stejné rozkladové třídě ~. Ale potom když k oběma přidám [latex]a^{k+1-i}[/latex] dostanu, že [latex]a^{k+1}ca^i.a^{k+1-i}
otin L[/latex] ale [latex]a^{k+1}c^j.a^{k+1-i}\in L[/latex], což je spor s tím, že ~ je pravá kongurence. Ten jazyk je nejspíš bezkontextový, ale zásobníkový automat jsem nevymyslel.
4.3 Prostě v jakémkoli pořadí barvím hrany G vždy nejmenší možnou přípustnou barvou.
No já měl tu "poněkud přísnější" komisi Sgall, Bulej, Fink a ještě někdo. Ani jednou se mě na nic neptali a rovnou řekli známku. U toho byli hodní :).
Celkový pocit je, že matematika byla překvapivě hard. Třeba oproti ukázkovým testům fakt znatelně. Myslel jsem, že u analýzy bude nějaká lehká limita nebo derivace, a ne lagrangeovy multiplikátory. A kombinatorika taky ne zrovna lehká. Docela lituju méně matematicky zaměřené kolegy, kteří matiku nevidí každý den, ty tohle mohlo pěkně zdrtit. Což taky zřejmě nastalo -- speciálně z matiky se vyhazovalo v nemalé míře. Informatika byla tak nějak adekvátní, možná až na ten těžkej jazyk (nebo je to easy a já to nevidím?)