• course annotation on Study Programmes pages (look at Intelligent Systems - Bc level)

Basic study literature for the course, complementing lectures:

• State space reprezentation
• Bling search through state space

• Heuristic search through state space, Algorithmus A*

• Game tree representation
• Search through game trees

• Problem reduction + And-or trees

• Section 1: Propositional logic

• Section 2: Predicate logic

• Section 3: Horn logic (forward and backward rule chaining)

• Crossword puzzle
• Consistency algorithms
• Search algorithms

• Semantic nets

• Frames and scripts

Additional material to the course

Lecture presentations (in Slovak)

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

Internet materials/demos

• A* pathfinding
• Search algorithm pathfinding
• Graph search (BFS and DFS, A*)
• Alpha-beta prunning
• Predicate logic resolution examples

Code experiments

Students' projects (2018)

Final exam 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

Copyright © MM

Last updated 22.10.2019