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)

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 D3

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 (eng.) (programme FI, D-IN4)
• Informatics (programme FI, D-IN4)
• 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 and Technologies (eng.) (programme FI, D-IN4)
• Computer Systems and Technologies (programme FI, D-IN4)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Embedded Systems (programme FI, N-IN)
• Service Science, Management and Engineering (eng.) (programme FI, N-AP)
• Service Science, Management and Engineering (programme FI, N-AP)
• 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

• VAZIRANI, Vijay V. Approximation algorithms. Berlin: Springer, 2001, xix, 378. ISBN 3540653678. info
• MOTWANI, Rajeev and Prabhakar RAGHAVAN. Randomized algorithms. Cambridge: Cambridge University Press, 1995, xiv, 476. ISBN 0521474655. info
• HROMKOVIČ, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. Berlin: Springer, 2001, xi, 492. ISBN 3540668608. info

Teaching methods

lectures, individual homeworks and projects aiming at practical skills with designe techniques

Assessment methods

Written test

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 2009, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2009/IA101