Inhalt

[ 289SEECNESV20 ] VL Algorithmen und Datenstrukturen

Versionsauswahl
Workload Ausbildungslevel Studienfachbereich VerantwortlicheR Semesterstunden Anbietende Uni
3 ECTS B1 - Bachelor 1. Jahr Informationselektronik Rick Rabiser 2 SSt Johannes Kepler Universität Linz
Detailinformationen
Quellcurriculum Bachelorstudium Elektronik und Informationstechnik 2020W
Ziele Algorithmen sind das formale Grundgerüst für die Software-Entwicklung. Sie sind das 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.

Lehrinhalte
  • 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, Beispiele
  • 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
  • Sortieren: Auswahlverfahren, Einfügeverfahren, Shellsort, Quicksort, internes und externes Mischsortieren, Sortieren von Listen, Heapsort, Topologisches Sortieren, Komplexität von Sortierverfahren
  • Bäume: Begriffe, Binäre Suchbäume, Balancierte Bä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
  • Klassifikation von Algorithmen
Beurteilungskriterien Vorlesungsklausur am Ende des Semesters
Lehrmethoden 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.

Abhaltungssprache Deutsch
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.
Lehrinhalte wechselnd? Nein
Sonstige Informationen Die Vorlesung wird foliengestützt abgehalten. Die Folien und ergänzende Unterlagen werden zum Download im PDF-Format bereitgestellt.
Äquivalenzen MEBPFVOPIN1: VL Praktische Informatik 1 (3 ECTS)
Präsenzlehrveranstaltung
Teilungsziffer -
Zuteilungsverfahren Zuteilung nach Reihenfolge