close

Algorithms and Data Structures 2 (2018WS)

Course Algorithms and Data Structures 2
Type VO, UE
Lecturer Ferscha (VO)
Anzengruber, Gruenberger (UE G1, UE G2, UE G3, UE G4)
Course-Id 340.023 (VO)
340.020 (UE G1)
340.024 (UE G2)
340.025 (UE G3)
340.026 (UE G4)
Hours/week 2 (VO)
1 (UE G1, UE G2, UE G3, UE G4)
News
Hörsaaleinteilung für Klausurtermin 28.1.2019 13:45-15:15 Uhr

Guten Morgen,

die Einteilung für die Klausur "Algorithmen und Datenstrukturen 2" heute um 13:45-15:15 Uhr ist wie folgt:

* Studierende mit einem Nachnamen beginnend mit A-R: HS 1

* Studierende mit einem Nachnamen beginnend mit S-Z: HS 18


Viel Erfolg!

Zielgruppe Hörer der Studienrichtung Informatik im dritten Semester
Ziele Der Begriff "Algorithmus" ist zentral in der technisch orientierten Grundlagenarbeit der Informatik. Jeder Problemstellung geht (aus klassischer Sicht) die Erarbeitung einer allgemeingültigen, eindeutigen, formalisierten und "ausführbaren" Vorschrift (Algorithmus) voraus - jedes Programm ist ein als endlicher Text formulierter und notierter Algorithmus. Hauptanliegen der gegenständlichen Veranstaltung ist es, bewährte Konstruktionsprinzipien und Entwichlungsmethoden an ausgewählten Problem- und Algorithmusklassen vorzustellen und damit eine Methoden- und Entscheidungskompetenz zu entwickeln: Eine allgemeine "konstruktive Theorie" zur Erzeugung eines optimalen Lösungsalgorithmus (für ein als lösbar erkanntes Problem und vorgegebenes Exekutionsmodell) existiert bisher nicht, womit Algorithmuskonstruktion nach wie vor praktische Ingenieursarbeit (oder "Ingenieurskunst") darstellt, deren Qualität sich aus der Kenntnis vieler bewährter Algorithmen bzw. deren Transformation, Integration und Kombination ableitet. Aus diesem Grunde wird keine taxative Behandlung punktueller Lösungen für punktuelle Probleme angestrebt, sondern vielmehr auf Methodenvielfalt, Analogieschlüsse, Lösungskombination, Abstraktion und Vereinfachung Wert gelegt.

In der Übung sollen die in der Vorlesung präsentierten Themen durch praktische Beispiele veranschaulicht werden, konkretes Ausprogrammieren von Algorithmen soll dabei das Verständnis verbessern.
Inhalt Ausgehend vom klassischen Algorithmusbegriff (schrittweises Lösen einer Klasse von Problemen, Zugrundelegung eines Exekutionsmodells (Prozessortyp), endlicher Zeit- und Ressourcenaufwand, vereinbarte Notation) werden Konstruktions- und Darstellungsprinzipien für Algorithmen bzw. geeignete dazugehörige Datenstrukturen präsentiert und prinzipielle Komplexitätsmaße (Abarbeitungsschrittzahl und Speicherplatzbedarf) zu deren quantitativer Beurteilung vorgestellt. Neben dem Anschauungsaspekt, der am besten anhand abstrakter Datentypen vermittelt wird, sollen hier aber auch in verschiedenen Informatikanwendungen nützliche (z.B. Suchen, Sortieren, Graphenalgorithmen) und optimierte Algorithmen (z.B. Skip Listen, Splay Trees) vorgestellt werden. Im Lichte der wachsenden Bedeutung paralleler und verteilter Anwendungen wird besonders auf verteilte Basisalgorithmen und die Konstruktion von Algorithmen für verteilte Exekutionsmodelle eingegangen. Abschließend wird gezeigt, wie durch das Einbringen nichtdeterministischer, stochastischer, evolutionärer oder genetischer Elemente Algorithmen konstruiert werden können, die zur Lösung bestimmter Problemklassen wesentlich leistungsfähiger sind, als die klassischen. Die Veranstaltung geht anhand folgender inhaltlicher Gliederung vor:

Algorithmusbegriff und Komplexität (Resümee aus Algorithmen und Datenstrukturen 1)

  • Intuitiver und klassischer Algorithmusbegriff
  • Algorithmenkonstruktion und Notation
  • Random Access Machine Modell
  • Zeit-/Speicherkomplexität, O-Notation, Korrektheit, Terminierung
  • Laufzeitermittlung, -abschätzung, Schranken

Abstrakte Datentypen

  • Definition
  • Konstruktion
  • Anschauungsbeispiele: Liste, Stack, Queue, Tree, Heap, Set
  • Effiziente Strukturen: Skip Listen, Splay Trees

Sortieren, Suchen, Hashing

  • Mergesort, Heapsort, (Bucket) Radixsort, externes Sortieren
  • Binäre Suche, AVL Bäume, String Matching
  • Hashfunktionen und -datenstrukturen

Divide and Conquer

  • Konstruktionstechnik
  • Anschauungsbeispiele: Karatsuba, Matrixmultiplikation Strassen

