| 
      
       Dozent: 
       Prof. Dr. Ernst W. Mayr
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik) 
       Wahlpflichtvorlesung im Gebiet Algorithmen
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
        Di 08:30 - 10:00, Hörsaal 1221 
	Fr 08:30 - 10:00, Hörsaal 0220 
	Beginn: 5. November
	
        | 
     
     
      
        
       | 
      
       Übung: 
       2 SWS Übung zur Vorlesung 
       Mi 12:00 - 14:00, Raum S2229 
       Ü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
       
        | 
     
     
      
        
       | 
      
       Empfehlenswert für: 
       Grundlagen 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.
        
       Der zweite Teil der Vorlesung findet im kommenden Sommersemester statt.
       
        | 
     
     
      
        
       | 
      
       Themenübersicht: 
       
         -  Grundlagen
	   
	     -  Notationen, Landau-Symbole
	   
  
          -  Felder und Matrizen
	   
	     -  Sortieren auf linearem Feld
	       
		 -  Wortorientierter Algorithmus
		 
 -  Bitorientierter Algorithmus
		 
 -  Untere Schranken
		 
 -  Gegenbeispiel - Abzählen
		 
 -  Eigenschaften des Netzwerk-Modells
	       
  
	      -  Ganzzahlige Arithmetik
	       
		 -  Carry-Lookahead-Adder
		 
 -  Präfix-Berechnungen
		 
 -  Segmentiertes Präfix
		 
 -  Carry-Save-Adder
		 
 -  Parallele Multiplikation zweier Zahlen, Konvolution
	       
  
	      -  Matrix-Algorithmen
	       
		 -  Matrix-Vektor-, Matrix-Matrix-Produkt
		 
 -  Algorithmen für Dreiecksmatrizen
		 
 -  Gauß-Elimination, mit Anwendungen: Matrix-Invertierung,
		      Rangbestimmung, Determinante
	       
  
	      -  Graph-Algorithmen
	       
		 -  Transitive Hülle
		 
 -  Zusammenhangskomponenten
		 
 -  Kürzeste Pfade
		 
 -  BFS-Spannbäume
		 
 -  Minimale Spannbäume, auf Gitter
	       
  
	      -  Mehr über Sortieren auf dem Gitter
	       
		 -  Odd-even transposition sort
		 
 -  Ein $\sqrt{n}(1+\log n)$ Sortieralgorithmus
		 
 -  Ein $3\sqrt{n} + o(\sqrt{n})$ Sortieralgorithmus
	       
  
	      -  Packet Routing
	       
		 -  Greedy Algorithmen, Analyse des einfachen
		      2D greedy Algorithmus
		 
 -  Greedy Algorithmen im Durchschnitt
			(n Pakete mit zufälligen Zieladressen)
			Eine Chernoff-Schranke
		 
 -  Randomisierte Routing-Algorithmen
		 
 -  Deterministische Routing-Algorithmen mit
		      kleinen Warteschlangen
		 
 -  Ein Off-line Algorithmus, der Heiratssatz
		 
 -  Andere Rounting-Modelle und Algorithmen
	       
  
	      -  Bild-Analyse und geometrische Algorithmen
	       
		 -  Komponentenbestimmung
		 
 -  Die Hough-Transformation
		 
 -  Nächste Nachbarn
		 
 -  Konvexe Hülle
		 
 -  Ausblick auf andere Architekturen:
		      höherdimensionale Felder, Tori, Hex-Gitter, MOT
	       
  
	     
	  -  Hyperwürfel und hyperwürfelartige Netzwerke
	   
 
	     -  Der n-dimensionale (binäre) Hyperwürfel
	       
		 -  Definitionen und Eigenschaften
		 
 -  Einbettung von Feldern in den Hyperwürfel
		      M(3,5) nicht Teilgraph von H(4)
		 
 -  Einbettung vollständiger Binärbäume
		   
		     -  Paritätsargument
		     
 -  DRCBT(r) ist Teilgraph des H(r)
		     
 -  Binomialbaum-Einbettung, normale
				Hyperwürfelalgorithmen
		     
 -  Dynamische Einbettung des DRCBT
		   
  
		  -  Einbettung beliebiger Binärbäume
		   
		     -  Der Flip-Bit-Algorithmus, Analyse
		     
 -  Eine untere Schranke für Algorithmen ohne Migration 
		     
 -  Ein optimaler deterministischer Algorithmus
				für beliebige Binärbäume
		     
 -  Optimale Dynamisierung
		   
  
	         
	      -  Butterfly, CCC, Benes-Netzwerk
	       
		 -  Das Butterfly-Netzwerk
		 
 -  Das Cube-Connected-Cycles-Netzwerk
		 
 -  Das Benes-Netzwerk (auch geschlossen)
	       
  
	     
         
       
        | 
     
     
      
        
       | 
      
       Weiterführende bzw. vertiefende Vorlesungen: 
       Parallele Algorithmen II
       
        
       Parallele und verteilte Programmierung 
       Effiziente Algorithmen und
       Datenstrukturen 
       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
       
        |