seminar07.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Seminar Problemorientierte Programmierung\n",
    "\n",
    "## Exkurs: Was mir an Python gefällt\n",
    "\n",
    "In dieser Rubrik, die immer am Anfang eines Kapitels steht, möchte ich Ihnen zeigen, wofür ich Python nutze und warum ich es mag. Sie werden vielleicht noch nicht verstehen, was ich genau mache, aber Sie sehen damit schon einmal die Möglichkeiten von Python und können später darauf zurückgreifen. Da dies auch ein Exkurs ist, können Sie diese Rubrik gerne auch erst einmal überspringen.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Und noch viele weitere schöne Beispiele: https://codegolf.stackexchange.com/questions/15860/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7 Iteration\n",
    "\n",
    "Dieses Kapitel ist eine Übersetzung des [Kapitels 8 \"Iteration\"](http://greenteapress.com/thinkpython2/html/thinkpython2008.html) von  Allen B. Downey. \n",
    "\n",
    "Dieses Kapitel handelt von der Iteration - der Möglichkeit, eine Folge von Anweisungen zu wiederholen. Wir haben eine Art der Iteration unter Verwendung der Rekursion schon im [Abschnitt 5.8](seminar05.ipynb#5.8-Rekursion) gesehen und eine andere Art, mit Hilfe der `for`-Schleife in [Abschnitt 4.2](seminar04.ipynb#4.2-Einfache-Wiederholung). In diesem Kapitel lernen wir eine weitere Variante unter Verwendung der `while`-Anweisung kennen. Aber vorher schauen wir uns noch einmal die Zuweisung eines Wertes an eine Variable an. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.1 Neuzuordnung\n",
    "\n",
    "Wie Sie vielleicht schon herausgefunden haben, ist es erlaubt, mehr als nur eine Zuweisung an die selbe Variable durchzuführen. Durch eine neue Zuweisung verweist eine existierende Variable auf einen neuen Wert (und nicht mehr auf den alten Wert)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 5\n",
    "print(x)\n",
    "x = 7\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wenn wir `x` beim ersten Mal ausgeben, ist sein Wert 5; beim zweiten Mal ist sein Wert 7.\n",
    "\n",
    "Die folgende Abbildung zeigt, wie diese **Neuzuordnung** (*reassignment*) in einem Zustandsdiagramm aussieht. \n",
    "\n",
    "![Neuzuordnung](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/zustandsdiagram_x57.svg)\n",
    "\n",
    "An dieser Stelle möchte ich auf eine häufige Ursache für Verwechslungen hinweisen. Da Python das Gleichheitszeichen (`=`) für die Zuweisung verwendet, ist es verlockend, eine Anweisung wie `a = b` wie eine mathematische Aussage der Gleichheit zu interpretieren, das heisst, die Behauptung, dass `a` und `b` gleich seien. Aber diese Interpretation ist falsch! \n",
    "\n",
    "Erstens ist Gleichheit eine symmetrische Beziehung und die Zuweisung ist es nicht. Beispielsweise gilt in der Mathematik: wenn $a=7$, dann ist auch $7=a$. Aber in Python ist die Anweisung `a = 7` erlaubt und `7 = a` ist es nicht. \n",
    "\n",
    "Außerdem ist in der Mathematik eine Aussage über die Gleichheit entweder wahr oder falsch und gilt durchgängig. Wenn $a = b$ jetzt gilt, dann wird $a$ stets gleich $b$ sein. Aber in Python kann eine Zuweisung zwei Variablen gleich machen, sie müssen aber nicht durchgängig gleich bleiben:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 5\n",
    "b = a  # a und b sind jetzt gleich\n",
    "a = 3  # a und b sind nicht mehr gleich\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die dritte Zeile ändert den Wert von `a` aber dadurch ändert sich nicht der Wert von `b`, so dass die beiden Variablen nicht mehr gleich sind.\n",
    "\n",
    "Variablen neue Werte zuzuweisen ist oft nützlich, aber Sie sollten vorsichtig damit umgehen. Wenn sich die Werte von Variablen häufig ändern, ist der Code schwerer zu lesen und zu debuggen. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.2 Variablen aktualisieren\n",
    "\n",
    "Eine übliche Art der Neuzuweisung ist eine **Aktualisierung** (*update*), bei der der neue Wert vom alten Wert abhängt:\n",
    "\n",
    "```python\n",
    "x = x + 1\n",
    "```\n",
    "\n",
    "Das bedeutet \"nimm' den aktuellen Wert von `x`, füge eins hinzu und aktualisiere dann `x` mit dem neuen Wert\".\n",
    "\n",
    "Wenn wir versuchen eine Variable zu aktualisieren, die nicht existiert, erhalten wir einen Fehler, denn Python evaluiert die rechte Seite der Zuweisung bevor es den Wert ver Variablen auf der linken Seite zuweist:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = y + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bevor wir eine Variable aktualisieren können, müssen wir sie **initialisieren**, typischerweise mittels einer Zuweisung:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = 0\n",
    "y = y + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Aktualisieren einer Variable mittels Addition der Zahl 1 wird **inkrementieren** genannt, das Subtrahieren einer 1 **dekrementieren**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.3 Die `while`-Anweisung\n",
    "\n",
    "Computer werden häufig dazu genutzt, um sich wiederholende Aufgaben zu automatisieren. Identische oder ähnliche Aufgaben zu wiederholen ohne dabei Fehler zu machen, ist etwas was Computer sehr gut können und Menschen eher schlecht. In einem Computerprogramm wird die Wiederholung auch als **Iteration** bezeichnet. \n",
    "\n",
    "Wir haben bereits zwei Funktionen gesehen, `countdown` und `print_t`, die mit Hilfe einer Rekursion eine Wiederholung durchführen. Da Wiederholung sehr häufig benötigt wird, bietet in Python Sprachkonstrukte die das vereinfachen.  Eines ist die `for`-Anweisung, die wir in [Abschnitt 4.2](seminar04.ipynb#4.2-Einfache-Wiederholung) kennengelernt haben. Darauf kommen wir später noch einmal zurück.\n",
    "\n",
    "Eine andere Möglichkeit ist die `while`-Anweisung. Dies ist eine Version von `countdown` die eine `while`-Schleife verwendet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countdown(n):\n",
    "    while n > 0:\n",
    "        print(n)\n",
    "        n = n - 1\n",
    "    print(\"Abheben!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wir können die `while`-Anweisung fast so lesen, als wäre es natürliche Sprache. Es bedeutet \"Solange `n` größer als 0 ist, zeige den Wert von `n` und dann dekrementiere `n`. Sobald 0 erreicht ist, gib das Wort `Abheben!` aus.\"\n",
    "\n",
    "Der Kontrollfluss der `while`-Schleife etwas formaler ausgedrückt sieht so aus:\n",
    "\n",
    "1. Bestimme ob die Bedingung wahr oder falsch ist.\n",
    "2. Wenn die Bedingung unwahr ist, beende die `while`-Schleife und fahre mit der Ausführung der nächsten Anweisung nach dem eingerückten Block von Anweisungen fort.\n",
    "3. Wenn die Bedingung wahr ist, führe die eingerückte Folge von Anweisungen im Schleifenrumpf aus und gehe dann zu Schritt 1.\n",
    "\n",
    "Diese Art von Kontrollfluss wird Schleife genannt, weil der dritte Schritt wieder zum ersten Schritt springt und damit den Kreis (Schleife) schließt. (Im Englischen Original passt es besser: *This type of flow is called a loop because the third step loops back around to the top*.)\n",
    "\n",
    "Der Schleifenrumpf sollte den Wert einer oder mehrerer Variablen ändern, so dass die Bedingung irgendwann einmal unwahr wird und die Schleife beendet wird. Ansonsten wiederholt sich die Schleife für immer, was **unendliche Schleife** (*infinite loop*) genannt wird.\n",
    "\n",
    "![Apple Campus: One Infinite Loop](https://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Apple_Campus_One_Infinite_Loop_Sign.jpg/640px-Apple_Campus_One_Infinite_Loop_Sign.jpg)\n",
    "\n",
    "[Joe Ravi](https://commons.wikimedia.org/wiki/File:Apple_Campus_One_Infinite_Loop_Sign.jpg)\n",
    "\n",
    "Im Fall von `countdown` können wir zeigen, dass die Schleife beendet wird: wenn `n` Null oder negativ ist, dann wird die Schleife niemals ausgeführt. Ansonsten wird `n` bei jedem Schleifendurchlauf verringert, so dass wir irgendwann 0 erreichen.\n",
    "\n",
    "Bei anderen Schleifen ist das nicht unbedingt so einfach zu sehen, zum Beispiel hier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sequence(n):\n",
    "    while n != 1:\n",
    "        print(n)\n",
    "        if n % 2 == 0:        # n ist gerade\n",
    "            n = n / 2\n",
    "        else:                 # n ist ungerade\n",
    "            n = n*3 + 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Schleifenbedingung ist hier `n != 1`, daher läuft die Schleife so lange, bis `n` gleich `1` ist, wodurch die Bedingung nicht mehr erfüllt ist.\n",
    "\n",
    "Bei jedem Schleifendurchlauf gibt das Programm den Wert von `n` aus und prüft dann, ob es eine gerade oder eine ungerade Zahl ist. Falls `n` eine gerade Zahl ist, wird `n` durch zwei geteilt. Falls `n` ungerade ist, wird der Wert von `n` ersetzt durch `n*3 + 1`. Übergeben wir der Funktion `sequence` beispielsweise 3 als Argument, dann sind die sich ergebenden Werte von `n` 3, 10, 5, 16, 8, 4, 2, 1. Probieren Sie es selbst für verschiedene Argumente aus:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Da `n` manchmal wächst und manchmal schrumpft gibt es keinen offensichtlichen Beweis, dass `n` jemals 1 erreichen wird oder das Programm beendet wird. Für einige bestimmte Werte von `n` können wir zeigen, dass das Programm beendet wird. Wenn beispielsweise der Startwert eine Potenz von 2 ist, dann ist `n` bei jedem Schleifendurchlauf eine gerade Zahl (und wird daher halbiert) bis die Schleife den Wert 1 erreicht. Das eben genannte Beispiel endet mit einer solchen Folge, die durch die Zahl 16 beginnt.\n",
    "\n",
    "Die schwierige Frage ist, ob wir beweisen können, dass dieses Programm für *jeden* positiven Wert von `n` beendet wird. Bis jetzt hat es noch niemand geschafft, dies zu beweisen *oder* das Gegenteil zu beweisen (siehe https://de.wikipedia.org/wiki/Collatz-Problem).\n",
    "\n",
    "Schreiben Sie als Übung die Funktion `print_n` aus  [Abschnitt 5.8](seminar05.ipynb#5.8-Rekursion) so um, dass eine Schleife statt der Rekursion verwendet wird:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_n(s, n):\n",
    "    # Implementieren Sie hier die Funktion mit Hilfe einer Schleife und ohne Rekursion\n",
    "    \n",
    "\n",
    "# Testaufruf\n",
    "print_n(\"hallo\", 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.4 `break`\n",
    "\n",
    "Manchmal wissen wir nicht, dass es Zeit wird eine Schleife zu beenden bevor wir den Schleifenrumpf nicht schon zur Hälfte ausgeführt haben. In einem solchen Fall können wir die `break`-Anweisung nutzen, um eine Schleife zu verlassen.\n",
    "\n",
    "Nehmen wir beispielsweise an, wir wollen eine Eingabe von der Nutzerin einlesen bis Sie `fertig` eingibt. Dann könnten wir folgendes schreiben:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while True:\n",
    "    line = input('> ')\n",
    "    if line == 'fertig':\n",
    "        break\n",
    "    print(line)\n",
    "\n",
    "print('Fertig!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Die Schleifenbedingung ist `True`, was stets wahr ist, daher läuft die Schleife so lange, bis die `break`-Anweisung erreicht wird.\n",
    "\n",
    "Bei jedem Durchlauf wird die Nutzerin aufgefordert, etwas einzugeben. Wenn Sie `fertig` eingibt, dann beendet die `break`-Anweisung die Schleife. Ansonsten gibt das Programm einfach nur aus, was die Nutzerin eingegeben hat und geht zurück zum Anfang der Schleife. Probieren Sie es selbst einmal aus.\n",
    "\n",
    "Diese Art eine `while`-Schleife zu nutzen ist üblich, denn wir können die Bedingung überall innerhalb der Schleife prüfen (nicht nur am Anfang) und wir können die Abbruchbedingung positiv formulieren (\"beende die Schleife, wenn folgendes passiert\") statt negativ (\"fahre fort bis folgendes passiert\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.5 Quadratwurzeln\n",
    "\n",
    "Schleifen werden häufig in Programmen genutzt, die numerische Werte berechnen, indem sie mit einem Näherungswert beginnen und diesen iterativ verbessern. \n",
    "\n",
    "Beispielsweise kann die Quadratwurzel einer Zahl mit dem [Newton-Verfahren](https://de.wikipedia.org/wiki/Newton-Verfahren) berechnet werden. Angenommen, wir wollen die Quadratwurzel von $a$ berechnen. Wenn wir mit einem (fast beliebigen) Näherungswert $x$ beginnen, können wir einen besseren Näherungswert $y$ mit der folgenden Formel berechnen:\n",
    "\n",
    "\\begin{equation}\n",
    "y = \\frac{x + a/x}{2}\n",
    "\\end{equation}\n",
    "\n",
    "Wenn beispielsweise $a$ gleich 4 ist und $x$ gleich 3:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 4\n",
    "x = 3\n",
    "y = (x + a/x) / 2\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Ergebnis ist näher an der richtigen Antwort ($\\sqrt{4} = 2). Wenn wir den Vorgang mit dem neuen Näherungswert wiederholen, kommen wir noch näher heran:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = y\n",
    "y = (x + a/x) / 2\n",
    "y "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nach ein paar mehr Aktualisierungen ist die Näherung fast exakt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = y\n",
    "y = (x + a/x) / 2\n",
    "y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = y\n",
    "y = (x + a/x) / 2\n",
    "y "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Im Allgemeinen wissen wir anfangs nicht, wie viele Schritte nötig sind, um die richtige Antwort zu erhalten, aber wir wissen es, wenn sich der Näherungswert nicht mehr verändert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = y\n",
    "y = (x + a/x) / 2\n",
    "y "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = y\n",
    "y = (x + a/x) / 2\n",
    "y "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sobald `x == y` gilt, können wir abbrechen. Im Folgenden eine Schleife, die mit einem Näherungswert `x` beginnt und diesen verbessert, bis er sich nicht mehr ändert:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 4\n",
    "x = 3\n",
    "\n",
    "while True:\n",
    "    print(x)\n",
    "    y = (x + a/x) / 2\n",
    "    if y == x:\n",
    "        break\n",
    "    x = y\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Für die meisten Werte von `a` funktioniert das sehr gut aber im Allgemeinen ist es gefährlich, die Gleichheit von Gleitkommazahlen zu testen. Gleitkommazahlen sind nur ungefähr exakt: die meisten rationalen Zahlen wie z.B. 1/3 und irrationale Zahlen wie z.B. $\\sqrt{2}$ können nicht exakt als Gleitkommazahl repräsentiert werden. \n",
    "\n",
    "Statt zu prüfen ob `x` und `y` exakt gleich sind ist es sicherer die eingebaute Funktion `abs` zu nutzen, um den Betrag des Unterschieds zwischen den beiden Zahlen zu berechnen:\n",
    "\n",
    "```python\n",
    "if abs(y-x) < epsilon:\n",
    "    break\n",
    "```\n",
    "\n",
    "Wobei wir für `epsilon` einen sehr kleinen Wert wie z.B. `0.0000001` wählen sollten, der bestimmt, welche Näherung gut genug für uns ist. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 7.8 Glossar\n",
    "\n",
    "Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 7 gelernt haben:\n",
    "\n",
    "\n",
    "\n",
    "Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Speichern](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/floppy.png) Speichern Sie dieses Notebook, so dass Ihre Änderungen nicht verlorengehen (nicht auf einem Pool-Rechner). Klicken Sie dazu oben links auf das Disketten-Icon und nutzen Sie beispielsweise einen USB-Stick, E-Mail, Google Drive, Dropbox oder Ihre [HU-Box](https://box.hu-berlin.de/).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Smiley](https://upload.wikimedia.org/wikipedia/commons/7/70/Face-devil-grin.svg)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 6. Kapitel geschafft. Weiter geht es in [7: Iteration](seminar07.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}