In unserer Lebenswelt sind Computer und eingebettete Systeme, u. a. in Mobiltelefonen, Kaffeeautomaten oder Kraftfahrzeugen, alltäglich. Algorithmen, Datenstrukturen und objektorientierte Modellierung sind Konstruktionsprinzipien solcher Informatiksysteme, die für deren Verständnis unerlässlich sind.
Such- und Sortieralgorithmen werden in vielen Anwendungen benötigt. Mit ihnen kann eine Suche effizient durchgeführt werden. Wir entwickeln einfache Such- und Sortieralgorithmen und werden diese in geeigneter Form beschreiben, darstellen und implementieren. Zudem analysieren wir das Laufzeitverhalten der Algorithmen und können dieses abschätzen.
Rekursion ist eine fundamentale Idee der Informatik. Mithilfe der Rekursion können viele Probleme gelöst werden, für die eine iterative Lösung nicht offensichtlich ist bzw. die rekursiv formuliert sind.
Für die objektorientierte Modellierung sind die Begriffe Klasse und Objekt von grundlegender Bedeutung. Bei der Analyse einer Problembeschreibung finden wir Objekte mit Eigenschaften und Funktionalitäten. Durch Reduktion auf relevante Eigenschaften und Funktionalitäten und durch Klassifikation von Objekten gewinnen wir Klassen und erkennen deren Beziehungen. Auf der Grundlage eines UML-Klassendiagrammes implementieren wir schließlich das entworfene Modell, prüfen Modellierung sowie Implementierung kritisch und überarbeiten diese gegebenenfalls.
Die höheren Datenstrukturen Liste und Baum werden wir objektorientiert im Kontext typischer Anwendungen modellieren und implementieren. Dabei beschäftigen wir uns mit den Vor- und Nachteile höherer Datenstrukturen in Bezug auf Speicherbedarf und Zeitkomplexität bei Standardoperationen.
Viele netzförmige Strukturen lassen sich mit Graphen objektorientiert modellieren. Die Kanten können mit Eigenschaften, wie z.B. Entfernung, Transportkapazität oder Richtung belegt werden. Anhand des Themenfeldes Graphen erarbeiten wir grundlegende Begriffe, Konzepte und Algorithmen, die in vielfältigen Kontexten angewendet werden können.
Q1.1 Such- und Sortieralgorithmen
grundlegendes Niveau (Grundkurs und Leistungskurs)
- grundlegende Algorithmen:
- lineare und binäre Suche
- einfache Sortieralgorithmen mit quadratischer Laufzeit
- Analyse und Bewertung von Sortieralgorithmen unter dem Aspekt Laufzeit
erhöhtes Niveau (Leistungskurs)
- effiziente Algorithmen:
- ein effizienter Sortieralgorithmus
Q1.2 Rekursion
grundlegendes Niveau (Grundkurs und Leistungskurs)
- Rekursion:
- rekursive Grafiken
- mathematische Funktionen
- „teile und herrsche“-Prinzip
- Grundstrukturen für die Implementierung:
- Terminationsbedingung
- Parameterübergabe
- einfache und mehrfache Rekursion
- Visualisierung
- Rekursion versus Iteration:
- Vor- und Nachteile rekursiver Algorithmen gegenüber iterativen Algorithmen
erhöhtes Niveau (Leistungskurs)
Q1.3 Klassen und Objekte
grundlegendes Niveau (Grundkurs und Leistungskurs)
- Klassen und Objekte:
- Objekt als Instanz einer Klasse
- Klasse als Bauplan für Objekte
- Attribut
- Methode
- Konstruktor
- Geheimnisprinzip
- Sichtbarkeit
- get-/set-Methoden
- UML-Klassendiagramm
- Assoziation
- Aggregation
- Feld von Objekten
erhöhtes Niveau (Leistungskurs)
- Klassenbeziehungen:
- Vererbung
- Liste von Objekten unter Verwendung von Bibliotheksklassen
Q1.4 Höhere Datenstrukturen und ihre objektorientierte Modellierung (nur Leistungskurs)
- lineare Listen:
- objektorientierte Modellierung
- Algorithmen zum Durchlaufen
- Einfügen, Löschen und Aktualisieren von Knoten
- Stapel und Warteschlange
- binäre Bäume:
- objektorientierte Modellierung
- Algorithmen zum Durchlaufen
- Einfügen, Löschen und Aktualisieren von Knoten
Q1.5 Graphen (nur Leistungskurs)
Wird im Leistungskurs Themenfeld 5 als verbindlich festgelegt, sollen Listen von Objekten unter Verwendung von Bibliotheksklassen bekannt sein.
- Graphen und ihre objektorientierte Modellierung:
- Knoten
- Kanten
- Pfade
- gerichtete und ungerichtete Graphen mit und ohne Bewertung
- Adjazenzmatrix
- Adjazenzliste
- Graphenalgorithmen:
- optimale Wege
- Tiefensuche
- Breitensuche