Poll

No polls currently selected on this page!

Repository

Repository is empty

Algorithm complexity

Code: 92958
ECTS: 5.0
Lecturers in charge: prof. dr. sc. Mladen Vuković
English level:

1,0,0

All teaching activities will be held in Croatian. However, foreign students in mixed groups will have the opportunity to attend additional office hours with the lecturer and teaching assistants in English to help master the course materials. Additionally, the lecturer will refer foreign students to the corresponding literature in English, as well as give them the possibility of taking the associated exams in English.
Load:

1. komponenta

Lecture typeTotal
Lectures 45
* Load is given in academic hour (1 academic hour = 45 minutes)
Description:
COURSE AIMS AND OBJECTIVES: The complexity classes are studied. Examples of different problem will explain and describe some classes. Some open problems of complexity theory are emphasized. At the end descriptive complexity theory are considered.

COURSE DESCRIPTION AND SYLLABUS:
- Complexity: problems and algorithms; time and space, non-deterministic computation, complexity classes, reductions, completeness.
- Basic relations: LOGSPACE, P, NP, PSPACE, EXPTIME i NEXPTIME; Cook - Levin theorem.
- Examples of problems: sorting, 2CNF, 3CNF, SAT, HORNSAT, graph coloring, CLIQUE, Hamiltonian path problem, knapsack problem, minimum travelling salesperson problem.
- Savitch theorem: PSPACE=NPSPACE; PSPACE-completeness, QBF problem, Stockmeyer's theorem.
- Probabilistic algorithms: probabilistic Turing machine; class BPP; examples of problem.
-Cryptography: private and public keys; one way functions.
- Descriptive complexity theory: fixed point logics, expressive power, Fagin's theorem.
Literature:
Prerequisit for:
Enrollment :
Passed : Design and analysis of algorithms
Attended : Computability

Examination :
Passed : Computability
4. semester
Mandatory course - Regular study - Computer Science and Mathematics
Consultations schedule: