IA012 Složitost

Fakulta informatiky
podzim 2024
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023.

IA012 Složitost

Fakulta informatiky
podzim 2023
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2024.

IA012 Složitost

Fakulta informatiky
podzim 2022
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
podzim 2021
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
podzim 2020
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2019
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2018
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2017
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2016
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2015
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2014
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2013
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2012
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2011
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2010
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2009
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2008
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2007
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2006
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2005
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ě.
Předmět je zařazen také v obdobích jaro 2004, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
jaro 2004
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
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ě.
Předmět je zařazen také v obdobích jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
podzim 2019

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.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.

IA012 Složitost

Fakulta informatiky
podzim 2002

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
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích jaro 2004, jaro 2005, jaro 2006, jaro 2007, jaro 2008, jaro 2009, jaro 2010, jaro 2011, jaro 2012, jaro 2013, jaro 2014, jaro 2015, jaro 2016, jaro 2017, jaro 2018, jaro 2019, podzim 2020, podzim 2021, podzim 2022, podzim 2023, podzim 2024.