IOI 26. 6. 2012 11.30

Ahoj,

tady jsou zhruba otázky, které jsme měli dnes v 11.30 na IOI. Pokud si pamatujete ostatní obory, nebo máte upřesnění, napište a post editnu. Enjoy.

Spojitost a derivace

• Definujte spojitost funkce v bodě.
  Definujte derivaci.
  Určete na jakých intervalech je funkce rostoucí a klesající: $xe^{-x}$

Vlastní čísla a vlastní vektory

• Má-li matice A řádu $n$ vlastní čísla $\lambda_i$ a vlastní vektory $v_i$. Jaká vlastní čísla a vektory bude mít matice
  $A^3$?
  Zjistěte všechna vlastní čísla a vektory matice:
  $$\left( \begin{array}{lll} 3 & 2 & 1 \\ 0 & 3 & 2 \\ 0 & 0 & 3\end{array}\right)^4$$

Tělesa

• Definujte těleso.
  Jsou $\mathbb{Z},\mathbb{Q}, \mathbb{R}$ se standardně definovaným sčítáním a násobením tělesa a proč?
  Sestrojte těleso na třech prvcích.

Bodové odhady a testování hypotéz

• Definujte střední hodnotu.
  Určete střední hodnotu náhodného rozdělení $F$, pokud máte vzorek hodnot náhodné veličiny. Dokažte, že je tento odhad nestranný.
  Popište testování hypotéz a v rámci vysvětlení vysvětelete "nulovou hypotézu" a "hladinu spolehlivosti".
  Máte vzorek náhodné veličiny (1,2,2,3,3,3). Úkolem je zjistit, zda by mohla střední hodnota být 2.2. Výsledek t-testu byla p-honota $\approx$ 0.7. Jak

Logika

• Zformulujte větu o úplnosti výrokové logiky a napište hlavní body důkazu.

Databázové systémy

• Popište relační datový model.
  Popište, proč převádíme do normálních forem.
  Definujte 3NF.
  Vytvořte relační schéma, které porušuje 2NF i 3NF. Použijte atributy IdUčitel, IdŠkola, UčitelŠkola, UčitelMěsto, UčitelPřednáška.

HeapSort

• Napište v pseudokódu HeapSort.
  Určete jeho časovou složitost.
  Porovnejte časovou složitost HeapSortu s QuickSortem.

Synchronizace

• Popište sémantiku metod v kódu:

  class Lock { void lock(); void unlock(); }

Řekněte, zda následující kód funguje dobře:

class Lock {
Semaphore s;
Lock() { s = new Semaphore(1); }
void lock() { s.down(); }
void unlock() { d.up(); }
}

Mějme kolekci, ke které se smí přistupovat pouze z jednoho vlákna. Jak toto omezení obejdeme bez modifikace dané dolekce? Diskutujte efektivitu tohoto řešení na víceprocesorových systémech.