|
T-79.4201 Search Problems and Algorithms (4 cr)
Autumn 2007 (periods I and II)
The course provides an introduction to the fundamental
concepts, techniques and tools used in dealing with large,
weakly structured combinatorial search spaces. The topics
covered include: search spaces and search methods; backtracking,
local and heuristic search; representing and solving
search problems using propositional satisfiability,
constraint programming and integer programming techniques.
[Current]
[General]
[Lectures]
[Tutorials]
[Assignments]
[Exams]
[Course material]
[Links]
Previous years:
[Autumn 2006]
[Spring 2006]
- [17 Dec 2007] The lectures and tutorials for this autumn are
over; many thanks for your active participation. The autumn
exam for the course is scheduled for Thu 20 Dec, 9-12,
in Lecture Hall T1. Please verify the time and place from
the DCSE department
exam schedule,
and remember to register for the exam
via TOPI.
Also, remember to provide feedback on the course via the
department's
course feedback system.
The electronic questionnaires open Mon 10 Dec and close Mon 7 Jan.
- [8 Nov 2007] The third
programming assignment
has been published. Deadline for returning the
solutions is 29 November. For further
information please contact the course assistant,
André Schumacher.
- [18 Oct 2007] The second
programming assignment
has been published. Deadline for returning the
solutions is 8 November. For further
information please contact the course assistant,
André Schumacher.
- [4 Oct 2007] The first
programming assignment
has been published. Deadline for returning the
solutions is 25 October. For further
information please contact the course assistant,
André Schumacher.
- [14 Aug 2007] First lecture Thu 13 Sep, room TB353.
Registration via
TOPI.
- Lectures:
Ilkka Niemelä
and
Pekka Orponen,
13 Sep - 13 Dec, Thu 14-16, room TB353.
- Tutorials:
André Schumacher,
20 Sep - 13 Dec, Thu 16-18, room TB353.
- Registration by
TOPI.
- Prerequisites: Basic knowledge of problem representations
and logic (T-79.1001, T-79.3001); facility in programming, data
structures and algorithms (T-106.1220 required, T-106.3100 recommended).
- Requirements: Examination and three programming assignments.
- Examination:
Scheduled for Thu 20 Dec,
registration by TOPI.
Check exact time and place from the DCSE department
exam schedule.
- Grading: Exam max 40 points, programming assignments
max 3*5 = 15 points, tutorials max 5 points, total 60 points.
For the programming assignments, a correctly
functioning program, returned on time with appropriate
work description yields 3 points; the remaining 2 points
are allocated based on an efficiency competition among
the submitted programs.
The preliminary lecture slides linked to the schedule below are
from the Autumn 2006 instalment of the course, and will be
updated to their current form after each lecture.
Week | Date | Topic |
Lecture slides |
37. | Sep 13 |
Course arrangements and overview of contents. |
PDF |
38. | Sep 20 |
Combinatorial search and optimisation problems. |
PDF |
39. | Sep 27 |
Complete search methods. |
PDF |
40. | Oct 4 |
Local search techniques. |
PDF |
41. | Oct 11 |
Constraint satisfaction: formalisms and modelling. |
PDF |
42. | Oct 18 |
Constraint satisfaction: algorithms. |
PDF |
43. | Oct 25 |
Exam week: no lecture, no tutorial session. |
44. | Nov 1 |
Constraint satisfaction: global constraints, local search
Linear and integer programming: formalism. |
PDF |
45. | Nov 8 |
Linear and integer programming: modelling and tools. |
PDF |
46. | Nov 15 |
Linear and integer programming: algorithms. |
PDF |
47. | Nov 22 |
Genetic algorithms. |
PDF |
48. | Nov 29 |
Novel methods. |
PDF |
49. | Dec 6 |
Independence day: no lecture, no tutorial session. |
50. | Dec 13 |
Complexity of search. |
PDF |
The weekly problem sets will be available here as the course progresses.
The problem sets are likely to be quite similar to those in
Autumn 2006.
There will be three small programming assignments using Java.
The aim is to gain hands-on experience with the techniques learned in
the course.
- The first
programming assignment
has been published. Deadline for returning the
solutions is 25 October. For further
information please contact the course assistant,
André Schumacher.
- The second
programming assignment
has been published. Deadline for returning the
solutions is 8 November. For further
information please contact the course assistant,
André Schumacher.
- The third
programming assignment
has been published. Deadline for returning the
solutions is 29 November. For further
information please contact the course assistant,
André Schumacher.
The first set of assignments will be handed out on 4 Oct,
the second on 18 Oct, and the third on 8 Nov.
A functioning program for each of the assignments must
be developed personally by each participant and submitted,
together with a brief description of the solution method used,
by e-mail to the tutorial assistant within three weeks of
the hand-out date.
The course does not follow any existing textbook. Here are
some pointers to general literature covering material
discussed at the lectures in more depth:
- E. Aarts, J. K. Lenstra (Eds.),
Local Search in Combinatorial Optimization.
J. Wiley & Sons, Chichester UK, 1997.
- Krzysztof R. Apt:
Principles of Constraint Programming. Cambridge University Press, 2003.
Book contents.
- T. Bäck,
Evolutionary Algorithms in Theory and Practice.
Oxford University Press, 1996.
- D. Corne, M. Dorigo, F. Glover (Eds.),
New Ideas in Optimization.
McGraw-Hill, London, 1999.
- A. E. Eiben, J. E. Smith,
Introduction to Evolutionary Computing.
Springer-Verlag, Berlin Heidelberg, 2003.
- H. H. Hoos, T. Stützle,
Stochastic Local Search: Foundations and Applications.
Morgan Kaufmann (Elsevier), Amsterdam, 2005.
- W. Michiels, E. Aarts, J. Korst,
Theoretical Aspects of Local Search.
Springer-Verlag, Berlin Heidelberg, 2007.
- M. Mitchell,
An Introduction to Genetic Algorithms.
The MIT Press, Cambridge MA, 1996.
- C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization:
Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, 1982.
(Reprinted by Dover, Mineola NY, 1998.)
Some links to material related to topics discussed in course:
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 12 May 2008.
|