Teorie algoritmů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh

Kód	Zakončení	Kredity	Rozsah	Jazyk výuky
A4M01TAL	Z,ZK	6	3+1s	česky

Přednášející:

Marie Demlová (gar.)

Cvičící:

Marie Demlová (gar.), Jiřina Scholtzová

Předmět zajišťuje:

katedra matematiky

Anotace:

Predmět se věnuje teoretickým základům teori algoritmů, důraz je kladen jak na analýzu časové a pměťové složitosti algoritmů a problémů, tak na ověření správnosti algoritmů. Dále jsou probrány základy teorie složitosti. Jedná se o třídy P, NP, NP-complete, PSPACE,

NPSPACE a vztah mezi těmito třídami. V předmětu se studenti seznámí také s pravděpodobnostními algoritmy a třidami RP a ZPP.

Požadavky:

Logika a grafy, Diskrétní matematika

Osnova přednášek:

1. Algoritmus, asymptotický růst funkcí, časová a paměťová složitost.

2. Správnost algoritmu, důkazy správnosti algoritmů, varianty a invarianty-

3. Rozhodovací a optimalizační problémy a jejich vztah.

4. Turingovy stroje a jejich varianty.

5. Vztah Turingova stroje a RAM.

6. Třída P a třída NP.

7. Redukce a polynomiální redukce úloh.

8. NP-úplné úlohy, Cookova věta.

9. Třídy PSPACE a NPSPACE.

10. Pravděpodobnostní algoritmy pracující v polynomiálním čase.

11. Třídy RP a ZZP.

12. Algoritmicky neřešitelné úlohy.

13. Rezerva.

Osnova cvičení:

1. Zjišťování časové a paměťové složitosti známých (např. grafových) algoritmů.

2. Ověřování správnosti jednoduchých algoritmů, hledání variantů a invariantů.

3. Turingovy stroje.

4. Příklady redukcí úloh.

5. Příklady pravděpodobnostních algoritmů.

6. Algoritmicky neřešitelné úlohy.

Cíle studia:

Studijní materiály:

[1] Kozen, D. C.: The design and Analysis of Algorithms, Springer-Vrelag, 1991

[2] Harel, D: Algorithmics: The Spirit of Computing, Addison-Wesleyt Inc., Reading MA 2002

[3] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+3s

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út	místnost T2:C3-340 Demlová M. 08:15–10:00 (přednášková par. 1) Dejvice Posluchárna
St	místnost T2:A4-205 Scholtzová J. 07:30–09:00 LICHÝ TÝDEN (přednášková par. 1 paralelka 101) Dejvice Učebnamístnost T2:A4-205 Scholtzová J. 09:15–10:45 LICHÝ TÝDEN (přednášková par. 1 paralelka 103) Dejvice Učebnamístnost T2:A4-205 Demlová M. 11:00–12:30 LICHÝ TÝDEN (přednášková par. 1 paralelka 105) Dejvice Učebna místnost T2:A4-205 07:30–09:00 SUDÝ TÝDEN (přednášková par. 1 paralelka 102) Dejvice Učebnamístnost T2:A4-205 Scholtzová J. 09:15–10:45 SUDÝ TÝDEN (přednášková par. 1 paralelka 104) Dejvice Učebnamístnost T2:A4-205 11:00–12:30 SUDÝ TÝDEN (přednášková par. 1 paralelka 106) Dejvice Učebna
Čt
Pá	místnost T2:C3-340 Demlová M. 12:45–14:15 SUDÝ TÝDEN (přednášková par. 1) Dejvice Posluchárna

Předmět je součástí následujících studijních plánů:

Otevřená informatika - Umělá inteligence (povinný předmět programu)
Otevřená informatika - Počítačové inženýrství (povinný předmět programu)
Otevřená informatika - Počítačové vidění a digitální obraz (povinný předmět programu)
Otevřená informatika - Počítačová grafika a interakce (povinný předmět programu)
Otevřená informatika - Softwarové inženýrství (povinný předmět programu)
Biomedicínské inženýrství a informatika - Biomedicínská informatika (povinný předmět oboru)
MVT01-Výpočetní technika - nový - softwarové inženýrství- strukturované studium (povinný předmět zaměření)
MVT04-Výpočetní technika - nový - počítačové sítě a internet- strukturované studium (povinný předmět zaměření)