Intelligent and Interactive Systems

User Tools

Site Tools


courses:2021s:703010:start

Algorithmen und Datenstrukturen (VO3 + PS2, Bachelor)

Die Vorlesung und das zugehörige Proseminar werden dieses Semester über Twitch gehalten (ähnlich wie die LV Rechnerarchitektur WS 2020/21, aber über einen anderen Kanal). Bitte erstellen Sie sich dort ein Pseudonym (eine Nutzerkennung), um an der Diskussion im Chat teilnehmen zu können. Dieses Pseudonym wird nicht mit Ihrer Identität in Systemen der Universität Innsbruck verknüpft.


Der 2. Klausur-Termin ist der 8.10.2021, 14:15-15:45. Bitte melden Sie sich ggf. während des Anmeldungszeitfensters im LFU:Online an. Die Klausur wird nach der 3G-Regelung in Präsenz abgehalten, falls dies möglich ist; andernfalls wird sie online im OLAT stattfinden.


Zeiten und Zugang

Stream für Vorlesung und Proseminar: https://www.twitch.tv/uibkiis_de
Der Stream startet in der Regel etwa eine Viertelstunde vor Veranstaltungsbeginn. Er wird jeweils aufgezeichnet und steht für mindestens eine Woche nach der Live-Übertragung zur Verfügung.

Während des Streams werden über ARSnova Umfragen an das Publikum gerichtet.

Die Vorlesung findet mittwochs 13:15-15:30 statt.

Das Proseminar findet montags 17:00-18:30 statt, für alle Gruppen gleichzeitig. Jede Proseminarsitzung beginnt mit einem kurzen Online-Test im OLAT. Teilnahme an diesem Test ist für alle verpflichtend, die den Kurs als eingeschriebene Studierende angerechnet bekommen. Die Vorbereitung auf diese Tests erfolgt durch Hausübungen, die jeweils ab Freitag unter demselben Link abgerufen werden können.

Für Q&A und Diskussionen außerhalb der Lehrveranstaltungszeiten steht eingeschriebenen Studierenden ein Forum zur Verfügung.

Agenda und Materialien

Proseminar-Langtest

2021-05-03 17:00-17:45 wird statt des üblichen Kurztests ein 45-minütiger Test stattfinden, wie üblich im OLAT. Die hier erzielten Punkte fließen mit dem gleichen Gewicht in die Proseminar-Note ein wie die der Kurztests.

Lehrbuch

Der Kurs folgt im Wesentlichen Goodrich, Tamassia, Goldwasser, Data Structures and Algorithms in Java, 6th Edition, Wiley 2014 (International Student Version; GTG). Eine Anschaffung des Buchs wird für die meisten nicht erforderlich sein (es sei denn, Sie ziehen ein Selbststudium dem regelmäßigen Vorlesungsbesuch vor); eine Konsultation in der Bibliothek wird jedoch allen empfohlen. Ältere Ausgaben (noch ohne Goldwasser) sind möglicherweise weit günstiger erhältlich, und sind für diesen Kurs größtenteils ebenso hilfreich.

Der Student Companion Site enthält weiteres Material, insbesondere Java-Quellcode aus dem Buch.

Zeitplan und Kursmaterialien

Die grünen Titel der Kapitel verlinken zu PDF-Dateien mit dem Inhalt der in der Vorlesung verwendeten Slides ergänzt um weiteres Material.

Die Inhalte werden jeweils vor dem Vorlesungstermin zur Verfügung gestellt. Die Kurzvideos sind auch gesammelt über die YouTube-Playlist erreichbar.

