Hauptinhalt
Datenstrukturen, Algorithmen und Programmierung 2
im Sommersemester 2012
[
Aktuelles]
[
Inhalt]
[
Begleitmaterial]
[
Teilnahmevoraussetzungen]
[
Studienleistungen]
[
Klausur]
[
Literatur]
[
Wiki und Forum]
Anmeldung zur Übung ist möglich mit
ASSESS.
Die Vorlesung beginnt erst am Donnerstag den 5.4.2012.
Damit ein Algorithmus eine Aufgabenstellung sinnvoll löst, muss er zum einen korrekt arbeiten, zum anderen
aber auch eine Lösung des Problems in annehmbarer Zeit berechnen, d.h. effizient sein. Um die Qualität von Algorithmen zu bewerten, muss man daher ihre Korrektheit und Effizienz beurteilen können. Neben der Bewertung von bestehenden Algorithmen ist ein wichtiges Arbeitsfeld eines Informatikers auch der Entwurf neuer Methoden zur Lösung von Problemen. Die Kenntnis grundlegender Methoden zum Entwurf von Algorithmen ist dabei ein wichtiges Werkzeug.
Daher ist das Ziel der Vorlesung Datenstrukturen, Algorithmen und Programmierung 2 das Erlernen von
- Methoden zur Bewertung der Effizienz von Algorithmen und Datenstrukturen
- Methoden zum Entwurf effizienter Algorithmen
- grundlegenden Algorithmen und Datenstrukturen
- Methoden zur Verifikation der Korrektheit von Algorithmen und Datenstrukturen.
Die in der Vorlesung untersuchten Probleme sind grundlegend für den Algorithmenentwurf und dienen insbesondere auch dazu, Entwurfs- und Analysemethoden zu illustrieren.
Das erlernte Wissen soll im Rahmen des zugehörigen Praktikums umgesetzt und vertieft werden.
Als Ergänzung zur Vorlesung eignet sich am besten das Buch "Introduction to Algorithms"
von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Das Buch ist auch
als dt. Version erschienen (Algorithmen - eine Einführung).
Vorlesungsfolien
05.04.2011:
Einführung und Laufzeit von Insertion Sort
10.04.2011:
Laufzeit von Insertion Sort und O-Notation
12.04.2011:
Laufzeit- und Korrektheitanalyse von Programmen
17.04.2011:
Korrektheitsanalyse und Teile und Herrsche Algorithmen - Mergesort
19.04.2011:
Teile und Herrsche Algorithmen - Binäre Suche und Multiplikation zweier Integer
24.04.2011:
Teile und Herrsche Algorithmen - Integer Multiplikation und allgemeine Analyse von Rekursionsgleichungen
26.04.2011:
Teile und Herrsche Algorithmen - Konvexe Hülle
03.05.2011:
Gierige Algorithmen - Einführung und Interval Scheduling
10.05.2011:
Gierige Algorithmen - Scheduling mit Deadlines (vorläufig aus dem letzten Jahr)
Für Studierende in den Informatik-Bachelor-Studiengängen ist die Studienleistung im Praktikum zu DAP1 Teilnahmevoraussetzung zur Modulprüfung DAP2.
Wenn Sie in einem anderen Studiengang studieren, überprüfen Sie bitte anhand ihres Modulhandbuchs, welche Voraussetzungen für Sie gelten!
Für Studierende in den Informatik-Bachelor-Studiengängen ist die Erbringung von Studienleistungen verpflichtender Bestandteil des Moduls DAP2.
Wenn Sie in einem anderen Studiengang studieren, überprüfen Sie bitte anhand ihres Modulhandbuchs, welche Studienleistungen für Sie verpflichend sind!
Nähere Informationen zu den einzelnen Studienleistungen finden sich auf den Webseiten zu den Übungen und zum Praktikum.
ACHTUNG: Für Studierende der Fächer ET/IT und IKT gibt es ein eigenes Praktikum.
Es werden zwei Klausuren mit einer Länge von jeweils 180 Minuten angeboten (90 Min. für Diplom Studiengänge).
Hinweise:
- Als Hilfsmittel ist ausschließlich ein handbeschriebener DIN-A4-Zettel erlaubt.
- Zur Bearbeitung der Klausur ist ein dokumentenechter, nicht roter Stift mitzubringen.
- Am Platz ist ein amtlicher Lichtbildausweis, sowie ein gültiger Studierendenausweis oder eine gültige Immatrikulationsbescheinigung mitzuführen.
- Seien Sie bei Klausurterminen bitte besonders pünktlich anwesend.
Termine:
- Di, 24.07.2012, 14-18 Uhr
- Di, 02.10.2012, 12:30-16:30 Uhr
Hörsäle:
- Audimax
- HG 2, HS 1
- HG 2, HS 3
- HG 2, HS 5
Die Hörsaalzuordnungen werden rechtzeitig bekannt gegeben.
Zur Vorlesung, den Übungen und dem Praktikum gibt es ein Forum.
Das Forum bietet Ihnen die Möglichkeit, sich untereinander Hilfestellung zu geben und über die Inhalte und das Organisatorische zu diskutieren.
- [CLRS] Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms", MIT Press / McGraw-Hill, 2nd ed., ISBN: 0-262-53196-8
- [DL] Demaine, Leiserson: "Introduction to Algorithms", Vorlesungsmaterialien (Folien, Video, Audio), MIT OpenCourseWare, Cambridge, Fall 2005. → Vorlesungsmaterialien online erhältlich!
- [KT] Kleinberg, Tardos: "Algorithm Design", Addison-Wesley, ISBN: 0-321-29535-8
- [OW] Ottman, Widmayer: "Algorithmen und Datenstrukturen", Spektrum Akademischer Verlag, ISBN: 3-827-41029-0
- [Sei] Seidel (ed.): "Datenstrukturen und Algorithmen", Vorlesungsskript, Universität des Saarlandes, WS 1995/96. → Vorlesungsskript online erhältlich!
Letzte Änderung am 3.04.2012 von C. Schwiegelshohn
