{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Suchen (Lösungen)\n", "\n", "Die ersten Algorithmen, mit denen Sie sich auseinandersetzen werden, dienen der Suche nach einem Element in einer Liste.\n", "\n", "---\n", "**Ziele**\n", "\n", "Sie können\n", "* sicher auf Listenelemente zugreifen.\n", "* über Listen *iterieren* (also *darüber loopen*, *Listen mit einer Schleife durchlaufen*).\n", "* die lineare und die binäre Suche mit eigenen Worten beschreiben.\n", "* die lineare Suche implementieren und Ihre Implementation erklären.\n", "* die binäre Suche auf Papier durchgehen und zeigen, dass sie schneller ist als die lineare Suche.\n", "* beurteilen, welcher der beiden Suchalgorithmen sich für eine bestimmte Ausgangslage eignet.\n", "* an einem Beispiel zeigen, dass es sich auch im Falle einfacher Algorithmen lohnen kann, über Optimierungen nachzudenken.\n", "\n", "Ausserdem sollten Sie sehen, dass es sich lohnt, Probleme schrittweise anzugehen. Wenn Sie erst den ganzen Code schreiben, bevor Sie ihn zum ersten Mal ausführen, werden Sie länger nach dem Fehler suchen müssen, falls etwas nicht funktioniert hat, auch wenn Sie die Fehlermeldungen lesen können.\n", "\n", "---\n", "\n", "## Suchspiele\n", "\n", "Um sich mit der Suche von Elementen auseinanderzusetzen, können Sie spielerisch vorgehen. Falls Sie nicht alleine arbeiten, suchen Sie sich eine Partnerin oder einen Partner und probieren Sie die folgenden Spiele aus. Ansonsten überlegen Sie sich kurz, wie Sie vorgehen würden.\n", "\n", "### Schiffe versenken\n", "\n", "Stellen Sie sich eine vereinfachte Form des Spiels \"Schiffe versenken\" in einem Fluss vor. Der Fluss ist in Felder eingeteilt (Sehen Sie die Liste dahinter?) und jedes Schiff hat eine Nummer. Die Nummern sind aber nicht geordnet. Die Schiffe bewegen sich nicht und der Fluss ist in Felder unterteilt (A bis Z). Jede Person hat nun ein Schiff der Länge 1 zur Verfügung. Überlegen Sie sich, wie Sie vorgehen müssen, um das gegnerische Schiff zu finden.\n", "\n", "\n", "| 🚢 83 | 🚢 47 | 🚢 44 | 🚢 72 | 🚢 15 | 🚢 16 | 🚢 12 | 🚢 68 | 🚢 9 | 🚢 58 | 🚢 11 | 🚢 55 | 🚢 78 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| A | B | C | D | E | F | G | H | I | J | K | L | M |\n", "\n", "| 🚢 46 | 🚢 93 | 🚢 87 | 🚢 60 | 🚢 35 | 🚢 2 | 🚢 10 | 🚢 4 | 🚢 99 | 🚢 26 | 🚢 70 | 🚢 22 | 🚢 14 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |\n", "\n", "\n", "\n", "**Variante** \n", "\n", "Nun haben die Schiffe wiederum Nummern. Die Nummern sind aber geordnet. Wie müssten Sie nun vorgehen, um das gegnerische Schiff möglichst schnell zu finden?\n", "\n", "| 🚢 2 | 🚢 4 | 🚢 9 | 🚢 10 | 🚢 11 | 🚢 12 | 🚢 14 | 🚢 15 | 🚢 16 | 🚢 22 | 🚢 26 | 🚢 35 | 🚢 44 |\n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| A | B | C | D | E | F | G | H | I | J | K | L | M |\n", "\n", "| 🚢 46 | 🚢 47 | 🚢 55 | 🚢 58 | 🚢 60 | 🚢 68 | 🚢 70 | 🚢 72 | 🚢 78 | 🚢 83 | 🚢 87 | 🚢 93 | 🚢 99 | \n", "| : | : | : | : | : | : | : | : | : | : | : | : | : |\n", "| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |\n", "\n", "\n", "Diese Übung ist inspiriert von [CS Unplugged: Schiffe versenken](https://classic.csunplugged.org/wp-content/uploads/2014/12/CSUnplugged_OS_2015_v3.2.2_AL_Ak-6.pdf) von der Seite zu [Suchalgorithmen](https://classic.csunplugged.org/searching-algorithms/).\n", "\n", "### Wer ist es?\n", "\n", "Wahrscheinlich mögen Sie sich an das Spiel \"Wer ist es\" erinnern, bei dem zwei Spielerinnen oder Spieler je zweimal dieselben Gesichter hatten, einmal als Spielkarten, einmal zum Umklappen. Zu Beginn suchten sich beide Spieler oder Spielerinnen ein Gesicht aus. Die Gesichter hatten Eigenschaften und es galt anhand der Eigenschaften die Auswahl möglichst schnell einzugrenzen, um das Gesicht des Gegners oder der Gegnerin zu finden.\n", "\n", "Je besser die Fragen, desto schneller war die gesuchte Person gefunden. Falls Sie eine Fotoklassenliste haben, lässt sich dieses Spiel schnell realisieren, ansonsten gibt es hier eine Idee aus Emojis, die Sie [herunterladen](./downloads/wer_ist_es.pdf) und ausdrucken können. Viel Spass beim Suchen und Raten.\n", "\n", "\n", "\n", "## Suchalgorithmen\n", "\n", "Die Suchspiele haben gezeigt, dass es verschiedene Strategien gibt, um ein Element in einer Sammlung von Elementen zu finden. Im Spiel \"Wer ist es\" hatten Sie den Blick auf das Ganze und konnten die Gesichter aussortieren, die nicht dem Kriterium entsprachen, das gerade genannt wurde. Dadurch wird die Auswahl immer kleiner. Genauso können Sie auch vorgehen, wenn die Elemente geordnet sind. Das Prinzip, wenn ein Problem immer weiter eingeschränkt wird, nennt man **Teile und Herrsche** (Divide & Conquer). Dieses Prinzip kommt in der Informatik oft zur Anwendung wird Ihnen auch bei den Sortieralgorithmen wieder begegnen.\n", "\n", "Wenn die Elemente nicht geordnet sind oder keine Möglichkeit besteht, das Problem einzugrenzen, wird die Suche mühsamer. Welche Strategie haben Sie bei der ersten Runde Schiffe versenken angewandt? Wahrscheinlich sind Sie die Liste entweder anhand eines Musters durchgegangen (von vorne nach hinten oder umgekehrt oder zuerst von vorne nach hinten jedes zweite Element und dann wieder zurück für die übriggebliebenen Elemente). Vielleicht haben Sie auch zufällig irgendwelche Werte genannt, wobei Sie aufpassen mussten, dass Sie den Überblick behielten und nicht zweimal denselben Wert prüften. Möglicherweise haben Sie mit einer Person gespielt, die Sie sehr gut kennen und haben die Suche dadurch möglicherweise eingegrenzt. Dazu benötigten Sie aber Informationen über die Person. Dies wäre zwar ebenfalls ein Ansatz, um ein Element zu finden, aber einer, der auf künstlicher Intelligenz beruht. So zeigt Ihnen Google beispielsweise die Werbung, die Sie am ehesten interessieren könnte, weil Google Daten zu Ihrem Suchverhalten analysiert hat. Dieser Kurs geht nicht auf diese Art von Algorithmen ein, aber da es immer wieder Schülerinnen und Schüler gibt, die auf diese Weise suchen würden, wird es hier erwähnt.\n", "\n", "Sie sehen also, je nachdem, ob die Daten, die Sie durchsuchen sortiert sind oder nicht, kommen andere Strategien zum Zug. An dieser Ausgangslage lassen sich zwei bekannte Suchalgorithmen zeigen: die lineare Suche und die binäre Suche. Sie werden im Folgenden thematisiert, aber da Sie für beide Suchalgorithmen sicher auf Listenelemente zugreifen und diese mit dem gesuchten Wert vergleichen müssen, machen Sie zuerst eine vorbereitende Übung.\n", "\n", "**Aufgabe 1 – Vorbereitung: Vergleich eines Listenelements mit einem gegebenen Wert** \n", "\n", "Um die Suchalgorithmen zu implementieren, müssen Sie auf Listenelemente zugreifen und deren Inhalte mit dem gesuchten Wert *vergleichen* können.\n", "\n", "Gegeben ist der folgende Code:\n", "\n", "```Python\n", "liste = [2,6,1,8,2,7,0]\n", "gesuchter_wert = 7\n", "```\n", "Sie wollen überprüfen, ob das vierte Element der Liste `liste` gleich dem gesuchten Wert ist. Implementieren Sie dies.\n", "\n", "Hinweis: \n", "Sie müssen den Vergleich nicht verwerten, also keine Verzweigung implementieren. Ihr Vergleich soll lediglich einen Boolean liefern: `True` wenn die beiden Elemente gleich sind gleich sind, `False` wenn sie nicht gleich sind." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "liste = [2,6,1,8,2,7,0]\n", "gesuchter_wert = 7\n", "\n", "# Zugriff aufs vierte Element der Liste liste:\n", "# Ihr Code...\n", "\n", "# Vergleich dieses Elements mit dem gesuchten Wert:\n", "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "liste = [2,6,1,8,2,7,0]\n", "gesuchter_wert = 7\n", "\n", "# Lösung:\n", "\n", "# Zugriff aufs vierte Element der Liste liste: \n", "print(liste[3]) # print macht den Wert in der Konsole sichtbar, gesucht ist nur liste[3]\n", "\n", "# Der Vergleich dieser beiden Werte liefert entweder True oder False zurück:\n", "\n", "liste[3] == gesuchter_wert" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bei der linearen Suche werden Sie nicht nur irgendein Element der Liste mit dem gesuchten Wert vergleichen wollen, sondern die Liste systematisch durchgehen und jedes Element mit dem gesuchten Wert vergleichen.\n", "\n", "**Aufgabe 2 – Listendurchlauf**\n", "\n", "Gehen Sie die Liste `liste` durch, d.h. machen Sie eine Schleife, welche die Liste durchläuft und den Wert jedes Elements ausgibt: \n", "Index 0 Wert 2 \n", "Index 1 Wert 6\n", "\n", "Es geht hier darum, die Liste durchzugehen und die Elemente der Liste auszugeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "# Es gibt zwei Möglichkeiten, über eine Liste zu iterieren und die \n", "# Listenelemente auszugeben.\n", "\n", "# Die erste geht über den Index\n", "print(\"Variante 1\")\n", "for i in range(0, len(liste)):\n", " print(liste[i])\n", " \n", "# Bei der zweiten Möglichkeit werden sämtliche Elemente angenommen:\n", "print(\"Variante 2\")\n", "for element in liste:\n", " print(element)\n", "\n", "# Da Sie am Ende werden wissen wollen, wo das Element in der Liste \n", "# genau war (Index), bietet sich für diese Aufgabe die erste Variante an.\n", "print(\"Lösung\")\n", "for i in range(0, len(liste)):\n", " print(\"Index\", i, \"Wert\", liste[i])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lineare Suche\n", "\n", "Um ein Element in einer ungeordneten Liste zu finden, muss diese durchlaufen und jedes Element mit dem gesuchten Wert verglichen werden.\n", "\n", "Da dies der erste Algorithmus ist, den Sie implementieren, werden Sie Schritt für Schritt durchgeführt.\n", "\n", "**Aufgabe 3 – Lineare Suche**\n", "\n", "Suchen Sie in einer Liste ein Element.\n", "\n", "a) Erstellen Sie eine Liste `unsortierte_liste`.\n", "* Erstellen Sie zuerst eine Liste, welche die Ganzzahlen von 0 bis 19 enthält." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "unsortierte_liste = [x for x in range(20)]\n", "\n", "# Kontrolle mit print:\n", "print(unsortierte_liste)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "b) Mischen Sie nun die Liste mithilfe der Funktion `random.shuffle()` aus dem Modul `random`. \n", "\n", "Vergessen Sie nicht, das Modul `random` zu importieren.\n", "\n", "
\n", " \n", " Hinweis\n", " \n", "\n", "```Python\n", "import random\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", "random.shuffle(unsortierte_liste)\n", "\n", "# Kontrolle mit print:\n", "print(unsortierte_liste)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "c) Grundgerüst der Funktion erstellen.\n", "\n", "Nun bereiten Sie Ihre Funktion für die lineare Suche vor:\n", "\n", "* Erstellen Sie eine Funktion `suche_linear()`. \n", "* Sie nimmt noch keinen Parameter entgegen, wird aber einen Index zurückgeben. \n", "* Jede Funktion braucht einen Funktionskörper. Solange nichts gemacht wird, können Sie einfach nichts zurückgeben:\n", "```Python\n", " return\n", "```\n", "* Rufen Sie Ihre Funktion auf.\n", "\n", "Damit haben Sie das Grundgerüst der Funktion. Sie macht noch nicht viel Gescheites, daru, sehen Sie auch nicht viel." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def suche_linear():\n", " return\n", "\n", "suche_linear()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Wie schnell schleicht sich ein Tippfehler ein oder geht ein Doppelunkt vergessen...* Indem Sie Ihren Code Stück für Stück schreiben und immer wieder ausprobieren ob die einzelnen Teile laufen oder zumindest kompilieren, vermeiden Sie viele Fehler und sind im Endeffekt sicherer.\n", "\n", "d) Erweitern Sie nun Ihre Funktion `suche_linear()`.\n", "\n", "* Wenn das das Element gefunden wird, soll sich die Funktion `suche_linear` den Index in der Variable `index_gefunden` merken. \n", " * Erstellen Sie nun innerhalb Ihrer Funktion diese Variable `index_gefunden` und\n", " * initialisieren Sie sie mit dem Wert `-1`. \n", " Dieser Wert soll zurückgegeben werden, wenn die Suche erfolglos war. \n", " > *Mit dem Wert `-1` codieren Sie das Ergebnis \"nicht gefunden\"*. \n", " > Das ist ein Vorgehen, das beim Programmieren sehr oft zur Anwendung kommt.\n", "* Rufen Sie die Funktion auf, um zu überprüfen, dass sie bereits den Wert `-1` zurückgibt." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "def suche_linear():\n", " index_gefunden = -1 # Am Schluss wird der Index zurückgegeben, \n", " # an dem sich der gesuchte Wert in der Liste befindet. \n", " # Falls kein Element mit dem gesuchten Wert gefunden wurde, \n", " # wird -1 ausgegeben. Dies wird durch die Initialisierung sichergestellt. \n", " return index_gefunden\n", "\n", "suche_linear()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "e) Nun wollen Sie die Funktion um den gesuchten Wert einbauen, damit sie für beliebige Suchwerte verwendet werden kann.\n", "\n", "* Erweitern Sie Ihre Funktion `suche_linear` um einen Parameter `wert`, nach dem gesucht werden soll.\n", "* Definieren Sie ausserhalb der Funktion eine Variable `gesuchter_wert`, die den Wert enthält, nach dem gesucht werden soll, zum Beispiel 12.\n", "* Passen Sie den Funktionsaufruf an. Da die Funktion nun den gesuchten Wert als Parameter entgegennimmt, müssen Sie ihn ihr übergeben." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "gesuchter_wert = 12\n", "\n", "def suche_linear(wert):\n", " index_gefunden = -1 # Dieser Wert wird später überschrieben werden, wenn das Element gefunden wurde.\n", " return index_gefunden\n", "\n", "suche_linear(gesuchter_wert)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ihre Funktion hat nun den Parameter `wert`, aber sie macht noch nichts damit. Nun können Sie in der Liste `unsortierte_liste` das Element suchen, das den gesuchten Wert aufweist.\n", "\n", "f) Implementieren Sie nun die eigentliche Suche.\n", "\n", "* Die Funktion `suche_linear` soll die ganze Liste `unsortierte_liste` durchgehen und jedes Element mit dem Wert `wert` vergleichen.\n", "\n", "Diesen Schritt haben Sie in Aufgabe 2 und 3 bereits vorbereitet. Versuchen Sie es dennoch selbst, da es hier auch darum geht, den Umgang mit Listen zu üben: wie greifen Sie auf ein Element zu." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "gesuchter_wert = 12\n", "\n", "def suche_linear(wert):\n", " index_gefunden = -1\n", " for i in range(0, len(unsortierte_liste)):\n", " if unsortierte_liste[i] == wert:\n", " index_gefunden = i\n", " return index_gefunden\n", "\n", "\n", "suche_linear(gesuchter_wert)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "g) Generalisierung\n", "\n", "Nun haben Sie die lineare Suche implementiert. Allerdings muss zwingend eine Liste `unsortierte_liste` definiert sein, sonst greift die Funktion `suche_linear` auf etwas zu, das es nicht gibt. Schöner wäre es, der Funktion auch die Liste `unsortierte_liste` als Parameter zu übergeben.\n", "\n", "Wenn eine Funktion generalisiert ist, nennt man sie auch **generisch**, sie ist dann in verschiedenen Situationen anwendbar.\n", "\n", "* Erweitern Sie Ihre Funktion `unsortierte_liste` um den Parameter `liste`, damit Sie keine Abhängigkeit nach aussen hat. \n", "* Rufen Sie die Funktion `suche_linear(liste, wert)` mit der Liste `unsortierte_liste` und dem wert `gesuchter_wert` auf." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "gesuchter_wert = 12\n", "\n", "def suche_linear(liste, wert):\n", " index_gefunden = -1\n", " for i in range(0, len(liste)):\n", " if liste[i] == wert:\n", " index_gefunden = i\n", " return index_gefunden\n", "\n", "suche_linear(unsortierte_liste, gesuchter_wert)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "👍 Sie haben nun die lineare Suche implementiert. 👍\n", "\n", "**Aufgabe 4 – Algorithmus genau beschreiben**\n", "\n", "Um sicherzugehen, dass man einen Algorithmus verstanden hat, lohnt es sich immer, ihn in eigenen Worten zu beschreiben. Beschreiben Sie die lineare Suche deshalb in eigenen Worten so genau wie möglich." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Nutzen Sie diese Zelle für Ihre Antwort." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Lösung:*\n", "\n", "In Aufgabe 3 haben Sie den folgenden Algorithmus programmiert:\n", "\n", "1. Über die Liste iterieren und jedes Element der Liste mit dem gesuchten Wert vergleichen.\n", "2. Falls das Listenelement denselben Wert aufweist wie der Suchwert: den Index merken.\n", "3. Falls der gesuchte Wert am Ende der Iteration noch nicht gefunden wurde, einen Index merken, der in der Liste nicht vorkommen kann, z.B. -1 (sozusagen ein Code für \"nicht gefunden\").\n", "4. Den gefundenen Index zurückgeben.\n", "\n", "In Aufgabe 5 werden Sie den Algorithmus optimieren.\n", "\n", "
\n", "\n", " Optimierter Algorithmus\n", "\n", "\n", "1. Über die Liste iterieren und jedes Element der Liste mit dem gesuchten Wert vergleichen.\n", "2. Falls das Listenelement denselben Wert aufweist wie der gesuchte Wert: den Index zurückgeben. (Fertig.)\n", "3. Falls der gesuchte Wert am Ende der Iteration noch nicht gefunden wurde, einen Wert zurückgeben, den es in der Liste nicht gibt, z.B. -1 (sozusagen ein Code für \"nicht gefunden\").\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Optimierung\n", "\n", "Stellen Sie sich vor, in der Liste, in der Sie suchen, kommt der gesuchte Wert mehrmals vor. So wie die Suche nun implementiert ist, gibt die Funktion das letzte Vorkommen des gesuchten Werts aus. Die anderen Indizes werden jeweils überschrieben, wenn ein neues Vorkommen des Wertes gefunden wird. Sie haben nun zwei Möglichkeiten: Entweder Sie merken sich alle Vorkommen oder Sie beenden die Suche nach dem ersten Vorkommen. Oft hat die Suche den Zweck zu schauen, ob ein Wert überhaupt in einer Liste vorkommt.\n", "\n", "Sie können hier davon ausgehen, dass es reicht, das erste Vorkommen zu finden. Sobald ein Element gefunden wird, kann die Suche abgebrochen werden. Da Ihre Funktion einen Wert zurückgibt, reicht es, die Rückgabe gleich zu machen, sobald der Wert gefunden wurde. Damit wird die Funktion verlassen und die weiteren Elemente bis zum Ende der Liste brauchen nicht mehr verglichen zu werden.\n", "\n", "**Aufgabe 5 – Lineare Suche optimiert**\n", "\n", "Implementieren Sie nun diese Optimierung in einer neuen Funktion `suche_linear_optimiert`.\n", "\n", "* Sobald in der Liste ein Element gefunden wurde, das den gesuchen Wert aufweist, soll der Index zurückgegeben werden.\n", "* Überlegen Sie sich, ob Sie die Variable `index_gefunden` noch brauchen und inwiefern Sie den Code ändern müssten, um ohne sie auszukommen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "def suche_linear_optimiert(liste, wert):\n", " # Die Variable index_gefunden brauchen Sie hier nicht mehr ...\n", " for i in range(0, len(liste)):\n", " if liste[i] == wert:\n", " return i\n", " # ... Falls die Schleife verlassen wird, wurde nichts gefunden.\n", " # In diesem Falle kann der Wert direkt zurückgegeben werden. \n", " return index_gefunden\n", "\n", "suche_linear_optimiert(unsortierte_liste, gesuchter_wert)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Challenge – Zeitmessungen mit dem Modul time**\n", "\n", "Mit Hilfe der Funktion `time.time()` des Moduls time lassen sich 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 (am Anfang und am Ende des zu messenden Bereichs) die Funktion `time.time()` auf und ermitteln die Differenz dieser beiden Werte.\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 der *Wartezeit* in Sekunden entspricht.\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", "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": [ "* Erstellen Sie sich nun geeignete Listen (auf- und absteigend sortiert, zufällig), wenden Sie die lineare Suche darauf an und machen Sie Zeitmessungen mit dem Modul time.\n", "* Um einen Effekt zu sehen, müssen Sie eine sehr lange Liste machen (100000 Elemente)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Listen erstellen:\n", "liste_aufsteigend = [x for x in range(100000)]\n", "liste_zufaellig = [x for x in range(100000)]\n", "random.shuffle(liste_zufaellig)\n", "\n", "# Liste durchgehen und am Ende den Index des gesuchten Eintrags ausgeben\n", "\n", "def messe_suche_linear(liste, wert):\n", " \n", " index_ges_element = -1\n", " \n", " # Timer starten:\n", " startzeit = time.time() \n", "\n", " index_ges_element = suche_linear(liste, wert)\n", "\n", " # Timer stoppen:\n", " endzeit = time.time()\n", "\n", " dauer_normal = endzeit - startzeit\n", " print(\"- Lineare Suche: Das gesuchte Element\", gesuchtes_element, \"befindet sich am Index\", index_ges_element)\n", " print(\"Benötigte Zeit in Sekunden:\", (dauer_normal)) \n", " \n", " return dauer_normal\n", "\n", "\n", "# Optimierte Linere Suche\n", "def messe_suche_linear_optimiert(liste, wert):\n", " \n", " index_ges_element = -1\n", " \n", " # Timer starten:\n", " startzeit = time.time() \n", "\n", " index_ges_element = suche_linear_optimiert(liste, wert)\n", "\n", " # Timer stoppen:\n", " endzeit = time.time()\n", "\n", " dauer_optimiert = endzeit - startzeit\n", " print(\"- Lineare Suche optimiert: Das gesuchte Element\", gesuchtes_element, \"befindet sich am Index\", index_ges_element)\n", " print(\"Benötigte Zeit in Sekunden:\", (dauer_optimiert)) \n", " return dauer_optimiert\n", "\n", "\n", "print(\" -- Messungen aufsteigende Liste, erstes Element\")\n", "\n", "# aufsteigende Liste, erstes Element\n", "gesuchtes_element = liste_aufsteigend[0] # Das Element, nach dem gesucht wird\n", "dauer_normal1 = messe_suche_linear(liste_aufsteigend, gesuchtes_element)\n", "dauer_optimiert1 = messe_suche_linear_optimiert(liste_aufsteigend, gesuchtes_element)\n", "print(\"-- Vom normalen zum optimierten: Faktor\", (dauer_normal1/dauer_optimiert1))\n", "print() # Leerzeile\n", "\n", "print(\" -- Messungen aufsteigende Liste, letztes Element\")\n", "# aufsteigende Liste, letztes Element\n", "gesuchtes_element = liste_aufsteigend[len(liste_aufsteigend)-1] # Das Element, nach dem gesucht wird\n", "dauer_normal2 = messe_suche_linear(liste_aufsteigend, gesuchtes_element)\n", "dauer_optimiert2 = messe_suche_linear_optimiert(liste_aufsteigend, gesuchtes_element)\n", "print(\"-- Vom normalen zum optimierten: Faktor\", (dauer_normal2/dauer_optimiert2))\n", "print() # Leerzeile\n", "\n", "print(\" -- Messungen aufsteigende Liste, letztes Element\")\n", "# normale Liste (dasselbe Element wie im letzten Durchgang)\n", "dauer_normal3 = messe_suche_linear(liste_zufaellig, gesuchtes_element)\n", "dauer_optimiert3 = messe_suche_linear_optimiert(liste_aufsteigend, gesuchtes_element)\n", "print(\"-- Vom normalen zum optimierten: Faktor\", (dauer_normal3/dauer_optimiert3))\n", "print() # Leerzeile\n", "\n", "print(\"-- Vergleich vom besten Fall zum schlechtesten\")\n", "print(\"- Lineare Suche: Faktor\", (dauer_normal2/dauer_normal1))\n", "print(\"- Lineare Suche optimiert: Faktor\", (dauer_optimiert2/dauer_optimiert1))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Binäre Suche\n", "\n", "In einer geordneten (sortierten) Liste lässt sich ein Element deutlich schneller finden, da der Suchbereich nach dem Prinzip *Teile und Herrsche* immer mehr **eingegrenzt** werden kann, bis das gesuchte Element gefunden ist.\n", "\n", "Wenn Sie von einer von aufsteigend sortierten Liste ausgehen, gibt es für jeden Vergleich drei Möglichkeiten:\n", "* Der Wert des Elements ist **gleich** dem gesuchten Wert: \n", " Sie haben das Element **gefunden** und sind **fertig**.\n", "* Der Wert des Elements ist **kleiner** als der gesuchte Wert: \n", " Sie können das Element und alle Elemente des unteren Teils der Liste ausschliessen und sich auf den oberen Teil konzentrieren.\n", "* Der Wert des Elements ist **grösser** als der gesuchte Wert: \n", " Sie können das Element und alle Elemente oberhalb ausschliessen und sich auf die untere Seite der Liste konzentrieren.\n", "\n", "Überlegen Sie sich kurz, welches Element Sie wählen würden, um jeweils einen möglichst grossen Teil der Liste verwerfen zu können.\n", "\n", "
\n", " \n", " Lösung\n", " \n", "\n", "Wie Sie bestimmt geahnt haben, werden Sie das Element in der Mitte der Liste wählen, um jeweils einen mögichst grossen Teil der Liste verwerfen zu können.\n", "\n", "
\n", "\n", "**Aufgabe 6 – Algorithmus beschreiben**\n", "\n", "Schreiben Sie die binäre Suche in Pseudocode oder erklären Sie in eigenen Worten, wie der Algorithmus funktioniert.\n", "\n", "Schauen Sie sich [die Animation auf der Seite der Universität San Francisco](https://www.cs.usfca.edu/~galles/visualization/Search.html) an, falls Sie Mühe haben, sich vorzustellen, wie die binäre Suche genau funktioniert.\n", "\n", "**Challenge – Binäre Suche**\n", "\n", "Versuchen Sie sich an die Schritte zu halten, die Sie ans Ziel führen. Falls Sie die Challenge in Angriff nehmen möchten, nur zu. Ansonsten können Sie jederzeit hierher zurück kommen.\n", "\n", "* Für diese Liste können Sie eine aufsteigende Liste erstellen oder eine solche wiederverwenden, wenn Sie weiter oben bereits eine gemacht haben.\n", "* Wie bereits im Falle der linearen Suche soll der Wert `-1` ausgegeben werden, wenn kein Element mit dem gesuchten Wert in der Liste enthalten ist.\n", "* kennzeichnen Sie die Ränder des Listenteils, in dem Sie noch suchen mit den Variablen `links` und `rechts`.\n", "* Überprüfen Sie am Anfang, ob der gesuchte Wert in der Liste enthalten ist (dann muss er innerhalb des Bereichs von `links` bis und mit `rechts` sein).\n", "* Nachdem Sie überprüft haben, dass das Element vom Wert her in der Liste enthalten sein kann. können Sie mit der eigentlichen Suche beginnen:\n", " * Um sicherzustellen, dass nicht nur einmal gesucht wird, brauchen Sie eine Schleife, die so lange ausgeführt wird, wie mehr als ein Element in der Teilliste enthalten ist.\n", " * Wenn das Element nicht gefunden wird, können Sie es zum linken oder rechten Rand der übrigbleibenden Suchliste machen." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# mögliche Lösung\n", "\n", "meine_liste = [5*x for x in range(30)] # geordnete Liste, die nicht alle Werte enthält\n", "gesuchter_wert = 145\n", "print(\"Liste:\", meine_liste, \"\\ngesuchter Wert:\", gesuchter_wert)\n", "\n", "def suche_binaer(liste, wert):\n", "\n", " links = 0\n", " rechts = len(liste) - 1\n", " \n", " while links <= rechts: # = weil Sie die Randelemente auch finden wollen\n", " mitte = links + (rechts - links) // 2\n", " if liste[mitte] == wert:\n", " return mitte\n", " elif liste[mitte] < wert:\n", " links = mitte + 1\n", " else: \n", " rechts = mitte - 1\n", " \n", " # Wenn die Schleife verlassen wurde, muss noch der Index rechts geprüft werden,\n", " # damit alle Elemente geprüft sind\n", " if liste[rechts] == wert:\n", " return rechts\n", " # Falls das Element noch immer nicht gefunden wurde, ist es in der Liste nicht \n", " # enthalten.\n", " return -1 # das Element wurde nicht gefunden\n", "\n", "gesuchter_index = suche_binaer(meine_liste, gesuchter_wert)\n", "print(gesuchter_index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Optimierung**\n", "\n", "Eine kleine Optimierung können Sie hier noch vornehmen. Da die Liste sortiert ist, können Sie am Anfang prüfen, ob Ihr Wert überhaupt in der Liste sein kann.\n", "\n", "Ergänzen Sie die Funktion `suche_binaer` um die entsprechende Abfrage." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "meine_liste = [5*x for x in range(30)] # geordnete Liste, die nicht alle Werte enthält\n", "gesuchter_wert = 145\n", "print(\"Liste:\", meine_liste, \"\\ngesuchter Wert:\", gesuchter_wert)\n", "\n", "def suche_binaer(liste, wert):\n", " \n", " # Abfrage, ob der gesuchte Wert überhaupt in der Liste sein kann.\n", " if wert < liste[0] or wert > liste[len(liste)-1]:\n", " print(\"Der gesuchte Wert ist zu gross oder zu klein für die Liste.\")\n", " return -1\n", " \n", " links = 0\n", " rechts = len(liste) - 1\n", " \n", " while links <= rechts: # = weil Sie die Randelemente auch finden wollen\n", " mitte = links + (rechts - links) // 2\n", " if liste[mitte] == wert:\n", " return mitte\n", " elif liste[mitte] < wert:\n", " links = mitte + 1\n", " else: \n", " rechts = mitte - 1\n", "\n", " # Wenn die Schleife verlassen wurde, muss noch der Index rechts geprüft werden,\n", " # damit alle Elemente geprüft sind\n", " if liste[rechts] == wert:\n", " return rechts\n", " # Falls das Element noch immer nicht gefunden wurde, ist es in der Liste nicht \n", " # enthalten.\n", " return -1 # das Element wurde nicht gefunden\n", "\n", "gesuchter_index = suche_binaer(meine_liste, gesuchter_wert)\n", "print(gesuchter_index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Zählen Sie nun, wie oft aufgeteilt wurde. \n", " \n", "* **Extra-Challenge**: Sehen Sie hinter der maximalen Anzahl Aufteilungen eine Gesetzmässigkeit? Versuchen Sie die maximale Anzahl Aufteilungen formal auszudrücken." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung\n", "# Die formale Beschreibung der maximalen Anzahl der Aufteilungen \n", "# wird später thematisiert werden und wird hier absichtlich noch nicht aufgelöst.\n", "\n", "meine_liste = [5*x for x in range(30)] # geordnete Liste, die nicht alle Werte enthält\n", "gesuchter_wert = 145\n", "print(\"Liste:\", meine_liste, \"\\ngesuchter Wert:\", gesuchter_wert)\n", "\n", "def suche_binaer(liste, wert):\n", " \n", " # Abfrage, ob der gesuchte Wert überhaupt in der Liste sein kann.\n", " if wert < liste[0] or wert > liste[len(liste)-1]:\n", " print(\"Der gesuchte Wert ist zu gross oder zu klein für die Liste.\")\n", " return -1\n", "\n", " links = 0\n", " rechts = len(liste) - 1\n", " \n", " zaehler = 0\n", " \n", " while links <= rechts: # = weil Sie die Randelemente auch finden wollen\n", " mitte = links + (rechts - links) // 2\n", " if liste[mitte] == wert:\n", " print(\"Die Liste wurde\", zaehler, \"Mal aufgeteilt.\")\n", " return mitte\n", " elif liste[mitte] < wert:\n", " links = mitte + 1\n", " zaehler += 1 # Aufteil-Zähler um 1 erhöhen\n", " else: \n", " rechts = mitte - 1\n", " zaehler += 1 # Aufteil-Zähler um 1 erhöhen\n", " \n", " # Wenn die Schleife verlassen wurde, muss noch der Index rechts geprüft werden,\n", " # damit alle Elemente geprüft sind\n", " if liste[rechts] == wert:\n", " print(\"Die Liste wurde\", zaehler, \"Mal aufgeteilt.\")\n", " return rechts\n", " \n", " # Falls das Element noch immer nicht gefunden wurde, ist es in der Liste nicht \n", " # enthalten.\n", " print(\"Die Liste wurde\", zaehler, \"Mal aufgeteilt.\")\n", " return -1 # das Element wurde nicht gefunden\n", "\n", "gesuchter_index = suche_binaer(meine_liste, gesuchter_wert)\n", "print(gesuchter_index)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* **Testen** Sie Ihre Lösung.\n", "\n", "Um in der Softwareentwicklung die Qualität sicherzustellen, wird am Ende der Entwicklung getestet.\n", "\n", "Ihre Lösung sollten Sie testen mit\n", "* einem Wert, der sich in der Liste befindet. \n", " Erwarteter Rückgabewert: der korrekte Index des gesuchten Elements.\n", "* einem Wert, der sich nicht in der Liste befindet. \n", " Erwarteter Rückgabewert: `-1`\n", "* einem Wert, der sich ausserhalb des Wertebereichs der Liste befindet. \n", " Erwarteter Rückgabewert: `-1`\n", "* den Randwerten der Liste (erster und letzter Wert der Liste) \n", " Erwartete Rückgabewerte: `0` und `len(liste)-1`" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Ihr Code..." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Lösung:\n", "\n", "# Hier bietet sich ein Vergleich mit der linearen Suche an.\n", "meine_liste = [5*x for x in range(30)] # 30 Elemente der Fünferreihe\n", "\n", "# Wert, der sich in der Liste befindet. \n", "# Erwarteter Rückgabewert: der korrekte Index des gesuchten Elements.\n", "\n", "testwert1 = 35\n", "testresultat1 = suche_binaer(meine_liste, testwert1) == suche_linear(meine_liste, testwert1)\n", "if testresultat1:\n", " print(\"test 1: ERFOLGREICH\")\n", "else:\n", " print(\"test 1: FEHLGESCHLAGEN\")\n", "\n", "# einem Wert, der sich nicht in der Liste befindet. \n", "# Erwarteter Rückgabewert: `-1`\n", "\n", "testwert2 = 2\n", "testresultat2 = suche_binaer(meine_liste, testwert2) == -1\n", "if testresultat2:\n", " print(\"test 2: ERFOLGREICH\")\n", "else:\n", " print(\"test 2: FEHLGESCHLAGEN\")\n", "\n", "# einem Wert, der sich ausserhalb des Wertebereichs der Liste befindet. \n", "# Erwarteter Rückgabewert: `-1`\n", "\n", "testwert3 = -5\n", "testresultat3 = suche_binaer(meine_liste, testwert3) == -1\n", "if testresultat3:\n", " print(\"test 3: ERFOLGREICH\")\n", "else:\n", " print(\"test 3: FEHLGESCHLAGEN\")\n", "\n", "# den Randwerten der Liste (erster und letzter Wert der Liste) \n", "# Erwartete Rückgabewerte: `0` und `len(liste)-1`\n", "testwert4 = meine_liste[0]\n", "testresultat4 = suche_binaer(meine_liste, testwert4) == 0\n", "if testresultat4:\n", " print(\"test 4: ERFOLGREICH\")\n", "else:\n", " print(\"test 4: FEHLGESCHLAGEN\")\n", "\n", "testwert5 = meine_liste[-1]\n", "print(\"5\", testwert5)\n", "testresultat5 = suche_binaer(meine_liste, testwert5) == 29\n", "if testresultat5:\n", " print(\"test 5: ERFOLGREICH\")\n", "else:\n", " print(\"test 5: FEHLGESCHLAGEN\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quiz\n", "\n", "Alles klar?\n", "\n", "Sie sollten nun die beiden Suchalgorithmen in eigenen Worten beschreiben und Ihre Implementation der linearen Suche erklären können.\n", "\n", "Testen Sie Ihr Verständnis anhand der Fragen, die erstellt werden, wenn Sie die folgenden Zellen gemäss Ihrer Umgebung ausführen.\n", "\n", "### NUR FALLS SIE AUF GOOGLE COLAB ARBEITEN\n", "\n", "Führen Sie bitte die **beiden** folgenden Zellen aus, um die Bibliothek für das Quiz zu laden." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "%%writefile quizclone.py\n", "import os\n", "from subprocess import getoutput\n", "getoutput(\"git clone -l -s https://github.com/donze-informatikunterricht/quiz.git cloned-repo\")\n", "os.chdir('cloned-repo')\n", "print('repo cloned successfully')" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# NUR falls Sie AUF GOOGLE COLAB arbeiten:\n", "# Führen Sie diese Zelle aus, um das Quiz zu sehen.\n", "\n", "import quizclone" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Quiz erstellen (unabhängig von Ihrer Arbeitsumgebung)\n", "\n", "Nun können Sie das Quiz erstellen. Führen Sie dazu bitte die folgende Zelle aus.\n", "\n", "Teile des Quiz basieren auf dem folgenden Programm:\n", "\n", "```python\n", "import random\n", "\n", "a = [57, 57, 57, 57, 57, 57, 57, 57, 57, 57]\n", "b = [0, 6, 12, 18, 24, 30, 36, 42, 48, 54]\n", "c = [24, 89, 83, 57, 84, 10, 31, 72, 88, 73]\n", "```" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "import quiz\n", "\n", "display(quiz.Q1_suchen)\n", "display(quiz.Q2_suchen)\n", "display(quiz.Q3_suchen)\n", "display(quiz.Q4_suchen)\n", "display(quiz.Q5_suchen)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Abschluss: Suchtänze\n", "\n", "Nun haben Sie sich mit der linearen Suche und der Binären Suche auseinandergesetzt. \n", "\n", "Sehr empfehlenswert für Such- und Sortieralgorithmen ist der [YouTube-Kanal AlgoRythmics](https://www.youtube.com/channel/UCIqiLefbVHsOAXDAxQJH7Xw), der Algorithmen in Form von Tänzen präsentiert.\n", "\n", "Führen Sie die beiden folgenden Zellen aus, um die Tänze zur Linearen und Binären Suche sehen zu können." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Führen Sie diese Zelle aus, um den Videoclip sehen zu können.\n", "\n", "import IPython\n", "\n", "IPython.display.IFrame(src=\"https://www.youtube.com/embed/-PuqKbu9K3U\", width=560, height=315)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "IPython.display.IFrame(src=\"https://www.youtube.com/embed/iP897Z5Nerk\", width=560, height=315)" ] }, { "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 }