seminar10.ipynb

   "source": [
    "letters = ['a', 'b', 'c']\n",
    "delete_head(letters)\n",
    "letters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Parameter `t` und die Variable `letters` sind Aliase für das selbe Objekt. Das Stapeldiagramm beim Aufruf von `delete_head` sieht folgendermaßen aus:\n",
    "\n",
    "![Stapeldiagramm delete_head](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/stapeldiagramm_delete_head.svg)\n",
    "\n",
    "Die zwei Blöcke `__main__` und `delete_head` teilen sich die Liste, daher zeigen zwei Pfeile auf sie.\n",
    "\n",
    "Es ist wichtig, dass wir zwischen Operationen unterscheiden, die Listen *verändern* und jenen, die neue Listen *erzeugen*. Beispielsweise verändert die Methode `append` eine Liste, aber der Operator `+` erzeugt eine neue Liste.\n",
    "\n",
    "Nachfolgend ein Beispiel zu `append`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t1 = [1, 2]\n",
    "t2 = t1.append(3)\n",
    "print(t1)\n",
    "print(t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Rückgabewert von `append` ist `None`.\n",
    "\n",
    "Nachfolgend ein Beispiel für den Operator `+`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t3 = t1 + [4]\n",
    "print(t1)\n",
    "print(t3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Das Ergebnis des Operators ist eine neue Liste; die Ursprungsliste ist unverändert.\n",
    "\n",
    "Dieser Unterschied ist wichtig, wenn wir Funktionen schreiben die Listen verändern. Beispielsweise entfernt die folgende Funktion *nicht* das erste Element einer Liste: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bad_delete_head(t):\n",
    "    t = t[1:]              # FALSCH!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Der Segmentoperator erzeugt eine neue Liste und die Zuweisung sorgt dafür, dass `t` auf die neue Liste verweist, aber das verändert nicht die Ursprungsliste:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t4 = [1, 2, 3]\n",
    "bad_delete_head(t4)\n",
    "t4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Am Anfang von `bad_delete_head` verweisen `t` und `t4` auf die gleiche Liste. Am Ende verweist `t` auf eine neue Liste, aber `t4` verweist immer noch auf die ursprüngliche, unveränderte Liste.\n",
    "\n",
    "Eine Alternative ist, eine Funktion zu schreiben, die eine neue Liste erzeugt und zurückgibt. Beispielsweise gibt `tail` alle bis auf das erste Element einer Liste zurück:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tail(t):\n",
    "    return t[1:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diese Funktion verändert die Ursprungsliste nicht! Folgendermaßen kann die Funktion verwendet werden:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "letters = ['a', 'b', 'c']\n",
    "rest = tail(letters)\n",
    "rest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.13 Debugging\n",
    "\n",
    "Unvorsichtige Verwendung von Listen (und anderen veränderbaren Objekten) kann langwieriges Debuggen verursachen. Einige übliche Fehler und Wege, sie zu vermeiden:\n",
    "\n",
    "#### 1. Die meisten Listenmethoden verändern das Argument und geben `None` zurück.\n",
    "\n",
    "Das ist das Gegenteil zum Verhalten der Methoden für Zeichenketten, die eine neue Zeichenkette zurückgeben und die ursprüngliche Zeichenkette unverändert lassen.\n",
    "\n",
    "Wenn Sie gewohnt sind, Code für Zeichenketten so zu schreiben:\n",
    "   \n",
    "```python\n",
    "word = word.strip()\n",
    "```\n",
    "   \n",
    "Dann ist es verlpckend, folgenden Code für Listen zu schreiben:\n",
    "   \n",
    "```python\n",
    "t = t.sort()      # FALSCH!\n",
    "```\n",
    "   \n",
    "Weil `sort` keinen Wert (also `None`) zurückliefert, wird die nächste Operation, die wir mit `t` durchführen würden wahrscheinlich fehlschlagen. \n",
    "   \n",
    "Bevor wir Methoden und Operatoren für Listen verwenden, sollten wir aufmerksam die Dokumentation lesen und mit etwas Beispielcode testen.\n",
    "   \n",
    "#### 2. Sich für ein Idiom entscheiden und dann dabei bleiben.\n",
    "\n",
    "Ein Teil des Problems mit Listen ist, dass es zu viele Möglichkeiten gibt, mit Ihnen umzugehen. Beispielsweise können wir zum Entfernen eines Elements `pop`, `remove`, `del` oder sogar den Segmentoperator verwenden. \n",
    "   \n",
    "Um ein Element hinzuzufügen, können wir die Methode `append` oder den Operator `+` verwenden. Angenommen, `t` ist eine Liste und `x` ist ein Listenelement, dann sind die folgenden Varianten korrekt:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = ['a', 'b', 'c']\n",
    "x = 'n'\n",
    "\n",
    "t.append(x)\n",
    "print(t)\n",
    "\n",
    "t = t + [x]\n",
    "print(t)\n",
    "\n",
    "t += [x]\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "und die folgenden sind falsch:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t.append([x])          # FALSCH!\n",
    "print(t)\n",
    "\n",
    "t = t.append(x)        # FALSCH!\n",
    "print(t)\n",
    "\n",
    "t + [x]                # FALSHC!\n",
    "print(t)\n",
    "\n",
    "t = t + x              # FLASCH!\n",
    "print(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probieren Sie diese Beispiele (einzeln!) aus und stellen Sie sicher, dass Sie wirklich verstanden haben, was sie tun. Beachten Sie, dass nur das letzte Beispiel einen Laufzeitfehler (*runtime error*) verursacht. Die anderen drei Varianten sind erlaubt, aber sie tun das Falsche.\n",
    "   \n",
    "#### 3. Kopien erzeugen, um Aliasing zu vermeiden.\n",
    "\n",
    "Wenn Sie eine Methode wie z.B. `sort` verwenden wollen, die das Argument verändert, aber Sie benötigen auch die Ursprungsliste, dann können Sie eine Kopie erzeugen:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [3, 1, 2]\n",
    "t2 = t[:]\n",
    "t2.sort()\n",
    "print(t)\n",
    "print(t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In diesem Beispiel könnten Sie auch die eingebaute Funktion `sorted` verwenden, die eine neue, sortierte Liste zurückgibt, ohne die Ursprungsliste zu verändern: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "t2 = sorted(t)\n",
    "print(t)\n",
    "print(t2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.14 Glossar\n",
    "\n",
    "Legen wir uns eine Liste mit den wichtigsten Begriffen an, die wir im Kapitel 10 gelernt haben:\n",
    "\n",
    "- Liste: eine Folge von Werten\n",
    "- Element:\n",
    "- verschachtelte Liste: \n",
    "- Akkumulator:\n",
    "- erweiterte Zuweisung\n",
    "- Reducer:\n",
    "- Mapper:\n",
    "- Filter:\n",
    "- Objekt:\n",
    "- äquivalent:\n",
    "- identisch:\n",
    "- Referenz:\n",
    "- Aliasing:\n",
    "- Trennzeichen:\n",
    "\n",
    "Ergänzen Sie die Liste in eigenen Worten. Das ist eine gute Erinnerungs- und Übungsmöglichkeit."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 10.15 Übung\n",
    "\n",
    "Sie finden die Lösungen für die Aufgaben hier: http://thinkpython2.com/code/list_exercises.py\n",
    "\n",
    "#### Aufgabe 1\n",
    "Schreiben Sie eine Funktion `nested_sum`, die eine Liste von Listen von ganzen Zahlen erwartet und die Werte der einzelnen Elemente aufaddiert und das Ergebnis zurückgibt. Beispielsweise sollte die Funktion für die Liste `t = [[1, 2], [3], [4, 5, 6]]` den Wert `21` zurückgeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def nested_sum(t):\n",
    "    # Implementieren Sie hier die Funktion\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 2\n",
    "Schreiben Sie eine Funktion `cumsum`, die eine Liste von Zahlen erwartet und die kumulative Summe zurückgibt, d.h. eine neue Liste, in der das *i*te Element die Summe der ersten *i + 1* Elemente der Original-Liste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1, 2, 3]` die Liste `[1, 3, 6]` zurückgeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cumsum(t):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testen Sie die Funktion mit verschiedenen Listen als Eingabe.\n",
    "\n",
    "Welche Liste müssten Sie der Funktion `cumsum` übergeben, um als Ergebnis die Liste `[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]` der ersten zehn Fibonacci-Zahlen zu erhalten?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 3\n",
    "Schreiben Sie eine Funktion `middle`, die eine Liste als Argument erwartet und eine neue Liste zurückgibt, die alle Elemente bis auf das erste und letzte der Ausgangsliste enthält. Beispielsweise sollte die Funktion für die Liste `t = [1,2,3,4]` die Liste `[2,3]` zurückgeben:\n",
    "\n",
    "```python\n",
    "t = [1,2,3,4]\n",
    "middle(t)\n",
    "```\n",
    "sollte `[2,3]` ergeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def middle(t):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 4\n",
    "Schreiben Sie eine Funktion `chop`, die eine Liste als Argument erwartet, das erste und letzte Element entfernt und `None` zurückgibt. Beispielsweise sollte\n",
    "\n",
    "```python\n",
    "t = [1,2,3,4]\n",
    "chop(t)\n",
    "t\n",
    "```\n",
    "`[2,3]` ergeben."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def chop(t):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 5\n",
    "Schreiben Sie eine Funktion `is_sorted`, die eine Liste als Argument erwartet und `True` zurückgibt, falls die Liste in aufsteigender Reihenfolge sortiert ist und ansonsten `False`. Also zum Beispiel:\n",
    "\n",
    "```python\n",
    ">>> is_sorted([1, 2, 2])\n",
    "True\n",
    ">>> is_sorted(['b', 'a'])\n",
    "False\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_sorted(t):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 6\n",
    "Zwei Wörter bilden ein *Anagramm*, wenn wir die Buchstaben des einen Wortes so umordnen können, dass sich das andere Wort ergibt. (Beispielsweise bilden *LAGER* und *REGAL* ein Anagramm.) Schreiben Sie eine Funktion `is_anagram`, die zwei Zeichenketten erwartet und `True` zurückgibt, falls sie ein Anagramm bilden (sonst `False`). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_anagram(v, w):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zusatzaufgabe: Suchen Sie in der Wortliste aus dem [8. Kapitel](seminar08.ipynb) nach Anagrammen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 7\n",
    "Schreiben Sie eine Funktion `has_duplicates`, die eine Liste als Argument erwartet und `True` zurückgibt, falls ein Element der Liste mehr als einmal in der Liste enthalten ist. Die Funktion soll die Ursprungsliste nicht verändern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_duplicates(t):\n",
    "    # Implementieren Sie hier die Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 8\n",
    "In dieser Aufgabe geht es um das sogenannte \"Geburtstags-Paradoxon\" über das Sie mehr in [Wikipedia](http://en.wikipedia.org/wiki/Birthday_paradox) lesen können.\n",
    "\n",
    "Wenn 23 Studierende in Ihrem Kurs sind, wie hoch ist dann die Wahrscheinlichkeit, dass zwei davon am gleichen Tag Geburtstag haben? Sie können diese Wahrscheinlichkeit schätzen, indem Sie zufällig 23 Geburtstage auswürfeln und prüfen, ob mindestens zwei davon identisch sind. (*Hinweis: Sie können zufällige Geburtstage mit Hilfe der Funktion `randint` aus dem [Modul `random`](https://docs.python.org/3.5/library/random) erzeugen.)\n",
    "\n",
    "Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/birthday.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n",
    "# Implementieren Sie hier Ihr Programm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 9\n",
    "Schreiben Sie eine Funktion, die die Datei \"top10000de.txt\" einliest (siehe [Abschnitt 9.1](seminar09.ipynb#9.1-Wortlisten-einlesen)) und daraus eine Liste erzeugt mit den Wörtern als Elementen erzeugt. Implementieren Sie zwei Versionen dieser Funktion: eine, die die Methode `append` verwendet und eine, die den Operator `+` mittels `t = t + [t]` verwendet. Welche der beiden Versionen hat eine größere Laufzeit? Warum?\n",
    "\n",
    "Eine Lösung für diese Aufgabe finden Sie hier: http://thinkpython2.com/code/wordlist.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier die beiden Varianten Ihrer Funktion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 10\n",
    "\n",
    "Um zu überprüfen, ob ein Wort in einer Wortliste ist, können wir den Operator `in` verwenden, aber das wäre recht langsam, denn der Operator muss dazu die Liste linear durchlaufen.\n",
    "\n",
    "Wenn wir mit einer sortierten Liste arbeiten, können wir den Vorgang beschleunigen, indem wir *binäre Suche* (auch bekannt als *bisection search*) verwenden. Das entspricht dem Verfahren, welches wir verwenden, wenn wir ein Wort in einem Wörterbuch nachschlagen: wir beginnen in der Mitte und schauen, ob das gesuchte Wort vor dem Wort in der Mitte der Liste stehen müsste. Falls dem so ist, durchsuchen wir die erste Hälfte der Liste auf die gleiche Art, ansonsten durchsuchen wir die zweite Hälfte.\n",
    "\n",
    "In jedem Fall halbieren wir damit den Suchraum. Im Fall unserer Wortliste mit 10000 Wörtern benötigen wir höchstens 13 Schritte, um das gesuchte Wort zu finden oder festzustellen, dass die Liste das Wort nicht enthält. \n",
    "\n",
    "Schreiben Sie eine Funktion `binary_search` die eine sortierte Liste sowie ein Wort als Argumente erwartet und `True` zurückgibt, falls das Wort in der Liste enthalten ist, ansonsten `False`.\n",
    "\n",
    "Alternativ können Sie auch die [Dokumentation für das Modul `bisect`](https://docs.python.org/3.5/library/bisect) lesen und dieses verwenden. Eine Lösung finden Sie hier: http://thinkpython2.com/code/inlist.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(t, w):\n",
    "    # Implementieren Sie hier die Funktion\n",
    "\n",
    "# Hinweis: Sie müssen die Liste sortieren, damit \n",
    "# binary_search funktioniert. Dies geht mittels\n",
    "# der Funktion sort - siehe help(list.sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 11\n",
    "Zwei Wörter sind ein \"umgekehrtes Paar\" (*reverse pair*), wenn jedes Wort rückwärts gelesen das jeweils andere ergibt (wie bei \"LAGER\" und \"REGAL\"). Schreiben Sie ein Programm, welches alle umgekehrten Paare in unserer Wortliste findet. (Ignorieren Sie dabei wieder Groß- und Kleinschreibung.) Eine Lösung finden Sie hier: http://thinkpython2.com/code/reverse_pair.py\n",
    "\n",
    "(*Hinweis: Sie werden einige doppelte Paare finden, was daran liegt, dass in top10000.txt Groß- und Kleinschreibung unterschieden wird.*)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier Ihr Programm\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Aufgabe 12\n",
    "Zwei Wörter \"greifen ineinander\" (*interlock*), wenn sich durch abwechselndes Hinzufügen eines Buchstabens aus beiden Wörtern ein neues Wort ergibt. Beispielsweise greifen \"Mai\" und \"im\" ineinander und bilden das Wort \"Miami\". \n",
    "\n",
    "![Mai + im = Miami](https://amor.cms.hu-berlin.de/~jaeschkr/teaching/spp/miami.svg)\n",
    "\n",
    "1. Schreiben Sie ein Program, welches alle Wortpaare findet, die ineinandergreifen. Hinweis: durchlaufen Sie nicht alle möglichen Wortpaare!\n",
    "2. Gibt es Wörter, die dreifach ineinandergreifen; das heißt, jeder dritte Buchstabe ergibt ein Wort, beginnend mit dem ersten, zweiten oder dritten Buchstaben? (*Leider ist unsere Wortliste mit 10000 Wörtern recht kurz ... als einziges einigermaßen sinnvolles Beispiel ergibt sich \"bekommt\", welches die \"Wörter\" \"Bot\", \"EM\", und \"km\" enthält.*)\n",
    "\n",
    "(Diese Aufgabe wurde durch ein Beispiel auf http://puzzlers.org/ inspiriert, eine Lösung finden Sie hier: http://thinkpython2.com/code/interlock.py)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Implementieren Sie hier das Programm"
   ]
  },
  {
   "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). \n",
    "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/thumb/7/79/Face-smile.svg/48px-Face-smile.svg.png)\n",
    "\n",
    "Herzlichen Glückwunsch! Sie haben das 10. Kapitel geschafft. Weiter geht es in [11: assoziative Felder](seminar11.ipynb)."
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}