1.3.1 Algorithmen auf ihre Laufzeitkomplexität untersuchen
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können Algorithmen auf ihre Laufzeitkomplexität untersuchen.
Algorithmen und Datenstrukturen: Sortieren und Suchbäume
Ausführliche Vorlesungsnotizen und Erklärungen zu klassischen Sortieralgorithmen wie Bubblesort, Selection Sort, Insertion Sort und Heapsort sowie zu binären Suchbäumen und deren Traversierung. Das Material vermittelt die theoretischen Grundlagen und Laufzeitanalysen (O-Notation) für effiziente Datenverarbeitung.
Aufwandsanalyse von Sortieralgorithmen
Das Unterrichtsmaterial führt in die Aufwandsanalyse von klassischen Sortieralgorithmen wie Selectionsort, Insertionsort, Bubblesort und Quicksort ein. Die Lernenden zählen Vergleiche, betrachten Best- und Worst-Case-Szenarien und analysieren die Kostenfunktionen in Abhängigkeit von der Problemgröße.
Laufzeitverhalten von Sortieralgorithmen
Das Material führt experimentell in die Laufzeitanalyse verschiedener Sortieralgorithmen (wie Selection Sort, Insertion Sort, Bubble Sort und Quicksort) mithilfe von Python ein. Die Lernenden messen systematisch Rechenzeiten, analysieren Gesetzmäßigkeiten und untersuchen den Einfluss verschiedener Implementierungen.
Der Graham-Scan-Algorithmus zur Bestimmung der konvexen Hülle
Dieses Unterrichtsmaterial erklärt detailliert den Graham-Scan-Algorithmus zur Berechnung der konvexen Hülle einer Punktmenge in der Computergeometrie. Es behandelt den theoretischen Hintergrund, die mathematische Korrektheit, eine vollständige Implementierung in C++ sowie eine Laufzeit- und Speicheranalyse.
Laufzeit- und Speicherkomplexität (Big-O-Notation) in Perl
Der Artikel erklärt praxisnah anhand von Codebeispielen in Perl verschiedene Stufen der Zeit- und Speicherkomplexität (von O(1) bis O(n!) und O(2^n)). Dabei werden grundlegende algorithmische Muster wie Suchen, Sortieren, Rekursion und Backtracking beleuchtet.
Aufwandsanalyse von Suchalgorithmen (Linear und Binär)
Dieses Unterrichtsmaterial behandelt die Aufwandsanalyse von Algorithmen am Beispiel der linearen und binären Suche. Anhand von Aufgaben analysieren die Lernenden den Best-Case und Worst-Case sowie die Laufzeitkomplexität in Abhängigkeit von der Listenlänge.
Exkurs: Rekursive Berechnungen mit hohem Aufwand
Das Material behandelt rekursive Funktionen in Python anhand des Galtonbretts und der Ackermann-Funktion. Es analysiert die Ineffizienz kaskadenartiger und verschachtelter Rekursionen durch Beobachtung der Funktionsaufrufe und Reduktionsketten.
Übungen zur Untersuchung und Verbesserung der Algorithmischen Effizienz in Python
Das Material enthält Übungsaufgaben zur Analyse und Steigerung der Effizienz von Algorithmen anhand von Python-Code. Die Lernenden untersuchen verschiedene Implementierungen von Potenzierungs- und Primzahltests und vergleichen deren Leistungsfähigkeit.
Effizienz von Algorithmen am Beispiel des Euklidischen Algorithmus
Das Material vergleicht zwei Algorithmen zur Bestimmung des grössten gemeinsamen Teilers (Wechselwegnahme und Euklidischer Algorithmus) hinsichtlich ihrer Effizienz und des Laufzeitverhaltens. Es führt grundlegende Begriffe wie die Äquivalenz und Ressourceneinsparung von Algorithmen ein.
Aktionen zählen mit Python
Dieses Unterrichtsmaterial zeigt anhand eines Python-Programms zum Euklidischen Algorithmus, wie durch den Einsatz von Zählvariablen die Anzahl der Schleifendurchläufe bestimmt werden kann. Die Lernenden führen das Programm aus und untersuchen die Laufzeitunterschiede bei unterschiedlichen Eingabewerten.
Swiss Olympiad in Informatics - First Round Tasks
Eine Sammlung von fortgeschrittenen algorithmischen Programmieraufgaben und theoretischen Fragestellungen aus der ersten Runde der Schweizer Informatik-Olympiade, die sich mit Graphentheorie, dynamischer Programmierung und Datenstrukturen befassen.
Swiss Olympiad in Informatics (SOI) Aufgaben und Material
Das Material enthaelt verschiedene anspruchsvolle Programmier- und Algorithmenaufgaben im Rahmen der Schweizer Informatik-Olympiade (SOI). Die Aufgaben decken Themen wie Graphentheorie, dynamische Programmierung, String-Verarbeitung und Komplexitätsanalyse ab.
Backtracking and the N-Queens Problem
Dieses Unterrichtsmaterial erklärt die algorithmische Strategie des Backtrackings anhand des klassischen Damenproblems. Es enthält eine theoretische Einführung, eine Beschreibung des Algorithmus sowie eine vollständige Implementation in C++ inklusive Laufzeitanalyse.
Convex Hull Trick und optimierte Dynamische Programmierung
Das Lehrmittel behandelt fortgeschrittene Techniken zur Optimierung von dynamischer Programmierung (DP) mittels des Convex Hull Tricks und der verallgemeinerten Deque-Optimierung. Es enthält mathematische Herleitungen sowie vollständige Implementierungen in C++.
Fenwick Trees (Binary Indexed Trees) in C++
Dieses fortgeschrittene Dokument behandelt die Theorie und Implementierung von Fenwick-Bäumen (Binary Indexed Trees) in C++. Es werden verschiedene Aspekte wie dynamische Prefix-Summen, multidimensionale Varianten, Bereichsabfragen sowie Koordinatenkompression detailliert erläutert.
Divide and Conquer on Ranges and Segment Trees
Der Text erklärt detailliert die theoretischen Grundlagen und die Implementierung von Segmentbäumen (Segment Trees) in C++. Dabei werden Divide-and-Conquer-Algorithmen, Bereichsanfragen (Range Queries) und effiziente Array-Updates behandelt.
Binäre Suche: Algorithmus, Implementation und Analyse
Dieses Unterrichtsmaterial erklärt das Prinzip der binären Suche für sortierte Arrays. Es enthält eine mathematisch begründete Problemstellung, eine Java-Implementierung sowie eine Analyse von Speicher- und Laufzeitkomplexität.
Einführung in Algorithmen und O-Notation
Das Material bietet eine verständliche Einführung in den Begriff des Algorithmus, die O-Notation zur Laufzeitanalyse sowie klassische Probleme wie das Rucksackproblem, das Travelling-Salesperson-Problem, das Finden eines Stars und das Maximum Subarray Problem. Es behandelt zudem verschiedene Entwurfsstrategien wie Teile-und-Herrsche und dynamische Ansätze.
The Cost of Computation: Algorithmische Komplexität und Big-O-Notation
Dieses Lehrmaterial führt in die Grundlagen der algorithmischen Analyse und die Big-O-Notation ein. Anhand von Beispielen zu Rekursion und Laufzeitvergleichen wird gezeigt, wie die Effizienz von Programmen gemessen und formal beschrieben wird.
Laufzeit von Algorithmen
Das Material führt in die Analyse der Zeitkomplexität von Algorithmen ein. Es erklärt die Unterscheidung zwischen Best-, Worst- und Average-Case sowie die Klassifizierung von Laufzeiten mithilfe der O-Notation.
Effizienz und Komplexität
Der Text führt in die Grundlagen der Analyse von Algorithmen ein. Es werden die zentralen Begriffe Effizienz und Komplexität im Hinblick auf Laufzeit und Speicherbedarf erläutert.
Fibonacci numbers via recursion
Eine Programmieraufgabe, bei der die n-te Fibonacci-Zahl mittels Rekursion in Python implementiert werden soll. Zudem wird die Reflexion über die Laufzeit im Vergleich zu iterativen Lösungen angeregt.
Komplexität von Algorithmen und Problemen
Dieses Unterrichtsmaterial führt systematisch in die Analyse des Laufzeitverhaltens und den Ressourcenverbrauch von Algorithmen ein. Anhand von Fallstudien werden verschiedene Problemlösungen und deren Effizienz untersucht.
Randomisierte Algorithmen
Diese mentorierten Unterrichtsmaterialien führen in das Konzept der randomisierten Algorithmen ein. Anhand von Beispielen wie Quicksort und der Verifikation von Matrixmultiplikationen wird analysiert, wie gezielter Zufall zur Lösung von Problemen eingesetzt werden kann.
Das Entscheidungsproblem der Knotenüberdeckung
Diese leitprogrammartigen Unterrichtsunterlagen behandeln das Knotenüberdeckungsproblem als Entscheidungs- und Optimierungsproblem. Die Schülerinnen und Schüler befassen sich mit Formalismen der theoretischen Informatik, betrachten die algorithmische Komplexität und schulen ihr algorithmisches Denken anhand graphentheoretischer Beispiele.
Rekursion und Aufwand
Dieses Unterrichtsmaterial beleuchtet die Eigenschaft von rekursiven Algorithmen, einen besonders hohen Rechenaufwand zu erzeugen. Anhand konkreter Beispiele, wie der Ackermann-Funktion, wird diese Problematik veranschaulicht.
Laufzeit messen mit Python
Dieses Unterrichtsmaterial demonstriert anhand eines Python-Programms für den Euklidischen Algorithmus und den Wechselwegnahme-Algorithmus, wie die Ausführungszeit von Programmen gemessen werden kann. Die Lernenden führen das Programm selbst aus und vergleichen die Rechenzeiten bei unterschiedlichen Eingabewerten.
Effizienz von Algorithmen
Dieses Material führt in das Konzept der algorithmischen Effizienz ein und zeigt Lernenden, wie sich die benötigten Ressourcen wie Rechenzeit und Speicherbedarf von Algorithmen unterscheiden. Zudem wird thematisiert, wie die Laufzeit von implementierten Algorithmen gemessen werden kann.
Schwierige Probleme in der Informatik
Die Lernenden entdecken mithilfe der Software GraphBench NP-vollständige Probleme der theoretischen Informatik und untersuchen Algorithmen, Laufzeiten sowie Extremfälle. Das Material bietet gelenktes entdeckendes Lernen und einen optionalen Lehrtext zur Komplexitätstheorie.
Rekursion und Algorithmen in Python
Ein praxisorientiertes Unterrichtsmaterial zur Vertiefung von Rekursion anhand von Fakultät, Ackermann-Funktion und Code-Analysen. Die Schüler:innen programmieren in Python, analysieren Laufzeiten und untersuchen den Call-Stack im Debug-Modus.
Zeitmessung und empirischer Vergleich von Sortieralgorithmen in Python
Die Schülerinnen und Schüler implementieren und vergleichen verschiedene klassische Sortieralgorithmen (Selection Sort, Insertion Sort, Merge Sort) in Python und messen deren Laufzeit empirisch für unterschiedliche Eingabegrössen mit dem Modul timeit.
Lineare und binäre Suche im Vergleich
Das Material erklärt und vergleicht die lineare und die binäre Suche anhand von Python-Codebeispielen. Es wird auf die Algorithmik, die O-Notation für das Wachstumsverhalten und einen praktischen Experimentvergleich mit matplotlib eingegangen.
Korrektheit und Aufwand von Algorithmen
Dieses Material führt in die zentralen Eigenschaften von Algorithmen ein, nämlich deren Korrektheit und den damit verbundenen Aufwand zur Problemlösung.
Einführung in die Komplexitätstheorie und das P-NP-Problem
Der Text behandelt grundlegende Konzepte der theoretischen Informatik wie Laufzeitkomplexität, die Komplexitätsklassen P und NP sowie das berühmte P-NP-Problem. Anhand von Beispielen wie der Primfaktorzerlegung, dem Erfüllbarkeitsproblem SAT und dem Travelling Salesman Problem werden diese theoretischen Konzepte greifbar gemacht.
Konzept Laufzeitkomplexität
Der Text erklärt das Konzept der Laufzeitkomplexität von Algorithmen in Abhängigkeit von der Eingabegrösse, das Worst-Case-Szenario sowie die asymptotische Betrachtung anhand einer anschaulichen Reiskorn-Analogie. Es handelt sich um eine kompakte theoretische Einführung ohne praktische Übungen oder Programmierbeispiele.
A Didactic Analysis of Functional Queues
Dieser wissenschaftliche Artikel präsentiert einen didaktischen Ansatz zur Durchführung einer amortisierten Analyse von funktionalen Warteschlangen ohne komplexe Kombinatorik. Er richtet sich primär an fortgeschrittene Lernende oder Lehrpersonen, um die Laufzeitanalyse verständlicher zu machen.