ČeskyEnglish

Popis předmětu - AE4M01TAL

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

Anotace:

The course brings several algorithms from the theory of graphs and cryptography. Stress is put on the analysis of time complexity of the algorithms presented. Further, basics of the theory of complexity are given. Next an example of randomized algorithms is given, it is the Miller-Rabin?s algorithm. When dealing with time complexity of specific algorithms suitable data structures will be given.

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

Osnovy přednášek:

1. Analyzing algorithms and problems, classifying functions by their growth rates, time complexity.
2. Basic graph algorithms, minimal spanning tree, Prim?s and Kruskal?s algorithms.
3. Algorithm for strongly connected components.
4. Matching in bipartite graphs.
5. Hungarian Algorithm.
6. Isomorphism of graphs.
7. Algorithms in cryptography, Eucleid?s Algorithm, RSA.
8. The classes of P and NP, polynomial reduction of problems.
9. NP-complete problems, examples of NP-complete problems.
10. Cook?s Theorem, reductions of NP-complete problems.
11. Heuristics for NP-complete problems, colouring.
12. Randomized algorithms, Miller-Rabin algorithm for primality testing.
13. Undecidable problems.

Osnovy cvičení:

1. Basic graph algorithms, minimal spanning tree, Prim?s and Kruskal?s algorithms.
2. Algorithm for strongly connected components.
3. Hungarian Algorithm.
4. Eucleid?s Algorithm, RSA.
5. NP-complete problems, polynomial reduction of problems.
6. Vertex colouring of graphs.
7. Miller-Rabin algorithm.

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 1002
[3] Talbot, J., Welsh, D.: Complexity and Cryptography, Cambridge University Press, 2006

Požadavky:

Logic and Graphs, Discrete Mathematics

Poznámka:

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

Webová stránka:

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

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

Plán Obor Role Dop. semestr
MEKME4 Sítě elektronických komunikací V 2
MEKME5 Komunikační systémy V 2
MEKME3 Elektronika V 2
MEKME2 Multimediální technika V 2
MEKME1 Bezdrátové komunikace V 2
MEOI1 Umělá inteligence P 2
MEOI3 Počítačové vidění a digitální obraz P 2
MEOI5NEW Softwarové inženýrství P 2
MEOI2 Počítačové inženýrství P 2
MEOI4 Počítačová grafika a interakce P 2
MEOI5 Softwarové inženýrství P 2
MEEEM3 Elektroenergetika V 2
MEEEM4 Ekonomika a řízení energetiky V 2
MEEEM5 Ekonomika a řízení elektrotechniky V 2
MEEEM1 Technologické systémy V 2
MEEEM2 Elektrické stroje, přístroje a pohony V 2
MEKYR4 Letecké a kosmické systémy V 2
MEKYR1 Robotika V 2
MEKYR2 Senzory a přístrojová technika V 2
MEKYR3 Systémy a řízení V 2


Stránka vytvořena 22.9.2017 07:47:47, 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.