Spaces:
Running
Running
| title: Algorithmen | |
| emoji: 🧮 | |
| colorFrom: blue | |
| colorTo: indigo | |
| sdk: static | |
| pinned: false | |
| short_description: Algorithmen, Datenstrukturen, Optimierung und AI Systems. | |
| # Algorithmen | |
| **Die deutschsprachige Referenz zu Algorithmen, Datenstrukturen, Laufzeitkomplexität, Suchverfahren, Sortierverfahren, Graphalgorithmen, Optimierung, Machine Learning und algorithmischen KI-Systemen.** | |
| Algorithmen gehören zu den grundlegenden Bausteinen der Informatik. Sie beschreiben **präzise Verfahren**, mit denen Eingaben verarbeitet, Probleme gelöst und Ergebnisse erzeugt werden. | |
| Ob Suchmaschine, Navigationssystem, Datenbank, Empfehlungssystem, Machine-Learning-Modell, KI-Agent oder Betriebssystem: Hinter nahezu jedem digitalen System stehen Algorithmen. | |
| Diese Hugging-Face-Organisation bündelt deutschsprachige technische Ressourcen rund um: | |
| - **Algorithmen** | |
| - **Datenstrukturen** | |
| - **Algorithm Design** | |
| - **Laufzeitkomplexität** | |
| - **Big-O-Notation** | |
| - **Sortieralgorithmen** | |
| - **Suchalgorithmen** | |
| - **Graphalgorithmen** | |
| - **Greedy Algorithms** | |
| - **Divide and Conquer** | |
| - **Dynamic Programming** | |
| - **Backtracking** | |
| - **Randomisierte Algorithmen** | |
| - **Optimierungsalgorithmen** | |
| - **Numerische Verfahren** | |
| - **Machine-Learning-Algorithmen** | |
| - **KI-Algorithmen** | |
| - **Such- und Planungsverfahren** | |
| - **Reinforcement Learning** | |
| - **Algorithmic Decision Systems** | |
| - **Algorithm Engineering** | |
| Ziel ist eine verständliche, technisch belastbare und praxisnahe Referenz mit **Erklärungen, Komplexitätsanalysen, Beispielen, Architekturmustern, interaktiven Spaces, Benchmarks und weiterführenden Ressourcen**. | |
| > **Kurzdefinition:** Ein Algorithmus ist eine endliche, eindeutig beschriebene Folge von Schritten, mit der ein Problem gelöst oder eine Eingabe in ein gewünschtes Ergebnis überführt wird. | |
| --- | |
| # Was ist ein Algorithmus? | |
| Ein Algorithmus ist eine präzise Handlungsanweisung. | |
| Er legt fest: | |
| 1. welche Eingaben verarbeitet werden, | |
| 2. welche Schritte durchgeführt werden, | |
| 3. in welcher Reihenfolge diese Schritte erfolgen, | |
| 4. wann der Prozess endet, | |
| 5. welches Ergebnis ausgegeben wird. | |
| Ein einfaches Beispiel ist das Sortieren einer Liste. | |
| Eingabe: | |
| ```text | |
| 5, 2, 9, 1 | |
| ``` | |
| Ausgabe: | |
| ```text | |
| 1, 2, 5, 9 | |
| ``` | |
| Der Algorithmus beschreibt, wie aus der unsortierten Liste die sortierte Liste entsteht. | |
| Wichtig ist: | |
| **Ein Algorithmus ist nicht dasselbe wie ein Programm.** | |
| Ein Algorithmus beschreibt die Logik. | |
| Ein Programm ist die konkrete Implementierung dieser Logik in einer Programmiersprache. | |
| --- | |
| # Algorithmus einfach erklärt | |
| Ein Kochrezept ist ein gutes Alltagsbeispiel. | |
| Ein Rezept enthält: | |
| - Zutaten, | |
| - Reihenfolge, | |
| - Verarbeitungsschritte, | |
| - Bedingungen, | |
| - Ergebnis. | |
| Ein Algorithmus funktioniert ähnlich. | |
| Beispiel: | |
| **Aufgabe:** Größte Zahl in einer Liste finden. | |
| Möglicher Algorithmus: | |
| 1. Nimm die erste Zahl als bisher größtes Element. | |
| 2. Vergleiche sie mit der nächsten Zahl. | |
| 3. Ist die neue Zahl größer, speichere sie als neues Maximum. | |
| 4. Wiederhole den Vergleich bis zum Ende. | |
| 5. Gib das größte Element aus. | |
| Dieser Algorithmus funktioniert unabhängig davon, ob die Liste 5, 500 oder 5 Millionen Werte enthält. | |
| --- | |
| # Warum sind Algorithmen wichtig? | |
| Algorithmen bestimmen: | |
| - wie schnell Software arbeitet, | |
| - wie viel Speicher benötigt wird, | |
| - wie gut ein Problem skaliert, | |
| - wie zuverlässig Ergebnisse entstehen, | |
| - wie Daten verarbeitet werden, | |
| - wie Entscheidungen automatisiert werden. | |
| Zwei Programme können dasselbe Problem lösen und trotzdem völlig unterschiedlich effizient sein. | |
| Ein schlechter Algorithmus kann bei kleinen Datenmengen funktionieren und bei großen Datenmengen unbrauchbar werden. | |
| Deshalb sind **Algorithmuswahl und Komplexitätsanalyse** zentrale Themen der Informatik. | |
| --- | |
| # Eigenschaften eines guten Algorithmus | |
| Ein guter Algorithmus sollte mehrere Eigenschaften besitzen. | |
| ## Korrektheit | |
| Er liefert für gültige Eingaben das erwartete Ergebnis. | |
| ## Endlichkeit | |
| Er endet nach einer endlichen Anzahl von Schritten. | |
| ## Eindeutigkeit | |
| Die einzelnen Schritte sind klar definiert. | |
| ## Effizienz | |
| Laufzeit und Speicherverbrauch sind angemessen. | |
| ## Robustheit | |
| Der Algorithmus kann mit Randfällen und problematischen Eingaben umgehen. | |
| ## Verständlichkeit | |
| Die Logik ist nachvollziehbar und wartbar. | |
| --- | |
| # Algorithmus vs. Heuristik | |
| Ein Algorithmus kann exakt definiert sein. | |
| Eine **Heuristik** ist dagegen häufig eine praktische Näherungsstrategie. | |
| Beispiel: | |
| Ein Optimierungsproblem kann theoretisch eine exakte Lösung besitzen, aber deren Berechnung wäre extrem teuer. | |
| Dann kann eine Heuristik eine ausreichend gute Lösung deutlich schneller finden. | |
| Heuristiken sind besonders relevant bei: | |
| - Planung, | |
| - Optimierung, | |
| - Suchproblemen, | |
| - KI-Systemen, | |
| - Routing. | |
| --- | |
| # Algorithmus vs. Künstliche Intelligenz | |
| Nicht jeder Algorithmus ist KI. | |
| Ein klassischer Sortieralgorithmus ist keine künstliche Intelligenz. | |
| KI-Systeme verwenden jedoch sehr viele Algorithmen. | |
| Beispiele: | |
| - Optimierungsalgorithmen, | |
| - Trainingsalgorithmen, | |
| - Suchverfahren, | |
| - Sampling, | |
| - Routing, | |
| - Retrieval, | |
| - Graphverfahren, | |
| - Planungsverfahren. | |
| Künstliche Intelligenz baut auf algorithmischen Grundlagen auf. | |
| --- | |
| # Algorithmus vs. Machine Learning | |
| Ein klassischer Algorithmus besitzt explizite Regeln. | |
| Ein Machine-Learning-Modell lernt Teile seines Verhaltens aus Daten. | |
| Beispiel: | |
| ## Klassischer Algorithmus | |
| ```text | |
| Wenn Temperatur > 80: | |
| Warnung ausgeben | |
| ``` | |
| ## Machine Learning | |
| Das Modell lernt aus historischen Daten, welche Kombination von Sensorwerten wahrscheinlich auf einen Fehler hinweist. | |
| Machine Learning ersetzt Algorithmen nicht. | |
| Es erweitert die Menge der Probleme, die algorithmisch gelöst werden können. | |
| --- | |
| # Was ist Algorithm Design? | |
| Algorithm Design beschreibt die systematische Entwicklung von Lösungsverfahren. | |
| Typische Fragen: | |
| - Wie lässt sich das Problem strukturieren? | |
| - Welche Datenstruktur passt? | |
| - Kann das Problem zerlegt werden? | |
| - Gibt es wiederkehrende Teilprobleme? | |
| - Ist eine exakte Lösung nötig? | |
| - Welche Laufzeit ist akzeptabel? | |
| Algorithm Design ist mehr als Programmieren. | |
| Es geht um die zugrunde liegende Problemlösungsstrategie. | |
| --- | |
| # Datenstrukturen | |
| Algorithmen und Datenstrukturen gehören zusammen. | |
| Eine Datenstruktur bestimmt, wie Informationen gespeichert und organisiert werden. | |
| Typische Datenstrukturen: | |
| - Array, | |
| - Liste, | |
| - Stack, | |
| - Queue, | |
| - Hash Table, | |
| - Tree, | |
| - Heap, | |
| - Graph, | |
| - Set, | |
| - Map. | |
| Die Wahl der Datenstruktur kann die Effizienz eines Algorithmus entscheidend beeinflussen. | |
| --- | |
| # Arrays | |
| Arrays speichern Elemente in einer festen Reihenfolge. | |
| Vorteile: | |
| - schneller direkter Zugriff über Index, | |
| - kompakte Speicherung. | |
| Typische Operationen: | |
| - Lesen, | |
| - Schreiben, | |
| - Iteration. | |
| --- | |
| # Verkettete Listen | |
| Linked Lists speichern Elemente als Knoten mit Verweisen. | |
| Vorteile: | |
| - flexible Größe, | |
| - Einfügen und Entfernen kann effizient sein. | |
| Nachteile: | |
| - kein direkter Indexzugriff, | |
| - zusätzlicher Speicher für Verweise. | |
| --- | |
| # Stack | |
| Ein Stack arbeitet nach dem Prinzip: | |
| **Last In, First Out** | |
| Typische Operationen: | |
| - push, | |
| - pop, | |
| - peek. | |
| Anwendungen: | |
| - Funktionsaufrufe, | |
| - Undo, | |
| - Parsing, | |
| - Tiefensuche. | |
| --- | |
| # Queue | |
| Eine Queue arbeitet typischerweise nach: | |
| **First In, First Out** | |
| Anwendungen: | |
| - Job-Verarbeitung, | |
| - Messaging, | |
| - Breadth-First Search, | |
| - Scheduling. | |
| --- | |
| # Hash Tables | |
| Hash Tables speichern Schlüssel-Wert-Paare. | |
| Typische Eigenschaft: | |
| Sehr schneller durchschnittlicher Zugriff. | |
| Anwendungen: | |
| - Caches, | |
| - Maps, | |
| - Dictionaries, | |
| - Indizes. | |
| Die Qualität der Hash-Funktion und Kollisionsbehandlung ist entscheidend. | |
| --- | |
| # Bäume | |
| Trees organisieren Daten hierarchisch. | |
| Beispiele: | |
| - Binary Tree, | |
| - Binary Search Tree, | |
| - AVL Tree, | |
| - B-Tree, | |
| - Trie. | |
| Bäume werden genutzt für: | |
| - Suche, | |
| - Dateisysteme, | |
| - Datenbanken, | |
| - Compiler, | |
| - Autovervollständigung. | |
| --- | |
| # Heaps | |
| Ein Heap ist eine Datenstruktur für Prioritätsoperationen. | |
| Typische Anwendung: | |
| - Priority Queue, | |
| - Scheduling, | |
| - Dijkstra, | |
| - Heap Sort. | |
| --- | |
| # Graphen | |
| Graphen bestehen aus: | |
| - Knoten, | |
| - Kanten. | |
| Sie modellieren Beziehungen. | |
| Beispiele: | |
| - Straßennetze, | |
| - soziale Netzwerke, | |
| - Abhängigkeiten, | |
| - Computernetze, | |
| - Knowledge Graphs, | |
| - Agentenbeziehungen. | |
| Graphalgorithmen sind deshalb besonders wichtig. | |
| --- | |
| # Laufzeitkomplexität | |
| Die Laufzeitkomplexität beschreibt, wie der Rechenaufwand mit der Eingabegröße wächst. | |
| Statt konkrete Millisekunden zu messen, betrachtet man häufig das Wachstum. | |
| Beispiele: | |
| - O(1) | |
| - O(log n) | |
| - O(n) | |
| - O(n log n) | |
| - O(n²) | |
| - O(2^n) | |
| --- | |
| # Big-O-Notation | |
| Die Big-O-Notation beschreibt eine obere asymptotische Schranke. | |
| Sie hilft zu beurteilen, wie ein Algorithmus bei großen Eingaben skaliert. | |
| ## O(1) | |
| Konstanter Aufwand. | |
| Beispiel: | |
| Zugriff auf ein Array-Element über Index. | |
| ## O(log n) | |
| Logarithmischer Aufwand. | |
| Beispiel: | |
| Binäre Suche. | |
| ## O(n) | |
| Linearer Aufwand. | |
| Beispiel: | |
| Einmal durch eine Liste laufen. | |
| ## O(n log n) | |
| Typisch für effiziente Vergleichssortierung. | |
| ## O(n²) | |
| Quadratischer Aufwand. | |
| Beispiel: | |
| Doppelte Schleife über alle Elementpaare. | |
| ## O(2^n) | |
| Exponentieller Aufwand. | |
| Kann bei größeren n sehr schnell unpraktisch werden. | |
| --- | |
| # Best Case, Average Case und Worst Case | |
| Algorithmen können je nach Eingabe unterschiedlich lange benötigen. | |
| ## Best Case | |
| Günstigste Eingabe. | |
| ## Average Case | |
| Typischer durchschnittlicher Aufwand. | |
| ## Worst Case | |
| Schlechtester möglicher Aufwand. | |
| Für kritische Systeme ist der Worst Case häufig besonders relevant. | |
| --- | |
| # Speicherkomplexität | |
| Neben Laufzeit ist Speicherverbrauch wichtig. | |
| Ein Algorithmus kann schnell sein, aber sehr viel Speicher benötigen. | |
| Speicherkomplexität beschreibt, wie der Speicherbedarf mit der Eingabe wächst. | |
| --- | |
| # Zeit-Speicher-Trade-off | |
| Häufig lässt sich Zeit gegen Speicher tauschen. | |
| Beispiel: | |
| Ein Cache benötigt zusätzlichen Speicher, kann aber wiederholte Berechnungen vermeiden. | |
| Solche Trade-offs sind zentral im Algorithm Engineering. | |
| --- | |
| # Sortieralgorithmen | |
| Sortieren ist ein klassisches Problem der Informatik. | |
| Wichtige Verfahren: | |
| - Bubble Sort, | |
| - Insertion Sort, | |
| - Selection Sort, | |
| - Merge Sort, | |
| - Quick Sort, | |
| - Heap Sort. | |
| --- | |
| # Bubble Sort | |
| Bubble Sort vergleicht benachbarte Elemente und vertauscht sie bei falscher Reihenfolge. | |
| Vorteile: | |
| - einfach zu verstehen. | |
| Nachteile: | |
| - ineffizient für große Datenmengen. | |
| Typische Laufzeit: | |
| **O(n²)** | |
| --- | |
| # Insertion Sort | |
| Insertion Sort baut schrittweise eine sortierte Teilliste auf. | |
| Vorteile: | |
| - einfach, | |
| - gut für kleine oder fast sortierte Daten. | |
| Worst Case: | |
| **O(n²)** | |
| --- | |
| # Merge Sort | |
| Merge Sort nutzt **Divide and Conquer**. | |
| Ablauf: | |
| 1. Liste teilen. | |
| 2. Teilprobleme sortieren. | |
| 3. Ergebnisse zusammenführen. | |
| Laufzeit: | |
| **O(n log n)** | |
| --- | |
| # Quick Sort | |
| Quick Sort wählt ein Pivot-Element und partitioniert die Daten. | |
| Durchschnittlich: | |
| **O(n log n)** | |
| Worst Case: | |
| **O(n²)** | |
| In der Praxis ist Quick Sort dennoch sehr effizient. | |
| --- | |
| # Heap Sort | |
| Heap Sort verwendet eine Heap-Datenstruktur. | |
| Laufzeit: | |
| **O(n log n)** | |
| Es benötigt keine rekursive Merge-Struktur wie Merge Sort. | |
| --- | |
| # Stabilität beim Sortieren | |
| Ein Sortieralgorithmus ist **stabil**, wenn Elemente mit gleichem Schlüssel ihre relative Reihenfolge behalten. | |
| Das kann wichtig sein, wenn bereits nach einem anderen Kriterium sortiert wurde. | |
| --- | |
| # Suchalgorithmen | |
| Suchalgorithmen finden Elemente oder Lösungen. | |
| Typische Verfahren: | |
| - lineare Suche, | |
| - binäre Suche, | |
| - Graphsuche, | |
| - heuristische Suche. | |
| --- | |
| # Lineare Suche | |
| Die lineare Suche prüft Elemente der Reihe nach. | |
| Laufzeit: | |
| **O(n)** | |
| Sie funktioniert auch bei unsortierten Daten. | |
| --- | |
| # Binäre Suche | |
| Die binäre Suche halbiert den Suchraum schrittweise. | |
| Voraussetzung: | |
| Die Daten sind sortiert. | |
| Laufzeit: | |
| **O(log n)** | |
| Bei großen Datenmengen ist das deutlich effizienter als lineare Suche. | |
| --- | |
| # Divide and Conquer | |
| Divide and Conquer zerlegt ein Problem in kleinere Teilprobleme. | |
| Typischer Ablauf: | |
| 1. Problem teilen. | |
| 2. Teilprobleme lösen. | |
| 3. Lösungen kombinieren. | |
| Beispiele: | |
| - Merge Sort, | |
| - Quick Sort, | |
| - Binary Search. | |
| --- | |
| # Dynamic Programming | |
| Dynamic Programming eignet sich für Probleme mit wiederkehrenden Teilproblemen. | |
| Statt dieselben Teilprobleme mehrfach zu berechnen, werden Ergebnisse gespeichert. | |
| Typische Strategien: | |
| - Memoization, | |
| - Tabulation. | |
| Anwendungen: | |
| - kürzeste Pfade, | |
| - Sequenzprobleme, | |
| - Optimierung, | |
| - Ressourcenplanung. | |
| --- | |
| # Greedy Algorithms | |
| Greedy Algorithms treffen lokal jeweils die scheinbar beste Entscheidung. | |
| Vorteil: | |
| - häufig einfach und schnell. | |
| Nachteil: | |
| - lokale Optima führen nicht immer zum globalen Optimum. | |
| Beispiele: | |
| - bestimmte Scheduling-Probleme, | |
| - Huffman Coding, | |
| - Minimum Spanning Tree. | |
| --- | |
| # Backtracking | |
| Backtracking probiert Lösungsmöglichkeiten aus und verwirft Pfade, die nicht funktionieren. | |
| Anwendungen: | |
| - Sudoku, | |
| - N-Queens, | |
| - Constraint Satisfaction, | |
| - kombinatorische Suche. | |
| Backtracking kann teuer werden, ist aber für viele Suchprobleme sehr nützlich. | |
| --- | |
| # Branch and Bound | |
| Branch and Bound verbessert systematische Suche durch Schranken. | |
| Teilbereiche werden verworfen, wenn klar ist, dass sie keine bessere Lösung liefern können. | |
| Anwendungen: | |
| - kombinatorische Optimierung, | |
| - Scheduling, | |
| - Integer Programming. | |
| --- | |
| # Rekursion | |
| Rekursion bedeutet, dass eine Funktion sich selbst aufruft. | |
| Typisch bei: | |
| - Trees, | |
| - Divide and Conquer, | |
| - Backtracking. | |
| Rekursion kann elegante Lösungen ermöglichen, benötigt aber Kontrolle über: | |
| - Abbruchbedingung, | |
| - Stack-Tiefe, | |
| - Laufzeit. | |
| --- | |
| # Iteration | |
| Iteration wiederholt Schritte über Schleifen. | |
| Viele rekursive Algorithmen können auch iterativ formuliert werden. | |
| Die Wahl hängt ab von: | |
| - Lesbarkeit, | |
| - Speicher, | |
| - Laufzeit, | |
| - Problemstruktur. | |
| --- | |
| # Graphalgorithmen | |
| Graphen sind zentral für viele moderne Systeme. | |
| Wichtige Graphalgorithmen: | |
| - Breadth-First Search, | |
| - Depth-First Search, | |
| - Dijkstra, | |
| - A*, | |
| - Bellman-Ford, | |
| - Floyd-Warshall, | |
| - Kruskal, | |
| - Prim, | |
| - Topological Sort. | |
| --- | |
| # Breadth-First Search | |
| BFS durchsucht einen Graphen schichtweise. | |
| Typische Anwendungen: | |
| - kürzester Pfad in ungewichteten Graphen, | |
| - Netzwerkreichweite, | |
| - Web Crawling. | |
| BFS verwendet typischerweise eine Queue. | |
| --- | |
| # Depth-First Search | |
| DFS verfolgt einen Pfad möglichst tief, bevor zurückgegangen wird. | |
| Anwendungen: | |
| - Zyklenerkennung, | |
| - Topological Sort, | |
| - Connected Components, | |
| - Backtracking. | |
| DFS verwendet häufig einen Stack oder Rekursion. | |
| --- | |
| # Dijkstra | |
| Dijkstra berechnet kürzeste Wege in Graphen mit nicht-negativen Kantengewichten. | |
| Anwendungen: | |
| - Routing, | |
| - Netzwerkplanung, | |
| - Navigation. | |
| Mit Priority Queue kann Dijkstra effizient implementiert werden. | |
| --- | |
| # A* | |
| A* erweitert Pfadsuche um eine Heuristik. | |
| Die Heuristik schätzt die verbleibenden Kosten zum Ziel. | |
| A* ist besonders wichtig in: | |
| - Navigation, | |
| - Games, | |
| - Robotik, | |
| - Planning. | |
| --- | |
| # Bellman-Ford | |
| Bellman-Ford kann kürzeste Wege auch bei negativen Kantengewichten berechnen. | |
| Es kann außerdem negative Zyklen erkennen. | |
| --- | |
| # Minimum Spanning Tree | |
| Ein Minimum Spanning Tree verbindet alle Knoten eines gewichteten Graphen mit minimalen Gesamtkosten. | |
| Wichtige Algorithmen: | |
| - Kruskal, | |
| - Prim. | |
| Anwendungen: | |
| - Netzdesign, | |
| - Infrastrukturplanung, | |
| - Clustering. | |
| --- | |
| # Topological Sort | |
| Topological Sort erzeugt eine Reihenfolge für gerichtete azyklische Graphen. | |
| Anwendungen: | |
| - Build-Systeme, | |
| - Abhängigkeiten, | |
| - Workflow-Orchestrierung, | |
| - Scheduling. | |
| --- | |
| # Optimierungsalgorithmen | |
| Optimierungsalgorithmen suchen die beste Lösung unter gegebenen Bedingungen. | |
| Ziele können sein: | |
| - Kosten minimieren, | |
| - Gewinn maximieren, | |
| - Weg verkürzen, | |
| - Ressourcen optimal verteilen. | |
| --- | |
| # Lineare Optimierung | |
| Lineare Optimierung arbeitet mit linearen Zielfunktionen und Nebenbedingungen. | |
| Anwendungen: | |
| - Logistik, | |
| - Produktionsplanung, | |
| - Ressourcenallokation. | |
| --- | |
| # Ganzzahlige Optimierung | |
| Integer Programming verlangt ganzzahlige Variablen. | |
| Typisch bei: | |
| - Auswahlproblemen, | |
| - Scheduling, | |
| - Routenplanung. | |
| Diese Probleme können deutlich schwieriger sein als lineare Programme. | |
| --- | |
| # Gradientenverfahren | |
| Gradientenverfahren optimieren eine Zielfunktion schrittweise. | |
| Ein wichtiges Beispiel ist **Gradient Descent**. | |
| Gradient Descent ist eine zentrale Grundlage für das Training neuronaler Netze. | |
| --- | |
| # Stochastic Gradient Descent | |
| SGD verwendet Teilmengen der Daten. | |
| Vorteile: | |
| - skalierbarer bei großen Datenmengen, | |
| - häufig schneller pro Schritt. | |
| Varianten: | |
| - Mini-Batch SGD, | |
| - Momentum, | |
| - Adam. | |
| --- | |
| # Randomisierte Algorithmen | |
| Randomisierte Algorithmen verwenden Zufall als Teil ihrer Strategie. | |
| Vorteile: | |
| - einfache Lösungen, | |
| - gute durchschnittliche Performance, | |
| - Robustheit gegen bestimmte Eingaben. | |
| Beispiele: | |
| - randomized Quick Sort, | |
| - Monte-Carlo-Verfahren, | |
| - Sampling. | |
| --- | |
| # Monte-Carlo-Verfahren | |
| Monte-Carlo-Verfahren nutzen Zufallsstichproben. | |
| Anwendungen: | |
| - Simulation, | |
| - Risikoanalyse, | |
| - numerische Integration, | |
| - Bayesianische Methoden. | |
| --- | |
| # Approximation Algorithms | |
| Einige Optimierungsprobleme sind so schwierig, dass exakte Lösungen für große Eingaben unpraktisch sind. | |
| Approximation Algorithms liefern Lösungen mit garantierter Nähe zum Optimum. | |
| Sie sind besonders wichtig für kombinatorische Optimierung. | |
| --- | |
| # Heuristische Optimierung | |
| Heuristiken suchen gute Lösungen ohne Garantie auf das globale Optimum. | |
| Beispiele: | |
| - Genetic Algorithms, | |
| - Simulated Annealing, | |
| - Tabu Search. | |
| Sie werden häufig genutzt, wenn der Suchraum extrem groß ist. | |
| --- | |
| # Algorithmen in Datenbanken | |
| Datenbanken verwenden Algorithmen für: | |
| - Indexierung, | |
| - Sortierung, | |
| - Join Planning, | |
| - Query Optimization, | |
| - Caching. | |
| Die Wahl des Query Plans kann große Auswirkungen auf Performance haben. | |
| --- | |
| # Algorithmen in Suchmaschinen | |
| Suchmaschinen kombinieren viele Verfahren: | |
| - Crawling, | |
| - Indexierung, | |
| - Ranking, | |
| - Retrieval, | |
| - deduplication, | |
| - semantische Suche. | |
| Moderne Suchsysteme kombinieren klassische Algorithmen mit Machine Learning und Embeddings. | |
| --- | |
| # Algorithmen in Empfehlungssystemen | |
| Empfehlungssysteme verwenden unter anderem: | |
| - Collaborative Filtering, | |
| - Content-Based Filtering, | |
| - Matrix Factorization, | |
| - Ranking, | |
| - Deep Learning. | |
| Sie optimieren häufig nicht nur auf Klicks, sondern auf mehrere Zielgrößen. | |
| --- | |
| # Machine-Learning-Algorithmen | |
| Machine Learning umfasst viele Algorithmen. | |
| Beispiele: | |
| - Linear Regression, | |
| - Logistic Regression, | |
| - Decision Trees, | |
| - Random Forest, | |
| - Gradient Boosting, | |
| - Support Vector Machines, | |
| - k-Nearest Neighbors, | |
| - k-Means, | |
| - Neural Networks. | |
| --- | |
| # Entscheidungsbäume | |
| Decision Trees treffen Entscheidungen über aufeinanderfolgende Regeln. | |
| Vorteile: | |
| - gut interpretierbar, | |
| - funktionieren für numerische und kategorische Daten. | |
| Nachteile: | |
| - können overfitten. | |
| --- | |
| # Random Forest | |
| Random Forest kombiniert viele Entscheidungsbäume. | |
| Vorteile: | |
| - robust, | |
| - gute Baseline für viele tabellarische Probleme. | |
| --- | |
| # Gradient Boosting | |
| Gradient Boosting baut Modelle schrittweise auf. | |
| Bekannte Varianten: | |
| - XGBoost, | |
| - LightGBM, | |
| - CatBoost. | |
| Sie sind besonders stark bei strukturierten tabellarischen Daten. | |
| --- | |
| # k-Nearest Neighbors | |
| k-NN klassifiziert oder schätzt anhand ähnlicher Beispiele. | |
| Vorteile: | |
| - einfach, | |
| - keine komplexe Trainingsphase. | |
| Nachteile: | |
| - kann bei großen Datenmengen teuer werden. | |
| --- | |
| # k-Means | |
| k-Means ist ein Clustering-Algorithmus. | |
| Er teilt Daten in k Cluster. | |
| Der Algorithmus optimiert die Abstände zu Clusterzentren. | |
| --- | |
| # Neuronale Netze | |
| Neuronale Netze bestehen aus vielen parametrisierten Recheneinheiten. | |
| Training erfolgt typischerweise über: | |
| - Forward Pass, | |
| - Loss, | |
| - Backpropagation, | |
| - Optimizer. | |
| --- | |
| # Backpropagation | |
| Backpropagation berechnet, wie stark einzelne Parameter zum Fehler beitragen. | |
| Diese Gradienten werden genutzt, um Modellgewichte anzupassen. | |
| Backpropagation ist eine zentrale Grundlage moderner Deep-Learning-Systeme. | |
| --- | |
| # Attention | |
| Attention berechnet, welche Teile einer Eingabe für eine bestimmte Verarbeitung besonders relevant sind. | |
| Self-Attention ist ein Kernbestandteil von Transformer-Modellen. | |
| --- | |
| # Transformer als Algorithmussystem | |
| Transformer sind keine einzelne einfache Prozedur. | |
| Sie kombinieren mehrere algorithmische Bausteine: | |
| - Tokenisierung, | |
| - Embeddings, | |
| - Attention, | |
| - Matrixoperationen, | |
| - Normalisierung, | |
| - Sampling. | |
| Große Sprachmodelle bauen auf diesen Mechanismen auf. | |
| --- | |
| # Algorithmen in Generativer KI | |
| Generative KI nutzt Algorithmen für: | |
| - Token Sampling, | |
| - Decoding, | |
| - Beam Search, | |
| - Temperature, | |
| - Top-k Sampling, | |
| - Top-p Sampling. | |
| Diese Verfahren beeinflussen, wie ein Modell seine Ausgabe erzeugt. | |
| --- | |
| # Greedy Decoding | |
| Greedy Decoding wählt jeweils das wahrscheinlichste nächste Token. | |
| Vorteil: | |
| - deterministisch und einfach. | |
| Nachteil: | |
| - kann zu weniger vielfältigen Ausgaben führen. | |
| --- | |
| # Beam Search | |
| Beam Search hält mehrere Kandidaten gleichzeitig. | |
| Er wird häufig bei Sequenzaufgaben eingesetzt. | |
| --- | |
| # Top-k Sampling | |
| Top-k betrachtet nur die k wahrscheinlichsten Tokens. | |
| Dadurch wird die Auswahl eingeschränkt. | |
| --- | |
| # Top-p Sampling | |
| Top-p, auch Nucleus Sampling, betrachtet die kleinste Tokenmenge, deren kumulierte Wahrscheinlichkeit einen Schwellenwert erreicht. | |
| Das ermöglicht dynamischere Auswahl als ein fixes k. | |
| --- | |
| # Algorithmen in RAG | |
| Retrieval-Augmented Generation nutzt algorithmische Komponenten für: | |
| - Chunking, | |
| - Embeddings, | |
| - Similarity Search, | |
| - Reranking, | |
| - Context Selection. | |
| Die Qualität eines RAG-Systems hängt stark von diesen Verfahren ab. | |
| --- | |
| # Similarity Search | |
| Semantische Suche verwendet häufig: | |
| - Cosine Similarity, | |
| - Dot Product, | |
| - Euclidean Distance. | |
| Diese Maße vergleichen Vektoren. | |
| --- | |
| # Approximate Nearest Neighbor | |
| Bei sehr großen Vektormengen ist exakte Suche teuer. | |
| ANN-Verfahren liefern sehr ähnliche Nachbarn deutlich schneller. | |
| Beispiele: | |
| - HNSW, | |
| - IVF, | |
| - Product Quantization. | |
| --- | |
| # Algorithmen in KI-Agenten | |
| KI-Agenten benötigen algorithmische Strukturen für: | |
| - Planning, | |
| - Routing, | |
| - Tool Selection, | |
| - Memory, | |
| - State Management, | |
| - Search, | |
| - Scheduling, | |
| - Evaluation. | |
| Agenten sind damit ein gutes Beispiel dafür, wie klassische Algorithmen und moderne KI zusammenkommen. | |
| --- | |
| # Planning | |
| Planning sucht nach einer Folge von Aktionen, die ein Ziel erreicht. | |
| Klassische KI nutzt hierfür unter anderem: | |
| - State Space Search, | |
| - Heuristics, | |
| - A*, | |
| - Constraint Solving. | |
| Moderne Agenten kombinieren solche Prinzipien mit Sprachmodellen. | |
| --- | |
| # Routing | |
| Routing wählt die passende Komponente. | |
| Beispiele: | |
| - Modell, | |
| - Tool, | |
| - Agent, | |
| - Datenquelle. | |
| Routing kann regelbasiert, statistisch oder modellgestützt erfolgen. | |
| --- | |
| # Scheduling | |
| Scheduling bestimmt, wann und in welcher Reihenfolge Aufgaben ausgeführt werden. | |
| Anwendungen: | |
| - Betriebssysteme, | |
| - Cloud Computing, | |
| - Produktionsplanung, | |
| - Agentenorchestrierung. | |
| --- | |
| # Reinforcement Learning | |
| Reinforcement Learning optimiert Entscheidungen über Belohnungssignale. | |
| Ein Agent beobachtet: | |
| - Zustand, | |
| - Aktion, | |
| - Reward, | |
| - nächsten Zustand. | |
| Ziel ist eine Strategie, die langfristig hohe Belohnung erzielt. | |
| --- | |
| # Exploration vs. Exploitation | |
| Reinforcement Learning muss zwischen zwei Strategien abwägen: | |
| ## Exploration | |
| Neue Aktionen ausprobieren. | |
| ## Exploitation | |
| Bekannte gute Aktionen nutzen. | |
| Dieser Trade-off ist ein zentrales algorithmisches Problem. | |
| --- | |
| # Algorithmen und AGI | |
| Auch zukünftige allgemeinere KI-Systeme werden algorithmische Mechanismen benötigen. | |
| Mögliche Bereiche: | |
| - Planung, | |
| - Suche, | |
| - Memory, | |
| - Tool Use, | |
| - Ressourcenallokation, | |
| - Selbstoptimierung, | |
| - Multi-Agent-Koordination. | |
| Der Begriff Algorithmus verliert durch leistungsfähigere KI deshalb nicht an Bedeutung. | |
| Im Gegenteil: Je komplexer KI-Systeme werden, desto wichtiger werden algorithmische Kontrolle, Effizienz und Verifikation. | |
| --- | |
| # Algorithm Engineering | |
| Algorithm Engineering verbindet Theorie und praktische Umsetzung. | |
| Ein theoretisch guter Algorithmus kann in realer Software schlechter sein, wenn: | |
| - Speicherzugriffe ungünstig sind, | |
| - Parallelisierung fehlt, | |
| - Datenstruktur nicht passt, | |
| - Cache-Verhalten schlecht ist. | |
| Praktische Performance hängt deshalb auch von Implementierungsdetails ab. | |
| --- | |
| # Parallel Algorithms | |
| Parallel Algorithms verteilen Arbeit auf mehrere Recheneinheiten. | |
| Anwendungen: | |
| - GPUs, | |
| - Multicore CPUs, | |
| - Distributed Systems. | |
| Wichtige Fragen: | |
| - Welche Schritte sind unabhängig? | |
| - Wie hoch ist Synchronisationsaufwand? | |
| - Wie werden Daten verteilt? | |
| --- | |
| # Distributed Algorithms | |
| Verteilte Algorithmen laufen auf mehreren Systemen. | |
| Themen: | |
| - Konsens, | |
| - Replikation, | |
| - Fehlertoleranz, | |
| - Leader Election, | |
| - verteilte Locks. | |
| Sie sind zentral für Cloud- und Datenbanksysteme. | |
| --- | |
| # Algorithmen und Skalierbarkeit | |
| Ein Algorithmus kann funktional korrekt und trotzdem nicht skalierbar sein. | |
| Skalierbarkeit hängt ab von: | |
| - Laufzeit, | |
| - Speicher, | |
| - Parallelisierung, | |
| - Netzwerk, | |
| - Datenvolumen. | |
| Deshalb sollten Algorithmen immer im Kontext realer Systemgrenzen bewertet werden. | |
| --- | |
| # Häufige Fehler beim Algorithmusdesign | |
| ## Zu früh optimieren | |
| Eine komplexe Optimierung ist nicht sinnvoll, wenn das Problem noch unklar ist. | |
| ## Falsche Datenstruktur | |
| Ein guter Algorithmus kann durch eine ungeeignete Datenstruktur ausgebremst werden. | |
| ## Randfälle ignorieren | |
| Leere Listen, doppelte Werte oder ungültige Eingaben müssen berücksichtigt werden. | |
| ## Worst Case ignorieren | |
| Durchschnittlich gute Performance reicht nicht immer. | |
| ## Keine Messung | |
| Theoretische Komplexität ersetzt keine Benchmarks. | |
| --- | |
| # Benchmarking | |
| Benchmarks messen reale Performance. | |
| Wichtige Faktoren: | |
| - Eingabegröße, | |
| - Datenverteilung, | |
| - Hardware, | |
| - Compiler, | |
| - Warmup, | |
| - Speicher. | |
| Gute Benchmarks sollten reproduzierbar sein. | |
| --- | |
| # Profiling | |
| Profiling zeigt, wo ein Programm tatsächlich Zeit oder Speicher verbraucht. | |
| Typische Fragen: | |
| - Welche Funktion ist langsam? | |
| - Wo entstehen viele Allokationen? | |
| - Welche Schleife dominiert? | |
| Profiling verhindert Optimierung an der falschen Stelle. | |
| --- | |
| # Algorithmische Fairness | |
| Algorithmen können Entscheidungen beeinflussen. | |
| Besonders bei datengetriebenen Modellen sind wichtig: | |
| - Bias, | |
| - Datenrepräsentation, | |
| - Zielmetriken, | |
| - Schwellenwerte. | |
| Fairness ist deshalb nicht nur ein Modellthema, sondern auch eine algorithmische Designfrage. | |
| --- | |
| # Algorithmische Transparenz | |
| Transparenz bedeutet, dass nachvollziehbar ist: | |
| - welche Eingaben verwendet werden, | |
| - welche Regeln gelten, | |
| - welche Ziele optimiert werden, | |
| - welche Grenzen bestehen. | |
| Bei komplexen Systemen kann vollständige Erklärbarkeit schwierig sein. | |
| Trotzdem sollte der Systemprozess dokumentiert sein. | |
| --- | |
| # Algorithmische Sicherheit | |
| Algorithmen können Sicherheitsrisiken erzeugen, wenn sie: | |
| - unkontrolliert Ressourcen verbrauchen, | |
| - sensible Daten offenlegen, | |
| - unerwartete Eingaben falsch behandeln. | |
| Sicheres Algorithmusdesign berücksichtigt: | |
| - Input Validation, | |
| - Limits, | |
| - Timeouts, | |
| - Fail-Safe-Verhalten. | |
| --- | |
| # Auswahl des richtigen Algorithmus | |
| Die Wahl hängt ab von: | |
| - Problemgröße, | |
| - Eingabeformat, | |
| - benötigter Genauigkeit, | |
| - Echtzeitanforderungen, | |
| - Speicher, | |
| - Skalierbarkeit, | |
| - Implementierungsaufwand. | |
| Es gibt selten einen universell besten Algorithmus. | |
| --- | |
| # Ein Algorithmus-Workflow | |
| Ein robuster Prozess: | |
| 1. Problem präzise definieren. | |
| 2. Eingabe und Ausgabe beschreiben. | |
| 3. Randfälle identifizieren. | |
| 4. Datenstruktur auswählen. | |
| 5. Lösungsstrategie entwerfen. | |
| 6. Korrektheit begründen. | |
| 7. Komplexität analysieren. | |
| 8. implementieren. | |
| 9. testen. | |
| 10. benchmarken. | |
| --- | |
| # Checkliste für Algorithmen | |
| Vor produktivem Einsatz: | |
| 1. Ist das Problem klar definiert? | |
| 2. Ist der Algorithmus korrekt? | |
| 3. Terminiert er? | |
| 4. Sind Randfälle getestet? | |
| 5. Ist die Laufzeit bekannt? | |
| 6. Ist der Speicherbedarf bekannt? | |
| 7. Passt die Datenstruktur? | |
| 8. Gibt es schnellere Alternativen? | |
| 9. Ist das Verhalten reproduzierbar? | |
| 10. Wurde auf realistischen Daten gemessen? | |
| --- | |
| # Entscheidbarkeit und Berechenbarkeit | |
| Nicht jedes mathematisch formulierte Problem lässt sich durch einen Algorithmus vollständig lösen. | |
| Die theoretische Informatik untersucht deshalb grundlegende Fragen: | |
| - Welche Probleme sind überhaupt berechenbar? | |
| - Welche Probleme sind entscheidbar? | |
| - Welche Probleme sind zwar entscheidbar, aber praktisch extrem teuer? | |
| Diese Fragen sind wichtig, weil sie Grenzen algorithmischer Systeme sichtbar machen. | |
| # Entscheidbare Probleme | |
| Ein Entscheidungsproblem fragt nach einer Ja-Nein-Antwort. | |
| Beispiel: | |
| > Existiert in diesem Graphen ein Pfad von A nach B? | |
| Ein Problem ist entscheidbar, wenn es einen Algorithmus gibt, der für jede gültige Eingabe nach endlicher Zeit eine korrekte Antwort liefert. | |
| # Unentscheidbare Probleme | |
| Manche Probleme sind grundsätzlich nicht algorithmisch vollständig entscheidbar. | |
| Ein bekanntes theoretisches Beispiel ist das Halteproblem. | |
| Es fragt vereinfacht: | |
| > Kann man für jedes beliebige Programm und jede Eingabe immer entscheiden, ob das Programm irgendwann stoppt? | |
| Für das allgemeine Halteproblem existiert kein Algorithmus, der diese Frage für alle möglichen Programme korrekt beantworten kann. | |
| Solche Resultate zeigen, dass es fundamentale Grenzen von Berechnung gibt. | |
| # Komplexitätsklassen | |
| Neben der Frage, ob ein Problem lösbar ist, interessiert, wie aufwendig die Lösung ist. | |
| Dafür verwendet die theoretische Informatik Komplexitätsklassen. | |
| # P | |
| P enthält vereinfacht Entscheidungsprobleme, die von einem deterministischen Rechner in polynomialer Zeit gelöst werden können. | |
| Polynomiale Laufzeiten wie: | |
| - O(n) | |
| - O(n²) | |
| - O(n³) | |
| gelten theoretisch als skalierbarer als exponentielle Laufzeiten. | |
| # NP | |
| NP enthält Entscheidungsprobleme, bei denen eine gegebene Lösung in polynomialer Zeit überprüft werden kann. | |
| Die zentrale offene Frage lautet: | |
| > Ist P = NP? | |
| Bis heute ist nicht bekannt, ob jedes Problem, dessen Lösung schnell überprüfbar ist, auch schnell gefunden werden kann. | |
| # NP-schwere Probleme | |
| NP-hard bezeichnet Probleme, die mindestens so schwierig sind wie die schwierigsten Probleme in NP. | |
| Viele wichtige Optimierungsprobleme gehören in diese Kategorie oder stehen in enger Beziehung dazu. | |
| Beispiele: | |
| - Traveling Salesperson Problem, | |
| - bestimmte Scheduling-Probleme, | |
| - kombinatorische Optimierung. | |
| In der Praxis verwendet man deshalb häufig: | |
| - Approximation, | |
| - Heuristiken, | |
| - Branch and Bound, | |
| - Metaheuristiken. | |
| # Das Traveling Salesperson Problem | |
| Das Traveling Salesperson Problem fragt: | |
| > Was ist die kürzeste Route, die alle Orte genau besucht und zum Start zurückkehrt? | |
| Für wenige Orte ist exakte Suche möglich. | |
| Mit wachsender Anzahl steigt der Suchraum jedoch extrem schnell. | |
| Das Problem ist deshalb ein klassisches Beispiel für kombinatorische Komplexität. | |
| # String-Algorithmen | |
| Viele Systeme verarbeiten Texte und Zeichenfolgen. | |
| String-Algorithmen werden eingesetzt für: | |
| - Suche, | |
| - Parsing, | |
| - Bioinformatik, | |
| - Compiler, | |
| - Textverarbeitung, | |
| - Suchmaschinen. | |
| # Naive String Search | |
| Die einfachste Textsuche vergleicht ein Muster an jeder möglichen Position. | |
| Sie ist leicht zu implementieren, kann bei langen Texten aber ineffizient sein. | |
| # Knuth-Morris-Pratt | |
| KMP vermeidet unnötige Wiederholungsvergleiche. | |
| Dazu wird eine Präfixstruktur des Suchmusters vorbereitet. | |
| Die Idee: | |
| Wenn ein Teil des Musters bereits bekannt ist, muss die Suche nicht vollständig zurückspringen. | |
| # Rabin-Karp | |
| Rabin-Karp verwendet Hashwerte für Teilstrings. | |
| Das ist besonders interessant, wenn mehrere Muster gesucht werden. | |
| # Trie | |
| Ein Trie speichert Zeichenfolgen über gemeinsame Präfixe. | |
| Anwendungen: | |
| - Autocomplete, | |
| - Wörterbücher, | |
| - Präfixsuche, | |
| - Routing. | |
| # Edit Distance | |
| Die Edit Distance misst, wie viele Operationen nötig sind, um eine Zeichenfolge in eine andere umzuwandeln. | |
| Typische Operationen: | |
| - Einfügen, | |
| - Löschen, | |
| - Ersetzen. | |
| Anwendungen: | |
| - Rechtschreibkorrektur, | |
| - Ähnlichkeit, | |
| - Bioinformatik, | |
| - Record Matching. | |
| # Sequenzalgorithmen | |
| Sequenzprobleme treten in vielen Bereichen auf. | |
| Ein klassisches Beispiel ist die **Longest Common Subsequence**. | |
| Dynamic Programming kann solche Probleme effizienter lösen als naive vollständige Suche. | |
| # Algorithmen für Mengen | |
| Mengenoperationen sind grundlegende Bausteine. | |
| Typische Operationen: | |
| - Union, | |
| - Intersection, | |
| - Difference, | |
| - Membership. | |
| Geeignete Datenstrukturen sind: | |
| - Hash Sets, | |
| - Balanced Trees, | |
| - Bitsets. | |
| # Union-Find | |
| Union-Find, auch Disjoint Set Union, verwaltet dynamische Mengen. | |
| Wichtige Operationen: | |
| - find, | |
| - union. | |
| Anwendungen: | |
| - Connected Components, | |
| - Kruskal, | |
| - Netzwerkprobleme. | |
| Optimierungen wie: | |
| - Path Compression, | |
| - Union by Rank | |
| machen Union-Find sehr effizient. | |
| # Bloom Filter | |
| Bloom Filter sind probabilistische Datenstrukturen. | |
| Sie beantworten schnell die Frage: | |
| > Ist dieses Element möglicherweise in einer Menge enthalten? | |
| Ein Bloom Filter kann False Positives liefern, aber keine False Negatives. | |
| Anwendungen: | |
| - Caches, | |
| - Datenbanken, | |
| - verteilte Systeme. | |
| # Algorithmen in verteilten Systemen | |
| Verteilte Systeme benötigen spezielle algorithmische Verfahren. | |
| Probleme entstehen durch: | |
| - Netzwerkverzögerung, | |
| - Teilausfälle, | |
| - parallele Änderungen, | |
| - fehlende globale Uhr. | |
| # Konsensalgorithmen | |
| Konsens bedeutet, dass mehrere Knoten sich auf einen gemeinsamen Zustand einigen. | |
| Bekannte Verfahren: | |
| - Paxos, | |
| - Raft. | |
| Konsens ist zentral für: | |
| - verteilte Datenbanken, | |
| - Cluster, | |
| - Replikation. | |
| # Leader Election | |
| Leader Election bestimmt einen Koordinator in einem verteilten System. | |
| Der Leader kann beispielsweise: | |
| - Writes koordinieren, | |
| - Jobs verteilen, | |
| - Replikation steuern. | |
| # Replikation | |
| Replikation speichert Daten mehrfach. | |
| Ziele: | |
| - Ausfallsicherheit, | |
| - Verfügbarkeit, | |
| - Performance. | |
| Algorithmische Herausforderungen: | |
| - Konsistenz, | |
| - Konflikte, | |
| - Reihenfolge von Änderungen. | |
| # Hashing | |
| Hashfunktionen bilden Eingaben auf kompakte Werte ab. | |
| Anwendungen: | |
| - Hash Tables, | |
| - Checksums, | |
| - Caches, | |
| - Datenverteilung. | |
| Eine gute Hashfunktion verteilt Eingaben möglichst gleichmäßig. | |
| # Consistent Hashing | |
| Consistent Hashing verteilt Schlüssel auf mehrere Server. | |
| Vorteil: | |
| Wenn Server hinzukommen oder entfernt werden, müssen nur relativ wenige Schlüssel neu verteilt werden. | |
| Anwendungen: | |
| - Distributed Caches, | |
| - Sharding, | |
| - verteilte Datenbanken. | |
| # Algorithmen in Kryptografie | |
| Kryptografische Systeme verwenden spezialisierte Algorithmen. | |
| Bereiche: | |
| - Verschlüsselung, | |
| - Hashing, | |
| - digitale Signaturen, | |
| - Schlüsselaustausch. | |
| Kryptografie ist ein eigenes tiefes Fachgebiet. Für Algorithm Engineering ist wichtig, kryptografische Primitive nicht selbst improvisiert neu zu erfinden. | |
| # Numerische Algorithmen | |
| Numerische Verfahren lösen mathematische Probleme näherungsweise. | |
| Beispiele: | |
| - Nullstellensuche, | |
| - lineare Gleichungssysteme, | |
| - numerische Integration, | |
| - Differentialgleichungen. | |
| Dabei spielen zusätzlich zur Laufzeit auch numerische Stabilität und Rundungsfehler eine wichtige Rolle. | |
| # Binäre Suche auf Antworten | |
| Binäre Suche kann nicht nur Elemente suchen. | |
| Sie kann auch einen Wertebereich durchsuchen, wenn eine monotone Bedingung existiert. | |
| Beispiel: | |
| > Was ist die kleinste Kapazität, mit der ein Prozess innerhalb eines Limits abgeschlossen werden kann? | |
| Dieses Muster wird häufig in Optimierungsaufgaben verwendet. | |
| # Two-Pointer-Technik | |
| Two Pointer verwendet zwei Indizes, die sich durch Daten bewegen. | |
| Typische Anwendungen: | |
| - sortierte Arrays, | |
| - Paar-Suche, | |
| - Fensterprobleme, | |
| - Duplikaterkennung. | |
| Die Technik kann naive O(n²)-Lösungen häufig auf O(n) reduzieren. | |
| # Sliding Window | |
| Sliding Window verarbeitet zusammenhängende Bereiche einer Sequenz. | |
| Anwendungen: | |
| - maximale Summe über k Elemente, | |
| - längstes Teilstück mit bestimmten Eigenschaften, | |
| - Streaming-Analysen. | |
| Statt jedes Fenster vollständig neu zu berechnen, wird der Zustand inkrementell aktualisiert. | |
| # Prefix Sums | |
| Prefix Sums speichern kumulative Summen. | |
| Dadurch können Bereichssummen später sehr schnell berechnet werden. | |
| Vorbereitung: | |
| **O(n)** | |
| Bereichsabfrage: | |
| häufig **O(1)** | |
| Dieses Muster zeigt, wie Precomputation spätere Abfragen beschleunigen kann. | |
| # Memoization | |
| Memoization speichert Ergebnisse bereits berechneter Funktionsaufrufe. | |
| Sie wird häufig mit Rekursion kombiniert. | |
| Besonders nützlich bei: | |
| - Dynamic Programming, | |
| - rekursiven Suchproblemen, | |
| - teuren wiederkehrenden Berechnungen. | |
| # Caching als Algorithmusstrategie | |
| Caching ist nicht nur Infrastruktur. | |
| Es ist auch eine algorithmische Strategie. | |
| Ein System speichert teure Ergebnisse, um spätere Zugriffe zu beschleunigen. | |
| Wichtige Fragen: | |
| - Was wird gecacht? | |
| - Wie lange? | |
| - Wann wird invalidiert? | |
| - Wie groß darf der Cache werden? | |
| Cache Invalidation gehört zu den schwierigeren praktischen Problemen verteilter Systeme. | |
| # Online Algorithms | |
| Online Algorithms müssen Entscheidungen treffen, bevor alle zukünftigen Eingaben bekannt sind. | |
| Beispiele: | |
| - Scheduling, | |
| - Streaming, | |
| - Ressourcenallokation. | |
| Sie unterscheiden sich von Offline-Algorithmen, die alle Daten im Voraus kennen. | |
| # Streaming Algorithms | |
| Streaming Algorithms verarbeiten Datenströme, ohne alle Daten dauerhaft zu speichern. | |
| Anwendungen: | |
| - Telemetrie, | |
| - Event Streams, | |
| - Netzwerkdaten, | |
| - Echtzeitanalyse. | |
| Wichtige Ziele: | |
| - geringer Speicher, | |
| - inkrementelle Verarbeitung, | |
| - niedrige Latenz. | |
| # Approximate Counting | |
| Bei sehr großen Streams können exakte Berechnungen teuer sein. | |
| Probabilistische Datenstrukturen erlauben Näherungen mit sehr geringem Speicher. | |
| Beispiele: | |
| - HyperLogLog, | |
| - Count-Min Sketch. | |
| # HyperLogLog | |
| HyperLogLog schätzt die Anzahl unterschiedlicher Elemente. | |
| Anwendung: | |
| - Unique Visitors, | |
| - große Event Streams, | |
| - verteilte Analysen. | |
| Es benötigt deutlich weniger Speicher als das Speichern aller eindeutigen Werte. | |
| # Count-Min Sketch | |
| Count-Min Sketch schätzt Häufigkeiten in Datenströmen. | |
| Anwendungen: | |
| - Heavy Hitters, | |
| - Netzwerkverkehr, | |
| - große Ereignisströme. | |
| # External Memory Algorithms | |
| Wenn Daten nicht vollständig in den Arbeitsspeicher passen, wird I/O zu einem zentralen Kostenfaktor. | |
| External-Memory-Algorithmen optimieren deshalb: | |
| - Disk Reads, | |
| - Blockzugriffe, | |
| - Datenlayout. | |
| Ein Beispiel ist External Merge Sort. | |
| # Cache-Aware und Cache-Oblivious Algorithms | |
| Moderne Prozessoren besitzen mehrere Cache-Ebenen. | |
| Algorithm Engineering kann Speicherzugriffe so strukturieren, dass Daten möglichst effizient genutzt werden. | |
| Das zeigt, dass reale Performance nicht nur von Big O abhängt. | |
| # Approximation vs. Exaktheit | |
| Nicht jedes Problem benötigt eine exakte Lösung. | |
| Praktische Systeme müssen häufig abwägen zwischen: | |
| - Genauigkeit, | |
| - Laufzeit, | |
| - Kosten, | |
| - Reaktionszeit. | |
| Bei Echtzeitsystemen kann eine sehr gute Näherung wertvoller sein als ein theoretisch perfektes Ergebnis, das zu spät kommt. | |
| # Deterministische und probabilistische Algorithmen | |
| ## Deterministisch | |
| Gleiche Eingabe erzeugt bei gleichem Zustand denselben Ablauf. | |
| ## Probabilistisch | |
| Zufall beeinflusst den Ablauf oder das Ergebnis. | |
| Probabilistische Verfahren sind wichtig in: | |
| - Sampling, | |
| - Approximation, | |
| - Machine Learning, | |
| - Simulation. | |
| # Algorithmen testen | |
| Algorithmen sollten systematisch getestet werden. | |
| Testfälle: | |
| - normale Fälle, | |
| - minimale Eingabe, | |
| - maximale Eingabe, | |
| - leere Eingabe, | |
| - doppelte Werte, | |
| - sortierte Eingabe, | |
| - umgekehrt sortierte Eingabe, | |
| - zufällige Eingabe. | |
| Zusätzlich sind Property-Based Tests nützlich. | |
| # Property-Based Testing | |
| Property-Based Testing prüft allgemeine Eigenschaften. | |
| Beispiel Sortierung: | |
| - Ausgabe ist sortiert. | |
| - Ausgabe enthält dieselben Elemente wie Eingabe. | |
| - Sortieren einer bereits sortierten Ausgabe verändert nichts. | |
| Solche Eigenschaften können viele zufällig erzeugte Testfälle abdecken. | |
| # Formale Verifikation | |
| Formale Verifikation versucht mathematisch zu zeigen, dass ein Algorithmus oder Programm bestimmte Eigenschaften erfüllt. | |
| Sie ist besonders relevant für: | |
| - sicherheitskritische Systeme, | |
| - Protokolle, | |
| - Kryptografie, | |
| - Hardware. | |
| # Invarianten | |
| Eine Invariante ist eine Eigenschaft, die während eines Algorithmus erhalten bleibt. | |
| Invarianten helfen bei: | |
| - Korrektheitsbeweisen, | |
| - Debugging, | |
| - formaler Verifikation. | |
| # Algorithmen visualisieren | |
| Visualisierung kann komplexe Abläufe verständlicher machen. | |
| Beispiele: | |
| - Sortierschritte, | |
| - Graphdurchläufe, | |
| - Heap-Operationen, | |
| - Dynamic-Programming-Tabellen. | |
| Interaktive Visualisierung ist besonders geeignet für Lern- und Referenzsysteme. | |
| # Algorithmische Auswahl in AI Systems | |
| Moderne KI-Systeme bestehen aus vielen Entscheidungen, die algorithmisch optimiert werden können. | |
| Beispiele: | |
| - welches Modell wird geroutet, | |
| - welche Dokumente werden retrieved, | |
| - welche Tools werden priorisiert, | |
| - wie werden Agenten geplant, | |
| - wann wird eskaliert. | |
| Dadurch verschiebt sich Algorithmusdesign zunehmend von einzelnen Funktionen zu ganzen AI-Systempipelines. | |
| # Algorithmische Effizienz bei LLMs | |
| Large Language Models erzeugen neue algorithmische Herausforderungen. | |
| Relevante Themen: | |
| - Attention-Komplexität, | |
| - KV Cache, | |
| - Batching, | |
| - Speculative Decoding, | |
| - Quantisierung, | |
| - Parallelisierung. | |
| Effizienzalgorithmen entscheiden mit darüber, ob große Modelle praktisch und wirtschaftlich nutzbar sind. | |
| # Algorithmen und World Models | |
| World Models versuchen, Zustände und Dynamik einer Umgebung abzubilden. | |
| Algorithmische Komponenten können umfassen: | |
| - State Estimation, | |
| - Planning, | |
| - Search, | |
| - Simulation, | |
| - Optimization. | |
| Damit verbinden sich klassische KI-Algorithmen mit modernen generativen Modellen. | |
| # Algorithmen und autonome Systeme | |
| Autonome Systeme müssen ständig Entscheidungen treffen. | |
| Sie benötigen Algorithmen für: | |
| - Wahrnehmung, | |
| - Planung, | |
| - Kontrolle, | |
| - Fehlerbehandlung, | |
| - Priorisierung. | |
| Je höher die Autonomie, desto wichtiger werden überprüfbare und robuste algorithmische Komponenten. | |
| # Zukunft von Algorithmen | |
| Algorithmen bleiben auch in einer Zukunft mit sehr leistungsfähiger KI fundamental. | |
| Modelle können Algorithmen automatisch erzeugen, auswählen oder verbessern. Trotzdem bleibt die Frage: | |
| - Ist der Algorithmus korrekt? | |
| - Ist er effizient? | |
| - Ist er sicher? | |
| - Ist er skalierbar? | |
| - Ist er nachvollziehbar? | |
| Mit zunehmender KI-Fähigkeit dürfte **automatisches Algorithm Design** wichtiger werden. | |
| KI-Systeme könnten: | |
| - neue Heuristiken entdecken, | |
| - Implementierungen optimieren, | |
| - Suchstrategien anpassen, | |
| - Algorithmen benchmarken. | |
| Dadurch wird Algorithmik nicht weniger wichtig, sondern stärker mit KI-Forschung und Software Engineering verschmelzen. | |
| # Typische Interview- und Lernmuster | |
| Viele algorithmische Aufgaben lassen sich auf wiederkehrende Muster zurückführen. | |
| Dazu gehören: | |
| - Hash Map, | |
| - Two Pointer, | |
| - Sliding Window, | |
| - Binary Search, | |
| - Stack, | |
| - Queue, | |
| - BFS, | |
| - DFS, | |
| - Heap, | |
| - Dynamic Programming, | |
| - Greedy, | |
| - Backtracking. | |
| Das Erkennen des Musters ist oft wichtiger als das Auswendiglernen einzelner Lösungen. | |
| # Algorithmuswahl als Engineering-Entscheidung | |
| In der Praxis zählt nicht nur theoretische Eleganz. | |
| Eine gute Lösung berücksichtigt: | |
| - Entwicklungszeit, | |
| - Wartbarkeit, | |
| - Teamwissen, | |
| - Performance, | |
| - Betriebskosten, | |
| - Risiko. | |
| Ein theoretisch minimal besserer Algorithmus kann praktisch schlechter sein, wenn er deutlich komplizierter zu warten ist. | |
| # Einfache Lösung zuerst | |
| Ein guter Engineering-Ansatz ist häufig: | |
| 1. korrekte einfache Lösung bauen, | |
| 2. messen, | |
| 3. Engpass identifizieren, | |
| 4. gezielt optimieren. | |
| Das verhindert unnötige Komplexität. | |
| # Wann braucht man keinen komplexen Algorithmus? | |
| Nicht jedes Problem benötigt eine hochoptimierte Lösung. | |
| Wenn: | |
| - Datenmenge klein ist, | |
| - Prozess selten ausgeführt wird, | |
| - Laufzeit bereits ausreichend ist, | |
| kann eine einfache O(n²)-Lösung besser sein als eine schwer wartbare komplexe Alternative. | |
| Algorithmische Qualität bedeutet deshalb nicht automatisch maximale theoretische Optimierung. | |
| # Häufige Fragen zu Algorithmen | |
| ## Was ist ein Algorithmus? | |
| Ein Algorithmus ist eine eindeutige, endliche Folge von Schritten zur Lösung eines Problems. | |
| ## Was ist ein Algorithmus einfach erklärt? | |
| Ein Algorithmus ist wie ein Rezept für einen Computer: Er beschreibt, welche Schritte in welcher Reihenfolge ausgeführt werden. | |
| ## Was ist der Unterschied zwischen Algorithmus und Programm? | |
| Der Algorithmus beschreibt die Logik. Das Programm ist die konkrete Implementierung. | |
| ## Was ist Big O? | |
| Big O beschreibt, wie Laufzeit oder Speicherbedarf mit der Eingabegröße wachsen. | |
| ## Was bedeutet O(n)? | |
| Der Aufwand wächst ungefähr linear mit der Anzahl der Elemente. | |
| ## Was bedeutet O(log n)? | |
| Der Aufwand wächst logarithmisch. Binäre Suche ist ein typisches Beispiel. | |
| ## Was ist ein Sortieralgorithmus? | |
| Ein Algorithmus, der Elemente in eine definierte Reihenfolge bringt. | |
| ## Was ist ein Suchalgorithmus? | |
| Ein Verfahren, das ein Element, einen Zustand oder eine Lösung findet. | |
| ## Was ist Dynamic Programming? | |
| Eine Methode, die Ergebnisse wiederkehrender Teilprobleme speichert. | |
| ## Was ist ein Greedy Algorithm? | |
| Ein Verfahren, das in jedem Schritt die lokal beste Entscheidung trifft. | |
| ## Was ist Backtracking? | |
| Eine Suchstrategie, die Möglichkeiten ausprobiert und bei Sackgassen zurückgeht. | |
| ## Was ist ein Graphalgorithmus? | |
| Ein Algorithmus zur Verarbeitung von Netzwerken aus Knoten und Kanten. | |
| ## Was ist Dijkstra? | |
| Ein Algorithmus zur Berechnung kürzester Wege in Graphen mit nicht-negativen Gewichten. | |
| ## Was ist A*? | |
| Ein Suchalgorithmus, der eine Heuristik nutzt, um den Weg zum Ziel effizienter zu finden. | |
| ## Was ist ein randomisierter Algorithmus? | |
| Ein Algorithmus, der Zufall als Teil seiner Strategie verwendet. | |
| ## Was ist ein Optimierungsalgorithmus? | |
| Ein Verfahren, das eine möglichst gute Lösung unter definierten Bedingungen sucht. | |
| ## Sind Machine-Learning-Modelle Algorithmen? | |
| Machine Learning verwendet Algorithmen zum Training und zur Vorhersage. Das trainierte Modell selbst ist jedoch nicht einfach mit einem klassischen Algorithmus gleichzusetzen. | |
| ## Welche Algorithmen nutzt KI? | |
| Unter anderem Optimierung, Suche, Sampling, Attention, Routing, Graphverfahren und Reinforcement Learning. | |
| ## Werden Algorithmen durch KI unwichtig? | |
| Nein. KI-Systeme selbst bestehen aus vielen algorithmischen Komponenten. | |
| ## Warum sind Algorithmen für AGI wichtig? | |
| Allgemeinere KI benötigt weiterhin effiziente Verfahren für Planung, Suche, Memory, Tool Use, Ressourcenallokation und Koordination. | |
| --- | |
| # Glossar | |
| **Algorithmus** | |
| Eindeutige endliche Schrittfolge zur Lösung eines Problems. | |
| **Algorithm Design** | |
| Systematische Entwicklung von Lösungsverfahren. | |
| **Big O** | |
| Notation für asymptotisches Wachstum von Laufzeit oder Speicherbedarf. | |
| **Backtracking** | |
| Suchstrategie mit systematischem Zurückgehen bei Sackgassen. | |
| **BFS** | |
| Breadth-First Search. | |
| **DFS** | |
| Depth-First Search. | |
| **Dynamic Programming** | |
| Methode zur Wiederverwendung bereits gelöster Teilprobleme. | |
| **Greedy Algorithm** | |
| Verfahren mit lokal optimalen Entscheidungen. | |
| **Graph** | |
| Datenstruktur aus Knoten und Kanten. | |
| **Hash Table** | |
| Datenstruktur für schnellen Schlüsselzugriff. | |
| **Heap** | |
| Datenstruktur für Prioritätsoperationen. | |
| **Heuristik** | |
| Praktische Näherungsstrategie ohne Garantie auf optimale Lösung. | |
| **Komplexität** | |
| Wachstum von Rechen- oder Speicheraufwand. | |
| **Optimierung** | |
| Suche nach der besten Lösung unter gegebenen Bedingungen. | |
| **Rekursion** | |
| Selbstaufruf einer Funktion. | |
| **Sortieralgorithmus** | |
| Algorithmus zur Ordnung von Elementen. | |
| **Suchalgorithmus** | |
| Algorithmus zum Finden von Elementen, Zuständen oder Lösungen. | |
| --- | |
| # Geplante Hugging-Face-Spaces | |
| Die Organisation **Algorithmen** kann eine kleine Anzahl praxisnaher deutschsprachiger Ressourcen bereitstellen. | |
| ## Algorithmen Explorer | |
| **Geplant:** `algorithmen/algorithmen-explorer` | |
| Interaktive Übersicht über Sortierung, Suche, Graphen, Dynamic Programming, Optimierung und KI-Algorithmen. | |
| ## Algorithmen Architektur | |
| **Geplant:** `algorithmen/algorithmen-architektur` | |
| Visuelle Karte von Datenstrukturen, algorithmischen Paradigmen und modernen AI-Systemalgorithmen. | |
| ## Komplexitäts-Check | |
| **Geplant:** `algorithmen/komplexitaets-check` | |
| Interaktive Orientierung zu Laufzeit, Speicher und Big-O. | |
| ## Algorithm Readiness | |
| **Geplant:** `algorithmen/algorithm-readiness` | |
| Bewertung von Korrektheit, Komplexität, Skalierbarkeit, Robustheit und Produktionsreife. | |
| --- | |
| # Forschung und Kooperationen | |
| Wir sind offen für technische Kooperationen, Open-Source-Projekte, Benchmarks, Datasets und gemeinsame Ressourcen rund um Algorithmen. | |
| Besonders interessant sind: | |
| - Algorithm Design | |
| - Datenstrukturen | |
| - Komplexitätsanalyse | |
| - Graphalgorithmen | |
| - Optimierung | |
| - Dynamic Programming | |
| - Search | |
| - Planning | |
| - Randomized Algorithms | |
| - Machine-Learning-Algorithmen | |
| - Reinforcement Learning | |
| - AI Systems | |
| - Algorithm Engineering | |
| Willkommen sind Entwicklerteams, Open-Source-Projekte, Hochschulen, Forschungseinrichtungen, Infrastrukturteams und Unternehmen mit algorithmischen oder KI-bezogenen Anwendungsfällen. | |
| **Kooperationen & Kontakt:** [ki-agenten@magenta.de](mailto:ki-agenten@magenta.de) | |
| --- | |
| # Projektprinzipien | |
| **Korrektheit vor Optimierung.** | |
| Ein schneller falscher Algorithmus ist wertlos. | |
| **Komplexität sichtbar machen.** | |
| Laufzeit und Speicherbedarf sollten verstanden werden. | |
| **Datenstruktur und Algorithmus gemeinsam denken.** | |
| Beide beeinflussen sich gegenseitig. | |
| **Einfach vor kompliziert.** | |
| Die einfachste korrekte Lösung ist häufig die beste Ausgangsbasis. | |
| **Messen statt raten.** | |
| Theorie sollte durch Benchmarks ergänzt werden. | |
| **Randfälle gehören zum Design.** | |
| Robustheit entsteht nicht erst beim Testen. | |
| **KI ersetzt algorithmisches Denken nicht.** | |
| Moderne KI-Systeme machen algorithmische Grundlagen sogar wichtiger. | |
| **Skalierbarkeit ist Teil der Qualität.** | |
| Ein Verfahren sollte auch unter realistischen Lasten bewertet werden. | |
| --- | |
| *Algorithmen ist eine unabhängige deutschsprachige technische Hugging-Face-Ressource zu Algorithm Design, Datenstrukturen, Komplexität, Optimierung, Machine Learning und algorithmischen KI-Systemen.* | |
| **Stand: September 2026** | |