# Informatika, 13. 9. 2012

<{ForumPost(poster="Oxyd", timestamp=2012-09-13 14:52:43)}>
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.

<{/ForumPost}>

<{ForumPost(poster="Pitr2311", timestamp=2012-09-13 21:42:37)}>
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)

<{/ForumPost}>

<{ForumPost(poster="paulie", timestamp=2012-09-14 11:43:25)}>
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ů.

<{/ForumPost}>