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

IB002 Návrh algoritmů I

Rozsah

2/0. 2 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í)

Garance

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

Rozvrh

St 16:00–17:50 D1, Čt 10:00–11:50 D1

Předpoklady

! I002 Návrh algoritmů I &&! I502 Návrh algoritmů I
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 jazyku.

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)
• Informatika (program FI, M-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)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)

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.
• Třídicí algoritmy: Třídění 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í

Kurs veden formou přednášek a je ukončen závěrečnou písemnou zkouškou.

Navazující předměty

• I063 Návrh algoritmů II

Informace učitele

http://www.fi.muni.cz/usr/skarvada/vyuka/IB002/

Další komentáře

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