NWERC Praktikum - Cheatsheet

Laufzeitanalyse von Algorithmen

Definition:

Analyse der Zeitkomplexität von Algorithmen zur Abschätzung der Effizienz.

Details:

• Asymptotische Notation: \(O(f(n))\), \(\Omega(f(n))\), \(\Theta(f(n))\)
• Best-Case, Average-Case, Worst-Case Laufzeit
• Wichtige Klassen: Polynomialzeit (P), NP, NP-vollständig
• Typische Funktionen: Konstante, logarithmische, lineare, quadratische, exponentielle Laufzeiten
• Master-Theorem für T(n) = aT(n/b) + f(n)
• Effiziente Algorithmen bevorzugen (z.B. logarithmische und lineare)

Greedy-Algorithmen

Definition:

Greedy-Algorithmen sind Algorithmusparadigmen, die in jeder Phase die lokal optimale Wahl treffen, mit der Hoffnung, die global optimale Lösung zu finden.

Details:

• Verwendet für Optimierungsprobleme.
• Keine Garantie auf globale Optimalität.
• Beispiele: Prim's Algorithmus, Kruskal's Algorithmus, Huffman-Codierung.
• Komplexität oft geringer als dynamische Programmierung.
• Lösungen bauen auf vorherigen Entscheidungen auf.
• Geeignet für Probleme mit der Greedy-Eigenschaft (Optimalitätsprinzip).

Dynamische Programmierung

Definition:

Methode zur Lösung von Optimierungsproblemen durch Zerlegung in überlappende Teilprobleme.

Details:

• Vermeide wiederholte Berechnungen durch Zwischenspeichern von Ergebnissen (Memoisierung).
• Verwende oft rekursive Formeln, z.B. bei der Berechnung eines optimalen Wertes.
• Nutze DP-Tabellen, um Zwischenresultate zu speichern.
• Typische Anwendungsbeispiele: kürzester Pfad (Floyd-Warshall), Rucksackproblem, Fibonacci-Zahlen.
• Unterscheide zwischen Top-Down (rekursive) und Bottom-Up (iterative) Ansätzen.

Graphalgorithmen wie Dijkstra und A*-Algorithmus

Definition:

Graphalgorithmen zur Suche nach kürzesten Pfaden. Dijkstra und A* werden häufig verwendet.

Details:

• Dijkstra: Funktioniert mit nichtnegativen Kantengewichten.
• Komplexität: O((|V| + |E|) \times \text{log}(|V|)) bei Verwendung eines Priority Queue.
• Formel: \(d[v] = \text{min}(d[v], d[u] + w(u, v))\) für alle Kanten \((u, v)\).
• A*: Erweiterung von Dijkstra mit Heuristik.
• Heuristik: Funktion \(h(v)\), die geschätzte Entfernung von \(v\) zum Ziel angibt.
• Formel: \(f(v) = g(v) + h(v)\), wobei \(g(v)\) die Kosten vom Startknoten zu \(v\) sind.

Binäre Suchbäume und AVL-Bäume

Definition:

Binäre Suchbäume sind Baumstrukturen, bei denen jedes Knotenpaar so angeordnet ist, dass der linke Teilbaum alle kleineren Werte und der rechte Teilbaum alle größeren Werte enthält. AVL-Bäume sind eine spezielle Art von binären Suchbäumen, die immer balanciert sind.

Details:

• Inorder-Traversierung ergibt sortierte Reihenfolge.
• Sucht, Einfügen und Löschen in durchschnittlich O(log n).
• AVL-Bäume balancieren sich selbst durch Rotationen.
• Höhenunterschied zwischen linken und rechten Teilbäumen max. 1.
• Rotationen: einfach (LL, RR) und doppelt (LR, RL).
• Balancierung nach Einfügen/Löschen durch Rotationen wiederhergestellt.

Best Practices für die Teamarbeit in der Programmierung

Definition:

Effektive Zusammenarbeit und Kommunikationsstrategien im Team, um Programmierprojekte effizient zu gestalten.

Details:

• Regelmäßige Kommunikation: Tägliche Stand-ups, wöchentliche Meetings.
• Code-Reviews: Qualitativer und konsistenter Code, Fehlervermeidung.
• Pair Programming: Wissenstransfer, sofortiges Feedback.
• Versionskontrolle: Nutzung von Git, Vermeidung von Merge-Konflikten.
• Klare Aufgabenverteilung: Nutzung von Kanban-Boards (z.B. Jira, Trello).
• Dokumentation: Gut dokumentierter Code, Wiki-Seiten für Projektinfos.
• Kollaborative Tools: Slack, Microsoft Teams für schnelle Kommunikation.
• Testing: Unit-Tests, Integrationstests, kontinuierliche Überprüfung.

Versionierungssysteme wie Git

Definition:

Git ist ein verteiltes Versionskontrollsystem zur Verwaltung von Quellcode.

Details:

• Ermöglicht das Nachverfolgen von Änderungen: Commit-Historie
• Verzweigung und Zusammenführung von Entwicklungszweigen: Branches und Merging
• Dezentralisiert: Jeder Klon ist ein vollständiges Repository
• Git-Befehle: \texttt{git init}, \texttt{git clone}, \texttt{git add}, \texttt{git commit}, \texttt{git push}, \texttt{git pull}, \texttt{git merge}
• Konflikte bei Zusammenführungen: Merge Conflicts
• Staging Area: Bereich zum Vorbereiten von Commits
• Remote Repositories: Zusammenarbeit via GitHub, GitLab etc.

Testgetriebene Entwicklung (TDD)

Definition:

Kurzer Zyklus der Softwareentwicklung: Test schreiben, Code implementieren, refaktorisieren

Details:

• Schritte: Schreiben eines fehlgeschlagenen Tests, Implementierung von minimalem Code, um Test zu bestehen, Refaktorisierung des Codes
• Testfall: Definiert Anforderungen vor der Implementierung des Codes
• Vorteile: Verbesserung der Codequalität, frühzeitige Fehlererkennung
• Tests sollten automatisierbar und wiederholbar sein