IB110 Základy informatiky

Fakulta informatiky
jaro 2020
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
RNDr. Petr Novotný, Ph.D. (přednášející)
Ondřej Svoboda (cvičící)
Bc. Anh Minh Tran (cvičící)
Garance
RNDr. Petr Novotný, Ph.D.
Katedra teorie programování - Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování - Fakulta informatiky
Rozvrh
Po 17. 2. až Pá 15. 5. Út 10:00–11:50 A217
  • Rozvrh seminárních/paralelních skupin:
IB110/01: Čt 12:00–13:50 C525, A. Tran
IB110/02: Po 14:00–15:50 A218, O. Svoboda
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ů.
Mateřské obory/plány
předmět má 15 mateřských oborů, zobrazit
Cíle předmětu
Cílem kurzu je seznámit studenty se základními abstraktními výpočetními modely a jejich využitím v analýze algoritmů a výpočetních problémů. Absolventi kurzu budou chápat základní koncepty z oblastí konečných automatů, rozhodnutelnosti a složitosti. Získané dovednosti budou schopni využít k hlubšímu pochopení konceptů vyskytujích se v programátorské praxi.
Výstupy z učení
Student bude po absolvování předmětu schopen:
- vysvětlit koncept konečného automatu a sestrojit konečný automat pro jednoduché regulární jazyky
- vysvětlit koncept regulárního výrazu a sestrojit regulární výraz pro jednoduché regulární jazyky
- vysvětlit pojem nedetriminismu a využít jej při konstrukci konečných automatů
- použít základní algoritmy pro úpravu konečných automatů (determinizace apod.)
- chápat pojem (ne)rozhodnutelného problému a být schopen vysvětlit existenci nerozhodnutelných problémů
- vysvětlit koncept Turingova stroje a navrhnout TS pro jednoduché problémy
- chápat pojem redukce mezi výpočetními problémy
- znát pojem výpočetní složitost a základní složitostní třídy, včetně vztahů mezi nimi
Osnova
  • Konečné automaty a regulární jazyky. Konstrukce konečných automatů.
  • Nedeterministické automaty, použití nedeterminismu, determinizace, minimalizace.
  • Regulární výrazy a gramatiky. Příklady neregulárních jazyků.
  • Výpočetní problémy a algoritmy. Turingovy stroje. Rozhodnutelné a nerozhodnutelné problémy, diagonalizace.
  • Redukce mezi výpočetními problémy.
  • Časová a prostorová složitost algoritmů a problémů. Třídy P a NP. NP-úplné problémy. Příklady složitostních tříd a vztahy mezi nimi.
Literatura
    doporučená literatura
  • JANČAR, Petr. Teoretická informatika. 2010. URL info
  • HOPCROFT, John E., Rajeev MOTWANI a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. 3rd ed. Boston: Pearson/Addison Wesley, 2007. xvii, 535. ISBN 0321455363. info
  • ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ a Antonín KUČERA. Formální jazyky a automaty I. Brno: Masarykova univerzita, 2006. 159 s. Elportal. ISSN 1802-128X. URL info
    neurčeno
  • HROMKOVIČ, Juraj. Sedem divov informatiky. xi, 336. ISBN 9788080849580. info
Výukové metody
přednášky a cvičení
Metody hodnocení
Výsledná známka bude určena na základě výsledků průběžného a závěrečného testu. K přihlášení ke zkoušce bude zapotřebí splnění podmínek na aktivitu v průběhu semestru: účast na cvičeních a vypracování domácích příkladů.
Informace učitele
https://is.muni.cz/auth/el/1433/podzim2017/IB110/index.qwarp
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
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 2021.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2020/IB110