IB110 Základy informatiky

Fakulta informatiky
jaro 2025
Rozsah
2/2/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně
Vyučující
doc. RNDr. Petr Novotný, Ph.D. (přednášející)
Mgr. Jakub Balabán (cvičící)
RNDr. Mgr. Jana Dražanová, Ph.D. (cvičící)
Bc. Tereza Kinská (cvičící)
Vojtěch Skyba (cvičící)
Bc. Adéla Štěpková (cvičící)
Bc. Dávid Šutor (cvičící)
Bc. Matěj Pavlík (pomocník)
Garance
doc. 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
Předmět je určen studentům mateřských programů. Studenti programu Informatika si zapisují plné předměty IB005 a IB107. Studenti, kteří absolvovali oba plné předměty, si mohou nechat IB110 uznat.
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 (vypracování domácích odpovědníků).
Informace učitele
https://is.muni.cz/auth/el/1433/jaro2023/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.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2025/IB110