Seminar - Cheatsheet.pdf

Formale Sprachen und Automaten

Definition:

Mathematikbasierte Systeme zur Beschreibung und Analyse von Sprachen und Automaten. Zentral für die Theoretische Informatik, speziell zur Sprachverarbeitung und zur Untersuchung von Berechenbarkeiten.

Details:

• Formale Sprachen: Mengen von Zeichenfolgen, definiert durch formale Grammatiken.
• Automaten: Abstrakte Maschinen, die auf Eingaben reagieren, z.B. DFA (Deterministische Endliche Automaten), NFA (Nichtdeterministische Endliche Automaten) und PDA (Kellerautomaten).
• Grammatiktypen (Chomsky-Hierarchie): Typ-0 (rekursiv aufzählbar), Typ-1 (kontextsensitiv), Typ-2 (kontextfrei), Typ-3 (regulär).
• \textbf{Reguläre Ausdrücke} für reguläre Sprachen.
• \textbf{Pumping-Lemma} zur Identifikation nicht-regulärer Sprachen.

Komplexitätstheorie

Definition:

Untersuchung der Effizienz von Algorithmen bezüglich ihrer benötigten Ressourcen wie Zeit und Speicher.

Details:

• Komplexitätsklassen: P, NP, NP-komplett, NP-schwer
• Zeitkomplexität: O(f(n)), Ω(f(n)), Θ(f(n))
• Raumkomplexität
• Reduktionen und Vollständigkeit
• Polynomialzeitreduktion

Algorithmenanalyse

Definition:

Evaluation der Effizienz von Algorithmen in Bezug auf Zeit- und Platzkomplexität.

Details:

• Asymptotische Notationen: \(O(f(n))\), \(\Omega(f(n))\), \(\Theta(f(n))\)
• Best Case, Average Case, Worst Case Analyse
• Wichtige Klassen: \(P\), \(NP\), \(NP\)-vollständig, \(NP\)-schwer
• Divide and Conquer, Dynamic Programming und Greedy-Algorithmen
• Amortisierte Analyse: Durchschnittliche Kosten über eine Sequenz von Operationen
• Analyse von Rekursionsgleichungen mittels Master-Theorem

Objektorientierte Programmierung

Definition:

Konzepte und Paradigmen zur Modellierung und Entwicklung von Software mithilfe von Objekten.

Details:

• Klassen und Objekte: Klasse = Bauplan, Objekt = Instanz
• Kapselung: Zugangskontrolle durch public/private/protected
• Vererbung: Ableitung von Klassen \rightarrow Wiederverwendbarkeit
• Polymorphie: Methoden können überladen/überschrieben werden
• Abstraktion: Reduktion der Komplexität durch Modelle

SQL-Datenbanken

Definition:

Relationale Datenbankenverwaltungssysteme, die SQL (Structured Query Language) nutzen zur Definition, Manipulation und Abfrage von Daten.

Details:

• Primärschlüssel (Primary Key): Eindeutige Identifikation jeder Zeile in einer Tabelle.
• Fremdschlüssel (Foreign Key): Verknüpft Zeilen zwischen Tabellen.
• Normalisierung: Prozess zur Strukturierung einer Datenbank, um Redundanz zu minimieren.
• Wichtige SQL-Befehle:
  • SELECT: Daten abfragen.
  • INSERT: Daten einfügen.
  • UPDATE: Daten aktualisieren.
  • DELETE: Daten löschen.
• Anfragen mit Bedingungen: SELECT ... FROM ... WHERE ...
• Joins: Tabellen zusammenführen, z.B. INNER JOIN, LEFT JOIN.

Entwurfsmuster

Definition:

Wiederverwendbare Lösung für häufig auftretende Probleme in der Softwareentwicklung.

Details:

• Erleichtern Kommunikation zwischen Entwicklern.
• Unterteilen in Erzeugungsmuster, Strukturmuster und Verhaltensmuster.
• Beispiele: Singleton, Factory, Observer.
• Reduzieren Komplexität und erhöhen Wartbarkeit des Codes.

Maschinelles Lernen

Definition:

Ein Teilgebiet der künstlichen Intelligenz, bei dem Algorithmen aus Daten lernen, ohne explizit programmiert zu werden.

Details:

• Arten: überwachtes Lernen, unüberwachtes Lernen, bestärkendes Lernen
• Wichtige Modelle: Entscheidungsbäume, Neuronale Netze, Support Vector Machines
• Grundlage: Training mit einem Datensatz, Validierung und Testen
• Wichtige Begriffe: Trainingsdaten, Testdaten, Validierungsdaten
• Fehlermetriken: Mean Squared Error, Accuracy, Precision, Recall
• Verfahren: Gradient Descent, Backpropagation
• Wichtige Bibliotheken: TensorFlow, PyTorch, Scikit-Learn

Künstliche Neuronale Netze

Definition:

Künstliche Neuronale Netze (KNN) sind Modelle der Informatik, die auf das Verhalten von biologischen neuronalen Netzen basieren, genutzt für maschinelles Lernen und Künstliche Intelligenz.

Details:

• Bestehen aus Schichten: Eingabeschicht, verborgene Schichten, Ausgabeschicht
• Jeder Knoten (Neuron) berechnet eine gewichtete Summe der Eingaben und wendet eine Aktivierungsfunktion an
• Häufige Aktivierungsfunktionen: Sigmoid, ReLU, Tanh
• Training durch Anpassung der Gewichte mittels Backpropagation und Optimierungsalgorithmen (z.B. Gradient Descent)
• KNN-Arten: Feedforward-Netze, Rekurrente Netze, Convolutional Neural Networks (CNN)