| 
      
       Dozent: 
       Prof. Dr. Ernst W. Mayr
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik) 
       Vertiefende Vorlesung im Gebiet Algorithmen
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
        Di 08:30 - 10:00, Hörsaal 2770 
	Fr 08:30 - 10:00, Hörsaal 1100 
	Beginn: 2. Mai
	
        | 
     
     
      
        
       | 
      
       Übung: 
       2 SWS Übung zur Vorlesung 
       Di 10:15 - 12:15, Raum S2225 
       Übungsleitung:
       Tom Friedetzky 
       Übungsschein: Einen Schein erhält, wer
       wenigstens 40% der Punkte zu den Hausaufgaben erreicht und
       erfolgreich an der Semestralklausur teilnimmt.
       
        | 
     
     
      
        
       | 
      
       Hörerkreis: 
       Studierende im Hauptstudium der Informatik 
       Studierende mit Nebenfach Informatik
       
        | 
     
     
      
        
       | 
      
       Voraussetzungen: 
       Stoff des Informatik-Grundstudiums 
       Vorlesung Parallele Algorithmen
       empfehlenswert
       
        | 
     
     
      
        
       | 
      
       Empfehlenswert für: 
       Grundlegend im Bereich Algorithmen
       
        | 
     
     
      
        
       | 
      
       Inhalt: 
       Der Zweck dieser Vorlesung ist das Studium fundamentaler Konzepte in der
       Parallelrechnung. Es werden Maschinenmodelle, der Entwurf paralleler
       Algorithmen und die Grundlagen paralleler Komplexitätstheorie
       besprochen.
       
        | 
     
     
      
        
       | 
      
       Themenübersicht: 
       
-  Hyperwürfel und hyperwürfelartige Netzwerke
-  Shuffle-Exchange und de Bruijn-Netzwerke
-  Definitionen und grundlegende Eigenschaften
 -  The Diaconis Card Tricks:
-  Ein Misch-Trick
 -  Ein Gedankenlese-Trick
  
 -  Simulation normaler Hyperwürfel-Algorithmen
 -  Weitere Einbettungs- und Teilgraph-Resultate
  
 -  Die Diskrete Fourier-Transformation (FFT)
-  Die algorithmischen Grundlagen
 -  Implementation auf dem Butterfly- und SE-Netzwerk
 -  Anwendungen: Konvolution, Polynomarithmetik
 -  Bitkomplexität der DFT
  
 -  Algorithmen für Packet-Routing
-  Definitionen, Modelle
 -  Greedy-Algorithmen, worst-case Instanzen
 -  Eine untere Schranke für oblivious Routing
 -  Konzentrations- und Monotones Routing:
-  Konzentrationsrouting auf dem Hyperwürfel
 -  Konzentrationsrouting auf dem Butterfly
 -  Inverses Konzentrationsrouting
 -  Monotones Routing
 -  Verallgemeinertes monotones Routing
  
 -  Randomisiertes Routing auf dem Butterfly
-  Analyse der Knotenbelastung
 -  Analyse des Zeitbedarfs
 -  Andere Contention-Resolution-Protokolle
 -  Übertragung auf den Hyperwürfel
  
 -  Umwandlung von Worst-case Instanzen in Average-Case Instanzen
-  Hashing, $r$-fach unabhängige Hashfunktionen
 -  Randomisiertes Routing
  
 -  Ergänzungen: Ranade's Algorithmus, Combining, Mehrfachkopien
  
 -  Sortieren
-  Odd-Even-Merge-Sort
 -  Sortieren kleiner Datenmengen
  
  
 -  Das PRAM-Modell
-  Grundlegende Diskussion
 -  Die Varianten des PRAM-Modells
 -  Grundlegende Algorithmen
-  Censusfunktionen und Präfixberechnung
 -  Beschleunigte Kaskadierung
-  Maximum in konstanter Zeit
 -  Algorithmus mit doppelt-logarithmischem Zeitbedarf
 -  Beschleunigte Kaskadierung
  
 -  Partitionierung
-  Einfacher Merging-Algorithmus
 -  Optimaler EREW-Merging-Algorithmus
  
 -  Symmetrieauflösung
-  Die grundlegende Routine
 -  Ein schneller 3-Färbungsalgorithmus
 -  Optimaler 3-Färbungsalgorithmus
  
  
 -  Listen und Bäume
-  List Ranking
-  Ein einfacher LR-Algorithmus
 -  Ein arbeits- und zeitoptimaler LR-Algorithmus, mit Analyse
  
 -  Euler-Tour
-  Definition, einfacher Algorithmus
 -  Berechnung von Baumfunktionen: 
-  Wurzeln eines Baums
 -  Postorder-Numerierung 
 -  Knotentiefe
  
  
 -  Baumkontraktion
-  Die Rake-Operation
 -  Auswertung arithmetischer Baumausdrücke
  
 -  Lowest Common Ancestors
-  Definition
 -  Der Schieber/Vishkin-Algorithmus
  
 -  Sortieralgorithmen
-  Definitionen
 -  Merging-basierte Algorithmen
 -  Cole's Merge-Sort
  
 -  Untere Schranken für die PRAM
-  Grundlagen
 -  Die allgemeine Methode
 -  Schranken für spezifische Probleme
  
  
 -  P-Vollständigkeit
-  Konzepte der Parallelisierbarkeit
 -  CVP ist P-vollständig
 -  Anwendungen auf DFS, LP
  
  
  
       
       
        | 
     
     
      
        
       | 
      
       Weiterführende bzw. vertiefende Vorlesungen: 
       Effiziente Algorithmen und
       Datenstrukturen II
       
        | 
     
     
      
        
       | 
      
       Skript: 
       kein Skript
       
        | 
     
     
      
        
       | 
      
       Literatur: 
        
	 - F. Thomson Leighton:
	 
 - Introduction to Parallel Algorithms and Architectures:
 
             Arrays - Trees - Hypercubes 
	     Morgan Kaufman Publishers, San Mateo, CA, 1992
	  - Joseph JáJá:
	 
 - Parallel Algorithms
 
                Addison Wesley Publishing Company, 1992
	  
	
        | 
     
     
      
        
       | 
      
       Sprechstunde: 
       siehe hier
       
        |