2014-06-23

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

2014-06-23

Příspěvekod       » 23. 6. 2014 12:30

vlastnosti kubického polynomu
- kolik má jakých kořenů a proč (ZVA + intuice o tom, jak vypadá který graf, násobné reálné vs. komplexní kořeny)

souvislost grafů
- k-souvislost vs. k+1 disjunktnich cest, vsude rozdily mezi vrcholovou/hranovou
- 3-regulárni graf - dokázat věci o vrcholové/hranové k-souvislosti

jordanův tvar s vlastníma číslama
- formulovat větu, kdy je ta matice diagonální (nevěděl jsem ani, co měly znamenat ty 1čky nad diagonálou)
- spočítat něco

derivace
- definice, vyjádření tečny ke grafu, monotonie, lagrangeova veta o střední hodnotě
- vyšetřit x/e^x

jazyk 0^n 1^n (n \in \NN)
- zařadit a dokázat, proč zrovna tak (Myhill-Nerode)
- definovat danou gramatiku i automat a nakreslit oboje

mergesort
- složitost, kód, stabilita

stránkování
- 'nuff said. naučte se počítat v hex, jinak na tom zabijete čas.

DNS
- co všechno se děje, když klient udělá požadavek (a cache po cestě jsou prázdné)
- reverzy (IPv4/v6, včetně triku s delegací podčásti 128/25 IN NS...)
- co se děje mezi autoritativníma

Nic na jednom z papírů ještě neznamená, že vyletíte. Ale musíte to vyvážit zbytkem. Prý "v rozumné míře".
Porota: Pangrác, Parízek, Šámal, Tůma. There is a God.
     
 

Re: 2014-06-23

Příspěvekod ips » 23. 6. 2014 16:52

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!
Naposledy upravil ips dne 24. 6. 2014 01:19, celkově upraveno 1
ips
Matfyz(ák|ačka) level I
 
Příspěvky: 11
Registrován: 10. 9. 2011 19:18
Typ studia: Informatika Bc.

Re: 2014-06-23

Příspěvekod success » 23. 6. 2014 17:26

ips píše:Tak já přihodím IOI a IP (stejná zadání v tomto termínu) a zkusím rozvést co si pamatuju:


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()?


Len doplnim, ze nie je to tak uplne jedno, lebo C# a Java maju virutalne aj konstruktry, ale C++ nema. Preto bola volba jazyka vcelku dolezita.
success
 

Re: 2014-06-23

Příspěvekod Návštěvník » 23. 6. 2014 17:46

Je to jedno, protože u C++ ty konstruktory virtuální byly. Každopádně to říkala i komise, že je to jedno (důkaz autoritou :))
Návštěvník
 

Re: 2014-06-23

Příspěvekod nahodny kolemjdouci » 23. 6. 2014 20:58

Ad 6 Ty adresy meli shodny offset(posledni tri znaky v 16) jinak by preklad nedaval smysl. Jen aby to nekoho nematlo... K te posledni uloze jsem napsal ze cache je zcela irelevantni, jde jen o to zdali se ta pozadovana pamet (4 byte) vleze do fyzickeho ramce za dany offset a k tomu nemeli vyhrad. Jen se nejak dal vyptavali a kdyz jsem jim rekl ze teda ten offset neni zarovnan na 4 byte coz by nekterym architekturam mohlo vadit tak dali pokoj :).

Ad 8 Nevim co teda myslite "virtualnim konstruktorem". V zasade jde o to jestli virtualni funkce volana z konstruktoru predka se zavola na predkovi ci potomkovi. Ja resil ulohu pro Javu kde je(Hnetynkou odsouhlaseno) volana metoda potomka. Hnetynka se vyptaval jestli to bude stejne v c++ tak jsem rekl ze nikoli ze tam se zavola ta metoda predka. Podle Hnetynky spravna odpoved. Jak je to u C# nevim.
nahodny kolemjdouci
 

Re: 2014-06-23

Příspěvekod ips » 24. 6. 2014 01:22

nahodny kolemjdouci píše:Ad 6 Ty adresy meli shodny offset(posledni tri znaky v 16) jinak by preklad nedaval smysl. Jen aby to nekoho nematlo... K te posledni uloze jsem napsal ze cache je zcela irelevantni, jde jen o to zdali se ta pozadovana pamet (4 byte) vleze do fyzickeho ramce za dany offset a k tomu nemeli vyhrad. Jen se nejak dal vyptavali a kdyz jsem jim rekl ze teda ten offset neni zarovnan na 4 byte coz by nekterym architekturam mohlo vadit tak dali pokoj :).

Ad 8 Nevim co teda myslite "virtualnim konstruktorem". V zasade jde o to jestli virtualni funkce volana z konstruktoru predka se zavola na predkovi ci potomkovi. Ja resil ulohu pro Javu kde je(Hnetynkou odsouhlaseno) volana metoda potomka. Hnetynka se vyptaval jestli to bude stejne v c++ tak jsem rekl ze nikoli ze tam se zavola ta metoda predka. Podle Hnetynky spravna odpoved. Jak je to u C# nevim.


Díky za upozornění, ty adresy už si přesně nepamatuju, tak jsem to trochu upravil aby to už smysl dávalo :). Jinak k té 8, když jsem to četl, vůbec mě nenapadlo, že bude záležet na volbě jazyka, prostě jsem si vybral ten svůj a napsal odpovědi pro něj (aniž bych vůbec uvedl, který jsem si vybral!).
ips
Matfyz(ák|ačka) level I
 
Příspěvky: 11
Registrován: 10. 9. 2011 19:18
Typ studia: Informatika Bc.


Zpět na Bakalářské SZZ

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron