Universität Bielefeld University of Bielefeld - Faculty of Technology - Artificial Intelligence Group


Intelligente Algorithmen

Seminar im Hauptstudium, Wintersemester 2003/2004

Termin: Do 16-18
Raum: V2-213
Beginn: 16.10.2003
Veranstalter: Stefan Kopp, Nadine Leßmann, Alf Kranstedt

Hilfen für die Erarbeitung von Vorträgen und Ausarbeitungen

Zum Runterladen gibt's hier eine Anleitung für die Erarbeitung von Vorträgen,
einen ausführlicheren "Speaker's Guide" aus dem Netz,
und unsere Vorstellungen über die Erstellung von Hausarbeiten
mit einer gesonderten Anleitung für die Gestaltung des Literaturverzeichnisses.
Desweiteren verweisen wir auf die Angebote des Schreiblabors der Universität.

Hier gibt's einen Text, den Ihr Euch für die Abschlussdiskussion ansehen solltet. Er vergleicht einige der im Seminar vorgestellten Verfahren hinsicht Adäquatheit und Effizienz.


Voraussetzungen/Vorkenntnisse:

Das Seminar ist als Ergänzung zur Vorlesung "Methoden der KI" gedacht und richtet sich an Studierende im Hauptstudium. Die Bereitschaft, sich auch mit abstrakteren mathematischen Formalismen auseinanderzusetzen wird vorausgesetzt.
Eine Teilnehmerliste hängt ab September in M4-122 aus. Es wird gebeten, sich dort vor Beginn des Semesters einzutragen.

Inhalt/Kommentar:

Unter intelligenten Algorithmen versteht man in der KI Verfahren, die gezielt Heuristiken einsetzen, um Probleme zu lösen, die ansonsten nur mit unverhältnismäßigen Aufwand (nicht effizienter als in exponentieller Zeit) vollständig lösbar wären. In diesem Seminar soll zunächst der Begriff der Problemkomplexität (P/NP) eingeführt werden. Anhand von ausgewählten Problemen (z.B. dem Traveling-Salesman-Problem aus dem Bereich Planen und Suchen, dem Subgraph-Matching aus der Graphentheorie und einem Problem aus der Spieltheorie) werden verschiedene algorithmische Lösungsansätze in Form ausgearbeiteter Vorträge vorgestellt. Dabei sollen verschiedene Ansätze wie z.B. heuristische Suchverfahren oder genetische Algorithmen erarbeitet, miteinander verglichen und auf ihre Anwendbarkeit für das konkrete Problem evaluiert werden. Auf Wunsch können ausgewählte Verfahren auch praktisch erarbeitet, implementiert und im Plenum demonstriert werden.

Terminübersicht

16.10.2003 Die Veranstalter Einführung und Organisatorisches
23.10.2003 Die Veranstalter Einführungsvortrag zur Problematik P/NP
30.10.2003 Die Veranstalter Suchverfahren
6.11.2003 Olaf Graeser Tabusuche
13.11.2003 Walli Hein Dynamisches Programmieren
20.11.2003 Adam El Sayed Auf / Kai Linnemann Genetische/Evolutionäre Algorithmen I
27.11.2003 Adam El Sayed Auf / Kai Linnemann Genetische/Evolutionäre Algorithmen II
4.12.2003   fällt aus
11.12.2003 Frank Schönmann Lineares Programmieren: Cutting-planes
18.12.2003 Jan Lümkemann Kooperatives Lernen: Ant Colonies
8.1.2004 Christoph Niehaus Randomisierte Verfahren: Simulated Annealing, Monte Carlo
15.1.2004 Tolga Dalman Quantencomputing
22.1.2004   fällt aus
29.1.2004   fällt aus
5.2.2004   Abschlußdiskussion


Literatur & Links

Diese Liste ist nicht statisch! Sie sollständig aktualisiert werden. Dabei nehmen wir gerne Anregungen von Euch auf!
Alle hier aufgeführten Texte sind, soweit nicht anders angegeben, über uns zu bekommen.

Überblicksliteratur: Komplexitätstheorie, NP-Vollständigkeit und kombinatorische Optimierung

Das Traveling Salesman Problem

Suchverfahren (Tabu Search)

Graphentheorie: Branch and Bound

Randomisierte Verfahren: Simulated Annealing, Monte Carlo

Dynamisches Programmieren

Lineares Programmieren: Die Cutting-Plane Methode

Genetisches/Evolutionäres Programmieren

Kombinierte Verfahren: Memetische Algorithmen

Kooperatives Lernen: Ant Colonies

Vergleichende Literatur


Vorträge

Folien der schon gelaufenen Vorträge zum Downloaden:

Ausarbeitungen


Stefan Kopp,
Nadine Leßmann,
Alf Kranstedt,

13.11.2003