IOI 05.02.2015

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 05.02.2015

Re: IOI 05.02.2015

od Sharduk » 6. 2. 2016 11:11

A ještě odpovědi na matiku:

1.
  • a) Z |E| <= 3|V| - 6 pro grafu obsahující trojúhelník a |E| <= 2|V| - 4 pro grafy bez trojúhelníku. Napsal jsem, že pro rovinné triangulace teda počet hran je mezi, ale prý se dá ukázat, že se rovná té horní hranici.
    b) Indukcí. Vezmu si normální trojúhelník, ten je určitě rovinnou triangulací. Vložím do něj vrchol a ten spojím se všemi původními vrcholy -> trojúhelník se mi rozdělí na tři a zase mám rovinnou triangulaci (nejde to nakreslit rovinně jinak). No a do nově vzniknuvších trojúhelníků můžu zase vkládat vrcholy a pokračovat do nekonečna.
    c)

    Kód: Vybrat vše

    |E| <= 3|V| - 6
    kn/2 <= 3n - 6
    k <= 6 - 12/n
    k < 6
    Prý by bylo hezké ukázat, že k může být 5. Toto nám pouze říká, že 6 být už nemůže. (Pro 4 se dá nakreslit lehce, pro 5 musí mít min 12 vrcholů)
2.
  • a) Polynom stupně alespoň 1, který není součinem polynomů nižších stupňů.
    b) x4 - 1 = (x2 - 1)(x2 + 1) = (x2 + 1)(x + 1)(x - 1) -> dál nejde, protože i neni v Q[x]
    c) x4 - 1 = (x2 - 1)(x2 + 1) = (x - 1)(x + 1)(x2 - 4) = (x - 1)(x + 1)(x - 2)(x + 2) = (x + 4)(x + 1)(x + 3)(x + 2) pro Z5[x]
    d) x2 + x + 1 -> (x2 je jen zkrácený zápis x*x)
3.
  • a) Snad znáte..
    b) První neplatí (např. pro x3). Druhé jen z části, derivace také nemusí být v tom bodě definovaná (to jsem přehlíd)
    c) Extrémy vyšly myslím v 0 minimum a ve 2 maximum.
4. (škrtal jsem -> výsledky neověřené)
  • a) Ker(ƒ) = {u| u € U, ƒ(u) = 0}
    b) Báze jádra mi vyšla {(0,0,0,0,a,b) | a,b € R}. Báze obrazu pak třeba {(1,0,0,0,0,0), (0,1,0,0,0,0), (0,0,1,0,0,0), (0,0,0,1,0,0)
    c) To jsem tipoval, ale nevím.}

IOI 05.02.2015

od Sharduk » 6. 2. 2016 10:54

Ahoj. Tady je pár otázek z posledního termínu (IOI, nástup 2011):

Informatika:
1. Diskrétní fourierova transformace
  • a) Definujte DFT.
    b) Najděte obraz vektoru (1, 0, -1, 0)
    c) Jaká je složitost FFT?
    d) Co je inverzí k DFT?
2. Relační algebra (s nějakými zadefinovanými relacemi pro daný příklad)
  • a) Definujte základní operace nad relační algebrou (je jich 7, selekce, projekce, etc..)
    b) Jak byste vybrali ID plodiny, která ještě nebyla pěstována?
    c) Jak byste vybrali pole o velikosti větší než jeden hektar, na kterých se pěstovala pšenice?
3. Procesory
  • a) Definujte jaké základní operace musí minimálně procesor podporovat (nemusíte uvádět přesné názvy, ale pár příkladů by bylo dobrých) (lw, sw, jump, etc).
    b) Jaké má procesor registry? (opět nemusíte uvádět přesné názvy, ale příklad by byl dobrý)
    c) Jak byste v assembleru napsali za vámi výše definovaných operací následující část kódu z vysokoúrovňového programovacího jazyka? (všechny proměnné jsou globální, jejich adresu si libovolně zvolte)

    Kód: Vybrat vše

    if (a + b == 0) a = b; else b = a;
