Archive: Spring Semester 2016

Grundlagen der künstlichen Intelligenz

VV-Nr	13548-01
Dozierende	Malte Helmert Martin Wehrle
Assistierende	Thomas Keller
Tutoren	Patrick Buder
Zeit und Ort	Mo 17:15 - 19:00; Seminarraum 05.002, Spiegelgasse 5 Fr 13:15 - 15:00; Seminarraum 05.002, Spiegelgasse 5
Start	22.02.2016
Übungen	Fr 15:15 - 17:00; Seminarraum 05.002, Spiegelgasse 5
Voraussetzungen	Keine formalen Voraussetzungen, aber gute Basiskenntnisse in praktischer und theoretischer Informatik (Algorithmen, Komplexitätstheorie) sind zum Verständnis des Stoffs erforderlich. Gute Programmierkenntnisse sind für die Bearbeitung eines Teils der Übungsaufgaben notwendig.
Lernziele	Das Ziel ist es, ein grundlegendes theoretisches und praktisches Wissen über klassische Probleme in der KI und deren Lösungsmethoden zu erlangen. Insbesondere werden die Teilnehmer in der Lage sein, gängige KI-Probleme (durch die Implementierung und Evaluation geeigneter Lösungsalgorithmen) selbständig auf einer praktischen Ebene zu lösen.
Inhalte	Die Vorlesung bietet eine Einführung in die grundlegenden Sichtweisen, Probleme, Methoden und Techniken der Künstlichen Intelligenz. Thematische Schwerpunkte: Einführung und historische Entwicklung der KI, der Agentenbegriff in der KI, Problemlösen und Suche, Constraint-Satisfaction-Probleme, Logik und Repräsentation, Handlungsplanung.
Literatur	Stuart Russell und Peter Norvig: Artificial Intelligence - A Modern Approach (3. Auflage), Prentice Hall, 2009.
Leistungsüberprüfung	Lehrveranst.-begleitend Bitte beachten : Mündliche Prüfung, Termine nach Vereinbarung. Zur Überprüfung der Lernziele werden wöchentlich Übungsaufgaben angeboten. Für den Erhalt der Kreditpunkte ist die aktive Teilnahme an den Übungen und das Bestehen der mündlichen Abschlussprüfung notwendig. Aktive Teilnahme an den Übungen bedeutet Erreichen von mindestens 50% der Punkte aus den Übungsaufgaben. Die Note für die Veranstaltung basiert ausschliesslich auf der mündlichen Abschlussprüfung.
Kreditpunkte	6
Skala	1-6 0,5
Module	Vertiefungsmodul Computer Science (Bachelor Informatik 07) Vertiefungsmodul Bioinformatik (Bachelor Informatik 07) Modul Wahlbereich Informatik (BSF - Informatik) Modul Praxis aktueller Informatikmethoden (MSF - Informatik) Vertiefungsmodul Computational Intelligence (Bachelor Informatik 10) Vertiefungsmodul Life Science-Informatik (Bachelor Informatik 10) Modul Methoden für Computational Biology (Bachelor Computational Sciences 11) Modul Methoden für Computational Chemistry (Bachelor Computational Sciences 11) Modul Methoden für Computational Mathematics (Bachelor Computational Sciences 11) Modul Methoden für Computational Physics (Bachelor Computational Sciences 11)
Belegen	Services (Anmeldung mit Passwort)

Source: wikimedia commons

Vorlesungsfolien

