{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Algorithmen\n", "\n", "Algorithmen sind nichts Neues für Sie. Immerhin haben Sie schon programmiert und sind damit vertraut, Probleme mit Hilfe einer Abfolge klar definierter Befehle zu lösen. Sie kennen vielleicht sogar bereits Funktionen, die Argumente entgegennehmen, verarbeiten und ein Resultat zurückgeben.\n", "\n", "In diesem eher informativen Notebook lernen Sie die Eigenschaften von Algorithmen kennen und sehen, warum es wichtig ist, Algorithmen exakt zu beschreiben. Manchmal ist diese exakte Beschreibung nicht so einfach. Dann kann Pseudocode zielführend sein oder eine grafische Darstellung in Form von Flussdiagrammen und Struktogrammen. Im Abschnitt zur Komplexität erfahren Sie, warum Algorithmen möglichst effizient sein sollen.\n", "\n", "---\n", "**Ziele**\n", "\n", "* Sie können in eignen Worten beschreiben, was ein Algorithmus ist und die fünf Eigenschaften von Algorithmen nennen und beschreiben.\n", "* Sie nennen Alltagsalgorithmen und beschreiben diese.\n", "* Sie erkennen, warum es wichtig ist, Algorithmen exakt zu formulieren.\n", "---- \n", "\n", "Auch im Alltag verwenden Sie Algorithmen. Als Analogie zu einem Algorithmus wird oft das Kochrezept genannt. Sie benötigen verschiedene Zutaten (*Eingabe*), die in einem genau definierten Ablauf verarbeitet werden (*Verarbeitung*), bis Sie am Ende ein Gericht haben oder einen Kuchen oder eine Salatsauce (*Ausgabe*). Algorithmen folgen also dem EVA-Prinzip (Eingabe – Verarbeitung – Ausgabe).\n", "\n", "Schauen Sie sich das folgende Rezept für Reis an:\n", "\n", "1. Eine kleine Zwiebel in heissem Öl anbraten.\n", "2. Eine Tasse Reis waschen, zugeben und umrühren, bis der Reis glasig wird.\n", "3. Zwei Tassen Wasser und etwas Salz zugeben.\n", "4. Die Hitze reduzieren und in den nächsten ca. 20 Minuten gelegentlich umrühren.\n", "5. Wenn beim Umrühren kein Wasser mehr zum Vorschein kommt, ist der Reis gar.\n", "\n", "Haben Sie noch nie selbst gekocht und hätten das Rezept gerne genauer?\n", "\n", "1. Eine kleine Tasse Reis abmessen.\n", "2. Den Reis in ein Sieb giessen und unter dem Wasserstrahl waschen.\n", "3. Eine kleine Zwiebel schälen.\n", "4. Die Zwiebel halbieren.\n", "5. Die Zwiebel hacken.\n", "6. Einen Esslöffel Öl in einer Pfanne heiss werden lassen.\n", "7. Die gehackte Zwiebel ins Öl geben und kurz anbraten.\n", "8. Den Reis zugeben.\n", "9. Umrühren, bis der Reis glasig wird.\n", "10. Den Reis mit zwei Tassen Wasser ablöschen.\n", "11. Einen halben Teelöffel Salz zugeben.\n", "12. Die Hitze vermindern.\n", "13. Alle 3 Minuten umrühren.\n", "14. Wenn der Reis nicht mehr im Wasser schwimmt, ist er fertig.\n", "\n", "Wahrscheinlich wissen Sie noch immer nicht, welche Art von Reis Sie verwenden sollten, welche Öle in Frage kommen oder auf welche Stufe Sie die Herdplatte erhitzen müssen. Und steht da überhaupt etwas von einer Herdplatte oder von einer Pfanne?\n", "\n", "**Aufgabe 1** \n", "\n", "Überlegen Sie sich, was für Algorithmen Sie aus dem Alltag kennen und versuchen Sie einen genau zu beschreiben.\n", "\n", "
\n", " \n", " Hinweis\n", " \n", "\n", "Mögliche Algorithmen aus dem Alltag wären neben Kochrezepten beispielsweise Spielanleitungen, Lego- oder Bauanleitungen, Wegbeschreibungen oder Tätigkeiten wie Zähneputzen oder Schuhebinden.\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Schauen Sie sich nun die Folge der Exact Instructions Challenge von Josh Darnit auf [YouTube](https://www.youtube-nocookie.com/embed/FN2RM-CHkuI) an. \n", "\n", "*Um den Videoclip sehen zu können, müssen Sie allenfalls die folgende Zelle ausführen.*" ] }, { "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-nocookie.com/embed/FN2RM-CHkuI\", width=560, height=315)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Aufgabe 2**\n", "\n", "Nehmen Sie eines der hier gezeigten Bilder und machen Sie eine möglichst genaue Anleitung, um das Gezeigte zu erstellen. Tauschen Sie dann mit einer Partnerin oder einem Partner die Anleitung aus und versuchen Sie gegenseitig, die Anleitungen zu befolgen. Kommen Sie auf dasselbe Ergebnis?\n", "\n", "Kreuzknoten | Bauklötze | Zopf | Lego | Endacht\n", ":-: | :-: | :-: | :-: | :-:\n", " | | | |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Eigenschaften von Algorithmen\n", "\n", "Es ist gar nicht so einfach, eine Anleitung *unmissverständlich* zu formulieren. Manchmal fehlen auch Details für ganz *genaue* Angaben. \"Nach Belieben würzen\" können Sie beispielsweise nicht so beschreiben, dass das Ergebnis dasselbe ist, wenn jemand anderes Ihr Rezept umsetzt.\n", "\n", "Viele Alltagsalgorithmen sind dann doch keine Algorithmen im Informatiksinn: Menschen mit Erfahrung können ein Gericht \"nach Belieben würzen\", **eine Maschine ist auf genaue** Mengen**angaben und Anweisungen angewiesen**.\n", "\n", "Zu jedem Zeitpunkt muss unmissverständlich klar sein, was als nächstes zu tun ist (**Eindeutigkeit**) und der Schritt muss ausführbar sein (**Ausführbarkeit**). Dieselben Eingabewerte müssen zur gleichen Ausgabe führen, aber der Algorithmus soll auch für andere Eingabewerte eine korrekte Ausgabe zur Folge haben (**Korrektheit**). Weiter soll ein Algorithmus nach einer endlichen Anzahl Schritte zu Ende kommen – entweder zu einer Ausgabe oder zu einem gezielt herbeigeführten Abbruch (**Endlichkeit**). Es wäre eine Verschwendung, mit einem Algorithmus nur ein spezifisches Problem zu lösen, weshalb Algorithmen allgemeingültig, also auf verschiedene Probleme anwendbar sein sollen (**Allgemeinheit**).\n", "\n", "
\n", "\n", "**Zusammenfassung**\n", "\n", "> Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems.\n", ">\n", "> Algorithmen haben folgende Eigenschaften:\n", "> \n", "> * **Eindeutigkeit**: Zu jedem Zeitpunkt ist klar, worin der nächste Schritt besteht.\n", "> * **Ausführbarkeit**: Jeder Schritt muss ausführbar sein.\n", "> * **Korrektheit**: Der Algorithmus liefert für sämtliche Eingabewerte eine korrekte Ausgabe.\n", "> * **Endlichkeit**: Der Algorithmus ist nach einer endlichen Anzahl Schritte fertig.\n", "> * **Allgemeinheit**: Der Algorithmus kann für verschiedene Probleme angewandt werden.\n", "\n", "
\n", "\n", "## Darstellung von Algorithmen\n", "\n", "Algorithmen können in verschiedenen Programmiersprachen implementiert werden. Dazu ist Wissen über die Programmiersprache erforderlich (über die Syntax der Sprache und gewisse Eigenheiten).\n", "\n", "Da es sich bei den Algorithmen allerdings um Verfahren handelt, wie ein Problem zu lösen ist, soll der Fokus in einem ersten Schritt nicht auf der Syntax und den Eigenheiten der Programmiersprache liegen, sondern auf der Lösung des Problems.\n", "\n", "Um ein Problem lösen zu können, muss dieses erst einmal klar definiert werden. Es muss klar sein, was gegeben ist (Eingabe) und was gesucht (Ausgabe). Wie Sie im Clip \"Exact Instructions Challenge\" weiter oben gesehen haben, muss der Ablauf schliesslich genau beschrieben werden. Es gibt verschiedene Darstellungsmöglichkeiten, die hier kurz eingeführt werden sollen. Nutzen Sie auch diese [Übersicht über die Darstellungsformen](./downloads/cheatsheet_algorithmen–darstellung.pdf).\n", "\n", "### Pseudocode\n", "\n", "Einen Algorithmus präzise in natürlicher Sprache zu beschreiben, kann sehr umständlich sein und ausführbaren Code in einer Programmiersprache zu schreiben wäre unter Umständen zu aufwändig und vor allem nicht universell verständlich, weil es zahlreiche Programmiersprachen mit unterschiedlicher Syntax und jeweils gewissen Besonderheiten gibt und das Verfahren allgemeingültig beschrieben werden soll. Deshalb werden Algorithmen oft mit **Pseudocode** beschrieben.\n", "\n", "Wenn Sie Pseudocode schreiben, dürfen Sie auch so tun, als würden Ihnen Funktionen zur Verfügung stehen, die Sie brauchen. So dürfen Sie beispielsweise schrieben `a und b tauschen` ohne sich darum kümmern zu müssen, wie dieser Tausch genau implementiert wird. Je nach Abstraktionsniveau wird Ihr Pseudocode mehr oder weniger detailliert sein. In der Regel genügt beispielsweise `l sortieren`, wenn eine Liste `l` sortiert werden soll. Wenn Sie sich mit Sortieralgorithmen beschäftigen, liegt der Fokus aber auf den Sortier*verfahren* und Ihr Pseudocode wird genauer beschreiben, wie die Suche ablaufen soll.\n", "\n", "**Beispiel Mittelwert**\n", "\n", "Nehmen Sie ein Beispiel, das Sie in der Schule oft anwenden, beispielsweise wenn Sie eine Prüfung zurückbekommen: Den Mittelwert.\n", "\n", "Er kann folgendermassen berechnet werden:\n", "\n", "$Mittelwert = \\frac{Summe\\_der\\_Einzelwerte}{Anzahl\\_Einzelwerte}$\n", "\n", "Diese Formel ist ähnlich wie Pseudocode: Sie beschreibt, wie vorzugehen ist, aber sie beschreibt nicht, wie die einzelnen Elemente zustande kommen. Um die Vorgehensweise zu verstehen, ist sie aber hilfreich, und möglicherweise auch lesbarer als eine ganz formale Beschreibung, die sich davon ableiten lässt.\n", "\n", "Pseudocode für die Berechnung des Mittelwertes könne folgendermassen aussehen:\n", "\n", "```\n", "Eingabe: liste l von Werten\n", "summe = summe aller Elemente von l\n", "mittelwert = summe / länge(l)\n", "```\n", "\n", "### Grafische Darstellungsformen\n", "\n", "Neben Pseudocode gibt es auch zwei grafische Darstellungsformen, die oft verwendet werden, um Algorithmen zu beschreiben. Das Flussdiagramm haben Sie bereits gesehen, als Sie Verzweigungen und Schleifen kennengelernt haben.\n", "\n", "Daneben gibt es auch noch das Struktogramm, nach den Erfindern auch bekannt als Nassi-Shneiderman-Diagramm. Die Elemente finden Sie in der Übersicht über die Darstellung von Algorithmen (PDF).\n", "\n", "**Beispiel GGT**\n", "\n", "Der euklidische Algorithmus gilt als der älteste bekannte nicht-triviale Algorithmus. Das Verfahren wurde von Euklid um 300 v. Chr. in seinem Werk Die Elemente beschrieben ([Wikipedia](https://de.wikipedia.org/wiki/Euklidischer_Algorithmus)). Auf der Suche nach einem gemeinsamen Mass für die Längen zweier Elemente wurde jeweils die kleinere der beiden Längen von der grösseren abgezogen.\n", "\n", "Vergleichen Sie die verschiedenen Darstellungsformen.\n", "\n", "* Code in Python:\n", "\n", " ```Python\n", "def GGT(a, b):\n", " if a == 0:\n", " ggt = b\n", " else:\n", " while b != 0:\n", " if a > b:\n", " a = a - b\n", " else:\n", " b = b - a\n", " ggt = a\n", " return ggt \n", " ```\n", " \n", "* Pseudocode:\n", " \n", " ```\n", " Eingabe: zwei Zahlen, a und b, mit a < b\n", " falls a = 0:\n", " b ist der ggt: zurückgeben\n", " sonst:\n", " solange b != 0:\n", " den grösseren Wert um den kleineren verringern\n", " a ist der ggt: zurückgeben\n", " ```\n", "\n", "* Flussdiagramm\n", "\n", "\n", "\n", "* Struktogramm\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Komplexität\n", "\n", "Algorithmen werden zur Verarbeitung riesiger Datenmengen verwendet. Da dies Zeit braucht, sind Informatikerinnen und Informatiker daran interessiert, möglichst effiziente Algorithmen zu finden. Wenn von der Effizienz eines Algorithmus die Rede ist, spricht man von **Komplexität**. \n", "\n", "Es gibt Algorithmen, die schnell rechnen, aber viel Speicher brauchen, um Zwischenergebnisse zu speichern und andere, die wenig Speicher benötigen, aber dafür langsamer sind. Um die Komplexität eines Algorithmus anzugeben, wird zwischen Laufzeit und Speichereffizienz unterschieden. Um die Laufzeit zu bestimmen, wird davon ausgegangen, dass $n$ Elemente verarbeitet werden, wobei $n$ eine sehr grosse Zahl darstellt. \n", "\n", "Sie werden hier nicht erfahren, wie die Laufzeit berechnet werden kann, aber Sie werden die Anzahl Berechnungen vergleichen und allenfalls sogar Zeitmessungen machen. Dabei werden Sie sehen, dass sich Algorithmen optimieren lassen und dass es beispielsweise nicht *den* ultimativen Sortieralgorithmus gibt, und dass sich sogar ein nicht gerade für seine Effizienz bekannter Algorithmus in gewissen Situationen dennoch anbieten kann.\n", "\n", "Algorithmen zu optimieren kann ein kreativer Prozess sein und oftmals entstehen Lösungen, die man am Anfang nicht erwartet hätte. In der Regel geht man dabei von der einfachsten Lösung aus und spricht dann von \"Brute Force\", also von \"roher Gewalt\". Die erste, meist intuitive Lösung ist nicht so schlecht oder böse wie das nun klingt. Sie bildet die Basis für Optimierungen, aber sich mit der erstbesten Lösung zufriedenzugeben, kann kostspielig sein und indem sie ihre Algorithmen optimieren, können Programmiererinnen und Programmierer sogar einen Beitrag zum **Energiesparen** leisten." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Quiz\n", "\n", "Alles klar? \n", "\n", "Testen Sie Ihr Verständnis anhand der Fragen, die erstellt werden, wenn Sie die nachfolgende Zelle 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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "import quiz\n", "\n", "display(quiz.Q1_algorithmen)\n", "display(quiz.Q2_algorithmen)\n", "display(quiz.Q3_algorithmen)" ] }, { "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 }