Vorlesung Informatik 3 Einführung in die Theoretische Informatik (01 – Einleitung)Prof. Dr. Th. Ottmann
Vorlesung Informatik 3 Einführung in die Theoretische Informatik (01 – Einleitung)
Prof. Dr. Th. Ottmann
Organisatorisches
Vorlesung: Jeweils montags, von 11 – 13 Uhr und mittwochs, von 9 – 11 Uhr
Übungen: wöchentl. zu versch. Terminen (4 Gruppen), Assistent: Dr. W. Hürst
Dienstags, 9 – 11 Uhr (2 Gruppen) Dienstags, 14 – 16 Uhr Freitags, 11 – 13 Uhr
Anmeldung über Web-Formular (Link in CampusOnline unter „News“ auf der Startseite der Vorlesung) ab sofort bis spätestens Donnerstag, 29.10.05
Weitere Infos: Siehe
Infoblatt zu CampusOnline (Anmeldung etc.) und
Infoblatt zum Vorlesungs-/Übungsbetrieb (Termine, Prüfungsvorraussetzungen etc.)
http://ad.informatik.uni-freiburg.de/lehre/ws0506/info3/
Die nächsten Termine
Mo 24.10. 11 – 13 Uhr, 1. Vorlesung, HS 026
Mi 26.10. Keine Vorlesung (Eröffnung des akademischen Jahres)
Mo 31.10. 11 – 13 Uhr, 2. Vorlesung, Wiedergabe der Aufzeichnung vom Mo 24.10., 16 – 18 Uhr, HS 106, MM-Raum
Mi 2. 11. 9 – 11 Uhr, 3. Vorlesung, Wiedergabe der Aufzeichnung vom Do 27.10., 13 – 15 Uhr, HS 106 MM-Raum
Mo 7.11. 11 – 13 Uhr 4. Vorlesung
Mi 9.11. 9 – 11 Uhr 5. Vorlesung
…..usw.
Literatur
U. Schöning: Theoretische Informatik kurz gefasst, Spektrum Akademischer Verlag (März 2001)
M. Sipser: Introduction to the Theory of Computation, Second Edition, Course Technology (2005)
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, Addison Wesley Publishing Company (2001)
Deutsche Übersetzung: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium (2002)
Katrin Erk, Lutz Priese: Theoretische Informatik, Springer, Berlin (2001)
Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik, 3. überarbeitete und erweiterte Auflage 2004XIV + 405 Seiten, € 29,90, ISBN 3-528-23147-5 Vieweg Verlag
U.v.a
Themen der Vorlesung
Antworten auf grundsätzliche Fragen, wie z.B.
Was kann man überhaupt (nicht) mit Computer lösen?
Wie groß ist der Aufwand zum Lösen von Problemen? Kann die Problemlösung am Aufwand scheitern?
Was sind sinnvolle mathematische Modelle von Automaten und Computern? Für welche Zwecke eignet sich welches Modell?
Welche Alternativen zur Modellierung von Rechenvorgängen gibt es?
Einige Antworten der Vorlesung
Theorie der Berechenbarkeit: Es gibt nicht berechenbare Funktionen; es gibt überhaupt viel mehr Funktionen als Algorithmen
Komplexitätstheorie: Es gibt Probleme, bei denen die Zeit zum Berechnen einer Lösung nur polynomiell von der Problemgröße abhängt und andere, zu deren Lösung (vermutlich) kein in Polynomzeit ausführbarer Algorithmus existiert
Automatentheorie: Es gibt eine Hierarchie von immer leistungsfähigeren Automaten, endliche Automaten, Pushdown- Automaten, Register- und Turingmaschinen
Theorie der formalen Sprachen: Es gibt eine Hierarchie Formaler Grammatiken, mit denen man immer größere Klassen von Sprachen erzeugen kann
Kurze Historie der Berechenbarkeitstheorie
~ 800 Ibn Musa Al-Chwarismi (persischer Mathematiker und Astronom) schreibt Lehrbuch über as Lösen von algebraischen Gleichungen
~ 1300 Raimundus Lullus (katalanischer Philosoph) sucht in Ars Magna Methode zur Lösung mathematischer Probleme
1888 Dedekind: primitiv rekursive Funktionen
1928 Ackermann: berechenbare, nicht primitiv rekursive Funktion
Bis 1931 Allgemeine Ansicht: Jedes hinreichend genau formulierte mathematische Problem kann gelöst werden. Hilbert sucht nach allgemeinem Lösungsverfahren.
1931 Gödel: In jedem hinreichend ausdrucksfähigen formalen System gibt es wahre Sätze, die nicht mit Hilfe eines Algorithmus hergeleitet werden können (Gödelscher Unvollständigkeitssatz). Erste Algorithmenpräzisierung
Um 1936 Verschiedene Präzisierungen des Algorithmenbegriffs. λ-Kalkül (Church), μ-rekursive Funktionen (Kleene), (allg.) rekursive Funktionen (Gödel, Herbrand), Turing-Maschinen (Turing)
Beispiel: Existenz nicht berechenbarer Funktionen
Unabhängig vom Rechnermodell gilt:
Algorithmen werden durch Programme beschrieben
Programme sind Texte endlicher Länge über einem endlichen Alphabet
Alle gültigen Programme lassen sich abzählen (mit einer Nummer identifizieren): P0, P1, P2, P3, P4, P5, ….
Satz: Es gibt mehr Funktionen f : N → N als berechnende Programme
Beweis: Technik: Diagonalisierung
Diagonalisierung
0 1 2 3 4 5 6 …. n ….
fP0
fP1
fP2
fP3
fP4
..
fd
Beweistechniken
Diagonal-/ Schubfachschluss
Direkter Beweis: Beweise die Aussage durch explizite Prüfung aller denkbaren Fälle
Indirekter Beweis: Nehme das Gegenteil der Behauptung an und zeige, dass das zu einem Widerspruch führt
Vollständige (strukturelle) Induktion: Zeige, dass Aussage
für gegebene Anfangs Strukturen gilt
sie richtig bleibt für (rekursiv aus einfacheren Bestandteilen) erzeugte Strukturen
Beispiel eines direkten Beweises
Satz: In jeder binären 2x2 Matrix kommen höchstens 3 der 4 möglichen Bitvektoren der Länge 2 vor.
Beispiel eines indirekten Beweises
Satz: 2 ist keine rationale Zahl, d.h. 2 kann man nicht als Bruch m/n darstellen.
Beispiel eines Induktionsbeweises
Satz: Für alle natürlichen Zahlen n ≥ 4 gilt: 2n ≥ n2
Beispiel für eine strukturelle Induktion
Sei P die wie folgt definierte Teilmenge der natürlichen Zahlen
3 P und 17 P
Wenn n P, dann sind auch die Zahlen 2n + 1 und 3n + 2 in P.
Satz: Alle Zahlen in P sind ungerade
Schubfachschluss - Zählargument
Satz: Für alle natürlichen Zahlen n ≥ 1 gilt: Die Zeilen und Spaltenvektoren einer n x n Bit-Matrix schöpfen nicht alle möglichem n-Bit Vektoren aus
Diagonalschluss
Satz: Für alle n ≥ 1 und jede beliebige n x n Bitmatrix M =(bij), 1 ≤ i, j ≤ n, gilt: Der n – Bit – Vektor V = (¬b11, ¬ b22, …, ¬ bnn) tritt weder als Zeilen- noch als Spaltenvektor in M auf.
Dabei bezeichnet ¬b für ein Bit b {0,1} das Bit:
¬b = 0, falls b = 1, ¬b = 1, falls b = 0
Wiederholung einiger Begriffe aus der diskreten Mathematik
Äquivalenzrelationen:
Eine zweistellige Relation heißt Äquivalenzrelation, wenn sie reflexiv, transitiv und symmetrisch ist
Grundbegriffe für Graphen
Sei V eine Menge von Knoten, G = (V, E) mit E V x V heißt Graph mit Knotenmenge V und Kantenmenge E.
Gerichteter, ungerichteter Graph
Pfad, Zyklus
Zusammenhängender, zyklischer, azyklischer Graph
Bäume, Wurzel, Blätter
Alphabete, Worte, Sprachen
Alphabet: Endliche Menge von Symbolen
Beispiele: = {0, 1}, = {a, b, c, …., x, y, z}
Wort (Zeichenreihe): Jede endliche Aneinanderreihung von Symbolen des zugrunde liegenden Alphabets inklusive des leeren Wortes ε.
Comments