PB164 Seminář z návrhu algoritmů

Fakulta informatiky
jaro 2006
Rozsah
0/2. 2 kr. (plus ukončení). Ukončení: z.
Vyučující
Mgr. Lubomír Krejčí (přednášející)
RNDr. Aleš Zlámal (cvičící)
RNDr. Jaroslav Pelikán, Ph.D. (náhr. zkoušející)
Garance
prof. RNDr. Václav Matyáš, M.Sc., Ph.D.
Katedra počítačových systémů a komunikací – Fakulta informatiky
Kontaktní osoba: Mgr. Lubomír Krejčí
Rozvrh seminárních/paralelních skupin
PB164/01: Po 12:00–13:50 B117, L. Krejčí
PB164/02: Po 14:00–15:50 B117, L. Krejčí
Předpoklady
IB001 Úvod do programování
Základní znalost strukturovaného programování a stavby algoritmu přibližně na úrovni úspěšného ukončení předmětu IB001 Úvod do programování skrze C.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.

Předmět si smí zapsat nejvýše 60 stud.
Momentální stav registrace a zápisu: zapsáno: 0/60, pouze zareg.: 0/60
Mateřské obory/plány
Cíle předmětu
Předmět je zaměřen na praktické zvládnutí implementace základních algoritmů a programovacích technik s důrazem na využití dynamické proměnné a aplikace teorie grafů
Osnova
  • Dynamická proměnná a její použití
  • Implementace základních dynamických datových struktur - zásobník, fronta, lineární seznam a jejich aplikace (převod infix - postfix, vyhodnocení výrazů, radix sort).
  • základní postupy pro implementaci topologického grafu - matice incidence a dynamické seznamy. Stavba jednoduchého grafového editoru se schopností vizualizace topologického grafu. Převod dynamické reprezentace topologického grafu na matici incidence a naopak.
  • Implementace základních algoritmů pro topologický graf - procházení souvislého topologického grafu do hloubky, do šířky, generování a nalezení sledu, tahu a cesty mezi dvěma uzly v souvislém topologickém grafu. Nalezení komponenty nesouvislého grafu.
  • Cesty v grafech - implementace algoritmů pro nalezení nejkratších cest mezi uzly grafu (Dikstrův algoritmus, maticové aplikace)
  • Kostry v grafech - implementace algoritmů pro nalezení libovolné a minimální kostry grafu (Borůvka/Kruskal, Jarník/Prim)
  • Toky v sítích - implementace Ford-Fulkersononova algoritmu pro nalezení maximálního toku v síti
  • Tahy a kružnice - implementace algoritmu pro nalezení Eulerovského tahu a Hamiltonovy kružice v souvislém topologickém grafu - úloha obchodního cestujícího a čínského pošťáka
  • Kořenové stromy - implementace kořenových stromů (BVS, AVL, vkládání a odebírání prvků, rotace).
  • Možná něco navíc - nejkrásnější nakreslení grafu, barvení grafu, minory grafu.
Literatura
  • DEMEL, Jiří. Grafy a jejich aplikace. Vyd. 1. Praha: Academia, 2002, 257 s. ISBN 8020009906. info
  • TÖPFER, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha: Prometheus, 1995, 299 s. ISBN 80-85849-83-6. info
  • LIBICHER, Ivan a Pavel TÖPFER. Od problému k algoritmu a programu :sbírka řešených úloh z programování. 1. vyd. Praha: Grada, 1992, 119 s. ISBN 80-85424-82-7. info
  • KUČERA, Luděk. Kombinatorické algoritmy. 2., nezměn. vyd. Praha: SNTL - Nakladatelství technické literatury, 1989, 286 s. info
  • DEMEL, Jiří. Grafy. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1988, 180 s. info
  • PLESNÍK, Ján. Grafové algoritmy. Vyd. 1. Bratislava: Veda, 1983, 343 s. info
  • DEMEL, Jiří. Teorie grafů. Vyd. 1. Praha: Ediční středisko ČVUT, 1982, 198 s. info
Metody hodnocení
Seminář bude zaměřen na praktické zvládnutí implementace základních dynamických struktur a zakladních algoritmů teorie grafů. Cílem semináře bude praktická implementace uvedených algoritmů v libovolně zvoleném programovacím jazyku. Přibližně polovina každého semináře bude věnována přednesu konkrétního postupu a vysvětlení algoritmu Seminář předpokládá část samostatné práce, včetně případné aplikace znalostí z paralelně běžící přednášky Návrh algoritmů I. Podmínky ukončení semináře: Odevzdaný programový balík, přehledně demonstrující probírané algoritmy.
Informace učitele
http://www.fi.muni.cz/~lkrejci/
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2007, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013.