Please disable Adblockers and enable JavaScript for domain CEWebS.cs.univie.ac.at! We have NO ADS, but they may interfere with some of our course material.
Ablauf
Die VU Algorithmen und Datenstrukturen 1 ist Bestandteil des Pflichtmoduls ADS Algorithmen und Datenstrukturen der Bachelorstudien Informatik und Wirtschaftsinformatik (Version 2016). Im Bachelorlehramtsstudium UF Informatik wird die VU Algorithmen und Datenstrukturen 1 anstelle der VO+UE Algorithmen und Datenstrukturen absolviert.
Die TeilnehmerInnen sollen die grundlegenden Algorithmen und Datenstrukturen kennenlernen und darüber hinaus in die Lage versetzt werden, die Komplexität und Qualität von Algorithmen und deren Implementierung zu bewerten.
Der Vorlesungsteil führt die grundlegenden Algorithmen und Datenstrukturen vor. Der vorgetragene Stoff bildet die Grundlage für die in den Übungen praktisch auszuarbeitenden Beispiele.
Im Wintersemester finden keine Vorlesungen statt. Es werden Aufzeichnungen aus dem Vorsemester zur Verfügung gestellt zu folgenden Themenschwerpunkten:
- Aufwandsabschätzungen
- Komplexitätsmaße
- Grundlegende Datenstrukturen
- Such- und Sortierverfahren
- Grundlegende Graph- und Optimierungsalgorithmen
Der Übungsteil wird in Form eines Projekts durchgeführt. Ziel des Projekts ist die Implementierung einer der in der Vorlesung behandelten Datenstrukturen. Die Studierenden können dabei aus einer Liste von Themen frei wählen. Die Themen sind unterschiedlich komplex, was später bei der Beurteilung berücksichtigt wird. Das Projekt wird im Anschluss an den Theoriekurs als Einzelarbeit durchgeführt.
Für die Übung werden grundlegende Kenntnisse der objektorientierten Programmierung (im speziellen in C++) vorausgesetzt (i.e. die Inhalte der Lehrveranstaltung «Einführung in die Programmierung 1»).
Leistungsbeurteilung
Über den Vorlesungsteil wird eine schriftliche Klausurarbeit abgelegt. Die Klausurtermine werden auf dieser Webseite bekanntgegeben. Alte Prüfungsangaben sind online verfügbar. Insgesamt können in dieser Klausur maximal 100 Punkte erreicht werden.
Für den Übungsteil werden Punkte für die Arbeit im Projekt wie folgt vergeben:
- 0-20 Punkte für den schriftlichen Test
- 10 Punkte für den fristgerechten Abschluss der ersten Projektphase
- 10 Punkte für den fristgerechten Abschluss der zweiten Projektphase
- 0-xx Punkte für das Projekt (Maximalanzahl der Punkte abhängig vom gewählten Projekt zwischen 30 und 60, siehe Spezifikation). Das Projekt wird mit einer Klausur abgeschlossen, in deren Rahmen die eigene Implementierung zu erweitern ist.
- 0-10 Punkte für die Qualität der Implementierung im Vergleich zu einer Referenzimplementierung (bezüglich Performance und Speicherplatzbedarf)
Projektpunkte und Qualitätspunkte
Zu jedem Thema werden die Leistungsdaten einer Referenzimplementierung zur Verfügung gestellt. Die Referenzimplementierung setzt keine Tricks oder Optimierungen ein und entspricht den Vorgaben in den Unterlagen. Die Leistungsdaten (Laufzeit, Speicherplatzbedarf) der Referenzimplementierung sollten daher in der Regel problemlos erreicht werden können.
Wenn die abgegebene Implementierung nicht den Vorgaben entspricht oder die Datenstrukturen bzw. Algorithmen nicht spezifikationskonform sind, dann werden Projektpunkte abgezogen. Bei schwerwiegend falschen Implementierungen kann dies eine positive Note verhindern. In einem solchen Fall muss auf jeden Fall nachgebessert werden (mit Projektpunkteabzug). Auch wenn die Leistungsdaten klar schlechter sind als jene der Referenzimplementierung weist dies auf eine falsche Implementierung hin und es werden Projektpunkte abgezogen. "Klar schlechter" bedeutet in der Ordnung schlechter oder um einen großen Faktor schlechter.
Die projektbezogenen Punkte (1. und 2. Projektphase, Projekt, Qualität) können nur vergeben werden, wenn das Projekt im Rahmen der Abschlussklausur erfolgreich abgeschlossen wurde.
Wenn die Leistungsdaten der Implementierung klar besser sind als jene der Referenzimplementierung, dann werden dafür Qualitätspunkte vergeben. Die Leistungsdaten werden dabei immer im Gesamten betrachtet. Ein Leistungsvorteil in einem Aspekt darf dabei nicht durch einen Leistungsnachteil in einem anderen Aspekt "erkauft" werden. Auch hier geht es nicht um minimale Abweichungen bei der Laufzeit (dafür ist die Messmethodik zu ungenau) oder beim Speicherplatzbedarf, sondern um deutliche Unterschiede.
Positive Beurteilung
Voraussetzung für eine positive Beurteilung ist jedenfalls:
- Die vorgegebenen Definitionen und Richtlinien (Klassendefinition, Dateistruktur, etc) werden eingehalten
- Die Implementation ist in der Laborumgebung lauffähig
- Die Implementation wird vom offiziellen Testscript ("Unit-Test") positiv evaluiert und absolviert den Performancetest ohne Fehler
- Die Datenstruktur ist spezifikationskonform implementiert. Dies kann vom Testscript nicht überprüft werden und wird daher im Zuge der Beurteilung am Ende der Lehrveranstaltung überprüft. Es gelten die Vorgaben in den Vorlesungsfolien. Bei Abweichungen bitte vorher Rücksprache mit der LV-Leitung halten (im Forum).
- Sowohl für den Vorlesungsteil, als auch für den Übungsteil werden jeweils mindestens 45 Punkte erreicht.
Notenskala
Punkte |
Note |
---|---|
>= 175 |
sehr gut (1) |
>= 150 |
gut (2) |
>= 125 |
befriedigend (3) |
>= 100 |
genügend (4) |
< 100 |
nicht genügend (5) |
Letzte Änderung: 03.10.2021, 10:24 | 653 Worte