460-6004/02 – Teorie algoritmů (TA)

Garantující katedraKatedra informatikyKredity10
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapostgraduálníPovinnostpovinně volitelný
RočníkSemestrzimní + letní
Jazyk výukyangličtina
Rok zavedení2015/2016Rok zrušení2021/2022
Určeno pro fakultyUSP, FEIUrčeno pro typy studiadoktorské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zkouška 28+0
kombinovaná Zkouška 28+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Student po úspěšném absolvování předmětu: - rozumí základním pojmům v oblasti algoritmické vyčíslitelnosti a výpočetní složitosti - umí navrhovat vhodné algoritmy pro praktické problémy - umí analyzovat složitost algoritmů a zařazovat problémy do tříd složitosti - zvládá i návrh a analýzu aproximačních, pravděpodobnostních a paralelních algoritmů - prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v oblasti teorie algoritmů

Vyučovací metody

Přednášky
Individuální konzultace
Projekt

Anotace

V kursu se stručně zopakuje základ teorie vyčíslitelnosti a složitosti, který studenti měli získat v magisterském studiu. Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilým partiím, jako je např. rozhodování logických teorií, aproximační algoritmy, pravděpodobnostní algoritmy, paralelní výpočty apod.

Povinná literatura:

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

Doporučená literatura:

D. Kozen: Automata and Computability, Springer 1997 D. Kozen: Theory of Computation; Springer 2006 I. Wegener: Complexity Theory; Springer 2005 Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990

Forma způsobu ověření studijních výsledků a další požadavky na studenta

Student sepíše stručný, ale výstižný a srozumitelný, článek o vybraném pokročilém tématu, které v rámci kurzu odprezentuje.

E-learning

Další požadavky na studenta

Žádné další požadavky na studenta nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Intuitivní pojem algoritmu a efektivní vyčíslitelné funkce. Různé matematické formalizace těchto pojmů (především Turingovy stroje a částečně rekurzivní funkce). Idea univerzálního algoritmu. Hlavní myšlenky důkazu ekvivalence uvedených matematických formalizací, Churchova teze. Problém zastavení (Halting problem), Postův korespondenční problém a další algoritmicky nerozhodnutelné problémy. Univerzální funkce, Kleeneho věta o normální formě. Rekurzivní a rekurzivně spočetné množiny, Postova věta. Věta o rekurzi, Riceova věta. Rekurzivní převeditelnost. Kreativní množiny. Rozhodnutelnost logických teorií. Časová a prostorová složitost algoritmů a problémů. P-NP problém. NP-úplnost a PSPACE-úplnost. EXPTIME, EXPSPACE, dokazatelně nezvládnutelné problémy. Aproximační algoritmy, pravděpodobnostní algoritmy. Paralelní a distribuované algoritmy. Další témata (např. alternace, kryptografie, ...)

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2015/2016 zimní semestr, platnost do: 2021/2022 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zkouška Zkouška   3
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2021/2022 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2021/2022 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2021/2022 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2020/2021 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0541D170006) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2019/2020 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2018/2019 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2017/2018 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2016/2017 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1103V036) Výpočetní a aplikovaná matematika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P1807) Informatika, komunikační technologie a aplikovaná matematika (1801V001) Informatika K angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy P angličtina Ostrava povinně volitelný stu. plán
2015/2016 (P2658) Výpočetní vědy (2612V078) Výpočetní vědy K angličtina Ostrava povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky

Předmět neobsahuje žádné hodnocení.