Uni Wien:Algorithmen und Datenstrukturen 1 VU (Wanek)

Daten

Vortragende	Helmut Wanek, Sonja Biedermann, Martin Polaschek, Ralph Vigne• bis 2023S auch Erich Schikuta
ECTS	6,00 / 4,00
Aufgezeichnet	Nein
Sprache	Deutsch
Links	ufind:051024

Zuordnungen

262	Modul Informatik A
Bachelor Lehramt Informatik
Bachelor Wirtschaftsinformatik	Modul Informatik (Pflichtfach)
Bachelor Informatik	Modul Informatik (Pflichtfach)

Inhalt

Diese Lehrveranstaltung führt in die Grundzüge von Algorithmen und Datenstrukturen ein und teilt sich in 6 Hauptbereiche auf:

1. Algorithmen: Paradigmen von Algorithmen und dessen Analysemethoden
   1. Häufige Designmuster, die beim Design von Algorithmen zur Anwendung kommen: Greedy, Divide-and-conquer und dynamische Programmierung
   2. Arten wie Algorithmen bewertet und analysiert werden können: Korrektheit durch Verifikation und Termination, Big-O/Ω/Θ-Notation durch verschiedene Methoden (Substitution, Iterationsteilung, Master theorem)
   3. Verschiedene Komplexitäten eines Algorithmus: Zeitkomplexität, Raumkomplexität, Strukturelle Komplexität, ...
2. Datenstrukturen: Allgemeiner Überblick über die wichtigsten Datenstrukturen: Vektoren, Listen und Bäume
3. Vektoren: Aufbau von auf Vektoren basierten Datenstrukturen und Algorithmen, die häufig auf diese angewendet werden
   1. Funktionsweise von der Dictionary-Datenstruktur und Hashing-Verfahren: Separate Chaining, Double Hashing, Linear Probing, Linear Hashing, Extendible Hashing, Bounded Index Size Extendible Hashing (BISEH)
   2. Vorstellung einiger Sortieralgorithmen und ihre Eigenschaften: Selection Sort, Bubble Sort, Quick sort, Mergesort, Counting sort, Radixsort, Binary quicksort, LSD-Radixsort, Bucketsort
4. Listen: Arten von Listen und Vergleiche zwischen deren Anwendungen
   1. Vorstellung von verschiedenen Arten von Listen: Stack, Queue, Linked List, Circular List, Double Linked List, Double Ended Lsit, Ordered List
5. Bäume: Funktionsweise von Bäumen, wichtige Begriffe und Eigenschaften von Bäumen und Algorithmen die auf diese angewendet werden
   1. Wichtige Begriffe: Wurzel, innere Knoten, Blätter, Länge, Höhe, Tiefe, Pfad, Weg
   2. Spezielle Baumformen: Binärer Suchbaum, AVL-Baum, 2-3-4-Baum, B+-Baum, Trie, Heap
   3. Algorithmen: Operationen auf verschiedene Baumformen wie Einfügen, Löschen und Suchen; weiterer Suchalgorithmus: Heapsort
6. Graphen:
   1. Wichtige Begriffe: Knoten, Kanten, ungerichteter Graph, gerichteter Graph, Kantenfolge, Weg, Kreis, Komponente, Knotengrad, (Minimaler) Spannbaum, Wald, Transitive Hülle
   2. Algorithmen: Topologisches Sortieren, Tiefensuche (Depth-first search), Breitensuche (Breadth-first search), Kruskal-Algorithmus, Prim-Algorithmus, Dijkstra-Algorithmus, Floyd-Warshall-Algorithmus

Die Algorithmen und Datenstrukturen werden dabei immer mit einer kleinen Einführung vorgestellt und erläutert. Daraufhin gibt es oft ein Beispiel, eine Metapher oder bei Algorithmen auch den entsprechenden Pseudocode oder C++-Code, um die Problemlösung sich prozedural vorstellen zu können.

Ablauf

Es gibt wöchentliche Vorlesungen, wo die Theorie vorgetragen wird. Zusätzlich muss man sich für eine Datenstruktur

