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)

  • Backtrackingverfahren

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

Q1.1 Verzweigte Datenstrukturen

Mit wachsenden Speichergrößen und immer günstiger werdenden Speicherpreisen ist abseh- bar, dass große Mengen von Daten verwaltet werden müssen. Dass hierfür effiziente Verfah- ren notwendig sind, ist einleuchtend. Niemand möchte erst lange warten, bis eine angeklickte MP3 auf der Festplatte lokalisiert und in den Speicher geladen wird – das Informatiksystem muss innerhalb von Sekundenbruchteilen »wissen«, wo genau die Datei sich befindet, um sie laden zu können.

Ein Verfahren zur Verwaltung von dynamisch wachsenden und sich verändernden Datenbe- ständen haben Sie bereits kennengelernt: Die lineare Liste. Mit ihrer Hilfe ist es möglich, Daten zu einer bestehenden Liste hinzuzufügen, Elemente daraus zu entfernen und die Liste mittels der linearen Suche elementweise zu durchsuchen.

Wie Sie sich vorstellen können, stößt diese Datenstruktur schnell an ihre Grenzen, wenn es darum gehen soll, »schnell mal« ein bestimmtes Element zu finden. Darum werden Sie in diesem Leitprogramm eine neue Datenstruktur kennen lernen, die Ihnen neue Möglichkeiten eröffnet. Wir beginnen damit allerdings nicht im oder am Informatiksystem, sondern stellen uns vor ein CD-Regal . . .


Q1.1 Such- und Sortieralgorithmen

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