Einführungsmodul - Cheatsheet

Grundlegende Computerarchitektur und Funktionsweisen

Definition:

Grundlegende Bausteine von Computern und deren Interaktionen.

Details:

• Zentraleinheit: CPU mit ALU, Steuerwerk und Registern
• Speicherorganisation: RAM, ROM, Cache
• E/A-Systeme: Schnittstellen zu Peripheriegeräten
• Von-Neumann-Architektur: Trennung von Daten und Programmen im selben Speicher
• Maschinenbefehle: Opcode, Operanden
• Bus-Systeme: Datenbus, Adressbus, Steuerbus
• Takt & Clockzyklen: Auswirkungen auf die Geschwindigkeit
• Parallele und serielle Datenverarbeitung
• Pipelining: Effizienz durch gleichzeitige Verarbeitung

Einführung in die Theorie der Berechenbarkeit

Definition:

Untersuchung der Frage, welche Probleme mit einem Algorithmus lösbar sind und welche nicht.

Details:

• Entscheidungsprobleme und Turingmaschinen
• Church-Turing-These: Jeder berechenbare Algorithmus kann durch eine Turingmaschine simuliert werden.
• Halteproblem: Ein Beispiel eines unentscheidbaren Problems.
• Komplexitätsklassen: P, NP und deren Unterschiede.
• Reduktionen: Methode um zu zeigen, dass ein Problem unentscheidbar ist.
• Sprachen und Automaten: Reguläre, kontextfreie und entscheidbare Sprachen.

Grundlegende Syntax und Struktur von Python

Definition:

Basisstruktur und Syntaxelemente der Programmiersprache Python.

Details:

• # Kommentarzeilen beginnen mit #.
• Einrückungen bestimmen den Blockumfang, keine geschweiften Klammern.
• Variablen: keine Deklaration nötig, Zuweisung mit =.
• Datentypen: int, float, str, list, dict, tuple.
• Kontrollstrukturen: if, elif, else für Bedingungen.
• Schleifen: for und while.
• Funktionen: Definition mit def, Rückgabe mit return.
• Module importieren mit import.

Fehlersuche und Debugging-Techniken

Definition:

Techniken zur Identifikation, Analyse und Behebung von Fehlern in Softwarecode

Details:

• Breakpoints setzen
• Schrittweise Ausführung (Step-by-Step-Debugging)
• Log-Ausgaben und Protokollierung
• Verwendung von Debugging-Tools (z. B. gdb, Visual Studio Debugger)
• Unit-Tests und Testautomatisierung
• Code-Reviews
• Analyse von Core Dumps

Rekursion und ihre Anwendungsgebiete

Definition:

Rekursion: Funktion, die sich selbst aufruft, bis Basisfall erreicht ist.

Details:

• Basisfall: Bedingung, die Rekursion beendet
• Rekursiver Fall: Funktionsaufruf mit geänderter Eingabe
• Anwendungsgebiete: Mathematik (z.B. Fakultät), Algorithmen (z.B. Quicksort, Mergesort), Dynamische Programmierung, Baum- und Graph-Traversierung (z.B. Tiefensuche)
• Effizienz: Kann zu hohen Speicherverbrauch und Stacküberlauf führen, optimierbar durch Tail-Call-Optimierung und Memoisierung

Komplexitätsanalyse und Effizienz von Algorithmen

Definition:

Analyse der Laufzeit- und Platzkomplexität eines Algorithmus zur Bewertung seiner Effizienz.

Details:

• Zeitkomplexität: Worst-Case-, Best-Case- und Average-Case-Analyse
• Raumkomplexität: Speicherbedarf des Algorithmus
• Beispiele für Komplexitätsklassen: \(O(1)\), \(O(n)\), \(O(n^2)\), \(O(\log n)\)
• Big-O-Notation zur Abschätzung der oberen Schranken
• Empirische Analyse: Durchführung von Tests zur Laufzeitanalyse

Sortier- und Suchalgorithmen

Definition:

Algorithmen zur Anordnung von Elementen in einer bestimmten Reihenfolge (Sortieren) und zur Auffindung bestimmter Elemente in Datenstrukturen (Suchen).

Details:

• Sortieralgorithmen: zur Anordnung von Elementen
• Wichtige Sortieralgorithmen: Bubble Sort, Insertion Sort, Quick Sort, Merge Sort
• Komplexitätsklassen: \(O(n^2)\) und \(O(n \log n)\)
• Suchalgorithmen: zur Auffindung von Elementen
• Wichtige Suchalgorithmen: Lineare Suche, Binäre Suche
• Komplexitätsklassen: \(O(n)\) und \(O(\log n)\)
• Binäre Suche erfordert sortierte Datenstruktur

Hashing und kollisionsfreie Speicherung

Definition:

Hashing: Technik zur Abbildung von Daten auf kleinere Werte-Bereiche. Kollisionsfreie Speicherung: Strategien zur Vermeidung von Schlüsselkonflikten bei Nutzung von Hash-Tabellen.

Details:

• Hashfunktionen: Funktion, die Eingabedaten in einen Hashwert umwandelt (\texttt{hash(key)})
• Kollision: Wenn zwei verschiedene Schlüssel auf denselben Hashwert abgebildet werden
• Strategien zur Kollisionsvermeidung: Offene Adressierung (Linear Probing, Quadratic Probing), Verkettung (Chaining)
• Komplexität: Durchschnittliche Zugriffszeit \texttt{O(1)}
• Gute Hashfunktion: Gleichmäßige Verteilung, minimaler Zeitaufwand