Zuletzt angesehen: • first

Menu

Aufklappen

Inhaltsverzeichnis

Über Algorithmen

Lernziele

obligatorisch

  • du kannst mit einem kollaborativen Dokument arbeiten
  • du entwickelst gemeinsam mit anderen eine Lösungsstrategie für ein Sortierproblem
  • du setzt gemeinsam mit anderen ein dir bisher unbekannte Lösungsstrategie um
  • du kennst den Fachbegriff Algorithmus, seine Merkmale und kannst Bezüge zum Bubblesort-Algorithmus herstellen
  • du kannst mit einer abstrakten Syntax den Algorithmus Bubblesort auf Papier umsetzen
  • du kennst die Lösungsstrategie „divide & conquer“ als einen grundlegenden Ansatz in der Informatik
  • du kennst mit dem algorithmischen Problemlösen einen Teilbereich der Informatik

fakultativ

  • du setzt den Quicksort-Algorithmus gemeinsam mit anderen um
  • du kannst mit einer abstrakten Syntax den Algorithmus Bubblesort und Quicksort auf Papier umsetzen
  • du vergleichst Quicksort und Bubblesort hinsichtlich ihrer Effizienz

Deine Erfahrung

Aufgabe 1 (alleine) - Deine Ideen zur Informatik

Was ist für dich Informatik? Tippe deine Ideen in die Box unter dieser Aufgabenstellung. Recherchiere dafür nicht vorher im Internet. Es geht erstmal um deine Ideen.

Bestimmt ist dir beim Tippen in dem Textfeld schon aufgefallen, dass einiges anders ist. Aber: Herzlichen Glückwunsch! Du hast soeben ein informatisches System (Etherpad) in Form eines kollaborativen Dokuments benutzt.

Mehr zu Etherpad

Informatik löst Probleme

Aufgabe 2 (zusammen, zwei Gruppen) - Ein einfaches Problem

Stellt euch in eurer Gruppe möglichst schnell nach der Schuhgröße auf. Beschreibt in dem unteren Kasten genau, wie ihr dieses Problem gelöst habt. Die andere Gruppe sollte nach eurer Anleitung ohne weitere mündliche Erklärungen eure Strategie später umsetzen können. Das prüfen wir dann auch …

Ihr habt eine klassisches informatisches Problem bearbeitet - es muss sehr oft etwas sortiert werden, z.B.

  • Artikel in Onlineshops nach dem Preis
  • Klassenlisten nach Alphabet
  • McDonalds-Filialen nach der Entfernung von euch
  • […]

Eine formale Sortierstrategie

Vielleicht habt ihr gemerkt, dass das mit dem Umsetzen von (fremden) Anleitungen gar nicht so einfach ist. Dafür muss man sehr präzise sein.

Aufgabe 3 (zusammen, zwei Gruppen) - Ein Problem nach einer Vorgabe lösen

Ihr bekommt alle eine Zahl auf einem Zettel.

  1. Ihr merkt euch diese Zahl und lasst sie irgendwo unsichtbar in einer Tasche in eurer Kleidung verschwinden.
  2. Ihr stellt euch irgendwie in einer Reihe auf
  3. Der/die Erste (Person A) in der Reihe sagt seinem linken Nachbarn (Person B) seine Zahl. Person B sagt ihre Zahl ebenfalls.
  4. Wenn die Zahl von Person A größer ist, als die von Person B, tauschen beide die Plätze
  5. Ansonsten behalten beide ihre Plätze in der Reihe
  6. Jetzt wird der/die Zweite in der Reihe Person A und der/die Dritte Person B
  7. Wenn ihr bei der vorletzten Person der Reihe angekommen seid, fangt ihr wieder bei der ersten Person an
  8. Ihr seid fertig, wenn ihr einmal durch die gesamte Reihe wandern könnt, ohne dass Plätze getauscht werden
  9. Prüft das am Schluss noch einmal, indem ihr in der Reihe stehen bleibt und alle eure Zahlen zeigt

Diskutiert die Unterschiede zwischen dieser Sortierstrategie und eurer eigenen aus Aufgabe 2!

Du hast mit der Beschreibung einen ersten Algorithmus kennengelernt! Diesen gibt es tatsächlich und er nennt sich "Bubblesort".

Lernen: Merkmale eines Algorithmus wissen, erklären und anwenden können

Ein Algorithmus ist eine Vorschrift zur Lösung eines Problems. Er hat folgende Eigenschaften:

  1. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
  2. Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
  3. Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung).
  4. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
  5. Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Algorithmen werden in der Informatik mit Programmiersprachen umgesetzt. Das sind Sprachen, mit denen sich Lösungsstrategien sehr gut und eindeutig formulieren lassen. Diese Sprachen unterscheiden sich voneinander in ihrer Syntax und ihren Möglichkeiten. Wie du noch sehen wirst, muss so eine Sprache noch nicht einmal Text enthalten - einfache Symbole oder gar Farben erfüllen auch diesen Zweck.

