IP 21.6.2011

Vše co se týká bakalářských státních závěrečných zkoušek.
steves
Matfyz(ák|ačka) level I
Příspěvky: 33
Registrován: 13. 12. 2008 16:29
Typ studia: Informatika Bc.

IP 21.6.2011

Příspěvek od steves »

1. 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)?

2. Algebra
Vypsat všechny podgrupy grupy S_3 (grupa permutací na 3 prvcích) a jejich index.
Definovat index podgrupy a vyslovit větu o vztahu velikosti grupy, její podgrupy a indexu (to měla být Lagrangeova věta).

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. Jazyky a automaty
Ukažte, že následující gramatika G je víceznačná S \rightarrow if\, then\, S\, else\, S\, | if\, then\, S\, | \lambda
Vytvořte gramatiku G', která nebude víceznačná, a bude platit L(G) = L(G').
Existuje obecně k libovolné bezkontextové gramatice G jednoznačná gramatika G' taková, že L(G) = L(G')?

5. Generika a šablony
Co je to generické programování, k čemu se používá a v čem spočívají jeho výhody?
Napište stručnou implementaci generické třídy List nebo HashTable.
Popište implementaci v C++ a Javě (asi by stačil i C#, ale v zadání byla explicitně napsaná java).

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.

Otázky mi sedly, ale stejně jsem nevěřil, že to půjde tak hladce. Nicméně, když jsem přišel před komisi, oznámili mi, že si ani nemám sedat, že se jim to líbilo a že není co řešit, což mi vyrazilo dech. Čekal jsem, že budou rejpat do poslední otázky, ale byli úplně v pohodě, dokonce mi řekli, že odpověď na poslední otázku se jim líbila nejvíc.
GR

Re: IP 21.6.2011

Příspěvek od GR »

My z IP, ktory sme zacali studium v rok 2007 a skor, sme mali:
(Pametam si len zhruba)

1. Konvergence rad.
Napiste definici konvergence rad.
Rozhodnete a zduvodnete, zda konverguji rady: 1/n, 1/n^2, sin(n)/n

2. Barevnost grafu
Popiste barevnost grafu.
Co plyne z barevnosti grafu (pocet vrcholu, nezavislost, klika, degenerovanost grafu, rovinne grafy ... a este volaco)

3. PIE
Napiste princip inkluze a exkluze.
Dokazte (staci dukaz na 3 mnozinach)

4. zamky
Napiste program, ktery resi problem producenta a konzumenta z pasivnim cekanim. (alebo nieco take)

5. Genericke programovani
Popiste sablony
Jak jsou implementovany (popiste jak jsou implementovany v C++ nebo Java) (to som teda fakt netusil)

6. B-stromy
Popiste B-stromy.
Porovnejte rychlost B-stromu s binarnim vyhledavacim stromem, ktere jsou ulozeny v sekundarni pameti.
el enfant
Matfyz(ák|ačka) level I
Příspěvky: 38
Registrován: 31. 1. 2006 17:14
Typ studia: Informatika Bc.

Re: IP 21.6.2011

Příspěvek od el enfant »

steves píše:Otázky mi sedly, ale stejně jsem nevěřil, že to půjde tak hladce. Nicméně, když jsem přišel před komisi, oznámili mi, že si ani nemám sedat, že se jim to líbilo a že není co řešit, což mi vyrazilo dech
Jen dotaz - tam, kde to nebylo explicitne zadano, jsi zadne dukazy navic nepsal? (Takze jen ta linearita stredni hodnoty?) Diky..
steves
Matfyz(ák|ačka) level I
Příspěvky: 33
Registrován: 13. 12. 2008 16:29
Typ studia: Informatika Bc.

Re: IP 21.6.2011

Příspěvek od steves »

el enfant píše:
steves píše:Otázky mi sedly, ale stejně jsem nevěřil, že to půjde tak hladce. Nicméně, když jsem přišel před komisi, oznámili mi, že si ani nemám sedat, že se jim to líbilo a že není co řešit, což mi vyrazilo dech
Jen dotaz - tam, kde to nebylo explicitne zadano, jsi zadne dukazy navic nepsal? (Takze jen ta linearita stredni hodnoty?) Diky..
Přesně tak. Napsal jsem důkaz střední hodnoty pro spojitý případ (jeden řádek :-)) a u jednoho z těch "=" jsem napsal poznámku "plyne z linearity integrálu". To jim stačilo a na víc se u ústní neptali. Asi by to vypadalo jinak, kdybych u druhé matematické otázky neměl vůbec nic a tohle by pro ně byla jediná možnost, jak ze mě dostat alespoň něco, za co by mi dali trojku...
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: IP 21.6.2011

Příspěvek od marion »

steves píše: Čekal jsem, že budou rejpat do poslední otázky, ale byli úplně v pohodě, dokonce mi řekli, že odpověď na poslední otázku se jim líbila nejvíc.
Mohl bys prosím stručně napsat, jak vypadá odpověď na tu poslední otázku, která se nejvíc líbila? :)
steves
Matfyz(ák|ačka) level I
Příspěvky: 33
Registrován: 13. 12. 2008 16:29
Typ studia: Informatika Bc.

Re: IP 21.6.2011

Příspěvek od steves »

marion píše: Mohl bys prosím stručně napsat, jak vypadá odpověď na tu poslední otázku, která se nejvíc líbila? :)
Měl jsem to rozepsané na celý ten papír (takže 2xA4). Co tam tak zhruba bylo:

- procesor se podívá na registr PC, vyzvedne další instrukci (tzv. fetch fáze)
- instrukce je dekódována v řadiči (tzv. decode fáze)
- řadič podle kódu instrukce nastaví vodiče na datové cestě
- vykonává se instrukce
- registr PC += velikost instrukce
- goto 1

během toho, kdykoliv se přistupuje do paměti, může vzniknout page-fault (načítání instrukce a potom ta adresa u instr. mov). U toho jsem popsal jak stránkování funguje. Že je typicky víceúrovňové, nejvyšší úroveň v nějakém registru nebo minimálně nemapované paměti. Že při přístupu na str. tabulku další úrovně může vzniknout další page-fault, co to je TLB atd. atd. A k tý komunikaci s OS: když vznikne page-fault je vyvolané přerušení a obsluha je předaná obslužné rutinně OS (a přepne se úroveň oprávnění na procesoru). Některé procesory to dělají u page-faultu ve stránkovací tabulce (Intel), některý už u page-faultu v TLB (MIPS) -- takže si potom OS může vybírat, jak měnit stránky v samotné TLB.

Tyhle věci mě celkem zajímají, takže pro mě nebylo takovým zlem přečíst si před státnicema Tanenbauma: Operating Systems a Pattersona: Computers Design: Hardware to software interface. Je to určitě overkill, ale pokud budeš mít prolistovaný tyhle dvě knihy, tak tě tam imho určitě nic nemůže překvapit.
Odpovědět

Zpět na „Bakalářské SZZ“