Informatika, 13. 9. 2012

Tak to mám s úspěchem za sebou. :D Budoucím generacím odkazuju seznam otázek z obecný informatiky (přepisuju z paměti, kdyžtak mě někdo opravte, kdo ste tam byl taky):

Derivace:

• Definujte pojem „derivace funkce“.

• Určete intervaly, na kterých je funkce $xe^{-x^2}$ rostoucí a klesající.

• Popište Newtonovu metodu hledání nulového bodu.

Matice:

• Dokažte, že elementárními úpravami používanými při Gaussově eliminační metodě se nemění množina řešení soustavy.

• Gaussovou metodou nalezněte řešení soustavy daného rozšířenou maticí soustavy: jakási rozšířená matice $3 \times 4$ s malými celými čísly, která se dala vyřešit ve dvou krocích G. eliminace

Grafy:

• Definujte úplný graf $K_n$ a úplný bipartitní graf $K_{m,n}$

• Pro která $n$ je $K_n$ cesta? Pro která $m,n$ je $K_{m,n}$ cesta?

• Pro která $n$ je $K_n$ rovinný? Pro která $m,n$ je $K_{m,n}$ rovinný?

• Odpovědi zdůvodněte.

Algebra:

• Definujte ireducibilní polynom.

• Dokažte, že každý polynom má rozklad na ireducibilní činitele.

• Najděte rozklad na ireducibilní činitele polynomu $x^3 + x$ v $\mathbb{R}$

• Najděte rozklad na ireducibilní činitele polynomu $x^3 + x$ v $\mathbb{C}$

Predikátová logika:

• Formulujte větu o kompaktnosti predikátové logiky a uveďte hlavní body důkazu.

Stránkování:
Uvažujte architekturu s 32-bitovými adresami a dvouúrovňovým stránkováním. Indexy stránek první i druhé úrovně mají stejnou velikost. Stránky jsou 4 kB. (Možná ještě něco dalšího. Prostě stejná situace jako na intelský x86.) Tabulka stránek mapuje virtuální adresu $123456_{16}$ na fyzickou adresu $123456_{16}$.

• Načrtněte schéma stránkovací tabulky, když $123456_{16}$ je jediná namapovaná adresa.

• Kolik položek ve stránkovací tabulce je třeba? (Opět $123456_{16}$ je jediná namapovaná adresa.)

• Které z následujících typů je nevhodné ukládat na adresu $123456_{16}$ a proč?

  uint32_t long double char[4096]

Transakce:

• Definujte pojem transakce. Vysvětlete význam slov zkratky ACID (atomicity, consistency, isolation, durability).

• Uvažujte transakce T1: R(X) R(Y) W(X), T2: R(X) R(Y) W(Y). Je rozvrh R1(X) R2(X) R1(Y) R2(Y) W1(X) W2(Y) konfliktově uspořádatelný?

Generické programování:
Uvažujte:

template <class b> class a {
  public:
    void f(b x) { ... }
};

public class a<b> {
  public void f(b x) { ... }
}

• Popište typy, které uvedené fragmenty definují.

• Pomocí šablon nebo generik zadefinujte rozhraní třídy implementující FIFO frontu, která má metody pro zařazení prvku na konec fronty a odebrání prvku z jejího začátku.

Ja zas pridám otázky z Programování na druhom termíne (11:30), opäť len voľne z pamäti, prípadne ma niekto opravte/doplňte :wink:

Primitívne funkcie:

• Definujte pojem „primitívna funkcia“.

• Vyslovte vetu na hľadanie primitívnej funkcie metódou „per partes“.

• Nájdite primitívnu funkciu k funkcii $x \cdot \sin x$.

Determinant:

• Definujte determinant matice.

• Dokážte $\det A = \det A^T$.

• Vyjadrite vzťah determinantov matice a jej inverznej matice.

Metrické priestory:

• Definujte metriku a metrický priestor. Napíšte príklad metriky na $R^n$, ktorá nie je euklidovská.

• Pre nasledujúce množiny uveďte, či sú otvorené a či sú uzavreté. Pre jednu dokážte:

  • $[0, 1]$

  • $(0, \infty)$

  • $(-\infty, \infty)$

Nezávislé javy:

• Jav A nastáva s pravdepodobnosťou P(A), jav B s pravdepodobnosťou P(B). Napíšte, s akou pravdepodobnosťou nastáva ich prienik, ak sú nezávislé.

• Rozšírte predchádzajúci vzorec, ak viete, že javy sú závislé. Stačí k tomuto vyjadreniu znalosť P(A) a P(B), alebo je potrebné ešte niečo?

• Hádžete dvoma kockami. Pre ktoré hodnoty $n \in \{2, \dots, 12\}$ je jav „Súčet bodov na kockách je n“ závislý na jave „Na prvej kocke padla hodnota 1“?

Procesory:
Tu si presne nepamätám znenie, viem, že sa pýtali na:

• zreťazené vyhodnocovanie inštrukcií na procesore, bolo potrebné kvantifikovať zdržanie pri pipeline stall a urýchlenie vyhodnotenia, keď každá inštrukcia má k krokov

• dôvod prítomnosti cache pri procesore, kvantifikovať stratu pri cache miss, definovať priamo adresovateľnú cache a množinovo asociovanú cache

Synchronizácia:

• Trieda Semaphore implementuje princíp semaforu. Popíšte sémantiku jednotlivých metód.

  Semaphore { Semaphore (int); void up (); void down (); }

• Upravte nasledujúci kód pomocou uvedenej implementácie semaforu tak, aby bol bezpečný pre viacero vláken.

  Counter { private int value; public int read () { return (value); }; public void increment () { value++; }; }

• Preveďte diskusiu, ako sa budú pri vašich úpravách ovplyvňovať vlákna, ktoré sa budú súčasne snažiť vykonávať funkciu read().

Návrhové vzory:

• Popíšte, čo sú návrhové vzory (design pattern) a čo je ich súčasťou.

• Vyberte si návrhový vzor Visitor, Abstract factory alebo Model-view-controller a popíšte ho.

XSLT:

• Stručne popíšte prácu XSLT procesora.

• Čo vráti prázdny XSLT skript?

• Aký bude výstup nasledujúceho skriptu, ak ho zavoláme na XML dokument obsahujúci zoznam zamestnancov, ktorí majú rodné číslo ako atribút a meno a priezvisko ako podelementy?

  xsl:stylesheet <xsl:template match="zamestnanec"> <xsl:value-of select="@rodniCislo"> <xsl:apply-template /> </xsl:template> </xsl:stylesheet>

(tu si absolútne nie som istý, či som niečo nevynechal)

Obor IOI měl od 11:30 stejné otázky jako IP, akorát místo Návrhových vzorů a XSLT byly tyto:

Asymetrická kryptografie a RSA

• Vysvětlete pojmy "asymetrická kryptografie", "veřejný klíč" a "soukromý klíč".
  Popište podepisování dokumentu pomocí asymetrické kryptografie.
  Vysvětlete inicializaci, šifrování a dešifrování algoritmu RSA.

Třídy složitosti

• Vysvětlete pojmy P, NP, NP-těžký a NP-úplný problém.
  Napište tři příklady NP-úplných problémů.