IOI 21. 6. 2011

Vše co se týká bakalářských státních závěrečných zkoušek.

IOI 21. 6. 2011

Příspěvekod el enfant » 21. 6. 2011 13:09

Ahoj, tak jsem si došel pro zadání, tady je:

1. Determinanty
Napište definici determinantu.
Nechť matice B typu n \times n vznikne z matice A typu n \times n přenásobením každého prvku konstantou c a výměnou prvního a posledního řádku. Jaká bude hodnota det(B) vzhledem k hodnotě det(A)?
Udejte podmínky, za kterých existuje ke čtvercové matici inverzní matice a popište vztah mezi jejich determinanty. Popište, jak s pomocí determinantu spočítáte inverzní matici k dané matici, pokud existuje.

2. Pravděpodobnost a statistika
Definujte pojem střední hodnoty reálné náhodné veličiny.
Vyslovte a dokažte větu o linearitě střední hodnoty.
Platí analogie této věty pro součin náhodných veličin, tedy platí \mathbb{E}(X\cdot Y) = \mathbb{E}(X) \cdot \mathbb{E}(Y)?

3. Základy diferenciálního počtu
Definujte Taylorův polynom.
Vyslovte větu o zbytku Taylorova polynomu.
Vypočtěte Taylorovu řadu pro funkci sin(x).

4. Logika
Zformulujte větu o existenci modelu a dokažte pomocí ní tvrzení: je-li T nějaká L-teorie a \phi je L-sentence, tak T \models \phi \Rightarrow T \vdash \phi.

5. Algoritmy a datové struktury
Napište pseudokód rekurzivní verze algoritmu pro prohledávání do hloubky na orientovaném grafu. Stačí jednoduchá verze neprovádějící klasifikaci hran. Zdůvodněte, jaká je asymptotická časová složitost tohoto algoritmu pro graf s n vrcholy a m hranami.
Doplňte pseudokód tak, aby rozhodl, zda je vstupní graf acyklický.
Napište definici topologického očíslování vrcholů orientovaného grafu. Pak doplňte pseudokód tak, aby jeho výstupem bylo i topologické očíslování vrcholů, pokud takové existuje.

6. Architektury počítačů a sítí
Daný procesor používá 32-bitovou architekturu a dvouúrovňové stránkování.
Instrukce MOV[0x12345678], EAX zapisuje obsah registru EAX na adresu 0x12345678.
Popište, jaká operace (přístupy do registrů a podobně) vykonává při provádění této instrukce procesor a jak při tom spolupracuje operační systém. Rozeberte všechny možné (z hlediska naplnění stránkovacích tabulek) případy, nepopisujte strategie výměny stránek.

Přišlo mi to docela jednoduché, kdybych se na to měl čas podívat a neabsolvoval bakalářské předměty tak dávno, tak by to mělo jít.

Držím ještě palce! :-)
el enfant
Matfyz(ák|ačka) level I
 
Příspěvky: 38
Registrován: 31. 1. 2006 17:14
Typ studia: Informatika Bc.

Re: IOI 21. 6. 2011

Příspěvekod otakáro » 21. 6. 2011 14:56

Přidám svoje zadání:
(Taky IOI ale ještě podle starších požadavků - pro ty co zahájili v roce 2007)

1. Limity
1.1 Definujte pojem limity funkce v bodě
2.1 Určete limitu funkcí sin(1/(x-1)) a (x-1)*sin(1/(x-1)) v bodě 1

2.Matice
2.1 Definujte pojmy řádkový prostor, sloupcový prostor a jádro matice
2.2 Jaké platí vztahy mezi dimenzemi těchto prostorů a hodností matice?
2.3 Existuje nad libovolným tělesem matice velikosti 3x3, která má dimenzi jádra 2? (Uveďte příklad nebo dokažte, že neexistuje)

3.Grafy
3.1 Definujte pojem barevnost grafu
3.2 Popište jak souvisí barevnost s těmito atributy grafu : počet vrcholů, klikovost, nezávislost, degenerovanost, rovinnost

4.Jazyky
4.1 Popište Chomského hierarchii tříd jazyků, jak se nazývají jazyky v každé třídě, jaký typ gramatiky je generuje a jaký typ automatu je přijímá.
4.2 Uveďte příklad neregulárního jazyka a ukažte, že není regulární.
4.3 Existuje uzávěrová vlastnost, na kterou nejsou uzavřené jazyky typu 0?

5.Databáze
5.1 Co je to relační algebra a jaké operace používá?
5.2 U každé operace popište schéma relace, na které se dá tato operace použít a definujte výsledek operace.
5.3 Jsou všechny operace nezbytné pro zachování vyjadřovací síly jazyka? (Pokud ne, které jsou?)
5.4 Čemu odpovídá operace přirozené spojení na relacích, které mají totožné schéma?
5.5 Čemu odpovídá operace přirozené spojení na relacích, jejichž schémata jsou disjunktní?

6.Generika
6.1 Co je to generické programování, k čemu se používá a v čem spočívají jeho výhody?
6.2 Napište stručnou implementaci generické třídy List nebo HashTable.

Na přípravu je 2,5 hodiny, pak asi 45 minut čekáte než to opraví (během té doby musíte zůstat v učebně, neměli byste s nikým mluvit ani se dívat do skript, používat mobil a podobně - i když u nás to zas tak přísně nebral) pak následuje ustní (u mě bez otázek za 1 :D )

Pokud vás to teprve čeká tak přeju hodně štěstí.
otakáro
 

