Algorithmen und Datenstrukturen 2 VU 4.0

Überblick

Kennzahl: 186.113 (nur Sommersemester).
Pflichtfach für Studierende des Schwerpunkts "Software Engineering" im Bakkalaureatsstudium "Software and Information Engineering".
Empfohlen für das vierte Semester.
Fortsetzung von Algorithmen und Datenstrukturen 1 VO 3.0 und Algorithmen und Datenstrukturen 1 UE 2.0.

Aktuelles

Die Nachtragsprüfung findet am Mo, 04.10.2004 um 16:00 Uhr im AudiMax statt. Eine Anmeldung zur Prüfung ist zwingend erforderlich! (Zur Prüfungsanmeldung)
Wir haben via Stimmungszettel Feedback bzgl. der Prüfung erhalten. Darin wurde die Prüfung vom 23.06.04 als zu schwer beschrieben. Wir nehmen natürlich Ihr Feedback ernst. Bei der Erstellung einer Prüfung versuchen wir immer den Schwierigkeitsgrad so zu wählen, dass das Ergebnis die Mitarbeit und das Verständnis des Stoffes korrekt widerspiegelt. Das ist eine schwierige Aufgabe, und es lässt sich nicht vermeiden, dass der Schwierigkeitsgrad von Prüfung zu Prüfung ein wenig variiert. Es gab auch einige organisatorische Probleme bei der Prüfung und das hat sicher auch zu mehr Stress für die Prüfungsteilnehmer geführt. Das tut uns leid. Wir werden erst nach der Korrektur der Prüfung (wahrscheinlich Ende Juli) in der Lage sein, die Situation korrekt einzuschätzen. Wir werden selbstverständlich versuchen, etwaige Probleme, die wir bei der Korrektur festgestellt haben, bei der zweiten Prüfung im Oktober zu berücksichtigen.
Es gibt neuen Sourcecode für den resultChecker. Dieser sollte jetzt eigentlich mit beliebig grossen Lösungen fertig werden.
Die Deadline für den Contest (Freestyle Wettbewerb) ist der 15. Juni 12:00
Es gibt ein paar neue Details zur Abgabe
Programmieraufgabe: Der Code des resultChecker ist online.
Programmieraufgabe: Die Datei "karawane2.dat" war bis dato nicht in dem Format, das der resultChecker versteht. Das ist jetzt geändert. Die Leerzeichen hinter den eckigen Klammern sind wichtig. Jetzt ist auch das erste Wettbewerbsproblem online.
Das vierte Übungsblatt ist online.
Hinweis zum 3. Übungsblatt, Aufgabe 4: Hier sollen Sie herausfinden, welche Kombination von Mischungen (Blends) den höchsten Profit ergibt.
Hinweis zum 3. Übungsblatt, Aufgabe 6: Hier reicht es aus, wenn Sie das duale lineare Programm nur angeben.

Termine

Vorbesprechung: Mittwoch, den 3. März 2004, 15:00 Uhr, EI 9 (Hlawka HS)
Vorlesung: Mittwochs, 15:15-16:45 Uhr, EI 9 (Hlawka HS)
Anmeldung: von Mittwoch, den 3. März 2004, 17:00 Uhr, bis einschließlich Donnerstag, den 11. März 2004, auf der Anmeldeseite. Eine Anmeldung innerhalb dieses Zeitraums ist für die Teilnahme an dieser Lehrveranstaltung zwingend erforderlich; nachträgliche Anmeldungen können nicht akzeptiert werden.

Weitere Termine:


Di	23.03.		1. Übungsstunde
Di	27.04.		2. Übungsstunde
Di	18.05.		3. Übungsstunde
Di	15.06.		4. Übungsstunde
Mo	21.06.	bis Fr 25.06.	Abgabe Programmieraufgabe
Mi	23.06.		Prüfung
Mo	04.10.		Nachtragsprüfung
Mo	22.11.		mündliche Prüfung (Nebentermin; Voranmeldung an sek @ads.tuwien.ac.at zwingend erforderlich). Bitte beachten Sie, dass dieser Termin als Nebentermin zählt und somit ein neues Zeugnis ausgestellt wird.
Fr	28.01.		mündliche Prüfung (Nebentermin; Voranmeldung an sek @ads.tuwien.ac.at zwingend erforderlich). Bitte beachten Sie, dass dieser Termin als Nebentermin zählt und somit ein neues Zeugnis ausgestellt wird.

