IOI 21. 6. 2011

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: IOI 21. 6. 2011

Re: IOI 21. 6. 2011

od Návštěvník » 5. 9. 2011 11: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
ot\vdash\phi \Leftrightarrow T,\lnot\phi je bezesporná a tedy má model \Leftrightarrow T
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ů.

Re: IOI 21. 6. 2011

od Germoe » 4. 9. 2011 20: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.

Re: IOI 21. 6. 2011

od aaaaa » 28. 8. 2011 14:44

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

Re: IOI 21. 6. 2011

od aaaaa » 28. 8. 2011 00: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...

Re: IOI 21. 6. 2011

od Yawgmoth » 22. 6. 2011 07: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)

Re: IOI 21. 6. 2011

od QZuzka » 22. 6. 2011 00:21

přijde mi, že to první zadání je o dost těžší než to druhé... podle čeho se přidělovala?

Re: IOI 21. 6. 2011

od otakáro » 21. 6. 2011 15: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í.

IOI 21. 6. 2011

od el enfant » 21. 6. 2011 14: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! :-)

Nahoru