Lecture presentations (in Slovak)

Basic terms (solution, candidate, candidate space, problem types)
(pdf)


Prototype combinatorial problems (satisfiability, travelling salesman, graph coloring)
(pdf)


Search paradigms (perturbative, constructive, systematic and local search)
(pdf)


DavisPutnam procedure
(pdf)


Local search (neighbourhood, algorithm structure, search trajectory)
(pdf)


Iterative improvement
(pdf)


Escape from local optimum (restarts, VND, VDS, RII, PII, TS, DLS)
(pdf)


Hybrid local search (ILS, GRASP, AICS)
(pdf)


Ant system algorithm
(pdf)


Bacterial foraging optimization algorithm
(pdf)


Artificial bee colony algorithm
(pdf)


Evolutionary algorithm
(pdf)


Estimation of Distribution algorithms
(pdf)


Computational complexity (P, NP, NPhard, NPcomplete, APX, PTAS, FPTAS)
(pdf)
[EXT:
youtubeshort,
youtubelong]

Topics
 Usage of prototype model in problem solving
 numerical/combinatorial optimisation
 problem structure, optimization types
 problem types (decision, optimisation and combined problem)
 traditional combinatorial problems
 SAT problem (informal and formal description, characteristics)
 TSP problem (informal and formal description, characteristics)
 GC problem (informal and formal description, characteristics)
 searching for solutions
 search as a solving paradigm
 perturbative and constructive search
 systematic and local search
 combination of search types
 search type selection
 local search
 characteristics of local search
 neighbourhood (role, definition) and neighbourhood graph
 basic components of local search (init, step, term)
 structure of local search (decision and optimisation problem)
 search trajectory
 iterative improvement
 informed vs. uninformed search strategy
 evaluation function
 iterative improvement (basic components)
 structure of iterative improvement
 escape from local optima
 random restarts (characteristics, structure)
 larger neighbourhood (pruning, pivot rules)
 neighbourhood switching
 VND (variable neighbourhood descent) structure
 step beyond neighbourhood (step construction in LK)
 VDS (variable depth search) structure
 acceptance of inferior candidates
 RII (randomised iterative improvement) characteristics and structure
 PII (probabilistic iterative improvement) characteristics and structure
 tabu search (short term memory, acceptance criterion, long term memory)
 TS (tabu search) structure
 dynamic changes of evaluation function
 DLS (dynamic local search) structure
 simulated annealing
 candidate acceptance
 algorithm structure
 annealing schedule
 hybrid search algorithms
 hybrid strategies
 GRASP (greedy randomised adaptive search procedure) characteristics and structure
 GRASP  constructive phase (greedyrandom, randomgreedy, random+greedy)
 pathrelinking (principle, usage in GRASP)
 AICS (adaptive iterated construction search) characteristics and structure
 biologically inspired algorithms  ant system
 ant characteristics, shortest path search
 AS (ant system) as a search algorithm
 AS  artificial ant world
 AS  selection of move direction
 AS  pheromone maintenance
 AS structure
 AS for MAXSAT (world topology and dynamics)
 biologically inspired algorithms  bacterial foraging
 movement vs food search (general animal, bacteria)
 movement of E.coli (basic movement, external influence, social influence)
 mapping between E.coli movement and BFO algorithm
 BFO  step function
 BFO structure
 BFO  social behaviour
 biologically inspired algorithms  bee colonies
 model of bee foraging, waggle dance
 mapping between bee colony and ABC algorithm
 ABC  simplified model of bee colony
 ABC  principles
 ABC structure
 ABC  source exploitation
 ABC  as a search algorithm
 biologically inspired algorithms  evolutionary algorithms
 natural selection and its model
 genetic transfer and its model
 EA structure
 estimation of distribution algoritms
 characteristics of EDA
 EDA structure
 probabilistic models
 UMDA characteristics
 UMDA structure
 PBIL characteristics
 PBIL structure
 MIMIC characteristics
 MIMIC structure
 BMDA characteristics
 BMDA structure
 computational complexity
 theory of computational complexity
 complexity of algorithms and problems
 P and NP complexity classes
 NPhard and NPcomplete complexity classes
 complexity of combinatorial problems
 solving NP problems
 stochastic versus deterministic search
 associated approximation problem, approximation complexity classes (APX, PTAS, FPTAS)
 randomised algorithms, MAXSAT randomised algorithm
