Subject description - A4M01TAL

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A4M01TAL Theory of Algorithms Extent of teaching:3+1
Guarantors:Demlová M. Roles:PO,ZZ,P,V Language of
teaching:
CS
Teachers:Demlová M. Completion:Z,ZK
Responsible Department:13101 Credits:6 Semester:L

Anotation:

The course brings theoretical background of the theory of algorithms with the focus at first on the time and space complexity of algorithms and problems, secondly on the correctness of algorithms. Further it is dealt with the theory of complexity; the classes P, NP, NP-complete, PSPACE and NPSPACE are treated and properties of them investigated. Probabilistic algorithms are studied and the classes RP and ZZP introduced.

Course outlines:

1. Analyzing algorithms and problems, classifying functions by their growth rates, time and space complexity.
2. Correctness of algorithms, variants and invariants.
3. Decision problems and optimization problems.
4. Turing machine and its variants.
5. Relation between Turing machine and RAM machine.
6. Classes P and NP.
7. Reduction and polynomial reduction of problems.
8. NP-complete problems, Cook's Theorem.
9. Classes PSPACE and NPSPACE..
10. Randomized algorithms with polynomial time complexity.
11. Classes RP and ZZP.
12. Undecidable problems.
13. Reserve.

Exercises outline:

1. Determining time and space complexity of well known algorithms.
2. Verifying correctness of algorithms using variants and invariants.
3. Turing machines.
4. Polynomial reductions of problems.
5. Examples of randomized algorithms.
6. Examples of undecidable problems.

Literature:

[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

Requirements:

Logic and Graphs, Discrete Mathematics

Webpage:

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

Subject is included into these academic programs:

Program Branch Role Recommended semester
MPIB Common courses V
MPOI1 Artificial Intelligence P 2
MPOI5NEW Software Engineering P 2
MPOI4NEW Computer Graphics and Interaction P 2
MPOI5 Software Engineering P 2
MPOI4 Computer Graphics and Interaction P 2
MPOI3 Computer Vision and Image Processing P 2
MPOI2 Computer Engineering P 2
MPKME1 Wireless Communication V 2
MPKME5 Systems of Communication V 2
MPKME4 Networks of Electronic Communication V 2
MPKME3 Electronics V 2
MPKME2 Multimedia Technology V 2
MPEEM1 Technological Systems V 2
MPEEM5 Economy and Management of Electrical Engineering V 2
MPEEM4 Economy and Management of Power Engineering V 2
MPEEM3 Electrical Power Engineering V 2
MPEEM2 Electrical Machines, Apparatus and Drives V 2
MPKYR4 Aerospace Systems V 2
MPBIO1 Biomedical Informatics PO 2
MPKYR1 Robotics V 2
MPKYR3 Systems and Control V 2
MPKYR2 Sensors and Instrumentation V 2
MVT01N Computer Science and Engineering ZZ 2
MVT04N Computer Science and Engineering ZZ 2


Page updated 19.7.2019 11:52:58, semester: Z,L/2020-1, L/2018-9, Z,L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)