Theorie der Programmierung - Cheatsheet

Chomsky-Hierarchie

Definition:

Hierarchie formaler Grammatiken, unterteilt in vier Klassen nach zunehmender Ausdruckskraft.

Details:

• Typ-0: Rekursiv aufzählbare Sprachen
• Typ-1: Kontext-sensitive Sprachen
• Typ-2: Kontextfreie Sprachen
• Typ-3: Reguläre Sprachen
• Enthält jede Klasse die darüber liegende Klasse (Inklusionsbeziehung)
• Wichtig für die Beschreibung von Sprachklassen und Automaten

Turingmaschinen und das Halteproblem

Definition:

Turingmaschine: Berechenbarkeitsmodell, untersucht algorithmische Probleme. Halteproblem: Feststellen, ob ein Programm auf Eingabe jemals hält.

Details:

• Turingmaschine: Besteht aus Eingabeband, Zustandsregister, Übergangsfunktion, Lese-Schreibkopf.
• Formale Beschreibung: \(M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})\)
• Halteproblem: Entscheidungsproblem, ob Turingmaschine M bei Eingabe w hält (stoppt) oder nicht.
• Unentscheidbarkeit: Halteproblem ist nachweislich unentscheidbar (es existiert kein Algorithmus, der das für alle Eingaben korrekt entscheidet).
• Reduktionsbeweis: Nutzt diagonales Argument oder Reduktion auf das Lügner-Paradoxon.
• Folge: Nicht alle Probleme sind algorithmisch lösbar, Grenzen der Berechenbarkeit.

Komplexitätsklassen P und NP

Definition:

P umfasst Entscheidungsprobleme, die auf einer deterministischen Turingmaschine in polynomialer Zeit gelöst werden können. NP umfasst Entscheidungsprobleme, bei denen eine Lösung in polynomialer Zeit auf einer deterministischen Turingmaschine verifiziert werden kann.

Details:

• P: Menge von Problemen, die in polynomialer Zeit (poly-time) lösbar sind.
• NP: Menge von Problemen, deren Lösung in polynomialer Zeit verifizierbar ist.
• Es gilt: P \( \subseteq \) NP.
• Unklarheit, ob P = NP (das P-NP-Problem).
• Bekannte NP-vollständige Probleme können benutzt werden, um die Schwierigkeit eines NP-Problems zu zeigen.
• Ein Problem ist NP-vollständig, wenn es selbst in NP ist und jedes Problem in NP polynomial auf es reduziert werden kann.

Prädikatenlogik und Unifikationsalgorithmen

Definition:

Prädikatenlogik: Erweiterung der Aussagenlogik um Quantoren und Prädikate. Unifikationsalgorithmus: Verfahren zur Bestimmung einer allgemeinsten Unifikator für Terme.

Details:

• Prädikatenlogik: Terme, Atome, Formeln
• Quantoren: Existenz (\thereexists), All (\forall)
• Unifikation: Ersetze Variablen so, dass Terme gleich werden
• Allgemeinster Unifikator (MGU): Ein minimaler Satz an Ersetzungen
• Algorithmus: Festlegen der Substitutionen bis Anpassung

Lambda-Kalkül: Alpha-, Beta- und Eta-Umwandlungen

Definition:

Lambda-Kalkül: Alpha-, Beta- und Eta-Umwandlungen - grundlegende Transformationen zur Manipulation und Vereinfachung von Lambda-Ausdrücken.

Details:

• Alpha-Umwandlung: Umbenennung von gebundenen Variablen.
• Beta-Umwandlung: Funktionenanwendung; \((\lambda x. M) N \rightarrow M[x := N]\).
• Eta-Umwandlung: Extensionalität; \(\lambda x. (M x) \rightarrow M\), falls \(x\) nicht frei in \(M\) ist.

Reguläre Ausdrücke und ihre Anwendungen

Definition:

Reguläre Ausdrücke (Regex) sind Muster, die verwendet werden, um Zeichenketten zu durchsuchen, zu bearbeiten oder zu validieren.

Details:

• Kern-Konzepte: Literale, Metazeichen, Quantoren, Zeichenklassen
• Syntaxbeispiele: . (beliebiges Zeichen), * (0 oder mehr), [^abc] (kein a, b oder c)
• Anwendungen: Pattern Matching, String-Manipulation, Such-und-Ersetz-Operationen, Validierung von Eingaben
• Integriert in viele Programmiersprachen und Tools: z.B. Python, Java, grep, sed

NP-Vollständigkeit und Polynomialzeitreduktionen

Definition:

NP-Vollständigkeit: Klasse von Problemen, die sowohl in NP liegen als auch NP-schwer sind. Ein Problem ist in NP, wenn die Lösung in polynomialer Zeit verifiziert werden kann. Polynomialzeitreduktionen: Mittel zur Transformation eines Problems in ein anderes, wobei die Transformationszeit polynomial ist.

Details:

• Ein Problem A ist NP-vollständig, wenn A in NP ist und jedes Problem in NP in polynomialer Zeit auf A reduziert werden kann.
• Verwende Polynomialzeitreduktionen (Reduktion in polynomieller Zeit), um die Komplexität eines Problems zu analysieren.
• Wenn ein NP-vollständiges Problem lösbar ist, dann sind alle Probleme in NP lösbar.
• Bekannte NP-vollständige Probleme: SAT, CLIQUE, Knotenüberdeckung.
• Verwendete Reduktionsmethoden: Karp-Reduktion, Turing-Reduktion.

Beweise und Beweiserhaltung im Lambda-Kalkül

Definition:

Beweise und Beweiserhaltung im Lambda-Kalkül betreffen die Korrektheit und Konsistenz von Ausdrücken und deren Manipulationen.

Details:

• Lambda-Kalkül: Formalismus der Funktionstheorie
• Korrektheit: Einhalten der typisierung im reduzierten Ausdruck
• Beweiserhaltung: Typen bleiben bei Reduktionsschritten erhalten
• Grundlegende Theoreme:
  • Substitutionstheorem: Erhaltung der Typkorrektheit bei Substitution
  • Reduktionstheorem: Bei Reduktion bleibt der Typ erhalten