FI:IB002 Návrh algoritmů I - Informace o předmětu

IB002 Návrh algoritmů I

Rozsah

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

Vyučující

RNDr. Libor Škarvada (přednášející)
Mgr. Miroslav Buda (cvičící)
Mgr. Bc. Matúš Goljer (cvičící)
Mgr. Matej Kollár (cvičící)
RNDr. Štěpán Kozák (cvičící)
Mgr. Matúš Madzin (cvičící)
Mgr. Josef Pacula (cvičící)
Oldřich Petr (cvičící)
doc. RNDr. David Svoboda, Ph.D. (cvičící)
Mgr. Marek Trtík, Ph.D. (cvičící)
Mgr. Radek Holčák (pomocník)

Garance

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

Rozvrh

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

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

IB002/01: každý sudý pátek 8:00–9:50 C525, D. Svoboda
IB002/02: každý lichý pátek 8:00–9:50 C525, D. Svoboda
IB002/03: každou sudou středu 14:00–15:50 G123, M. Trtík
IB002/04: každou lichou středu 14:00–15:50 G123, M. Trtík
IB002/05: každé sudé úterý 18:00–19:50 G123, Š. Kozák
IB002/06: každé liché úterý 18:00–19:50 G123, Š. Kozák
IB002/07: každou sudou středu 16:00–17:50 G123, J. Pacula
IB002/08: každou lichou středu 16:00–17:50 G123, J. Pacula
IB002/09: každé sudé úterý 16:00–17:50 G123, M. Kollár
IB002/10: každé liché úterý 16:00–17:50 G123, M. Kollár
IB002/11: každé sudé úterý 8:00–9:50 G123, M. Goljer
IB002/12: každé liché úterý 8:00–9:50 G123, M. Goljer
IB002/13: každý sudý čtvrtek 10:00–11:50 G123, M. Buda
IB002/14: každý lichý čtvrtek 10:00–11:50 G123, M. Buda
IB002/15: každý sudý čtvrtek 12:00–13:50 G123, M. Madzin
IB002/16: každý lichý čtvrtek 12:00–13:50 G123, M. Madzin
IB002/17: každé sudé úterý 16:00–17:50 G101, Š. Kozák
IB002/18: každé liché úterý 16:00–17:50 G101, Š. Kozák
IB002/19: každou sudou středu 12:00–13:50 G123, M. Trtík
IB002/20: každou lichou středu 12:00–13:50 G123, M. Trtík
IB002/21: každou sudou středu 18:00–19:50 G123, J. Pacula
IB002/22: každou lichou středu 18:00–19:50 G123, J. Pacula

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 že se již setkali se zápisem algoritmů v imperativním i funkcionálním stylu.

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-BI)
• Informatika a druhý obor (program FI, B-FY)
• Informatika a druhý obor (program FI, B-GE)
• Informatika a druhý obor (program FI, B-GK)
• Informatika a druhý obor (program FI, B-CH)
• Informatika a druhý obor (program FI, B-IO)
• Informatika a druhý obor (program FI, B-MA)
• Informatika a druhý obor (program FI, B-SO)
• Informatika a druhý obor (program FI, B-TV)
• Informatika (program FI, B-IN)
• Informatika ve veřejné správě (program FI, B-AP)
• Matematická informatika (program FI, B-IN)
• Matematika pro víceoborové studium (program PřF, B-MA)
• Matematika (program PřF, B-MA)
• 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)
• Profesní matematika (program PřF, B-MA)
• 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. Zaměřuje se na dokazování korektnosti algoritmů a na jejich efektivnost. Základní algoritmické pojmy a konstrukce jsou uváděny bez přímé návaznosti na konkrétní programovací jazyk a bez požadavků na jejich praktickou programovou realizaci. Cílem je naučit studenta pracovat s vlastními algoritmy oproštěnými od implementačních detailů. To dovoluje presentovat poměrně široký záběr technik, používaných ve funkcionálním, imperativním i v objektově orientovaném programování.

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, zásobníky a fronty. Binární vyhledávací stromy, vyvážené stromy, representace množin.
• Ř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 písemná a má dvě části -- v polovině semestru a na jeho konci.

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
  fi/IB002">IB002||(typ_studia(N)&&fakulta(fi))  

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