• 31.03.09: Ergebnisse der Klausur vom 26.03.09 (die mit * gekennzeichneten Teilnehmer waren nicht über das ZPA angemeldet)
  

        

 

• 09.02.09: Die Liste der zur Klausur zugelassenen Bachelor-Studenten kann hier eingesehen werden.
• 09.02.09: Ein Fragenkatalog zur Klausur kann hier heruntergeladen werden.
• 02.02.09: Die Klausur aus dem WS 07/08 kann hier heruntergeladen werden.
• 30.01.09: Zusätzlich zur Bachelorklausur wird am 16.02.09 parallel eine weitere Präsenzübung angeboten, in der Studierende, die bislang nicht die Zulassung zur Bachelorklausur erhalten haben, die Möglichkeit bekommen, diese noch für die Nachholklausur zu erlangen. Dieser Termin gilt auch für Studierende, die bei der 2. Präsenzübung erkrankt waren. Es wird für sie also keine mündliche Prüfung geben. Es sind 40% der Punkte dieser Präsenzübung nötig, um die Klausurzulassung zu erhalten. Die alten Präsenzübungen sind hierbei irrelevant. Thema wird sowohl Berechnbarkeit als auch Komplexität sein.
• 30.01.09: Ergebnisse der 2. Präsenzübung

 

• 16.12.08: Ergebnisse der 1. Präsenzübung 

     

• 10.12.08: Hier die Musterlösung zu Aufgabe 3b von Übungsblatt 7
  
• 08.12.08: Hier finden Sie die Präsenzübung des letzten Jahres

Es wird zwei Präsenzübungen am 12.12.2008 (zur Vorlesungszeit) und am 27.01.2009 (ebenfalls zur Vorlesungszeit) geben. Die Bachelor-/Vordiplomklausur wird am 16.02.2009 und die Nachschreibeklausur am 26.03.2009 stattfinden. Die Zeiten werden noch bekanntgegeben.

Die Sprechstunden der Assistenten sind zu folgenden Zeiten:

Welche Probleme kann man mit dem Computer lösen? Und welche Probleme kann man effizient lösen? - Das sind die Fragestellungen, um die es in dieser Vorlesung geht. Wir versuchen diese Fragen mit mathematischen Methoden zu beantworten. Dazu müssen wir zunächst Begriffe wie Problem, Computer und Effizienz modellieren. Anschließend werden wir verblüffend klare und weitgehende Aussagen über die (effiziente) Lösbarkeit von Problemen auf Rechnern machen können. Grundlage der Vorlesung sind mathematische Modelle und Methoden. Der Bezug zu realistischen Computern und praktischen Problemen wird aber klar herausgearbeitet. Ein Highlight der Vorlesung ist die NP-Vollständigkeitstheorie, deren Auswirkung auf Theorie und Praxis wohl kaum überschätzt werden kann. Im Einzelnen gliedert sich die Vorlesung wie folgt:

 

Teil 1: Berechenbarkeit

• 1.1 Modellierung von Problemen
• 1.2 Computermodelle
• 1.3 Nicht rekursive Probleme
• 1.4 Semi-Entscheidbarkeit und Rekursive Aufzählbarkeit
• 1.5 Eigenschaften rekursiver und rekursiv aufzählbarer Sprachen
• 1.6 Die Technik der Reduktion
• 1.7 Klassische Probleme aus der Rekursionstheorie
• 1.8 Mächtigkeit von Programmiersprachen

Teil 2: Komplexität

 

 

Ein Skript zur Volesung kann hier heruntergeladen werden.

 

Die folgenden Bücher eignen sich als zusätzliche Literatur und stehen in der Informatikbibliothek zur Verfügung.