23.6.2016 Matika, Informatika (IPSS)

Vše co se týká bakalářských státních závěrečných zkoušek.
Katami
Matfyz(ák|ačka) level I
Příspěvky: 27
Registrován: 3. 2. 2014 13:40
Typ studia: Informatika Ph.D.

23.6.2016 Matika, Informatika (IPSS)

Příspěvek od Katami »

Formát viz blog kolegy Petra Hudečka.

Obor jsem měl IPSS. Píšu zadání ranní informatiky a odpolední matiky (matika byla stejná i pro IOI). Čekám, že někdo doplní chybějící části, opraví nekorektnosti, případně i doplní řešení :twisted:.
Zadání je volně přepsáno.

Matematika
1 Ortogonální doplněk (odmítl jsem, chtěli definici, něco ukázat a něco spočítat)

2 Funkce více proměnných
1. Definujte pojem totální diferenciál.
2. Vyslovte větu o nutné podmínce pro lokální extrém.
3. Nalezněte lokální a globální extrémy funkce f(x,y) = x + 2x/y + 1/y

3 Pravděpodobnost
1. Definujte podmíněnou pravděpodobnost.
2. Mějme balíček bonbónů obsahující 15 s jahodovou příchutí, 15 s malinovou a 15 s citronovou. Z balíčku náhodně vytáhneme 6 bonbonů (nevrací se). Napište výpočet pravděpodobností následujících jevů (není nutné vyčíslovat numericky)
a) Z balíčku vytáhneme alespoň jeden citronový.
b) Z balíčku vytáhneme alespoň jeden z každou příchutí.
c) Z balíčku vytáhneme 6 citronových, za předpokladu že alespoň jeden je citronový.

4 Teorie grafů
1) Mějme graf C_9 s vrcholy označenými \{v_1, ..., v_9\} (postupně, tedy hrany vedou z v_i do v_{i+1} ; 9+1 = 1). K tomuto grafu přidáme hrany mezi vrcholy v_i,v_j tak, že i \equiv j\ (\textrm{mod}\ 3). Kolik nejvíce lze z grafu odebrat hran tak, aby byl pořád souvislý.
2) Kolik nejvíce vrcholů lze odebrat, aby v_1 a v_5 leželi v jiné komponentě souvislosti.
3) Vyslovte Mengerovu větu a naznačte důkaz.

Informatika
1 Systémové Programování (jedno ze zaměření IPSS)
a) Vysvětlete koncept paměťově mapovaných souborů (memory mapped files). Navrhněte nové (nebo popište existující) API na práci s paměťově mapovanými soubory.
b) Detailně popište, co se stane když se chce od 1000 bytu zapsat jeden byte do paměťově mapovaného souboru), pro popis použijte vaše navržené API. Popis by měl začínat prvním příkazem aplikace pro práci s mapovanými soubory a měl by končit fyzickým zápisem na disk. Detailně vysvětlete kdo (aplikace, OS, procesor) provádí které kroky.
c) Předpokládejme standardní multithreadový procesor s hardwarovou podporou pro více jader. Může se stát, že by při čtení stejného souboru jedním vláknem dostalo druhé vlákno data již z cache (myšleno procesorové cache, ne cache OS).

2 Programovací jazyky
Pro následující otázky si vyberte jeden z jazyků C++/C#/Java. Svou volbu vyznačte.
1) Navrhněte API pro práci se zjednodušeným formátem XML dokumentu, kde elementy mohou mít jen pod elementy a atributy. Atribut je textová dvojce klíč, hodnota. API by mělo podporovat jednoduché operace nad XML dokumenty - přidání nového elementu, atributu, výpis elementů. Navrhujete API, součástí nejsou těla metod.
2) Přidejte do API metodu \verb|forEach| s jedním argumentem přijímající lambda výraz a která pro element zavolá lambda výraz na všechny atributy daného elementu, včetně všech pod elementů a jejich atributů. Lambda má dva parametry - atribut a element atributu. Zde píšete i tělo metody.

