Stoff - Theoretische Informatik

1. Definitionen, Begriffe, Resultate, Zusammenhänge

2. Verfahren (wesentlicher Teil der Klausur)

• ( aufzählbare Sprachen
• Halteproblem )
  

• Umwandlung Zahlendarstellung
• nicht det. Programme
• schnelle Suche mit DEAs
• Potenzmengenkonstruktion
• DEA -> regulärer Ausdruck
• Anwendung: Pumping Lemma für reguläre Sprachen
• Umwandlung kontextfreie Grammatik -> Chomsky Normalform
• CYK Algorithmus

3. Beweise (für die 1 vor dem Komma erforderlich)

• ohne Beweise 2,0 möglich
• bei technisch aufwändigen Beweisen reicht Beweisidee

Weiterhin:

• Keine Definitionen voraussichtlich
• Kein Multiple Choice

Thx2 Andi!