Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

# Učební texty k státní bakalářské zkoušce
Obecná informatika

študenti MFF

Vážený študent/čitateľ,

toto je zbierka vypracovaných otázok pre bakalárske skúšky Informatikov. Otázky boli vypracované študentmi MFF počas prípravy na tieto skúšky, a teda zatiaľ neboli overené kvalifikovanými osobami (profesormi/dokotorandmi mff atď.) - preto nie je žiadna záruka ich správnosti alebo úplnosti.

Väčšina textov je vypracovaná v čestine resp. slovenčine, prosíme dodržujte túto konvenciu (a obmedzujte teda používanie napr. anglických textov). Ak nájdete nejakú chybu, nepresnosť alebo neúplnú informáciu - neváhajte kontaktovať administrátora alebo niektorého z prispievateľov, ktorý má write-prístup k svn stromu, s opravou :-) Podobne - ak nájdete v texte veci ako ??? a TODO, znamená to že danú informáciu je potrebné skontrolovať, resp. doplniť...

Texty je možné ďalej používať a šíriť pod licenciou GNU GFDL (čo pre všetkých prispievajúcich znamená, že musia súhlasiť so zverejnením svojich úprav podľa tejto licencie).

Veríme, že Vám tieto texty pomôžu k úspešnému zloženiu skúšok.

(1,0)300

Hlavní writeři :-) :

- ajs
- andree - http://andree.matfyz.cz/
- Hydrant
- joshis / Petr Dvořák
- kostej
- nohis
- tuetschek - http://tuetschek.wz.cz/

Úvodné verzie niektorých textov vznikli prepisom otázok vypracovaných písomne na papier, alebo inak ne-TEX-ovsky. Autormi týchto pôvodných verzií sú najmä nasledujúce osoby: gASK, Grafi, Kate (mat-15), Nytram, Oscar, Stando, xStyler. Časť je prebratá aj z pôvodných súborkových textov... Všetkým patrí naša/vaša vďaka.

- Obsah
- Logika
  - Logika - jazyk, formule, sémantika, tautologie
    - Jazyk
    - Formule
    - Sémantika
    - Tautologie
  - Rozhodnutelnost, splnitelnost, pravdivost a dokazatelnost
    - Splnitelnost
    - Pravdivost
    - Dokazatelnost
    - Rozhodnutelnost
  - Věty o kompaktnosti a úplnosti výrokové a predikátové logiky
  - Normální tvary výrokových formulí, prenexní tvary formulí predikátové logiky
    - Prenexní tvary formulí predikátové logiky
- Automaty a jazyky
  - Automaty - Chomského hierarchie, třídy automatů a gramatik, determinismus a nedeterminismus.
    - Třídy automatů a gramatik
    - Chomského hierarchie
    - Determinismus a nedeterminismus
  - Uzávěrové vlastnosti tříd jazyků
- Algoritmy a datové struktury
  - Časová složitost algoritmů, složitost v nejhorším a průměrném případě
    - Asymptotická složitost
    - Amortizovaná složitost
  - Třídy složitosti P a NP, převoditelnost, NP-úplnost
  - Metoda rozděl a panuj - aplikace a analýza složitosti
  - Binární vyhledávací stromy, vyvažování, haldy
    - Binární strom
    - Binární vyhledávací strom
    - Vyvažované vyhledávací stromy
    - Halda
    - #1
  - Hašování
    - Hašování se separovanými řetězci
      - Očekávaný počet testů
    - Hašování s uspořádanými řetězci
      - Očekávaný počet testů
    - Hašování s přemísťováním
      - Očekávaný počet testů
    - Hašování se dvěma ukazateli
      - Očekávaný počet testů
    - Srůstající hašování
    - Hašování s lineárním přidáváním
    - Shrnutí
    - Univerzální hašování
    - Perfektní hašování
    - Externí hašování
  - Sekvenční třídění, porovnávací algoritmy, přihrádkové třídění, třídící sítě
    - Sekvenční třídění a porovnávací algoritmy
    - Přihrádkové třídění
    - Třídící sítě
  - Grafové algoritmy
    - Graf
    - Prohledávání do hloubky a do šířky
    - Souvislost
    - Topologické třídění
    - Hledání nejkratší cesty v grafu
    - Minimální kostra grafu
    - Toky v sítích
  - Tranzitivní uzávěr
  - Algoritmy vyhledávání v textu
    - Rabin-Karp
    - Aho-Corasick
    - Knuth-Morris-Pratt
  - Algebraické algoritmy
    - Diskrétní Fourierova Transformace (DFT)
    - Euklidův algoritmus
  - Základy kryptografie, RSA, DES
    - Základy kryptografie
    - RSA (Rivest-Shamir-Adleman)
    - DES (Data Encryption Standard)
  - Pravděpodobostní algoritmy - testování prvočíselnosti
  - Aproximační algoritmy
