Theoretische Informatik (Vorlesung 2)

Klausur

• 10 Aufgaben werden gestellt
• aber nur 5-6 müssen bearbeitet werden
• Ob Unterlagen mitgenommen werden dürfen, gibt der Professor noch bekannt.
• Bereich 1-4 sind für die Vorlesung (und Klausur) interessant.
• Schwerpunkt Formale Sprachen.

Definition

• „Die Theoretische Informatik beschäftigt sich mit der Abstraktion, Modellbildung und grundlegenden Fragestellungen, die mit der Struktur, Verarbeitung, Übertragung und Wiedergabe von Informationen in Zusammenhang stehen.“ (Wikipedia)
• Probleme zusammenführen und dann ganze Problemklassen lösen

Dokumente

• Skripte von Dr. Lange werden als Referenz genutzt.

Aufgabenbereiche der Theoretischen Informatik

1. Automatentheorie:
   • Welcher Probleme können mit welchen Automaten gelöst werden?
   • So einfach wie möglich komplexe Sachverhalte lösen können.
   • Deterministische und nicht deterministische endliche Automaten
   • Kellerautomaten
   • Linear beschränkte Automaten
   • Turingmaschinen
2. Formale Sprachen: 
   • Sei Σ eine Menge. Wir nennen Σ auch Alphabet ( ∑={0,1}, ∑={a,b,…, z,A,B,…Z} )
   • Mit Σ* = {W₁,W₂,..W_n ∈ ∑ } ∪ {Ø} bezeichnen wir die Menge aller Worte über Σ.
   • Für Σ = {0,1} ist Σ* die Menge aller Bitstrings
   • Eine Teilmenge L ⊆ Σ* nennen wir eine Sprache
   • Viele Probleme lassen sich auf folgende Fragestellung reduzieren:
     • Wortproblem L⊆ Σ*
     • gegeben: Ein Wort W ∈ Σ*
     • Frage: Gilt W ∈ L?
     • Für welche Sprachen lösen welche Automaten das Wortproblem?
3. Berechenbarkeit:
   • Welche Probleme sind lösbar, welche Funktionen sind berechenbar?
   • Es gibt Funktionen, die nicht berechenbar sind.
4. Komplexitiätstheorie:
   • Nicht nur interessant: Berechenbarkeit, sondern auch: wie effizient kann etwas berechnet werden?
   • Ähnlich schwere Probleme werden in Komplexitätsklassen zusammengefasst.
5. Kryptologie
   • Wie werden Inhalte verschlüsselt?
   • Wie wird eine Verschlüsselung gebrochen?
6. Informationstheorie
   • Wie viel Information steckt in einem Text?
   • Wichtig für die Kryptographie: Enthält ein verschlüsselter Text noch Informationen über den ursprünglichen Inhalt?
   • Wichtig für Komprimierungsalgorithmen.
7. Algorithmik
8. Logik und Datenbanktheorie

Allgemein

• Ein Verfahren gilt sicher, wenn einem Angreifer das Verfahren bekannt ist, aber der Schlüssel nicht brechbar und der Code somit nicht knackbar.
• Je länger der verschlüsselte Text ist, desto wahrscheinlicher ist es, dass der Text geknackt wird

1. Kryptographie

1.1 CAESAR – Cipher

• Wir identifizieren die 26 Buchstaben des Alphabets in Zahlen.
• Gerechnet wird Modulo 26, d.h. x,y ∈ { 0,1,.., 25}
• es gilt x+y mod 26 = { x+y falls x+y < 26 || x+y -26 falls x+y >=26 }

A	B	C	D	E	F	..	Z
0	1	2	3	4	5	..	25

• Verschlüsselung:
  • Für einen Schlüssel k ∈ { 0, 1, .. , 25 } und ein Wort x = x₁… x_n mit x₁, …, x_n ∈ { 0,1 .. 25 } sei f(x,k) = (x₁+k) mod 26 ….. ( x_n+k) mod 26
• Entschlüsselung:
  • Entschlüsselung mit – k
• Beispiel: 
  • Für CAECAR = 2 0 4 2 0 17 wird der Schlüssel k=3 benutzt
  • Ist die Verschlüsselung = 5 3 7 5 3 20 = F D H F D U
• Sicherheit:
  • Das Verfahren ist unsicher, da es nur 26 verschiedene Schlüssel gibt
  • Einen Schlüssel > 26 ist ineffektiv, da z.B. 27 wieder 1 ist
• Verbesserung
  • Unterschiedliche Abstände bzw. Auswahlen für die einzelnen Zeichen
  • Bijektion muss gewährleistet sein ( A → B und B → A)
  • Maximale Anzahl der Schlüssel wird dadurch zu 26! = 2^88
• Brute Force ist sinnlos:
  • 2^88 Sekunden = 2^63 Jahre
  • Alter der Erde = 2^30 Jahre
  • Alter des Universums = 2^34 Jahre
  • Die Größe des Schlüsselraumes ist für ein Durchprobieren viel zu groß.
• Lösungswege:
  • Relative Buchstabenverteilungen in sinnvollen deutschen Texten:
    • E = 17.8%
    • N = 9.78%
    • I = 7.55 %
    • […]
    • X = 0.03 %
    • Q = 0.02 %
  • Selbst wenn nur 30% aller Zeichen geknackt werden können, ist der Sinn in einem Text weitestgehend verständlich geworden.

1.2 Zwei weitere Beispiele

• Definition 1.1: Ein Graph g=(V,E) besteht aus
  1. einer endlichen Menge V ( Knoten )
  2. einer Teilmenge E ⊆ Potenzmenge (P₂)  (V) der zweielementigen Teilmengen von V (Kanten)
  • Bsp.:
    • g = ( V, E) mit V = { 1,2,3,4} und E = {{ 1,2 }, {1,3}, {2,4}, {2,3}, {3,4}}
• Definition 1.2:
  • Sei g = (V, E) ein Graph. Eine Clique ist eine Teilmenge C ⊆ V so, dass je zwei Knoten aus C durch eine Kante verbinden sind.
    • Cliquen der Größe 2: {1,2}, {2,4}, {1,3}, {3,4}, {2,3}
    • Cliquen der Größe 3:  {1,2,3}, {3,2,4}
    • Keine Clique:  {1,2,4} (1 und 4 sind durch keine Kante verbunden)
• Problem Clique:
  • Eingabe: Graph g=(V,E)
  • Ausgabe: Eine größte Clique C ⊆ V
  • Sogenannte Optimierungsprobleme
• Problem Clique (modifiziert)
  • Eingabe: Graph g=(V,E) und eine Zahl k ∈ ℕ
  • Frage: Gibt es in G eine Clique der Größe k
  • Sogenannte Entscheidungsprobleme mit den zulässigen Antworten „ja“ und „nein“

Literaturvorschläge

1. „Mopcraft: Theoretische Informatik und ..“ bzw. Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit ( Hopfcroft )