Inhalt

Suchen in Texten
Randomisierte Algorithmen
Algorithmen für große Datenmengen
Optimierungsalgorithmen
Flüsse in Netzwerken
Geometrische Algorithmen

Vorlesungen

Datum	Vortragender	Thema	Folien
3.3.04	Gunnar Klau	Organisatorisches, Suchen in Texten: Naives Verfahren, Knuth-Morris-Pratt	Organisatorisches, Folien
10.3.04	Gunnar Klau	Suchen in Texten: Boyer-Moore, Karp-Rabin	Folien
16.03.04	René Weiskircher	Randomisierte Algorithmen und Datenstrukturen	Folien
24.03.04	René Weiskircher	Algorithmen für große Datenmengen	Folien
31.03.04	René Weiskircher	Algorithmen für große Datenmengen, Cache optimierte Algorithmen, Lineare Programme	Folien
21.04.04	René Weiskircher	Lineare Programme, Polyederthoerie	Folien
28.04.04	René Weiskircher	Simplex	Folien
5.05.04	Gunnar Klau	Kombinatorische Optimierung	Folien
12.05.04	Gunnar Klau	Exakte Verfahren zur Lösung kombinatorischer Optimierungsprobleme	Folien
19.05.04	Gunnar Klau	Schnittebenenverfahren	Folien
26.05.04	Gunnar Klau	Metaheuristiken + Flüsse I	Folien
2.06.04	Gunnar Klau	Flüsse II	Folien
9.06.04	René Weiskircher	Geometrische Algorithmen I	Folien
16.06.04	René Weiskircher	Geometrische Algorithmen II	Folien

Fragen

Vorlesung

Übung

erster Ansprechpartner: ihr(e) Tutor(in)
Stud.Ass. Georg Kraml
Univ. Ass. Dr. Andreas Kerren

Modus

Die Übung findet im Rahmen von Kleingruppen statt, die sich vier Mal im Semester zu etwa 45 Minuten langen Übungsstunden treffen. Sie müssen sich bei der Anmeldung zur Übung auf eine bestimmte Übungsgruppe festlegen und können während des Semesters nur an den Treffen genau dieser Gruppe teilnehmen; eine Teilnahme an ‘fremden’ Übungsstunden ist ausnahmslos unzulässig. Die genauen Koordinaten der Übungsstunden:

Gruppe:	Tag:	Uhrzeit:	Hörsaal:
01	Dienstag	08:00 - 09:00	HS 14
02	Dienstag	09:00 - 10:00	HS 14
03	Dienstag	13:00 - 14:00	HS 20
04	Dienstag	14:00 - 15:00	HS 20
05	Dienstag	14:00 - 15:00	FH HS 2
06	Dienstag	15:00 - 16:00	FH HS 2
07	Dienstag	18:00 - 19:00	HS 14
08	Dienstag	19:00 - 20:00	HS 14
09	Dienstag	11:00 - 12:00	EI 4
10	Dienstag	12:00 - 13:00	EI 4
11	Dienstag	09:00 - 10:00	HS 11
12	Dienstag	10:00 - 11:00	HS 11

