456-0907/01 – 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ýukyčeština
Rok zavedení1997/1998Rok zrušení2009/2010
Určeno pro fakultyFEIUrč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í Zápočet a zkouška 2+0
kombinovaná Zápočet a zkouška 2+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

Předmět poskytuje exaktní základ především pojmům algoritmické řešitelnosti a algoritmické složitosti, se kterými se posluchači seznámili v průběhu řádného studia na víceméně intuitivní úrovni. Je věnován některým pokročilým partiím vyčíslitelnosti a složitosti (jako rozhodování logických teorií, pravděpodobnostní algoritmy, paralelní výpočty, atd.)

Povinná literatura:

M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997 E.Borger: Computability, Complexity, Logic. North-Holland 1989 D.Harel: Algorithmics, The Spirit of Computing, Addison-Wesley1992 Hopcroft, Ullman: Introduction to Automata Theory, Languages and Computation, Addison-Wesley 1979

Doporučená literatura:

M.Sipser: Introduction to the Theory of Computation, PWS Publ. Comp. 1997 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

E-learning

Další požadavky na studenta

Prerekvizity

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

Korekvizity

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

Osnova předmětu

Přednášky: 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, krypografie, ...)

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

Prezenční forma (platnost od: 1960/1961 letní semestr, platnost do: 2008/2009 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
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
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2009/2010 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie K čeština Ostrava povinně volitelný stu. plán
2008/2009 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika K čeština Ostrava povinně volitelný stu. plán
2007/2008 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (P2646) Informační technologie (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (P2612) Elektrotechnika a informatika (1801V002) Informatika a aplikovaná matematika P češ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