IB110 Základy informatiky

Fakulta informatiky
jaro 2023
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno prezenčně.
Vyučující
RNDr. Petr Novotný, Ph.D. (přednášející)
Bc. Jakub Balabán (cvičící)
Matej Focko (cvičící)
Bc. Matěj Pavlík (cvičící)
RNDr. Eva Šmijáková (cvičící)
Dávid Šutor (cvičící)
Garance
RNDr. Petr Novotný, Ph.D.
Katedra teorie programování - Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování - Fakulta informatiky
Předpoklady
! IB005 FJA || ! IB107 Vyčíslitelnost a složitost
žá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. 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
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.