Zur JKU Startseite
LIT Cyber-Physical Systems Lab
Was ist das?

Institute, Schools und andere Einrichtungen oder Angebote haben einen Webauftritt mit eigenen Inhalten und Menüs.

Um die Navigation zu erleichtern, ist hier erkennbar, wo man sich gerade befindet.

Algorithmen und Datenstrukturen

VL Algorithmen  und Datenstrukturen (Vorlesung)

Algorithmen sind das formale Grundgerüst für die Software-Entwicklung. Sie sind ein Bindeglied zwischen der Theoretischen Informatik und der eigentlichen Programmierung.

In dieser Lehrveranstaltung werden die wesentlichen Eigenschaften von Algorithmen untersucht und wichtige Klassen von Algorithmen in Bezug auf ihre praktische Anwendung vorgestellt.

Die Behandlung der Algorithmen erfolgt großteils in Pseudocode. Dies erlaubt die Betrachtung von Algorithmen losgelöst von einer konkreten Programmiersprache. Manche Lehrinhalte werden durch Vorführungen (Demo-Videos) veranschaulicht. Manche Algorithmen werden auch an der Tafel/am Whiteboard gemeinsam konstruiert.

Inhalt

  • Der Algorithmusbegriff
    Definition, Abgrenzung zwischen Algorithmen und Programmen, Darstellungsarten, Abstraktionsschichten und Bestandteile von Algorithmen
  • Spezifikation
    Zweck, Schnittstellenbeschreibung, Aufgabenbeschreibung, Darstellungsarten
  • Schrittweise Verfeinerung
    "Divide & Conquer", systematisches Lösen großer Probleme, Beispiel in Java
  • Algorithmen mit Gedächtnis
    Begriff, Implementierungsvarianten
  • Komplexität
    Begriff, Laufzeitanalyse, Laufzeitmessung, Asymptotische Komplexität, Minimale Komplexität von Problemen
  • Dynamische Datenstrukturen
    Klassen als Referenztypen, Lineare Listen, Unsortierte Listen, Sortierte Listen, Ringlisten, Doppelt verkettete Listen, Stacks, Queues, Mengen
  • Rekursion
    Begriff, Klassifizierung, Terminierung, Anwendungen, Umwandlung rekursiver Algorithmen in iterative und umgekehrt
  • Bäume
    Begriffe, Binäre Suchbäume, Balancierte Bäumeer Suchbäume, Topdown-234-Bäume, Rot-Schwarz-Bäume, B-Bäume
  • Graphen
    Begriffe, Depth-First-Search, Breadth-First-Search, Kleinster spannender Baum, Kürzester Pfad, Transitive Hülle, Serialisierung von Graphen
  • Exhaustion
    Das n-Damen-Problem, Schema zum Suchen einer Lösung, Exhaustionsvariante, Optimierungsvariante, Darstellung von Lösungsvektoren, Näherungsverfahren, Nichtdeterministische Algorithmen
  • Sortieren
    Auswahlverfahren, Einfügeverfahren, Shellsort, Quicksort, internes und externes Mischsortieren, Sortieren von Listen, Heapsort, Topologisches Sortieren, Komplexität von Sortierverfahren

Leistungsnachweis:

VO: Vorlesungsklausur am Ende des Semesters.

UE: Beurteilung ausgearbeiteter Übungsaufgaben.

 

Unterlagen

Die Vorlesung wird foliengestützt abgehalten. Die Folien und ergänzende Unterlagen werden zum Download im PDF-Format bereitgestellt.

 

Literatur

  • Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms. Addison-Wesley 1983.
  • Goodrich, M. T., Tamassia, R., and Goldwasser, M. H.: Data structures and algorithms in Java. John Wiley & Sons. 2014.
  • Knuth D.E.: The Art of Computer Programming. Addison-Wesley 1973.
    Band 1: Fundamental Algorithms.
    Band 2: Seminumerical Algorithms.
    Band 3: Sorting and Searching.
  • Pomberger G., Dobler H.: Algorithmen und Datenstrukturen. Pearson 2008.
  • Saake G., Sattler K.: Algorithmen und Datenstrukturen. dpunkt 2006.
  • Sedgewick R.: Algorithmen in Java. Pearson 2014.
  • Wirth N.: Algorithmen und Datenstrukturen. Teubner Studienbücher Informatik 1986.

Links

Visualisierung und Animation diverser Algorithmen: hier, öffnet eine externe URL in einem neuen Fenster und hier, öffnet eine externe URL in einem neuen Fenster.

{{ labelInLang('cid') }} {{ labelInLang('title') }} {{ labelInLang('registration') }} {{ labelInLang('type') }} {{ labelInLang('hours') }} {{ labelInLang('teachers') }} {{ labelInLang('rhythm') }}
{{ item._id }} ({{ item.term }}) {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('register') }} {{ item.type }} {{ item['hours-per-week'] }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }} {{ item.rhythm }}
{{ item._id }} ({{ item.term }})
{{ labelInLang('title') }} {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('registration') }} {{ labelInLang('register') }}
{{ labelInLang('type') }} {{ item.type }}
{{ labelInLang('hours') }} {{ item['hours-per-week'] }}
{{ labelInLang('teachers') }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }}
{{ labelInLang('rhythm') }} {{ item.rhythm }}
 

