Introduction to informatics for Students of Mathematics - Cheatsheet.pdf

Komplexitätsanalyse von Algorithmen

Definition:

Analyse der erforderlichen Ressourcen (Zeit, Speicher) zur Ausführung eines Algorithmus.

Details:

• Zeitkomplexität: Beschreibt wie die Laufzeit eines Algorithmus mit der Eingabegröße wächst. Notationen: \( O(n) \), \( \theta(n) \), \( \theta(n^2) \)
• Speicherkomplexität: Beschreibt wie der Speicherbedarf eines Algorithmus mit der Eingabegröße wächst. Notationen analog.
• Worst-Case, Best-Case, Average-Case: Verschiedene Betrachtungsweisen der Komplexität anhand der Eingabe.
• Asymptotisches Verhalten: Fokus auf das Verhalten für große Eingabegrößen, Vernachlässigung von konstanten Faktoren und niedrigeren Ordnungsterminen.
• Methoden: Dominante Terme identifizieren, Summen & Rekursionsgleichungen lösen.

Sortieralgorithmen: Quicksort und Mergesort

Definition:

Sortieralgorithmen: Quicksort und Mergesort - die zwei wesentlichen Algorithmen zur Sortierung von Daten.

Details:

• Quicksort: Ein 'Divide-and-Conquer'-Algorithmus, der ein Array rekursiv in kleinere Arrays aufteilt.
• Pivot-Element wählen, Array in zwei Teillisten aufteilen: kleiner und größer als Pivot.
• Rekursive Anwendung auf Teillisten.
• Best Case: \(O(n \log n)\), Worst Case: \(O(n^2)\) (bei schlechtem Pivot).
• Mergesort: Ebenfalls ein 'Divide-and-Conquer'-Ansatz.
• Array in zwei Hälften teilen, jede Hälfte rekursiv sortieren, sortierte Hälften zusammenführen (Merge).
• Kombiniere zwei sortierte Listen zu einer sortierten Liste.
• Komplexität: stets \(O(n \log n)\).

Graphensuche: BFS und DFS

Definition:

Graphensuche: BFS (Breitensuche) und DFS (Tiefensuche) sind Algorithmen zur Traversierung oder Suche von Knoten in einem Graphen.

Details:

• BFS (Breitensuche): Durchsucht die Knoten Ebene für Ebene.
• Verwendet Schlange (Queue) als Datenstruktur.
• Komplexität: \(O(V + E)\)
• Nützlich für kürzeste Wege in ungewichteten Graphen.
• Pseudocode:

  enqueue(start); while(queue not empty) { node = dequeue(); process(node); enqueue(all unvisited neighbors); }

• DFS (Tiefensuche): Durchsucht die Knoten tiefer entlang jedes Zweigs.
• Verwendet Stapel (Stack) oder rekursive Aufrufe.
• Komplexität: \(O(V + E)\)
• Nützlich für Pfaderkennung und Zyklen in Graphen.
• Pseudocode:

  push(start); while(stack not empty) { node = pop(); if (node not visited) { process(node); push(all unvisited neighbors); } }

Rekursive Algorithmen

Definition:

Verfahren, bei dem eine Funktion sich selbst aufruft, um ein Problem zu lösen.

Details:

• Basisfall: Stoppt die Rekursion.
• Rekursionsfall: Bricht das Problem auf kleinere Teilprobleme herunter.
• Beispiel: Fakultät, Fibonacci, Türme von Hanoi.
• Zeichenkette: def rekursion(x): if x == basisfall: return basiswert return x * rekursion(x-1)
• Komplexität analysieren: oft durch Rekursionsgleichungen.
• Vor Nachteile: Klarheit, Einfachheit vs. Speicherbedarf (Stack-Overflow).
• Memoization: Zwischenergebnisse speichern zur Effizienzsteigerung.

Lineare vs. hierarchische Datenstrukturen

Definition:

Lineare Datenstrukturen sind solche, bei denen die Elemente in einer sequenziellen Reihenfolge organisiert sind, während hierarchische Datenstrukturen Elemente in einer Baum- oder verschachtelten Struktur organisieren.

Details:

• Lineare Datenstrukturen: Arrays, Listen, Stacks, Queues
• Hierarchische Datenstrukturen: Bäume, Grafen
• Lineares Durchlaufen: Zugriff auf jedes Element in einer Reihe
• Hierarchisches Durchlaufen: Zugriff auf Knoten und deren Kinder
• Zeitkomplexität variiert stark zwischen beiden Typen je nach Operation (Einfügen, Löschen, Suchen)
• Verwendung: Lineare für einfache Durchlaufmuster und hierarchische für komplexe Beziehungen

Hash-Tabellen und Haschierverfahren

Definition:

Verfahren zur effizienten Zuordnung von Schlüsseln zu Werten mittels einer Hash-Funktion.

Details:

• Hash-Funktion: Abbildung eines Schlüssels auf einen Index im Array
• Kollisionsbehandlung: Methoden wie Verkettung oder offenes Adressieren
• Typische Operationen: Einfügen \texttt{insert(key, value)}, Suchen \texttt{search(key)}, Löschen \texttt{delete(key)}
• Komplexität: Durchschnittlich O(1) für Einfügen, Suchen und Löschen

Einführung in Python und Java

Definition:

Einführung in Python und Java. Grundlegende Programmierkenntnisse.

Details:

• Python: Interpretiert, dynamisch typisiert, einfach zu erlernen.
• Java: Kompiliert, statisch typisiert, objektorientiert.
• Syntax:
• Python: Indentierung, keine Semikolons.
• Java: Blockstruktur mit Klammern, Semikolons erforderlich.
• Beispiel: Hello World
• Python:

  print('Hello, World!')

• Java:

  public class Main {  public static void main(String[] args) {    System.out.println('Hello, World!');  }}

• Mathematische Operationen:
• Python:

  a = 5b = 3sum = a + bproduct = a * b

• Java:

  int a = 5;int b = 3;int sum = a + b;int product = a * b;

• Nützlich für: Algorithmen, Datenanalyse, Softwareentwicklung.

Softwareentwicklungsprozesse: Wasserfall vs. Agile

Definition:

Softwareentwicklungsprozesse vergleichen und verstehen: Wasserfallmodell vs. Agile Methoden, um das passende Vorgehen für Projekte zu wählen.

Details:

• Wasserfallmodell: Sequenzielles Vorgehen mit klar definierten Phasen (Analyse, Design, Implementierung, Test, Wartung).
• Stabilität und Struktur durch feste Reihenfolge der Phasen, aber wenig Flexibilität bei Änderungen.
• Hoher Planungsaufwand und ausführliche Dokumentation vor der Implementierung notwendig.
• Agile Methoden: Iterativer und inkrementeller Ansatz mit häufigen Feedback-Schleifen und Anpassungen.
• Flexibilität und kontinuierliche Verbesserung durch regelmäßige Reviews und Anpassungen.
• Fokus auf funktionierende Software und Kundenzufriedenheit durch kurze Entwicklungszyklen (Sprints).