Metainformationen zur Seite
Der Algorithmusbegriff
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
Aufgabe 1 (zusammen, Partnerarbeit) - Ein Problem nach einer Vorgabe lösen
- Erklärt, warum die Beschreibung von Bubblesort 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 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 2 (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.