3 Toky v sítích
1) Definujte pojem maximálního toku.
2) Napište v pseudokódu Fordův-Fulkersonův algoritmus a dokažte, že pro celočíselné hodnocení hran se algoritmus zastaví.
3) Nalezněte tokovou síť, která obsahuje nejvýše deset hran, ale algoritmus provede nalezne postupně alespoň 10000 zlepšujících cest.

4 Databáze (odmítl jsem, takže jen velmi zhruba)
1) Popište množinové operace v relační algebře. Jsou všechny operace nutné, nebo zle některé složit s ostatních?
2) Vysvětlete pojem dvou-fázové zamykání.
3) (Ani jsem nečetl, ale vypadalo to na rozhodnutí uspořadatelnosti a zotavitelnosti nějakých transakcí)

Nevím kolik bylo komisí. V mojí byli čtyři členové (kolegové V. Jelínek, Hladík, Tůma, Bednárek). Informatiku se mnou řešili Tůma a Bednárek, matiku pak Hladík a Jelínek.

V informatice jsem neuměl otázku svého zaměření, na papíře jsem měl blbosti. Tůma s Bednárkem se ze mě snažili něco vydolovat, ale nepodařilo se jim to. Pak mi oznámili, že ostatní otázky mám pěkně zpracované, chtěli řešit jenom drobnosti, ale protože neumím otázku ze svého zaměření, tak mi to nemůžou dát.

V matice mě Hladík hned pokáral, že nemám rád ortogonální doplněk, tak jsem ho ujistil, že ho mám rád, ale ne tolik jako funkce více proměnných. Nenapsal jsem definici totálního diferenciálu, kde jsem jim hned řekl, že to ze mě nedostanou. Ve větě jsem zapomněl dodat, že parc. derivace musí existovat. Příklad jsem neměl dopočítaný, ale bylo naznačené řešení (dosadit kořeny do Hessiánu, ověřit pozitivní/negativní definitnost). Hladík se mě ptal jak zjistím definitnost. Tak jsem mu řekl, že horní trojúhelník musí být kladný/záporný a determinant musí být kladný/záporný. To mi řekl, že není dostatečná podmínka pro větší matice než 2x2. Na subdeterminanty jsem si nevzpomněl. V pravděpodobnosti jsem nepřišel na b) (princip inkluze a exkluze). V teorii grafů, v první úloze jsem Jelínkovi oznámil, že jsem vycházel z nepravdivého tvrzení (nicméně zbytek jsem měl dobře) a dokázal jsem to alternativní cestou. Pak mi řekl, že autor příkladu zadání myslel jinak (já jsem to pochopil jako "Jaké je nejvyšší n, takové, že odebráním n hran už graf nebude souvislý.", ale mělo to být "Kolik nejvíce hran lze odebrat, aby graf pořád byl souvislý". Tak jsem z patra nastřelil první myšlenku co mě napadla a dokázal jí. Jelínek se ptal i na drobnosti. V druhé úloze mi říkal, že úplně nepochopil můj argument, který jsem mu převyprávěl jinak, a uznal mi to. Třetí příklad jsem vůbec neměl (i přesto, že vím co to je a možná bych i naznačil důkaz), jenže jsem to neznal pod názvem Mengerova věta. Jelínek mi sice naznačoval o čem to je, ale vůbec mi to nedošlo v tu chvíli. Pak mě požádali, abych na chvíli odešel, že se poradí na známce. Řekli mi, že každou z otázek mám na dvojku, takže mám dvojku.

Kolega měl poněkud přísnější komisi: Bulej, Sgall a dva, pro něj neznámí. Naznačoval, že na ústní části nebylo moc prostorů pro diskusi a více méně se jen dozvěděl, co měl správně, co ne a dostal známku.

Druhá verze matematiky byla prý hardcore (Lagrange a vázané extrémy).
JS_

Re: 23.6.2016 Matika, Informatika (IPSS)

Příspěvek od JS_ »

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 f(x,y,z)=\sin(x)\sin(y)\sin(z) pro body takové, že x+y+z=\pi/2 a x,y,z>0.

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 (-1)^n, 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 \binom{10}{7}(15/100)^7 (85/100)^3.

2.3 Jak jsem řekl, vytvořující funkce. Označím si polynom p(x)=1+x+x^2+\cdots+x^{50}. Pak hledané číslo je koeficient u x^{100} v polynomu (p(x))^4. 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 0<x,y,z<\pi/2, tak mu vyjde, že x=y=z=\pi/6. 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 x=\frac{k(n-1)}{|E(G)|}. Teď už si jenom spočítám, že |E(G)|=\frac{nd}{2} díky d-regularitě G a dostanu x=\frac{2k(n-1)}{nd}. 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: L=\{ucv\mid u,v\in\{a,b\}^*,u
eq v\}.

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 2\Delta -1, kde \Delta 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 a^{k+1}ca^0,a^{k+1}ca^1,a^{k+1}ca^2,\ldots,a^{k+1}ca^k, těch je k+1, takže existují indexy i<j takové, že a^{k+1}ca^i a a^{k+1}ca^j jsou ve stejné rozkladové třídě ~. Ale potom když k oběma přidám a^{k+1-i} dostanu, že a^{k+1}ca^i.a^{k+1-i}
otin L ale a^{k+1}c^j.a^{k+1-i}\in L, 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?)
adad adadsa

