FI:IB002 Návrh algoritmů I - Informace o předmětu
IB002 Návrh algoritmů I
Fakulta informatikyjaro 2003
- 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
- Út 10:00–11:50 D1, Út 18:00–19: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
- 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-IN)
- 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. Hašovací tabulky. 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
- 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
- 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
fi/IB002">IB002||(typ_studia(N)&&fakulta(fi))
- IB114 Úvod do programování a algoritmizace II
- Statistika zápisu (jaro 2003, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2003/IB002