Es gibt wöchentliche Vorlesungen in denen die oben genannten Inhalte vorgetragen werden. Zusätzlich zu dem theoretischen Teil muss innerhalb der ersten eineinhalb Monate eine Datenstruktur gewählt werden, die man auf der Plattform "CEWebS" auswählen muss. In den letzten Semestern (Stand: Sommersemester 2023) wurden folgende Datenstruktur zur Auswahl angeboten:

• Coalesced Hashing (30 Punkte)
• Separate Chaining (30 Punkte)
• Linear Hashing (50 Punkte)
• Extendible Hashing (50 Punkte)
• B+-Baum (60 Punkte)

Nach Abschluss des Entscheidungszeitraums muss ein Take-at-Home-Exam abgeschlossen werden, der bis zu 20 Punkte bringen kann. Der Test soll dazu anregen sich relativ früh mit der ausgewählten Datenstruktur zu beschäftigen. Dieser besteht aus mehreren Beispielen, wo vorgegebene Operationen auf der Datenstruktur angewendet werden soll. Im Laufe des restlichen Semesters gibt es zwei Meilensteine, wo bereits bestimmte Funktionalitäten implementiert werden müssen. Im ersten Meilenstein sind nur die grundlegende Datenstruktur mit unoptimierten Einfüge- und Suchoperationen zu implementieren. Im zweiten Meilenstein werden die restlichen Operationen (wie das Löschen), der Iterator und das richtige Destrukturieren der Datenstruktur implementiert. Hier ist es essentiell, dass beim Erstellen, Löschen und sonstigen Operationen der Speicher richtig alloziert und wieder freigegeben wird. Man bekommt für gute Performance und die rechtzeitige Abgabe Extra-Punkte von jeweils 10 Punkten.

Als Hilfe und Orientierung bei dem Projekt gibt es zwei Einheiten, wo jeweils der erste und zweite Meilenstein eines Beispielprojektes mit Kommentar vorprogrammiert wird. Diese Einheiten sollte man nicht verpassen, da dort viele gute Tipps und ein guter Leitfaden für das eigene Projekt gegeben werden. Es gibt auch Aufnahmen von früheren Implementierung zu anderen Datenstrukturen auf CEWebS.

Am Ende des Semesters - nach erfolgreicher Abgabe und Tests - muss die praktische Abschlussklausur abgeschlossen werden, wo in einer dreistündigen Einheit die Datenstruktur erweitert werden muss. Meist besteht diese Erweiterung an einer speziellen Zusatzmethode am Iterator. Erst nachdem diese erfolgreich abgeschlossen wurde kann auch die Theorieprüfung angetreten werden, wo die Inhalte aus der Vorlesung mit praktischen Beispielen abgefragt werden. Hierbei müssen meist bestimmte Algorithmen auf oder mit Datenstrukturen angewendet werden. Für die Projektabschlussklausur und der Theorieprüfung gibt es jeweils einen Haupttermin und zwei Nachtermine.

Benötigte/Empfehlenswerte Vorkenntnisse

Uni_Wien:Programmierung_1_VU_(Wanek) & Uni_Wien:Programmierung_2_VU_(Stertz) (hier nur das Vektor Projekt, also muss PR2 nicht vorher machen aber gleichzeitig ist ideal)

Vortrag

Die Vorlesung ist sehr interessant und gut gehalten. Es lohnt sich, sie anzuschauen, aber es ist nicht nötig, da man mit den Folien und Internetmateralien sich den Stoff oft gut bis besser aneignen kann. Es liegt ganz im eigenen Ermessen.

Übungen

Siehe der Beschreibung in Ablauf (ab zweitem Absatz).

Prüfung, Benotung

Die meisten Abgaben werden automatisch benotet: So wird die Funktionsweise der Datenstruktur mit automatischen Tests kontrolliert und bewertet. Man bekommt dadurch ein schnelles Feedback zur eigenen Implementierung, besonders mit den Performance-Tests beim zweiten Meilenstein. Auch bei der Projektabschlussklausur kommt das gleiche Schema zur Anwendung, wo man bei einem erfolgreichen Durchlauf der Tests ohne Fehler die Prüfung bestanden hat. Nachdem diese abgeschlossen wurde, wird der Code noch einem Plagiatscheck unterzogen und einer der Prüfer*innen schaut sich den Code an und bewertet händisch auf Performance, Struktur und richtige Implementierung. Hier kann es zu einem Punktabzug kommen.

