SOPRA: Für die Studenten, die sich für SoPra angemeldet haben,
die Klausur jedoch nicht bestanden haben findet eine zeitnahe Einsichtnahme statt:
Fr. 4.August, 10:00-11:00 (Sem.Raum 2.02, OH14).
Diese Einsichtnahme ist ausschliesslich für diese Studenten!
Klausurergebnisse:
Von den 260 Teilnehmern haben 128 bestanden (49,2 Prozent).
Gratulation an alle die die Klausur positiv bestanden haben, insbesondere an die beiden Studenten die uns
(bei ihrem ersten Antritt!) bei der Korrektur mit 58 bzw. mit allen 60 Punkten
besonders Freude gemacht haben!
Download: Punkteschema,
Ergebnisliste
Klausur / Nebentermin
Termin: 09.10.2006, 10:00-12:00
Stoffumfang: Vorlesungsstoff mit Ausnahme von Kapitel 7
Es herrschte Anmeldepflicht; man war nicht durch den ersten Antritt automatisch angemeldet! Die Einteilung in die verschiedenen Hörsäle erfolgte nach den Matrikelnummern.
Um bei der Einsichtnahme nicht alles vielfach erklären zu müssen:
Lösungen und Anmerkungen zur Klausur.
Wir möchten aber klarstellen, dass alle Angaben wie bei Lotto im Fernsehen ohne Gewähr sind ;-)
Klausurergebnisse:
Von den 229 Teilnehmern haben leider nur 69 bestanden (30,1 Prozent).
Gratulation an alle die die Klausur positiv bestanden haben; auch dieses Mal gab es zwei Studenten,
die mit 58,5 und 56,5 Punkten herausragende Leistungen geboten haben.
Download: Punkteschema,
vorläufige Ergebnisliste
Reguläre Einsichtnahme: Die Einsichtnahme findet am Freitag, 10. November,
von 10:00-12:00 in OH14, Seminarraum 2.02 statt.
Einsichtnahme für Zum-Dritten-Mal-Negativ: Für diejenigen, die die Klausur zum dritten Mal
nicht bestanden haben (und nur für diese!) findet eine vorgezogene Einsichtnahme am Freitag,
27. Oktober, von 10:00-11:00 in OH14, Seminarraum 2.02 statt. Abhängig von eurer DPO steht euch eine
mündliche Ergänzungsprüfung zu (zB bei Informatik, Physik,...). Details dazu werden ebenfalls
beim Einsichtnahmetermin besprochen.
Mündliche Ergänzungsprüfungen:
Anbei die Termine, aufgeschlüsselt nach Studiengang.
Informatikstudenten werden einen Brief mit dem genauen Termin erhalten.
Die betroffenen Physikstudenten mögen sich bitte, sofern sie es noch nicht getan haben, bei mir
(markus.chimani (at) cs.uni-dortmund.de) melden!
Wenn jemand seinen genauen Termin/Uhrzeit schon jetzt wissen möchte, genügt eine Mail an mich
(von eurem Uni-Account aus!). Angewandte Informatik: Mo. 18.12. Nachmittag, Do. 21.12. Nachmittag. Kerninformatik: Di. 12.12., Do. 14.12., Di. 19.12., Do. 19.12. jeweils Vormittag; Mo. 11.12. Nachmittag Physik: Di. 19.12. Nachmittag.
Diejenigen Studenten, die bei ihrem dritten Versuch angemeldet waren, nicht angetreten sind, und kein Attest
vorgewiesen haben, mögen sich wegen ihrer Termine bei mir melden.
Inhalt
In der Vorlesung DAP1 stand der Entwurf von Software, also Programmierung und Eigenschaften von
Programmen, im Vordergrund. Ein Softwareprodukt ist aber erst dann rundum gut, wenn es
effizient arbeitet. Daher behandeln wir in der Vorlesung DAP2 Datenstrukturen und
Entwurfsmethoden für effiziente Algorithmen.
Naive Lösungen algorithmischer Probleme können praktisch nutzlos sein, da die benötigten
Ressourcen an Rechenzeit und/oder Speicherplatz nicht zur Verfügung stehen. Mit Hilfe des
Einsatzes geeigneter Datenstrukturen und algorithmischer Methoden lassen sich viele
algorithmische Probleme effizienter lösen. Diese Effizienz kann sich im praktischen Gebrauch
erweisen und zuvor mit Experimenten belegt werden; besser ist jedoch ein Produkt mit
Gütegarantie. Dies bedeutet den formalen Beweis, dass die Datenstruktur oder der Algorithmus
das Gewünschte leistet, und die Abschätzung der benötigten Ressourcen. Daher
gehören zu dieser
Vorlesung stets auch Korrektheitsbeweise und Analysen.
Wie entwirft man nun für ein gegebenes Problem einen effizienten Algorithmus? Zunächst
benötigen wir grundlegende Kenntnisse über das Gebiet, aus dem das Problem stammt. Dieses
Wissen kann in späteren Spezialvorlesungen erlernt werden, oder es wird direkt bei der
Bearbeitung des Problems erworben. In dieser grundlegenden Vorlesung werden wir nur solche
Probleme behandeln, für die derartige Spezialkenntnisse nicht erforderlich sind. Darüber hinaus
ist der Entwurf effizienter Algorithmen ein Handwerk, wobei Meisterleistungen nur mit viel
Erfahrung, dem richtigen Gefühl für das Problem und einer Portion Intuition, manchmal auch
Glück, erbracht werden. Ziel unserer Vorlesung muss es also sein, das notwendige Handwerkszeug
bereitzustellen und dieses praktisch zu erproben.
Die von uns behandelten Probleme sind so ausgewählt, dass es sich einerseits um wichtige und
interessante Probleme handelt und andererseits bei der Lösung dieser Probleme allgemeine
Prinzipien und Methoden erlernt werden können.
An den obigen Kapiteln werden von Zeit zur Zeit Veränderungen, insbesondere Ausbesserungen, vorgenommen. Daher sind
sie auf der Titelseite mit einer Versionsnummer versehen. Details kann man dem
CHANGELOG entnehmen.
Folien
Die Folien liegen als PDF vor, wahlweise mit einer Folie pro Seite (pdf-1) oder mit 6 Folien pro Seite (pdf-6).
Als weiterführende Literatur empfehlen wir eines der folgenden Bücher:
Robert Sedgewick: Algorithmen (2. Auflage,
Pearson Studium 2002)
Sehr anschauliches und gut zu lesendes Buch. Sowohl auf Deutsch als auch auf Englisch erhältlich.
Diese (aktuelle) Ausgabe beschreibt die Algorithmen - so wie wir es auch in der Vorlesung tun werden - mittels
Pseudocode, und umfasst den gesamten Stoffumfang.
Es existieren vom selben Autor auch die sehr ähnlichen Werke "Algorithmen für C++",
"Algorithmen für Java", etc. Doch Obacht! Die aktuellen Ausgaben dieser
programmierspracheninkludierenden Bücher sind in 2 Bände (Band 1 = Teil 1-4, Band 2 = Teil
5) geteilt; in der Vorlesung behandeln wir den Stoff aus beiden Bänden!
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms (2nd
Edition, MIT Press 2001)
Dieses Buch ist ausschliesslich auf Englisch verfügbar, stellt aber das wissenschaftliche
Standardwerk auf diesem Gebiet dar. Es erklärt den Inhalt sehr schön und ausführlich.
T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen (4. Auflage, Spektrum
Akademischer Verlag 2001)
Bietet ebenfalls einen sehr anschaulichen Einstieg in die Thematik.
Übung
Zur Vertiefung des Lerninhaltes bieten wir eine mit der Vorlesung synchronisierte
Übung zu DAPII an.
Home
ls11.cs.tu-dortmund.de>
