Course on Intelligent Decision-making Systems

-> Home page -> Teaching activities flag

Basic study literature for the course, complementing lectures:

Uninformed state space search
Informed state space search
Adversarial search
And-or tree search
Propositional logic
Predicate logic
Horn logic
Constraints
Semantic nets
Frames and scripts

Additional material to the course

Lecture presentations (in Slovak)

go Introduction (symbolic AI, rational agent and environment) (pdf verzia)
go Search space (pdf verzia)
go Uninformed state space search (breadth/depth first, iter.deepening, uniform cost) (pdf verzia)
go Informed state space search (greedy search, A*) (pdf verzia)
go Search in different environments (memory bounded) (pdf verzia)
go Game tree search (minimax, alfa-beta prunning, expectimax) (pdf verzia)
go Constraints (consistency enforcing, search) (pdf verzia)
go DPLL algorithm (pdf verzia)
go Prolog and Clips (prolog pdf verzia, older)
go Propositional and first-order logics (syntax, semantics, inference) (pdf verzia)

Internet materials/demos

Code experiments

Software online tools
Code snippets

Students' projects (2018)

Auxiliary code for Mancala project
Sudoku

Topics

  1. State space definition
  2. Search tree (tree nodes versus states)
  3. Properties of search strategies
  4. Breadth-first search - algorithm, properties
  5. Depth-first search - algorithm, properties, depth limitation
  6. Iterative deepening
  7. Uniform cost search
  8. Bidirectional search
  9. Best-first search - algorithm structure
  10. Cost function types
  11. Greedy search - cost function, algorithm, properties
  12. A* - cost function, algorithm
  13. A* - heuristic function admissibility deduction
  14. Optimality and complexity of A*
  15. Creation of heuristics
  16. Memory bounded search (RBFS)
  17. A* - suboptimal search (A*eps, dynamic weighting)
  18. Game trees (deterministic turn-taking two-player zero-sum games)
  19. Evaluation of game tree nodes (minimax)
  20. Alfa-beta prunning
  21. Partial game trees (static evaluation function, cutting off level)
  22. Games with chance (expectiminimax)
  23. Constraints (domains, explicit and induced constraints, search space)
  24. Constraint network
  25. Consistency ((i,j)-consistency, arc, path and inverse path consistency)
  26. Consistency enforcing algorithms (AC)
  27. Combination of consistency levels (RPC, k-RPC, max-RPC)
  28. Singleton consistency algorithms (SAC, SPIC, SRPC)
  29. Search-based solving of constrained problems (backtracking)
  30. Search improvement - jump algorithms (conflict-directed backjumping)
  31. Search improvement - memory algorithms (backchecking, no-goods recording)
  32. Search improvement - ordering algorithms (variable ordering, value ordering)
  33. Combination of consistency and search algorithms (forward checking)
  34. Problem reduction, AND/OR graphs
  35. AND/OR graph search (breadth first, heuristic)
  36. Logic and inference (entailment, soundness, completeness and grounding)
  37. Propositional logic (syntax, semantics)
  38. Inference in propositional logic (model checking, direct proof, refutation proof)
  39. Knowledge representation (grounding, variables, constraints)
  40. CNF (syntax, transformation)
  41. Basic tasks in propositional logic (model searching, deduction)
  42. Resolution in propositional logic (principles, strategies)
  43. DPLL algorithm (basic form)
  44. DPLL algorithm - extensions
  45. DPLL -Implication graph, conflict analysis
  46. DPLL algorithm - heuristics
  47. SAT encoding (cardinality constraints)
  48. Zero/First order predicate logic (syntax)
  49. Variables in FOL (free/bound variables, quantifiers)
  50. Semantics of FOL (interpretations)
  51. Knowledge representation in FOL, transformation to CNF
  52. Inference in FOL (proof by refutation)
  53. Resolution in first order logic
  54. Unification of literals
  55. Resolution-based algorithm (extensions)
  56. Answering questions in FOL
  57. Derivation graph, resolution strategies
  58. Horn logic
  59. Backward chaining (principle, resolution rule)
  60. Backward chaining algorithm
  61. Prolog (syntax, depth-first database searching)
  62. Box model

Additional reading

aima Artificial Intelligence: A Modern Approach - the third edition of a now classic AI textbook (used in more than 1000 universities)

Copyright MM
Last updated 23.5.2018