Algorithmen und Datenstrukturen
Die Informatik verbinden viele Menschen mit programmieren. Das ist nicht ganz falsch. Die Softwareentwicklung ist ein wichtiges Forschungsgebiet der Informatik und eine der rentabelsten Wirtschaftszweige. Daher beginnen wir den Unterricht in der Oberstufe auch mit diesem wichtigen Thema. Besonders wichtig dabei ist die Bereitstellung der notwendigen Techniken für den Bundeswettbewerb Informatik. An diesem Wettbewerb nehmen alle Leistungskursschüler teil und auch einige Schüler des Grundkurses.
Nachfolgend sind einige Themengebiete des Oberstufenunterrichts abgebildet. Die Inhalte werden in Leistungs- wie auch Grundkursen besprochen. Die Programmierung erfolgt mit C#. Nach der Vermittlung der Grundlagen wird die Behandlung der Binären Suchbäume mit der Sprache Haskell durchgeführt.
Materialien zum Thema findet man auf dieser Seite.
- Einführung in die Sprache C#: das Microsoft .NET Framework, C# im Vergleich zu anderen Sprachen und Sprachparadigmen, Arbeitsweise des C#-Compilers (Erzeugung und Interpretation von Assemblies)
- Grundlagen der Programmierung mit C#: Benutzung des MSDN-Bibliothekssystem, Arbeit mit der Dokumentation, einfache Datentypen (Casting), Referenztypen, iteratives und rekursives Programmieren
- Algorithmen: Definition, Beispiele, Darstellung von Algorithmen (Flussdiagramme, Pseudocode, Struktogramme, Quelltext)
- wichtige Algorithmen: Euklidischer Algorithmus, Fakultät, Fibonacci-Zahlen, Primzahlsieb, Türme von Hanoi, Damenproblem, Springerproblem, Suchen- und Sortieren
- Groß-O-Notation: Definition, Anwendung für eine erste Klassifizierung der behandelten Algorithmen: z. B. \(\mathcal O(1)\), \(\mathcal O(log_ {n})\), \(\mathcal O(\sqrt{\tiny{n}})\), \(\mathcal O(n)\),\(\mathcal O(n \cdot log\,n)\), \(\mathcal O(n \cdot log_{2} n)\), \(\mathcal O(n^2)\), \(\mathcal O(n^3)\)
- schnelle Sortierverfahren (QuickSort, HeapSort, MergeSort, Fachsortieren, ShellSort) und die möglichst exakte mathematische Analyse ihres Aufwandes
- Stringalgorithmen: naiv, Knuth-Morris-Pratt, Boyer-Moore-Algorithmus
- das Rucksackproblem: Greedy-Algorithmen und Dynamisches Programmieren
- Konzepte des funktionalen Programmierens: Endrekursion, höhere Funktionen, Currying, Lambda-Kalkül, Typklassen, Module
- abstrakte Datentypen als wichtiges Hilfsmittel für effiziente Erstellung großer Softwaresysteme
- Listen als erstes Beispiel für einen abstrakten Datentyp (ADT): Implementation (bei gleichbleibender Spezifikation) als verkettet bzw. als sequenziell gespeicherte Struktur, Aufwand von Grundoperationen auf Listen in Abhängigkeit von der Implementation; ArrayList als professionelle Implementation des ADT Liste
- Listen als eine einfache Möglichkeit zum Modellieren des ADT dictionary
- Simulation verschiedener Konzepte von selbstanordnenden Listen und Vergleich ihrer Effizienz
- Suchbäume als zweite (und effizientere) Lösung des Wörterbuchproblems; Abschätzung des Erwartungswertes der mittleren Suchpfadlänge von natürlichen Suchbäumen
- AVL-Bäume als Beispiel für balancierte (Such-)Bäume; worst-case-Abschätzung der Höhe sowie der mittleren Suchpfadlänge von AVL-Bäumen in Abhängigkeit von der Schlüsselzahl.
- Strukturelle Induktion auf Bäumen und Listen
- B-Bäume als effiziente externe Datenstruktur; Implementation von B-Bäumen (mit den Operationen Suchen und Einfügen) mittels Dateien; Ideensammlung für eine effiziente Entferne-Operation
- Rot-Schwarz-Bäume, Bruder-Bäume
Ralf Dorn, Fachleiter Informatik (erreichbar: ralf.dorn[at]hhgym.de)
