# Exam

version 2025/2026

## Foundations

- Define a constraint satisfaction problem (including the notion of constraint) and its solution.
- Define Boolean CSP and Binary CSP and show transformations of CSP to Binary CSP (dual encoding, hidden variable encoding).

## Local search techniques

- Explain the core principles and notions of local search, including intensification and diversification, (non)strict local/global optimum, plateau.
- Describe hill climbing, min-conflicts, and random walk techniques and discuss their relations.
- Describe Tabu Search, GSAT, Genet, and simulated annealing and discus their properties.

## Look-back search techniques

- Describe backtracking as a CSP solving technique, discuss its weaknesses (thrashing, redundant work, late detection of conflicts).
- Describe backjumping and its versions (graph-directed, Gaschnig), discuss how to find a conflicting variable.
- Describe dynamic backtracking and its core components.
- Describe backmarking.

## Consistency techniques

- Define Node Consistency and describe how it can be achieved.
- Define Arc Consistency and describe and compare algorithms to achieve it (AC-1, AC-2, AC-3, AC-4, AC-3.1), Discuss their time complexities.
- Define Directional Arc Consistency, compare it with AC (discuss tree-structured CSPs), and describe how it can be achieved.
- Define Path Consistency and describe algorithms to achieve it (PC-1, PC-2 in detail, other in principle), define direction path consistency.
- Describe relations between AC and PC, explain restricted path consistency algorithm.
- Define the concepts of (strong) k-consistency and (i,j)-consistency and their relation to backtrack-free search.
- Explain inverse and singleton consistencies.

## Higher-arity constraints

- Define Generalized Arc Consistency and describe how it be achieved.
- Define global constraints and describe their relation to GAC, give some examples of global constraints including the filtering algorithm (all-diVerent, gcc, lex, regular, grammar, slide, unary resources).

## Consistency techniques in search

- Describe integration of consistency techniques and search.
- Describe and compare forward checking, partial look-ahead, and full look-ahead.
- Describe variable-ordering and value ordering heuristics, explain fail-first and succeed-first principles.
- Describe various branching schemas (enumeration, step labeling, bisection).
- Explain cycle-cutset technique and MAC Extended algorithm.

## Incomplete and discrepancy search techniques

- Explain the principle of incomplete depth-first search.
- Describe algorithms bounded backtrack, iterative broadening, depth-bounded, and credit search.
- Explain principles of discrepancy search, describe Limited Discrepancy Search, Improved LDS, and Depth-Bounded Discrepancy Search.

## Constraint Optimization

- Define a constraint optimization problem, including the representation of objective function.
- Describe branch-and-bound technique and its versions.

## Over-constrained problems

- Define an over-constrained problem.
- Describe techniques Partial CSP, Valued CSP, and Semiring-based CSP and their instances.
- Define constraint hierarchies, including comparators (local/global, predicate/metric) and describe techniques to solve them (DeltaStar, DeltaBlue, Indigo, projection).