Algorithmen und Datenstrukturen I (12/1)

• Kleinere rekursive Algorithmen: „Türme von Hanoi“, „Binomialkoeffizienten“, etc.; Schachtelmodell zur Veranschaulichung der Rekursion
• ADT Queue (nach den Vorgaben des Zentralabiturs), Anwendung z.B. Simulation eines Wartezimmers
• ADT Stack (nach den Vorgaben des Zentralabiturs), Anwendung z.B. Stackrechner, klammernfreie UPN-Notation von mathematischen Termen.
• ADT Lineare Liste (objektorientiert implementiert), Methoden der Linearen Liste (nach den Vorgaben des Zentralabiturs). Anwendung z.B. lexikographisch geordnete Listen, Projekt z.B. „Geordnete Adressliste", Laden und Speichern von Listen mittels Streams.
• Klassendiagramme, ist-, hat- und kennt- Beziehungen zwischen Klassen. Dokumentation von Projekten.
• Einführung in den ADT Binärbaum über das Städteraten (Methoden des Binärbaums nach den Vorgaben des Zentralabiturs, insbesondere die rekursive Charakterisierung), Traversierungsalgorithmen.
• Suchbaum als spezieller Binärbaum. ADT OrderedTree, Suchbaumoperationen Einfügen und Suchen, rekursiv formuliert. Laden und Speichern von Bäumen mittels Streams.

• Einführung in formale Sprachen: Grammatik, Alphabet, Syntax-Analyse und abstraktes Wortproblem. Formale Ableitung von Wörtern aus dem Startsymbol. Reguläre Grammatiken und Sprachen.
• Endliche Automaten und ihre Grenzen in der Syntax-Analyse. Alternativ die Methode des rekursiven Abstiegs. Parser zur Syntaxanalyse. Wertliefernde Automaten und wertliefernde Parser. Entwurf und Implementation von Teilen eines Compilers für eine einfache formale Sprache, Trennung von Scanner und Parser.

• hierarchische und relationale Datenbanksysteme, exemplarische, einfache SQL-Anfragen, Integration von MySQL in die Hochsprache Java, Implementation von Datenbank-Abfragen, Normalisierung von Datenbanken: Überführung einer Datenbank in die 1. bis 3. Normalform, Relationenalgebra (Selektion, Projektion, Join), SQL-Abfragen über eine oder mehrere verknüpfte Tabellen,
• Kryptologie, Symmetrische Verschlüsselungsverfahren (Cäsar, Vigenére), Asymmetrische Verschlüsselungsverfahren (RSA), Datenschutzaspekte

• ADT Stack, ADT Queue, ADT List, ADT BinTree, ADT OrderedTree,
• Formale Sprachen, Automaten, Methode des rekursiven Abstiegs, Compilerbau
• Datenbanken

---

• Backtracking-Algorithmus zur Lösung komplexer Suchprobleme, Beispiele „Acht Damen auf dem Schachbrett“, „Teilbarkeitspuzzle“ und "Springerwanderung". Integration des Backtracking-Algorithmus in die fundamentalen Suchstrategien Tiefensuche, Breitensuche und Bestensuche.