I063 Návrh algoritmů II

Fakulta informatiky
jaro 2004
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 10:00–11:50 D2
Předpoklady
SOUHLAS
.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Teoretické základy, aplikace.
  • Metody návrhu aproximativních algoritmů -- sekvenční metody, lokální vyhledávání, linerární programování. Aplikace.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace.
  • Metody návrhu on-line algoritmů. Srovnávací analýza. Náhodnostní on-line algoritmy.
Literatura
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Metody hodnocení
Predmet sa otvara posledny krat a je urceny studentom, ktori mali zapisany predmet I063 semestri ja studiaro 2003, ale v tomto semestri predmet neukoncili. Vyuka sa bude konat formou indiviualneho studia.
Další komentáře
Předmět je vyučován naposledy.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2003.

I063 Návrh algoritmů II

Fakulta informatiky
jaro 2003
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
doc. Ing. RNDr. Barbora Bühnová, Ph.D. (pomocník)
Mgr. Tomáš Hanžl (pomocník)
RNDr. Lukáš Hejtmánek, Ph.D. (pomocník)
Mgr. Pavel Krčál (pomocník)
Mgr. Petr Liška (pomocník)
Mgr. Pavel Moravec (pomocník)
doc. Mgr. Adam Rogalewicz, Ph.D. (pomocník)
Mgr. Jitka Žídková (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Rozvrh
Út 8:00–9:50 D1
Předpoklady
( I002 Návrh algoritmů I || IB002 Návrh algoritmů I )&&! IB108 Návrh algoritmů II &&(!NOW( IB108 Návrh algoritmů II ))
Kurz je určen studentům 5-letého magisterského studia a v jarním semestru 2002/03 se otevírá naposledy.
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Teoretické základy, aplikace.
  • Metody návrhu aproximativních algoritmů -- sekvenční metody, lokální vyhledávání, linerární programování. Aplikace.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace.
  • Metody návrhu on-line algoritmů. Srovnávací analýza. Náhodnostní on-line algoritmy.
Literatura
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Informace učitele
http://www.fi.muni.cz/usr/cerna/NAII/i063.html
Další komentáře
Předmět je vyučován naposledy.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2004.

I063 Návrh algoritmů II

Fakulta informatiky
jaro 2002
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. Ivana Černá, CSc. (přednášející)
Mgr. Pavel Krčál (pomocník)
doc. Mgr. Radek Pelánek, Ph.D. (pomocník)
doc. Mgr. Adam Rogalewicz, Ph.D. (pomocník)
Mgr. Jitka Žídková (pomocník)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Rozvrh
St 10:00–11:50 D2
Předpoklady
I002 Návrh algoritmů I && M010 Kombinatorika a grafy
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Teoretické základy, aplikace.
  • Metody návrhu aproximativních algoritmů -- sekvenční metody, lokální vyhledávání, linerární programování. Aplikace.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace.
  • Metody návrhu on-line algoritmů. Srovnávací analýza. Náhodnostní on-line algoritmy.
Literatura
  • Brassard,G.- Bratley,P. Fundamentals of algorithmics. Prentice Hall, 1996
  • Cormen,T.H. - Leiserson,C.E. - Rivest,R.L. Introduction to algorithms. MIT Press, 1990
  • Kozen, D. The Design and Analysis of Algorithms. Springer-Verlag, 1992
  • Motwani,R. - Raghavan,P. Randomized algorithms. Cambridge University Press, 1995
Informace učitele
http://www.fi.muni.cz/usr/cerna/i063.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000, jaro 2001, jaro 2003, jaro 2004.

I063 Návrh algoritmů II

Fakulta informatiky
jaro 2001
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. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Rozvrh
Po 9:00–10:50 D2
Předpoklady
I002 Návrh algoritmů I && M010 Kombinatorika a grafy
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Obecná formulace, aplikace, teoretické základy.
  • Metody návrhu aproximativních algoritmů -- relativní aproximace a aproximativní schémy. Aplikace: pokrytí grafu, obchodní cestující, rozvrhování, pokrytí množin, vyhledávaní řetězů.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace: vyhledávací stromy, nezávislé množiny.
  • Metody návrhu on-line algoritmů. Srovnávací analýza on-line algoritmů. Náhodnostní on-line algoritmy. Aplikace: stránkování, obsluha procesorů
Literatura
  • BRASSARD, Gilles a Paul BRATLEY. Fundamentals of algorithmics. London: Prentice-Hall International, 1996, xix, 524 s. ISBN 0-13-073487-X. info
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
  • KOZEN, Dexter C. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992, 320 s. ISBN 0387976876. info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Informace učitele
http://www.fi.muni.cz/usr/cerna/i063.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2000, jaro 2002, jaro 2003, jaro 2004.

I063 Návrh algoritmů II

Fakulta informatiky
jaro 2000
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. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Předpoklady
I002 Návrh algoritmů I && M010 Kombinatorika a grafy
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda.
  • Návrh a využití efektivních datových struktur. Binomiální a Fibonacciho haldy. Balancované vyhledávací stromy. Množinové datové struktury.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, hladové algoritmy, prohledávání. Obecná formulace, aplikace, teoretické základy.
  • Metody návrhu aproximativních algoritmů -- relativní aproximace a aproximativní schémy. Aplikace: pokrytí grafu, obchodní cestující, rozvrhování, pokrytí množin, vyhledávaní řetězů.
  • Metody návrhu pravděpodobnostních algoritmů -- náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Derandomizace. Aplikace: vyhledávací stromy, nezávislé množiny.
  • Metody návrhu on-line algoritmů. Srovnávací analýza on-line algoritmů. Náhodnostní on-line algoritmy. Aplikace: stránkování, obsluha procesorů
Literatura
  • BRASSARD, Gilles a Paul BRATLEY. Fundamentals of algorithmics. London: Prentice-Hall International, 1996, xix, 524 s. ISBN 0-13-073487-X. info
  • MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
  • KOZEN, Dexter C. The Design and Analysis of Algorithms. New York: Springer-Verlag, 1992, 320 s. ISBN 0387976876. info
  • CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Informace učitele
http://www.fi.muni.cz/usr/cerna/i063.html
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 1999, jaro 2001, jaro 2002, jaro 2003, jaro 2004.

I063 Návrh algoritmů II

Fakulta informatiky
jaro 1999
Rozsah
2/0. 2 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Předpoklady
I002 Návrh algoritmů I && M010 Kombinatorika a grafy
Podmínkou pro zápis je absolvování kursů I002 Návrh algoritmů I a M010 Kombinatorika a teorie grafů.
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda. Aplikace a využití při návrhu efektivních datových struktur.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, greedy algoritmy. Obecná formulace, aplikace, teoretické základy.
  • Efektivní algoritmy -- polynomy (Fourieova trnasformace), vyhledávaní řetězů (algoritmy Knuth-Morris-Pratt, Boyer-Moore).
  • Metody návrhu pravděpodobnostních algoritmů -- očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Příklady.
  • Metody návrhu aproximativních algoritmů -- relativní aproximace a aproximativní schémy. Aplikace: pokrytí grafu, obchodní cestující, rozvrhování, pokrytí množin, vyhledávaní řetězů.
  • On-line algoritmy. Metody analýzy jejich složitosti -- potenciálové funkce, minimax princip. Příklady.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i063.html
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích léto 1998, jaro 2000, jaro 2001, jaro 2002, jaro 2003, jaro 2004.

I063 Návrh algoritmů II

Fakulta informatiky
léto 1998
Rozsah
2/0. 2 kr. Doporučované ukončení: zk. Jiná možná ukončení: k, z.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Předpoklady
Podmínkou pro zápis je absolvování kursů I002 Návrh algoritmů I a M010 Kombinatorika a teorie grafů.
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
Osnova
  • Složitost algoritmů -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
  • Metody analýzy složitosti algoritmů -- shluková technika, technika účtů, potenciálová metoda. Aplikace a využití při návrhu efektivních datových struktur.
  • Techniky návrhu efektivních algoritmů -- divide et impera, dynamické programování, greedy algoritmy. Obecná formulace, aplikace, teoretické základy.
  • Efektivní algoritmy -- polynomy (Fourieova trnasformace), vyhledávaní řetězů (algoritmy Knuth-Morris-Pratt, Boyer-Moore).
  • Metody návrhu pravděpodobnostních algoritmů -- očekávaná vs. průměrná složitost. Algoritmy Las Vegas a Monte Carlo. Náhodné přeuspořádaní, náhodné vyhledávaní, balancování. Příklady.
  • Metody návrhu aproximativních algoritmů -- relativní aproximace a aproximativní schémy. Aplikace: pokrytí grafu, obchodní cestující, rozvrhování, pokrytí množin, vyhledávaní řetězů.
  • On-line algoritmy. Metody analýzy jejich složitosti -- potenciálové funkce, minimax princip. Příklady.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i063.html
Předmět je zařazen také v obdobích jaro 1999, jaro 2000, jaro 2001, jaro 2002, jaro 2003, jaro 2004.