Hempel: Informatik 12 GK/LK - D Algorithmen und Daten

Kursthemen

• 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 Problemlösens in der imperativen Sprache Java aus Klasse 10 wiederholen und festigen. Die Implementierung einfacher Algorithmen und Sortierverfahren bereitet das komplexe Thema der Softwareentwicklung vor. Der Leistungskurs beurteilt zudem Algorithmen hinsichtlich ihrer Effizienz.

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

  Stand 2023-10-02: Dieser Kurs wird aktuell nicht mehr gepflegt.

  Lehrbücher:

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

  • Kommunikation im Kurssystem

    Neben der direkten Kommunikation mithilfe des Moodle-Mitteilungsdienstes, der auch auf der App funktioniert und der E-Mail-Option, gibt es öffentliche Austausch- und Informationsmöglichkeiten in den Foren.

  • 

    Ankündigungen Forum
  • Software im Themenfeld

    Der Großteil der im Unterricht eingesetzten Programmwerkzeuge ist als Open Source oder Freeware deklariert. Für Hausaufgaben oder zum Nachvollziehen der Unterrichtsbeispiele kann der IoStick für die Sekundarstufe II benutzt werden. 

  • 

    Informatik on Stick mit allen Programmen - IoStick Link/URL
  • 

    LK: Programm zur Untersuchung von Sortieralgorithmen Link/URL
  • 

    Online-Java Textseite
  • Tafelwerksergänzungen

    Die Abituraufgabenkommission Informatik M-V stellt für die Themengebiete Algorithmen und Daten sowie Softwareentwicklung Tafelwerksergänzungen zur Verfügung, da gedruckte Tafelwerke nicht alle benötigten Informationen enthalten. Die Verwendung dieser Ergänzungen ist stets erlaubt. 

  • 

    Tafelwerksergänzungen Verzeichnis

• 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.

    

  • 

    Seymour Papert war Professor für Mathematik und Erziehungswissenschaften am Massachusetts Institute of Technology. Seine Ziele waren die Entwicklung informatischer Fähigkeiten der Schüler bei gleichzeitiger Mündigkeit von der IT. Er entwickelte in den 1960er die Programmiersprache LOGO, in der es eine Turtle - also eine Schildkröte - gab, die man durch Befehle steuern konnte. Sie zeichnete den abgelaufenen Weg. Kinder konnten so geometrische Figuren programmieren und zeichnen.

    ... und wir auch!

    Unsere Turtle verfügt über Befehle zum Bewegen und Drehen, kann aber auch die Stiftfarbe ändern. Eine Übersicht über die Fähigkeiten unserer Turtle 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, es sei denn: Sie sind in LK
  • 

    Aufgaben Einfache Schleifen Link/URL
  • 

    Lösungen Einfache Schleifen Datei

    Nicht verfügbar, es sei denn: Sie sind in LK
  • 

    Aufgaben Verschachtelte Schleifen Link/URL
  • 

    Lösungen Verschachtelte Schleifen Datei

    Nicht verfügbar, es sei denn: Sie sind in LK
  • 

    Aufgaben Verzweigungsfiguren Datei
  • 

    Lösungen Verzweigungen Datei

    Nicht verfügbar, es sei denn: Sie sind in LK
  • 

    Komplexe Übungen Teil 1 Datei
  • 

    Aufgaben Komplexe Übungen Link/URL
  • 

    Komplexe Übungen Teil 1 Lösungen Datei

    Nicht verfügbar, es sei denn: Sie sind in LK
  • 

    Lösungen Komplexes Datei

    Nicht verfügbar, es sei denn: Sie sind in LK
  • 

    Erläuterungen Rekursion Link/URL
  • 

    Aufgaben Rekursion Link/URL

• 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 Datei
  • 

    Übersicht: Listen in Java Datei
  • 

    Turtlerechner Vorgabe Datei
  • 

    Turtlerechner Lösung Datei

    Nicht verfügbar, es sei denn: Sie sind in LK

• Intermezzo: Projekte zur Verwaltung von Listen
  • Die Sommerferien sind um und wir starten in das dritte und kurze Semester. Beginnen wir mit einem kleinen Softwareprojekt, dass an die letzten Aufgaben des Turtle-Rechners aus dem Vorjahr anknüpft - den Umgang mit Listen.

    Notizverwalter

    Unsere Software soll beliebig viele Textnotizen verwalten, also einzelne Notizen anzeigen, hinzufügen, ändern und löschen können.
    Das Programm soll die Anzahl aller Notizen sowie die interne Nummer der Notiz ausgeben können.
    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, es sei denn: Sie sind in LK
  • Notenverwalter

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

  • 

    Analyse und Erweiterung des Notenverwalters Aufgabe
  • 

    02 Notenlisten Lösung Datei

    Nicht verfügbar, es sei denn: Sie sind in LK

