====== - Algorithmen I ======

===== - Einführung Algorithmen =====

==== Definition ====

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

==== Beispiel ====

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

{{:gf_informatik:pasted:20220914-135450.png?200}}


=== 1) Menschliche Sprache ===

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.

=== 2) Pseudocode ===

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.

<code>
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) 
</code>

=== 3) Flussdiagramm ===

{{:gf_informatik:pasted:20220914-135346.png}}


==== Aufgaben A ====

=== Aufgabe A1 (Wasserhahn) ===

   * 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.\\ \\


=== Aufgabe A2 (Subtraction Game) ===

   * 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 

{{ :gf_informatik:subtraction_game.png?480 |}}

===== - Struktogramme =====

==== Grundlagen ====

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
{{ :gf_informatik: struktogramme_anweisungen.png?250 |}}
   1. **Solange-Schleife:** Wiederholt die darin enthaltenen Anweisungen *solange*, wie die Bedingung erfüllt ist.
{{ :gf_informatik: struktogramme_solange.png?250 |}}
   1. **Verzweigungen:** Je nach dem, ob die Bedingung erfüllt ist oder nicht, werden andere Befehle ausgeführt.
{{ :gf_informatik:struktogramme_verzweigungen.png?250 |}}


==== Aufgaben B ====

=== Aufgabe B1 (Wasserhahn revisited) ===

   * 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.

<nodisp 1>
++++Tipps|
Mögliche Anweisungen:
{{ :gf_informatik:struktogramme_wasserhahn_anweisungen.png?250 |}}
Mögliche Schleifen:
{{ :gf_informatik:struktogramme_wasserhahn_solange.png?250 |}}
Mögliche Verzweigungen:
{{ :gf_informatik:struktogramme_wasserhahn_verzweigung.png?250 |}}
++++
</nodisp>

=== Aufgabe B2 (Karamell-Bonbons revisited) ===

Wandle das Flussdiagramm mit dem Algorithmus zur Herstellung von [[gf_informatik:algorithmen_i#flussdiagramm|Karamell-Bonbons]] in ein Struktogramm um.

=== Aufgabe B3 (Subtraction Game revisited) ===

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.
   1. Diesmal soll die Spieler:in beginnen. Der Computer soll gewinnen, sobald die Spieler:in einen Fehler macht.
   1. Erweitere dein Struktogramm aus 2., so dass beide Fälle (Computer beginnt (nicht)) abgedeckt sind.


==== Eingabe und Ausgabe in Struktogrammen ====

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:
{{ :gf_informatik: struktogramme_input.png?250 |}}
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:
{{ :gf_informatik: struktogramme_output.png?250 |}}

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

{{ :gf_informatik:struktogramme_bsp_count.png?250 |}}

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.

==== Evaluation von Struktogrammen ====

Um eine Algorithmus in Form eines Struktogramms genau zu verstehen, **evaluieren** wir diesen *Schritt-für-Schritt* in einer Tabelle:
{{ :gf_informatik:struktogramme_bsp_count_table.png?400 |}}
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!

==== Aufgaben C ====

=== Aufgabe C1 (Struktogramme evaluieren & verstehen) ===

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

== Teil i) ==

{{ :gf_informatik:struktogramme_aufgabe_a.png?300 |}}

== Teil ii) ==

{{ :gf_informatik:struktogramme_aufgabe_b.png?300 |}}

=== Aufgabe C2 (Struktogramme aufschreiben) ===

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

== Teil i) ==

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

== Teil ii) ==

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

== Teil iii) ==

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


=== Aufgabe C3 (Zusatzaufgabe: Ratespiel) ===

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

