Universität Wien

051024 VU Algorithmen und Datenstrukturen 1 (2019W)

6.00 ECTS (4.00 SWS), SPL 5 - Informatik und Wirtschaftsinformatik
Prüfungsimmanente Lehrveranstaltung
CEWebs

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 100 Teilnehmer*innen
Sprache: Deutsch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

Die Lehrveranstaltung findet außerhalb des regulären Rhythmus zusätzlich auch im WS 2019 statt.

Die Lehrveranstaltung richtet sich vor allem an jene Studierenden, die die entsprechende Veranstaltung im Sommersemester bereits belegt, aber nicht erfolgreich abgeschlossen haben. Wir gehen davon aus, dass die Stoffinhalte bereits bekannt sind. Studierende, denen diese Kenntnisse fehlen, müssen die Inhalte gegebenenfalls mit den zur Verfügung gestellten Lehrunterlagen aus dem Sommersemester selbstständig erarbeiten.

Es ist zulässig, Projekte, die im letzten Semester eigenständig erstellt wurden, weiter zu verwenden.

Anwesenheit und Unterschreiben der aufliegenden Liste in der Vorbesprechung am Fr 11.10.2019 verpflichtend.

  • Freitag 11.10. 11:30 - 13:00 Hörsaal 1, Währinger Straße 29 1.UG (Vorbesprechung)
  • Freitag 08.11. 11:30 - 13:00 Hörsaal 1, Währinger Straße 29 1.UG
  • Donnerstag 05.12. 15:00 - 16:30 PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
  • Donnerstag 05.12. 15:00 - 18:15 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Freitag 13.12. 16:45 - 20:00 Hörsaal 1, Währinger Straße 29 1.UG
    Seminarraum 5, Währinger Straße 29 1.UG
  • Donnerstag 23.01. 15:00 - 18:15 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Freitag 31.01. 09:45 - 13:00 Hörsaal 1, Währinger Straße 29 1.UG
  • Dienstag 25.02. 17:00 - 20:00 PC-Unterrichtsraum 2, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 3, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 4, Währinger Straße 29 1.OG
    PC-Unterrichtsraum 5, Währinger Straße 29 2.OG
    PC-Unterrichtsraum 6, Währinger Straße 29 2.OG
  • Mittwoch 26.02. 15:00 - 18:15 Hörsaal 1, Währinger Straße 29 1.UG

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Die Studierenden erlangen Kenntnisse über Aufwandsabschätzungen, Komplexitätsmaße, grundlegende Datenstrukturen, Such- und Sortierverfahren und grundlegende Graph- und Optimierungsalgorithmen. Sie werden dadurch befähigt Algorithmen und geeignete Datenstrukturen für gegebene Problemstellungen zu entwerfen oder auszuwählen und das Leistungsverhalten zu beurteilen.

In der Lehrveranstaltung im Wintersemester entfällt der Vorlesungsteil. Zur selbstständigen Erarbeitung des Stoffes stehen die Unterlagen und aufgezeichneten Streams aus dem vorangegangenen Sommersemester zur Verfügung.

Im Laufe des Semesters muss eine auszuwählende Datenstruktur implementiert werden.

Folgende Stoffinhalte sind neben den Fähigkeiten, die für die Programmierung der Datenstruktur notwendig sind, relevant:
0. Einführung (Programmstrukturen )
1. Algorithmen (Paradigmen, Analyse)
2. Datenstrukturen (Allgemeiner Überblick)
3. Listen (Lineare Speicherstrukturen, Stack, Queue)
4. Bäume (Suchstrukturen)
5. Vektoren (Sortieren, Hashing)
Diese Inhalte werden im Rahmen einer theoretischen Prüfung am Ende des Semesters geprüft.
6. Graphen (Optimierungsalgorithmen)

Art der Leistungskontrolle und erlaubte Hilfsmittel

Für die schriftliche Prüfung zu den theoretischen Inhalten am Ende des Semesters werden bis zu 100 Punkte vergeben. Zur Prüfung sind keine Hilfsmittel zugelassen.

Für den Praktikumsteil (Projekt) sind mehrere Teilleistungen zu erbringen. Im Laufe des Semesters ist ein schriftlicher Test zu absolvieren, sowie ein Projekt mit einer aus einer Liste möglicher Themen gewählten Aufgabenstellung zu realisieren. Für einzelne Teilleistungen werden Punkte vergeben. Die maximal erreichbaren Punkte sind - abhängig vom Aufwand/Schwierigkeitsgrad - je nach Thema unterschiedlich (bis zu 100). Das Projekt wird mit einer Klausurarbeit im Rechnerlabor abgeschlossen, in deren Rahmen die eigene Implementierung zu erweitern ist. Es sind keine Hilfsmittel erlaubt.

Beim schriftlichen Test im Praktikumsteil werden die grundlegenden Operationen (Einfügen/Löschen/Suchen) auf der für das Projekt ausgewählten Datenstruktur geprüft. Es sind keine Hilfsmittel erlaubt.

Mindestanforderungen und Beurteilungsmaßstab

Für den erfolgreichen Abschluss sind zumindest jeweils 45 Punkte bei der Vorlesungsprüfung und beim Praktikumsteil erforderlich. Die Note ergibt sich aus der erreichten Punkteanzahl wie folgt:

>=175 Punkte Sehr gut
<175 Punkte und >=150 Punkte Gut
<150 Punkte und >=125 Punkte Befriedigend
<125 Punkte und >=100 Punkte Genügend
<100 Punkte Nicht genügend

Prüfungsstoff

Die Prüfung zum Vorlesungsteil umfasst den gesamten in der Vorlesung im vorangehenden Sommersemester vorgetragenen Stoffinhalt (Folien des Vortrags sind auf der Webseite verfügbar).

Prüfungsstoff im Praktikumsteil ist das gewählte Thema und der für dessen Implementierung erforderliche Sprachumfang von C++11.

Literatur

R. Sedgewick, Algorithmen in C++ (Teil 1-4), Addison Wesley, 3. überarbeitete Auflage, 2002.
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, published by MIT Press and McGraw-Hill. (First published in 1990.)
Steven Skiena, The Algorithm Design Manual, 2nd Edition, Springer
Donald E. Knuth, The Art of Computer Programming (Vol 1-3), Addison Wesley.

Bjarne Stroustrup, Einführung in die Programmierung mit C++, Pearson Studium.
Bjarne Stroustrup, Programming Principles and Practice Using C++, Addison Wesley.
Bjarne Stroustrup, The C++ Programming Language, Addison Wesley.

Zuordnung im Vorlesungsverzeichnis

Module: ADS UF-INF-09

Letzte Änderung: Mo 07.09.2020 15:20