Algorithmen I: Einfache Algorithmen und Struktogramme LEGACY

Slides: 2022_algorithmen_i.pdf

Definition Algorithmus:

• Ein Algorithmus ist eine Abfolge eindeutiger Handlungsanweisung für die Lösung von Problemen.
• Eindeutig bedeutet, dass jeder Einzelschritt zu $100\%$ klar ist und keinen Interpretationsspielraum lässt.
• Algorithmen können in verschiedenen Sprachen formuliert werden wie menschliche Sprachen oder Programmiersprachen.
• Für die Problemlösung wird eine bestimmte Eingabe (Input) Schritt für Schritt in eine bestimmte Ausgabe (Output) überführt.

Analogie: Algorithmus ist wie ein (sehr klares) Kochrezept

Algorithmus für die Herstellung von Karamell-Bonbon formuliert auf drei verschiedenen Arten/Sprachen:

100 g Zucker und 2 EL Wasser in Pfanne geben. Bei mittlerer Hitze erwärmen, bis der Zucker goldbraun ist. Das Caramel auf geölte Alufolie geben und auskühlen lassen.

Pseudocode ähnelt höheren Programmiersprachen (wie z.B. Python), gemischt mit natürlicher Sprache und mathematischer Notation. Damit kann er nicht von einem Computer ausgeführt werden.

topf.input(sugar(100,g),water(2,es))
platte.on(.75)
while not(topf.inhalt.getcolor() == "goldbraun")
    warte(1000,ms) 
alufolie.input(topf.inhalt ())
platte.off()
while not(alufolie.inhalt.gettempdeg() < 20)
    warte(10000,ms) 

• Regeln:
  • Person ist blind, sieht also nichts.
  • Person hat kein Gefühl für Distanzen. „Laufe $2$m nach vorne“ ist also unzulässig. Was hingegen geht ist „Mache einen Schritt nach vorne“.
  • Person kann sich drehen, z.B. „Drehe dich um 90 Grad nach rechts“.
  • Einzige Sensoren, die Person hat sind nach vorne gerichtete Hände. Mit diesen können Hindernisse (Wände und Tische) detektiert werden.
  • Die Wege sollen frei von Rucksäcken usw. sein. Andere Personen werden ignoriert.
• Ausführen:
  • Nimm Algorithmus von Kollegin …
  • und befolge diesen genau so, wie er da steht.
  • Führt dich der Algorithmus zum Ziel?
    
    
• Zusatzaufgabe: Der Algorithmus soll von jedem beliebigen Sitzplatz im Schulzimmer funktionieren. Passe deinen Algorithmus entsprechend an.
  
  

• Regeln:
  • $21$ Bleistifte
  • Zwei Spieler:innen nehmen abwechselnd je 1-3 Stifte weg.
  • Wer die letzten Stifte nehmen kann, hat gewonnen.
• Warum ist das Spiel interessant?
  • Es gibt eine optimale Spielstrategie, …
  • welche dem Computer als Algorithmus beigebracht werden kann.
• Auftrag & Ziel:
  • Gegeneinander spielen (verwendet eure Stifte)
  • Optimale Spielstrategie finden …
  • … und als Algorithmus in menschlicher Sprache formulieren
• Online-Spiel: https://upload.wikimedia.org/wikipedia/commons/4/4d/Subtraction_game_SMIL.svg

  

Struktogramme bieten eine Möglichkeit, um Algorithmen zu formulieren. Sie weisen Elemente, die typischerweise in Programmiersprachen vorkommen, beinhalten aber auch normale (menschliche) Sprache.

Wir verwenden für unsere Struktogramme die folgenden drei Elemente:

1. Anweisungen: einfache Befehle, pro Befehl eine Zeile / ein Rechteck
2. Solange-Schleife: Wiederholt die darin enthaltenen Anweisungen solange, wie die Bedingung erfüllt ist.
3. Verzweigungen: Je nach dem, ob die Bedingung erfüllt ist oder nicht, werden andere Befehle ausgeführt.

• Schreibe deinen Algorithmus, der eine Person zum Wasserhahn bringt als Struktogramm um. Verwende nur die vorgegebenen drei Arten von Elementen.
• Erweitere Algorithmus: Die Person soll, nachdem sie den Wasserhahn erreicht hat, Wasser davon trinken.
• Es kann sein, dass Wasserhahn bereits läuft.

