FI:IB110 Základy informatiky - Informace o předmětu
IB110 Základy informatiky
Fakulta informatikyjaro 2024
- 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í)
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 - Rozvrh
- Po 12:00–13:50 D1
- Rozvrh seminárních/paralelních skupin:
IB110/02: Út 10:00–11:50 A217, P. Novotný
IB110/03: Čt 8:00–9:50 C511, J. Dražanová
IB110/04: Čt 10:00–11:50 C511, J. Dražanová
IB110/05: Čt 18:00–19:50 C511, V. Skyba
IB110/06: Po 18:00–19:50 C525, V. Skyba
IB110/07: St 12:00–13:50 A320, T. Kinská
IB110/08: St 18:00–19:50 B204, T. Kinská
IB110/09: Čt 12:00–13:50 C511, A. Štěpková
IB110/10: Po 18:00–19:50 C511, D. Šutor
IB110/11: St 12:00–13:50 A318, J. Balabán - 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/jaro2023/IB110/index.qwarp
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2024/IB110