Algorithmen und Datenstrukturen 2 VU 4.0
LVA-Kennzahl:
186.113 (nur SS)
Aktuelles:
Die Ergebnisse der Vorlesungsprüfung vom 26.06.2003 finden Sie jetzt auf dem Web. Für diejenigen unter Ihnen, die die Prüfung nicht bestanden haben bzw. nicht teilnehmen konnten, gibt es einen Ersatztermin am 10. Oktober. Beachten Sie dazu auch unsere Webseite mit den Prüfungsterminen!
Für die Aufgaben 7-10 auf dem 4ten Übungsblatt wird es volle Punktzahl geben, unabhängig von der Bearbeitung
Die Infos für den Free-Style-Kreuzungsminimierungswettbewerb sind auf der Seite des KreuzungsMinimierungsprojektes abrufbar. Die Informationen zur Anmeldung für die Abgabe der Programmieraufgabe sind auf der Seite des KreuzungsMinimierungsprojektes abrufbar. Die Abgabegraphen für die Kreuzungsminimierung sind abrufbar.
Allgemeines:
Die VU ist die Fortsetzung der Algorithmen und Datenstrukturen 1 VO 3.0 bzw. der dazugehörigen Übung. Sie beschäftigt sich mit dem Suchen in Texten, Randomisierte Algorithmen, Datenstrukturen und Algorithmen für grosse Datenmengen (Externspeicher- sowie Cache-Oblivious), Optimierung (Lineare, Ganzzahlige und Kombinatorische Optimierung), Graphenalgorithmen (Flüsse in Netzwerken), und geometrischen Algorithmen.
Die VU besteht aus einem Vorlesungs- und einem Übungsteil, letzterer wiederum gliedert sich in Übungsgruppen und in eine Programmieraufgabe.
Vorbesprechung:
Mittwoch, 5. März 2003, 15:00, EI 9 Hlawka HS.
Anmeldung:
Mittwoch, 5. März bis Donnerstag, 13. März 2003, im Web.
Laufende Unterlagen:
Folien zur Vorlesung am 26.03.2003, Externspeicheralgorithmen 1 (.ppt-Format bzw. .html-Format).
Folien zur Vorlesung am 02.04.2003, Externspeicheralgorithmen 2 (.ppt-Format bzw. .html-Format).
Folien zur Vorlesung von Robert E. Bixby am 09.04.2003, Linear and Integer Programming (.ppt-Format bzw. .html-Format).
Folien zur Vorlesung am 30.04.2003, Optimierungsalgorithmen 1 (.ppt-Format bzw. .html-Format).
Folien zur Vorlesung am 06.05.2003, Optimierungsalgorithmen 2: -- Grundlagen der Polyedertheorie: (.pdf-Format), -- Lineare Programmierung: .ppt-Format bzw. .html-Format).
Folien zur Vorlesung am 14.05.2003, Optimierungsalgorithmen 3: .ppt-Format bzw. .html-Format).
Termine:
Die Vorlesung findet jeden Mittwoch um 15:00 c.t. im EI 9 Hlawka HS statt. Die erste Vorlesung wird gemeinsam mit der Vorbesprechung am Mittwoch, den 5. März gehalten, die letzte Vorlesung am Mittwoch, den 18. Juni. Weitere Termine:
| Do 13. 03. | Anmeldeschluss |
| Di 25. 03. | 1. Übungsstunde |
| Di 29. 04. | 2. Übungsstunde |
| Di 20. 05. | 3. Übungsstunde |
| Di 17. 06. | 4. Übungsstunde |
| Do 26. 06. | Prüfung |
Übungsstunden:
Der Übungsteil findet im Rahmen von Kleingruppen statt, die sich vier Mal im Semester zu etwa 60 Minuten langen Übungsstunden treffen. Etwa zwei bis drei Wochen vor jeder Übungsstunde erhalten Sie ein Übungsblatt mit zehn Übungsbeispielen, die Sie zu Hause ausarbeiten sollen. Das erste Übungsblatt erhalten Sie am Mittwoch, den 5. März nach der Vorlesung; das zweite bis vierte Übungsblatt erhalten Sie in den Übungsstunden. Alternativ können Sie die Übungsblätter auch von dieser Webseite herunterladen:
Für die Aufgaben 7-10 auf dem 4ten Übungsblatt gibt es unabhängig von der Bearbeitung volle Punktzahl
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. 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. Wo und wann genau sich Ihre Gruppe trifft, entnehmen Sie bitte der folgenden Liste:
Programmieraufgabe:
Prüfung:
Um ein positives Zeugnis zu erhalten, müssen Sie eine ausserdem eine schriftliche Prüfung bestehen; der Prüfungstermin für dieses Semester ist am Donnerstag, den 26. Juni. Stoff der Prüfung ist der gesamte während des Semesters durchgenommene Lehrinhalt; die gestellten Aufgaben umfassen sowohl theoretische Fragen als auch praktische Beispiele. Hier einige alte Prüfungsangaben zum übungsweisen Ausarbeiten -- wobei allerdings etwas Vorsicht geboten ist, da sich der Lehrinhalt der LVA und damit der Prüfungsstoff mit diesem Semester signifikant ändern:
| 19. Jänner 2001 | PostScript | |
| 9. März 2001 | PostScript | |
| 18. Mai 2001 | PostScript | |
| 19. Juni 2001 | PostScript | |
| 14. Dezember 2001 | PostScript | |
| 1. Februar 2002 | PostScript | |
| 15. März 2002 | PostScript | |
| 17. Mai 2002 | PostScript | |
| 17. Juni 2002 | PostScript | |
| 11. Oktober 2002 | PostScript | |
| 6. Dezember 2002 | PostScript | |
| 26. Juni 2003 | PostScript |
Bei den Prüfungen sind keine Computer oder Taschenrechner sowie keine Unterlagen (Bücher, Skripten, Mitschriften, Ausarbeitungen etc.) erlaubt, Mobiltelefone sind abzuschalten.
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 das Programmierbeispiel erhalten Sie ebenfalls maximal 20 Punkte; bei der Prüfung können Sie jeweils maximal 50 Punkte erhalten. Sie können also insgesamt 90 Punkte erzielen. Um die VU zu bestehen, müssen Sie
- mehr als 25 Punkte auf Ihre Prüfung erhalten haben,
- das Programmierbeispiel erfolgreich gelöst, sowie
- mehr als die Hälfte der Übungsbeispiele angekreuzt 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.
Wenn Sie eine dieser drei Bedingungen nicht erfüllen, erhalten Sie automatisch eine negative Note. Wenn Sie die drei Bedingungen erfüllen, ergibt sich Ihre Note anhand des folgenden Punkteschlüssels:
| [79, 90] | sehr gut |
| [68, 79[ | gut |
| [57, 68[ | befriedigend |
| [46, 57[ | genügend |
| [0, 45[ | nicht genügend |
Wer nicht mehr als die Hälfte der Übungsbeispiele angekreuzt, kein Programmierbeispiel abgegeben und auch nicht an der Prüfung teilgenommen hat, erhält kein Zeugnis.
Unterlagen:
Ein Skriptum (ca. 130 Seiten) wird im Anschluss an eine der kommenden Vorlesungen (voraussichtlich 21. Mai) verkauft; ab diesem Zeitpunkt ist es alternativ auch im Sekretariat des Instituts (Favoritenstraße 9-11, Stiege 2, 5. Stock), erhältlich. Das Skriptum würde normalerweise EUR 7,00 kosten. Weil Sie aber so lange darauf warten mussten, bieten wir es Ihnen diesmal (bis Ende SS03) zum Sonderpreis von 4 EUR an, der unsere Kosten nicht deckt.
Weiterführende Literatur:
- T. H. Corm en, C. E. Leiserson und R. I. Rivest: Algorithms
- C. H. Papadimitriou und K. Steiglitz: Combinatorial Optimization: Algorithms and Complexity
- T. Ottmann und P. Widmayer: Algorithmen und Datenstrukturen
- R. Sedgewick, Algorithmen
Von Sedgewicks Algorithmen gibt es auch Versionen, die zur Veranschaulichung mit konkreten Programmiersprachen arbeiten: Algorithmen in C, Algorithmen in C++ und Algorithmen in Java.
Noch Fragen?
Falls Sie noch Fragen zum Ablauf oder zum Stoff der Übung haben, wenden Sie sich persönlich oder per Mail an den Leiter Ihrer Übungsgruppe.
Wenn (und nur wenn) Ihnen Ihr Gruppenleiter nicht weiter helfen kann, wenden Sie sich telefonisch, persönlich oder per Mail an Georg Kraml oder an eine/n der anderen Verantwortlichen. Falls Sie uns im Institut besuchen wollen, kommen Sie bitte ausschließlich während unserer Sprechzeiten (s. u.). Wir helfen Ihnen gerne, können Ihnen aber nicht zu jeder beliebigen Tages- und Nachtzeit für ein persönliches Gespräch zur Verfügung stehen -- unsere Sprechstunden sind nur ein kleiner Teil unserer Verpflichtungen, bitte haben Sie dafür Verständnis.
Verantwortliche:
Stud. Ass.
Georg Kraml
Univ. Prof. Dr. Petra
Mutzel
Univ. Ass. Dr. Andreas
Kerren
Univ. Ass. Dr. Martin
Schönhacker
Univ. Ass. Dr.
René Weiskircher
Algorithms and Data Structures Group | Institute of Computer Graphics and Algorithms | TU Wien