Proseminar: Komplexität konkreter Algorithmen
|
|
|
|
|
Veranstaltungsnummer: 18.058
Titel: Proseminar: Komplexität konkreter Algorithmen
Veranstalter: Berndt Farwer, Matthias Jantzen
Ort und Zeit: Mi 10-12 C-221
Lernziel:
- Kennenlernen von Grundlagen der Komplexitätstheorie, mit denen es möglich ist, die Effizienz von Algorithmen zu messen. Erwerb der Fähigkeit, das algorithmische Grundproblem einer gestellten Programmieraufgabe einzuschätzen.
- Umgang mit wissenschaftlicher Literatur (Lesen, Verstehen und Darstellen von wissenschaftlichen Texten).
Inhalt:
Es werden Algorithmen zur Lösung einiger in der Informatik immer wiederkehrender Probleme, wie z.B. Sortieren, Pattern Matching, Suche nach kürzesten Pfaden in Graphen vorgestellt und auf ihre Komplexität (Effizienz) hin untersucht. Zu Beginn des Semesters werden zunächst Kriterien für die Komplexität von Algorithmen vorgestellt, die es ermöglichen, Algorithmen unabhängig vom verwendeten Rechner und ohne Information über die Eingabe einzustufen.
Stellung im Studienplan: Grundstudium
Voraussetzung:
Grundkenntnisse im Programmieren, z.B. durch Beherrschung einer Programmiersprache oder Kenntnis des Informatik-A2-Stoffes.
Vorgehen:
Ausgewählte Arbeiten werden durch die Teilnehmer, evtl. in kleinen Gruppen, aufbereitet und vorgestellt. Im Plenum werden die Arbeiten diskutiert.
Literatur:
Material zu den Vorträgen wird zu Beginn des Semesters vergeben. Als Einführungen eignen sich u.a.:
- Sara Baase, Computer Algorithms
- Aho, Hopcroft, Ullman, Data Structures and Algorithms
Periodizität: unregelmäßig
Bemerkungen:
Für LehrerInnen / NebenfächlerInnen geeignet.
Last Change: 17:40 05/19/2011 Imprint/Disclaimer