Einführung in die Informatik - Cheatsheet

Syntax und Semantik von Programmiersprachen

Definition:

Syntax: Regeln und Struktur von Programmiersprachen. Semantik: Bedeutung der Programme und Befehle.

Details:

• Syntax beschreibt die Form, wie Programme geschrieben werden müssen - z.B. Schlüsselwörter, Klammern, Operatoren.
• Semantik legt fest, was diese Programme tun - z.B. Berechnungen, Datenmanipulation.
• Formale Sprache für Syntax: Kontextfreie Grammatiken.
• Semantik kann durch mathematische Modelle wie Operational oder Denotational Semantics beschrieben werden.
• Wichtige Begriffe: Syntaxbaum (Parse Tree), Semantische Analyse.

Kontrollstrukturen: Schleifen und Bedingungen

Definition:

Kontrollstrukturen steuern den Programmablauf. Schleifen wiederholen Anweisungen, Bedingungen verzweigen ihn.

Details:

• Schleifen: for, while, do-while
• for: \texttt{for(init; condition; increment) \{ Anweisung \}}
• while: \texttt{while(Bedingung) \{ Anweisung \}}
• do-while: \texttt{do \{ Anweisung \} while(Bedingung);}
• Bedingungen: if, if-else, switch
• if: \texttt{if(Bedingung) \{ Anweisung \}}
• if-else: \texttt{if(Bedingung) \{ Anweisung \} else \{ Anweisung \}}
• switch: \texttt{switch(variable) \{ case Wert: Anweisung; break; \}}

Algorithmen: Such- und Sortieralgorithmen

Definition:

Such- und Sortieralgorithmen nutzen effiziente Methoden zur Datenorganisation und -suche.

Details:

• Suchalgorithmen: Finden von Elementen in Datenstrukturen.
• Sortieralgorithmen: Ordnen von Daten in einer bestimmten Reihenfolge.
• Klassische Suchalgorithmen: Lineare Suche, Binäre Suche (\textit{O(n)}, \textit{O(\text{log} n)}).
• Klassische Sortieralgorithmen: Bubble Sort, Merge Sort (\textit{O(n^2)}, \textit{O(n \text{log} n)}).
• Effizienz abhängig von Zeit- und Speicherkomplexität (\textit{Big-O-Notation}).

Komplexitätsanalyse: Laufzeit und Speicherbedarf

Definition:

Bewertung eines Algorithmus hinsichtlich der benötigten Zeit (Laufzeit) und des Speicherbedarfs (Space Complexity). Ziel ist die Klassifizierung der Effizienz.

Details:

• Laufzeit: Beschreibt, wie viel Zeit ein Algorithmus basierend auf der Eingabengröße benötigt. In der Regel wird die Laufzeit durch eine Funktion wie z.B. O(n), O(n^2) ausgedrückt.
• Speicherbedarf: Gibt an, wie viel Arbeitsspeicher ein Algorithmus in Abhängigkeit der Eingabengröße benötigt. Funktionen wie O(1), O(n) geben Aufschluss.
• Big-O-Notation: Verwendet, um das asymptotische Verhalten bzgl. Laufzeit und Speicherbedarf zu beschreiben; z.B. O(log n), O(n!), O(2^n).
• Worst-Case, Best-Case, Average-Case: Verschiedene Szenarien zur Analyse der Laufzeit.
• Amortisierte Analyse: Betrachtung der durchschnittlichen Laufzeit pro Operation über eine Folge von Operationen.

Relationale Datenbankmodelle und SQL

Definition:

Repräsentation von Daten in Tabellenform zur Gewährleistung der Datenintegrität und Vermeidung von Redundanzen.

Details:

• Tabellen: Zeilen (Datensätze) und Spalten (Attribute)
• Primärschlüssel: Eindeutiger Bezeichner einer Zeile
• Fremdschlüssel: Attribut, das auf Primärschlüssel einer anderen Tabelle verweist
• Normalisierung: Prozess zur Minimierung von Redundanzen und Abhängigkeiten
• SQL (Structured Query Language): Sprache zur Durchführung von Abfragen und Datenmanipulation
• Wichtige SQL-Befehle:
  • SELECT: Datenabfrage
  • INSERT: Dateneinfügen
  • UPDATE: Datenaktualisierung
  • DELETE: Datenlöschung

Automaten und formale Sprachen

Definition:

Automaten und formale Sprachen modellieren Berechnungsprozesse und syntaktische Strukturen.

Details:

• Endliche Automaten (FA): Akzeptieren reguläre Sprachen.
• Kontextfreie Grammatiken (CFG): Erzeugen kontextfreie Sprachen.
• Deterministische endliche Automaten (DFA) vs. nichtdeterministische endliche Automaten (NFA).
• Pumpinglemma: Nachweis nicht-regulärer Sprachen.
• Chomsky-Hierarchie: Klassifikation von Sprachen und Grammatiken.

Grundlagen der Wahrscheinlichkeitstheorie

Definition:

Grundbegriffe und Gesetze der Wahrscheinlichkeitstheorie, wichtig für Zufallsprozesse und statistische Analyse

Details:

• Gewisse Ereignisse: Ereignisse mit Wahrscheinlichkeit 1
• Unmögliche Ereignisse: Ereignisse mit Wahrscheinlichkeit 0
• Laplace-Regel: \( P(A) = \frac{|A|}{|\Omega|} \) für endliche, gleichwahrscheinliche Ereignisse
• Additionssatz: \( P(A \cup B) = P(A) + P(B) - P(A \cap B) \)
• Multiplikationssatz: \( P(A \cap B) = P(A) \cdot P(B|A) \)
• Unabhängige Ereignisse: \( P(A \cap B) = P(A) \cdot P(B) \)
• Gesetz der totalen Wahrscheinlichkeit: Dabei wird die Wahrscheinlichkeit eines Ereignisses als Summe der Wahrscheinlichkeiten von Teilergebnissen ausgedrückt \( P(A) = \sum_{i}P(A|B_i) \cdot P(B_i) \)

Regressionsmodellierung: Lineare und logistische Regression

Definition:

Regressionsanalyse zur Modellierung von Beziehungen zwischen abhängigen und unabhängigen Variablen. Lineare Regression für kontinuierliche Zielvariablen, logistische Regression für binäre bzw. kategorische Zielvariablen.

Details:

• Lineare Regression: Modell: \[\text{Y} = \beta_0 + \beta_1X_1 + \beta_2X_2 + \text{...} + \beta_nX_n + \text{E}\], Methode: gewöhnliche kleinste Quadrate (OLS)
• Logistische Regression: Modell: \[\text{log}\bigg( \frac{p}{1-p} \bigg) = \beta_0 + \beta_1X_1 + \beta_2X_2 + \text{...} + \beta_nX_n\], Methode: Maximum-Likelihood-Schätzung (MLE)
• Annahmen bei der linearen Regression: Linearität, Homoskedastizität, Unabhängigkeit der Fehler, Normalverteilung der Fehler
• Gütemaße: R-Quadrat (lineare Regression), McFadden R-Quadrat (logistische Regression), AIC/BIC
• Logistische Regression für Klassifikationsaufgaben