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í

prof. RNDr. Tomáš Pitner, Ph.D. (přednášející)
RNDr. Libor Škarvada (přednášející)
doc. RNDr. Jiří Filipovič, Ph.D. (cvičící)
RNDr. Marek Kašík (cvičící)
doc. RNDr. Barbora Kozlíková, Ph.D. (cvičící)
RNDr. Václav Lorenc (cvičící)
doc. RNDr. Martin Maška, Ph.D. (cvičící)
doc. RNDr. Pavel Matula, Ph.D. (cvičící)
doc. Mgr. Hana Rudová, Ph.D. (cvičící)
Mgr. Adriana Strejčková (cvičící)
doc. RNDr. David Svoboda, Ph.D. (cvičící)
RNDr. Aleš Zlámal (cvičící)
Mgr. Radek Holčák (pomocník)
RNDr. Filip Andres (náhr. zkoušející)
RNDr. Lukáš Boháč (náhr. zkoušející)
RNDr. Josef Šprojcar, Ph.D. (náhr. zkoušející)

Garance

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

Rozvrh

Po 18:00–19:50 D3, Po 18:00–19:50 D1

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

IB002/01: každé sudé úterý 10:00–11:50 B011, H. Rudová
IB002/02: každé liché úterý 10:00–11:50 B011, H. Rudová
IB002/03: každé sudé úterý 18:00–19:50 B011, L. Škarvada
IB002/04: každé liché úterý 18:00–19:50 B011, L. Škarvada
IB002/05: každou sudou středu 12:00–13:50 B011, P. Matula
IB002/06: každou lichou středu 12:00–13:50 B011, P. Matula
IB002/07: každý sudý pátek 10:00–11:50 C511, D. Svoboda
IB002/08: každý lichý pátek 10:00–11:50 C511, D. Svoboda
IB002/09: každé sudé úterý 16:00–17:50 B007, M. Kašík
IB002/10: každé liché úterý 16:00–17:50 B007, M. Kašík
IB002/11: každou sudou středu 8:00–9:50 C511, M. Maška
IB002/12: každou lichou středu 8:00–9:50 C511, M. Maška
IB002/13: každý sudý čtvrtek 10:00–11:50 C511, V. Lorenc, A. Zlámal
IB002/14: každý lichý čtvrtek 10:00–11:50 C511, V. Lorenc, A. Zlámal
IB002/17: každý sudý čtvrtek 18:00–19:50 B410, B. Kozlíková
IB002/18: každý lichý čtvrtek 18:00–19:50 B410, B. Kozlíková
IB002/19: každou sudou středu 18:00–19:50 B003, A. Strejčková
IB002/20: každou lichou středu 18:00–19:50 B003, J. Filipovič

Předpoklady

Předpokládá se, že posluchači jsou schopni číst a psát elementární programy v nějakém funkcionálním a nějakém imperativním programovacím jazyce.

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)
• 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)
• Matematika pro víceoborové studium (program PřF, B-MA)
• Matematika (program PřF, B-MA)
• Obecná matematika (program PřF, B-MA)
• Profesní matematika (program PřF, B-MA)

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 a do šířky.

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

Metody hodnocení

Zkoušky jsou písemné. Dvě zkoušky budou průběžné (polosemestrální) a jedna závěrečná za celý semestr.
Účast na cvičeních je povinná, neučast je možná pouze ze závažných důvodů. Student může maximálně ve dvou případech navštívit jinou skupinu cvičení, než do které je zapsán. V tomto případě je ale povinen tuto skutečnost nahlásit cvičícímu své seminární skupiny e-mailem a zapsat se na prezenční listinu seminární skupiny, na kterou se dostaví.

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 2007, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/jaro2007/IB002