Nr.	Thema	Datum	Folien
0.	Organizational Matters	22.02.2016	(Bildschirm) (Drucker)
1.	Introduction: What is Artificial Intelligence?	22.02.2016	(Bildschirm) (Drucker)
2.	Introduction: AI Past and Present	26.02.2016	(Bildschirm) (Drucker)
3.	Introduction: Rational Agents	26.02.2016	(Bildschirm) (Drucker)
4.	Introduction: Environments and Problem Solving Methods	29.02.2016	(Bildschirm) (Drucker)
5.	State-Space Search: State Spaces	29.02.2016	(Bildschirm) (Drucker)
6.	State-Space Search: Representation of State Spaces	04.03.2016	(Bildschirm) (Drucker)
7.	State-Space Search: Examples of State Spaces	04.03.2016	(Bildschirm) (Drucker)
8.	State-Space Search: Data Structures for Search Algorithms	07.03.2016	(Bildschirm) (Drucker)
9.	State-Space Search: Tree Search and Graph Search	07.03.2016	(Bildschirm) (Drucker)
10.	State-Space Search: Breadth-first Search	11.03.2016	(Bildschirm) (Drucker)
11.	State-Space Search: Uniform Cost Search	11.03.2016	(Bildschirm) (Drucker)
12.	State-Space Search: Depth-first Search & Iterative Deepening	14.03.2016	(Bildschirm) (Drucker)
13.	State-Space Search: Heuristics	14.03.2016	(Bildschirm) (Drucker)
14.	State-Space Search: Analysis of Heuristics	18.03.2016	(Bildschirm) (Drucker)
15.	State-Space Search: Best-first Graph Search	18.03.2016	(Bildschirm) (Drucker)
16.	State-Space Search: Greedy BFS, A, Weighted A	01.04.2016	(Bildschirm) (Drucker)
17.	State-Space Search: IDA*	01.04.2016	(Bildschirm) (Drucker)
18.	State-Space Search: Properties of A*, Part I	04.04.2016	(Bildschirm) (Drucker)
19.	State-Space Search: Properties of A*, Part II	04.04.2016	(Bildschirm) (Drucker)
20.	Combinatorial Optimization: Introduction and Hill-Climbing	08.04.2016	(Bildschirm) (Drucker)
21.	Combinatorial Optimization: Advanced Techniques	08.04.2016	(Bildschirm) (Drucker)
22.	Constraint Satisfaction Problems: Introduction and Examples	11.04.2016	(Bildschirm) (Drucker)
23.	Constraint Satisfaction Problems: Constraint Networks	11.04.2016	(Bildschirm) (Drucker)
24.	Constraint Satisfaction Problems: Backtracking	15.04.2016	(Bildschirm) (Drucker)
25.	Constraint Satisfaction Problems: Arc Consistency	15.04.2016	(Bildschirm) (Drucker)
26.	Constraint Satisfaction Problems: Path Consistency	18.04.2016	(Bildschirm) (Drucker)
27.	Constraint Satisfaction Problems: Constraint Graphs	18.04.2016	(Bildschirm) (Drucker)
28.	Constraint Satisfaction Problems: Decomposition Methods	22.04.2016	(Bildschirm) (Drucker)
29.	Propositional Logic: Basics	22.04.2016	(Bildschirm) (Drucker)
30.	Propositional Logic: Reasoning and Resolution	25.04.2016	(Bildschirm) (Drucker)
31.	Propositional Logic: DPLL Algorithm	25.04.2016	(Bildschirm) (Drucker)
32.	Propositional Logic: Local Search and Outlook	29.04.2016	(Bildschirm) (Drucker)
33.	Automated Planning: Introduction	29.04.2016	(Bildschirm) (Drucker)
34.	Automated Planning: Planning Formalisms	02.05.2016	(Bildschirm) (Drucker)
35.	Automated Planning: Delete Relaxation	02.05.2016	(Bildschirm) (Drucker)
36.	Automated Planning: Delete Relaxation Heuristics	09.05.2016	(Bildschirm) (Drucker)
37.	Automated Planning: Abstraction and Pattern Databases	13.05.2016	(Bildschirm) (Drucker)
38.	Automated Planning: Merge-and-Shrink Abstractions	13.05.2016	(Bildschirm) (Drucker)
39.	Automated Planning: Landmarks	20.05.2016	(Bildschirm) (Drucker)
40.	Automated Planning: Landmark Heuristics	20.05.2016	(Bildschirm) (Drucker)
41.	Board Games: Introduction and State of the Art	23.05.2016	(Bildschirm) (Drucker)
42.	Board Games: Minimax Search and Evaluation Functions	23.05.2016	(Bildschirm) (Drucker)
43.	Board Games: Alpha-Beta Search	27.05.2016	(Bildschirm) (Drucker)
44.	Monte-Carlo Tree Search: Introduction	27.05.2016	(Bildschirm) (Drucker)
45.	Monte-Carlo Tree Search: Advanced Topics	30.05.2016	(Bildschirm) (Drucker)
46.	AlphaGo and Outlook	30.05.2016	(Bildschirm) (Drucker)
47.	Research Group Artificial Intelligence: Introducing Ourselves	03.06.2016	(Bildschirm)

Übungsblätter

Nr.	Abgabedatum	Dateien
1.	04.03.2016	Blatt 1
2.	11.03.2016	Blatt 2 state-spaces.tar
3.	18.03.2016	Blatt 3 uniform-cost-search.tar
4.	01.04.2016	Blatt 4
5.	08.04.2016	Blatt 5 astar-search.tar
6.	15.04.2016	Blatt 6 chess-board.tex
7.	22.04.2016	Blatt 7
8.	29.04.2016	Blatt 8 cantons.dot
9.	09.05.2016	Blatt 9
10.	13.05.2016	Blatt 10 bridges-strips-domain.pddl koenigsberg-problem.pddl
11.	20.05.2016	Blatt 11
12.	27.05.2016	Blatt 12

Zusatzmaterial

Kap.	Beschreibung	Dateien
1.	Turings "Computation Machinery and Intelligence"	PDF
2.	Bowling et al.'s "Heads-up Limit Hold’em Poker is Solved"	PDF
2.	DARPA Grand Challenge, Video 1	Video
2.	DARPA Grand Challenge, Video 2	Video
3.	Silver et al.'s "Mastering the game of Go with deep neural networks and tree search"	(*)
6.	8-Puzzle als expliziter Graph	BZ2
6.	8-Puzzle deklarativ repräsentiert	Zip
6.	8-Puzzle als Black Box	Zip
6.	Delling et al.'s "Engineering Route Planning Algorithms"	PDF
8.	Burns et al.'s "Implementing Fast Heuristic Search Code"	PDF
10.	Korf und Schultzes "Large-Scale Parallel Breadth-First Search"	PDF
12.	Aufwandsberechnung iterative Tiefensuche	Python
22.	McGuire et al.'s "There is no 16-Clue Sudoku"	PDF
26.	Simonis' "Sudoku as a Constraint Problem"	PDF
32.	Bayless et al.'s "SAT Modulo Monotonic Theories"	PDF
34.	PDDL-Beispiel	Zip
36.	Keyder and Geffners "Heuristics for Planning with Action Costs Revisited"	PDF
42.	Schaeffer et al.'s "Checkers Is Solved"	(*)

(*) Please get in touch with us if you are interested in this material. For copyright reasons, we are not allowed to make it available online.