{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Vorbereitungen zur Evaluation von Such- und Sortieralgorithmen (Lösungen)\n", "\n", "Um Algorithmen miteinander vergleichen zu können, werden sie in der Regel auf verschiedene Ausgangslagen angewandt:\n", "\n", "* Eine **bestmögliche** Ausgangslage \n", " *Suchen:* Suche nach dem Wert des ersten Elements, das der Algorithmus mit dem gesuchten Wert vergleicht. \n", " *Sortieren:* sortierte Liste\n", "* eine **schlechtmöglichste** Ausgangslage \n", " *Suchen:* Suche nach dem Wert des letzten Elements, das der Algorithmus mit dem gesuchten Wert vergleicht. \n", " *Sortieren:* umgekehrt sortierte Liste\n", "* eine **zufällige Liste** für den \"Normalfall\".\n", "\n", "## Listen erstellen\n", "\n", "Es ist viel angenehmer, Listen automatisch zu erstellen, als sie manuell zu erfassen. Hier erfahren Sie, wie Sie Listen zielgerichtet erstellen können.\n", "\n", "### Sortierte und umgekehrt sortierte Listen\n", "\n", "Sie wissen bereits, wie Sie eine Liste mit Einheitswerten initialisieren können. \n", "\n", "Zur Erinnerung, eine Liste, die 10 Nullen enthält, wird erstellt, indem für jedes Element eines Bereichs ein Einheitswert in die Liste geschrieben wird.\n", "\n", "Das Beispiel" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "nullen = [0 for x in range(10)]\n", "print(nullen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "erstellt eine Liste mit Namen `nullen`, die 10 Nullen enthält. \n", "\n", "`for x in range 10` bedeutet, dass $x$ den Bereich \\[0,10) durchläuft, also alle Werte von 0 bis und ohne 10 annimmt.\n", "\n", "Anstelle eines Einheitswerts kann aber auch eine Funktion auf jedes Element $x$ des Bereichs angewandt werden, beispielsweise die Quadratfunktion $x^2$:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "quadratzahlen = [x**2 for x in range(10)]\n", "print(\"quadratzahlen:\", quadratzahlen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Sie können nun selbst Listen erstellen, beispielsweise eine Liste, die sämtliche Ganzzahlen von 0 bis 99 enthält.\n", "\n", "**Aufgabe 1 – Auf- und absteigende Liste erstellen**\n", "\n", "Erstellen Sie eine Liste `aufsteigend` und eine Liste `absteigend`, welche die Zahlen von 0 bis 9 in aufsteigend bzw. absteigend (umgekehrt) sortierter Reihenfolge enthalten." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "aufsteigend = [x for x in range(10)]\n", "print(\"aufsteigend: \", aufsteigend)\n", "\n", "absteigend = [9-x for x in range(10)]\n", "print(\"absteigend: \", absteigend)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Zufällig sortierte Listen\n", "\n", "Die soeben erstellten Listen sind geordnet. Vor allem wenn Sie Sortieralgorithmen testen wollen, werden Sie nicht nur sortierte Listen erstellen wollen.\n", "\n", "Sie können auch eine Liste erstellen, die «Zufallszahlen» enthalten oder Ihre bereits erstellen Listen mischen, damit diese dieselben Werte enthält, aber in «zufälliger» Reihenfolge.\n", "\n", "Dazu bietet sich das Modul `random` an. Sie können es folgendermassen importieren:\n", "```Python\n", "import random\n", "```\n", "\n", "#### Nützliche Funktionen des Moduls random\n", "\n", "Das Modul `random` ([Dokumentation](https://docs.python.org/3/library/random.html)) liefert Ihnen unter anderem die folgenden Funktionen:\n", "* `random()` erstellt einen «zufälligen» *Float* im Bereich `[0.0, 1.0)`, d.h. von 0.0 bis und ohne 1.0\n", "* `randint(a, b)` erstellt einen «zufälligen» *Integer* im Bereich `[a, b]`, d.h. von a bis und *mit* b\n", "* `shuffle(liste)` mischt die Elemente der Liste `liste`\n", "\n", "Hier werden Sie mehr zur Funktion `random.shuffle()` erfahren, die sich gerade anbietet, weil Sie zum Vergleichen Ihrer Algorithmen Listen verwenden wollen, die dieselben Werte in unterschiedlicher Reihenfolge enthalten. Unten in diesem Notebook erfahren Sie mehr über «Zufallszahlen».\n", "\n", "##### random.shuffle()\n", "\n", "Mit der `random.shuffle()`-Funktion können Sie die Werte in einer Liste \"mischen\". \n", "\n", "**Aufgabe 2 – Geordnete Liste mischen**\n", "\n", "Erstellen Sie eine Liste, die zehn geordnete Werte enthält. Geben Sie die erstellte Liste aus, mischen Sie sie und geben Sie die gemischte Liste ebenfalls aus.\n", "\n", "
\n", " \n", " Hinweise\n", " \n", "\n", "- Fehlermeldung: Bei einem NameError: name 'random' is not defined:\n", "Denken Sie daran, das Modul `random` zu importieren: \n", "```Python\n", "import random\n", "```\n", "\n", "- Für die Ausgabe können Sie die Funktion `print()` verwenden.\n", " \n", "- Wenn Sie, um die Liste mit Nullen zu initialisieren, für jedes Element im Bereich von 0 bis und ohne 10 den Wert 0 einsetzen können: \n", "```Python\n", "meine_liste = [0 for x in range(10)]\n", "```\n", "was müssen Sie denn einsetzen, um Werte von 0 bis und ohne 10 zu erhalten?\n", " \n", "
" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "import random\n", "\n", "zufaellig = [x for x in range(10)]\n", "print(\"liste geordnet:\", zufaellig)\n", "random.shuffle(zufaellig)\n", "print(\"liste gemischt:\", zufaellig)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Laufzeitanalyse: Anzahl Vergleiche zählen\n", "\n", "Um zu analysieren, wie effizient Ihr Algorithmus ist, wollen Sie einen Anhaltspunkt haben, wie viele Schritte gemacht werden. Da beim Sortieren immer wieder Elemente verglichen werden, bietet es sich an, Vergleiche zu zählen.\n", "\n", "Nach der Implementation können Sie Ihren Algorithmus auf Listen verschiedener Grösse anwenden, z.B. 10, 100, 1000 (bei 10000 Elementen werden einige bereits sehr langsam und Sie müssen lange auf das Ergebnis warten).\n", "\n", "Das Ziel dieser Übung besteht darin, eine Tabelle zu erstellen, in der Sie sehen, wie sich Ihr Algorithmus in den verschiedenen Fällen verhält. \n", "\n", "| Liste | sortiert | zufällig | umgekehrt sortiert |\n", "| :----------------- | :----------------------- | :----------------------- | :----------------------- |\n", "| Ohne Optimierung | ________________________ | ________________________ | ________________________ |\n", "| Erste Optimierung | ________________________ | ________________________ | ________________________ |\n", "| Zweite Optimierung | ________________________ | ________________________ | ________________________ |\n", "...\n", "\n", "### Anzahl Vergleiche formal erfassen\n", "\n", "Versuchen Sie auch, sich zu überlegen, wie Sie die Anzahl Vergleiche formal beschrieben können.\n", "\n", "Wenn Sie die dabei gefundenen Funktionen auf eine grosse Anzahl Elemente anwenden, sehen Sie, was Sie mit Ihren Optimierungen gewonnen haben." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Zeitmessungen mit dem Modul `time`\n", "\n", "Wenn Sie sich auch für die Laufzeit der Algorithmen interessieren, möchten Sie möglicherweise irgendwann die Zeit messen können, die für die Ausführung eines Algorithmus benötigt wird. Sie werden hier erfahren, wie Sie Zeitmessungen machen können.\n", "\n", "Um zu messen, wie lange die Ausführung Ihres Algorithmus dauert, können Sie mit der Funktion `time.time()` des Moduls `time` Zeitstempel abfragen. Sie können sich vorstellen, dass Sie am Anfang des zu messenden Bereichs einen Timer stellen und am Ende schauen, wieviel Zeit vergangen ist. Dazu rufen Sie zweimal die Funktion `time.time()` auf und ermitteln die Differenz dieser beiden Werte. \n", "\n", "Das Modul `time` bietet noch andere zeitbezogene Funktionen. \n", "\n", "**Beispiel**\n", "\n", "Um die Zeitmessung zu demonstrieren, wird die Funktion `time.sleep(d)` verwendet, wobei `d` der Dauer in Sekunden entspricht. \n", "\n", "Der Startwert wird in die Variable `startzeitpunkt` gespeichert, dann wird in einer Schleife zehnmal eine Sekunde lang gewartet und anschliessend wird der aktuelle Wert in die Variable `endzeitpunkt` gespeichert. Die Differenz der beiden Werte entspricht der vergangenen Dauer in Sekunden und wird ausgegeben.\n", "\n", "Da im Beispiel zehnmal eine Sekunde gewartet wird, liegt die Ausgabe leicht über zehn Sekunden." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import time\n", "\n", "# Startzeitpunkt erfassen:\n", "startzeitpunkt = time.time()\n", "\n", "for i in range(10):\n", " time.sleep(1) \n", " \n", "# Endzeitpunkt erfassen:\n", "endzeitpunkt = time.time()\n", " \n", "print(\"Benötigte Zeit in Sekunden:\", (endzeitpunkt - startzeitpunkt)) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Weitere Informationen zu «Zufallszahlen»\n", "\n", "##### random.random()\n", "\n", "Mit der Funktion `random.random()` lassen sich «zufällige» Fliesskommazahlen im Bereich von 0.0 bis und ohne 1.0 generieren. Werden die Zahlen gerundet, kann dabei auch die Zahl 1.0 entstehen.\n", "\n", "Das folgende Beispiel generiert eine Liste mit zehn «zufällige» Floatwerten im Bereich von 0.0 bis und ohne 1.0:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "print([random.random() for x in range(10)])\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Funktion random.randint()\n", "\n", "Mit der Funktion `random.randint(a, b)` lassen sich «zufällige» Ganzzahlen (Integers) im Bereich von a bis und *mit* b generieren.\n", "\n", "Das folgende Beispiel generiert eine Liste mit 10 «zufälligen» Integern im Bereich von 1 bis und mit 100:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print([random.randint(1, 100) for x in range(10)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Simulation eines Würfels\n", "\n", "Die generierten «Zufallszahlen» sind *uniform* verteilt. Das bedeutet, sie kommen alle etwa gleich oft vor, sind also gleich wahrscheinlich. \n", "\n", "Dies können Sie beispielsweise nutzen, um einen Würfel zu simulieren. \n", "\n", "Wenn Sie also 60 «Zufallszahlen» von 1 bis 6 generieren, wird jeder Wert etwa zehnmal auftreten. Je mehr Zahlen Sie erstellen, desto ähnlicher werden sich die Anzahl Vorkommen.\n", "\n", "**Challenge – Simulation eines Würfels**\n", "\n", "* Vorbereitung: \n", " Erstellen Sie eine Liste `wuerfelzahlen` und initialisieren Sie diese mit sechs Nullen. In dieser Liste werden Sie die Anzahl Vorkommen der Werte 1 bis 6 sammeln.\n", "* Würfeln: \n", " Generieren Sie nun 6'000 «Zufallszahlen» und erhöhen Sie die Zähler jeweils in der Liste `wuerfelzahlen`.\n", "* Geben Sie die Liste `wuerfelzahlen` aus. Sie dürfen erwarten, dass alle sechs Werte in `wuerfelzahlen` in der Grössenordnung 1000 sind.\n", "* Ändern Sie die Anzahl der generierten Würfe, beispielsweise 100, 1'000, ..., 1'000'000. Sie werden sehen, dass Ihr Loop an die Grenzen stösst, übertreiben Sie es also nicht. Falls Sie die Ausführung Ihres Programms abbrechen wollen, können Sie den Kernel unterbrechen (Menü Kernel > Interrupt oder ◼️-Button)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "import random\n", "\n", "# In Zeile 8 den Bereich (Range) anpassen und 100, 1000, ... 1'000'000 \"Zufallszahlen\" generieren.\n", "# Die Liste rands enthält die Anzahl der Vorkommen der einzelnen Augenzahlen,\n", "# wobei sich die Vorkommen in der gleichen Grössenordnung befinden.\n", "\n", "wuerfelzahlen = [0 for x in range(6)]\n", "for i in range (1, 6000): # <--- range anpassen...\n", " wurf = random.randint(1, 6)\n", " if wurf == 1:\n", " wuerfelzahlen[0]+=1 # wuerfelzahlen[0] entspricht der Anzahl Einsen\n", " elif wurf == 2:\n", " wuerfelzahlen[1]+=1 # wuerfelzahlen[1] entspricht der Anzahl Einsen\n", " elif wurf == 3: \n", " wuerfelzahlen[2]+=1 # wuerfelzahlen[2] entspricht der Anzahl Einsen\n", " elif wurf == 4:\n", " wuerfelzahlen[3]+=1 # wuerfelzahlen[3] entspricht der Anzahl Einsen\n", " elif wurf == 5: \n", " wuerfelzahlen[4]+=1 # wuerfelzahlen[4] entspricht der Anzahl Einsen\n", " elif wurf == 6:\n", " wuerfelzahlen[5]+=1 # wuerfelzahlen[5] entspricht der Anzahl Einsen\n", " \n", "print(wuerfelzahlen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Pseudozufallszahlen\n", "\n", "Vielleicht ist Ihnen aufgefallen, dass der Begriff *Zufallszahlen* weiter oben mit Gänsefüsschen versehen ist. Die mit `random` generierten Zufallszahlen sehen zwar aus, als wären sie zufällig entstanden, wurden aber mit einem Algorithmus generiert, der dieselben Werte liefert, wenn er mit dem gleichen Wert initialisiert wird. Diese Zahlen sind dadurch nicht ganz so zufällig. Solange Sie keine sicherheitsrelevanten Anwendungen programmieren, können Sie bedenkenlos Pseudozufallszahlen verwenden.\n", "\n", "Mit der Funktion `random.seed()` lässt sich der Zufallszahlengenerator initialisieren. \n", "\n", "**Aufgabe 3 – Zufallszahlengenerator initialisieren**\n", "\n", "* Initialisieren Sie den Zufallszahlengenerator mit einer Zahl (z.B. 12).\n", "* Erstellen Sie anschliessend 10 Zufallszahlen. \n", "\n", "Dies machen Sie zweimal hintereinander. Was kommt dabei heraus?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "random.seed(12)\n", "print([random.randint(0,100) for x in range(10)])\n", "\n", "random.seed(12)\n", "print([random.randint(0,100) for x in range(10)])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Es wird tatsächlich dieselbe Liste generiert. \n", "\n", "😱 Sie können sich nun vorstellen, weshalb Pseudozufallszahlen in sicherheitsrelevanten Applikationen nicht verwendet werden dürfen. Zum Glück wird der Prüfcode, den Sie erhalten, wenn Sie sich ins Onlineportal Ihrer Bank einloggen, etwas weniger vorhersagbar generiert! " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.8" } }, "nbformat": 4, "nbformat_minor": 4 }