Problems and Algorithms

Lecturer:

Jan Schmidt (gar.)

Tutor:

Petr Fišer, Jan Schmidt (gar.), Pavel Kordík, Jan Pospíšil

Supervisor:

Department of Digital Design

Synopsis:

Students are able to evaluate discrete problems by complexity and by the purpose of optimisation (on-line tasks, multicriterial optimisation). They understand principles and properties of heuristics and exact algorithms and, therefore, are able to select, apply, and experimentally evaluate a suitable heuristics for a practical problem.

Requirements:

The notion of complexity, asymptotic complexity bounds. Basic graph theory. Programming in any imperative language using queues, stacks, and lists.

Syllabus of lectures:

1. Discrete optimization, examples of practical tasks. Combinatorial problems. Algorithm complexity, problem complexity.

2. State, state space, search space. Basic exact search methods.

3. Decidable problems. models of computation. The classes P and NP. Polynomial hierarchy. The classes PO and NPO.

4. The notion of completeness. Complexity comparison techniques. The classes NP-complete and NP-hard. The structure of NP and NPO.

5. Deterministic approximation algorithms. Classification of approximative problems. Pseudopolynomial algorithms. Randomization and randomized algorithms.

6. Practical deployment of heuristic and exact algorithms. Experimental evaluation.

7. Simple local heuristics in state space and search space.

8. Simulated annealing.

9. Simulated evolution: taxonomy, genetic algorithms.

10. Advanced genetic algorithms: competent GA, fast messy GA, the selfish gene method. Applications to multicriterial optimization.

11. Stochastic optimization: models and applications. Bayesian optimization.

12. Tabu search.

13. Global methods, taxonomy of decomposition-based methods. Exact and heuristic global methods, the Davis-Putnam procedure seen as a global method.

Syllabus of tutorials:

1. Seminar: terminology, examples of complexity.

2. Seminar: examples of state space.

3. Homework consultation when required, self-study: dynamic programming revision.

4. Solved problems session: the classes P and NP, complexity proofs, problems beyond NP.

5. Solved problems session: completeness, reductions.

6. Homework consultation when required.

7. Homework consultation when required.

8. Homework consultation when required.

9. Midterm test.

10. Homework consultation when required.

11. Solved problems session: advanced heuristics, applications.

12. Homework consultation when required.

13. Homework consultation when required.

14. Backup test term, evaluation.

Study Objective:

Many practical tasks are computationally infeasible. Students will learn to distinguish tasks where the complexity grows too fast with the task size from those which are undecidable independently of size. They will learn fast algorithms for exact and, primarily, approximate solution. Some of the more advanced ones are inspired by processes in nature and sometimes referred to as softcomputing. A series of homeworks will lead students from very simple tasks to applications of advanced heuristics on a practical problem.

Study materials:

1. Garey, M. R., Johnson, D. S. ''Computers and Intractability: A Guide to the Theory of NP-Completeness''. W. H. Freeman, 1979. ISBN 0716710455.

2. Ausiello, G., Crescenzi, P., Kann, V., Gambosi, G., Spaccamela, A. M. ''Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties''. Springer, 2003. ISBN 3540654313.

Note:

Time-table for winter semester 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon	roomT9:345 Kordík P. 12:45–14:15 (lecture parallel1 parallel nr.106) Dejvice NBFIT HW ucebnaroomT9:155 Schmidt J. 14:30–16:00 (lecture parallel1) Dejvice Posluchárna
Tue	roomT9:345 Kordík P. 12:45–14:15 (lecture parallel1 parallel nr.101) Dejvice NBFIT HW ucebnaroomT9:345 Fišer P. 14:30–16:00 (lecture parallel1 parallel nr.102) Dejvice NBFIT HW ucebnaroomT9:345 Fišer P. 16:15–17:45 (lecture parallel1 parallel nr.103) Dejvice NBFIT HW ucebnaroomT9:345 Fišer P. 18:00–19:30 (lecture parallel1 parallel nr.104) Dejvice NBFIT HW ucebna
Fri	roomT9:345 Pospíšil J. 11:00–12:30 (lecture parallel1 parallel nr.107) Dejvice NBFIT HW ucebnaroomT9:345 Pospíšil J. 12:45–14:15 (lecture parallel1 parallel nr.108) Dejvice NBFIT HW ucebnaroomT9:345 Fišer P. 16:15–17:45 (lecture parallel1 parallel nr.109) Dejvice NBFIT HW ucebnaroomT9:345 Fišer P. 18:00–19:30 (lecture parallel1 parallel nr.105) Dejvice NBFIT HW ucebna
Thu
Fri

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Branch Software Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Master Branch Web Engineering - Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Computer Security, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Design of Digital Systems, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Computer Systems and Networks, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Knowledge Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Branch Web and Software Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course of the specialization)
• Master Informatics, Version for Students who Enrolled in 2010, Presented in Czech (VO)
• Master Informatics, Presented in Czech, Version for Students who Enrolled in 2011 (VO)
• Branch Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Branch Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Knowledge Engineering, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Computer Security, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Design of Digital Systems, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Computer Systems and Networks, Presented in Czech, Version for Students who Enrolled in 2011 (compulsory course of the specialization)
• Master Informatics, Presented in Czech, Version for Students who Enrolled in 2012 (VO)
• Computer Security, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Design of Digital Systems, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Branch Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Branch Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Web and Software Engineering, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Knowledge Engineering, in Czech, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)
• Computer Systems and Networks, Presented in Czech, Version for Students who Enrolled in 2012 (compulsory course of the specialization)