Die Theorieprüfung besteht aus ein paar praktischen Beispielen auf welche gelernte Algorithmen angewendet werden sollen. Es scheint so als wären die Beispiele teilweise zufallsgeneriert und dass es nur ein relativ kleinen Pool an Aufgaben gibt aus dem ausgewählt wird. Bei der Benotung scheint es so als würde nicht extrem detailreich auf die Lösung geschaut, aber man sollte schon auf ein annähernd richtiges Ergebnis gekommen sein um mit Punkten rechnen zu können.

Dauer der Zeugnisausstellung

Das Zeugnis wird meistens kurz nach erfolgreicher Theorieprüfung ausgegeben.

Zeitaufwand

Je nach vorhandenen C++-Kenntnissen, algorithmischen Denkvermögen und dem ausgewählten Projekt liegt diese Lehrveranstaltung im oder außerhalb der 150 Stundenvorgabe.

Wenn man sich beim Programmieren noch nicht so gut auskennt, sollte man eher zu den Projekten mit weniger Punkten aber dafür leichterer Implementierung greifen (~15-50 Stunden). Die dynamischen Hashingverfahren sollten gewählt werden, wenn man schon gute Programmierkenntnisse hat und sich auch an ein etwas komplizierteres Problem trauen möchte (~40-80 Stunden). Der B+-Baum sollte nur gewählt werden, wenn man sich schon sehr gut beim Programmieren in C++ oder ähnlichen Sprachen fühlt und auch daran Spaß hat sehr lange an dem Projekt zu programmieren. Die Punkte beim B+-Baum sind es den Zeitaufwand nicht wert.

Für die Theorieprüfung kann man mit aktivem Zuhören und ungefähr ein paar Tagen bis einer Woche Lernen und Üben der Altprüfungen eine gute Note erlangen.

Unterlagen

noch offen

Tipps

• Projektimplementierung
  • Man sollte früh anfangen um am Ende des Semesters nicht in Stress zu kommen
  • Der B+-Baum sollte wirklich nur gewählt werden, wenn man sich mit C++ schon leicht tut und man wirklich Zeit und Lust hat Datenstrukturen genau kennenzulernen (die +10 Punkte bringen wenig bei der Notenbewertung)
  • Auch Linear Hashing und Extendible Hashing sollten eher bei guten C++-Kenntnissen bzw. gutem algorithmischen und strukturellen Kenntnissen gewählt werden, aber sie sind mit Aufwand sehr gut möglich
  • Es hilft sehr Fragen im Forum zu stellen und verschiedene Ressourcen im Internet darüber aufzusuchen (Videos, Papers, etc.)
  • Man sollte aber sehr aufpassen, dass man sich an die in den Folien vorgestellten Vorgehensweisen hält, da es sonst zu Punkteabzug kommen kann
• Projektabschlussklausur
  • Man sollte einen guten Überblick über die eigene Implementierung haben und sich ggf. Kommentare schreiben um geschriebenen Code leicht wieder verstehen zu können
  • Es stehen auf CEWebS sehr viele Altprüfungen zu Verfügung, wo man auch eine Handvoll lösen sollte, um ein gutes Gefühl dafür zu bekommen
• Theorieprüfung
  • Es stehen auf CEWebS sehr viele Altprüfungen zu Verfügung, wo man auch eine Handvoll lösen sollte, um ein gutes Gefühl dafür zu bekommen
  • Die Beispiele beschränken sich größtenteils auf bestimmte Themen, die man sich aus den Altprüfungen herausholen sollte

• Wenn man Fragen hat, bekommen man im LV-Forum sehr schnelle und gute Hilfe

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Diese Seite hat noch keine Anhänge, du kannst aber neue hinzufügen.