Wandle das Flussdiagramm mit dem Algorithmus zur Herstellung von Karamell-Bonbons in ein Struktogramm um.

Der 'Computer' spiele gegen eine Spieler:in. Schreibe den Algorithmus, mit dem der Computer das Subtraction Game spielen soll, als Struktogramm für drei verschiedene Versionen:

1. Der Computer soll immer beginnen und natürlich immer das Spiel gewinnen.
2. Diesmal soll die Spieler:in beginnen. Der Computer soll gewinnen, sobald die Spieler:in einen Fehler macht.
3. Erweitere dein Struktogramm aus 2., so dass beide Fälle (Computer beginnt (nicht)) abgedeckt sind.

In den nächsten Lektionen wollen wir einige mathematischen Algorithmen anschauen und selber schreiben. Zum Beispiel können wir ein Struktogramm schreiben, bei welchem man eine Zahl eingeben kann und welches dann bestimmt, ob es sich …

• um eine gerade oder ungerade Zahl handelt.
• um eine positive oder negative Zahl handelt.
• um die Lieblingszahl deiner Mathelehrperson handelt.

Eine Eingabe notieren wir wie folgt: Die eingegebene Zahl muss irgendwie gespeichert werden. Dazu verwenden wir Variablen. Hier hat die Variable den Namen $x$ gespeichert werden soll. Natürlich kann man auch andere Variablennamen verwenden, es können auch Wörter sein. Mit dem Ausdruck in der Klammer geben wir an, ob man eine Zahl oder Text (resp. String, siehe unten) eingeben soll.

Einer Variablen kann man auch direkt und ohne Eingabe einen Wert zuweisen:

Im ersten Beispiel weisen wir der Variablen x die Zahl $42$ zu. Im zweiten Beispiel wird der Variablen name Text zugewiesen - in der Informatik spricht man dabei von einem String. Beachte, dass wir für String Anführungs- und Schlusszeichen verwenden, um zwischen Variablen und Text zu unterscheiden:

Beachte, dass das Einzelgleich ($=$) ein Zuweisungsoperator ist. Mit diesem weist man einer Variablen auf der linken Seite den Wert auf der rechten Seite zu. Folgende Anweisungen machen deshalb also keinen Sinn:

• 3 = i Problem: Variable steht rechts
• 2*i = 3 Problem: Variable links steht nicht alleine

Um etwas auszugeben, zum Beispiel ein Resultat, schreiben wir:

In Solange-Schleifen und Falls-Verzweigungen werden immer Bedingungen überprüft, zum Beispiel 'Solange x kleiner als 7' oder 'Falls alter gleich 27'. Um dies etwas mathematischer auszudrücken, verwenden wir Vergleichsoperatoren:

• 'Solange x kleiner als 7' → 'Solange x < 7'
• 'Falls alter gleich 27' → 'Falls alter == 27'
• Weitere Vergleichsoperatoren sind '>' (grösser), '>=' und '⇐' (grösser gleich und kleiner gleich), '!=' ungleich.

Beachte, dass wir das Doppelgleich == schreiben, um in einer Bedingung Gleichheit zu überprüfen. Zur Erinnerung: Das Einzelgleich = wird bereits als Zuweisungsoperator verwendet!

Beispiel: Die folgenden beiden Notationen sind gleichwertig:

Schreibe das Struktogramm für einen einfachen Taschenrechner, der zwei Zahlen addieren kann. Die Benutzer:in soll zuerst nacheinander die beiden Zahlen eingeben können, das Resultat wird dann ausgegeben.