Anwendungsorientierte Algorithmen 1: Graphen

  • Terminologie und Eigenschaftsnachweise
  • Breiten-/Tiefensuche, topologische Sortieren
  • Verbundene Komponenten, minimaler SpannBaum
  • kürzeste Wege und Flüße
  • Traveling Salesman (Hamilton Kreis)

Anwendungsorientierte Algorithmen 2: Geometrie

  • 2D Algorithmen (Normalisierungstransformationen, Line Clipping, Polygone)
  • 3D Algorithmen (Koordinatensysteme, 3D Transformationen, Viewing)

Anwendungsorientierte Algorithmen 3: Multimedia

  • Textkomprimierung (run length, statistisch, tabellengesteuert)
  • Bildkomprimierung (Binärbild-, Farbbildkompression)

Parallele Algorithmen

  • PRAM Modelle
  • Reduktionen und Scans
  • Kostenoptimalität (Theorem von Brent)
  • Performance und Speedup Modelle
  • Anschauungsbeispiele:
  • Matrix-Algorithmen, Lineare Gleichungssysteme
  • PRAM Sort
  • Kombinatorisches Suchen

Verteilte Basisalgorithmen

  • Kausale Ordnung, Virtuelle Uhren
  • Synchronisation und Gegenseitiger Ausschluß
  • Wellenalgorithmen
  • Distributed Election
  • Verteilte Terminationserkennung, Konsistente Snapshots
  • Anschauungsbeispiel: Verteilte Simulation

Heuristische Algorithmen

  • Kombinatorische Optimierung, Branch and Bound
  • Simulated Annealing
  • Genetische Algorithmen

Ausblick

  • Probabilistische Algorithmen
  • Future Computing: neuronale, optische, molekulare, quantum computing Ansätze
Vorkenntnisse Zum Verständnis der Vorlesung sind Kenntnisse einer strukturierten, höheren Programmiersprache wie Pascal, Modula-2, Java oder C erforderlich. Die Vorlesung wird durch theoretische und praktische Übungen ergänzt. Programmiersprache für die Übungen ist Java.
Unterlagen gesammelte Vorlesungsvorlagen
Primärliteratur Ottmann, Thomas; Widmayer, Peter: Algorithmen und Datenstrukturen.

Heidelberg: Spektrum Akademischer Verlag, 3. Auflage, 1996.

Behandelt sehr fachkundig und leicht verständlich den „klassichen“ Themenkern einer Standardvorlesung „Algorithmen und Datenstrukturen" (vom Suchen und Sortieren über Adreßberechnungsmethoden und Listenstrukturen (Bäume aller Art) bis zu Geometrischen Algorithmen und Graphenalgorithmen. Auch in elektronischer Form verfügbar.


M.A. Weiss: Data Structures and Algorithm Analysis in Java, Addison-Wesley, 1999.
M.T. Goodrich, R. Tamassia: Data Structures and Algorithms in Java John Wiley & Sons, 1998

Zwei Werke die insbesondere für die praktischen Übungen von Bedeutung sein werden, da sie klassische A&D auf die Zielprogrammiersprache Java abbilden.


G. Tel: Introduction to Distributed Algorithms, Cambridge University Press, 1994.

Standardwerk im Bereich Algorithmen für Distributed Computing.

Sekundärliteratur T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990.
R. Sedgewick: Algorithms in C++, Addison Wesley, 1992.


N. Wirth: Algorithmen und Datenstrukturen, Stuttgart, Teubner, 1983.


A.V. Aho, J.E. Hopcroft, J.D. Ullman: Data Structures and Algorithms, Addison Wesley, 1987.


Knuth, Donald E.:
The Art of Computer Programming. Volume 1 / Fundamental Algorithms.
The Art of Computer Programming. Volume 2 / Seminumerical Algorithms.
Reading, Mass.: Addison Wesley Longman, 1997.

Frühe Standardwerke in der Informatik Grundausbildung.


J. JaJa: An Introduction to Parallel Algorithms, Addison Wesley, 1992..


N. A. Lynch: Distributed Algorithms, Morgan Kaufmann Publishers, San Francisco, 1996.


H. Attiya, J. Welch: Distributed Computing, McGraw-Hill, 1998


M. Quinn: Parallel Computing, McGraw-Hill, 1994

Leistungsnachweis Schriftliche Prüfung am Ende des Semesters.
Übungsmodus Die Übungen dauern 45 Minuten und finden wöchentlich statt. Die ausgearbeiteten Übungen sind von den Studenten - sofern nicht anders festgelegt - spätestens 14 Tage nach der Ausgabe abzugeben. Abgabe und Rückgabe der Übungen erfolgen ausschließlich elektronisch über die Instituts-Webseite. Jeder Student hat die Übungsaufgaben selbstständig zu lösen; Gruppenarbeiten sind nicht gestattet. Bei Zweifeln an der Urheberschaft werden die Übungen aller Beteiligten als nicht abgegeben bewertet. Es werden voraussichtlich 9 Übungen ausgegeben, wovon mindestens 7 abzugeben sind. Jede Übung wird mit maximal 24 Punkten bewertet; für eine positive Note muss der Punktedurchschnitt der besten 7 Übungen mindestens 12 Punkte betragen.