Re: 23.6.2016 Matika, Informatika (IPSS)

Příspěvek od adad adadsa »

Musím souhlasit - matematika byla překvapivě těžká, ale asi je to daný tím, že jsem procházel ukázkový příklady od novějších ke starším a když na to teď koukám, tak mi přijde, že tu matiku dělaj systematicky těžší (jestli je to dobře nebo špatně nehodnotím, ale bylo by dobrý, kdyby ukázkový příklady byly stejný obtížnosti).

Pro srovnání ukázkový příklady z léta 2013 konkrétně 12 a 13:
definice limity funkce a výpočet triviálních limit posloupnosti. Oproti tomu Lagrangeovy multiplikátory a vázaný extrémy, to jsem se ani neučil, protože jsem nabyl dojmu, že v matice dávaj lehký věci. Nakonec jsem to dal na 3.

Informatika mi na druhou stranu přišla stejně obtížná jako ukázkové příklady.

Jinak IPSS:
ráno matika stejná jako v předchozím příspěvku.
odpoledne informatika:
1 Přihrádkové třídění (viz výše)

2 TCP
1) popsat navázání a ukončení spojení a k čemu je three-way hadnshake
2) jak se zajišťuje spolehlivost a flow control
3) popsat význam položek source port, destination port, sequence number, acknowledgement number a window v TCP.

3 Objektově orientované programování (C++, C# nebo Java)
1) Hrubá implementace dynamického pole, které umožňuje přidávat položky na konec, získat počet položek a získat i. položku (tz. jednoduchejt List/vector)
2) co to je iterátor/enumerátor a jak by se to implementovalo
3) přidat do vytvořené třídy metodu Sort, která provede QuickSort a popsat jak bude potřeba upravit zbytek třídy, aby to fungovalo. QuickSort není třeba implementovat, jenom napsat signaturu metody.

4 Procesy a vlákna
to jsem pořádně nečetl, protože jsem to nedělal, ale zkusím aspoň zhruba
1) rozdíl mezi procesem a vláknem a jaký maj u sebe údaje
2) kolik procesů spustí příkaz

Kód: Vybrat vše

ls | head -n 3 > out.txt
3) jak je zajištěno, že může head číst výstup ls
qwerty

Re: 23.6.2016 Matika, Informatika (IPSS)

Příspěvek od qwerty »

abychom se vyhnuli prekvapeni, tak jsem zjistil, ze v zari 2016 budou pisemne statnice probihat trochu jinak - na kazdou cast bude tusim 90 misto 75 minut a budou zadany pouze 3 otazky v kazdem okruhu s tim, ze nepujde skrtat ... good luck
Odpovědět

Zpět na „Bakalářské SZZ“