Mitschrift zum 1. Teil der Vorlesung Berechenbarkeit (Wintersemester 2004/2005) bei Prof. Dr. Martin Grohe, zusammen mit Jan Bretschneider
Die Mitschrift enthält nur die Themen der ersten Semesterhälfte (bis zum 6. Dezember 2004): Berechenbare Funktionen, Nummerierung berechenbarer Funktionen, universelle Programme, entscheidbare und aufzählbare Mengen, der Kleene’sche Fixpunktsatz, die Struktur rekursiv aufzählbarer Mengen unter many-one-Reduktionen, relative Berechenbarkeit und Turingreduktionen, sowie die arithmetische Hierarchie.
Vielleicht möchte jemand diese Mitschrift irgendwann um den 2. Teil ergänzen und vervollständigen – dafür kann man hier die LATEX-Quellen herunterladen.
Dateien
Übungen mit selbst erstellten Lösungen zur Vorlesung Theoretische Informatik 3 (Sommersemester 2003) bei Dr. Till Nierhoff
In den Übungen werden Aufgaben zu RAM, SAT, bipartiten Graphen, Vertex Cover, Bin Packing, Clique, Independent Set, 3SAT, DHC, Knapsack, NTM, Task Scheduling, NP-Vollständigkeit, Approximationsalgorithmen, MaxCut und Machine Scheduling gelöst.
Dateien
Mitschrift zur Vorlesung Theoretische Informatik 2 (Wintersemester 2002/2003) bei Dr. Till Nierhoff, sowie Übungen mit selbst erstellten Lösungen
In den Übungen werden Aufgaben zu Turingmaschinen, Groß-O-Notation, rekursive Aufzählbarkeit, Reduktion, Chomsky-Grammatiken, DFA, NFA und Graphentheorie gelöst.
Die Mitschrift ist angereichert mit ein paar Beispielen aus der Übung und Ergänzungen aus Sekundärliteratur, sowie Literaturangaben. Ich möchte mich an dieser Stelle herzlich bei all denen bedanken, die mir geduldig Woche für Woche Verbesserungsvorschläge geschickt und meine Fehler verbessert haben.
Themen der Mitschrift sind Turingmaschinen, Entscheidbarkeit, Chomsky-Grammatiken, reguläre Sprachen, kontextfreie Sprachen, Graphen, Greedy-Algorithmen, dynamische Programmierung und eine Einführung in die Graphentheorie.
Dateien
letzte Kommentare