456-0090/01 – Vyčíslitelnost a složitost (VAS)

Garantující katedraKatedra informatikyKredity8
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
RočníkSemestrletní
Jazyk výukyčeština
Rok zavedení1996/1997Rok zrušení2010/2011
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAN59 prof. RNDr. Petr Jančar, CSc.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

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

Cílem předmětů je zvládnutí základních pojmů a metod v oblasti algoritmické rozhodnutelnosti a složitosti.

Vyučovací metody

Anotace

Kurs seznamuje se zakladnimi pojmy, vysledky a metodami teorie algoritmu, specialne teorie vycislitelnosti a slozitosti. Nejprve jsou rekapitulovany obecne metody navrhu algoritmu a je analyzovana (casova, pametova) slozitost konkretnich algoritmu; referencnim abstraktnim modelem pocitace je pritom RAM (random access machine). Pote je diskutovana slozitost problemu a jsou zavedeny tridy slozitosti. Specialni pozornost je venovana tridam PTIME a NPTIME; je vysvetlena jejich dulezitost jak z teoretickeho, tak praktickeho hlediska. Dale je objasnen pojem algoritmicke nerozhodnutelnosti. Kurs je pak doplnen strucnou ilustraci aproximacnich, pravdepodobnostnich a take paralelnich a distribuovanych algoritmu.

Povinná literatura:

L. Kučera: Kombinatorické algoritmy, matem. seminář SNTL 18, Praha 1983 J. Morávek: Složitost výpočtů a optimální algoritmy, Academia, Praha 1984 M. Chytil: Automaty a gramatiky, matem. seminář SNTL 19, Praha 1984 J. Hopcroft, J. Ullman: Formálne jazyky a automaty, Alfa, Bratislava 1978 Z. Manna: Matematická teorie programů, SNTL, Praha 1981 D. Harel: Algorithmics (The Spirit of Computing); Addison Wesley 1993 T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms; The MIT Press, 1990 J. Hopcroft, J. Ullman: Introduction to Automata Theory, Languages, and Computation; Addison Wesley 1979

Doporučená literatura:

Pracovní text ke kursu zpracovaný P. Jančarem (odkaz z http://www.cs.vsb.cz/jancar/VYCSLOZ/vycsloz.htm)

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: Uvod ke kursu. Slozitost algoritmu. Model RAM. Odhady slozitosti. Nejhorsí vs. prumerný pripad. Analyza vybranych algoritmu. Metoda `rozdel a panuj'. Analyza dalsich algoritmu. `Greedy' algoritmy. Metoda dynamickeho programovani. Problemy, tridy slozitosti problemu, horni a dolní odhady. Turinguv stroj. Turingovy stroje a dalsi vypocetni modely; jejich vzajemna `polynomialni' simulace. Trida P (=PTIME) jako aproximace tridy prakticky zvladnutelných problemu. Trida NP (=NPTIME). Polynomialni preveditelnost. NP-uplnost. NP-uplne problemy. Otevrena otazka, zda P=NP. Dalsi tridy casove i prostorove slozitosti a jejich vzajemne vztahy. Dokazatelne nezvladnutelne problemy. Church-Turingova teze. Rozhodnutelnost a castecna rozhodnutelnost problemu. Univerzalni Turinguv stroj. Rekurzivni a rekurzivne spocetne mnoziny (jazyky). Rekurzivni a castecne rekurzivni funkce. Metoda diagonalizace. Nerozhodnutelnost problemu zastaveni. Dalsi nerozhodnutelne problemy. Riceova věta. Dalsi temata teorie algoritmu.

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

Prezenční forma (platnost od: 1960/1961 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.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2008/2009 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 4 povinný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 3 povinný stu. plán

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

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