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.

English, switch language
Zur JKU Startseite

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

Es werden 9 Übungsblätter zu den Themen der Vorlesung ausgegeben. Die Übungsvorbesprechung findet am Mittwoch, 08. März 2023 während der Vorlesung statt. Die erste Übungssitzung mit Ausgabe des ersten Übungsblattes am Mittwoch, 15. März 2023.

510.211   UE Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 12:00-12:45

Room: HS 14

Start: 15.03.2023, Vorbesprechung am 08.03.2023 im Rahmen der ersten VL

510.214   UE Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 12:45-13:30

Room: HS 14

Start: 15.03.2023, Vorbesprechung am 08.03.2023 im Rahmen der ersten VL

510.215   UE Algorithmen und Datenstrukturen

1 UE

Feichtinger

MI 13:45-14:30

Room: HS 14

Start: 15.03.2023, Vorbesprechung am 08.03.2023 im Rahmen der ersten VL

 

Modus der Übung

  • Diskussion offener Fragen/Musterlösungen
  • Veranschaulichung der Übungen durch Beispiele
  • Vorstellung der aktuellen Aufgabenstellung
  • Keine Anwesenheitspflicht

Tutorium

Ein virtuelles Tutorium mit den Tutoren findet jeden Dienstag von 16:15 - 17:00 Uhr statt. Der Zoom-Link wird in Moodle zur Verfügung gestellt.

Abgabe von Übungsaufgaben

  • Elektronische Abgabe der Übungen im Moodle-Kurs
  • Jede Übung hat eine Bearbeitungszeit von mindestens 7 Tagen. Fester Abgabetermin um 23:59:00 Uhr!
  • Als Abgabeformate werden nur ZIP-Archive und/oder PDF akzeptiert.
    • PDF für (hand-)schriftliche Aufgaben; ZIP für Programmieraufgaben.
  • Die einzureichenden Dateien müssen einer Namenskonvention folgen:
    • algo1_ue<nr>_<matrNr>.zip (Beispiel: algo1_ue02 _01255105.zip).
  • Alle für die Lösung relevanten Klassen sind in einem Java-Paket zu speichern.
  • Es werden nur Einzelarbeiten akzeptiert. Erkannte Plagiate werden bestraft. Mindestens erhalten ALLE Beteiligten 0 Punkte OHNE Ausnahme. Weitere Maßnahmen werden festgelegt. Das Ändern von Variablennamen o.ä. schützt nicht vor Plagiaten.

Benotung

  • Insgesamt 9 Übungsblätter mit jeweils unterschiedlichen Aufgabenstellungen zur Vorlesung.
  • 3 der ersten 4 Übungen und 3 der zweiten 4 Übungen sind abzugeben. Übung 9 ist eine Wiederholung.
  • In jeder Übung können maximal 24 Punkte erreicht werden.
  • Die 8 besten Übungen der 9 Übungsblätter gehen in die Note ein.
  • Die Summe der erreichten Punkte der 8 besten bewerteten Übungen bestimmt die Note.
  • Nicht abgegebene Übungen werden mit 0 Punkten benotet.

Noten

Note

Minimum

Maximum

Sehr Gut

>=168

<=192

Gut

>=144

<168

Befriedigend

>=120

<144

Genügend

>=96

<120

Nicht Genügend

0

<96

 

Material

Die Übungsdetails und das Zusatzmaterial zum Kurs stehen im Moodle-Kurs zum Download bereit.

{{ 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 }}
 
Zur JKU Startseite

Johannes Kepler Universität Linz

Altenberger Straße 69

4040 Linz, Österreich

Fax +43 732 2468 4929
Kontakt