- Databáze
  - Podstata a architektury DB systemů
    - Databázové modely
    - Architektury databázových systémů
  - Konceptualní, logická a fyzická úroveň pohledu na data
  - Relační datový model, relační algebra
  - Algoritmy návrhu schémat relací
    - Normální formy
    - Algoritmy návrhu schémat relací
    - Referenční integrita
  - Základy SQL
    - Standardy SQL
    - Dotazy v SQL
    - Definice a manipulace s daty, ostatní příkazy
  - Transakční zpracování, vlastnosti transakcí, uzamykací protokoly, zablokování
    - Vlastnosti transakcí
    - Uzamykací protokoly
      - Dvoufázový protokol (2PL)
      - Striktní dvoufázový protokol (S2PL)
      - Konzervativní dvoufázový protokol (C2PL)
    - Vylepšení zamykacích protokolů
      - Sdílené a výlučné zámky
      - Strukturované uzamykání (multiple granularity)
    - Alternativní protokoly
      - Časová razítka
      - Optimistické protokoly
  - Organizace dat na vnější paměti, B-stromy a jejich varianty
    - Vnější paměť
    - Soubor
    - Statické metody organizace souboru
    - Třídění na vnější paměti
    - B-stromy
- Architektury počítačů a sítí
  - Architektury počítače
    - Základní dvě architektury počítačů
  - Procesory, multiprocesory
    - Multiprocesory
  - Vstupní a výstupní zařízení
  - Architektury OS
  - Procesy, vlákna, plánování
    - Procesy a vlákna
    - Plánovanie
  - Synchronizační primitiva, vzájemné vyloučení
    - Pojmy
    - Aktivní čekání
    - Pasivní čekání
    - Klasické synchronizační problémy
  - Zablokování a zotavení z něj
    - Coffmanovy podmínky
    - Řešení zablokování
  - Organizace paměti, alokační algoritmy
  - Principy virtuální paměti, stránkování, algoritmy pro výměnu stránek, výpadek stránky, stránkovací tabulky, segmentace
    - Virtuální paměť
    - Stránkování
    - Algoritmy pro výměnu stránek
    - Segmentace
  - Systémy souborů, adresářové struktury
  - Bezpečnost, autentifikace, autorizace, přístupová práva
  - Architektura ISO/OSI
    - Úvod
    - 7 vrstev
    - Kritika
  - Rodina protokolů TCP/IP (ARP, IPv4, IPv6, ICMP, UDP, TCP) - adresace, routing, fragmentace, spolehlivost, flow control, congestion control, NAT
    - Adresace, IPv4, IPv6
    - Routing
    - Fragmentace
    - Spolehlivost, Flow control, Congestion control
    - NAT
    - ARP
    - ICMP
    - UDP, TCP
  - Spojované a nespojované služby, spolehlivost, zabezpečení protokolu
- Programovací jazyky
  - Principy implementace procedurálních programovacích jazyků, oddělený překlad, sestavení
  - Objektově orientované programování
  - Neprocedurální programování, logické programování
    - Neprocedurální programování
    - Prolog
    - Haskell
    - Lisp
    - Logické programování
  - Generické programování a knihovny
    - Knihovna
- About this document ...