===== Ü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. {{url>https://pad.apps.mzclp.de/p/informatik10}} Bestimmt ist dir beim Tippen in dem Textfeld schon aufgefallen, dass einiges anders ist. Aber: Herzlichen Glückwunsch! Du hast soeben ein informatisches System ([[https://etherpad.org/|Etherpad]]) in Form eines kollaborativen Dokuments benutzt. ++++Mehr zu Etherpad | === Tipp 1: Mehr über Etherpad erfahren === Wahrscheinlich kennst du Etherpad schon aus deinem Unterricht - für alle anderen gibt es hier eine kurze Einführung. {{youtube>rqhbathigpc?}} ++++ ==== 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 ... {{url>https://pad.apps.mzclp.de/p/informatik10g1}} 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. - Ihr **merkt** euch diese Zahl und lasst sie irgendwo unsichtbar in einer Tasche in eurer Kleidung verschwinden. - Ihr stellt euch **irgendwie in einer Reihe** auf - Der/die Erste (Person A) in der Reihe sagt seinem linken Nachbarn (Person B) seine Zahl. Person B sagt ihre Zahl ebenfalls. - **Wenn** die Zahl von Person A größer ist, als die von Person B, **tauschen** beide die Plätze - **Ansonsten** behalten beide ihre Plätze in der Reihe - Jetzt wird der/die Zweite in der Reihe Person A und der/die Dritte Person B - **Wenn** ihr bei der vorletzten Person der Reihe angekommen seid, fangt ihr wieder bei der ersten Person an - Ihr seid fertig, **wenn** ihr einmal durch die gesamte Reihe wandern könnt, ohne dass Plätze getauscht werden - 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 [[https://de.wikipedia.org/wiki/Bubblesort|"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: - Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (**Finitheit**). - Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (**Ausführbarkeit**). - Das Verfahren darf nur endlich viele Schritte benötigen (**Terminierung**). - Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (**Determiniertheit**). - 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 | Du kannst dir hier die Umsetzung von Bubblesort in Python ansehen - einer momentan sehr weit verbreiteten Programmiersprache. def bubbleSort(arr): # Anzahl der Zahlen ermitteln n = len(arr) # Erstmal nehmen wir an, dass keine Vertauschungen notwendig waren swapped = False # Jetzt nehmen wir uns jede Zahl vor und vergleichen sie mit ihrer Nachbarzahl for i in range(n-1): # "for" ist eine Schleife, die (n-1)-mal läuft # i ist ein Zähler und erhöht sich bei jedem Durchlauf um 1 # die letzte Zahl lassen wir beim Vergleich aus # wir gehen nur bis zur vorletzten (n-1) # das sind praktisch die "Durchläufe" for j in range(0, n-i-1): # bei jedem Durchlauf müssen wir Schritt für Schritt durch die # noch nicht geprüften Zahlen gehen # Durchlauf 1 - Schritt 1, Durchlauf 1 - Schritt 2 usw. if arr[j] > arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] if not swapped: # wenn wir nichts tauschen mussten, sind wir fertig return # Zahlen, die zu sortieren sind arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print("Ausgabe der sortierten Zahlen:") for i in range(len(arr)): print("% d" % arr[i], end=" ") ++++ === Aufgabe 4 (zusammen, Partnerarbeit) - Ein Problem nach einer Vorgabe lösen === - Erklärt, warum die Beschreibung von Bubblesort in Aufgabe 3 ein Algorithmus ist! - Warum ist es kein Problem, wenn einige Zahlen mehrfach vorkommen? - Wie viele Schritte braucht man bei Bubblesort im einfachsten Fall (bereits sortierte Zahlen) immer? - **Schwierig:** Was könnte man ändern, damit der Bubblesort-Algorithmus nie terminiert? Bubblesort nutzt eine sehr grundlegende informatische Lösungsstrategie, die sich [[https://de.wikipedia.org/wiki/Teile-und-herrsche-Verfahren|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 - Schreibe die Abfolge der Durchläufe in der kurzen Schreibweise für diese Zahlenreihe auf. - Vergleiche zwischendurch immer mal wieder mit den Lösungen deiner Nachbarn. - [[loesung:bubblesort|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. {{youtube>ka24mbzv93w?}} 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 | Das Aufwändige für einen Rechner sind Vergleiche. Im Prinzip muss man für einen Vergleich eine Subtraktion durchführen und dann zwei Fälle unterscheiden: - Ist das Ergebnis 0, dann sind die Zahlen gleich - Ist das Ergebnis von 0 verschieden, dann sind die Zahlen nicht gleich Ein Tausch von Zahlen ist dagegen vergleichweise einfach - es wird intern nur ein Zeiger umgestellt. [[loesung:bubblesort|Bei Bubblesort hast du gesehen]], dass für die gegebene Zahlenreihe 40 Vergleiche notwendig sind, um den Algorithmus abzuschließen. Quicksort ist etwas schwieriger syntaktisch aufzuschreiben, aber wir schauen mal. * das aktuelle Pivotelement ist **fett** formatiert. * eine unterstrichene Zahl ist ein Zahl, die mit dem Pivot-Element verglichen wurde * die Anzahl der unterstrichenen Zahlen ist also die Gesamtzahl der Vergleiche im aktuellen Durchgang **Durchgang 1 - 6 ist Pivotelement:**\\ __3__ __7__ 1 8 2 5 9 __4__ **6**\\ 3 //4// 1 8 2 5 9 //7// **6** ( 4 und 7 wurden getauscht)\\ 3 4 __1__ __8__ 2 __5__ __9__ 7 **6**\\ 3 4 1 //5// 2 //8// 9 7 **6**( 5 und 8 wurden getauscht)\\ [ 3 4 1 5 2 ] //6// [ 9 7 //8// ] ( 6 und 8 wurden getauscht, Vergleich war unnötig, die 6 muss die kleinste Zahl sein)\\ Wir haben in diesem ersten Durchgang insgesamt 7x Zahlen miteinander verglichen. Die 6 liegt jetzt schon auf ihrer Endposition. Wir werden weiterhin ... * für das Pivot-Element **2** 3x vergleichen müssen * für das Pivot-Element **4** 2x vergleichen müssen * für das Pivot-Element **8** 1x vergleichen müssen Wir kommen also mit 13 Vergleichen aus. Quicksort ist um Größenordnungen effizienter als Bubblesort. Bei einer bereits sortierten Liste (Best-Case) bringt Quicksort keinen Nachteil gegenüber Bubblesort. ++++ ===== 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: - **Problemlösungsstrategien** lassen sich in Form eines **Algorithmus** beschreiben - Wenn man **Probleme eindeutig und kurz** beschreiben möchte, braucht man dafür eine **Syntax** - Es kann **unterschiedliche Lösungsstrategien** für das **gleiche Problem** geben (Bubblesort / Quicksort) - Lösungen können **unterschiedlich effizient** sein - Man kann **komplexe Probleme** in kleinere, **leichter lösbare Probleme zerlegen** (z.B. Divide&Conquer-Strategie)