PB164 Seminář z návrhu algoritmů

Fakulta informatiky
jaro 2005
Rozsah
0/2. 2 kr. (plus ukončení). Ukončení: z.
Vyučující
Mgr. Lubomír Krejčí (cvičící)
RNDr. Aleš Zlámal (cvičící)
RNDr. Jaroslav Pelikán, Ph.D. (náhr. zkoušející)
Garance
prof. RNDr. Tomáš Pitner, Ph.D.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: Mgr. Lubomír Krejčí
Rozvrh seminárních/paralelních skupin
PB164/01: Po 14:00–15:50 B116, L. Krejčí
PB164/02: Út 10:00–11:50 B116, L. Krejčí
Předpoklady
! I065 Seminář z návrhu algoritmů I && IB001 Úvod do programování
Základní znalost strukturovaného programování v Pascalu 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
předmět má 11 mateřských oborů, zobrazit
Cíle předmětu
Předmět je zaměřen na praktické zvládnutí základních algoritmů a programovacích technik.
Osnova
  • Dynamická proměnná a její použití.
  • Dynamické datové struktury - zásobník, fronta, lineární seznam a jejich aplikace ( převod infix -> postfix, vyhodnocení výrazů, radix sort).
  • Základní algoritmy pro topologické grafové stromy - procházení do hloubky/šířky, vyhledávací stromy (BVS, AVL,...).
  • Základní algoritmy pro procházeni topologickým grafem, sledy, tahy, cesty, Eulerovy grafy, Hamiltonovy kružnice.
  • Backtracking - problém osmi dam, pohyb šachového koně.
  • Využití backtrackingu pro návrh heuristických algoritmů.
Literatura
  • 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
  • PLESNÍK, Ján. Grafové algoritmy. Vyd. 1. Bratislava: Veda, 1983, 343 s. info
Metody hodnocení
Průběh semináře : v průběhu semináře (cca po 6-tém cvičení) písemka na ověření znalostí dynamických proměnných a probraných grafových algoritmů. Během cvičení samostatná práce nad stavbou strukturovaného algoritmu řešícího jeden z nabídnutých témat nebo studentem navržený problém odsouhlasený cvičícím. Výsledny postup - řešení zadání - by měl zahrnout alespoň 30% probíraných dilčích algoritmů - bude záležet na zvoleném řešení a navrženém postupu. Od 6 cvičení průběžná diskuze nad jednotlivými řešeními studentů. Postupně každý ze studentů v 20 minutách přednese vybrané zadání a nastíni jím zvolený postup řešení. Za cvičení cca tři studenti. Předpokládá se krátká diskuze, komentář až rada od ostatních studentů nad zvoleným postupem. Přibližně polovina každého semináře bude věnována přednesu nejzákladnějších definic, vět a algoritmů, nutných pro pochopení a aplikaci probíraných postupů a neuvedených v dosud proběhlých přednáškách (především paraleně běžící přednes Návrh algoritmů I). Seminář předpokádá část samostatné práce, včetně aplikace znalostí z paralelně běžící přednášky Návrh algoritmů I. Podmínky ukončení semináře: písemka napsaná s úspěšností alespoň 50%, psaná na papír v průběhu semestru; odevzdaný program, přehledně řešící zvolené zadání, striktně vyhovující strukturovanému programování.
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 2006, jaro 2007, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013.