Dies ist eine alte Version des Dokuments!
Erste Schritte in der Programmierung mit Python
Ein Algorithmus - was ist das?
Einstiegsaufgabe
Aufgabe 1
Lösen Sie diese Aufgabe schriftlich direkt in OneNote!
a) Führen Sie die folgende Rechenanleitung durch … ohne Taschenrechner;-)
- Wählen Sie eine Zahl zwischen 1 und 9.
- Verdoppeln Sie die Zahl.
- Addieren Sie 2.
- Multiplizieren Sie die Zahl mit 100.
- Halbieren Sie das Resultat.
- Wenn Sie bereits Geburtstag hatten, addieren Sie das aktuelle Jahr und subtrahieren 2100.
- Wenn Sie noch nicht Geburtstag hatten, addieren Sie das aktuelle Jahr und subtrahieren 2101.
- Subtrahieren Sie die letzten beiden Zahlen Ihres Jahrganges (z.B. bei 1991 subtrahieren Sie 91).
- Ihre Zahl sollte dreistellig sein. Die erste Ziffer besteht aus der Zahl, welche Sie sich am Anfang gemerkt haben, die letzten beiden Ziffern sind Ihr Alter in Jahren. Verblüffend, nicht?
Anmerkung: Falls sie vor dem Jahr 2000 geboren wurden, dann sollten Sie nicht 2100 sondern 2000 bezeihungsweise nicht 2101 sondern 2001 subtrahieren
b) Sie haben gerade eine Art „Algorithmus“ ausgeführt. Diskutieren Sie kurz zu zweit, welche „Eigenschaften“ eine solche Anleitung (oder Algorithmus) haben muss, um ausgeführt werden zu können?
Was ist ein Algorithmus?
Definition:
Ein Algorithmus ist eine Folge von Schritten oder Anweisungen, mit der eine Aufgabe ausgeführt oder ein Problem gelöst wird. Oft enthält ein Algorithmus sich wiederholende Schritte, Entscheidungen zwischen zwei Schritten oder nach geordneten Schritten, oder auch Schritte, die sich auf den Algorithmus beziehen oder Teilaufgaben erledigen bzw. Teilprobleme lösen. (Quelle: Programmieren ganz einfach, Die Basics für Einsteiger Schritt für Schritt, dk-Verlag, Deutsche Ausgabe 2020 München)
Eigenschaften eines Algorithmus
Damit Algorithmen befolgt (oder auch programmiert) werden können, müssen sie die folgenden Eigenschaften aufweisen:
Eindeutigkeit. Ein Algorithmus darf keine widersprüchliche Beschreibung haben. Diese muss eindeutig sein. Im Muffinsrezept müssen die Mengenangaben genau (nummerisch, in Gramm o.ä.) sein. Dies ist eine Schwierigkeit bei der Faltaufgabe. Der Text muss eindeutig sein.
Ausführbarkeit. Es darf im Algorithmus nie eine Stelle geben, die nicht ausführbar ist (durchlaufen werden kann). Der nächste Backschritt-, Faltschritt oder Rechenschritt muss klar definiert und „bearbeitbar“ (also ausführbar) sein.
Terminierung. Der Algorithmus muss ein Ende haben. Es darf lange dauern, aber es muss endlich sein, da sonst eine vollständige Bearbeitung (ein vollständiges Durchlaufen der Arbeitsanweisungen nicht möglich ist.)
Determiniertheit (Bedingtheit). Dies bedeutet in unserem Zusammenhang, dass ein Algorithmus bei gleichen Voraussetzungen stets das gleiche Ergebnis liefern muss. Er kann somit nicht einfach mit der gleichen Eingabe zwei verschiedene Ergebnisse ausgeben. Die Faltanleitung muss immer (mehr oder weniger genau) das gleiche Faltergebnis liefern.
Determinismus (Bestimmtheit). Es muss zu jedem Zeitpunkt während der Ausführung des Algorithmus nur eine Möglichkeit bestehen, den Algorithmus fortzusetzen. Als Leser bzw. ausführende Person (oder auch eine Maschine) eines Algorithmus darf man somit nie vor einer Wahl stehen.
Aufgabe 2
Lösen Sie diese Aufgabe direkt in OneNote:
a) Schauen Sie sich die folgende Faltanleitung an! Wenn Sie wollen (freiwillig), können Sie Sie auch versuchen, nachzufalten (Blätter sind bei der Lehrperson vorhanden)!
b) Diskutieren Sie zu zweit, ob bei dieser Anleitung Ihrer Meinung nach die genannten Punkte (Eigenschaften von Algorithmen) erfüllt wurden, oder nicht! Überlegen Sie sich auch, was mit diesen Punkten genau gemeint ist und ob Sie diese verstehen.
a. Eindeutigkeit: b. Ausführbarkeit: c. Terminierung: d. Determiniertheit: e. Determinismus:
Das EVA-Prinzip
Grundlage für einen Algorithmus ist das EVA-Prinzip.
E steht für Eingabe. Eingaben können über von Benutzern die Tasten, die Maus oder den Touchbildschirm direkt gemacht werden. Es können aber auch Eingaben über Sensoren oder andere Computersysteme erfolgen. Kurz kann eine Eingabe über Nutzerinteraktion, externe Informationen oder Sensoreingaben erfolgen.
V steht für Verarbeitung. Die Eingaben werden verarbeitet, meist durchlaufen Sie ein Programm. Das Programm ist oft ein in Computersprache niedergeschriebener Algorithmus.
A für Ausgabe: Die Ausgaben erfolgen über den Bildschirm, einen Drucker oder das Senden der Ausgabeinformation an ein anderes System.
In diesem Kontext sollte nun eine Definition und die Eigenschaften eines Algorithmus folgen.
Aufgabe 3 Darstellungsformen von Algorithmen
a) Im Film sehen Sie ein Muffinsrezept. Es wird aufgezeigt, was dieses mit Algorithmen zu tun hat. Schauen Sie sich das Video an, machen Sie sich Notizen zu den verschiedenen Diagrammelementen.
b) Versuchen Sie selber ein solches Flowchartdiagramm (Aktivitätsdiagramm) zu zeichnen zum Ablauf des Kochens von Spaghetti. Setzen Sie hierbei die korrekten Diagrammelemente ein (siehe Notizen zum Film):
- Startsymbol
- Rechtecke für konkrete Handlungen / Aufgaben / Operationen
- Raute (<>) für Selektion, also Entscheidungen
- Fügen Sie zusätzlich ein Ende-Symbol ein (Kreis mit „Ende“)
Aufgabe 4
Gegeben ist das folgende Diagramm (ein sogenanntes Aktivitätsdiagramm). Eine Spielfigur steht beim Pfeilsymbol im Labyrinth (Startposition).
- Auf welchem Weg verlässt die Figur das Labyrinth, wenn Sie diesen Algorithmus nutzt? (Papierversionen des Labyrinths liegen bereit). Arbeiten Sie zu zweit.
- Wie muss das Labyrinth oder die Startposition oder beides verändert werden, damit dieser Algorithmus nicht mehr zum Ausgang führt? Hierbei darf der Ausgang des Labyrinths nicht aufgehoben werden, was die triviale Antwort auf die Frage wäre.
| Labyrinth | Aktivitätsdiagramm |
|---|---|
 |  |
Freiwillige Zusatzaufgabe 5: Berühmte Algorithmen
- Zwei bekannte Algorithmen sind der PageRank-Algorithmus oder der Dijkstra-Algorithmus. Informieren Sie sich, welche Aufgaben diese Algorithmen übernehmen bzw. welche Probleme diese lösen.
- Was haben Algorithmen mit personalisierter Werbung oder Chatbots zu tun? Erklären Sie!