LEA

Parallele Algorithmen

  • Dozent:
    Prof. Dr. Ernst W. Mayr
  • Modul: IN2011, TUMonline
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
    Vertiefende Vorlesung im Gebiet Algorithmen und Wissenschaftliches Rechnen
  • Zeit und Ort:
    Dienstag, 08:30–10:00, 00.13.009A
    Donnerstag, 08:30–10:00, MI HS 2
  • Übung:
    2 SWS Übung zur Vorlesung
    Übungsleitung: Chris Pinkau
    Fr, 12:15–13:45, Raum 00.08.055
  • Klausur:
    Termin: 11.2.2013, 14:30 bis 17:30 Uhr, im Hörsaal Ch 22210.
    Die angegebenen Zeiten sind die reinen Bearbeitungszeiten. Anwesenheit mindestens 15min vorher.
    Als Hilfsmittel ist nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • ECTS: 8 Punkte
  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
  • Empfehlenswert für:
    Erweiterte Kenntnisse im Bereich Algorithmen

Inhalt

siehe hier.

Literatur

Die Inhalte der Vorlesung werden in wesentlichen Teilen durch folgende Bücher und Artikel abgedeckt:
  1. F. Thomson Leighton.
    Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes.
    Morgan Kaufmann: San Mateo, CA, 1992.
    Kopien aus dem Buch, Seiten 144 - 199.
    Kopien aus dem Buch, Seiten 223 - 226.
    Kopien aus dem Buch, Seiten 277 - 353.
    Kopien aus dem Buch, Seiten 389 - 430.
    Kopien aus dem Buch, Seiten 430 - 510.
  2. Joseph JaJa.
    An introduction to parallel algorithms.
    Addison-Wesley: Reading, MA, 1997.
    Kopien aus dem Buch, Seiten 529 - 561.
  3. Jeffrey D. Ullman.
    Computational Aspects of VLSI.
    Computer Science Press: Rockville, USA, 1984
  4. Selim G. Akl.
    The Design and Analysis of Parallel Algorithms.
    Prentice Hall: Englewood Cliffs, NJ, 1989.
  5. John E. Savage:
    Models of Computation
    Addison-Wesley: Reading, MA, 1998.
  6. S. Arora, B. Barak:
    Computational Complexity --- A Modern Approach
    Cambridge University Press, 2009.
    Link zu einer Draft-Version des Buches
    Kapitel über Boolean Circuits
  7. K. Rüdiger Reischuk:
    Komplexitätstheorie --- Band 1: Grundlagen
    Teubner, Stuttgart, 1999.
  8. C.P. Schnorr, A. Shamir:
    An optimal sorting algorithm for mesh connected computers
    STOC 1986.
  9. V. Heun, E.W. Mayr:
    Efficient Dynamic Embeddings of Binary Trees into Hypercubes
    J. Algorithms 2002.