Informace o předmětu

IA012 Složitost

Rozsah

2/0/1. 3 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 14:00–15:50 B411

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

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

Další komentáře

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

IA012 Složitost

Rozsah

2/0/1. 3 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 12:00–13:50 A318

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 49 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

Rozsah

2/0/1. 3 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 A218

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 49 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

Rozsah

2/0/1. 3 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. 9. až Út 7. 12. Út 14:00–15:50 A218

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 48 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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ředpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 48 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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 16:00–17:50 D2

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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ředpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

Rozsah

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

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)
RNDr. Mária Svoreňová, 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

Čt 14:00–15:50 D2

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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)
RNDr. Mária Svoreňová, 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

Čt 14:00–15:50 D2

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 18 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

Rozsah

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

Vyučující

RNDr. Nikola Beneš, Ph.D. (přednášejí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 B411

Předpoklady

SOUHLAS
V semestru "jaro 2014" předmět výjimečně běží v omezeném režimu. V tomto semestru je předmět určen pouze těm, kteří jej nezbytně potřebují k dokončení studia. Ostatní zájemci o předmět prosíme, aby si předmět zapsali v semestru "jaro 2015", kdy předmět poběží ve standardní podobě.
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 18 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2014/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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

Čt 10:00–11:50 B410

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 18 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2012/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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 B204

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 22 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2012/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 21 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2011/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 21 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2010/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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 10:00–11:50 B410

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 18 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2009/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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 10:00–11:50 B410

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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á 18 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html

Další komentáře

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

IA012 Složitost

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 10:00–11:50 B410

Předpoklady

! I017 Strukturní složitost
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html

Další komentáře

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

IA012 Složitost

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 10:00–11:50 B410

Předpoklady

! I017 Strukturní složitost
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html

Další komentáře

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

IA012 Složitost

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 B410

Předpoklady

! I017 Strukturní složitost
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost

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

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

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

V průběhu semsestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html

Další komentáře

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

IA012 Složitost

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 B410

Předpoklady

! I017 Strukturní složitost
Znalost problematiky v rozsahu předmětu IB107 - Vyčíslitelnost a složitost.

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

• Aplikovaná informatika (program FI, N-AP)
• Informatika (program FI, M-IN)
• Informatika (program FI, N-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Učitelství výpočetní techniky pro střední školy (program FI, N-SS)

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na průběžné práci v semestru. Přesná specifikace požadavkú viz www stránka předmětu.

Informace učitele

http://www.fi.muni.cz/usr/cerna/Slozitost/ia012.html

Další komentáře

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

IA012 Složitost

Předmět se v období podzim 2019 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. 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

Předpoklady

Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.

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á 48 mateřských oborů, zobrazit

Cíle předmětu

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Výstupy z učení

Student bude po absolvování předmětu schopen:
- aktivně používat pojem výpočetní složitosti problémů a algoritmů,
- analyzovat dolní a horní odhady složitosti,
- rozlišovat mezi prakticky řešitelnými a prakticky neřešitelnými problémy,
- definovat základní složitostní třídy a znát vztahy mezi nimi,
- vysvětlit pojem (NP) úplného problému a identifikovat úplné problémy složitostních tříd,
- popsat meze deterministických, nedeterministických, alternujících, pravděpodobnostnícha a paralelních výpočtů,

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostní složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

povinná literatura
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info

doporučená literatura
• ARORA, Sanjeev a Boaz BARAK. Computational Complexity : a modern approach. 1st pub. New York: Cambridge University Press, 2009, xxiv, 579. ISBN 9780521424264. info
• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Výukové metody

teoretická příprava doplněna domácími úkoly a projekty

Metody hodnocení

V průběhu semesestru studenti samostaně řeší zadané problémy. Závěrečné hodnocení je založeno na výsledcích písemné zkoušky a na řešení zadaných problémů.

Informace učitele

https://is.muni.cz/auth/el/1433/jaro2018/IA012/index.qwarp

Další komentáře

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

IA012 Složitost

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.

Předpoklady

! I017 Strukturní složitost

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

Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limity výpočetních procesů. Kurs prezentuje strukturu prostoru algoritmických problémů a rozvíjí techniky, které dovolují redukovat hledání efektivních algoritmů pro celou třídu algoritmických problémů na hledání efektivní metody pro klíčové algoritmické problémy. Teorie klasifikuje problémy podle jejich výpočetní složitosti na prakticky zvladatelné a nezvladatelné a ukazuje důvody nezvladatelnosti (praktické neřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunout hranici zvladatelnosti techniky jako randomizace, aproximace a paralelní postupy řešení problémů.

Osnova

• Struktura a vlastnosti časových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Struktura a vlastnosti prostorových složitostních tříd. Vztah determinizmu a nedeterminizmu.
• Nezvladatelné problémy. Nekonečnost hierarchie složitostních tříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetní složitost.
• Pravděpodobnostné složitostní třídy a jejich struktura. Aproximativní složitostní třídy a neaproximovatelnost.
• Alternování a hry. Interaktivní protokoly a interaktivní důkazové systémy.
• Techniky pro získavaní dolních odhadů složitosti. Kolmogorovská složitost.
• Deskriptivní složitost.

Literatura

• SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
• PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info

Záložky

https://is.muni.cz/ln/tag/FI:IA012!

Metody hodnocení

Závěrečné hodnocení je založeno na výsledcích písemné zkoušky.

Navazující předměty

• I017 Strukturní složitost

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ší)