=== Aufgabe C4 (Zusatzaufgabe: Teilertest) ===

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|
Bei [[#aufgabe_c1_struktogramme_evaluieren_verstehen|Aufgabe C1]] schauen...
++++

<nodisp 1>
++++Lösung|
{{:gf_informatik:pasted:20231004-111322.png?nolink&400}}
++++
</nodisp>
=== Aufgabe C5 (Zusatzaufgabe: Primzahltest) ===

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.

<nodisp 1>
++++Lösung|
{{:gf_informatik:pasted:20231003-092642.png?nolink&400}}
++++
</nodisp>

==== Käfer-Struktogramme ====

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:
{{:gf_informatik:pasted:20221003-153211.png?480}}

Situation 1:
{{:gf_informatik:pasted:20221003-153313.png}}
{{:gf_informatik:pasted:20221003-153318.png}}
Situation 2:
{{:gf_informatik:pasted:20221003-153307.png}}
{{:gf_informatik:pasted:20221003-153244.png}}

=== Aufgabe D1: ===
Algorithmus:
{{:gf_informatik:pasted:20221003-153527.png?480}}

Situationen:
{{:gf_informatik:pasted:20221003-153543.png}}
{{:gf_informatik:pasted:20221003-153548.png}}

=== Aufgabe D2: ===
Algorithmus:
{{:gf_informatik:pasted:20221003-153657.png?240}}

Situationen:
{{:gf_informatik:pasted:20221003-153705.png}}
{{:gf_informatik:pasted:20221003-153709.png}}
===== Lösungen Aufgaben =====

<nodisp 1>
++++Lösungen Aufgaben A|

==== Aufgaben A ====

=== Aufgabe A1 (Wasserhahn) ===

=== Aufgabe A2 (Subtraction Game) ===

Gewinnstrategie- Ziel:
   * Gegner soll landen auf $4,8,12,16,20$ (Vielfaches von $4$)
   * Wenn kann beginnen: nimm nur $1$, damit Gegner auf $20$ landet

{{ :gf_informatik:subtraction_game_strategie.png?500 |}}

++++
</nodisp>

<nodisp 1>
++++Lösungen Aufgaben B|

==== Aufgaben B ====

=== Aufgabe B1 (Wasserhahn revisited) ===

{{ :gf_informatik:struktogramme_wasserhahn_loesung.png?300 |}}

=== Aufgabe B2 (Karamell-Bonbons revisited) ===

{{ :gf_informatik:struktogramm_karamell_loesung.png?300 |}}

=== Aufgabe B3 (Subtraction Game revisited) ===

== Variante 1: Computer beginnt (und gewinnt) ==

Lösung 1:
{{ :gf_informatik:struktogramm_sub_game_I_a.png?300 |}}
Lösung 2 (eleganter):
{{ :gf_informatik:struktogramm_sub_game_I_b.png?300 |}}

== Variante 2: Spieler:in beginnt ==

Lösung 1:
{{ :gf_informatik:struktogramm_sub_game_II_a.png?600 |}}
Lösung 2 (eleganter):
{{ :gf_informatik:struktogramm_sub_game_II_b.png?600 |}}
Lösung 3 (am elegantesten):
{{ :gf_informatik:struktogramm_sub_game_II_c.png?600 |}}

== Variante 3: Computer oder Spieler:in beginnt ==

Ist einfache Erweiterung von Struktogramm aus Variante 2:
{{ :gf_informatik:struktogramm_sub_game_III_c.png?600 |}}

++++
</nodisp>

<nodisp 1>
++++Lösungen Aufgaben C|

==== Aufgaben C ====

=== Aufgabe C1 (Struktogramme evaluieren & verstehen) ===

== Teil i) ==

Evaluierung:
   * a=14 und b=4 liefern 3 und 2
   * a=38 und b=5 liefern 7 und 3

{{ :gf_informatik:struktogramme_aufgabe_a_table.png?400 |}}

Beschreibung: Algorithmus bestimmt **Quotient und Rest der Ganzzahldivision** a durch b und gibt diese aus.

== Teil ii) ==

Evaluierung:
   * n=3 liefert die Ausgabe 6
   * n=7 liefert die Ausgabe 28

{{ :gf_informatik:struktogramme_aufgabe_b_table.png?400 |}}

Beschreibung: Algorithmus bestimmt Summe aller natürlicher Zahlen von 1 bis und mit n. 

=== Aufgabe C2 (Struktogramme aufschreiben) ===

== Teil i) ==

{{ :gf_informatik:struktogramme_aufgabe_c_lsg.png?250 |}}

== Teil ii) ==

{{ :gf_informatik:struktogramme_aufgabe_d_lsg.png?250 |}}

== Teil iii) ==

{{ :gf_informatik:struktogramme_aufgabe_e_lsg.png?600 |}}

++++
</nodisp>

<nodisp 1>
++++Lösungen Aufgaben D|
{{:gf_informatik:algorithmen_i:pasted:20241020-185003.png?nolink&400}}

++++
</nodisp>