| 
      
       Dozent: 
       Prof. Dr. Angelika Steger
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik) 
       Sonstige prüfbare Vorlesung
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
	Mi 10:15 - 11:45, Hörsaal S2229 
	Beginn: 7. Mai
	
        | 
     
     
      
        
       | 
      
       Ü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/Komplexität
       
        | 
     
     
      
        
       | 
      
       Inhalt: 
       Eine der spektakulärsten Fortschritte der theoretischen Informatik
       in den letzten Jahren ist eine neue Charakterisierung der Klasse NP
       durch probabilistisch verifizierbarer Beweise und die dadurch initierten
       rasanten Fortschritte bei der Klassifizierung der Approximierbarkeit
       kombinatorischer Optimierungsprobleme. 
       In dieser Vorlesung wollen wir die mit  diesem Thema
       zusammenhängenden Aussagen und Ergebnisse vorstellen. Einen
       einführenden Artikel hierzu finden Sie
       hier
       (aus: Highlights der Informatik, Ingo Wegener (Ed.),
       Springer-Verlag, 1996).
       
        | 
     
     
      
        
       | 
      
       Skript: 
       Kein Skript, aber so etwas ähnliches. Details in der Vorlesung.
       
        | 
     
     
      
        
       | 
      
       Literatur: 
       Genaue Referenzen werden in der Vorlesung bekannt
       gegeben.
       
        | 
     
     
      
        
       | 
      
       Sprechstunde: 
       siehe hier!
       
        |