Ähnlich wie die vorherige Aufgabe, nur soll der neue Code neben der Addition auch die Subtraktion beherrschen. Die Benutzer:in muss neben den beiden Zahlen also auch eingeben, welche Operation sie ausführen möchte (z.B. 'a' für Addition und 's' für Subtraktion). Achtung, Operatoren (wie $+,-,*,/$ können nicht in Variablen gespeichert werden, $op = +$ geht also nicht.

Zusatzaufgabe:

Erweitere das Struktogramm so, dass auch noch Multipliziert und Dividiert werden kann.

Die Benutzer:in soll ihr Alter eingeben. Das Struktogramm sagt ihr dann, welche Getränke (Sirup, Bier, Schnapps) sie in der Schweiz legal trinken darf.

Die Benutzer:in soll eine positive ganze Zahl eingeben. Das Struktogramm soll dann einen Countdown, startend bei der eingegebenen Zahl, ausgeben.

Beispiel: Wird $5$ eingegeben, gibt das Struktogramm aus: $$5$$$$4$$$$3$$$$2$$$$1$$$$\text{Los!}$$

Zusatzaufgabe: Die Aufgabe macht nur Sinn, wenn die Benutzer:in auch wirklich eine positive ganze Zahl eingibt. Der Code hat ein Problem, wenn man z.B. $-5$ (negativ) eingibt. Erweitere deinen Code nun wie folgt: Überprüfe zuerst die Eingabe und lasse den Countdown code nur dann laufen, wenn die Eingabe in Ordnung ist. Falls nicht, gibst du eine enstsprechende Rückmeldung (z.B. „Eingabe nicht zulässig, kein Countdown möglich!“) und der Code wird abgebrochen.

Schreibe ein Struktogramm für ein Ratespiel, in dem die Benutzer:in dein Lieblingsessen (oder etwas anderes Lieblings…) erraten soll. Das Spiel soll solange wiederholt werden, bis die richtige Antwort erraten wurde.

Betrachten wir ein einfaches Struktogramm:

• Es soll eine positive Zahl eingegeben werden (Eingabe)
• Der Algorithmen soll dann alle Zahlen von $1$ bis zu dieser Zahl ausgeben (Ausgabe).
• Beispiel: Wird $5$ eingegeben, sollen die Zahlen $1,2,3,4,5$ ausgegeben.

Das folgende Struktogramm macht genau das:

Code im Detail:

• In Zeile 1 wird man aufgefordert, eine Zahl einzugeben. Diese wird in der Variablen $x$ gespeichert.
• In Zeile 2 wird eine Variable $i$ definiert und es wird ihr der Wert $1$ zugewiesen. Die Idee ist dann, diese Zahl solange zu erhöhen, bis sie $x$ erreicht hat.
• Dazu überprüfen wir in Zeile 3 die Bedingung, ob $i <= x$ (kleiner gleich) ist.
• Falls ja, wird in Zeile 4 der Wert von $i$ ausgegeben.
• In Zeile 5 wird der Wert von $i$ dann um $1$ erhöht ($i = i + 1$). Erinnere dich, dass in der Programmierung das Einzelgleich $=$ ein Zuweisungsoperator ist: Es weist der Variablen auf der linken Seite den Wert, der rechts steht, zu.

Um eine Algorithmus in Form eines Struktogramms genau zu verstehen, evaluieren wir diesen Schritt-für-Schritt in einer Tabelle: Dabei gilt:

• Spalte ganz links: heisst Bedingungen, notiere hier Bedingungen von Schleifen und Verzweigungen und Angabe, ob erfüllt oder nicht (True / False)
• Spalte ganz rechts: heisst Ausgabe, notiere hier Werte, die ausgegeben werden
• Spalten dazwischen: Werte von Variablen in Reihenfolge, in der sie im Code vorkommen
• Pro ausgeführte Zeile Code, genaue eine Zeile in der Tabelle!

1. Evaluiere den Algorithmus mit den angegebenen Werten in einer Tabelle.
2. Beschreibe in einem Satz, was der Algorithmus genau macht.

Erstelle das Struktogramm des Algorithmus und evaluiere dieses für 1-2 Beispiele wie oben gelernt in Tabellen:

Maximum: Zwei Zahlen sollen eingegeben und die grössere der beiden Zahlen ausgegeben werden.

Sortieren: Drei Zahlen sollen eingegeben werden und danach in absteigender Reihenfolge der Grösse ausgegeben werden.

2er Potenzen: Es soll eine (positive ganze) Zahl eingegeben. Es sollen dann die ersten Zweierpotenzen ausgegeben werden und zwar genau so viele, wie die eingegebene Zahl. Beispiele:

• Eingabe: $1$, Ausgabe: $2$
• Eingabe: $6$, Ausgabe: $2,4,8,16,32,64$

Schreibe das Struktogramm für ein Ratespiel: Eine geheime Zahl wird in einer Variablen gespeichert. Die Spieler:in versucht solange, die geheime Zahl zu erraten, bis sie erfolgreich ist.

Erweiterungen:

• Das Programm gibt der Spieler:in Tipps, z.B. `Ausgabe: „Die eingegebene Zahl ist zu klein“’
• Die Anzahl Fehlversuche wird gezählt und am Schluss ausgegeben.
• eigene Ideen umsetzen