SZZ Bc Informatika 2017-6

Jak to dnes vypadalo + otázky v následujících komentářích.

Každý test z informatiky byl s 9 otázkami, každá po 3 bodech, ze zaměření byly 3 otázky. Pro projití zkouškou je nutné získat aspoň polovinu bodů zaokrouhleno dolů, tj. 13 z 27. A je nutné mít z otázek ze zaměření také alespoň půlku, též zaokrouhleno dolů. (S výjimkou zaměření algoritmy a optimalizace, ti měli jen 8 otázek z toho 2 ze zaměření.)

Zadávání testů a psaní probíhalo zároveň ve 2 učebnách S4, S5. Tedy komentář k zadání byl v obou místnostech proveden Tůmou (takže to nebylo paralelní).
V místnosti je 1 člověk jako dozor, plus tam různě pobíhají lidé, kteří umějí dovysvětlit zadání. Takže pokud si člověk něčím není jistý, může se kdykoliv zeptat. Ptejte se! V nejhorším případě dostanete odpověď "Tahle věc je letos v sylabu předmětu, který se k tomu vztahuje, máte to vědět, víc vám nenapovíme.". Pokud chcete hint k otázce (ve smyslu fakt netušíte jak na ni i když třeba tématu rozumíte a předmět jste zvládali), taky se zeptejte, pravděpodobně hint dostanete a dostanou ho i všichni ostatní.

Na test nebyl na začátku stanoven limit na dobu řešení. Tedy i když naše místnost začínala možná kolem 8:45, ještě v 14:30 spousta lidí vesele i nevesele psala. (Mimochodem odhad obtížnosti na délku vypracování byl cca 2 h od zadávajících.)

Nezapomeňte si sebou doklad totožnosti s fotkou nebo ISIC, sice to nikdo nekontroloval, ale u sebe smíte mít jen doklad, psací potřeby, jídlo, pití a cokoliv, co uzná komise za přípustné v tom směru, že vám to nijak nebude pomáhat fixlovat, takže klidně plyšového medvídka, ale ne telefon či příliš chytré hodinky.

Hoši i dámy, přijďte klidně v pižamu pokud vám to bude pohodlné, fakt nikdo nevyžaduje saka a šaty, je to prostě jenom písemka bez jakékoliv ústní části.

[Státnice informatika] sepsal Kuba:
Takže co tam dneska bylo: za každý okruh jedna otázka, celkem 9 otázek, z toho tři poslední se týkaly vybraného zaměření. Za každou otázku maximálně tři body, požadované minimum byla polovina bodů + polovina bodů z otázek ze zaměření. Žádné otázky se neškrtaly.

1. ADS: zadefinovat topologické třídění, popsat algoritmus a vysvětlit, jak pomocí něj najít počet různých cest z jednoho vrcholu do druhého.

2. Databáze: máme tabulku, která odpovídá rozvrhu na MFF s položkami jako ID předmětu, jméno předmětu, den v týdnu, čas, semestr, místnost, vyučující. Úkolem bylo převést do BCNF a napsat SQL, které vrátí vyučující, kteří mají v rozvrhu překryvy (stačilo udělat kartézský součin tabulky).

3. Autogramy: máme zjednodušený JSON, hloubka omezena na 3, klíč je vždy string a hodnota je buď číslo, nebo blok. hodnota v "config"/"version" musí existovat a být nastavena na 10. Napište na to gramatiku, určete, zda je LL(1) a rozhodněte, jestli takový JSON dokážete přijímat konečným automatem.

4. Programování: editor 2D vektorové grafiky, dokážeme v něm klikáním vybírat tvary (čtverec, kruh...) a umisťovat je na plátno. Navrhněte objektový model.

5. Sítě: Posíláte přes SMTP email s textem T a předmětem S z adresy A na adresu B. Vy jste na počítači s adresou P, server je na adrese Q. Popište přesně zprávy, ke kterým dochází při komunikaci. [Tohle mi přišlo hardcore, fakt si musíme pamatovat formát SMTP zpráv? Podle dotazů by nicméně stačilo i popsat přibližný proces odesílání.] Ještě chtěli vědět, jaký transportní protokol se používá.

6. Principy počítačů: Máme dva programy, které transformují string na vstupu a hned ho pošlou na výstup (pascalovský zdroják: while not eof do ReadLn; Transform; WriteLn). Spustili jsme Program1.exe < in.txt | Program2.exe > out.txt. Mohou Program1 a Program2 běžet alespoň zčásti paralelně? Šlo by zařídit, aby si nemuseli string předávat přes standardní vstup, ale přes část paměti? Pokud předpokládáme, že Program1 přidá na začátek řádku plus, Program2 na konec řádku vykřičník a podstrčíme jim na vstup binární obrázek (JPG, BMP...), budou s tím mít programy problém?
   Počítač má jeden jednojádrový procesor.

