Abschnittsübersicht

  • Einklappen Ausklappen

    12 D: Algorithmen und Daten

    Alles einklappen Alles aufklappen

    Herzlich Willkommen im Kurs Informatik 12 D zum Thema Algorithmen und Daten!

    Sie werden in diesem Kurs die Grundlagen des imperativen Problemlösens in der Sprache Java aus Klasse 10 wiederholen und festigen. Die Implementierung einfacher Algorithmen und Sortierverfahren bereitet das komplexe Thema Softwareentwicklung vor. Der Leistungskurs beurteilt zudem die Effizienz von Sortieralgorithmen.

    Der Moodle-Kurs begleitet den Unterricht. Sie finden hier alle Tafelbilder, Aufgaben, Dateien, Arbeitsblätter sowie Lösungen. Die Unterlagen werden nach der Unterrichtsstunde veröffentlicht. 

    Stand 2025-10-01: Dieser Kurs wird gepflegt.

    Lehrbücher:

    Eingesetzt werden die Lehrbücher Informatik 1 (2014) und Informatik 2 (2014) aus dem Verlag Schöningh.

  • Einklappen Ausklappen

    Mit Turtle Joe algorithmische Strukturen und Grundkonzepte der Objektorientierung verstehen

    • Herzlich Willkommen in unserer Welt, Ina und Joe!

      Ina und Joe sind zwei junge Schildkröten. Joe ist eine halbe Stunde vor seiner Schwester Ina geschlüpft ist. Ina erkennt man im Bild sehr gut, denn sie hat auf den letzten zwei Platten des Wirbelschildes (fünf Platten) keine schwarzen Punkte. Joe hingegen besitzt auf der vierten Platte einen schwarzen Punkt und auf der fünften Platte keinen Punkt. Beide bewegen sich so langsam vorwärts.

      Joe (links oben) und Ina, zwei soeben geschlüpfte Schildkröten

      ... und schon sind wir mittendrin in der Beschreibung der Welt mithilfe der objektorientierten Modellierung. In der Informatik werden Joe und Ina Objekte der Klasse Schildkröte genannt. Eine Klasse ist dabei eine Art Bauplan für gleichartige Objekte, die durch Eigenschaften (Attribute) und Fähigkeiten (Methoden) definiert werden. Ein Objekt ist also eine konkrete Realisierung und wird als Instanz bezeichnet. Die Attribute des Objekts/der Instanz besitzen bestimmte Werte.

      Hinweis: Eine ähnliche Art der Modellierung ist uns aus der Unterrichtseinheit Datenbanksysteme schon bekannt. Dort betrachteten wir Entitäten mit Attributen und Attributwerten und stellten die Abstraktion als Entitätstyp im ER-Diagramm dar. Allerdings spielten die Fähigkeiten keine Rolle.

      Eine Objektkarte dient der übersichtlichen Darstellung des Zustands eines Objekts zu einem bestimmten Zeitpunkt. Für Ina und Joe sehen die Objektkarten so aus:

      Zur Darstellung der Klasse verwenden wir das Klassendiagramm. Es gibt neben dem Namen und den Eigenschaften auch die Fähigkeiten (Methoden) an. Einige Methoden benötigen weitere Angaben, die mithilfe von Parametern übergeben werden können.

    • Seymor Papert CC-BY-SA 3, Matematicamente.it, Wikipedia

      Seymour Papert war Professor für Mathematik und Erziehungswissenschaften am Massachusetts Institute of Technology. Er wollte Schülern informatische Fähigkeiten bei gleichzeitiger Mündigkeit von der IT vermitteln. Dazu entwickelte er in den 1960er die Programmiersprache LOGO. In dieser gab es eine Turtle, also eine Schildkröte, die man durch Befehle steuern konnte und die den dabei abgelaufenen Weg zeichnete. 

      ... und das können wir auch machen!

      Die Turtles verfügen über Befehle zum Bewegen und Drehen, können aber auch die Stiftfarbe ändern. Eine Übersicht über die Fähigkeiten unserer Turtles liefert das Klassendiagramm. Unsere Turtle joe lebt in der Entwicklungsumgebung BlueJ und solle neue Fähigkeiten erlernen. Aus dem Klassendiagramm wissen wir bereits, dass Fähigkeiten = Methoden sind. Also müssen wir Methoden (in Java) entwickeln.

    • Turtle-Aufgabe: Joe erkundet BlueJ und lernt eine erste Methode
    • 00 Vorgabe Turtlezeichner Datei
    • Klassendiagramm Turtle Datei

    • Wir erweitern die Klasse Turtlezeichner nun immer weiter um Fähigkeiten mit dem Objekt Joe und nutzen dabei die Aufgaben aus dem SOL-Kurs "Turtle-Grafik mit Java".

    • Turtle-Grafik mit Java Link/URL

      Das Tutorial führt uns durch algorithmische Strukturen und Grundlagen der Programmierung. Beachten Sie, dass sich die Turtle-Befehle in den Beispielen von unseren hier unterscheiden. Sie können also nicht die Quelltexte kopieren.

    • Methoden in Java

      In unserer BlueJ-Welt existiert das Objekt joe der Klasse Turtle in der Klasse Turtlezeichner. Für das Lernen neuer Zeichnungen nutzen wir diese Klasse und ergänzen sie um eigene Methoden.

      Eine Methode, die wir von außen aufrufen können (public) und die nichts zurück gibt (void) - also einen Auftrag ausführt - hat in Java folgenden Aufbau:

      public void machWas(){
        //hier Algorithmus einfügen
      }

      Sind Parameter zur Übergabe von Werten notwendig, dann verwenden wir folgende Struktur:

      public void machWasAnderes(Datentyp pParameter){
        //hier Algorithmus einfügen
      }

      Beispiele:

      Joe zeichnet ein Quadrat mit fester Seitenlänge:

      public void zeichneQuadrat(){
  for (int i = 1; i <= 4; i++){
    joe.move(100);
    joe.turn(90);  
  }
}

      Joe zeichnet ein Rechteck mit variablen Seitenlängen:

      public void zeichneRechteck(int pLaenge, int pBreite){
  for (int i = 1; i <= 2; i++){
    joe.move(pLaenge);
    joe.turn(90);  
    joe.move(pBreite);
    joe.turn(90);
  }
}
    • Zum Weiterarbeiten: Lerntheke Turtle Datei
    • Aufgaben Einfaches Zeichnen Link/URL
    • Lösungen Einfaches Zeichnen Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Aufgaben Einfache Schleifen Link/URL
    • Lösungen Einfache Schleifen Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Aufgaben Verschachtelte Schleifen Link/URL
    • Lösungen Verschachtelte Schleifen Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Aufgaben Verzweigungsfiguren Datei
    • Lösungen Verzweigungen Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Komplexe Übungen Teil 1 Datei
    • Aufgaben Komplexe Übungen Link/URL
    • Komplexe Übungen Teil 1 Lösungen Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Lösungen Komplexes Datei
      Nicht verfügbar, außer: Sie sind in LK
    • Erläuterungen Rekursion Link/URL
    • Aufgaben Rekursion Link/URL
  • Einklappen Ausklappen

    Algorithmen darstellen, interpretieren und implementieren

    • Im Folgenden soll die Implementation von Lösungsalgorithmen in Java trainiert werden. Dazu liegen Aufgaben vor, die sich entweder mit grundlegenden mathematischen Problemen, wie sie in der Verschlüsselung von Nachrichten eingesetzt werden, oder mit Datumsberechnungen beschäftigen. Bei der Bearbeitung des Portfolios werden zusätzlich die Methodenart Anfrage sowie die Datenstruktur Liste kennengelernt, das Handling mit Parametern geübt und die Unterscheidung zwischen Datentypen gefestigt. 

    • Portfolio Imperatives Problemlösen Fach BlueJ (incl. Primfaktoren) Datei
    • Übersicht: Listen in Java (für die letzten Aufgaben) Datei
    • Turtlerechner Vorgabe Datei
    • Turtlerechner Lösung Datei
      Nicht verfügbar, außer: Sie sind in einer Gruppe
  • Einklappen Ausklappen

    Intermezzo: Projekte zur Verwaltung von Listen

    • Im Turtle-Rechner hatten wir Erstkontakt mit der Datenstruktur Liste. Mit dieser wollen wir uns zunächst beschäftigen und beginnen mit einem kleinen Softwareprojekt.

      Notizverwalter

      Unsere Software soll eine kleine Notiz-App werden, die beliebig viele Textnotizen verwalten, also einzelne Notizen anzeigen, hinzufügen, ändern und löschen kann. 
      Die Anzahl aller Notizen sowie die interne Nummer der Notiz soll ausgeben werden können und eine Möglichkeit zum Sortieren ist vorzusehen. Die Notizen sind redundanzarm zu speichern. 

      Zur Entwicklung der Software bietet sich die Datenstruktur Liste an.

    • Analyse und Erweiterung des Notizverwalters Aufgabe
    • 01 Notizen Lösung Datei
      Nicht verfügbar, außer: Sie sind in einer Gruppe

    • Notenverwalter

      Nachdem das Projekt Notizenverwalter gemeinsam bearbeitet wurde, gilt es nun im Projekt Notenverwalter alle notwendigen Methoden allein zu erstellen und zu prüfen.

    • Analyse und Erweiterung des Notenverwalters Aufgabe
    • 02 Notenlisten Lösung Datei
      Nicht verfügbar, außer: Sie sind in LK
  • Einklappen Ausklappen

    Sortieralgorithmen auf Listen analysieren (nur LK)

    Hervorgehoben

    • In unserem Notizverwalter hatten wir das Problem, dass uns keine Methode zum Sortieren der Listen bekannt war. Mit Trick 17 haben wir es aber dann doch mit der Listenmethode sort(null) hinbekommen. Aber ist das eine guter Sortieralgorithmus? Ist er schnell und gründlich? Was macht einen guten Algorithmus eigentlich aus?

    • Intuitive Untersuchung des Sortierens von Daten Aufgabe

      Öffnen Sie die beiden Datensammlungen in verschiedenen Tabellenkalkulationssystemen (OnlyOffice, LibreOffice Calc, MS Excel, Google Tabellen).

      1. Ermitteln Sie die Anzahl der vorhandenen Datensätze.
      2. Sortieren Sie die darin enthaltenen Daten jeweils nach einem Kriterium und schätzen Sie ab, welches Programm die Daten an schnellsten sortiert.
      3. Untersuchen Sie die Dauer des Sortierens, falls die Daten bereits sortiert sind, umgekehrt sortiert sind sowie eine beliebige Reihenfolge haben.
      4. Welche Probleme sind Ihnen beim Öffnen und Sortieren der Daten aufgefallen?

    • Untersuchungsprinzip und Hilfsmittel

    • Unsere Ergebnisse sind sehr subjektiv. Die Qualität des Sortierens hängt von vielen Faktoren ab. Gesucht ist daher eine Qualitätsbeschreibung, die unabhängig von Hardwareeigenschaften funktioniert. 

      Dazu betrachten und implementieren wir verschiedene Sortieralgorithmen in drei Szenarien:

      • best case: die Daten liegen in der korrekten Sortierung vor
      • worst case: die Daten liegen in der umgekehrten Sortierung vor
      • average case: die Daten liegen weder in best noch worst case vor

      Anschließend erfolgt das Messen von Zeiten für unterschiedlich große Datenmengen in den drei Szenarien, die grafische Darstellung, eine Hypothesenbildung, eine rechnerischen Abschätzung und eine Prognose über die Effizienz des Algorithmus.

    • Spielkarten zum Sortieren Datei
    • BlueJ-Projekt: Vorgabe Sortierverfahren Datei
    • 1. Sortierverfahren: „Sortieren durch Austausch“ – RippleSort und BubbleSort
    • 02 AB Bubblesort Datei

    • Beim Durchlaufen der Liste werden die jeweiligen Nachbarelemente miteinander verglichen und ggf. ausgetauscht. Am Ende des ersten Laufs befindet sich das größte Element am Listenende. Dieser Vorgang wird nun erneut gestartet, allerdings diesmal bis zum vorletzten Element. Danach hat man das zweitgrößte Element gefunden. Der ganze Vorgang wird nun so oft wiederholt, bis die gesamte Liste sortiert ist.

      Der Name leitet sich von Luftblasen ab, die je nach Größe nach oben steigen.

      Unserer Implementation von RippleSort folgend, könnte BubbleSort ebenfalls durch zwei geschachtelte Zählschleifen realisiert werden, also so:

      Die Analyse von best, worst und average case führt uns für diese Implementation zu einem Laufzeitverhalten von O(n2), welches sich in Analogie zu Ripplesort erklären lässt.