This course, offered to the Master in Computer Science and Engineering , deepens the knowledge on the topic of Search, listed in theACM Computing Curriculum 2020 in the area of Intelligent Systems (IS / items A, B and C), and its use for solving combinatorial problems.
Combinatorial problems (both satisfaction and/or optimization) are common in many application domains (resource management, scheduling, timetabling) including computer science itself (eg hardware/software configuration, program verification). The complexity of combinatorial problems require the use of efficient methods of resolution, studied in this course unit, and based on complete search in finite (or Boolean) domains, constraint propagation to narrow the variable domains during search. The course also addresses constraint propagation adapted for continuous domains, although in this case the completeness of search cannot be generally guaranteed.
Knowledge:
Application:
Soft-skills:
|
1. Decision problems in discrete domains.
2. Problem Modelling.
3. Problem Solving.
4. Introduction to Interval Constraints.
5. Continuous Constraints and Interval analysis.
6. Interval Newton Method.
7. Associating Narrowing Functions to Constraints.
8. Constraint Propagation and Consistency Enforcement.
9. Problem Solving in Continuous Domains.
Main References:
Complementary Reference:
N/A
Hours per credit | 28 | ||
Hours per week | Weeks | Hours | |
Aulas práticas e laboratoriais | 24.0 | ||
Aulas teóricas | 24.0 | ||
Avaliação | 6.0 | ||
Self study | 54.0 | ||
Orientação tutorial | 6.0 | ||
Project | 54.0 | ||
Total hours | 168 | ||
ECTS | 6.0 |