4. Automaty
  • a) Definujte zásobníkový automat.
    b) Do jaké Chomského hierarchie patří jazyk {ww^r | w € {a,b}*}? Dokažte. (Tady mi bylo lehce vytknuto, že jsme nedokázal, že nepatří do L3)
Matematika:
1. Rovinná triangulace
  • Info: O grafu řekneme, že je rovinnou triangulací, pokud pro libovolné (každé - pozn. aut.) jeho rovinné nakreslení jsou všechny jeho stěny trojuhelníkem.
    a) Uveďte horní obecný odhad počtu hran pro rovinné grafy. Je možné lépe určit toto číslo pro rovinné triangulace?
    b) Dokažte, že pro n >= 3 existuje rovinná triangulace právě na n vrcholech.
    d) Pro jaké k existuje rovinný graf se všemi vrcholy stupně k?
2. Ireducibilní polynomy
  • a) Definujte pojem ireducibilní polynom.
    b) Najděte rozklad polynomu x4 - 1 na ireducibilní polynomy v Q[x].
    c) Najděte rozklad polynomu x4 - 1 na ireducibilní polynomy v Z5[x]
    d) Najděte ireducibilní polynom stupně dva v Z2[x].
3. Derivace a extrémy funkce
  • a) Definujte pojem derivace funkce v bodě.
    b) Která z následujících tvrzení jsou pravdivá?
    • i) Pokud ƒ'(a) = 0, pak má funkce ƒ v bodě a minimum nebo maximum.
      ii) Pokud má funkce ƒ v bodě a minimum nebo maximum, pak ƒ'(a)=0.
    c) Nalezněte extrémy funkce x2e-x
4. Lineární zobrazení
  • a) Definujte pojem jádra linearního zobrazení ƒ: U -> V.
    b) Mějme nad tělesem polynomů max. stupně 5 zobrazení ƒ: U->V druhých derivací. Najděte bázi jádra ƒ a bázi obrazu ƒ.
    c) Spočítejte hodnost matice zobrazení ƒ vůči bázi 7, x, x2 - x, 3x3 - 2, x4 - x2, x5 + 3. (Ty hodnoty byly trochu jinak)
Komise byla neuvěřitelně hodná (vím, že to asi při přípravě všude čtete a nevěříte, nebo tak, ale pochopíte, až tam budete :D) a snažila se, aby člověk na ústním něco vymyslel. Apeluju na vás, NIKDY, ale NIKDY neodcházejte před prvním rozhodnutím z ústního. Byť si můžete řikat, že neumíte nic, tak na ten papír radši napište největší kravinu, protože pak se můžete s komisí bavit. Já jsem si po obdržení zadání byl jistej, že to dneska nevyjde a chtěl se slzou na krajíčku odejít. Nakonec jsem si řek, že tam zůstanu, a napíšu aspoň něco, co si pamatuju. DFT jsem škrtnul, poprvý v životě jsem psal něco v assembleru, selekční algebra byla naprosto tristní (automaty jsem měl dobře). Komise se mě na všechno možný ptala a vytahovala ze mě i věci, který jsem netušil, že tuším. K mému údivu mě pustili do další části, kde jsem matiku dal v pohodě, a nakonec se budu řadit mezi absolventy :D 4,5 roku se vyplatilo!

Úspěšnost odhadem ~ 60% (kombinace DFT a Relační algebry byla vražedná), bylo nás tam 11.

Takže pro příští generace:
  • 1) Nikdy neházejte flintu do žita.
    2) Radši na papír napište i (podle vás, třeba se mýlíte) největší bulšit, než ho nechávat prázdnej.
    3) Nevím jak ostatní, ale já jsem nechápal, jak ta komise byla hodná. (Lokoč, Ježek, Skopal, Mareš, Majerech)
Hodně štěstí!

P.S.: Taky jsme chtěli pustit pejska a kočičku, a nakonec jsme dostali večerníček bez zvuku :D

Nahoru