Algorithmen I

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 alufolie.inhalt.gettempdeg() > 25
    warte(10000,ms) 

• 2er Gruppen
• Jede Person nimmt Blatt Papier (ja Papier, nicht Laptop!!!)
• Notiere für Partner:in Algorithmus, der sie von aktueller Position (wahrscheinlich am Pult sitzend) zum Wasserhahn des Zimmers bringt.
• Notiere den Algorithmus in normaler Sprache.
  
  
• Regeln:
  • Person kann nur gerade aus …
  • und maximal $50$cm weit sehen.
  • „Schau wo der Wasserhahn ist und geh' dorthin“ geht also nicht!
  • Person hat kein Gefühl für Distanzen $>50$cm. „Laufe $2$m nach vorne“ ist also unzulässig.
  • Person hat Gefühl für Winkel (weiss also z.B. was ein $90^\circ$ Winkel ist).
  • Augen sind einzige Sensoren (Hände usw. dürfen nicht verwendet werden z.B. um Wand abzutasten).
  • Tische sind wie Wände, werden von den Sensoren (Augen) also detektiert.
    
    
• Ausführen:
  • Nimm Algorithmus von Kolleg:in …
  • und befolge diesen genau so, wie er da steht.
  • Führt dich der Algorithmus zum Ziel?
    
    
• Zusatzaufgabe: Der Algorithmus soll von jedem beliebigen Startpunkt 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.

Struktogramme kann man auch verwenden, um mathematische Algorithmen darzustellen. Ein einfaches Beispiel wäre:

• Es soll eine positive Zahl eingegeben werden (Eingabe)
• Der Algorithmen soll dann alle Zahlen von $1$ bis zu dieser Zahl ausgeben (Ausgabe).

Eine Eingabe notieren wir wie folgt: Diese bedeutet, dass eine Zahl eingegeben und in einer Variablen mit Name $x$ gespeichert werden soll. Natürlich kann man auch andere Variablennamen verwenden.

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

Das Beispiel von oben (Zahl eingeben, alle Zahlen bis zu dieser ausgeben) können wir dann wie folgt umsetzen:

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$). Achtung, in der Programmierung ist $=$ ein Zuweisungsoperator: Er weist den Wert rechts der Variablen auf der linken Seite zu.

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

• Spalte links: heisst Bedingung, notiere hier Bedingungen von Schleifen und Verzweigungen und Angabe, ob erfüllt oder nicht (True / False)
• Spalte 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 in Tabellen:

Summe: Zwei Zahlen sollen eingegeben und die Summe dieser Zahlen ausgegeben werden.

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.

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

Schreibe das Struktogramm für einen Algorithmus, der den Teilertest durchführt: zwei Zahlen a und b werden als Eingabe eingelesen. Die Ausgabe soll True sein, falls b ein Teiler von a ist (Beispiel: a = 9 und b = 3), sonst False.

Hinweis

Schreibe das Struktogramm für einen Algorithmus, das herausfindet, ob eine eingegebene Zahl eine Primzahl ist.

1. Definiere Primzahl.
2. Überlegt in Zweiergruppen, wie der Algorithmus funktionieren könnte. Könnte der Teilertest von C4 helfen?
3. Schreibe den Algorithmus als Struktogramm.

Du siehst jeweils abgebildet ein Struktogramm sowie zwei Situationen, in denen dieser Algorithmus angewendet wird. Zeichne den Weg ein, den der Käfer zurücklegt.

Beispiel:

Algorithmus:

Situation 1: Situation 2:

Algorithmus:

Situationen:

Algorithmus:

Situationen: