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
go Propositional and first-order logics (syntax, semantics, inference) (pdf verzia)

Internet demos

Code experiments

Software online tools
Code snippets

Students' projects (2018)

Auxiliary code for Mancala project
Sudoku

Topics

  1. Definition of symbolic artificial intelligence
  2. Rational agent
  3. Environment types
  4. State space definition
  5. Search tree (tree nodes versus states)
  6. Properties of search strategies
  7. Breadth-first search - algorithm, properties
  8. Depth-first search - algorithm, properties, depth limitation
  9. Iterative deepening, bidirectional search
  10. Best-first search - algorithm structure
  11. Cost function types (uniform-cost search, greedy search, A* search)
  12. A* - heuristic function admissibility deduction
  13. Optimality and complexity of A*
  14. A* - comparison of heuristics
  15. Creation of heuristics
  16. Propositional logic (syntax, semantics)
  17. Knowledge representation (grounding, variables, constraints)
  18. CNF (syntax, transformation)
  19. Inference in propositional logic (model searching, deduction)
  20. Resolution in propositional logic (principles)
  21. DPLL algorithm (basic form, extensions)
  22. Implication graph, conflict analysis
  23. Zero/First order predicate logic (syntax)
  24. Variables in FOL (free/close variables, quantifiers)
  25. Semantics of FOL (interpretations)
  26. Knowledge representation in FOL, transformation to CNF
  27. Inference in FOL (model checking, direct proof, proof by refutation)
  28. Resolution in first order logic
  29. Unification of literals
  30. Resolution-based algorithm (extensions)
  31. Answering questions in FOL
  32. Derivation graph, resolution strategies
  33. Semantic networks (structure,elements)
  34. Inference in semantic networks
  35. Frames and scripts (slots, facets, if-needed, if-added, if-deleted)
  36. Constraints (domains, explicit and induced constraints, search space)
  37. Consistency ((i,j)-consistency, arc, path and inverse path consistency)
  38. Consistency enforcing algorithms (AC)
  39. Combination of consistency levels (RPC, k-RPC, max-RPC)
  40. Search-based solving of constrained problems (backtracking)
  41. Search improvement - jump algorithms (conflict-directed backjumping)
  42. Search improvement - memory algorithms (backchecking, no-goods recording)
  43. Search improvement - ordering algorithms (variable ordering, value ordering)
  44. Combination of consistency and search algorithms (forward checking)
  45. Horn logic
  46. Forward chaining (principle, resolution rule, hyperresolution)
  47. Forward chaining algorithm
  48. Production system (basic concepts, Clips)
  49. Production cycle (agenda, activations, rule firing)
  50. Rete network structure (alpha and beta networks, node types)
  51. Propagation of working memory changes through Rete network
  52. Negation in Rete network (single and double negation)
  53. Backward chaining (principle, resolution rule)
  54. Backward chaining algorithm
  55. Prolog (syntax, depth-first database searching)
  56. 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