- de
- en
Lecture: Foundations of Artificial Intelligence
Course Number | 13548-01 |
Lecturers | Malte Helmert |
Assistants | Thomas Keller |
Tutors | Jendrik Seipp Silvan Sievers |
Time and Location | Mon 16:15 - 18:00; Seminarraum 05.002, Spiegelgasse 5 Wed 14:15 - 16:00; Seminarraum 05.002, Spiegelgasse 5 |
Start | 26-02-2018 |
Exercises | Tue 16:15 - 18:00; Seminarraum 00.003, Spiegelgasse 1 Wed 16:15 - 18:00; Computer-Labor U1.001, Spiegelgasse 1 Group assignment (Requires login) |
Prerequisites | No formal requirements, but solid basic knowledge of foundational concepts in computer science (algorithms, complexity theory) and mathematics (formal proofs and basic concepts like sets, functions and relations) are necessary for following the lecture. Good programming skills are necessary for some of the exercises. |
Objectives | Students learn the theoretical and practical foundations of classical problems in artificial intelligence and their algorithmic solution. In particular, participants will obtain the necessary knowledge and skills to independently solve typical AI problems by selecting, implementing and evaluating standard algorithms from the AI literature. |
Contents | The course offers an introduction into the basic concepts, problems, methods and algorithms of artificial intelligence. Topics include: introduction and historical development of AI, rational agents, problem solving and search, constraint satisfaction problems, formal logic, and automated planning. |
Literature | Stuart Russell and Peter Norvig: Artificial Intelligence - A Modern Approach (3rd edition), Prentice Hall, 2009. |
Assessment | Lehrveranst.-begleitend Please note: The course includes weekly homework assignments and weekly exercise sessions. To pass the course, students need to successfully work on the homework assignments and pass the final written examination. At least 50% of the possible marks from homework assignment are needed to qualify for the final exam. The final grade for the course is based exclusively on the final exam. The written exam will take place on Wednesday, 13 June, 2-4 p.m., at Spiegelgasse 1, room 00.003. |
Credit Points | 8 |
Grades | 1-6 0,5 |
Registration | Services (Requires login) |
Slides
No. | Topic | Date | Slides |
0. | Organizational Matters | 26.02.2018 | (Screen) (Printer) |
1. | Introduction: What is Artificial Intelligence? | 26.02.2018 | (Screen) (Printer) |
2. | Introduction: AI Past and Present | 05.03.2018 | (Screen) (Printer) |
3. | Introduction: Rational Agents | 05.03.2018 | (Screen) (Printer) |
4. | Introduction: Environments and Problem Solving Methods | 07.03.2018 | (Screen) (Printer) |
5. | Introduction: State-Space Search: State Spaces | 07.03.2018 | (Screen) (Printer) |
6. | State-Space Search: Representation of State Spaces | 12.03.2018 | (Screen) (Printer) |
7. | State-Space Search: Examples of State Spaces | 12.03.2017 | (Screen) (Printer) |
8. | State-Space Search: Data Structures for Search Algorithms | 14.03.2018 | (Screen) (Printer) |
9. | State-Space Search: Tree Search and Graph Search | 14.03.2018 | (Screen) (Printer) |
10. | State-Space Search: Breadth-first Search | 19.03.2018 | (Screen) (Printer) |
11. | State-Space Search: Uniform Cost Search | 19.03.2018 | (Screen) (Printer) |
12. | State-Space Search: Depth-first Search & Iterative Deepening | 21.03.2018 | (Screen) (Printer) |
13. | State-Space Search: Heuristics | 21.03.2018 | (Screen) (Printer) |
14. | State-Space Search: Analysis of Heuristics | 26.03.2018 | (Screen) (Printer) |
15. | State-Space Search: Best-first Graph Search | 26.03.2018 | (Screen) (Printer) |
16. | State-Space Search: Greedy BFS, A*, Weighted A* | 28.03.2017 | (Screen) (Printer) |
17. | State-Space Search: IDA* | 28.03.2017 | (Screen) (Printer) |
18. | State-Space Search: Properties of A*, Part I | 04.04.2018 | (Screen) (Printer) |
19. | State-Space Search: Properties of A*, Part II | 04.04.2018 | (Screen) (Printer) |
20. | Combinatorial Optimization: Introduction and Hill-Climbing | 09.04.2018 | (Screen) (Printer) |
21. | Combinatorial Optimization: Advanced Techniques | 09.04.2018 | (Screen) (Printer) |
22. | Constraint Satisfaction Problems: Introduction and Examples | 11.04.2018 | (Screen) (Printer) |
23. | Constraint Satisfaction Problems: Constraint Networks | 11.04.2018 | (Screen) (Printer) |
24. | Constraint Satisfaction Problems: Backtracking | 16.04.2018 | (Screen) (Printer) |
25. | Constraint Satisfaction Problems: Arc Consistency | 16.04.2018 | (Screen) (Printer) |
26. | Constraint Satisfaction Problems: Path Consistency | 18.04.2018 | (Screen) (Printer) |
27. | Constraint Satisfaction Problems: Constraint Graphs | 18.04.2018 | (Screen) (Printer) |
Exercise sheets
No. | Due Date | Files |
1. | 14.03.2018 | Sheet 1 |
*. | -- | Presence sheet 1 state-spaces.tar.gz |
2. | 21.03.2018 | Sheet 2 state-spaces.tar.gz |
3. | 28.03.2018 | Sheet 3 uniform-cost-search.tar.gz |
4. | 11.04.2018 | Sheet 4 astar-search.tar.gz |
*. | -- | Presence sheet 2 hill-climbing.tar.gz |
5. | 18.04.2018 | Sheet 5 hill-climbing.tar.gz |
6. | 25.04.2018 | Sheet 6 |
Supplementary material
Chap. | Description | Files |
1. | Turing's "Computation Machinery and Intelligence" | |
2. | Bowling et al.'s "Heads-up Limit Hold’em Poker is Solved" | |
6. | 8-Puzzle as explicit graph | BZ2 |
6. | 8-Puzzle declaratively represented | Zip |
6. | 8-Puzzle as black box | Zip |
6. | Delling et al.'s "Engineering Route Planning Algorithms" | |
8. | Burns et al.'s "Implementing Fast Heuristic Search Code" | |
10. | Korf and Schultze's "Large-Scale Parallel Breadth-First Search" | |
12. | Complexity estimation script | Python |
12. | Korf's "Depth-First Iterative Deepening: An Optimal Admissible Tree Search" | (*) |
22. | McGuire et al.'s "There is no 16-Clue Sudoku" | |
22. | Numberphile video on Four Colour Problem | Youtube |
26. | Simonis' "Sudoku as a Constraint Problem" |