Otázky B-IVV Informatika ve vzdělávání

Studijní plán Minor

Teoretické základy informatiky

  1. Výroková logika. Syntax, sémantika, odvozovací systém výrokové logiky, důkazy ve výrokové logice, pravdivost a dokazatelnost logických formulí. (IB000)
  2. Funkce a rekurze. Rekurzivní definice funkcí, rekurzivní datové typy (seznamy, stromy), funkce nad rekurzivními datovými typy. (IB114)
  3. Datové struktury a jejich implementace. Abstraktní datové typy: seznam, pole, zásobník, fronta, binární strom, obecný strom, vyhledávací strom. Implementace binárních a vyhledávacích stromů a operací nad nimi. (IB113, IB114)
  4. Grafy. Typy grafů, stromy, stupně vrcholů, orientované grafy, reprezentace grafů. Algoritmy prohledávání grafu do hloubky a do šířky a jejich využití. Komponenty souvislosti. (IB114)
  5. Třídění. Základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním. (IB114)
  6. Regulární jazyky. Regulární jazyky, regulární gramatiky, regulární výrazy, konečné automaty. Vlastnosti regulárních jazyků, vztah mezi konečnými automaty a regulárními gramatikami. (IB110)
  7. 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. (IB110)
  8. Vyčíslitelnost. Turingův stroj jako univerzální výpočetní model. Problém zastavení. Rozhodnutelnost a částečná rozhodnutelnost, nerozhodnutelnost. Diagonalizace. (IB110)
  9. Složitost. Složitost algoritmu versus složitost problému. Složitostní třídy (P, NP) a vztahy mezi nimi, příklady problémů z jednotlivých tříd. Těžkost a úplnost problému v dané třídě, polynomiální redukce problémů, NP-úplné úlohy. (IB110)
Programové, výpočetní a informační systémy

  1. Výpočetní systémy I. Číselné soustavy, vztahy mezi soustavami, zobrazení celého čísla v počítači, aritmetika. Kódy, vnitřní, vnější, detekční a opravné. Procesory, jejich parametry a architektury. (PB150)
  2. 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. (IB113).
  3. 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í. Plánování v operačních systémech. (PB153)
  4. Počítačové sítě. Topologie, přístupové metody a architektury počítačových sítí (Ethernet, Fast Ethernet, Token-ring, ATM, atd.). Bezdrátové komunikační technologie. Model OSI. Protokol TCP/IP. Propojování počítačových sítí a směrování informací. (PB156)
  5. 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í. (PB168)
  6. Databáze II. Dotazovací jazyk SQL (příkaz select, spojování relací, agregační funkce). Zpracování dotazů. Základní principy, příklad. Indexování. Transakce. Vlastnosti transakčního zpracování.
  7. Softwarové inženýrství. Vývoj software. Specifikace požadavků, analýza a návrh systému, testování, verifikace a validace, provoz systému. Použití UML při vývoje software. (PB007)