FI:IB002 Algoritmy a datové struktury - Informace o předmětu

IB002 Algoritmy a datové struktury I

Rozsah

2/2. 4 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

Ing. Mgr. et Mgr. Zdeněk Říha, Ph.D. (přednášející)
RNDr. Libor Škarvada (přednášející)
Mgr. Miroslav Buda (cvičící)
Mgr. et Mgr. Martin Derka, M.Sc. (cvičící)
RNDr. Pavel Karas, Ph.D. (cvičící)
Mgr. Marek Klučár (cvičící)
Mgr. Matúš Madzin (cvičící)
doc. RNDr. David Svoboda, Ph.D. (cvičící)
RNDr. Martin Ukrop, Ph.D. (cvičící)
RNDr. Vladimír Ulman, Ph.D. (cvičící)
Mgr. Matej Kollár (pomocník)
Mgr. Eva Mráková, Ph.D. (pomocník)
doc. RNDr. Vojtěch Řehák, Ph.D. (pomocník)
Mgr. et Mgr. Tomáš Sklenák (pomocník)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: RNDr. Libor Škarvada
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 16:00–17:50 D2, Po 16:00–17:50 D1, Po 16:00–17:50 D3

• Rozvrh seminárních/paralelních skupin:

IB002/T01: Po 10:00–12:00 Učebna S6 (20), Čt 10:00–11:55 Učebna S11 (58), M. Derka, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB002/T02: St 16:00–17:55 Učebna S11 (58), M. Klučár, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB002/T03: Čt 16:00–17:55 Učebna S4 (35a), L. Škarvada, Nepřihlašuje se. Určeno pro studenty se zdravotním postižením.
IB002/T04: Po 18. 2. až Ne 19. 5. Čt 13:00–14:40 Učebna S8 (17), D. Svoboda
IB002/01: Čt 8:00–9:50 B311, D. Svoboda
IB002/02: Po 14:00–15:50 B130, M. Ukrop
IB002/03: Čt 18:00–19:50 B204, M. Ukrop
IB002/04: Čt 16:00–17:50 B130, M. Ukrop
IB002/05: St 8:00–9:50 B130, M. Klučár
IB002/06: St 10:00–11:50 B130, M. Klučár
IB002/07: St 14:00–15:50 B130, M. Klučár
IB002/08: St 10:00–11:50 G126, M. Derka
IB002/09: St 12:00–13:50 G126, M. Derka
IB002/10: Čt 10:00–11:50 G126, M. Madzin
IB002/11: Út 8:00–9:50 G101, V. Ulman
IB002/12: Út 10:00–11:50 G101, V. Ulman
IB002/13: Čt 8:00–9:50 G101, M. Madzin
IB002/14: Út 16:00–17:50 B204, M. Buda
IB002/15: Út 14:00–15:50 B130, M. Buda
IB002/16: Čt 14:00–15:50 B204, M. Buda
IB002/17: Čt 16:00–17:50 B204, P. Karas
IB002/18: Čt 14:00–15:50 B130, P. Karas
IB002/19: Út 18:00–19:50 B204

Předpoklady

Předpokládá se, že posluchači alespoň na intuitivní úrovni rozumějí základním pojmům algoritmus, výpočet, datová struktura a podobným.

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

• Aplikovaná informatika (program FI, B-AP)
• Bioinformatika (program FI, B-AP)
• Ekonomické informační systémy (program ESF, B-SI)
• Informatika a druhý obor (program FI, B-EB)
• Informatika a druhý obor (program FI, B-FY)
• Informatika a druhý obor (program FI, B-IO)
• Informatika a druhý obor (program FI, B-MA)
• Informatika a druhý obor (program FI, B-TV)
• Informatika ve veřejné správě (program FI, B-AP)
• Matematická informatika (program FI, B-IN)
• Obecná matematika (program PřF, B-MA)
• Paralelní a distribuované systémy (program FI, B-IN)
• Počítačová grafika a zpracování obrazu (program FI, B-IN)
• Počítačové sítě a komunikace (program FI, B-IN)
• Počítačové systémy a zpracování dat (program FI, B-IN)
• Programovatelné technické struktury (program FI, B-IN)
• Programovatelné technické struktury (program FI, N-IN)
• Služby - výzkum, řízení a inovace (program FI, N-AP)
• Sociální informatika (program FI, B-AP)
• Umělá inteligence a zpracování přirozeného jazyka (program FI, B-IN)

Cíle předmětu

Kurs probírá základní techniky analýzy algoritmů, datové struktury a operace nad nimi.

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í, využití rekurentních relací při analýze algoritmů.
• Fundamentální datové struktury: Seznamy, fronty. Binární haldy, representace množin. Binární vyhledávací stromy, vyvážené stromy.
• Řadicí algoritmy: Řazení rozdělováním, slučováním, haldou, dolní odhad složitosti.
• Základní grafové algoritmy: Representace grafů. Procházení grafu do hloubky, zúplnění uspořádání, silně souvislé komponenty. Procházení grafu do šířky, Dijkstrův algoritmus. Minimální kostry grafu.

Literatura

• SKIENA, Steven S. The algorithm design manual. New York: Springer, 1998, xvi, 486. ISBN 0387948600. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info

Výukové metody

Kurs probíhá formou přednášek a cvičení k přenáškám.

Metody hodnocení

Zkouška je má tři části -- test v polovině semestru, praktický test na jeho konci a závěrečnou písemnou zkoušku.

Navazující předměty

• I063 Návrh algoritmů II

Informace učitele

http://www.fi.muni.cz/~libor/vyuka/IB002/

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ů

• IB114 Úvod do programování a algoritmizace II
  (IB111 || IB113) && !IB002 && !NOW(IB002)  
• IV003 Algorithms and Data Structures II
  IB002 || program(PřF:N-MA)  
• IV100 Paralelní a distribuované výpočty
  IB002  
• MA015 Graph Algorithms
  IB002||(typ_studia(N)&&fakulta(fi))  

• Statistika zápisu (jaro 2013, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2013/IB002