23.6.2016 Matika, Informatika (IPSS)
Napsal: 23. 6. 2016 18:54
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í .
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
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 s vrcholy označenými (postupně, tedy hrany vedou z do ; ). K tomuto grafu přidáme hrany mezi vrcholy tak, že . Kolik nejvíce lze z grafu odebrat hran tak, aby byl pořád souvislý.
2) Kolik nejvíce vrcholů lze odebrat, aby a 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 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ž . 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šší , takové, že odebráním 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).
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í .
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
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 s vrcholy označenými (postupně, tedy hrany vedou z do ; ). K tomuto grafu přidáme hrany mezi vrcholy tak, že . Kolik nejvíce lze z grafu odebrat hran tak, aby byl pořád souvislý.
2) Kolik nejvíce vrcholů lze odebrat, aby a 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 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ž . 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šší , takové, že odebráním 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).