| 
      
       Dozent: 
       
       Prof. Dr. Angelika Steger
       
       
        | 
     
     
      
        
       | 
      
       Bereich: 
       
       4 SWS Vorlesung im 
       Bereich Informatik III (Theoretische Informatik) 
       Wahlpflichtvorlesung
       im Gebiet Komplexität
       
       
        | 
     
     
      
        
       | 
      
       Zeit und Ort: 
       
       Di. 8:30 - 10:00 (S1128) 
       Fr. 9:15 - 11:00  (1100) 
       Beginn: 4.5.99 
       
       
        | 
     
     
      
        
       | 
      
       
       
       Übung: 
       2 SWS Übung zur Vorlesung 
       Termin: Mo 12:15 - 13:45, Raum S2229    
       Übungsleitung: Jens Ernst
  
       Übungsschein: Einen Schein erhält, wer
       mindestens 40% der Punkte zu den Hausaufgaben erreicht und
       erfolgreich an der Semestralprüfung teilnimmt.
       
       
        | 
     
     
      
        
       | 
      
       Hörerkreis: 
       
       Studierende im Hauptstudium der Informatik 
       Studierende mit Nebenfach Informatik
       
       
        | 
     
     
      
        
       | 
      
       Voraussetzungen: 
       
       Stoff des Informatik Grundstudiums 
       Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
       
       
        | 
     
     
      
        
       | 
      
       Empfehlenswert für: 
       
       Erweiterte Kenntnisse im Bereich Komplexität
       
       
        | 
     
     
      
        
       | 
      
       Inhalt: 
       
       In der Vorlesung wird im wesentlichen der Stoff des
       Buches Introduction to the Theory of Complexity
       von Bovet und Crescenzi behandelt.
       
       
        | 
     
     
      
        
       | 
      
       Weiterführende bzw. verwandte Vorlesungen: 
       
       
       
        | 
     
     
      
        
       | 
      
       Skript: 
       
       Kein Skript.
       Aber einige Slides, die in der Vorlesung aufgelegt wurden: 
       Optimierungsprobleme I  
       Optimierungsprobleme II  
       Probabilistisch verifizierbare Beweise  
       
       
        | 
     
     
      
        
       | 
      
       Literatur: 
       
       
        - 
         Balczar, Daz, Gabarr:
        
 - 
         Structural Complexity I
 
         EATCS Monographs, Springer-Verlag.
         - 
         Daniel Pierre Bovet, Pierluigi Crescenzi:
        
 - 
         Introduction to the Theory of Complexity
 
         Prentice Hall Verlag.
         - 
         Rüdiger Reischuk:
        
 - 
         Einführung in die Komplexitätstheorie
 
         Teubner-Verlag.
         
       
       
        | 
     
     
      
        
       | 
      
       Sprechstunde: 
       
       siehe hier
       
       
        |