Bakalářská státnice - Informatika - Základy informatiky - obor Obecná informatika

Tato stránka není kompletní a/nebo může obsahovat chyby!

Převzato z webu MFF a převedeno na strukturovaný seznam:

1. Logika
   1. (Základy:)
      • jazyk,
      • formule,
      • sémantika,
      • tautologie.
   2. (Vlastnosti:)
      • rozhodnutelnost,
      • splnitelnost,
      • pravdivost,
      • dokazatelnost.
   3. Věty o kompaktnosti a úplnosti výrokové a predikátové logiky.
   4. (Tvary formulí:)
      • normální tvary výrokových formulí,
      • prenexní tvary formulí predikátové logiky.
2. Automaty a jazyky
   1. (Základy:)
      • Chomského hierarchie,
      • třídy automatů a gramatik,
      • determinismus a nedeterminismus.
   2. Uzávěrové vlastnosti tříd jazyků.
3. Algoritmy a datové struktury
   1. Časová složitost algoritmů, složitost v nejhorším a průměrném případě.
   2. Třídy složitosti P a NP, převoditelnost, NP-úplnost.
   3. Metoda „rozděl a panuj“ - aplikace a analýza složitosti.
   4. (Datové struktury:)
      • binární vyhledávací stromy,
      • vyvažování,
      • haldy.
   5. Hašování.
   6. (Třídění:)
      • sekvenční třídění,
      • porovnávací algoritmy,
      • přihrádkové třídění,
      • třídící sítě.
   7. Grafové algoritmy:
      • prohledávání do hloubky a do šířky,
      • souvislost,
      • topologické třídění,
      • nejkratší cesta,
      • kostra grafu,
      • toky v sítích.
   8. Tranzitivní uzávěr.
   9. Algoritmy vyhledávání v textu.
   10. Algebraické algoritmy:
       • DFT,
       • Euklidův algoritmus.
   11. (Kryptografie:)
       • Základy kryptografie,
       • RSA,
       • DES.
   12. Pravděpodobnostní algoritmy - testování prvočíselnosti.
   13. Aproximační algoritmy.
4. Databáze
   1. Podstata a architektury DB systémů.
   2. Konceptuální, logická a fyzická úroveň pohledů na data.
   3. Relační datový model, relační algebra.
   4. Algoritmy návrhu schémat relací, normální formy, referenční integrita.
   5. Základy SQL.
   6. Transakční zpracování, vlastnosti transakcí.
   7. Organizace dat na vnější paměti, B-stromy a jejich varianty.
5. Architektury počítačů a sítí
   1. Architektury počítače.
   2. Procesory, multiprocesory.
   3. Vstupní a výstupní zařízení, ukládání a přenos dat.
   4. Architektury OS.
   5. Procesy, vlákna, plánování.
   6. Synchronizační primitiva, vzájemné vyloučení.
   7. Zablokování a zotavení z něj.
   8. Organizace paměti, alokační algoritmy.
   9. Principy virtuální paměti, stránkování.
   10. Systémy souborů, adresářové struktury.
   11. Bezpečnost, autentifikace, autorizace, přístupová práva.
   12. ISO/OSI vrstevnatá architektura sítí.
   13. TCP/IP.
   14. Spojované a nespojované služby, spolehlivost, zabezpečení protokolů.
6. Programovací jazyky
   1. Principy implementace procedurálních programovacích jazyků, oddělený překlad, sestavení.
   2. Objektově orientované programování.
   3. Neprocedurální programování, logické programování.
   4. Generické programování.