Zaměření "softwarové inženýrství":
7. XSLT: dostanete nějaký stylesheet, který transformuje zadané XML do HTML, a máte napsat, jaký bude výsledek. Šlo o celkem triviální převod seznamu zaměstnanců do odrážkového seznamu.
8. C++: v zadání je třída Matrix, shromažďující prvky matice v lineárním vektoru. Pomocí traits a policy classes zajistěte, aby si uživatel mohl vybrat, zda chce v tom vektoru mít prvky řazené sloupec po sloupci, nebo řádek po řádku.
9. Návrhové vzory: pro univerzitu děláme nový SIS. Lidé ze školy jsou buď studenti, učitelé, nebo zaměstnanci a tyto typy se zřejmě nebudou rozšiřovat. Chceme být schopni jednoduše implementovat nové operace, protože rektorát vydává stále nové předpisy. Udělejte návrh business logiky (tj. neřešte frontend ani ukládání do databáze) a použijte k tomu nějaký návrhový vzor/vzory. Ukažte, co implementovat/změnit, pokud vytvoříme novou operaci, která má za úkol u studentů zjistit průměrnou dobu studia. Co je třeba změnit, pokud porušíme podmínku v zadání a přidáme nový typ člověka Knihovník?

===
Bylo to jednodušší, než jsem čekal, ale taky zdlouhavější. Začínali jsme v 8.45, odcházel jsem v 13.30 a to většina ještě psala. Pangrác byl z toho evidentně překvapený

Většina otázek byla rozdělena na 2-3 podotázky (pro jednotlivé části nebylo stanoveno za kolik jsou bodů)

[Zaměření Temno+Kombagra]

1. Automaty Uvažujte slova nad abecedou {O,1}*. Jazyk L(A) = {w | w je dělitelné třemi} 1. Zkonstruujte deterministický zásobníkový automat přijímající jazyk L(A). 2. Napište k němu regulární výraz. 3. Napište k němu gramatiku, která je co (nejstriktnější) nejvýš v Chomského hierarchii.

2. Databáze Máme tabulku Rozvr s atributy: Kód předmětu, Název předmětu, Rok, Semestr, Den, Čas zčačátku, Místnost, Délka, Typ (Přdnáška/cvičení), Vyučující. Žádný atribut nemá hodnotu NULL, databáze zajišťuje, že nezačíná žádné 2 věcí zároveň na stejném místě. Už ale nezaručuje, že časy (délky) se nepřekrývají, či že jeden vyučující nemá rozvrženo více výuky ve stejný čas. 1. Napište minimální (primární) klíč, pokud jich existuje více napište libovolný. 2. Kterým normálním formám (1NF - 5NF) schéma vyhovuje a zdůvodněte proč. 3. Převeďte to do BCNF.

3. Sítě SMTP viz Kuba

4. ADS 1. Definujte topologické uspořádání pro orientovaný acyklický graf. 2. Popište algoritmus, kterým lze najít topologické uspořádání a rozeberte jeho časovou složitost. 3. Jak lze pomocí algoritmu na nalezení topologického uspořádání najít počet různých cest z vrcholu u do vrcholu v.

5. Architektura počítačů viz Kuba to bylo taky rozdělené do 3 podotázek

6. Programování Viz Kuba bylo to na 2 podotázky byly 1. Vytvořte návrh 2. Upravte návrh tak, aby bylo možné jednotlivým tvarům nastavovat rozměry, všechny rozměry jsou typu double, ale kažýd tvar jich může mít různý počet a různě pojmenované.

Zaměření:
7.Temno 1. Zformulujte axiom výběru. 2. Jak souvisí axiom výběru s existencí neměřitelných množin?
8. Kombagra 1. Uvažujte úplný tripartitní graf. Jaké velikosti mohou mít partity, aby měl graf perfektní párování? 2. Zformulujte Tutteovu větu o perfektním párování 3. Nechť T je storm. Dokažte že T má perfektní párování právě tehdy když T-v
9. Kombagra 1. Formulujte Ramseyovu větu pro úplné grafy s obarvením hran dvěma barvama. 2. Dokažte, že v nekonečné posloupnosti různých celých čísel lze vybrat nekonečnou monotonní podposloupnost.

Ještě si dovolím přikopírovat další zaměření od kolegů:

**[ Zaměření algoritmy a optimalizace]
**
bylo jen 8 otázek (jen dvě otázky ze zaměření).

1. definovat Voroného diagramy ve 2D a nastínit základní myšlenky důkazu jejich kombinatorické složitosti ve 2D pomocí tvrzení o složitosti 3D mnohostěnu s n vrcholy.

2. aproximační algoritmy na SAT (zformulovat LP SAT a analyzovat ho), zformulovat biased sat (měli to tam napsáno popisem, do kterého by se vešel i randsat, ale podle mě mysleli biased sat), říct, jestli to nejde nějak lépe (s nápovědou, že máme zkusit zkombinovat předchozí dva algoritmy).tedy otázka na bestsat (nebo jak se jmenoval)...

[Zaměření grafika]

1. vektorova vs rasterova grafika, napsat priklady obou formatu, napsat jaky kompresni algoritmy se pouzivaji u rasterove

2. prvni otazku si nepamatuju, antialiasing u rasterovych obrazku, antialiasing u raytracingu

3. popsat jak reprezentovat efektivne data pro 3d scenu kde je teren a pohybujici se modely, popsat jak se data dostavaji do gpu, treti si nepamatuju