Fakulta elektrotechnická

České vysoké učení technické v Praze

ČVUT v Praze

Popis předmětu - A4M01TAL

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M01TAL Teorie algoritmů Rozsah výuky:3+1
Garanti:Demlová M. Role:PO,ZZ,P,V Zakončení:Z,ZK
Vyučující:Demlová M.
Zodpovědná katedra:13101 Kreditů:6 Semestr:L

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.

Výsledek studentské ankety předmětu je zde: AD4M01TAL

Výsledek studentské ankety předmětu je zde: A4M01TAL

Osnovy 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.

Osnovy 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.

Literatura:

[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

Požadavky:

Logika a grafy, Diskrétní matematika

Poznámka:

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

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/tal_vyuka.html

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPIB Před zařazením do oboru V
MPOI1 Umělá inteligence P 2
MPOI2 Počítačové inženýrství P 2
MPOI3 Počítačové vidění a digitální obraz P 2
MPOI5NEW Softwarové inženýrství P 2
MPOI5 Softwarové inženýrství P 2
MPOI4NEW Počítačová grafika a interakce P 2
MPOI4 Počítačová grafika a interakce P 2
MPKME2 Multimediální technika V 2
MPKME4 Sítě elektronických komunikací V 2
MPKME1 Bezdrátové komunikace V 2
MPKME3 Elektronika V 2
MPKME5 Komunikační systémy V 2
MPEEM5 Ekonomika a řízení elektrotechniky V 2
MPEEM4 Ekonomika a řízení energetiky V 2
MPEEM2 Elektrické stroje, přístroje a pohony V 2
MPEEM1 Technologické systémy V 2
MPEEM3 Elektroenergetika V 2
MPKYR4 Letecké a kosmické systémy V 2
MPBIO1 Biomedicínská informatika PO 2
MPKYR1 Robotika V 2
MPKYR2 Senzory a přístrojová technika V 2
MPKYR3 Systémy a řízení V 2
MVT01N Výpočetní technika ZZ 2
MVT04N Výpočetní technika ZZ 2


Stránka vytvořena 23.11.2017 09:47:48, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.