IB114 Úvod do programování a algoritmizace II

Fakulta informatiky
jaro 2022
Rozsah
2/1/0. 3 kr. (plus ukončení). Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Jaromír Plhák, Ph.D. (cvičící)
Garance
prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 15. 2. až Út 10. 5. Út 16:00–17:50 D1
  • Rozvrh seminárních/paralelních skupin:
IB114/01: St 16. 2. až St 11. 5. každou lichou středu 8:00–9:50 B411, J. Plhák
IB114/02: St 23. 2. až St 4. 5. každou sudou středu 8:00–9:50 B411, J. Plhák
IB114/03: St 16. 2. až St 11. 5. každou lichou středu 10:00–11:50 A320, J. Plhák
IB114/04: St 23. 2. až St 4. 5. každou sudou středu 10:00–11:50 A320, J. Plhák
Předpoklady
( IB111 Základy programování || IB113 Úvod do progr. a algoritmizace ) && ! IB002 Algoritmy a datové struktury && !NOW( IB002 Algoritmy a datové struktury )
Předmět je určen primárně studentům, kteří mají Informatiku jako vedlejší obor a studentům bakalářského studijního programu Kyberbezpečnost. Studenti bakalářských studijních programů Informatika a Programování a vývoj aplikací zapisují předmět IB002.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 80 stud.
Momentální stav registrace a zápisu: zapsáno: 26/80, pouze zareg.: 0/80, pouze zareg. s předností (mateřské obory): 0/80
Mateřské obory/plány
Cíle předmětu
Cílem kurzu je získat dovednosti v používání základních datových struktur a algoritmů a zároveň schopnost navrhovat a analyzovat jednoduché algoritmy. Současně studenti rozvíjejí své dovednosti v implementaci navržených algoritmů v konkrétním programovacím jazyce (Python).
Výstupy z učení
Student bude po absolvování předmětu schopen:
- aktivně používat základní algoritmy pro řazení a pro průzkum grafů,
- aktivně navrhovat jednoduché algoritmy,
- aktivně používat základní statické a dynamické datové struktury,
- pracovat s pojmy časové složitosti a korektnosti algoritmů,
- implementovat jednoduché algoritmy ve vyučovaném programovacím jazyce (Python).
Osnova
  • Základy analýzy algoritmů. Korektnost algoritmu, vstupní a výstupní podmínky, parciální korektnost, konvergence, verifikace. Délka výpočtu, složitost algoritmu, složitost problému. Asymptotická analýza časové a prostorové složitosti, růst funkcí.
  • Fundamentální datové struktury. Seznamy, fronty. Representace množin, hašovací tabulky. Binární haldy. Binární vyhledávací stromy.
  • Řadicí algoritmy. Řazení rozdělováním, slučováním, haldou.
  • Základní grafové algoritmy: Representace grafů. Procházení grafu do hloubky a do šířky, aplikace prohledávácích algoritmů.
Literatura
    doporučená literatura
  • CORMEN, Thomas H. Introduction to algorithms. 3rd ed. Cambridge, Mass.: MIT Press, 2009, xix, 1292. ISBN 9780262533058. URL info
Výukové metody
Kurs probíhá formou přednášek a cvičení k přednáškám.
Metody hodnocení
Závěrečná písemná zkouška na konci semestru. Podmínkou účasti na závěrečné zkoušce je splnění průběžného hodnocení z cvičení, které se skládá z pravidelných písemných testů. Podrobnosti jsou zveřejněny v Interaktivní osnově předmětu https://is.muni.cz/auth/el/1433/jaro2021/IB114/index.qwarp
Informace učitele
https://is.muni.cz/auth/el/1433/jaro2021/IB114/index.qwarp
Další komentáře
Studijní materiály
Předmět je vyučován každoročně.
Nachází se v prerekvizitách jiných předmětů
Předmět je zařazen také v obdobích jaro 2020, jaro 2021, jaro 2023, jaro 2024, jaro 2025.