Hauptinhalt
Datenstrukturen, Algorithmen und Programmierung
Sommersemester 2010
[
Aktuelles][
Inhalt] [
Begleitmaterial]
[
Übungen] [
Studienleistung]
[
Lernraumbetreuung] [
Programmierpraktikum]
[
Klausur][
Forum]
Die Einsicht findet am 21.10.10 von 12-14 Uhr in GB 4, Raum 113 statt.
Die Klausurergebnisse sind da! Und zwar gibt es die Ergebnisse als Aushang bei uns am Lehrstuhl im Schaukasten (OH14, 3. Stock), direkt am Eingang).
Die 2. Klausur findet am 21.09.2010 im Audimax statt. Bitte seid um 12.30 da, um 12.45 beginnt die Klausur.
Die Anmeldefrist für die Studiengänge Diplom-/Bachelor Informatik, Bachelor Mathe, IKT, ET/IT und Lehramt endet am
13.09.2010.
Die Einsicht findet am 07.09.2010 von 14-17 Uhr in Raum 304 in der OH 14 (3. Stock) statt. Um den Andrang etwas zu verteilen, beachtet bitte die folgende Einteilung:
14-15 Uhr: Nachnamen mit A-H
15-16 Uhr: Nachnamen mit J-R
16-17 Uhr: Nachnamen mit S-Z
Die Klausurergebnisse sind da! Und zwar gibt es die Ergebnisse als Aushang bei uns am Lehrstuhl im Schaukasten (OH14, 3. Stock), direkt am Eingang).
Am 10.08.2010 findet die erste Klausur statt. Wir schreiben in zwei Hörsälen mit der folgenden Aufteilung:
Audimax: Studierende mit Nachnamen, die mit
A-R beginnen
HG2, HS 1: Studierende mit Nachnamen, die mit
S-Z beginnen
Bitte seid um
17 Uhr in Eurem Hörsaal, um 17.15 Uhr beginnt die Klausur.
Lehramtsstudierende, die den Praktikumsschein früher erworben haben als laut ihrem Studienplan vorgesehen, benötigen einen gedruckten Schein, da die Information in BOSS vermutlich nicht dauerhaft gespeichert wird. Bitte meldet Euch bei uns, wenn ihr zu dieser Gruppe gehört, dann stellen wir Euch einen Schein aus.
Neben den Vorlesungsfolien stehen jetzt teilweise genauere Quellenangaben.
Beim
Begleitmaterial gibt es jetzt eine Probeklausur. Diese soll dazu dienen, dass ihr Euch ein ungefähres Bild davon machen könnt, wie die Klausur aufgebaut sein wird. Bitte beachtet, dass die Probeklausur nichts darüber aussagt, welche Themen oder speziellen Aufgaben in der Klausur vorkommen (im Gegensatz zum Beispieltest)! In der Klausur werden auch keine bereits bekannten Aufgaben gestellt. Die Probeklausur dient nur dazu, ein Bild vom Aufbau und der Schwierigkeit zu geben. Sie ist ein bißchen anspruchsvoller als eine tatsächliche Klausur.
Die Lernraumbetreuung am Dienstag beginnt heute und in den verbleibenden Wochen um 15.30 Uhr statt um 15 Uhr.
In den Folien zur Vorlesung 11 gab es einen kleinen Fehler: Das Feld für die DP-Tabelle heißt nun an allen Stellen korrekt "Opt" und nicht "A".
In den Folien zur Vorlesung 14 hatte sich auf Folie 123 (Vollversion) ein kleiner Fehler eingeschlichen: bei gleichem Schlüssel wird in den linken Unterbaum eingefügt, nicht in den rechten. Demnach
sind alle Knoten im rechten Unterbaum eines Knotens x größer als key[x] und nicht größer gleich.
Die Deadline für das Bearbeiten der Heimübungsblätter wird dauerhaft auf Montags, 12 Uhr, verlegt.
Es ist neue Versionen von Vorlesung 7 und 8 online, die eine getippte Version der Tafelanschriebe aus der letzten Woche enthalten.
Damit ein Algorithmus eine Aufgabenstellung sinnvoll löst, muss er zum einen korrekt 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. Grundlegende Entwurfsmethoden zur Erstellung von Algorithmen kennen sind dabei ein wichtiges Werkzeug.
Daher ist das Ziel der Vorlesung Datenstrukturen, Algorithmen und Programmierung II 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.
Das erlernte Wissen soll im Rahmen des zugehörigen Praktikums umgesetzt und vertieft werden.
Die in der Vorlesung untersuchten Probleme sind grundlegend für den Algorithmenentwurf und dienen insbesondere auch dazu, Entwurfs- und Analysemethoden zu illustrieren.
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
13.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 1.1--1.2, 2.1; [KT] Kap. 2.1--2.2; [OW] Kap. 1.1, 2.1.2
15.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion)
20.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 3; [KT] Kap. 2.1--2.2; [OW] Kap. 1.1
22.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 2.3, Kap. 4.1--4.2; [KT] Kap. 5.1; [OW] Kap. 2.4, 3.2.2
27.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 28.2; [KT] Kap. 5.5; [OW] Kap. 1.2
29.04.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 4.3--4.4, 28.2
04.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 33.4; [KT] Kap. 5.4; [OW] Kap. 7.7--7.7.1
06.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 33.3
11.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 15.3
20.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 15.3--15.4
25.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 16.2; [KT] Kap. 6.4
27.05.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 16.2; [KT] Kap. 4.1
01.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [KT] Kap. 4.1--4.2; [OW] Kap. 1.5
08.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 10.2, 12; [KT] Kap. 2.3; [OW] Kap. 1.5, 5.1
10.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [OW] Kap. 5.2.1; [Sei] Kap. 4.3
15.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 11.1--11.3; [KT] Kap. 13.6; [OW] Kap. 4.1--4.2
22.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 6; [KT] Kap. 2.5; [OW] Kap. 2.3
24.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 22.2; [KT] Kap. 3.1--3.3
29.06.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 24.3; [KT] Kap. 4.4; [OW] Kap. 8.5.1
01.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 24--24.1; [KT] Kap. 6.10; [OW] Kap. 8.5.2
06.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 25--25.2; [OW] Kap. 8.5.3
08.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 22.3--22.4; [KT] Kap. 3.2--3.3
13.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [CLRS] Kap. 23--23.2; [KT] Kap. 4.5--4.6; [OW] Kap. 8.6
15.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion)
20.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion)
22.07.2010:
Powerpoint PDF (ausführlich)
PDF (Druckversion) [KT] Kap. 4.7
Die Übungen beginnen in der zweiten Vorlesungswoche und finden wöchentlich statt. Die erste Übung ist eine Präsenzübung, d.h. Aufgaben werden von den Studierenden selbstständig unter Anleitung gelöst. In der ersten Woche wird außerdem ein Übungszettel herausgegeben, der in Heimarbeit bearbeitet und in der dritten Übung besprochen wird. Anschließend wechseln sich Präsenz- und Heimübungszettel ab.
Die Anmeldung zu den Übungen erfolgt über AsSESS und ist ab sofort freigeschaltet. Die Anmeldung endet am Donnerstag, den 15. April um 18 Uhr.
Zur Anmeldung ist eine eine Unimail-Adresse oder IRB-Adresse erforderlich, d.h. eine Emailadresse, die auf @udo.edu, @(cs.)uni-dortmund.de oder @(cs.)tu-dortmund.de endet. Wer noch keinen Unimail-Account besitzt, muss sich vor der Anmeldung zu den Übungen darum kümmern.
Veranstalter der Übungen
Termine der Übungen
| Montag |
Dienstag |
Mittwoch |
Donnerstag |
| -- |
10-12 (2 Gruppen) |
-- |
-- |
| -- |
-- |
12-14 (2 Gruppen) |
12-14 (2 Gruppen) |
| 14-16 (2 Gruppen) |
14-16 (1 Gruppe) |
14-16 (2 Gruppen) |
-- |
| 16-18 (2 Gruppen) |
16-18 (1 Gruppe) |
16-18 (2 Gruppen) |
16-18 (3 Gruppen) |
Für Studierende in den Informatik-Bachelor-Studiengängen ist die Erbringung von Studienleistungen verpflichtender Bestandteil des Moduls DAP2.
Dabei ist das erfolgreiche Absolvieren der Studienleistung für die Übungen verpflichtende Voraussetzung für die Teilnahme an der Klausur.
[Wenn Sie in einem anderen Studiengang studieren, überprüfen Sie bitte anhand ihres Modulhandbuchs, welche Studienleistungen für Sie verpflichend sind!]
Die Studienleistung für die DAP2-Übungen wird erbracht durch
- regelmäßige und aktive Teilnahme an den Übungen (maximal zweimal unentschuldigtes Fehlen),
- mindestens 50 % der Punkte, die in den Heimarbeitsübungsblättern erreichbar sind, und
- Erreichen von 50 % in mindestens einem der beiden Übungstests.
Die Heimübungen dürfen in Gruppen von maximal drei Studenten abgegeben werden.
Die Studienleistung für das Praktikum ist verpflichtend für das Modul DAP2 (nicht zwingend für die Klausur). Wie diese Studienleistung
erbracht wird, steht
hier.
Wir bieten begleitend eine Lernraumbetreuung an, in der Fragen zur Vorlesung und zu den Übungen gestellt werden können und nach Möglichkeit beantwortet werden. So besteht die Möglichkeit, Fragen zeitnah zu klären. Wir hoffen, dass dieses Angebot zahlreich genutzt wird, da der Lerneffekt viel größer ist, wenn man der Vorlesung stetig folgen kann. Das spart auch Zeit beim Lernen und Wiederholen des Vorlesungsstoffs!
Die Lernraumbetreuung findet an folgenden Terminen statt und startet in der zweiten Vorlesungswoche:
| Montag |
Dienstag |
Mittwoch |
Donnerstag |
| C-Fragestunde! 14.30-17.30 in OH14, U04 |
15.30-18.30 Uhr (OH14, Raum 340) |
13-16 Uhr (OH14, Raum 340) |
9-12 Uhr (GB IV, Raum 105) |
|
|
Am 9.6. abweichend von 14-17 Uhr |
Achtung! Hier stand vorher GB V |
Es wird zwei Klausuren mit einer Länge von jeweils 180 Minuten geben, wobei die erste voraussichtlich am 10.08.2010 im Zeitraum 17:00-21:00 Uhr und die zweite am 21.09.2010 im Zeitraum 12:30-16:30 Uhr stattfindet. Die späten Uhrzeiten können leider aufgrund knapper Raumresourcen nicht vermieden werden.
Zur Vorlesung, den Übungen und dem Praktikum gibt es auch ein Forum.
Informationen zum DAP2-Programmierpraktikum finden sich hier.
- [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 Adakemischer 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 27.07.2010 von L. Pradel