Bubblesort in der Programmiersprache Python

Aufgabe 4 (zusammen, Partnerarbeit) - Ein Problem nach einer Vorgabe lösen

  1. Erklärt, warum die Beschreibung von Bubblesort in Aufgabe 3 ein Algorithmus ist!
  2. Warum ist es kein Problem, wenn einige Zahlen mehrfach vorkommen?
  3. Wie viele Schritte braucht man bei Bubblesort im einfachsten Fall (bereits sortierte Zahlen) immer?
  4. Schwierig: Was könnte man ändern, damit der Bubblesort-Algorithmus nie terminiert?

Bubblesort nutzt eine sehr grundlegende informatische Lösungsstrategie, die sich divide&conquer nennt („teile und bewältige“). Es werden immer nur zwei Zahlen (divide) aus einer großen Menge von Zahlen miteinander verglichen (conquer). Das Problem, welche Zahl größer ist, lässt sich sehr einfach und mit wenig Aufwand lösen.

Bubblesort einmal abstrakt in einer Syntax

Wir nehmen einmal an, dass die Zahlen 3,7,1 und 8 zu sortieren sind.

Durchlauf 1.1: 3 7 1 8 (nichts tauschen)

Durchlauf 1.2: 3 7⇔1 8 (1 gegen 7 tauschen)

Durchlauf 1.3: 3 1 7 8 (nichts tauschen, am Ende angekommen, von vorne)

Durchlauf 2.1: 3⇔1 7 8 (3 gegen 1 tauschen)

Durchlauf 2.2: 1 3 7 8 (nichts tauschen)

Durchlauf 2.3: 1 3 7 8 (nichts tauschen, am Ende angekommen, von vorne)

Durchlauf 3.1: 1 3 7 8 (nichts tauschen)

Durchlauf 3.2: 1 3 7 8 (nichts tauschen)

Durchlauf 3.3: 1 3 7 8 (nichts tauschen, am Ende angekommen und vorher nichts getauscht - wir sind fertig)

Wir brauchen also neun einzelne Vergleiche, um die vier Zahlen zu sortieren. Vergleiche sind die aufwändigste Operation beim Sortieren. Wir müssen in den dritten Durchlauf, da wir noch keinen Durchlauf ohne Tausch hatten. Eine kürzere Schreibweise (Syntax) ohne Kommentare könnte so aussehen:

1.1: 3 7 1 8

1.2: 3 7⇔1 8

1.3: 3 1 7 8

2.1: 3⇔1 7 8

2.2: 1 3 7 8

2.3: 1 3 7 8

3.1: 1 3 7 8

3.2: 1 3 7 8

3.3: 1 3 7 8

Aufgabe 5 (alleine) - eine Syntax umsetzen

Folgende Zahlenfolge ist gegeben: 3, 7, 1, 8, 2, 5, 9, 4, 6

  1. Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf.
  2. Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn.
  3. Lösung

Hardcore: Quicksort

Wenn du diesen Abschnitt nicht lösen oder bearbeiten kannst, ist das nicht schlimm. Schau dir dieses Video bis zum Zeitindex 5:00 an.

Es wird dir ein weiterer Sortieralgorithmus mit dem Namen Quicksort angezeigt. Es wird die gleiche Zahlenfolge wie eben sortiert.

  • Könntest du das Verfahren in einer Gruppe durchspielen wie bei Bubblesort?
  • Was sagt dein Gefühl über die Anzahl der Vergleiche, die für die Sortierung benötigt werden, im Unterschied zu Bubblesort?

Auflösung

Ja, und was ist jetzt mit Informatik?

Für eine ganz präzise Formulierung ist es jetzt noch zu früh, aber du hast unglaublich wichtige Grundprinzipien eines Teilbereichs der Informatik (algorithmisches Problemlösen) kennen gelernt:

  1. Problemlösungsstrategien lassen sich in Form eines Algorithmus beschreiben
  2. Wenn man Probleme eindeutig und kurz beschreiben möchte, braucht man dafür eine Syntax
  3. Es kann unterschiedliche Lösungsstrategien für das gleiche Problem geben (Bubblesort / Quicksort)
  4. Lösungen können unterschiedlich effizient sein
  5. Man kann komplexe Probleme in kleinere, leichter lösbare Probleme zerlegen (z.B. Divide&Conquer-Strategie)
Nach oben