IB110 Základy informatiky

Fakulta informatiky
podzim 2020

Předmět se v období podzim 2020 nevypisuje.

Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Jaroslav Bendík, Ph.D. (pomocník)
Garance
prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Předpoklady
! IB102 Automaty a gramatiky && ! IB005 FJA
žádné
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.

Předmět si smí zapsat nejvýše 35 stud.
Momentální stav registrace a zápisu: zapsáno: 0/35, pouze zareg.: 0/35
Mateřské obory/plány
předmět má 46 mateřských oborů, zobrazit
Cíle předmětu
Cílem kurzu je seznámit studenty se základními koncepty, myšlenkami, metodami a výsledky informatiky. Úspěšní absolventi kurzu by měli získat základní představu a problémech spojených s teoretickou informatikou, algoritmizací a výpočetní složitostí.
Výstupy z učení
Student bude po absolvování předmětu schopen:
- rozumět pojmu algoritmus,
- vysvětlit význam a nezbytnost Churchovy - Turingovy teze a formální definice algoritmu prostřednictvím Turingova stroje
- navrhnout jednoduchý konečný automat a Turingův stroj,
- vysvětlit pojem nedeterminizmu,
- rozlišit pojem rozhodnutenlný, částečné rozhodnutelný a nerozhodnutelný problém,
- identifikovat základné rozhodnutelné a nerozhodnutelné problémy,
- znát pojem výpočetní složitost,
- rozlišit prakticky řešitelné a prakticky neřešitelné problémy.
Osnova
  • Pojem algoritmického problému a algoritmu. Struktura algoritmu. jeho korektnost a složitost. Efektivní algoritmy a meze efektivity. Složitostní třídy, problém P vs NP. Algoritmicky neřešitelné problémy. Rozhodnutelné a nerozhodnutelné problémy.
Literatura
    povinná literatura
  • HROMKOVIČ, Juraj. Sedem divov informatiky. Ružomberok: Verbum, 2012, xi, 336. ISBN 9788080849580. info
    neurčeno
  • HAREL, David a Yishai A FELDMAN. Algorithmics :the spirit of computing. 3rd ed. Harlow: Addison-Wesley, 2004, xviii, 514. ISBN 0-321-11784-0. info
Výukové metody
přednášky a cvičení
Metody hodnocení
Přednášky a cvičení s testy v průběhu semestru. Závěrečný písemný test.
Informace učitele
https://is.muni.cz/auth/el/1433/podzim2017/IB110/index.qwarp
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 2009, podzim 2010, podzim 2011, podzim 2012, podzim 2013, podzim 2014, podzim 2015, podzim 2016, podzim 2017, podzim 2018, podzim 2019, jaro 2020, jaro 2021, jaro 2022, jaro 2023, jaro 2024.