Re: IOI 21. 6. 2011

Příspěvekod QZuzka » 21. 6. 2011 23:21

přijde mi, že to první zadání je o dost těžší než to druhé... podle čeho se přidělovala?
QZuzka
Matfyz(ák|ačka) level III
 
Příspěvky: 209
Registrován: 2. 12. 2007 19:51
Bydliště: Praha 4
Typ studia: Informatika Mgr.

Re: IOI 21. 6. 2011

Příspěvekod Yawgmoth » 22. 6. 2011 06:01

druhé zadání bylo pro ty co studují déle :-) (začátek 2007 a dřív)

já jsem měl taky tohle zadání "pro starší", ale obor IP .. a přišlo mi to snad ještě jednodušší, tenhle termín se jim docela povedl, asi se nás už chtěli zbavit :-)

(místo limit Konvergence řad (taky definice + určit u tří konkrétních, 1/n, 1/n2, (sin n) / n), místo matic Princip inkluze a exkluze s jednoduchým příkladem (kolik přirozených čísel <= 1000 je dělitelných 3, 5, nebo 7) a důkaz pro 3 množiny, Grafy stejná otázka na barevnost, místo jazyků definovat zámek a podmíněnou proměnnou + implementovat producenta/konzumenta, místo databází definovat B-strom, operaci vkládání a porovnat rozdíl mezi ním a binárním stromem pro indexaci na vnější paměti ... a generika zase stejná, teda bylo tam ještě napsat srovnání jejich implementace v C++ a Java)
Uživatelský avatar
Yawgmoth
Matfyz(ák|ačka) level I
 
Příspěvky: 24
Registrován: 17. 5. 2007 19:09
Typ studia: Informatika Mgr.

Re: IOI 21. 6. 2011

Příspěvekod aaaaa » 27. 8. 2011 23:30

otakáro píše:Přidám svoje zadání:
(Taky IOI ale ještě podle starších požadavků - pro ty co zahájili v roce 2007)

5.Databáze
5.1 Co je to relační algebra a jaké operace používá?
5.2 U každé operace popište schéma relace, na které se dá tato operace použít a definujte výsledek operace.
5.3 Jsou všechny operace nezbytné pro zachování vyjadřovací síly jazyka? (Pokud ne, které jsou?)
5.4 Čemu odpovídá operace přirozené spojení na relacích, které mají totožné schéma?
5.5 Čemu odpovídá operace přirozené spojení na relacích, jejichž schémata jsou disjunktní?



no nic v zlom, ale to akoze do akeho okruhu spada relacna algebra z tych, ktore su vypisane na stranke mff? tu su okruhy pre tych co zahajili studium do 2007, obor IP, ostatne obory tvoria co sa tyka databazovych otazok len podmnozinu tychto:
http://www.mff.cuni.cz/studium/bcmgr/ok/i3a32x.htm

konkretne sekcia:

3. Databáze
Architektury databázových systémů. Konceptuální, logická a fyzická úroveň pohledů na data. Algoritmy návrhu schémat relací, normální formy, referenční integrita. Transakční zpracování, vlastnosti transakcí, uzamykací protokoly, zablokování. ER-diagramy, metody návrhů IS. SQL. Indexy, triggery, uložené procedury, uživatelé, uživatelská práva. Vícevrstevné architektury. Vazba databází na internetové technologie. Organizace dat na vnější paměti, B-stromy a jejich varianty. Technologie XML. XML Schema, XSLT, XQuery a jejich použití.



na zaklade tohto zoznamu by som sa teda ja osobne veci ako relacny kalkul ci relacna algebra urcite neucil...
aaaaa
 

Re: IOI 21. 6. 2011

Příspěvekod aaaaa » 28. 8. 2011 13:44

ok nic, IOI to ma v tych okruhoch, jaksi som to len prehliadol
aaaaa
 

Re: IOI 21. 6. 2011

Příspěvekod Germoe » 4. 9. 2011 19:38

el enfant píše:Ahoj, tak jsem si došel pro zadání, tady je:
4. Logika
Zformulujte větu o existenci modelu a dokažte pomocí ní tvrzení: je-li T nějaká L-teorie a \phi je L-sentence, tak T \models \phi \Rightarrow T \vdash \phi.


Neprozradil by mi někdo řešení? 0:-)
Dík.
Germoe
Matfyz(ák|ačka) level I
 
Příspěvky: 34
Registrován: 28. 5. 2008 14:40
Typ studia: Informatika Ph.D.

Re: IOI 21. 6. 2011

Příspěvekod Návštěvník » 5. 9. 2011 10:30

Germoe píše:
el enfant píše:Ahoj, tak jsem si došel pro zadání, tady je:
4. Logika
Zformulujte větu o existenci modelu a dokažte pomocí ní tvrzení: je-li T nějaká L-teorie a \phi je L-sentence, tak T \models \phi \Rightarrow T \vdash \phi.


Neprozradil by mi někdo řešení? 0:-)
Dík.


Požadovaná věta bude nejspíš "Každá bezesporná teorie má model (i nějaký velikosti nejvýše |L(T)|)". A důkaz toho tvrzení už pak plyne snadno: T
<br />ot\vdash\phi \Leftrightarrow T,\lnot\phi je bezesporná a tedy má model \Leftrightarrow T
<br />ot\models\phi. Jen kdyby tam nebyla sentence ale formule s volnými proměnnými, tak se ještě musí uzavřít pomocí kvantifikátorů.
Návštěvník
 


Zpět na Bakalářské SZZ

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků

cron