Tak já přihodím
IOI a
IP (stejná zadání v tomto termínu) a zkusím rozvést co si pamatuju:
1. Polynomy
Co platí o kubickém polynomu s reálnými koeficienty (u všeho je nutno zdůvodnit):
- má alespoň jeden a nejvýš tři komplexní kořeny
- má min. jeden reálný kořen
- má-li reálný kořen, pak je dvojnásobný
- má-li dva reálné kořeny, pak jeden z nich je dvojnásobný
-
tady už si bohužel nevzpomínám, možná mě někdo doplní
2. K-souvislost grafů
- definujte hranovou a vrcholovou k-souvislost grafu (jako jeho vlastnost)
- znění věty o k-souvislosti a počtu disjunktních cest mezi dvěma vrcholy
- dokažte, že je-li graf 3-regulární a hranově k-souvislý, pak je i vrcholově k-souvislý
3. Jordanova normální forma
- uveďte nutnou a postačující podmínku pro to, aby Jordanova normální forma matice byla diagonální
- najděte Jordanovu normální formu matice
1 0 0 3
0 1 0 0
0 0 2 0
0 0 0 2
4. Derivace funkce
- definujte derivaci funkce jedné reálné proměnné
- uveďte souvislost mezi derivací a tečnou ke grafu funkce
- formulujte Lagrangeovu větu o střední hodnotě
- uveďte větu o souvislosti monotonie v bodě s první derivací a naznačte důkaz pro jeden z případů
- najděte intervaly, na nichž je funkce xe^(-x) rostoucí a klesající
5. MergeSort
- napište v pseudokódu třídící algoritmus MergeSort
- uveďte jeho časovou složitost v průměrném a nejhorším případě
- diskutujte stabilitu vašeho algoritmu
6. Stránkování
32bit architektura, dvouúrovňová stránkovací tabulka, každá úroveň obsahuje 1024 položek
- virtuální adresa 12A34BCD, rozdělte ji na jednotlivé indexy a offset do stránky
- nakreslete obsah stránkovací tabulky obsahující překlad výše uvedené virtuální adresy na fyzickou adresu 1234ABCD, uveďte přesný obsah všech položek, jež budou přečteny procesorem při překladu této adresy (neuvedené položky vhodně doplňte)
- popsaná architektura používá cache s velikostí bloku 64B, je problém uložit 4B proměnnou na výše uvedenou virtuální adresu ve virtuálním adresním prostoru procesu?
Tady jsem moc nechápal, co po nás chtěli, patrně šlo o to zjistit, zda by daná proměnná neležela na rozhraní dvou bloků v cache.
7. Automaty a gramatiky
Dán jazyk L = {0^(n)1^(n), n z N}
- najděte pro tento jazyk gramatiku
- do které úrovně Chomského hierarchie nalezená gramatika patří?
- najděte automat odpovídající kategorie přijímající tento jazyk
- formálně definujte použitou kategorii automatu
8. Objektově orientované programování
Níže uvedené fragmenty kódu byly v zadání napsány v Javě, C++ a C#, aby nebyl nikdo znevýhodněn. Já se pokusím zrekonstruovat C# variantu.
Kód: Vybrat vše
public class A { public virtual void M() {Console.WriteLine("A::M");} }
public class B : A { public override void M() {Console.WriteLine("B::M");} }
A a = new A(); B b = new B(); A ab = new B();
a.M(); b.M(); ab.M();
- jaký bude výpis tohoto fragmentu kódu?
- uvažujte, že k předchozímu kódu přibudou navíc následující definice, změní se nějak výstup?
Kód: Vybrat vše
public class A { public A() {Console.WriteLine("A");} }
public class B { public B() {Console.WriteLine("B");} }
- jak bude vypadat výstup, přidáme-li na konec těchto metod (
myšleno konstruktory, bylo to tam nějak provázané odkazy typu "Fragment č. 3", aby to nemuseli přímo nazývat konstruktorem) volání metody M()?
Moje komise byla výborná, ve složení Fiala, Hric, Kopecký a jeden člověk, jemuž bohužel nemohu přijít na jméno
. Skvělé bylo že vůbec neřešili detaily (chybějící plusy a mínusy, ostré a neostré nerovnosti) a zajímalo je jen porozumění tématu. Nakonec to bylo všechno celkem v klidu, takže hodně štěstí dalším generacím!
Tak já přihodím [b]IOI[/b] a [b]IP[/b] (stejná zadání v tomto termínu) a zkusím rozvést co si pamatuju:
[b]1. Polynomy[/b]
Co platí o kubickém polynomu s reálnými koeficienty (u všeho je nutno zdůvodnit):
- má alespoň jeden a nejvýš tři komplexní kořeny
- má min. jeden reálný kořen
- má-li reálný kořen, pak je dvojnásobný
- má-li dva reálné kořeny, pak jeden z nich je dvojnásobný
- [i]tady už si bohužel nevzpomínám, možná mě někdo doplní[/i]
[b]2. K-souvislost grafů[/b]
- definujte hranovou a vrcholovou k-souvislost grafu (jako jeho vlastnost)
- znění věty o k-souvislosti a počtu disjunktních cest mezi dvěma vrcholy
- dokažte, že je-li graf 3-regulární a hranově k-souvislý, pak je i vrcholově k-souvislý
[b]3. Jordanova normální forma[/b]
- uveďte nutnou a postačující podmínku pro to, aby Jordanova normální forma matice byla diagonální
- najděte Jordanovu normální formu matice
1 0 0 3
0 1 0 0
0 0 2 0
0 0 0 2
[b]4. Derivace funkce[/b]
- definujte derivaci funkce jedné reálné proměnné
- uveďte souvislost mezi derivací a tečnou ke grafu funkce
- formulujte Lagrangeovu větu o střední hodnotě
- uveďte větu o souvislosti monotonie v bodě s první derivací a naznačte důkaz pro jeden z případů
- najděte intervaly, na nichž je funkce xe^(-x) rostoucí a klesající
[b]5. MergeSort[/b]
- napište v pseudokódu třídící algoritmus MergeSort
- uveďte jeho časovou složitost v průměrném a nejhorším případě
- diskutujte stabilitu vašeho algoritmu
[b]6. Stránkování[/b]
32bit architektura, dvouúrovňová stránkovací tabulka, každá úroveň obsahuje 1024 položek
- virtuální adresa 12A34BCD, rozdělte ji na jednotlivé indexy a offset do stránky
- nakreslete obsah stránkovací tabulky obsahující překlad výše uvedené virtuální adresy na fyzickou adresu 1234ABCD, uveďte přesný obsah všech položek, jež budou přečteny procesorem při překladu této adresy (neuvedené položky vhodně doplňte)
- popsaná architektura používá cache s velikostí bloku 64B, je problém uložit 4B proměnnou na výše uvedenou virtuální adresu ve virtuálním adresním prostoru procesu?
[i]Tady jsem moc nechápal, co po nás chtěli, patrně šlo o to zjistit, zda by daná proměnná neležela na rozhraní dvou bloků v cache.[/i]
[b]7. Automaty a gramatiky[/b]
Dán jazyk L = {0^(n)1^(n), n z N}
- najděte pro tento jazyk gramatiku
- do které úrovně Chomského hierarchie nalezená gramatika patří?
- najděte automat odpovídající kategorie přijímající tento jazyk
- formálně definujte použitou kategorii automatu
[b]8. Objektově orientované programování[/b]
[i]Níže uvedené fragmenty kódu byly v zadání napsány v Javě, C++ a C#, aby nebyl nikdo znevýhodněn. Já se pokusím zrekonstruovat C# variantu.[/i]
[code]public class A { public virtual void M() {Console.WriteLine("A::M");} }
public class B : A { public override void M() {Console.WriteLine("B::M");} }
A a = new A(); B b = new B(); A ab = new B();
a.M(); b.M(); ab.M();[/code]
- jaký bude výpis tohoto fragmentu kódu?
- uvažujte, že k předchozímu kódu přibudou navíc následující definice, změní se nějak výstup?
[code]public class A { public A() {Console.WriteLine("A");} }
public class B { public B() {Console.WriteLine("B");} } [/code]
- jak bude vypadat výstup, přidáme-li na konec těchto metod ([i]myšleno konstruktory, bylo to tam nějak provázané odkazy typu "Fragment č. 3", aby to nemuseli přímo nazývat konstruktorem[/i]) volání metody M()?
Moje komise byla výborná, ve složení Fiala, Hric, Kopecký a jeden člověk, jemuž bohužel nemohu přijít na jméno :(. Skvělé bylo že vůbec neřešili detaily (chybějící plusy a mínusy, ostré a neostré nerovnosti) a zajímalo je jen porozumění tématu. Nakonec to bylo všechno celkem v klidu, takže hodně štěstí dalším generacím!