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

Garantující katedraKatedra informatikyKredity10
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapostgraduálníPovinnostpovinně volitelný typu B
RočníkSemestrzimní + letní
Jazyk výukyangličtina
Rok zavedení2019/2020Rok zrušení
Určeno pro fakultyUSP, FEIUrčeno pro typy studiadoktorské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zkouška 28+0
kombinovaná Zkouška 28+0
distanční Zkouška 10+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. Ústní zkouška.

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

Prezenční forma (platnost od: 2019/2020 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zkouška Zkouška  
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2020/2021 (P0613D140006) Informatika P angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140006) Informatika K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140021) Výpočetní vědy K angličtina Ostrava povinně volitelný typu B stu. plán
2020/2021 (P0613D140021) Výpočetní vědy P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140006) Informatika P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140006) Informatika K angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140021) Výpočetní vědy P angličtina Ostrava povinně volitelný typu B stu. plán
2019/2020 (P0613D140021) Výpočetní vědy K angličtina Ostrava povinně volitelný typu B stu. plán

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

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