| 
      
       Dozent: 
       
       Prof. Dr. Ernst W. Mayr
       
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       
       2 SWS Vorlesung im 
       Bereich Informatik III (Theoretische Informatik) 
       Vertiefende Vorlesung
       im Gebiet Komplexität
       
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
       
       Do 8:30 - 10:00, Hörsaal 1180 
       Beginn: 5. November
       
       
        | 
     
     
      
        
       | 
      
       
       
       Übung: 
       2 SWS Übung zur Vorlesung 
       Mi 8:30 - 10:00, Raum S2225 
       Beginn: 11. November 
       Übungsleitung: Volker Heun 
       Übungsschein: Einen Schein erhält, wer
       mindestens 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: 
       Vorlesung Komplexitätstheorie vorteilhaft, aber nicht notwendig.
       
        | 
     
     
      
        
       | 
      
       Empfehlenswert für: 
       
       Erweiterte Kenntnisse im Bereich Komplexität
       
       
        | 
     
     
      
        
       | 
      
       Inhalt: 
       Ein sehr interessantes, aber auch schwieriges Gebiet der
       Algorithmentheorie ist das Zeigen unterer Schranken für
       die Zeit- oder Platzkomplexität von Problemen. In dieser
       Vorlesung werden verschiedene bekannte Techniken zum Beweisen
       unterer Schranken vorgestellt und anhand paradigmatischer
       Beispiele veranschaulicht.
       
           - Einleitung, Übersicht
           
               - Zweck der Vorlesung
               
 - Literatur
               
 - Techniken für Untere Schranken
               
 - Modelle
               
 - Einige Notationen
           
  
            - Einige Platz- und Zeitschranken für Turingmaschinen
           
               - Eine quadratische Zeitschranke für 1-Band-TMs
               
 - Ein Gap-Theorem für kleinen deterministischen Platz
               
 - Gap-Theorem für 1-Band-Turingmaschinen
               
 - Hierarchien
               
                   - Allgemeiner Hierarchiesatz
                   
 - Zeithierarchien
                   
 - Platzhierarchie
                   
 - Nichtdeterministische Hierarchiesätze
               
  
                - Platz vs. Zeit
               
                   - 1-Band Turingmaschinen
                   
 - Ein Spiel auf Graphen
                   
 - Konstruktion von Berechnungsgraphen
               
  
             
            - Boolesche Schaltkreise
           
               - Grundlagen
               
 - Asymptotische Schranken
               
 - Probabilistische Methoden
               
                   - Die Klasse AC0
                   
 - Schaltkreise geringer Tiefe für Parität
                   
 - Håstad's untere Schranke
                   
 - Exponentielle untere Schranke für Parität
               
  
                - Eine algebraische Methode (Razborov)
           
  
            -  Zusammenfassung und Ausblick
       
  
       
        | 
     
     
      
        
       | 
      
       Weiterführende bzw. verwandte Vorlesungen: 
       
       EinfÏhrung in die KomplexitÌtstheorie
       
       
        | 
     
     
      
        
       | 
      
       Skript: 
       
       Kein Skript.
       
       
        | 
     
     
      
        
       | 
      
       Literatur: 
       
       
        - 
         K.R. Reischuk:
        
 - 
         Einfhrung in die Komplexittstheorie
 
         B.G. Teubner, 1990
         - 
         J. HÔstad:
        
 - 
         Computational limitations of small-depth circuits
 
         The MIT Press: Cambridge(MA)-London, 1987
         
       
       
        | 
     
     
      
        
       | 
      
       Sprechstunde: 
       
       siehe hier
       
       
        |