| 
      
       Dozenten: 
       Prof. Dr. Ernst W. Mayr 
       Prof. Dr. Angelika Steger
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik) 
       Sonstige prüfbare Vorlesung
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
	Mi 16:00 - 17:30, Hörsaal S2229 
	Beginn: 6. November
	
        | 
     
     
      
        
       | 
      
       Übung: 
       keine Übung
       
        | 
     
     
      
        
       | 
      
       Hörerkreis: 
       Studierende im Hauptstudium der Informatik
       Studierende im Hauptstudium der Mathematik mit Nebenfach Informatik
        
        | 
     
     
      
        
       | 
      
       Voraussetzungen: 
       Solide Grundkenntnisse der Theoretischen Informatik
       
        | 
     
     
      
        
       | 
      
       Empfehlenswert für: 
       Vertiefung im Bereich Algorithmen
       
        | 
     
     
      
        
       | 
      
       Inhalt: 
       Die Verwendung tiefliegender Resultate aus der Kombinatorik
       hat in den letzten Jahren zu einigen
       schönen und verblüffenden Ergebnissen
       in der theoretischen Informatik geführt.
       Typische Beispiele hierfür sind
       Lovász Local Lemma und Szemerédi's Regularity Lemma.
       In ihrer ursprünglichen Form waren beide reine
       Existenzaussagen, mit entsprechend geringer Bedeutung für die
       Informatik. Dies änderte sich mit der Veröffentlichung
       einer algorithmischen Version durch Beck (1991) bzw.
       Alon, Duke, Lefmann, Rödl, Yuster (1992).
       In dieser Vorlesung wollen wir uns Aussage, Bedeutung und Anwendungen
       dieser beiden Lemmata erarbeiten.       
       
        | 
     
     
      
        
       | 
      
       Skript: 
       Kein Skript, die Vorlesung hält sich eng an Originalarbeiten.
       
        | 
     
     
      
        
       | 
      
       Literatur: 
       Originalarbeiten. Genauer Referenzen werden in der Vorlesung
       bekannt gegeben.
       
        | 
     
     
      
        
       | 
      
       Sprechstunde: 
       siehe hier
       |