Datum Kapitel 00 ▾▴ Thema Buch
2021-03-03 Kapitel 00 ▾▴ Einführung GTG 2.1
2021-03-03 Video 0.1 Abstrakte Datentypen, Datenstrukturen und Algorithmen
2021-03-03 Kapitel 01 ▾▴ Analyse von Algorithmen GTG 1.8.2, 4
2021-03-03 Video 1.1 Empirische Laufzeitanalyse
2021-03-03 Video 1.2 Zählen primitiver Operationen
2021-03-03 Video 1.3 Groß-O Notation
2021-03-03 Video 1.4 Eigenschaften von Groß-O
2021-03-10 Video 1.5 Asymptotische Laufzeitanalyse
2021-03-10 Video 1.6 Verwandte von Groß-O
2021-03-10 Kapitel 02 ▾▴ Rekursion GTG 5
2021-03-10 Video 2.1 Fakultät
2021-03-10 Video 2.2 Binärsuche
2021-03-17 Video 2.3 Verzeichnisbaum
2021-03-17 Video 2.4 Rekursion und Iteration
2021-03-17 Kapitel 03 ▾▴ Stapel und Schlangen GTG 6
2021-03-17 Video 3.1 ADT Stapel
2021-03-17 Video 3.2 Datenstrukturen und Algorithmen für Stapel
2021-03-17 Video 3.3 Warteschlange
2021-03-17 Video 3.4 Doppelstapel
2021-03-24 Kapitel 04 ▾▴ Listen-Abstraktionen GTG 7
2021-03-24 Video 4.1 ADT Liste und DS ArrayList
2021-03-24 Video 4.2 Dynamische Arrays
2021-03-24 Video 4.3 Positionsbasierte Listen
2021-03-24 Video 4.4 Iteratoren
2021-04-14 Kapitel 05 ▾▴ Bäume GTG 8
2021-04-14 Video 5.1 ADT und Methoden
2021-04-14 Video 5.2 Binärbäume
2021-04-14 Video 5.3 Datenstrukturen
2021-04-14 Video 5.4 Prä-, Post-, und Inorder-Traversierung
2021-04-14 Video 5.5 Euler-Tour und Breiten-Traversierung
2021-04-21 Kapitel 06 ▾▴ Vorrangwarteschlangen GTG 9
2021-04-21 Video 6.1 Abstrakter Datentyp
2021-04-21 Video 6.2 Implementierung mittels Liste
2021-04-21 Video 6.3 Heap
2021-04-21 Video 6.4 Implementierung mittels Heap
2021-04-21 Video 6.5 Bottom-Up Heap Construction
2021-04-21 Video 6.6 Sortieren mit einer Vorrangwarteschlange
2021-04-28 Kapitel 07 ▾▴ Zuordnungstabellen GTG 10
2021-04-28 Video 7.1 ADT und Methoden
2021-04-28 Video 7.2 Lookup Tables und Hash-Codes
2021-04-28 Video 7.3 Einfache Hash-Funktionen
2021-04-28 Video 7.4 Kompressionsfunktionen und Beispiele
2021-04-28 Video 7.5 Kollisionsbehandlung: Überblick
2021-04-28 Video 7.6 Kollisionsbehandlung: Offene Addressierung
2021-04-28 Video 7.7 Hash-Tabellen: Wichtige Aspekte
2021-05-05 Kapitel 10 ▾▴ Gierige Algorithmen GTG 12.4
2021-05-05 Video 10.1 Münzrückgabe
2021-05-05 Video 10.2 Huffman Coding: Einführung
2021-05-05 Video 10.3 Huffman Coding: Algorithmus und Analyse
2021-05-05 Video 10.4 Das fraktionale Rucksack-Problem
2021-05-05 Kapitel 11 ▾▴ Teile & Herrsche; Sortieren GTG 13
2021-05-05 Video 11.1 Merge-Sort
2021-05-05 Video 11.2 Quicksort
2021-05-05 Video 11.3 Vergleichsbasiertes Sortieren: Minimale Laufzeit
2021-05-05 Video 11.4 Vergleichsbasiertes Sortieren: Gegenüberstellung
2021-05-12 Kapitel 12 ▾▴ Dynamische Programmierung GTG 12.5
2021-05-12 Video 12.1 Paradigma
2021-05-12 Video 12.2 Längste gemeinsame Untersequenzen: Ansatz
2021-05-12 Video 12.3 Längste gemeinsame Untersequenzen: Algorithmus
2021-05-12 Video 12.4 Rekonstruktion der längsten gemeinsamen Untersequenzen
2021-05-19 Kapitel 13 ▾▴ Graphen GTG 14
2021-05-19 Video 13.1 Konzepte und ADT
2021-05-19 Video 13.2 Datenstrukturen
2021-05-19 Video 13.3 Tiefentraversierung
2021-05-19 Video 13.4 Breitentraversierung
2021-05-19 Video 13.5 Kürzeste Pfade und Dijkstras Algorithmus
2021-05-19 Video 13.6 Dijkstras Algorithmus: Korrektheit und Laufzeit
2021-05-26 Kapitel 08 ▾▴ Zeichenkettensuche GTG 12.2 außer 12.2.2
2021-05-26 Video 8.1 Problemstellung und Brute-Force-Algorithmus
2021-05-26 Video 8.2 Knuth-Morris-Pratt-Algorithmus
2021-05-26 Video 8.3 KMP Failure-Funktion
2021-05-26 Kapitel 09 ▾▴ Suchbäume GTG 11
2021-05-26 Video 9.1 Konzepte und ADT
2021-05-26 Video 9.2 Rotation für selbstausgleichende Suchbäume
2021-05-26 Video 9.3 AVL-Bäume
2021-06-02 Video 9.4 Mehrweg-Suchbäume
2021-06-02 Video 9.5 (2,4)-Bäume: Einfügen und Entfernen
2021-06-02 Video 9.6 Rot-Schwarz-Bäume: Konzepte und Einfügen
2021-06-02 Video 9.7 Rot-Schwarz-Bäume: Entfernen und Laufzeiten
2021-06-09 Kapitel 14 Anwendungsbeispiel: Lernplanung J.P., Planning Readings
2021-06-16 Wiederholung; Fragen
2021-06-23 Klausur (1. Termin) im OLAT

Feedback

Über Kritik, Fragen und Anregungen per E-Mail an Justus.Piater@uibk.ac.at freuen wir uns sehr. Sollten wir bei der Verwendung von Materialien versehentlich gegen Ihre Urheberrechte verstoßen, machen Sie uns bitte darauf aufmerksam.

courses/2021s/703010/start.txt · Last modified: 2022/01/08 12:39 by Justus Piater