• Sortieralgorithmen auf Listen analysieren

  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

  • 

    Untersuchung des Verfahrens RippleSort Aufgabe
  • Beginnen wir mit der Untersuchung eines bekannten Verfahrens, welches verbal und als Struktogramm vorliegt – RippleSort

    Das erste Element der Liste wird schrittweise mit allen nachfolgenden Elementen verglichen. Ist das erste Element größer als das Vergleichselement, so werden die Elemente getauscht. Nach dem ersten Listendurchlauf steht das kleinste Element der Liste am Listenanfang. Nun wird das zweiten Element nach gleichen Prinzip schrittweise mit allen nachfolgenden Elementen verglichen und ggf. mit dem Vergleichselement getauscht. Nach dem zweiten Listendurchlauf steht das zweitkleinste Element der Liste fest. Der Algorithmus wird solange fortgesetzt, bis alle Elemente der Liste mit den nachfolgenden Elementen nach diesem Prinzip behandelt wurden.

    

    Der Name leitet sich von denen wie kleine Wellen nach vorn schiebenden Elementen ab.

    Eine grafische Darstellung des verbalen Algorithmus zeigt folgendes Struktogramm.

    

  • 

    Lösung Klasse Ripplesort für das BlueJ-Projekt Datei
  • Auswertung der Untersuchung von RippleSort in BlueJ bzw. in einer Simulation

    Die Auswertung legt die Vermutung nahe, dass es zwischen der Anzahl der Vergleiche und der Anzahl der Elemente einen quadratischen Zusammenhang gibt, denn:

    • Erhöht sich die Anzahl der Elemente um den Faktor 10, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 100.
    • Erhöht sich die Anzahl der Elemente um den Faktor 5, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 25.
    • Erhöht sich die Anzahl der Elemente um den Faktor 2, so erhöht sich die Anzahl der Vergleiche ca. um den Faktor 4.

    Das heißt aber auch, dass es wahrscheinlich einen quadratischen Zusammenhang zwischen der Gesamtzeit des Sortierens der Liste und der Anzahl der Elemente gibt. Stellt man dies grafisch dar, so kann man einen Parabelast vermuten.

    

    Bildet man den Proportionalitätsfaktor, so untermauert dieser die Hypothesen: V(n ) ~ n² bzw. T(n ) ~ n²

    Können wir dies erklären?

    1. Beim ersten Durchlaufen wird das erste Element mit allen weiteren Elementen verglichen, also mit n – 1 Elementen. 
    2. Beim zweiten Durchlauf wird das erste Element nicht mehr berücksichtigt, es wird das zweite Element mit den nachfolgenden verglichen, also mit n – 2 Elementen. 
    3. Beim dritten Durchlauf wird ... bis zum letzten Element. 

    Der gesamte Sortiervorgang ist also nach V(n ) = ((n – 1) + (n – 2) + ... + 2 + 1) Vergleichen beendet.
    Die in der Formel enthaltene Summierung lässt sich mithilfe der Gaußschen Summenformel umschreiben zu
    V(n ) = ½(n² - n) ≈ ½n².

    Diese Überlegung kann man für den worst case auch für die Vertauschungen machen. Auch dort ergibt sich ein quadratischer Zusammenhang. Da jeder Vergleich und eine Vertauschung eine bestimmte Anzahl von Rechentakten benötigt, können diese als eine Abschätzung der Laufzeit eines Algorithmus unabhängig von der Taktfrequenz eines Prozessors verwendet werden. 

    Die Laufzeit eines Algorithmus kann durch die Anzahl der für den Algorithmus notwendigen Elementaroperationen beschrieben werden.

    In der Regel interessiert nicht die exakte Anzahl Elementaroperationen, sondern eine grobe Abschätzung mithilfe einer oberen Schranke. Man nutzt dazu Klassenbezeichnungen mithilfe des Landau-Symbols O. In unserem Fall liegt eine quadratische Funktion vor. Dies wird als O(n²) abgeschätzt und bedeutet, dass sich die Laufzeit des Algorithmus höchstens wie n² verhält. Damit haben wir einen Ausdruck, der die zeitliche Qualität eines Algorithmus beschreibt. 

    RippleSort hat im worst, average und best case ein Laufzeitverhalten von O(n²).

  • Sortieren durch Austauschen zweier Elemente lässt sich aber auch noch anders realisieren – 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(n²), welches sich in Analogie zu Ripplesort erklären lässt.

  • 

    Lösung Klasse Buublesort für das BlueJ-Projekt Datei
  • Unsere Implementierung hat aber noch Verbesserungspotential: Wird ein Durchlauf ohne jeglichen Tausch absolviert, so sind die Daten sortiert und der Sortiervorgang kann also beendet werden. Daher bietet sich statt einer Zählschleife eine weniger starre Schleife an, in deren Kopf dies als flexible Abbruchbedingung notiert werden kann. 

    

    Damit erreicht BubbleSort im best case das Laufzeitverhalten von O(n ).

  • 

    Lösung Klasse BubblesortII für das BlueJ-Projekt Datei
  • 2. Sortierverfahren: „Sortieren durch Auswählen“ - SelectSort

  • 

    Verfahren, Implementierung, Analyse Aufgabe
  • 3. Sortierverfahren: „Sortieren durch Einfügen“ - InsertSort

  • 

    Verfahren, Implementierung, Analyse Aufgabe
  • 

    Lösungen Textseite
  • Zusammenfassung des Laufzeitverhaltens der bisher untersuchten Verfahren

    	best case	worst case	(average case)
    RippleSort	O(n2)	O(n2)	O(n2)
    BubbleSortII	O(n )	O(n2)	O(n2)
    SelectSort	O(n2)	O(n2)	O(n2)
    InsertSort	O(n )	O(n2)	O(n2)

    Im worst case und (nicht näher untersuchten) average case liegt stets eine quadratische Laufzeit vor. Bedeutet dies, dass es keine besseren Sortieralgorithmen gibt oder müssen wir einfach nur einen anderen Denkansatz verwenden?

  • 4. Sortierverfahren: „Sortieren durch Mischen“ - MergeSort

  • 

    04 AB Mergesort Datei
  • Das MergeSort-Verfahren nutzt das fundamentale informatische Prinzip „Teile und Herrsche“. 
    Es findet eine Zerlegung des Problems der Größe n (Sortierung von n Elementen) in zwei Teilprobleme kleinerer Größe (Sortierung der Hälfte der n Elemente) statt, die jeweils gelöst und anschließend zu einer Gesamtlösung des Grundproblems zusammengesetzt werden.

    Der prinzipielle Ablauf erfolgt in 3 Schritten:

    1. Zerlegung der Menge in zwei Teilmengen
    2. Sortierung der beiden Teilmengen
    3. Mischen der Teilmengen zu einer Menge, wobei nur die beiden ersten Elemente der Teilmengen miteinander verglichen werden und das kleinere der beiden in die Gesamtmenge übernommen wird. Dieser Vorgang wird sooft wiederholt, bis keine Elemente mehr in den Teilmengen vorhanden sind. Sollte eine Teilmenge leer sein, können alle Elemente der anderen Teilmenge zur  Gesamtmenge hinzufügt werden. 

    Dieser prinzipielle Ablauf wird jedoch rekursiv ausgeführt, d. h. die Zerlegung wird solange fortgesetzt, bis nur noch ein Element der Menge übrig ist. Dieses ist dann bereits sortiert und man kann die Rekursion mit dem Mischen auflösen.

    Beispiel: 

    Unsere Implementation besteht nun aus zwei Teilen. Dies ist dem rekursiven Algorithmus geschuldet. Zunächst das Struktogramm mit dem Teilen der Liste, dem rekursiven Aufrufen von Mergesort für die beiden Teillisten und das anschließende Zusammenfügen der sortieren Teillisten durch Mischen. 

    

    Für das Mischen ist nachfolgende Visualisierung zu nutzen. 

    

  • Untersuchung des Laufzeitverhaltens von MergeSort im worst-case

    • Um zwei Teilfelder zu einem zu verschmelzen, ist 1 Schritt notwendig.
    • Um vier Teilfelder zu einem zu verschmelzen sind 2 Schritte notwendig.
    • Um acht Teilfelder zu einem zu verschmelzen sind 3 Schritte notwendig. usw.

    Demzufolge existiert ein Zusammenhang zwischen der Schrittzahl und der Anzahl der Teilfelder, nämlich: Teilfeldzahl = 2^Schrittzahl. 
    Die Gleichung lässt sich nach der Schrittzahl umformen zu:

    Schrittzahl = log₂(Teilfeldzahl)

    Also: Zum Zerlegen und zum Verschmelzen benötigt man einen Zeitaufwand von jeweils O(log₂n). Für jedes Verschmelzen ist jeweils ein Vergleichsdurchlauf erforderlich, der einmal durch das Teilfeld läuft. Sein Zeitaufwand lässt sich also mit O(n ) abschätzen. 

    Somit hat Mergesort einen Zeitaufwand von O(n·log₂n). 

    Hinweis: In der informatischen Literatur wird häufig die Basis des Logarithmus weggelassen, da sie bezüglich der O-Notation keine spezielle Bedeutung hat. Man spricht meist vom 2er-Logarithmus.