Informace o předmětu

IA101 Algoritmika pro těžké problémy

Rozsah

2/0/0. 2 kr. (plus ukončení). Ukončení: zk.
Vyučováno kontaktně

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 25. 9. až St 18. 12. St 8:00–9:50 B411

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 29 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2024/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Čt 12:00–13:50 A218

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 54 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 14:00–15:50 A218

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 54 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 15. 9. až St 8. 12. St 12:00–13:50 A217

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 53 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Čt 14:00–15:50 A217

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 53 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Jaroslav Bendík, Ph.D. (pomocník)

Garance

prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Čt 10:00–11:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 53 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Čt 10:00–11:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 24 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Čt 10:00–11:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 24 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- identifikovat algoritmicky těžké problémy,
- identifikovat oblasti, ve kterých je možné použít pseudopolynomiální, aproximativní, pravděpodobnostné a heuristické algoritmy,
- aktívně používat dostupné pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy a správně interpretovat jejich výstupy,
- navrhovat jednoduché pseudopolynomiální, aproximativní a pravděpodobnostné algoritmy,
- experimentálně evaluovat performanci heuristických algoritmů.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

neurčeno
• KLEINBERG, Jon a Éva TARDOS. Algorithm design. Boston: Pearson/Addison-Wesley, 2006, xxiii, 838. ISBN 0321372913. URL info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2017/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

St 18:00–19:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 24 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2014/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Út 12:00–13:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 24 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2014/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 12:00–13:50 D2

Předpoklady

Předpokladem jsou znalosti základních technik pro návrh algoritmů (rekurze, dynamické programování, hladové techniky), datových struktur a algoritmů (v rozsahu předmětů IB002 a IV003).

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

předmět má 23 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické techniky: pseudopolynomiální algoritmy, parametrizované algoritmy, branch--and--bound, exponenciální algoritmy.
• Aproximativní přístup: koncept aproximativního algoritmu, klasifikace aproximatívních algoritmů, stabilita aproximatívních algoritmů, neaproximovatelnost. Techniky návrhu aproximatívních algoritmů. Využití principů dynamického programování a hladových techník. Techniky využívající redukci na úlohu lineárního programování. Kombinatorické přístupy.
• Náhodnostní přístup: klasifikace a paradigmata náhodnostních agoritmů. Techniky návrhu náhodnostních algoritmů. Derandomizace. Kombinace aproximativních a náhodnostních technik.
• Heuristiky: lokální vyhledávání, simulované žíhání, genetické algoritmy.

Literatura

doporučená literatura
• D. Williansom, D. Shmoys. The Design of Approximation Algorithms. Cambridge, 2011
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info
• CORMEN, Thomas H., Charles Eric LEISERSON a Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1989, xvii, 1028. ISBN 0070131430. info
• COOK, William. In pursuit of the traveling salesman : mathematics at the limits of computation. Princeton: Princeton University Press, 2012, xiii, 228. ISBN 9780691152707. info
• CHVÁTAL, Václav. Linear programming. New York: W.H. Freeman, 1983, xiii, 478. ISBN 0716715872. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/el/1433/podzim2014/IA101/index.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Nikola Beneš, Ph.D. (pomocník)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 14:00–15:50 D2

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

předmět má 23 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Algoritmy a datové struktury I a Algoritmy a datové struktury II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné způsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2010%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Nikola Beneš, Ph.D. (pomocník)

Garance

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky

Rozvrh

Po 14:00–15:50 D2

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

předmět má 23 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2010%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
Mgr. Sven Dražan (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

Po 14:00–15:50 D2

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

předmět má 23 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2010%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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 14:00–15:50 D2

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

předmět má 26 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2010%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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 14:00–15:50 D3

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

předmět má 26 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Výukové metody

teoretická výuka doplněna individuálním procvičováním probíraných návrhových technik

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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 14:00–15:50 D2

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

předmět má 19 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Metody hodnocení

Pisemna zkouska na konci semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
Mgr. Jiří Šimša (cvičí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 14:00–15:50 D2

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

předmět má 20 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001
• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001

Metody hodnocení

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
Mgr. Jiří Šimša (cvičí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 12:00–13:50 D1

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

předmět má 7 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001
• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001

Metody hodnocení

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Informace učitele

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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 12:00–13:50 D3

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

předmět má 7 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001
• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001

Metody hodnocení

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Algoritmika/ia101.html

Další komentáře

Studijní materiály
Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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 8:00–9:50 D2

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

předmět má 7 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001
• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001

Metody hodnocení

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Algoritmika/ia101.html

Další komentáře

Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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

Út 8:00–9:50 B204

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

předmět má 6 mateřských oborů, zobrazit

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001
• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001

Metody hodnocení

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Algoritmika/ia101.html

Další komentáře

Předmět je vyučován každoročně.

IA101 Algoritmika pro těžké problémy

Předmět se v období podzim 2002 nevypisuje.

Rozsah

2/0. 2 kr. (plus ukončení). Ukončení: zk.

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.

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, N-AP)
• Informatika (program FI, M-IN)
• Informatika (program FI, N-IN)

Cíle předmětu

Kurz je volným pokračováním bakalářských kurzů Návrh algoritmů I a Návrh algoritmů II. Prezentuje algoritmické koncepty a konstrukty pro těžké výpočetní úlohy. Systematicky vysvětluje, kombinuje a srovnává možné spůsoby atakování těžkých problémů, jakými jsou randomizace, heuristiky, aproximace a lokální vyhledávání.

Osnova

• Deterministické přístupy: Pseudo--polynomiální algoritmy, parametrizovaná složitost, branch--and--bound, snižování složitosti nejhoršího případu pro exponenciální algoritmy, lokální vyhledávání, relaxace lineárního programování.
• Aproximativní přístupy: koncept aproximativního algoritmu, klasifikace aproximativních algoritmů, stabilita aproximativních algoritmů, neaproximovatelnost. Techniky návrhu aproximativních algoritmů.
• Randomizované přístupy: klasifikace randomizovaných algoritmů a paradigmata jejich návrhu. Techniky návrhu randomizovaných algoritmů. Derandomizace.
• Heuristické přístupy: simulované žíhání, genetické algoritmy.

Literatura

• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001
• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev a Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info

Další komentáře

Předmět je vyučován každoročně.
Výuka probíhá každý týden.

• Statistika zápisu (nejnovější)