Otázky IO

Teoretické základy informatiky

Z prvních tři následujících okruhů, neskládají zkoušku ti, kteří mají v kombinaci matematiku.
  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í, rezoluce)
  5. Predikátová logika prvního řádu (syntax, sémantika, prenexace, skolemizace, unifikace, rezoluce)
  6. Prolog (SLD-rezoluce, SLD-stromy, výpočetní mechanismus Prologu, základy programování v Prologu)
  7. Důkazy programů (dokazování vlastností programů, induktivní metody, invarianty cyklů)
  8. 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ů)
  9. 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)
  10. 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)
  11. 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)
  12. 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ů)
  13. 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).
  14. 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)
  15. Třídění (základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním)
  16. Grafové algoritmy (procházení grafu do hloubky a do šířky, složitost procházení grafu)

Programové, informační a výpočetní 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, Shefferova a Piercova 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 (achitektury 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í)