FI:IB110 Základy informatiky - Informace o předmětu

IB110 Základy informatiky

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/01: Út 8:00–9:50 A217, P. Novotný
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 (jaro 2024, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2024/IB110