InformatikLeistungskurs

Objektorientierte Modellierung und Programmierung

Wie im Grundkurs werden Objekte, Klassen und Methoden nach dem Message-Passing-Modell behandelt, zusätzlich mit Vererbung und Polymorphie.

• ·Objektorientierung und das Message-Passing-Modell
• ·Klassen, Objekte, Attribute
• ·Konstruktoren und Methoden
• ·Vererbung und Polymorphie

Rekursion

Rekursive Methoden und Definitionen werden als Problemlösungsstrategie eingeführt und mit iterativen Varianten verglichen.

• ·Rekursion als Problemlösungsstrategie
• ·Lineare und baumförmige Rekursion und ihre Aufrufschemata
• ·Vergleich äquivalenter rekursiver und iterativer Algorithmenvarianten
• ·Rekursive Definition der Fakultät und der Fibonacci-Zahlen

Suchen und Sortieren

Zusätzlich zu den einfachen Suchverfahren werden im Leistungskurs die effizienteren Sortierverfahren Mergesort und Quicksort behandelt.

• ·Sequentielle Suche
• ·Binäre Suche
• ·Einfache Sortierverfahren: Bubblesort, Selectionsort, Insertionsort
• ·Höhere Sortierverfahren: Mergesort, Quicksort

Dynamische Datenstrukturen: lineare Listen und binäre Bäume

Neben binären Bäumen werden im Leistungskurs auch lineare Listen mit den Datenstrukturen Stack und Queue sowie die strukturelle Induktion als Beweismethode behandelt.

• ·Definition linearer Listen sowie der Begriffe head, tail, Länge
• ·Algorithmik auf linearen Listen: Suchen, Löschen, Ersetzen, Einfügen
• ·Die Datenstruktur Stack mit den Operationen isEmpty, top, push, pop
• ·Die Datenstruktur Queue mit den Operationen isEmpty, front, enqueue, dequeue
• ·Definition binärer Bäume sowie der Begriffe Wurzel, linker/rechter Teilbaum, Knoten, Tiefe
• ·Algorithmik auf binären Bäumen und Suchbäumen
• ·Baumtraversierungen: Preorder-, Inorder-, Postorder-Durchläufe
• ·Strukturelle Induktion

Kryptologie

Zusätzlich zu den im Grundkurs behandelten Verfahren kommen der Man-in-the-middle-Angriff, die digitale Signatur und hybride Verschlüsselungsverfahren hinzu.

• ·Kryptographische Grundbegriffe: Klartext, Geheimtext, Schlüssel, Prinzip von Kerckhoffs
• ·Sicherheit: Vertraulichkeit, Authentizität, Integrität
• ·Chiffrieralgorithmen: Substitutions- und Transpositionsalgorithmen
• ·Klassische symmetrische Verschlüsselungsverfahren: Skytale, Cäsar, Vigenère
• ·Angriffsarten: Brute-Force, Known-Plaintext, Häufigkeitsanalysen
• ·Schlüsselaustauschverfahren: Diffie-Hellman, Man-in-the-middle-Angriffe
• ·Asymmetrische Verschlüsselung und digitale Signatur: das RSA-Verfahren
• ·Die Idee hybrider Verschlüsselungsverfahren

Komplexitätstheorie

Das Laufzeitverhalten von Algorithmen wird mit der Landau'schen O-Notation klassifiziert, einschließlich der Klassen P und NP.

• ·Der Begriff der Problemgröße
• ·Laufzeit und die Begriffe best-case, average-case, worst-case
• ·Der funktionale Zusammenhang zwischen Problemgröße und Laufzeit
• ·Definition der Landau'schen O-Notation
• ·Algorithmenklassifizierung anhand der O-Notation
• ·Die Klassen P und NP und das P = NP-Problem

Berechenbarkeit und ihre Grenzen

Am Beispiel der Turingmaschine werden die Grenzen der Berechenbarkeit untersucht, unter anderem am Halteproblem.

• ·Bestandteile und Aufbau einer Turingmaschine
• ·Darstellung von natürlichen Zahlen und Wahrheitswerten
• ·Turingmaschinenprogramme: Addition, Subtraktion, Verdopplung, Paritätsprüfung
• ·Die busy-beaver-Funktion und ihre Nicht-Berechenbarkeit
• ·Das Halteproblem für Turingmaschinen
• ·Universalität

Formale Sprachen

Wie im Grundkurs werden endliche Automaten und Grammatiken behandelt, zusätzlich mit der Chomsky-Hierarchie und Beispielen nicht-regulärer Sprachen.

• ·Definition des Begriffs der formalen Sprache
• ·Endliche Automaten mit und ohne Ausgabe als 5-Tupel (Akzeptor)
• ·Übergangs- und Ausgabetabellen sowie Übergangsgraphen
• ·Konstruktion endlicher Automaten zu vorgegebenen Problemstellungen
• ·Teilmengenkonstruktion
• ·Grammatiken als 4-Tupel
• ·Chomsky-Hierarchie, Beispiele nicht-regulärer und nicht-kontextfreier Sprachen
• ·Umwandlung regulärer Grammatiken und akzeptierender Automaten ineinander

Graphentheorie

Graphen werden als Paar aus Knoten und Kanten definiert und algorithmisch bearbeitet, unter anderem mit dem Dijkstra-Algorithmus und dem Traveling-Salesman-Problem.

• ·Definition gerichteter Graphen als Paar aus Knoten und Kanten
• ·Ungerichtete Graphen als Spezialfall gerichteter Graphen
• ·Grundbegriffe: Knotengrad, schlichte, vollständige und zusammenhängende Graphen, gewichtete Graphen
• ·Graphendarstellung: mengentheoretische Darstellung, Adjazenzlisten und Adjazenzmatrizen
• ·Bäume als gerichtete, azyklische Graphen
• ·Algorithmik auf Graphen: Breiten- und Tiefensuche, Spannbäume, Kürzeste-Wege-Problem und Dijkstra-Algorithmus, Hamiltonkreise und Traveling-Salesman-Problem