Algorithmen I: Einfache Algorithmen und Struktogramme LEGACY [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== - Algorithmen I: Einfache Algorithmen und Struktogramme LEGACY ======

Slides: {{ :gf_informatik:2022_algorithmen_i.pdf |}}

===== - 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 not(alufolie.inhalt.gettempdeg() < 20)
    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 *blinde* Partnerin Algorithmus, der sie von aktueller Position (am Pult sitzend) zum Wasserhahn des Zimmers bringt und dort trinken lässt.
   * Notiere den Algorithmus in Python-Pseudocode.\\ \\ 
   * **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.\\ \\


=== 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?300 |}}


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


==== Variablen, Eingaben und Ausgaben ====

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

{{ :gf_informatik:x_42.png?250 |}}
{{ :gf_informatik:meinnameistalbert.png?250 |}}

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

==== Zuweisungsoperator und Vergleichsoperatoren ====

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:
<WRAP group>
<WRAP 45% column>
{{ :gf_informatik:falls_z_42_a.png?300 |}}
</WRAP>
<WRAP 45% column>
{{ :gf_informatik:falls_z_42_b.png?300 |}}
</WRAP>
</WRAP>


==== Aufgaben C (Ein- & Ausgabe) ====

=== Aufgabe C1 (Taschenrechner I) ===

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.

=== Aufgabe C2 (Taschenrechner II) ===

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

=== Aufgabe C3 (Sirup, Bier oder Schnapps) ===

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.

=== Aufgabe C4 (Countdown) ===

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.

=== Aufgabe C5 (Quiz) ===

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.

==== Evaluation von Struktogrammen ====

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:

{{ :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$). 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:
{{ :gf_informatik:struktogramme_bsp_count_table.png?400 |}}
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!

==== Aufgaben D ====

=== Aufgabe D1 (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 D2 (Struktogramme aufschreiben) ===

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

== Teil i) ==

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

== Teil ii) ==

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

== Teil iii) ==

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


=== Aufgabe D3 (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


===== 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 (Taschenrechner I) ===

Einfache Lösung:
{{ :gf_informatik:taschenrechner_1op.png?250 |}}
Etwas schönere Lösung (verstehst du den Unterschied?):
{{ :gf_informatik:taschenrechner_1op_b.png?250 |}}

=== Aufgabe C2 (Taschenrechner II) ===

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

**Zusatzaufgabe:**

{{ :gf_informatik:taschenrechner_4op.png?650 |}}

=== Aufgabe C3 (Sirup, Bier oder Schnapps) ===

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

=== Aufgabe C4 (Countdown) ===

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

**Zusatzaufgabe:**
{{ :gf_informatik:struktogramm_countdown_b.png?400 |}}

++++
</nodisp>


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

==== Aufgaben D ====

=== Aufgabe D1 (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 D2 (Struktogramme aufschreiben) ===

== Teil i) ==

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

== Teil ii) ==

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

== Teil iii) ==

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

=== Aufgabe D3 (Zusatzaufgabe: Ratespiel) ===

Schicke deine Lösung der Lehrperson.

++++
</nodisp>