UE Algorithmen und Datenstrukturen (Übungen für Mechatronik, ELIT, Maschinenbau)

Die Übungen für Algorithmen und Datenstrukturen dienen zur Vertiefung der Inhalte der gleichnamigen Vorlesung. Die Übungen werden entsprechend eng an den Vorlesungsstoff angepasst und ausgegeben.

Informationen zu der Vorlesung finden Sie hier, öffnet eine externe URL in einem neuen Fenster

Es werden 7 Übungsblätter zu den Themen der Vorlesung ausgegeben. Die Übungsvorbesprechung findet am Mittwoch, 09. März 2022 im Rahmen der Vorlesung statt. Die erste Übungseinheit mit der Ausgabe des ersten Übungsblattes am Mittwoch, 16. März 2022.

510.211   UE   Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 12:00-12:45

Raum: BA 9909

Beginn: 09.03.2022, Vorbesprechung am 09.03.22 im Rahmen der ersten VL

510.214   UE   Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 12:45-13:30

Raum: BA 9909

Beginn: 09.03.2022, Vorbesprechung am 09.03.22 im Rahmen der ersten VL

510.215   UE   Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 13:45-14:30

Raum:HF 9904

Beginn: 09.03.2022, Vorbesprechung am 09.03.22 im Rahmen der ersten VL

510.216   UE   Algorithmen und Datenstrukturen

1 UE

Bertram

MI 14:30-15:15

Raum: HF 9904

Beginn: 09.03.2022, Vorbesprechung am 09.03.22 im Rahmen der ersten VL

 

Übungsmodus

  • Die Übung wird in Präsenz abgehalten (je nach Bestimmungen könnte sich dies noch auf Hybrid/Digital ändern)
  • Wöchentliche Übungen (mit Ausnahmen zu Ostern und zum OÖ Landespatron)
  • Besprechung von offenen Fragen/Musterlösungen
  • Veranschaulichung der Übungen durch Beispiele
  • Vorstellung der aktuellen Aufgabenstellung
  • Keine Anwesenheitspflicht

Übungsabgabe

  • Elektronische Übungsabgabe im Moodle-Kurs, öffnet eine externe URL in einem neuen Fenster
  • Mindestens 14 Tage Bearbeitungszeit
  • Abgabe jeweils Mittwochs um 23:59:00 CEST (hard deadline!).
  • Es werden nur ZIP Archive und/oder PDF als Abgabeformate akzeptiert.
  • PDF für (hand-)schriftliche Aufgaben; ZIP für Programmieraufgaben
  • Die abzugebenden Dateien müssen einer Namenskonvention folgen:
  • algo_ue[#]_[matrikelnummer].zip (Beispiel: algo_ue02_01255105.zip)
  • Nur die zur Verfügung gestellten Java Klassen abgeben
  • Die definierten Schnittstellen dürfen nicht verändert werden!
  • Source code formatieren!
  • Es werden ausschließlich Einzelausarbeitungen akzeptiert. Entdeckte Plagiate werden geahndet. Das Ändern von Variablennamen oder ähnlichem verhindert kein Plagiat! Bei Plagiatsverdacht werden alle involvierten Übungen mit 0 Punkten bewertet!

Leistungsnachweis

  • Insgesamt 7 Übungsblätter mit jeweils verschiedenen Aufgaben mit Bezug zur Vorlesung
  • Bei jeder Übung können bis zu 36 Punkte gesammelt werden.
  • Die Summe der 6 besten Übungen bestimmt die Note.
  • Die 6 besten Übungen der 7 Übungen werden in die Benotung einbezogen.
  • Nicht abgegebene Übungen werden mit 0 Punkten gewertet.

Notenschlüssel

Note

Minimum

Maximum

Sehr Gut

>=189

<=216

Gut

>=162

<189

Befriedigend

>=135

<162

Genügend

>=108

<135

Nicht Genügend

0

<108

 

Unterlagen

Die Übungsangaben und ergänzende Unterlagen zur Übung stehen im Moodle Kurs zum Download zur Verfügung.

 

{{ labelInLang('cid') }} {{ labelInLang('title') }} {{ labelInLang('registration') }} {{ labelInLang('type') }} {{ labelInLang('hours') }} {{ labelInLang('teachers') }} {{ labelInLang('rhythm') }}
{{ item._id }} ({{ item.term }}) {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('register') }} {{ item.type }} {{ item['hours-per-week'] }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }} {{ item.rhythm }}
{{ item._id }} ({{ item.term }})
{{ labelInLang('title') }} {{ item.title }}: {{ item.subtitle }}
{{ labelInLang('moreinfo') }}
{{ labelInLang('expand') }} {{ labelInLang('collapse') }}
{{ labelInLang('registration') }} {{ labelInLang('register') }}
{{ labelInLang('type') }} {{ item.type }}
{{ labelInLang('hours') }} {{ item['hours-per-week'] }}
{{ labelInLang('teachers') }} {{ teacher.firstname }} {{ teacher.lastname }} {{ item.teachers.teacher.firstname }} {{ item.teachers.teacher.lastname }}
{{ labelInLang('rhythm') }} {{ item.rhythm }}