IB110 Základy informatiky

Fakulta informatiky
jaro 2021
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
doc. RNDr. Petr Novotný, Ph.D. (přednášející)
Mgr. Jiří Zárevúcky (cvičící)
Bc. Ondřej Darmovzal (pomocník)
Mgr. Ondřej Svoboda (pomocník)
Mgr. Anh Minh Tran (pomocník)
Garance
doc. RNDr. Petr Novotný, Ph.D.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Čt 10:00–11:50 Virtuální místnost
  • Rozvrh seminárních/paralelních skupin:
IB110/01: Út 10:00–11:50 Virtuální místnost, P. Novotný
IB110/02: St 12:00–13:50 Virtuální místnost, P. Novotný
IB110/03: Po 16:00–17:50 Virtuální místnost, P. Novotný
IB110/04: St 18:00–19:50 Virtuální místnost, J. Zárevúcky
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
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. Ružomberok: Verbum, 2012, 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/podzim2021/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 2020, jaro 2022, jaro 2023, jaro 2024, jaro 2025.