FI:IB110 Základy informatiky - Informace o předmětu
IB110 Základy informatiky
Fakulta informatikyjaro 2022
- 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. Jakub Balabán (cvičící)
Bc. Matej Focko (cvičící)
Bc. Matěj Pavlík (cvičící)
RNDr. Eva Šmijáková (cvičící)
Bc. Dávid Šutor (cvičící)
Zbyněk Cincibus (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
- St 16. 2. až St 11. 5. St 10:00–11:50 D3
- Rozvrh seminárních/paralelních skupin:
IB110/02: Čt 17. 2. až Čt 12. 5. Čt 16:00–17:50 A320, M. Pavlík
IB110/03: Po 14. 2. až Po 9. 5. Po 16:00–17:50 A319, M. Pavlík
IB110/04: Po 14. 2. až Po 9. 5. Po 14:00–15:50 A319, M. Pavlík
IB110/05: St 16. 2. až St 11. 5. St 14:00–15:50 C416, E. Šmijáková
IB110/06: Čt 17. 2. až Čt 12. 5. Čt 12:00–13:50 B204, J. Balabán
IB110/07: Po 14. 2. až Po 9. 5. Po 18:00–19:50 C525, M. Focko
IB110/08: Út 15. 2. až Út 10. 5. Út 12:00–13:50 C416, D. Šutor - 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/jaro2022/IB110/index.qwarp
- Další komentáře
- Předmět je vyučován každoročně.
- Statistika zápisu (jaro 2022, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2022/IB110