FI:IA101 Algorithmics for Hard Problems - Course Information

IA101 Algorithmics for Hard Problems

Extent and Intensity

2/0. 2 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).

Teacher(s)

prof. RNDr. Ivana Černá, CSc. (lecturer)
Mgr. Jiří Šimša (seminar tutor)

Guaranteed by

prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.

Timetable

Mon 14:00–15:50 D2

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Applied Informatics (programme FI, N-AP)
• Information Technology Security (programme FI, N-IN)
• Bioinformatics (programme FI, N-AP)
• Information Systems (programme FI, N-IN)
• Informatics (programme FI, D-IN)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Mathematical Informatics (programme FI, B-IN)
• Parallel and Distributed Systems (programme FI, N-IN)
• Computer Graphics (programme FI, N-IN)
• Computer Networks and Communication (programme FI, N-IN)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Theoretical Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
• Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
• Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
• Image Processing (programme FI, N-AP)

Course objectives

The course expands on courses Algorithm design I and Algorithm design II. It focuses on the design of algorithms for hard computing tasks. The course systematically explains, combines, and compares the main possibilities for attacking hard algorithmic problems like randomization, heuristics, approximation and local search.

Syllabus

• Deterministic approaches: pseudo-polynomial-time algoirithms, parametrized complexity, branch-and-bound, lowering worst case complexity of exponential algorithms, local search, relaxation to linear programming.
• Approximation approaches: concept of approximation algorithms, classification of optimization problems, stability of approximation, inapproximability, algorithms design.
• Randomized approaches: classification of randomized algorithms and design paradigms, design of randomized algorithms, derandomization.
• Heuristics> simulated annealing, genetic algorithms.

Literature

• Hromkovič, Juraj. Algorithmics for Hard Problems. Springer, 2001
• R. Motwani, R. Prabhakar: Randomized Algorithms. Cambridge University Press, 1995
• V. Vazirani: Approximation Algorithms. Springer, 2001

Assessment methods (in Czech)

Pisemna zkouska na konci semestru. Reseni ukolu v prubehu semestru.

Language of instruction

Czech

Further Comments

Study Materials
The course is taught annually.

Teacher's information

https://is.muni.cz/auth/elearning/warp.pl?fakulta=1433;obdobi=3523;kod=IA101;qurl=%2Fel%2F1433%2Fpodzim2006%2FIA101%2Findex.qwarp

• Enrolment Statistics (Autumn 2007, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2007/IA101