Ruhr-Universität Bochum zum Inhalt Startseite der RUB pix
Startseite Uni Startseite
Überblick Uni Überblick
A-Z Uni A-Z
Suche Uni Suche
Kontakt Uni Kontakt

pix
 
Das Siegel
Naturwissenschaften Ingenieurwissenschaften Geisteswissenschaften Medizinische Einrichtungen Zentrale Einrichtungen
pix
 
pix Lehrstuhl Mathematik & Informatik
Komplexitätstheorie SS 08
 
 
 
Unser Angebot: Mitarbeiter | Forschung | Lehre | Abschlussarbeiten   
pix
Startseite » Lehre » Komplexitätstheorie SS 08
LV-NR 150 242
Veranstaltung Komplexitätstheorie
4.0 std. NA 1/64 Di 10.00-12.00  
NA 1/64 Do 10.00-12.00    
Dozent(inn)en Simon, H. U.
Übung Kallweit, M.

2.0 std.
NA 1/64 Di 08.30-10:00   

Einmalige Sonderübung am Do., 10.4.08 von 08.30-10.00 in NA 2/24    

    Voraussetzungen 
   
Elementare Grundkenntnisse zu der Thematik, wie sie etwa in der Vorlesung "Theoretische Informatik" vermittelt werden, werden weitgehend vorausgesetzt. (Diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden relativ rasch im Selbststudium herstellbar.)

    Kommentar 
   
Die Komplexitätstheorie stellt sich die Aufgabe, Berechnungsprobleme anhand des zu ihrer Lösung erforderlichen Verbrauchs an Rechenzeit oder Speicherplatz in Klassen einzuordnen. Probleme von (annähernd) gleicher Komplexität landen dabei in derselben Klasse. Gegenstand der Vorlesung sind hauptsächlich die Komplexitätsklassen zwischen P und PSpace wie zum Beispiel die Klasse NP. Hierbei bezeichnet P die Klasse der in Polynomialzeit und PSpace die Klasse der mit polynomiell beschränktem Speicherplatz erkennbaren Sprachen. NP ist das nicht-deterministische Pendant zu P und bezeichnet die Klasse der nichtdeterministisch in Polynomialzeit erkennbaren Sprachen. Diese Klasse enthält eine Vielzahl von grundlegenden Problemen aus verschiedenen Wissenschaftsbereichen. Eine der wichtigsten ungeklärten Fragen der theoretischen Informatik ist, ob die Klassen P und NP überhaupt verschieden sind. In der Vorlesung behandeln wir eingehend die NP-Vollständigkeitstheorie, die sich mit schwersten Problemen innerhalb NP beschäftigt. Weitere Themen sind die polynomielle Hierachie von Stockmeyer, schwerste Probleme in PSpace und schliesslich randomisierte Algorithmen bzw. Approximationsalgorithmen und die jeweils dazu passenden Komplexitaetsklassen.

    Literatur
   
Zur Theorie der NP-Vollständigkeit empfehle ich den Klassiker: Garey and Johnson, Computers and Intractability. (A Guide to the Theorie of NP-Completeness), Freeman and Company. Zur Theorie der Approximationsalgorithmen empfehle ich das Buch "Complexity and Approximation" von Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela und Protasi, Springer. Weiterhin kann das Buch "Complexity Theory" von Wegener, Springer, empfohlen werden.



Materialien


Skriptum

Woche 1 bis 7:   PDF  
Juni:   Abschnitte 1.4,  3,  6.3,  6.4 aus dem Buch "Complexity and Approximation" von Ausiello, Crescenzi, Kann, Marchetti-Spaccamela, Protasi
Hinweis: Das Buch steht in der Fakultätsbibliothek bereit
Juli:   Abschnitt 8 aus dem Buch "Complexity and Approximation" von Ausiello, Crescenzi, Kann, Marchetti-Spaccamela, Protasi
Hinweis: Das Buch steht in der Fakultätsbibliothek bereit
        Seiten 1-14 Aus der Arbeit "Probabilistically Checkable Proofs and their Consequences for Approximation Algorithms" von Hougardy, Proemel, Steger
Hinweis: Die Arbeit kann hier als PDF heruntergeladen werden




Übungsaufgaben

Blatt 01:   PDF   PS
Blatt 02:   PDF   PS
Blatt 03:   PDF   PS
Blatt 04:   PDF   PS
Blatt 05:   PDF   PS
Blatt 06:   PDF   PS
Blatt 07:   PDF   PS
Blatt 08:   PDF   PS
Blatt 09:   PDF   PS
Blatt 10:   PDF   PS
Blatt 11:   PDF   PS
Blatt 12:   PDF   PS

 
 
Zum Seitenanfang   Seitenanfang | Diese Seite drucken
Letzte Änderung: 09.04.2008 | Ansprechpartner: Webmaster