Rechtzeitig vor jeder Übungsstunde können Sie auf dieser Seite ein Übungsblatt mit zehn Übungsbeispielen herunterladen, die Sie zu Hause ausarbeiten sollen:
Zu Beginn der Übungsstunde kreuzen Sie in einer Liste an, welche der zehn aktuellen Übungsbeispiele Sie gelöst haben. Der Leiter Ihrer Übungsgruppe wählt aufgrund dieser Liste Teilnehmer aus, die ihre Lösungen dann an der Tafel präsentieren. Die Anzahl der von Ihnen angekreuzten Beispiele und Ihre Leistungen bei diesen Präsentationen fließen in Ihre Beurteilung ein.
Zusätzlich zu den Übungsstunden müssen Sie eine Programmieraufgabe sowie eine 90 Minuten lange schriftliche Prüfung absolvieren.
Die Prüfung findet am
Mittwoch, den 23. Juni, 16:00, im Audimax
statt. Stoff der Prüfung ist der gesamte bis dahin in Vorlesung und Übung durchgenommene Lehrinhalt. Schriftliche Unterlagen und elektronische Hilfsmittel sind nicht erlaubt. Vom Schwierigkeitsgrad und der Art der Fragestellung her sind Testbeispiele ähnlich den Übungsbeispielen; es lohnt sich also spätestens bei der Prüfung, wenn Sie die Übungsblätter eigenständig ausgearbeitet haben.
Es wird am Montag, den 4.10.2004, um 16:00 Uhr im Audimax einen zweiten (und letzten) schriftlichen Prüfungstermin für diese Veranstaltung geben. Die Punktzahl der letzten von Ihnen absolvierten Prüfung zählt für das Zeugnis.
Alte Prüfungsangaben zum übungsweisen Ausarbeiten:
- 26. 06. 2003

Beurteilung

Für Ihre Leistung in den Übungsstunden erhalten Sie zwischen 0 und 20 Punkte, je nachdem, wieviele Beispiele Sie angekreuzt und wie überzeugend und richtig Sie diese präsentiert haben. Für die Programmieraufgabe erhalten Sie ebenfalls zwischen 0 und 20 Punkte. Für die Prüfung erhalten Sie zwischen 0 und 50 Punkte.
Insgesamt können Sie also 90 Punkte erzielen. Um ein positives Zeugnis zu erhalten, müssen Sie
1. mehr als die Hälfte der Übungsbeispiele angekreuzt,
2. die Programmieraufgabe bewätigt,
3. mehr als 25 von 50 möglichen Prüfungspunkten und
4. mehr als 45 von 90 möglichen Gesamtpunkten
erzielt haben. Wenn Sie eine dieser vier Bedingungen nicht erfüllen, erhalten Sie normalerweise ein negatives Zeugnis. Sie erhalten allerdings ausnahmsweise kein negatives Zeugnis, wenn Sie weder mehr als die Hälfte der Übungsbeispiele angekreuzt noch die Programmieraufgabe ausgearbeitet noch an der Prüfung teilgenommen haben.
Vorsicht: Es muss nicht jedes Beispiel, das Sie ankreuzen, auch anerkannt werden: sollten Sie ‘spekulieren’, also Beispiele ankreuzen, für die Sie dann keine Lösung präsentieren können, werden Ihnen zumindest die Beispiele der betreffenden Übungsstunde aberkannt. Im Wiederholungsfall wird Ihnen der Gruppenleiter alle Beispiele aberkennen; damit wären Sie durchgefallen. Darüber hinaus können Ihre Beispiele nur gewertet werden, wenn Sie während der gesamten Übungsstunde persönlich anwesend waren; mit anderen Worten: zu spät kommen und nachträglich ankreuzen gilt nicht, ankreuzen und dann die Flucht ergreifen gilt auch nicht.

Unterlagen

Im Anschluss an die dritte Vorlesung (17.3.2004) sowie nach diesem Zeitpunkt auch im Sekretariat der Abteilung wird ein Skriptum verkauft. Das Skriptum kostet 7.50 Euro und umfasst etwa 140 Seiten.
Weiterführende Literatur:
1. T. H. Cormen, C. E. Leiserson und R. I. Rivest: Algorithms
2. C. H. Papadimitriou und K. Steiglitz: Combinatorial Optimization: Algorithsm and Complexity
3. T. Ottmann und P. Widmayer: Algorithmen und Datenstrukturen
4. R. Sedgewick: Algorithmen. Von diesem Buch gibt es auch Versionen, die zur Veranschaulichung mit konkreten Programmiersprachen arbeiten, nämlich Algorithmen in C, Algorithmen in C++ und Algorithmen in Java.

Algorithms and Data Structures Group | Inst. of Computer Graphics and Algorithms | TU Wien

If you have any suggestions, please contact webmaster @ads.tuwien.ac.at.
Last modification: 2004-11-29, 11:51