Jste zde: Fakulta informatiky » Studium » Základ I

Teoretické základy informatiky

  1. Množiny a relace (zobrazení, funkce, rozklady a ekvivalence)
  2. Elementární kombinatorika (variace, kombinace a permutace)
  3. Uspořádání (relace uspořádání, uspořádané množiny a svazy, číselné obory)
  4. Výroková logika (syntax, sémantika, odvozovací systém výrokové logiky, důkazy ve výrokové logice, pravdivost a dokazatelnost logických formulí)
  5. Důkazy programů (dokazování vlastností programů, induktivní metody, invarianty cyklů)
  6. Rekurze (rekurzivní definice funkcí, funkce vyššího řádu, částečná aplikace, curryifikace, definice funkcí rekurzivně a pomocí kombinátorů, definice vyšších funkcí bez použití formálních parametrů)
  7. Vyhodnocování výrazů (pořadí vyhodnocování, striktní a normální redukce, líná redukce, efektivita nekonečné datové struktury, definice funkcí nad nekonečnými strukturami)
  8. Regulární jazyky (regulární jazyky, způsoby jejich reprezentace, vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami)
  9. Konečné automaty (definice, konstrukce konečného automatu, minimalizace konečného automatu, převod nedeterministického konečného automatu na deterministický automat)
  10. Bezkontextové jazyky (definice, vlastnosti, způsoby jejich reprezentace, konstrukce bezkontextové gramatiky a zásobníkového automatu, normální formy bezkontextových gramatik, použití lematu o vkládání pro bezkontextové jazyky, uzávěrové vlastností bezkontextových jazyků)
  11. Zásobníkové automaty (definice, převod bezkontextové gramatiky na zásobníkový automat). Syntaktická analýza (syntaktická analýza shora dolů a zdola nahoru, průběh analýzy daného slova)
  12. Turingovy stroje a jazyky typu 0 (definice, vztah ke gramatikám Chomského hierarchie, rekurzivní a rekurzivně spočetné jazyky, uzávěrové vlastnosti)
  13. Vyčíslitelnost (rekurzivní a rekurzivně spočetné množiny. První Riceova věta. Redukce a její vlastnosti. Uzávěrové vlastnosti rekurzívních a rekurzivně spočetných množin. Příklady rekurzivních a rekurzivně spočetných množin. )
  14. Složitost (časová a prostorová složitost, hierarchie tříd složitosti a vztahy mezi nimi. NP-těžké a NP-úplné úlohy.Polynomiální redukce. Příklady NP-těžkých a NP-úplných úloh. Metody důkazu NP-těžkosti.)
  15. Datové struktury a jejich implementace (seznam, zásobník, fronta, binární strom, obecný strom, vyhledávací stromy a jejich modifikace. Implementace binárních a vyhledávacích stromů a operací nad nimi)
  16. Třídění (základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním). Grafové algoritmy (procházení grafu do hloubky a do šířky, složitost procházení grafu, komponenty souvislosti, hledání nejkratších cest, toky v sítích, kostra grafu)
  17. Algoritmy pro práci s řetězci. (Vyhledávání vzorků v textu. Naivní vyhledávání. Algoritmus Karpův-Rabinův. Algoritmus založený na konečných automatech. Složitost vyhledávání.)
  18. Metody analýzy složitosti algoritmů (složitost v nejlepším, nejhorším, průměrném případu, očekávaná složitost)
  19. Metody konstrukce efektivních algoritmů. (Rozděl a panuj. Dynamické programování. Hladové strategie. Backtracking. Meze použitelnosti i jednotlivých technik. Příklady algoritmů postavených na jednotlivých technikách.)

Programové, výpočetní a informační systémy

  1. Výpočetní systémy I (číselné soustavy, vztahy mezi číselnými soustavami, zobrazení čísel v počítači, principy provádění aritmetických operací. Booleova algebra, kombinační a sekvenční logické obvody)
  2. Výpočetní systémy II (Procesory, jejich parametry a architektury. Architektura Intel. Vnitřní a vnější paměti a principy jejich funkce. Vstupní a výstupní zařízení počítače a jejich připojování)
  3. Programování (strukturované programování v imperativním jazyce, datové a řídicí struktury programovacích jazyků, datové typy, procedury a funkce, bloková a modulární struktura programu)
  4. Objektově orientované programování (základní pojmy OOP, zapouzdření, dědičnost, polymorfizmus, objektové programování v imperativním jazyce, spolupráce objektů. Událostmi řízené programování. Výjimky)
  5. Operační systémy (architektury operačních systémů, rozhraní operačních systémů. Procesy, synchronizace procesů, uváznutí a metody ochrany proti uváznutí. Práce s pamětí, logický a fyzický adresový prostor, správa paměti a způsoby jejího provádění)
  6. Plánování v operačních systémech (správa a plánování činnosti procesorů. Systémy souborů. Správa a plánování činnosti V/V zařízení)
  7. Počítačové sítě (topologie, přístupové metody a architektury počítačových sítí (Ethernet, Fast Ethernet, Token-ring, ATM,...). Bezdrátové komunikační technologie. Model OSI. Protokol TCP/IP. Propojování počítačových sítí a směrování informací)
  8. Databáze I (relační model, relační schéma, klíče relačních schémat, integritní omezení, relační algebra, spojování relací)
  9. Databáze II (funkční závislosti; klíče relačních schémat; Armstrongovy axiómy; dekompozice relačních schémat; normální formy obecně, 1NF, 2NF, 3NF, Boyce-Coddova NF, vztahy mezi NF; převody relačních schémat do NF)
  10. SQL (syntaxe a sémantika příkazů; vestavěné funkce, triggery, uložené procedury, příkazy pro definici dat; transakční zpracování; atomické operace; optimalizace dotazů)
  11. Základy datového modelování (návrh datových struktur; ER diagramy; entity, atributy, vztahy; grafické vyjádření)