{ "cells": [ { "cell_type": "markdown", "id": "06ff6911", "metadata": {}, "source": [ "# Ausarbeitungen zu den DMTI-Übungen\n", "\n", "Dieses Notebook ist als Begleitmaterial zu den Übungen zur Vorlesung \"Diskrete Mathematik und Theoretische Informatik\" gedacht.\n", "\n", "Es enthält (unter anderem) Anleitungen und Hilfsfunktionen, mit denen die kleinen Programme, die im Rahmen der Übungen auszuarbeiten sind, in einem \"standardisierten Format\" abgespeichert werden können: Es geht meist um _Funktionen_, die ausprogrammiert werden sollen; dafür sind bereits \"Schablonen\" vorbereitet, die den Namen der Funktion und der Argumente bereits vorgeben. Ebenso vorbereitet sind kleine Hilfsfunktionen, mit den die von Ihnen in diesem Notebook ausgearbeiteten Funktionen und Progrmmteile in einzelne Files geschrieben werden.\n", "\n", "(Die Anleitungen können manchmal eine zusätzliche Recherche in der Dokumentation für python, numpy oder sympy erfordern.)\n", "\n", "Bitte verwenden Sie dieses \"standardisierte Format\"!\n", "\n", "Wenn Sie das Notebook irgendwie in einen unlesbaren Zustand bringen (das kann erfahrungsgemäß leider passieren), können Sie das \"Original\" immer wieder neu aus dem Moodle herunterladen - Ihre eigenen Ausarbeitungen sind dann aber verloren; außer wenn Sie _Sicherungskopien_ angefertigt haben: \"Sicherungskopien sind\n", " fast immer eine gute Idee!\"\n", "\n", "## Initialisierung: Module, Konstante, Hilfsfunktionen\n", "\n", "Bitte _ändern_ Sie die Konstanten (siehe auch die Kommentare bei diesen Konstanten)\n", "\n", "* MATRIKEL auf Ihre eigene Matrikelnummer\n", "* DATAPATH auf einen Pfad, in dem Sie Ihre Ausarbeitungen speichern können,\n", "\n", "und führen Sie beim Neustart dieses Notebooks immer die folgende Zelle aus:" ] }, { "cell_type": "code", "execution_count": 1, "id": "6b898f21", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Dieses Notebook wurde zuletzt am 2022-02-25 gestartet, und zwar am Rechner Kratt5\n" ] } ], "source": [ "# Import von Modulen, die (vermutlich) gebraucht werden:\n", "import sys\n", "import os\n", "import math\n", "import string\n", "import time\n", "import re\n", "import datetime\n", "import itertools\n", "import inspect\n", "import numpy as np\n", "from copy import deepcopy\n", "from sympy import Rational, nsimplify, S\n", "from scipy.special import binom\n", "import matplotlib.pyplot as plt\n", "#import pycurl\n", "import sympy as sp\n", "import sympy.solvers as spsolvers\n", "from collections import deque\n", "\n", "# KONSTANTE: Bitte ändern Sie die untenstehenden\n", "# \"Default-Werte\" passend!\n", "MATRIKEL = \"123456789\" # Bitte ändern auf Ihre Matrikelnummer!\n", "DATAPATH = \"/Users/mfulmek/tmp\" # Bitte ändern auf passenden\n", "# Pfadnamen, wo Ihre Ausarbeitungen gespeichert werden sollen:\n", "# Wenn Sie z.B. einen USB-Stick unter Windows verwenden, so\n", "# wird dieser (vermutlich) als Laufwerk \"D:\" angesprochen,\n", "# Ihr Pfadname könnte als (nur zum Beispiel!) so lauten:\n", "# DATAPATH = \"D:/ausarbeitungen\"\n", "\n", "# Beispielhafte Anwendung von Funktionen aus den Modulen\n", "# os und datetime; in einer sogenannten \"try-clause\", die\n", "# einen möglichen Fehler (der sonst zum Programmabbruch\n", "# führen würde) \"abfängt\":\n", "try:\n", " # Auf Unix-Rechnern (Linux, Mac, ...) funktioniert\n", " # das Herausfinden des Rechnernamens so:\n", " hostname = os.uname().nodename.split('.')[0].capitalize()\n", "except AttributeError:\n", " # Auf non-Unix-Rechnern (Windows) muß man das aber anders machen:\n", " hostname = os.environ['COMPUTERNAME']\n", "# Das Folgende sollte aber \"einheitlich\" funktionieren:\n", "last_started = datetime.date.today()\n", "print(f\"Dieses Notebook wurde zuletzt am {last_started} gestartet, und zwar am Rechner {hostname}\")\n", "\n", "# HILFSFUNKTIONEN\n", "def write_code(the_code, the_name, rootpath=DATAPATH):\n", " r\"\"\"Schreibe den Source-Code 'the_code' (bzw. irgendeinen\n", " String) in ein einzelnes Python-Script File mit dem Namen\n", " 'the_name'.\"\"\"\n", " # Write to file:\n", " # Nützliches Python-Konstrukt: with ... as ... sorgt \"automatisch\"\n", " # dafür, daß das File, das hier mit \"open\" geöffnet wird, am Ende\n", " # der \"with-clause\" wieder geschlossen wird!\n", " with open(os.path.join(rootpath,f'{the_name}_{MATRIKEL}.py'), 'w', encoding='utf-8') as ofile:\n", " print(the_code, file=ofile, end=\"\")\n", "\n", "def write_function(the_func,rootpath=DATAPATH,):\n", " r\"\"\"Schreibe den Source-Code der Funktion 'the_func' in ein einzelnes\n", " Python-Script File mit dem Namen der Funktion.\"\"\"\n", " # Get the source-code of the_func:\n", " text = inspect.getsource(the_func)\n", " # Get the name of the function:\n", " name = the_func.__name__\n", " # Verwende Funktion write_code: Die Zuweisung \"rootpath=rootpath\"\n", " # sieht auf den ersten Blick vielleicht schräg aus - auf der _linken_\n", " # Seite steht aber der Variablenname aus dem \"namespace\" der Funktion\n", " # write_code(), auf der rechten Seite der Variablenname aus dem \"namespace\"\n", " # der Funktion write_function(); obwohl die Variablennamen also identisch\n", " # sind, beziehen sie sich auf verschiedene Objekte.\n", " write_code(text, name, rootpath=rootpath)" ] }, { "cell_type": "markdown", "id": "ad347518", "metadata": {}, "source": [ "## Beispiele zur Verwendung der Hilfsfunktionen" ] }, { "cell_type": "code", "execution_count": 2, "id": "f378db23", "metadata": {}, "outputs": [], "source": [ "# Einfaches Beispiel: Wir definieren einen String (der einem\n", "# einfachen Python-Programm entspricht) und schreiben ihn mit\n", "# write_code() in ein File:\n", "HELLO = \"\"\"# Nur ein Beispiel:\n", "print(\"Hello, world!\")\n", "\"\"\"\n", "write_code(HELLO,'hello')" ] }, { "cell_type": "code", "execution_count": 3, "id": "f4d3c6b9", "metadata": {}, "outputs": [], "source": [ "# Noch ein Beispiel: Unter der Annahme, daß die vorige Zelle die Nummer 2\n", "# hat, kann man ihren Inhalt so in ein File schreiben:\n", "write_code(_ih[2],'ein_beispiel')" ] }, { "cell_type": "code", "execution_count": 4, "id": "2a2024c5", "metadata": {}, "outputs": [], "source": [ "# Noch ein Beispiel: Wir können die zuvor definierte Funktion\n", "# write_function() als String in ein File schreiben:\n", "write_function(write_function)" ] }, { "cell_type": "markdown", "id": "7cc7bfd6", "metadata": {}, "source": [ "# Kapitel 1: Graph(ik)en, Permutationen und erzeugende Funktionen\n", "\n", "## Permutationen\n", "\n", "Permutationen sind hier einfach als (geordnete) Listen (oder Tupel) der ersten n Zahlen {1,2,...,n} dargestellt. Alle Funktionen gehen davon aus, daß die entsprechenden Argumente \"in diesem Sinn richtige\" Permutationen sind und prüfen dies _nicht_ eigens nach: Eine \"praxistaugliche\" Version sollte auf eine solche Prüfung nicht verzichten, aber für unsere Zwecke ist das nicht erforderlich.\n", "\n", "### Aufgabe 5" ] }, { "cell_type": "code", "execution_count": 1, "id": "d44b1cf2", "metadata": {}, "outputs": [], "source": [ "def doppel_faktorielle(n):\n", " \"\"\"Berechne die \"Doppelfaktorielle\" n!! _rekursiv_:\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 6, "id": "df298ed4", "metadata": {}, "outputs": [], "source": [ "# Funktion in ein kleines Python-File schreiben\n", "# (das dann ins Moodle geladen werden sollte):\n", "write_function(doppel_faktorielle)" ] }, { "cell_type": "code", "execution_count": 2, "id": "e5dbadcc", "metadata": {}, "outputs": [], "source": [ "def fibonacci(n):\n", " \"\"\"Berechne die n-te Fibonacci-Zahl _rekursiv_:\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 8, "id": "228c897e", "metadata": {}, "outputs": [], "source": [ "# Funktion in ein kleines Python-File schreiben\n", "# (das dann ins Moodle geladen werden sollte):\n", "write_function(fibonacci)" ] }, { "cell_type": "code", "execution_count": 3, "id": "25791b02", "metadata": {}, "outputs": [], "source": [ "def fibonorial(n):\n", " \"\"\"Berechne die \"Fibonacci-Faktoriellen\" n_F! _rekursiv_:\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 10, "id": "9c609c2c", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(fibonorial)" ] }, { "cell_type": "markdown", "id": "c37ee352", "metadata": {}, "source": [ "### Aufgabe 10\n", "\n", "#### Hilfsfunktion aus dem Skriptum:" ] }, { "cell_type": "code", "execution_count": 30, "id": "6e565494", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[3, 1, 2]" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def perm_mul(sigma, tau):\n", " \"\"\"Berechne die Permutation sigma(tau), dargestellt als _Listen_\n", " (d.h.: in Einzeilen-Notation)\"\"\"\n", " # Permutationen sind als _Listen_ dargestellt; die Indizierung\n", " # von Listen beginnt bei 0 (nicht bei 1!):\n", " return [sigma[tau_i-1] for tau_i in tau]\n", "\n", "# Anwendung dieser Funktion:\n", "perm_mul([2,1,3],[3,2,1])" ] }, { "cell_type": "code", "execution_count": 31, "id": "fd36e787", "metadata": {}, "outputs": [], "source": [ "# Verwenden Sie für die Aufgabe die folgende \"Übersetzungstabelle\",\n", "# die den Permutationen der S_4 einen Buchstaben mit Subskript zuordnet:\n", "# itertools.permutations liefert _Tupel_ (keine Listen), die können\n", "# also direkt als \"keys\" (Schlüsselbegriffe) in einem Dictionary\n", "# verwendet werden, das wir mit zip und list comprehension ganz\n", "# schnell erzeugen können:\n", "# Liste der Permutationen von [1,2,3,4]:\n", "permutationen = [pi for pi in itertools.permutations([1,2,3,4])]\n", "# Liste von 24=4! Bezeichnungen dieser Permutationen\n", "bezeichnungen = [f's{i}' for i in range(1,1*2*3*4+1)]\n", "# Übersetzungstabelle \"Permutation->Label\":\n", "pi2label = dict(zip(permutationen, bezeichnungen))\n", "# Umgekehrte Übersetzungstabelle \"Label->Permutation\":\n", "label2pi = dict(zip(bezeichnungen, permutationen))" ] }, { "cell_type": "code", "execution_count": 32, "id": "60470445", "metadata": {}, "outputs": [], "source": [ "# Diese \"Übersetzungstabellen\" kann man wie folgt verwenden:\n", "def mul_perm(label1, label2):\n", " pi1 = label2pi[label1]\n", " pi2 = label2pi[label2]\n", " # Achtung: perm_mul liefert eine _Liste_ - um als \"key\" in\n", " # einem dictionary zu funktionieren, muß die Liste in ein\n", " # _Tupel_ umgewandelt werden:\n", " produkt = tuple(perm_mul(pi1, pi2))\n", " \n", " produkt_label = pi2label[produkt]\n", " \n", " print(f'{label1} mal {label2} = {produkt_label} (also {pi1} mal {pi2} = {produkt})')" ] }, { "cell_type": "code", "execution_count": 33, "id": "677f4364", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "s12 mal s13 = s16 (also (2, 4, 3, 1) mal (3, 1, 2, 4) = (3, 2, 4, 1))\n" ] } ], "source": [ "mul_perm('s12','s13')" ] }, { "cell_type": "markdown", "id": "a371f17e-1430-47f5-ab8d-dd052b1fe548", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 34, "id": "5f191904", "metadata": {}, "outputs": [], "source": [ "def mult_tab_S4():\n", " \"\"\"Gib die Multiplikationstabelle der S_4 aus.\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None\n", " # Diese Funktion muß kein Ergebnis zurückgeben" ] }, { "cell_type": "code", "execution_count": 35, "id": "149a7025", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(mult_tab_S4)" ] }, { "cell_type": "markdown", "id": "10d8be99", "metadata": {}, "source": [ "### Aufgabe 11" ] }, { "cell_type": "code", "execution_count": 4, "id": "9aa4b71b", "metadata": {}, "outputs": [], "source": [ "def count_inversions(pi):\n", " \"\"\"Bestimme die Anzahl der Inversionen der Permutation pi (als\n", " Liste oder Tupel dargestellt).\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 48, "id": "867bf9dd", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(count_inversions)" ] }, { "cell_type": "markdown", "id": "c4967ee9", "metadata": {}, "source": [ "### Aufgabe 14\n", "\n", "##### Hilfsfunktion aus dem Skriptum:" ] }, { "cell_type": "code", "execution_count": 45, "id": "86b0ddcf", "metadata": {}, "outputs": [], "source": [ "def cycle_decomposition(pi):\n", " \"\"\"Bestimme die (nicht-kanonische) Zyklenzerlegung einer Permutation\"\"\"\n", " n = len(pi)\n", " # \"Buchführung\": Liste der Elemente (MINUS 1), die noch nicht auf\n", " # Zyklen \"verteilt\" wurden.\n", " yet_to_consider = list(range(n))\n", " # Rückgabewert: Liste von Zyklen (Listen); anfangs leer\n", " list_of_cycles = []\n", " while len(yet_to_consider):\n", " # Erstes noch zu verteilendes Element (MINUS 1) ...\n", " i = yet_to_consider[0]\n", " # ... eröffnet einen neuen Zyklus:\n", " new_cycle = [i+1]\n", " # Dieses Element wird von der Liste der noch zu verteilenden\n", " # Elemente gestrichen:\n", " yet_to_consider = yet_to_consider[1:]\n", " # Nun wird der neue Zyklus zusammengestellt:\n", " while True:\n", " pi_i = pi[i]\n", " # Abbruchbedingung: Wenn wir wieder am Anfang des Zyklus'\n", " # angekommen sind, ist der Zyklus fertig zusammengestellt\n", " # und wird in die Liste der Zyklen aufgenommen.\n", " if pi_i == new_cycle[0]:\n", " list_of_cycles += [new_cycle]\n", " break\n", " \n", " # Ansonsten: Weitermachen! Der Zyklus wird um pi_i \"verlängert\" ...\n", " new_cycle+= [pi_i]\n", " # und der pi_i entsprechende Index wird aus der Liste der noch\n", " # zu behandelnden Elemente entfernt ...\n", " yet_to_consider.remove(pi_i - 1)\n", " # ... und wir machen weiter ...\n", " i = pi_i - 1\n", " return list_of_cycles" ] }, { "cell_type": "markdown", "id": "00605f33-e02f-4d24-97d8-72fafc77260c", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 5, "id": "60eeef78", "metadata": {}, "outputs": [], "source": [ "def sign_by_definition(pi):\n", " \"\"\"Berechne das Signum der Permutation pi gemäß Definition.\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 6, "id": "9d0dd866", "metadata": {}, "outputs": [], "source": [ "def sign_by_inversions(pi):\n", " \"\"\"Berechne das Signum der Permutation pi durch Berechnung\n", " der Inversionen.\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 7, "id": "63de635d", "metadata": {}, "outputs": [], "source": [ "def sign_by_cycle_decomposition(pi):\n", " \"\"\"Berechne das Signum der Permutation pi durch Bestimmung\n", " der Zyklenzerlegung.\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 53, "id": "a9ddb825", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "# Kleine for-Schleife:\n", "for function in [sign_by_definition, sign_by_inversions, sign_by_cycle_decomposition]:\n", " write_function(function)" ] }, { "cell_type": "markdown", "id": "d1f89396", "metadata": {}, "source": [ "Laufzeitvergleich mit %timeit:" ] }, { "cell_type": "code", "execution_count": 54, "id": "fbc104e1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100000 loops, best of 3: 2.86 µs per loop\n" ] } ], "source": [ "%timeit sign_by_definition([5,3,4,1,2,6])" ] }, { "cell_type": "code", "execution_count": 55, "id": "fd843de3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100000 loops, best of 3: 2.3 µs per loop\n" ] } ], "source": [ "%timeit sign_by_inversions([5,3,4,1,2,6])" ] }, { "cell_type": "code", "execution_count": 56, "id": "7a162ba6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "100000 loops, best of 3: 1.97 µs per loop\n" ] } ], "source": [ "%timeit sign_by_cycle_decomposition([5,3,4,1,2,6])" ] }, { "cell_type": "markdown", "id": "77b50118", "metadata": {}, "source": [ "## Abzählung und erzeugende Funktionen\n", "\n", "### Aufgabe 23" ] }, { "cell_type": "code", "execution_count": 8, "id": "05ac90c4", "metadata": {}, "outputs": [], "source": [ "def check_identities():\n", " \"\"\"Prüfe die Identitäten aus Aufgabe 24 \"empirisch\" nach:\n", " Die Funktion \"binom()\" wurde zu Beginn bereits aus \"scipy.special\"\n", " importiert; alternativ kann man auch die Version aus Moduel\n", " \"math\" verwenden:\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Naheliegend wäre hier eine doppelte Schleife, oder \n", " # geeignete Iteratoren aus Modul \"itertools\" ...\n", " \n", " # Diese Funktion muß kein Ergebnis zurückgeben:\n", " # return None\n", "\n", "check_identities()" ] }, { "cell_type": "code", "execution_count": null, "id": "3afd3278", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(check_identities)" ] }, { "cell_type": "markdown", "id": "cabbc914", "metadata": {}, "source": [ "## Elementares Abzählen\n", "\n", "### Aufgabe 36" ] }, { "cell_type": "code", "execution_count": 9, "id": "6c0f5fa4", "metadata": {}, "outputs": [], "source": [ "def evaluate36(n):\n", " \"\"\"Evaluiere die Summe aus Aufgabe 36: Verwenden Sie aber\n", " _nicht_ die \"normale\" Division von float-Zahlen (a/b), und\n", " schon gar nicht die ganzzahlige Division von int-Zahlen (a//b),\n", " sondern die sympy-Funktion Rational(a,b), die rationale Zahlen\n", " liefert - dann sehen Sie schneller die richtige Vermutung!\"\"\"\n", " # Bitte Code einfügen!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 60, "id": "eee67a6f", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(evaluate36)" ] }, { "cell_type": "markdown", "id": "3a5e8d94", "metadata": {}, "source": [ "Lassen Sie sich die Rechenergebnisse in einer Liste anzeigen, dann haben Sie sicher gleich die richtige Vermutung:" ] }, { "cell_type": "code", "execution_count": 10, "id": "10504ab3", "metadata": {}, "outputs": [], "source": [ "# Die ermittelten Ergebnisse für 0 bis 10 in Form einer Liste:\n", "[evaluate36(n) for n in range(11)]" ] }, { "cell_type": "markdown", "id": "fe9d0b87", "metadata": {}, "source": [ "### Aufgabe 39\n", "\n", "#### Vorbereitung: Stirling-Zahlen\n", "\n", "Sie können die folgende Funktion für die rekursive Bestimmung der Stirling-Zahlen 2. Art verwenden ..." ] }, { "cell_type": "code", "execution_count": 14, "id": "6fd52c71", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 \n", "0 1 \n", "0 1 1 \n", "0 1 3 1 \n", "0 1 7 6 1 \n", "0 1 15 25 10 1 \n" ] } ], "source": [ "def stirling2(n,k):\n", " \"\"\"Stirling-Zahlen der 2. Art\"\"\"\n", " if k < 0 or k > n:\n", " return 0\n", " # Impicit else:\n", " if k == 0:\n", " return 1 if n == 0 else 0\n", " # Implicit else:\n", " if k == 1 or k == n:\n", " return 1\n", " # Implicit else:\n", " if k == 2:\n", " return 2**(n-1) - 1\n", " if k == n-1:\n", " return sp.binomial(n,2)\n", " # Implicit else: Die Rekursion für diese Zahlen.\n", " return stirling2(n-1,k-1)+k*stirling2(n-1,k)\n", "\n", "for n in range(6):\n", " for k in range(n+1):\n", " print(stirling2(n,k), end=\" \")\n", " print(\"\")" ] }, { "cell_type": "markdown", "id": "0b28627e", "metadata": {}, "source": [ "... oder einfach die in sympy zur Verfügung gestellte Funktion:" ] }, { "cell_type": "code", "execution_count": 20, "id": "b91b03c3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 \n", "0 1 \n", "0 1 1 \n", "0 1 3 1 \n", "0 1 7 6 1 \n", "0 1 15 25 10 1 \n" ] } ], "source": [ "for n in range(6):\n", " for k in range(n+1):\n", " print(sp.functions.combinatorial.numbers.stirling(n,k, kind=2), end=\" \")\n", " print(\"\")" ] }, { "cell_type": "code", "execution_count": 26, "id": "7d7bd6c8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 \n", "0 1 \n", "0 1 1 \n", "0 2 3 1 \n", "0 6 11 6 1 \n", "0 24 50 35 10 1 \n" ] } ], "source": [ "# Nur als ergänzende Illustration zum Thema Rekursionen: Hier auch\n", "# die _vorzeichenlosen_ Stirling-Zahlen erster Art\n", "def stirling1(n,k):\n", " \"\"\"Stirling-Zahlen der 1. Art\"\"\"\n", " if k < 0 or k > n:\n", " return 0\n", " # Impicit else:\n", " if k == 0:\n", " return 1 if n == 0 else 0\n", " # Implicit else:\n", " if k == n:\n", " return 1\n", " if k == 1:\n", " return sp.factorial(n-1)\n", " # Implicit else: Die Rekursion für diese Zahlen.\n", " return stirling1(n-1,k-1)+(n-1)*stirling1(n-1,k)\n", "\n", "for n in range(6):\n", " for k in range(n+1):\n", " print(stirling1(n,k), end=\" \")\n", " print(\"\")" ] }, { "cell_type": "markdown", "id": "9e05120a", "metadata": {}, "source": [ "#### Eigentliche Aufgabe\n", "\n", "Verwenden Sie einfach die Identitäten aus dem Skriptum. Achten Sie auf den Unterschied zwischen steigenden und fallenden Faktoriellen und verwenden Sie den Zusammenhang\n", "\n", "$$\n", "x^{\\overline k} = (-1)^k (-x)^{\\underline k}\n", "$$" ] }, { "cell_type": "code", "execution_count": 24, "id": "de70db63", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "x^0 = 1: True\n", "x^1 = x: True\n", "x^2 = x*(x + 1) - x: True\n", "x^3 = x*(x + 1)*(x + 2) - 3*x*(x + 1) + x: True\n", "x^4 = x*(x + 1)*(x + 2)*(x + 3) - 6*x*(x + 1)*(x + 2) + 7*x*(x + 1) - x: True\n", "x^5 = x*(x + 1)*(x + 2)*(x + 3)*(x + 4) - 10*x*(x + 1)*(x + 2)*(x + 3) + 25*x*(x + 1)*(x + 2) - 15*x*(x + 1) + x: True\n" ] } ], "source": [ "# Sie können für die sympy-Funktionen kürzere Namen vergeben\n", "# (nur zur Bequemlichkeit, notwendig ist das nicht):\n", "rising_factorial = sp.functions.combinatorial.factorials.RisingFactorial\n", "stirling2 = sp.functions.combinatorial.numbers.stirling # Der Default-Wert für \"kind\" ist 2\n", "# Eine sympy-Variable:\n", "var_x = sp.symbols('x')\n", "def power_expansion(n):\n", " \"\"\"Entwicklung von x^n in der Basis der steigenden Faktoriellen\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None\n", "\n", "# Testen Sie Ihr Ergebnis:\n", "for n in range(6):\n", " print(f'x^{n} = {power_expansion(n)}: {sp.factor(power_expansion(n))==var_x**n}')" ] }, { "cell_type": "code", "execution_count": null, "id": "89ef0d6c", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(power_expansion)" ] }, { "cell_type": "markdown", "id": "0b24818f", "metadata": {}, "source": [ "### Aufgabe 40" ] }, { "cell_type": "code", "execution_count": 12, "id": "abfaada9", "metadata": {}, "outputs": [], "source": [ "# Eine sympy-Variable:\n", "var_m = sp.symbols('m')\n", "def power_sum_formula(n):\n", " \"\"\"Formel für sum_{k=1}^m k^n als Polynom in m\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "119e5864", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(power_sum_formula)" ] }, { "cell_type": "markdown", "id": "b961088f", "metadata": {}, "source": [ "NICHT VERGESSEN: Für diese Aufgabe ist auch \"mathematisch\" noch etwas zu tun!" ] }, { "cell_type": "markdown", "id": "1a7b02ed", "metadata": {}, "source": [ "#### f-Strings und r-Strings, Ausgabe in LaTeX\n", "\n", "Nur als kleine Ergänzung gedacht - das muß man _natürlich nicht_ alles gleich beherrschen!" ] }, { "cell_type": "code", "execution_count": null, "id": "7197eed7", "metadata": {}, "outputs": [], "source": [ "# Ausgabe im LaTeX-Format:\n", "# Da der Backslash \"\\\" in Strings normalerweise ein \"Escape-Symbol\"\n", "# ist (z.B. bedeutet \"\\n\" \"newline\", oder \"\\t\" \"tab\"), müssen wir\n", "# einen _doppelten_ Backslash \"\\\\\" schreiben, wenn wir in der\n", "# Ausgabe tatsächlich einen Backslash _sehen_ wollen:\n", "print(\"\\\\begin{align}\")\n", "for n in range(6):\n", " # Der Buchstabe \"r\" vor dem String bewirkt, daß wir Backslashes\n", " # \"einfach\" schreiben können statt \"doppelt\" (\"\\\" statt \"\\\\\");\n", " # die geschwungenen Klammern, die im ausgegebenene String\n", " # _erscheinen_ sollen, müssen wir aber innerhalb des f-Strings\n", " # \"verdoppeln\" (\"{{}}\" statt \"{}\"):\n", " print(fr'\\sum_{{x=1}}^m x^n &= {sp.latex(power_sum_formula(n))} \\\\')\n", "print(\"\\\\end{align}\")" ] }, { "cell_type": "markdown", "id": "4f0a9780", "metadata": {}, "source": [ "# Algorithmen\n", "\n", "## Einfache Beispiele\n", "\n", "### Aufgabe 45\n", "\n", "Die Programmbibliothek numpy stellt viele wichtige Funktionen zur Verfügung, insbesondere einfache Addition und Skalarmultiplikation für Vektoren, z.B.:" ] }, { "cell_type": "code", "execution_count": 49, "id": "1158c4d5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([10, 14])" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Zwei Vektoren mit vorgegebenem Datentyp int:\n", "vector1 = np.array([1,2], dtype=int)\n", "vector2 = np.array([3,4], dtype=int)\n", "vector1 + 3*vector2" ] }, { "cell_type": "markdown", "id": "53fa3eca", "metadata": {}, "source": [ "Versuchen Sie, die Zahlen d, a und b in _jedem Schritt_\n", "$$ d = a - q\\cdot b$$\n", "des Euklidischen Algorithmus immer auch als Linearkombinationen der Anfangswerte a und b zu schreiben ..." ] }, { "cell_type": "code", "execution_count": 13, "id": "f237fa6f", "metadata": {}, "outputs": [], "source": [ "def gcd_enhanced(a,b):\n", " \"\"\"Euklidischer Algorithmus zur Bestimmung des größten\n", " gemeinsamen Teilers der (ganzen) Zahlen a und b.\"\"\"\n", " # Es sollte a > b > 0 gelten: Wir korrigieren\n", " # \"fehlerhafte\" Eingaben, falls erforderlich.\n", " if a == 0:\n", " return b\n", " if b == 0:\n", " return a\n", " if a < 0:\n", " a = -a\n", " if b < 0:\n", " b = -b\n", " if a < b:\n", " dummy = a\n", " a = b\n", " b = dummy\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 51, "id": "805239bb", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(gcd_enhanced)" ] }, { "cell_type": "markdown", "id": "ee1da9e4", "metadata": {}, "source": [ "## Das Travelling Salesperson Problem\n", "\n", "### Aufgabe 46" ] }, { "cell_type": "code", "execution_count": 14, "id": "0206f9d6", "metadata": {}, "outputs": [], "source": [ "def tsp(weights):\n", " \"\"\"Mathematisch richtige (aber praktisch nur für kleine Zahlen brauchbare)\n", " Lösung des Travelling Salesperson Problems.\"\"\"\n", " n,m = weights.shape\n", " if n != m:\n", " print(\"Die Matrix der Gewichte sollte quadratisch sein!\")\n", " return None\n", " # Die Matrix weights sollte außerdem reell und symmetrisch sein,\n", " # und lauter positive Einträge haben - aber das prüfen wir jetzt\n", " # nicht nach:\n", " \n", " # Wir beginnen mit einer \"sicher zu großen\" Zahl:\n", " the_minimum = np.sum(weights)\n", " the_solution = list(range(n))\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " # Liste der minimalen \"Rundreise\", beginnend (und endend) im Knoten 0\n", " # Kosten dieser Rundreise:\n", " return the_solution, the_minimum" ] }, { "cell_type": "code", "execution_count": 70, "id": "28339bbc", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(tsp)" ] }, { "cell_type": "markdown", "id": "eccc3ca7", "metadata": {}, "source": [ "### Aufgabe 47" ] }, { "cell_type": "code", "execution_count": 121, "id": "859782ae", "metadata": {}, "outputs": [], "source": [ "def strassen(A,B):\n", " \"\"\"A und B sollten zwei quadratische Matrizen der Dimension 2^m sein.\"\"\"\n", " m,n = A.shape\n", " # Für Dimension 0 ist das ja nur eine Skalarmultiplikation:\n", " if n == 1:\n", " return A[0,0]*B[0,0]\n", " # Implicit else:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:" ] }, { "cell_type": "code", "execution_count": null, "id": "abf2ccff", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(strassen)" ] }, { "cell_type": "markdown", "id": "8d2cc6be", "metadata": {}, "source": [ "## Algorithmische Erzeugung kombinatorischer Objekte\n", "\n", "### Aufgabe 49\n", "\n", "Um die Aufgabe vollständig zu lösen, sollten Sie für ein Argument mu (lambda ist ein keyword in Python und sollte daher lieber nicht als Variablenname verwendet werden) prüfen, ob\n", "\n", "* mu ein Tupel ist: isinstance(mu, tuple)\n", "* mu ein Tupel von ganzen Zahlen (int) ist: all(isinstance(mu_i,int) for mu_i in mu)\n", "* mu ein _absteigend geordnetes_ Tupel ganzer Zahlen ist: tuple(sorted(mu, reverse=True)) == mu\n", "* mu nur positive ganze Zahlen enthält: mu[-1] > 0\n", "\n", "(die Reihenfolge dieser Tests ist _nicht zufällig_ gewählt;-)." ] }, { "cell_type": "code", "execution_count": 147, "id": "2a20b34d", "metadata": {}, "outputs": [], "source": [ "def check_partition(mu):\n", " \"\"\"Prüfe ob mu ein Tupel ist, das einer Zahl-Partition entspricht\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "10ee5e41", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(check_partition)" ] }, { "cell_type": "markdown", "id": "714bcc5a", "metadata": {}, "source": [ "### Aufgabe 50" ] }, { "cell_type": "code", "execution_count": 152, "id": "7f18498c", "metadata": {}, "outputs": [], "source": [ "def gray_code(n):\n", " \"\"\"Konstruiere _rekursiv_ einen n-stelligen (klassischen) Gray-Code\n", " (als Liste von Listen)\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:" ] }, { "cell_type": "code", "execution_count": null, "id": "06c04d66", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(gray_code)" ] }, { "cell_type": "markdown", "id": "367143cc", "metadata": {}, "source": [ "### Aufgabe 52\n", "\n", "\"Reverse engineering\": Versuche, aus dem gegebenen Programmcode den zugrundeliegenden Algorithmus zu erkennen (die Kommentare sollten dabei helfen - so sind sie jedenfalls gedacht;-).\n", "\n", "Die Funktion numpy.nonzero(v) gibt _im wesentlichen_ das array der _Positionen_ ungleich Null im array v zurück; aber für jede \"Dimension\" von v extra - also ein _Tupel_ von \"Positions-arrays\". Ein _Vektor_ v hat Dimension 1, also liefert numpy.nonzero(v)[0] das array der Positionen ungleich Null im Vektor v. Siehe auch\n", "\n", " https://numpy.org/doc/stable/reference/generated/numpy.nonzero.html" ] }, { "cell_type": "code", "execution_count": 156, "id": "f82a4fc6", "metadata": {}, "outputs": [], "source": [ "# Die Funktion aus dem Skriptume:\n", "def product_gray_code(the_maxima):\n", " \"\"\"Erzeuge Gray-Code des cartesischen Produkts: Diesmal\n", " beginnen wir mit dem Zählen bei Null, betrachten also\n", " {0,...,m_1-1} x {0,...,m_2-1} x ... x {0,...,m_n-1}.\n", " ACHTUNG: Hier muß min(the_maxima) > 1 gelten! (Faktoren der\n", " Mächtigkeit 1 sind ja \"in allen Tupeln konstant\", und\n", " Faktoren der Mächtigkeit 0 ergeben ein leeres Produkt;\n", " das ist also keine starke Einschränkung.)\n", " \"\"\"\n", " if min(the_maxima) <= 1:\n", " # Diesen Fall behandeln wir hier nicht.\n", " print('Wir behandeln nur Produkte von Faktoren S mit |S|>1!')\n", " return\n", " \n", " dim = len(the_maxima)\n", " # Erstes Tupel:\n", " current_tuple = np.zeros(dim, dtype=int)\n", " # Vektor, der die \"Richtungen\" anzeigt, in die\n", " # die Komponenten des Tupels während des Algorithmus\n", " # bewegt werden:\n", " directions = np.ones(dim, dtype=int)\n", " # Vektor, der die \"aktiven\" Koordinaten anzeigt:\n", " active_flags = np.ones(dim, dtype=int)\n", " \n", " finished = False\n", " while not finished:\n", " yield current_tuple\n", " # Die numpy-Funktion nonzero(v) liefert array der Indices\n", " # der Elemente von v, die ungleich Null sind; genauer gesagt:\n", " # Ein _Tupel_ von arrays von Indizes - für jede Dimension\n", " # von v ein Index-Array; unser v is eindimensional, wir brauchen\n", " # also einfach das ERSTE Element (mit Index 0) dieses Tupels:\n", " active_positions = np.nonzero(active_flags)[0]\n", " # Wenn es keine aktiven Koordinaten mehr gibt: Fertig!\n", " if len(active_positions) == 0:\n", " return\n", " # Die größte aktive Koordinate wird in die entsprechende\n", " # Richtung (+/- 1) verändert:\n", " pos = np.max(active_positions)\n", " current_tuple[pos] += directions[pos]\n", " # Wenn wir an die \"oberen/unteren Grenzen\" gestoßen sind,\n", " # kehren wir die Richtung um und setzen die Koordinate auf\n", " # \"nicht aktiv\":\n", " if current_tuple[pos] == 0 or current_tuple[pos] == the_maxima[pos] - 1:\n", " directions[pos] = -directions[pos]\n", " active_flags[pos] = 0\n", " # Setze alle active-flags ab pos+1 auf 1: Die entsprechenden\n", " # Koordinaten können im nächsten Schleifen-Durchlauf verändert\n", " # werden. - Zuweisung einer Zahl zu numpy-array-slice ist möglich!\n", " active_flags[pos+1:] = 1" ] }, { "cell_type": "code", "execution_count": 158, "id": "8bb168d9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0 0 0]\n", "[0 0 1]\n", "[0 0 2]\n", "[0 0 3]\n", "[0 1 3]\n", "[0 1 2]\n", "[0 1 1]\n", "[0 1 0]\n", "[0 2 0]\n", "[0 2 1]\n", "[0 2 2]\n", "[0 2 3]\n", "[1 2 3]\n", "[1 2 2]\n", "[1 2 1]\n", "[1 2 0]\n", "[1 1 0]\n", "[1 1 1]\n", "[1 1 2]\n", "[1 1 3]\n", "[1 0 3]\n", "[1 0 2]\n", "[1 0 1]\n", "[1 0 0]\n" ] } ], "source": [ "# Schauen Sie sich an, was die Funktion liefert:\n", "for gc in product_gray_code([2,3,4]):\n", " print(gc)" ] }, { "cell_type": "markdown", "id": "92b3d3c0", "metadata": {}, "source": [ "### Aufgabe 54\n", "\n", "Überlegen Sie als erstes, wie Sie _alle_ Teilmengen von {1,2,...n} einfach codieren können; oder verwenden Sie itertools.combinations(). Das Produkt über alle Elemente eines Tupels (oder einer Liste) \"das_tupel\" erhalten Sie mit np.prod(das_tupel)." ] }, { "cell_type": "code", "execution_count": 22, "id": "c025ef63", "metadata": {}, "outputs": [], "source": [ "def sum_of_products(n):\n", " \"\"\"Summe über alle Produkte der Elemente aller Teilmengen von {1,2,...,n}.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:" ] }, { "cell_type": "code", "execution_count": null, "id": "bd715a53", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(sum_of_products)" ] }, { "cell_type": "markdown", "id": "4baaac35", "metadata": {}, "source": [ "### Aufgabe 56" ] }, { "cell_type": "code", "execution_count": 15, "id": "6772ed80", "metadata": {}, "outputs": [], "source": [ "def as_factorial_sum(m, n):\n", " \"\"\"Hilfsfunktion: Stelle die Zahl 0 <= m < n! dar als eine Summe c_k k!\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 177, "id": "a8f956bc", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(as_factorial_sum)" ] }, { "cell_type": "markdown", "id": "c3d7104e", "metadata": {}, "source": [ "### Aufgabe 57" ] }, { "cell_type": "code", "execution_count": 184, "id": "05633cc3", "metadata": {}, "outputs": [], "source": [ "# Der \"generische\" rank/unrank-Test aus der Vorlesung\n", "def generic_rank_unrank_test(description, rank_func, unrank_func, cardinality):\n", " \"\"\"Ein einfacher (aber gründlicher;-) _generischer_ Test,\n", " ob das Ranking/Unranking richtig funktioniert: description ist eine\n", " Variable, die den Ranking/Unranking-Funktioen rank_func und unrank_funk\n", " übergeben wird, und cardinality ist der Anzahl der erzeugten Objekte.\"\"\"\n", " # Schleife über alle Zahlen, die als Rang eines description-Objekts\n", " # auftreten (sollen):\n", " for i in range(cardinality):\n", " # Es müßte \"rank o unrank = identität\" gelten - wenn nicht, geben\n", " # wir eine Fehlermeldung aus:\n", " if i != rank_func(unrank_func(i,description),description):\n", " print(f'Oops: Fehler für {description} bei Nummer {i}!')\n", " return False\n", " \n", " print(f'Alles bestens: (rank o unrank) = identity gilt für {description}!')\n", " return True" ] }, { "cell_type": "markdown", "id": "f4ac7473", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe:" ] }, { "cell_type": "code", "execution_count": 16, "id": "b1c6c2c0", "metadata": {}, "outputs": [], "source": [ "def unrank_perm_lex(m, n):\n", " \"\"\"Bestimme die m-te Permutation von {1,2,...,n} in _lexikographischer\n", " Ordnung_, wobei die Numerierung bei 0 beginnt\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "bb52a462", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(unrank_perm_lex)" ] }, { "cell_type": "markdown", "id": "8b42c755", "metadata": {}, "source": [ "Für die Rank-Funktion ist vielleicht folgende Hilfsfunktion nützlich (Sie können das aber natürlich auch anders implementieren!):" ] }, { "cell_type": "code", "execution_count": 183, "id": "dbd6ac6d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "execution_count": 183, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def count_less_than_first(pi):\n", " \"\"\"Hilfsfunktion: Liefert Anzahl der Elemente der Liste pi,\n", " die echt kleiner sind als ihr erstes Element\"\"\"\n", " return sum([1 if pi_i < pi[0] else 0 for pi_i in pi[1:]])\n", "\n", "count_less_than_first([1,5,3,4])" ] }, { "cell_type": "code", "execution_count": 187, "id": "438434ac", "metadata": {}, "outputs": [], "source": [ "# Die Variable n ist hier an sich überflüssig, aber sie ist für\n", "# den \"generischen rank/unrank-Test\" notwendig:\n", "def rank_perm_lex(pi,n):\n", " \"\"\"Ranking einer Permutation pi (in bezug auf die lexikographische Ordnung)\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:" ] }, { "cell_type": "code", "execution_count": null, "id": "33b33af0", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(rank_perm_lex)" ] }, { "cell_type": "code", "execution_count": 188, "id": "de5290c6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Alles bestens: (rank o unrank) = identity gilt für 5!\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 188, "metadata": {}, "output_type": "execute_result" } ], "source": [ "generic_rank_unrank_test(5, rank_perm_lex, unrank_perm_lex, 120)" ] }, { "cell_type": "markdown", "id": "1a2b2233", "metadata": {}, "source": [ "### Aufgabe 59\n", "\n", "Am elegantesten gelingt der erste Teil der Aufgabe, wenn Sie die Permutation, die erzeugt werden soll, als numpy-Array definieren und in den richtigen Momenten\n", "\n", "* die numpy-Funktion roll() (if everything fails, read the instructions!)\n", "* und das \"Slicing\" von Arrays\n", "\n", "verwenden (es geht aber natürlich auch mit Python-Listen)." ] }, { "cell_type": "code", "execution_count": 214, "id": "9a686e94", "metadata": {}, "outputs": [], "source": [ "def inv_word2perm(inv_word):\n", " \"\"\"Bestimme die Permutation, die durch die Inversionsfolge inv_word\n", " gegeben ist.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 225, "id": "73c3e347", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(inv_word2perm)" ] }, { "cell_type": "markdown", "id": "595faea4", "metadata": {}, "source": [ "Für den zweiten Teil der Aufgabe verwenden Sie am besten itertools.product zur Erzeugung der Inversionsfolgen. Einen \"Generator\" erhalten Sie (sehr einfach gesagt), indem Sie den return-Befehl durch den yield-Befehl ersetzen." ] }, { "cell_type": "code", "execution_count": 17, "id": "8553c1c9", "metadata": {}, "outputs": [], "source": [ "def generate_permutations(n):\n", " \"\"\"Erzeuge die Permutation von {1,2,...,n} in der durch ihre\n", " lexikographisch geordneten Inversionsfolge bestimmten Reihenfolge.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 226, "id": "f1fb86ca", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(generate_permutations)" ] }, { "cell_type": "markdown", "id": "40fd4f74", "metadata": {}, "source": [ "### Aufgabe 60" ] }, { "cell_type": "code", "execution_count": 229, "id": "a0280443", "metadata": {}, "outputs": [], "source": [ "# Eine kleine Hilfsfunktion\n", "def starts_with_two_ascents(pi):\n", " \"\"\"Test: Gilt für die Liste pi pi[0] < pi[1] < pi[2]? \"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "004e5af4", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(starts_with_two_ascents)" ] }, { "cell_type": "code", "execution_count": 227, "id": "7947835d", "metadata": {}, "outputs": [], "source": [ "def monte_carlo_permutations(n, sample_size, test_permutation):\n", " \"\"\"Erzeuge zufällig sample_size Permutationen von {1,2,...,n}\n", " und liefere die relative Häufigkeit der Permutationen, für die\n", " die Testfunktion test_permutation den Wert True liefert.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "1ed3052f", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(monte_carlo_permutations)" ] }, { "cell_type": "code", "execution_count": 233, "id": "a5741c09", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "MC-simulation: Generate 100000 random permutations\n", "of 10 elements (10! = 3628800) and count for how many\n", "of them the function \"starts_with_two_ascents\" returns True:\n" ] }, { "data": { "text/plain": [ "0.16743" ] }, "execution_count": 233, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Beispiel eines Experiments:\n", "monte_carlo_permutations(10, 100000, starts_with_two_ascents)" ] }, { "cell_type": "markdown", "id": "9fe146dd", "metadata": {}, "source": [ "### Aufgabe 61\n", "\n", "#### Vorbereitungen" ] }, { "cell_type": "code", "execution_count": 236, "id": "06edc34d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Folge mit Startwert 1, Endwert (exklusive) 2 und Schrittweite 0.1: [1. 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9]\n" ] }, { "data": { "text/plain": [ "array([1, 2, 3, 4, 5, 6, 7, 8, 9])" ] }, "execution_count": 236, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Die numpy-Funktion arange erzeugt eine arithmetische Folge von Zahlen;\n", "# z.B. allgemein\n", "print(f'Folge mit Startwert 1, Endwert (exklusive) 2 und Schrittweite 0.1: {np.arange(1,2,0.1)}')\n", "# oder einfacher (Default-Schrittweite 1):\n", "np.arange(1,10, dtype=int)" ] }, { "cell_type": "code", "execution_count": 252, "id": "6829f624", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Auf die Elemente einer Menge kann man nicht per Index zugreifen!\n", "{1, 2, 3}\n" ] } ], "source": [ "# Der Befehl \"set\" erzeugt eine _Menge_ aus einer Liste oder einem Tupel:\n", "# Eine Menge ist _nicht_ geordnet (man kann also nicht per \"Indizierung\"\n", "# auf Ihre Elemente zugreifen) und enthält _lauter verschiedene_ Elemente.\n", "menge = set([1,2,2,3])\n", "try:\n", " menge[0]\n", "except TypeError:\n", " print('Auf die Elemente einer Menge kann man nicht per Index zugreifen!')\n", "print(menge)" ] }, { "cell_type": "markdown", "id": "e1260117-b1bf-4435-8a71-b1ed8bc0f21f", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 248, "id": "7e8f7457", "metadata": {}, "outputs": [], "source": [ "def test61(pi):\n", " \"\"\"Wir gehen davon aus, daß pi eine Liste oder ein Tupel oder ein\n", " numpy-array ist, das einer Permutation von {1,2,...,n} entspricht\n", " (in Einzeilen-Notation), und testen die Bedingung:\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 253, "id": "9a3e2214", "metadata": {}, "outputs": [], "source": [ "def count61(n):\n", " \"\"\"Zähle \"brute force\", wieviele Permutationen von {1,2,...,n}\n", " die Bedingung erfüllen.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "3f82e23a-4b84-485c-838e-0cb3fc2fab36", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(test61)\n", "write_function(count61)" ] }, { "cell_type": "markdown", "id": "aa501d26", "metadata": {}, "source": [ "## Zahl-Partitionen\n", "\n", "Der Generator für Zahl-Partitionen aus dem Skriptum:" ] }, { "cell_type": "code", "execution_count": 258, "id": "3dc972e3", "metadata": {}, "outputs": [], "source": [ "def integer_partitions(n):\n", " \"\"\"Generator, der einen Iterator liefert, der alle Partitionen von n erzeugt\"\"\"\n", " # Eine Partition von n kann höchstens n Teile haben: Wir bereiten ein\n", " # numpy-array dieser Länge vor, mit Datentyp int\n", " mu = np.zeros(n, dtype=int)\n", " # Die \"kleinste\" Partition (in umgekehrt lexikographischer Ordnung) ist einfach\n", " # gleich [n] (bzw. [n,0,0, ...,0]).\n", " mu[0] = n\n", " nof_parts = 1\n", " while True:\n", " # Der Befehl \"yield\" (statt \"return\") macht aus der Funktion einen Generator:\n", " yield mu[:nof_parts]\n", " # Wenn eine Partition mit 1 beginnt, gibt es keine \"größere\" (in umgekehrt\n", " # lexikographischer Ordnung) mehr:\n", " if mu[0] == 1:\n", " break\n", " # Suche letzten Teil der Partition, der größer als 1 ist:\n", " # Dazu verwenden wir die \"Vektor-Funktionen\" von numpy;\n", " # der Ausdruck \"mu>0\" liefert ein boolean numpy-array\n", " # in dem wir die \"nicht False\"-Einträge abzählen, die\n", " # sind aber intern \"nicht Null\"-Einträge:\n", " nof_greater_one = np.count_nonzero(mu>1)\n", " # Dieser letzte Teil, der größer ist als 1, wird um 1 vermindert ...\n", " new_part = mu[nof_greater_one-1]-1\n", " # ... und der ursprüngliche Teil wird mit den restlichen Einsern\n", " # (sofern vorhanden) zusammengezählt ...\n", " sum_rest = np.sum(mu[nof_greater_one-1:])\n", " # ... aus dieser Summe machen wir \"soviel wie möglich\" Teile new_part (Achtung:\n", " # ganzzahlige Division \"//\" verwenden, sonst ist das Ergebnis Typ float!) ...\n", " nof_new_parts = sum_rest//new_part\n", " # ... der Rest wird hinten als ein neuer Teil angestückelt ...\n", " additional_part = sum_rest - new_part*nof_new_parts\n", " # ... und zwar durch \"Slicing\" (Herausschneiden) eines \"Stückes\" aus mu, dem\n", " # dann ein konstanter Wert zugewiesen wird; zuerst mal die Teile der Größe\n", " # new_part:\n", " alpha = nof_greater_one-1\n", " omega = alpha + nof_new_parts\n", " mu[alpha:omega] = new_part\n", " nof_parts = omega\n", " # Dann der zusätzliche Teil:\n", " if omega < n:\n", " mu[omega] = additional_part\n", " # Wenn der zusätzliche Teil nicht Null ist, erhöht er die Anzahl der Teile:\n", " if additional_part:\n", " nof_parts += 1\n", " # Zuguterletzt: Alles nach dem zusätzlichen Teil wird auf Null gesetzt.\n", " mu[omega+1:] = 0" ] }, { "cell_type": "code", "execution_count": 260, "id": "c53f9660", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[7]\n", "[6 1]\n", "[5 2]\n", "[5 1 1]\n", "[4 3]\n", "[4 2 1]\n", "[4 1 1 1]\n", "[3 3 1]\n", "[3 2 2]\n", "[3 2 1 1]\n", "[3 1 1 1 1]\n", "[2 2 2 1]\n", "[2 2 1 1 1]\n", "[2 1 1 1 1 1]\n", "[1 1 1 1 1 1 1]\n" ] } ], "source": [ "for mu in integer_partitions(7):\n", " print(mu)" ] }, { "cell_type": "markdown", "id": "0f6a6228", "metadata": {}, "source": [ "### Aufgabe 65\n", "\n", "Aus einem numpy-array kann man ganz einfach _auswählen_, wie das folgenden Beispiel zeigt:" ] }, { "cell_type": "code", "execution_count": 265, "id": "128f1ad4", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Die charakteristische Funktion der Elemente > 3 in [0 1 2 3 4 5 6 7 8 9]: [False False False False True True True True True True]\n", "Die Auswahl aller Elemente > 3 in [0 1 2 3 4 5 6 7 8 9]: [4 5 6 7 8 9]\n" ] } ], "source": [ "range10 = np.arange(10,dtype=int)\n", "# Welche Elemente sind größer als 3?\n", "auswahl = range10 > 3\n", "print(f'Die charakteristische Funktion der Elemente > 3 in {range10}: {auswahl}')\n", "print(f'Die Auswahl aller Elemente > 3 in {range10}: {range10[auswahl]}')" ] }, { "cell_type": "code", "execution_count": 266, "id": "8b02096b", "metadata": {}, "outputs": [], "source": [ "def distinct_even_parts(mu):\n", " \"\"\"Teste, ob die _geraden Teile_ einer gegebene Partition mu\n", " (also eines absteigend geordneten numpy-Vektors von positiven\n", " ganzen Zahlen) alle _verschieden_ sind.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "2ed1f1b8", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(distinct_even_parts)" ] }, { "cell_type": "markdown", "id": "7a75f351", "metadata": {}, "source": [ "Die numpy-Funktion bincount zählt die Vielfachheiten in einem Array nichtnegativer ganzer Zahlen, wie das folgende Beispiel zeigt:" ] }, { "cell_type": "code", "execution_count": 272, "id": "f14778e0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Die Vielfachheiten der Teile in [4] sind [0 0 0 0 1].\n", "Die Vielfachheiten der Teile in [3 1] sind [0 1 0 1].\n", "Die Vielfachheiten der Teile in [2 2] sind [0 0 2].\n", "Die Vielfachheiten der Teile in [2 1 1] sind [0 2 1].\n", "Die Vielfachheiten der Teile in [1 1 1 1] sind [0 4].\n" ] } ], "source": [ "for mu in integer_partitions(4):\n", " print(f'Die Vielfachheiten der Teile in {mu} sind {np.bincount(mu)}.')" ] }, { "cell_type": "markdown", "id": "ff0d4b26", "metadata": {}, "source": [ "Der Python-Befehl all, angewendet auf eine Liste, ein Tupel oder ein numpy-Array von Wahrheitswerten, ergibt genau dann True, wenn alle Elemente True sind; sonst False. Beispiel:" ] }, { "cell_type": "code", "execution_count": 284, "id": "d65a7bd6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 284, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all([True,True,True])" ] }, { "cell_type": "code", "execution_count": 285, "id": "766d0c8d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 285, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all([True,0>1,True])" ] }, { "cell_type": "code", "execution_count": 276, "id": "bc3ef131", "metadata": {}, "outputs": [], "source": [ "def part_multiplicity_leq_3(mu):\n", " \"\"\"Teste, ob alle Teile einer gegebene Partition mu\n", " (also eines absteigend geordneten numpy-Vektors von positiven\n", " ganzen Zahlen) Vielfachheit <= 3 haben.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 286, "id": "b5da7cda", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(part_multiplicity_leq_3)" ] }, { "cell_type": "code", "execution_count": 292, "id": "bc8df680", "metadata": {}, "outputs": [], "source": [ "def count65(n):\n", " \"\"\"Zähle alle Zahl-Partitionen von n, die die Bedingungen (a) bzw.\n", " (b) erfüllen.\"\"\"\n", " count_a = 0\n", " count_b = 0\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return count_a, count_b" ] }, { "cell_type": "code", "execution_count": 299, "id": "41e598d0", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(count65)" ] }, { "cell_type": "markdown", "id": "67b9de15", "metadata": {}, "source": [ "### Aufgabe 66" ] }, { "cell_type": "code", "execution_count": 300, "id": "2f60f1be", "metadata": {}, "outputs": [], "source": [ "def nof_parts_odd(mu):\n", " \"\"\"Teste, ob die Anzahl der Teile der Partition ungerade ist.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 301, "id": "6e6b6374", "metadata": {}, "outputs": [], "source": [ "def nof_parts_even(mu):\n", " \"\"\"Teste, ob die Anzahl der Teile der Partition gerade ist.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 305, "id": "84ccf7a9", "metadata": {}, "outputs": [], "source": [ "def all_parts_odd_distinct(mu):\n", " \"\"\"Teste, ob die Partition mu lauter ungerade und paarweise\n", " verschiedene Teile hat.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 303, "id": "60f67e6f", "metadata": {}, "outputs": [], "source": [ "def count66(n):\n", " \"\"\"Zähle alle Zahl-Partitionen von n, die die Bedingungen (a), (b) bzw.\n", " (c) erfüllen.\"\"\"\n", " count_a = 0\n", " count_b = 0\n", " count_c = 0\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return count_a, count_b, count_c" ] }, { "cell_type": "code", "execution_count": 311, "id": "e4e254bc", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "for func in [nof_parts_odd, nof_parts_even, all_parts_odd_distinct, count66]:\n", " write_function(func)" ] }, { "cell_type": "markdown", "id": "84dc5a2d", "metadata": {}, "source": [ "# Rekursionen und Formale Potenzreihen\n", "\n", "## Rekursionen\n", "\n", "### Aufgabe 72\n", "\n", "Es ist hier wahrscheinlich nützlich, die folgende Darstellung der n-ten Fibonacci-Zahl zu verwenden (siehe auch Skriptum):\n", "\n", "$$\n", "F_n = \\left\\lfloor\\frac1{\\sqrt 5}\\cdot\\left(\\frac{1+\\sqrt 5}{2}\\right)^n + \\frac12\\right\\rfloor\n", "$$" ] }, { "cell_type": "code", "execution_count": 321, "id": "ca19b150", "metadata": {}, "outputs": [], "source": [ "# Definiere Konstante:\n", "sqrt5 = np.sqrt(5.0)\n", "golden_ratio = (1+sqrt5)/2\n", "def fibo(n):\n", " \"\"\"n-te Fibonacci-Zahl\"\"\"\n", " return int(np.floor((golden_ratio ** (n)) / sqrt5 + 1/2))" ] }, { "cell_type": "code", "execution_count": 327, "id": "20027efb", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]" ] }, "execution_count": 327, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[fibo(n) for n in range(17)]" ] }, { "cell_type": "code", "execution_count": 330, "id": "82519bf9", "metadata": {}, "outputs": [], "source": [ "def fibo_expansion(m):\n", " \"\"\"Finde die Darstellung der Zahl m>0 als Summe von nicht-\n", " aufeinanderfolgenden Fibonacci-Zahlen\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "a610ee48", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(fibo_expansion)" ] }, { "cell_type": "markdown", "id": "f59356e1", "metadata": {}, "source": [ "### Aufgabe 74\n", "\n", "Es geht um die Rekursion\n", "$$\n", "C_k = \\sum_{j=0}^{k-1} C_j C_{k-1-j}\n", "$$\n", "für $k>0$, mit der Anfangsbedingung $C_0=1$. (Ja, die Catalan-Zahlen kann man auch einfacher berechnen - es geht hier um die schlaue Verwendung der numpy-Funktion inner.)" ] }, { "cell_type": "code", "execution_count": 340, "id": "9e20a103", "metadata": {}, "outputs": [], "source": [ "def catalan_rekursiv(n):\n", " \"\"\"Berechne die Catalan-Zahlen C_0 bis C_n _rekursiv_;\n", " speichere sie in einem numpy-Vektor.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 342, "id": "5a50ec55", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(catalan_rekursiv)" ] }, { "cell_type": "markdown", "id": "0a6721d9", "metadata": {}, "source": [ "### Aufgabe 75\n", "\n", "Bedenken Sie: sympy kann natürlich keine \"Wunder vollbringen\" - die Partialbruchzerlegung ist nur dann leicht, wenn die Nullstellen des Nennerpolynoms leicht gefunden werden können!" ] }, { "cell_type": "code", "execution_count": 348, "id": "294bc3ac", "metadata": {}, "outputs": [], "source": [ "# Definiere eine sympy-Variable:\n", "var_x = sp.symbols('x')\n", "# Ein Polynom ist durch die Folge seiner Koeffizienten eindeutig bestimmt:\n", "def make_polynomial(c):\n", " \"\"\"Hilfsfunktion: Bastle sympy-Polynom in x mit Koeffizientenvektor c.\"\"\"\n", " poly = 0\n", " for n, c_n in enumerate(c):\n", " poly+= c_n*var_x**n\n", " return poly" ] }, { "cell_type": "code", "execution_count": 350, "id": "74282be6", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\displaystyle x^{2} + 2 x + 1$" ], "text/plain": [ "x**2 + 2*x + 1" ] }, "execution_count": 350, "metadata": {}, "output_type": "execute_result" } ], "source": [ "make_polynomial([1,2,1])" ] }, { "cell_type": "code", "execution_count": 351, "id": "34efd76f", "metadata": {}, "outputs": [], "source": [ "def partial_fraction(p,q):\n", " \"\"\"Partialbruchzerlegung von p/q (sympy-Polynome) mit der sympy-Funktion apart()\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "15fbddef", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(partial_fraction)" ] }, { "cell_type": "markdown", "id": "bd267a9b", "metadata": {}, "source": [ "### Aufgabe 87\n", "\n", "Wenn man zwei numpy-Vektoren von Wahrheitswert koordinatenweise mit or verknüpfen will, kann man das am einfachsten so machen:" ] }, { "cell_type": "code", "execution_count": 362, "id": "3f7dc4aa", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([ True, True])" ] }, "execution_count": 362, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.logical_or(np.array([True,False]), np.array([False,True]))" ] }, { "cell_type": "code", "execution_count": 363, "id": "7bf5d4af", "metadata": {}, "outputs": [], "source": [ "def mod_5_1_or_4(mu):\n", " \"\"\"Teste, ob alle Teile der Partition mu kongruent +/1 modulo 5 sind.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 364, "id": "532df993", "metadata": {}, "outputs": [], "source": [ "def no_equal_or_consecutive(mu):\n", " \"\"\"Teste, ob keine zwei Teile der Partition gleich oder aufeinanderfolgend\n", " sind.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 365, "id": "eb4e5971", "metadata": {}, "outputs": [], "source": [ "def count87(n):\n", " \"\"\"Zähle alle Zahl-Partitionen von n, die die Bedingungen (a), (b) bzw.\n", " (c) erfüllen.\"\"\"\n", " count_a = 0\n", " count_b = 0\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return count_a, count_b" ] }, { "cell_type": "code", "execution_count": 19, "id": "06ed6d3e", "metadata": {}, "outputs": [], "source": [ "[count87(n) for n in range(1,17)]" ] }, { "cell_type": "code", "execution_count": null, "id": "fe80df01-9ec5-48d8-b750-74e265c03f36", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "for func in [mod_5_1_or_4, no_equal_or_consecutive, count87]:\n", " write_function(func)" ] }, { "cell_type": "markdown", "id": "9a56cfd4", "metadata": {}, "source": [ "### Aufgabe 89" ] }, { "cell_type": "code", "execution_count": 368, "id": "cda5c2f8", "metadata": {}, "outputs": [], "source": [ "def conjugate(mu):\n", " \"\"\"Bestimme die konugierte Partition zu mu.\"\"\"\n", " cmu = np.zeros(mu[0], dtype=int)\n", " for i in range(1,mu[0]+1):\n", " # Ja, das funktioniert: \"mu >= i\" ist zwar ein Vektor\n", " # von Wahrheitswerten, aber die Funktion wendet \"implizit\"\n", " # die Methode __nonzero__ auf alle Elemente des Arrays\n", " # an ...\n", " cmu[i-1] = np.count_nonzero(mu >= i)\n", " return cmu" ] }, { "cell_type": "code", "execution_count": 369, "id": "e5f7f1c1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([10, 6, 3, 1])" ] }, "execution_count": 369, "metadata": {}, "output_type": "execute_result" } ], "source": [ "conjugate(np.array([4,3,3,2,2,2,1,1,1,1],dtype=int))" ] }, { "cell_type": "markdown", "id": "e8e4a72a", "metadata": {}, "source": [ "Ob zwei numpy-Arrays _koordinatenweise_ übereinstimmen, stellt man so fest:" ] }, { "cell_type": "code", "execution_count": 387, "id": "5be88e37", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([False, True, True])" ] }, "execution_count": 387, "metadata": {}, "output_type": "execute_result" } ], "source": [ "np.equal(np.array([1,2,3]), np.array([0,2,3]))" ] }, { "cell_type": "code", "execution_count": 388, "id": "61748ecd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 388, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all(np.equal(np.array([1,2,3]), np.array([0,2,3])))" ] }, { "cell_type": "markdown", "id": "af4b40a5-dd73-40ec-bab6-ff187f5ca62a", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 384, "id": "872dfb6d", "metadata": {}, "outputs": [], "source": [ "def is_self_conjugate(mu):\n", " \"\"\"Teste, ob die Partition selbskonjugiert ist.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 391, "id": "63a809e6", "metadata": {}, "outputs": [], "source": [ "def count89(n):\n", " \"\"\"Zähle alle Zahl-Partitionen von n, die die Bedingungen (a) bzw.\n", " (b) erfüllen.\"\"\"\n", " count_a = 0\n", " count_b = 0\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return count_a, count_b" ] }, { "cell_type": "code", "execution_count": 20, "id": "3cb0a19a", "metadata": {}, "outputs": [], "source": [ "[count89(n) for n in range(1,17)]" ] }, { "cell_type": "code", "execution_count": null, "id": "83e02e22-c06c-4d6d-a4b6-8d6be6a1dc79", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "for func in [is_self_conjugate, count89]:\n", " write_function(func)" ] }, { "cell_type": "markdown", "id": "cda85c53", "metadata": {}, "source": [ "# Graphen und Netzwerke\n", "\n", "## Bäume und Wälder\n", "\n", "### Aufgabe 96\n", "\n", "#### Vorbereitungen" ] }, { "cell_type": "code", "execution_count": 400, "id": "1ac7e5e2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 400, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Graphen auf n Knoten stellen wir durch ihre n x n\n", "# Adjazenzmatrizen dar: Für _einfache_ Graphen ist diese\n", "# Matrix symmetrisch und hat Nullen auf der Hauptdiagonale.\n", "# Hier ein Beispiel zum Testen:\n", "testmat = np.array([\n", " [0,0,1,0,1],\n", " [0,0,1,1,1],\n", " [1,1,0,1,0],\n", " [0,1,1,0,1],\n", " [1,1,0,1,0]\n", "])\n", "# Prüfe, ob diese Matrix symmetrisch ist:\n", "print(np.equal(testmat,testmat.T).all())\n", "# Prüfe, ob diese Matrix Nullen auf der Hauptdiagonalen hat:\n", "(np.diagonal(testmat) == 0).all()" ] }, { "cell_type": "code", "execution_count": 422, "id": "9d07b438", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 0 1 2 3]\n", " [ 4 5 6 7]\n", " [ 8 9 10 11]\n", " [12 13 14 15]]\n", "[[ 1 2 3]\n", " [ 5 6 7]\n", " [13 14 15]]\n" ] }, { "data": { "text/plain": [ "15" ] }, "execution_count": 422, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Eine Submatrix entsprechend vorgegebenen Zeilen und\n", "# Spalten können wir mit numpy-Hilfsfunktion ix_() erhalten:\n", "zeilen = [0,1,3]\n", "spalten = [1,2,3]\n", "eine_matrix = np.arange(16,dtype=int).reshape((4,4))\n", "print(eine_matrix)\n", "submatrix = eine_matrix[np.ix_(zeilen,spalten)]\n", "print(submatrix)\n", "# Achtung: Die Zeilen/Spalten der Submatrix sind wieder\n", "# fortlaufend numeriert; bei Null beginnend!\n", "submatrix[2,2]" ] }, { "cell_type": "code", "execution_count": 416, "id": "edcc3c3f", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([24, 28, 32, 36])" ] }, "execution_count": 416, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Die Summe über alle Zeilen einer Matrix erhalten wir so:\n", "np.sum(eine_matrix,axis=0)" ] }, { "cell_type": "code", "execution_count": 417, "id": "9e481ab7", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([ 6, 22, 38, 54])" ] }, "execution_count": 417, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Die Summe über alle Spalten einer Matrix erhalten wir so:\n", "np.sum(eine_matrix,axis=1)" ] }, { "cell_type": "code", "execution_count": 420, "id": "01912378", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(array([1, 3]),)" ] }, "execution_count": 420, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Die Indizes von Elementen _ungleich Null_ in einem Vektor\n", "# erhalten wir so:\n", "np.nonzero(np.array([ 0, 22, 0, 54]))[0]\n", "# Nicht auf \"[0]\" vergessen - np.nonzero liefert ein _Tupel_,\n", "# nämlich die Summen über jede Achse eines Arrays (ein Vektor\n", "# hat nur eine Achse)." ] }, { "cell_type": "markdown", "id": "df6ba7be-b777-416a-ad0e-277e2dedc169", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 440, "id": "dcff7419", "metadata": {}, "outputs": [], "source": [ "def kugelschalen(amat,m):\n", " \"\"\"Für eine gegebene Adjazenzmatrix amat und index\n", " m (beginnend bei 0) eines Knotens berechnen wir die\n", " \"Kugelschalen\" aller Punkte \"um m herum\". Wenn der Graph\n", " nicht zusammenhängend ist: Ausgabe einer Fehlermeldung.\"\"\"\n", " # Am Anfang sind alle Knoten \"frei\", also noch keiner\n", " # Kugelschale zugeteilt:\n", " freie_knoten = list(range(amat.shape[0]))\n", " # Die Kugelschale mit \"Radius\" 0 enthält nur den\n", " # Knoten mit Index m selbst:\n", " kugelschalen = [[m]]\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return kugelschalen" ] }, { "cell_type": "code", "execution_count": 439, "id": "21478d8e", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(kugelschalen)" ] }, { "cell_type": "markdown", "id": "e7de85c7", "metadata": {}, "source": [ "### Aufgabe 97" ] }, { "cell_type": "code", "execution_count": 441, "id": "5af4b0a4", "metadata": {}, "outputs": [], "source": [ "def nachbarn(amat, v):\n", " \"\"\"Hilfsfunktion: Finde in einem Graphen G (gegeben durch\n", " seine Adjazenzmatrix amat) die Nachbarn (also die adjazenten\n", " Knoten) eines Knotens v.\"\"\"\n", " return np.nonzero(amat[v])[0]" ] }, { "cell_type": "code", "execution_count": 443, "id": "44d63ee8", "metadata": {}, "outputs": [], "source": [ "# Am einfachsten wird die Programmierung _rekursiv_:\n", "# Die Funktion übernimmt den \"bisher beschrittenen\"\n", "# Weg \"path\", den gesuchten Endknoten e und die Liste\n", "# der bereits \"durchlaufenen\" (gerichteten!) Kanten und\n", "# versucht, den Weg fortzusetzen; oder einen Schritt zurück\n", "# zu machen:\n", "def schritt_weiter(amat,path,e,used_edges):\n", " \"\"\"Hilfsfunktion: Angenommen, wir haben bereits einen Teil-Weg \"path\"\n", " absolviert und eine Menge schon benutzter Kanten (dargestellt in Form\n", " einer Liste \"used_edges\") angesammelt, dann machen wir jetzt rekursiv weiter.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 449, "id": "ab53907e", "metadata": {}, "outputs": [], "source": [ "def theseus(amat,s,e):\n", " \"\"\"Finde in einem einfach zusammenhängenden Graphen (gegeben durch\n", " seine Adjazenzmatrix amat) einen Weg von Knoten s nach Knoten v, sodaß\n", " in dem Algorithmus keine Kante öfter als zweimal betrachtet wird.\"\"\"\n", " # Jede Kante wird höchstens \"einmal hin und einmal zurück\" durchlaufen:\n", " ausweg = [s]\n", " used_edges = []\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": 23, "id": "47455d8f", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "for func in [schritt_weiter, theseus]:\n", " write_function(func)" ] }, { "cell_type": "markdown", "id": "c815325d", "metadata": {}, "source": [ "### Aufgabe 98\n", "\n", "Die Funktion\n", "\n", " find_spanning_tree2\n", "\n", "aus der Vorlesung (bzw. dem Skriptum) gibt einen \"naheliegenden\" Lösungsweg vor, den Sie hier bitte geeignet modifizieren sollten." ] }, { "cell_type": "code", "execution_count": null, "id": "0a5c9fc7", "metadata": {}, "outputs": [], "source": [ "def kruskal(adj_matrix):\n", " \"\"\"Kruskals Greedy Algorithm\"\"\"\n", " # adj_matrix sollte die Adjazenzmatrix des (einfachen) Graphen\n", " # sein: Die Anzahl der Zeilen (bzw. Spalten) ist also die Anzahl\n", " # der Knoten. Die Einträge sind nun FLOAT-Zahlen, die das GEWICHT\n", " # der Kante angeben. Achtung, Eintrag np.nan bedeutet, daß die\n", " # entsprechende Kante NICHT existiert; anders als bei \"herkömmlichen\"\n", " # Adjazenzmatrizen soll Eintragung (i,j)=0 hier bedeuten: Die\n", " # Kante von i nach j hat Gewicht 0.\n", " \n", " # Modifizieren Sie die Funktion find_spanning_tree2 aus der\n", " # Vorlesung so, daß Kruskals Algorithmus implementiert wird:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " \n", " # Rückgabe: Minimales Gewicht, Kanten des minimalen spannenden\n", " # Waldes, Zusammenhangskomponenten (als Partition der Knotenmenge;\n", " # codiert als Funktion von beschränktem Wachstum):\n", " return sum_of_weights, list_of_used_edges, fn_restricted_growth" ] }, { "cell_type": "code", "execution_count": null, "id": "1ff3771a-6a30-441b-b5f5-713cbab3a945", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(kruskal)" ] }, { "cell_type": "markdown", "id": "9567380e", "metadata": {}, "source": [ "## Eulersche Graphen\n", "\n", "### Aufgabe 99\n", "\n", "#### Hilfsfunktionen" ] }, { "cell_type": "code", "execution_count": 453, "id": "afef1027", "metadata": {}, "outputs": [], "source": [ "def modify_edge (am, i, j, entry =1):\n", " \"\"\"Modifiziere Eintrag in einer Adjazenzmatrix, sodaß diese symmetrisch bleibt.\"\"\"\n", " try :\n", " am[i][j] = am[j][i] = entry\n", " except IndexError :\n", " print(f'Indices ({i},{j}) nicht in {am.shape}!')" ] }, { "cell_type": "code", "execution_count": 465, "id": "90b94810", "metadata": {}, "outputs": [], "source": [ "def get_component(amat, v):\n", " \"\"\"Bestimme die Liste der Knoten, die zur selben Zusammenhangskomponente\n", " gehören wie der Knoten v. (Der Graph ist - wie immer - durch seine Adjazenzmatrix\n", " amat gegeben.)\"\"\"\n", " # v gehört natürlich zu \"seiner eigenen\" Komponente:\n", " component = [v]\n", " # Am Anfang ist v außerdem der einzige Knoten, von dem\n", " # aus die Komponente \"potentiell erweitert\" werden kann:\n", " pot_ext = [v]\n", " # Im Verlauf des einfachen Algorithmus werden \"Kanten gestrichen\",\n", " # also die Adjazenzmatrix modifiziert: Dafür stellen wir eine _Kopie_\n", " # der \"originalen\" Adjazenzmatrix her (die ja vielleicht anderweitig\n", " # noch gebraucht wird.)\n", " graph = np.copy(amat)\n", " # Solange es Knoten gibt, von denen aus die Komponente\n", " # \"potentiell erweitert\" werden kann, probieren wir das:\n", " while pot_ext:\n", " # Der Befehlt pop entfernt das letzte Element der Liste\n", " # und liefert es als Wert zurück:\n", " u = pot_ext.pop()\n", " # Suche die Nachbarn von u (als Liste):\n", " neighbours = list(nachbarn(graph, u))\n", " # Entferne alle Kanten, die _irgendwelche_ Knoten aus der Liste\n", " # component+neighbours verbinden: Damit ist sichergestellt, daß im\n", " # nächsten Schritt keine Nachbarn gefunden werden, die bereits\n", " # zur Komponente dazugefügt wurden!\n", " for i,j in itertools.combinations(component+neighbours,2):\n", " modify_edge(graph, i, j, 0)\n", " # Diese (\"außerhalb der Komponente liegenden\" Nachbarn!!!)\n", " # erweitern die Komponente und die \"potentiell erweiternden\"\n", " # Knoten:\n", " component+= neighbours\n", " pot_ext+= neighbours\n", " \n", " return component" ] }, { "cell_type": "code", "execution_count": 466, "id": "12d6fddf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 2, 4, 1, 3]" ] }, "execution_count": 466, "metadata": {}, "output_type": "execute_result" } ], "source": [ "get_component(testmat, 0)" ] }, { "cell_type": "code", "execution_count": 468, "id": "06093792", "metadata": {}, "outputs": [], "source": [ "def is_connected(amat):\n", " \"\"\"Test: Ist der durch die Adjazenzmatrix amat gegebene Graph zusammenhängend?\"\"\"\n", " n = amat.shape[0]\n", " if n <= 1:\n", " # Der \"leere Graph\" und der einpunktige Graph sind zusammenhängend\n", " return True\n", " # Implicit else:\n", " return len(get_component(amat, 0)) == n" ] }, { "cell_type": "code", "execution_count": 469, "id": "c8ea58d3", "metadata": {}, "outputs": [], "source": [ "def is_eulerian(amat):\n", " \"\"\"Teste, ob die (symmetrische) Adjazenmatrix amat einen Eulerschen\n", " Graphen bestimmt.\"\"\"\n", " if not is_connected(amat):\n", " return False\n", " # Implicit else:\n", " return (np.sum(amat, axis=0, dtype=int)%2 == 0).all()" ] }, { "cell_type": "code", "execution_count": 470, "id": "29a0c2cf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 470, "metadata": {}, "output_type": "execute_result" } ], "source": [ "is_eulerian(testmat)" ] }, { "cell_type": "markdown", "id": "781c92f4", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe" ] }, { "cell_type": "code", "execution_count": 473, "id": "d948984a", "metadata": {}, "outputs": [], "source": [ "def eulerian_trail(amat):\n", " \"\"\"Finde eine Eulersche Wanderung.\"\"\"\n", " if not is_eulerian(amat):\n", " return None\n", " # Implicit else:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "8bf37294-ceba-49dc-b45d-2f4dc2c11386", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(eulerian_trail)" ] }, { "cell_type": "markdown", "id": "e531a4d4", "metadata": {}, "source": [ "## Digraphen und Netzwerke\n", "\n", "### Aufgabe 105\n", "\n", "Der \"Fluß\" sollte genauso dargestellt werden wie die \"Kapazität\", nämlich als (Adjazenz-)Matrix von Kantengewichten. " ] }, { "cell_type": "code", "execution_count": null, "id": "f2eba650", "metadata": {}, "outputs": [], "source": [ "def construct_S_E(cap, flow, source, sink):\n", " \"\"\"Konstruiere die Mengen S und E_S aus dem Beweis des Lemmas\n", " zum Satz von Ford und Fulkerson: cap ist die \"Kapazitätsmatrix\"\n", " des (gerichteten Graphen), flow ist die \"Flußmatrix\" (d.h.,\n", " die Eintragung (i,j) entspricht der Kapazität bzw. dem Fluß für\n", " die Kante (i,j); alle Eintragungen sind ganzzahlig.\"\"\"\n", " S=None\n", " E=None\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return S, E" ] }, { "cell_type": "code", "execution_count": null, "id": "4dd3714e-4304-4492-bd09-5d3eda730e0a", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(construct_S_E)" ] }, { "cell_type": "code", "execution_count": null, "id": "67612c3f", "metadata": {}, "outputs": [], "source": [ "def ford_fulkerson(cap, source, sink):\n", " \"\"\"Konstruiere einen (ganzzahligen) maximalen Fluß für\n", " das durch cap (ganzzahlige Kapazitäten), source und sink\n", " gegebene Netzwerk.\"\"\"\n", " dim = cap.shape[0]\n", " flow = np.zeros(dim*dim).reshape((dim,dim))\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return flow " ] }, { "cell_type": "code", "execution_count": null, "id": "81ca98fe-e6f8-423f-80c6-f7a86a5aa397", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(ford_fulkerson)" ] }, { "cell_type": "markdown", "id": "2c761869", "metadata": {}, "source": [ "# Gewichtserhaltende vorzeichenumkehrende Involutionen\n", "\n", "## Der Eulersche Pentagonalzahlensatz\n", "\n", "### Aufgabe 116" ] }, { "cell_type": "code", "execution_count": 21, "id": "de6e2145", "metadata": {}, "outputs": [], "source": [ "def partition_table(m):\n", " \"\"\"Erzeuge eine Liste der ersten m Werte der Partitionsfunktion p(n)\n", " mit der Rekursion aus dem Abschnitt zum Eulerschen Pentagonalzahlensatz\"\"\"\n", " table = np.zeros(m, dtype=int)\n", " table[0] = table[1] = 1\n", " # table[0] = table[1] = 1 sind also schon richtig belegt, um den\n", " # Rest müssen wir uns jetzt kümmern:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return table" ] }, { "cell_type": "code", "execution_count": null, "id": "1a5157ed-1846-4b43-b949-1b716b24697d", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(partition_table)" ] }, { "cell_type": "markdown", "id": "ac9522ec", "metadata": {}, "source": [ "# Datenstrukturen und Algorithmen\n", "\n", "## Sortieralgorithmen\n", "\n", "### Aufgabe 128" ] }, { "cell_type": "code", "execution_count": null, "id": "83f47c02", "metadata": {}, "outputs": [], "source": [ "def quicksort_clever(liste):\n", " \"\"\"Implementiere den quicksort-Algorithmus \"speichersparend\", wie\n", " im Skriptum gezeigt. Das Argument der Funktion sollte ein numpy-\n", " Vektor sein.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "4493acbb-fdf7-4aea-92da-bb16b7e8a003", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(quicksort_clever)" ] }, { "cell_type": "markdown", "id": "05e3e79d", "metadata": {}, "source": [ "## Suchbäume in der Praxis\n", "\n", "### Aufgabe 129" ] }, { "cell_type": "code", "execution_count": null, "id": "6c7b9cd0", "metadata": {}, "outputs": [], "source": [ "class BinaryTreeNode:\n", " def __init__(self, key=None, data = None, predecessor = None, node_type = \"root\"):\n", " \"\"\"Initialize:\"\"\"\n", " # \"Pointer\" (sort of...) to predecessor\n", " self.predecessor = predecessor\n", " # Is this node the \"global\" root, or a left or right subtree\n", " # of its predecessor?\n", " self.node_type = node_type\n", " # Informations on left/right subtrees\n", " self.left = None # Ein neu erzeugter Knoten hat noch keinen ...\n", " self.right= None # ... linken oder rechten Teilbaum!\n", " # And, of course: Store the key ...\n", " self.key = key\n", " # ... and the data _as a list_: Maybe we want to add other data\n", " # later for the _same_ key! (In practice, we might want to use\n", " # deepcopy(), but this is simply a programming exercise;-)\n", " self.data = [data]\n", "\n", " def __str__(self):\n", " \"\"\"Return string representation:\"\"\"\n", " return f'{self.node_type}({self.key})<{self.data}>.'\n", " \n", " # Auxiliary functions:\n", " def is_leaf(self):\n", " \"\"\"Return True if self is, in fact, a leaf of the tree:\"\"\"\n", " return self.left == None and self.right == None\n", " \n", " # Append successor as a left subtree:\n", " def append_left(self, successor):\n", " # Annahme ist natürlich, daß \"successor\" eine Instanz\n", " # der Klasse \"BinaryTreeNode\" ist!\n", " # ... bitte ausarbeiten!\n", "\n", " # Append successor as a right subtree:\n", " def append_right(self, successor):\n", " # Annahme ist natürlich, daß \"successor\" eine Instanz\n", " # der Klasse \"BinaryTreeNode\" ist!\n", " # ... bitte ausarbeiten!\n", "\n", " # Traverse the tree rooted at self \"breadth-first\" and apply a function which\n", " # takes node, level_of_node as arguments\n", " def bf_transversal(self, the_func):\n", " # Use a queue for storing the nodes (in their order:\n", " # \"level by level, from left to right\":\n", " queue = deque()\n", " # Here, we also collect information about the level\n", " # and number of the node (in its level, from left to right). \n", " # Append (root,level=0) to the right:\n", " queue.append((self,0))\n", " # Now traverse the tree:\n", " # ... bitte ausarbeiten!" ] }, { "cell_type": "code", "execution_count": null, "id": "358df04c-7c07-45a9-9ed1-387a6fd63656", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern! Das\n", "# ist hier ein bißchen umständlicher:\n", "INPUT_NUMMER = 1 # Bitte ändern auf die Nummer der vorigen Zelle! \n", "write_code(_ih[INPUT_NUMMER],'BinaryTreeNode')" ] }, { "cell_type": "markdown", "id": "578739a3", "metadata": {}, "source": [ "Ein binärer Baum besteht aus einer Wurzel (an der in den _interessanten_ Fällen Teilbäume hängen;-):" ] }, { "cell_type": "code", "execution_count": null, "id": "7b5a9da7", "metadata": {}, "outputs": [], "source": [ "class BinaryTree:\n", " def __init__(self, root_or_key, data=None):\n", " # Wir lassen die Möglichkeit zu, daß \"root_or_key\"\n", " # bereits eine Instanz der Klasse \"BinaryTreeNode\"\n", " # (und damit bereits ein Wurzelbaum!) IST:\n", " if isinstance(root_or_key, BinaryTreeNode):\n", " self.root = root_or_key\n", " else:\n", " # \"root_or_key\" kann aber auch einfach ein \"key\"\n", " # (also eine Kennzahl, nach der die Daten in diesem\n", " # Baum sortiert werden sollen) sein:\n", " self.root = BinaryTreeNode(root_or_key, data=data)\n", " # Queue for breadth-first search\n", " self.bf_queue = deque()\n", " \n", " def __str__(self):\n", " return f'BinaryTree (root: {self.root})'\n", "\n", " # Search depth-first for key in subtree rooted at node:\n", " def df_search_subtree(self, node, key):\n", " # Implementiere die Suche: Falls erfolglos, gib\n", " # None zurück ... \n", " # Hinweis: Am einfachsten REKURSIV\n", "\n", " # Search depth-first for key in self:\n", " def df_search(self, key):\n", " return self.df_search_subtree(self.root, key)\n", " \n", " def insert_as_leaf(self, new_key, parent_key, left=True, data=None):\n", " # Ein neuer Knoten mit key \"new_key\" soll an den Knoten\n", " # mit key \"parent_key\" als linkes oder rechtes Blatt angehängt\n", " # werden - wenn es keinen solchen Knoten gibt, oder wenn\n", " # die entsprechenden linken oder rechten Teilbäume schon\n", " # existieren, ist das ein FEHLER!\n", " # ... bitte ausarbeiten!\n", " \n", " def delete_leaf(self, the_key):\n", " # Ein Blatt mit key \"the_key\" soll entfernt werden: Wenn\n", " # es keinen Knoten mit key \"the_key\" gibt, ist das ein\n", " # FEHLER; ebenso wenn der Knoten zwar existiert, aber kein\n", " # Blatt ist. Wenn das Blatt zugleich die Wurzel ist,\n", " # setze self.root = None\n", " # ... bitte ausarbeiten!\n", " the_node = self.df_search(the_key)" ] }, { "cell_type": "code", "execution_count": null, "id": "cae9fe00-4678-47fc-920d-ca25acad3c51", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern! Das\n", "# ist hier ein bißchen umständlicher:\n", "INPUT_NUMMER = 1 # Bitte ändern auf die Nummer der vorigen Zelle! \n", "write_code(_ih[INPUT_NUMMER],'BinaryTree')" ] }, { "cell_type": "markdown", "id": "bba63309", "metadata": {}, "source": [ "### Aufgabe 130" ] }, { "cell_type": "code", "execution_count": null, "id": "a8218d9b", "metadata": {}, "outputs": [], "source": [ "def huffman(p_dist):\n", " \"\"\"Erzeuge einen binären Suchbaum mit dem Huffman-Algorithmus\n", " für die gegebene Wahrscheinlichkeitsveteilung p_dist (ein numpy-\n", " Vektor).\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Richtiges Ergebnis zurückgeben:\n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "4eaea725-06e5-4153-9061-34ecf5b0ed32", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern!\n", "write_function(huffman)" ] }, { "cell_type": "markdown", "id": "c3fe93ec", "metadata": {}, "source": [ "### Aufgabe 131\n", "\n", "#### Vorbereitungen und Hilfsfunktionen\n", "\n", "Knoten eines Baumes sollen ja nicht nur den \"key\" enthalten, der die _Ordnung_ im Baum bestimme, sondern auch \"relevante Inhalte\": Das können wir in eine eigene Klasse auslagern." ] }, { "cell_type": "code", "execution_count": null, "id": "85eb2df3", "metadata": {}, "outputs": [], "source": [ "class InnerNodeContents:\n", " \"\"\"An \"auxiliary\" class basically containing a key _only_, to be used\n", " for the initialization of inner nodes in complete binary search trees.\"\"\"\n", " def __init__(self, key):\n", " \"\"\"Initialize:\"\"\"\n", " # Key for sorting:\n", " self.key = key\n", " self.data = None\n", "\n", " def update(self, data):\n", " \"\"\"Dummy-function, just to satisfy pylint;-)\"\"\"\n", " self.data = data\n", "\n", " def __str__(self):\n", " \"\"\"Return string representation:\"\"\"\n", " return f'inner node {self.key}'" ] }, { "cell_type": "markdown", "id": "91605902", "metadata": {}, "source": [ "In jedem Knoten wird also eine Datenstruktur \"data\" gespeichert, die je nach Anwendung unterschiedlich gestaltet sein kann: Im einfachsten Fall ist das einfach eine Liste, die\n", "\n", "* bei der Initialisierung eines Knotens neu erzeugt wird,\n", "* beim \"Updaten\" eines Knotens mit den neuen Informationen ergänzt wird,\n", "* beim Entfernen eines Knotens wieder gelöscht wird.\n", "\n", "Das englische Word \"default\" bedeutet zunächst \"Ausfall, Auslassung oder Versäumnis\": Im Zusammenhang mit Programmierung ist ein \"Default-Wert\" für eine Variable ein vorgegebener Wert, der der Variable dann zugewiesen wird, wenn eine explizite Zuweisung ausgelassen wurde. In der Folge auch Default-Funktionen für Aufrufe von depth-first- bzw. breadth-first traversal:" ] }, { "cell_type": "code", "execution_count": null, "id": "786a5eaf", "metadata": {}, "outputs": [], "source": [ "# Auxiliary functions:\n", "def default_initialize(data):\n", " \"\"\"Default-Funktion: Was soll beim Initialisieren eines\n", " _neuen_ Knoten mit den Daten geschehen?\n", " Hier: Erzeuge eine neue Liste, deren (vorläufig) einziges\n", " Element die Daten sind.\"\"\"\n", " return [data]\n", "\n", "def default_update(the_leaf, data):\n", " \"\"\"Default-Funktion: Was soll beim Update eines _existierenden_\n", " mit den neuen Daten geschehen?\n", " Hier: Füge sie einfach an die bestehende Liste an.\"\"\"\n", " the_leaf.data += [data]\n", "\n", "def default_delete(the_leaf, data):\n", " \"\"\"Default-Funktion: Wie sollen Daten in einem Blatt gelöscht werden?\n", " Und wann ist das Blatt _insgesamt_ zu löschen?\n", " Hier: Entferne Daten aus der bestehenden Liste; das Blatt ist\n", " zu löschen, wenn die Liste danach leer ist.\"\"\"\n", " if data in the_leaf.data:\n", " the_leaf.data.remove(data)\n", " # No more data?\n", " return len(the_leaf.data) == 0\n", "\n", "def simply_delete(the_leaf, data):\n", " \"\"\"Default-Funktion: Gib einfach \"True\" zurück: Im Zusammenhang hier\n", " heißt das \"Lösche das Blatt sofort, ohne auf die Daten zu achten.\"\"\"\n", " print(f'Delete {the_leaf} ({data})')\n", " return True\n", "\n", "def default_df(node, nof_steps):\n", " \"\"\"Default-Funktion für depth-first-traversal\"\"\"\n", " # Simply show the data, if node is a leaf:\n", " if node.data is not None:\n", " data = \" and \".join([f'{nodedata}' for nodedata in node.data])\n", " else:\n", " data = 'None'\n", " print(f'{nof_steps}: {node.key} -> {data}')\n", "\n", "def default_bf(node, level, count):\n", " \"\"\"Default-Funktion für breadth-first-traversal\"\"\"\n", " if node.is_leaf():\n", " print(f'({count},{-level}) LEAF: key = {node.key}, data = {node.data}.')\n", " else:\n", " sides = ['left','right']\n", " info = [\n", " f\"{node.subtree[side]['root'].key}/{node.subtree[side]['depth']}\"\n", " for side in sides\n", " ]\n", " print(f'({count},{-level}) key = {node.key}: {\" \".join(info)}')" ] }, { "cell_type": "code", "execution_count": null, "id": "5b930630", "metadata": {}, "outputs": [], "source": [ "# Auxiliary dictionary: Zur einfachen \"Spiegelung\", also Vertauschung\n", "# von left und right:\n", "mirror = {'left' : 'right', 'right' : 'left'}" ] }, { "cell_type": "markdown", "id": "ff1180ff", "metadata": {}, "source": [ "#### Die eigentliche Aufgabe\n", "\n", "Knoten für AVL-Trees:" ] }, { "cell_type": "code", "execution_count": null, "id": "70c6da0d", "metadata": {}, "outputs": [], "source": [ "class AVLNode:\n", " \"\"\"Class implementing (nodes of) AVL-trees: key_n_data is supposed to have a\n", " member 'key' (which is used for sorting) and a member data (containing useful\n", " information).\n", "\n", " NOTE: The implementation should never change the \"leaf-ness\" of nodes!\n", " NOTE: Any AVLNode serves also as root of the subtree pending from it!\"\"\"\n", " def __init__(self,\n", " key_n_data,\n", " predecessor = None,\n", " node_type = \"root\",\n", " initialize = default_initialize\n", " # update = default_update\n", " ):\n", " \"\"\"Initialize:\"\"\"\n", " # Store key:\n", " self.key = key_n_data.key\n", " # \"Pointer\" (sort of...) to predecessor\n", " self.predecessor = predecessor\n", " # Is this node the \"global\" root, or a left or right subtree\n", " # of its predecessor?\n", " self.node_type = node_type\n", " # Informations on left/right subtrees\n", " self.subtree = {\n", " 'left': {'root' : None, 'depth' : -1},\n", " 'right': {'root' : None, 'depth' : -1}\n", " }\n", " # And, of course: Store the the data! - Here, we \"enclose\" data in\n", " # a _list_, since we might want to store several \"data instances\"\n", " # with the _same_ key!\n", " self.data = initialize(key_n_data.data)\n", "\n", "\n", " def __str__(self):\n", " \"\"\"Return string representation:\"\"\"\n", " i_l = 'leaf' if self.is_leaf() else 'inner'\n", " s_1 = f'{i_l} {self.node_type}-node (key {self.key})'\n", " s_2 = f'{self.subtree_depth(\"left\"), self.subtree_depth(\"right\")}.'\n", " return f'[{s_1}, depths: ({s_2})]'\n", "\n", " # Auxiliary functions:\n", " def subtree_depth(self, left_or_right):\n", " \"\"\"Return depth of subtrees\"\"\"\n", " return self.subtree[left_or_right]['depth']\n", "\n", " def is_leaf(self):\n", " \"\"\"Return True if self is, in fact, a leaf of the tree:\"\"\"\n", " return self.subtree[\"left\"][\"root\"] is None and self.subtree[\"right\"][\"root\"] is None\n", "\n", " def depth(self):\n", " \"\"\"Return the depth of (sub-)tree rooted at self.\"\"\"\n", " return max(self.subtree_depth(\"left\"), self.subtree_depth(\"right\")) + 1\n", "\n", " # Basic functionality:\n", " def replace_subtree(self, new_subtree, side):\n", " \"\"\"Replace the left_or_right subtree by new_subtree,\n", " do the corresponding \"local book-keeping\" for pointers, and\n", " return the subtree thus replaced.\n", "\n", " NOTE: This operation does consider neither \"leaf-ness\" nor\n", " keys of self and new_subtree!\"\"\"\n", " if new_subtree is None:\n", " # new_subtree might by None: In this case, there are no members\n", " # predecessor, node_type and depth().\n", " new_subtree_depth = -1\n", " else:\n", " new_subtree.predecessor = self\n", " new_subtree.node_type = side\n", " new_subtree_depth = new_subtree.depth()\n", "\n", " replaced_subtree = self.subtree[side]['root']\n", "\n", " self.subtree[side]['root'] = new_subtree\n", " self.subtree[side]['depth'] = new_subtree_depth\n", "\n", " # Nothing has changed \"locally\" in the replaced subtree!\n", " return replaced_subtree\n", "\n", " def append_me(self, the_leaf, side):\n", " \"\"\"Append self to an existing leaf as subtree \"side\" and\n", " return root of rebalanced tree.\n", "\n", " NOTE: We want that all leaves _stay_ leaves during their\n", " whole lifetime, so the node \"leaf\" should be a leaf _again_\n", " after this operation!\n", " \"\"\"\n", " # Check that the_leaf actually is a leaf:\n", " if not the_leaf.is_leaf():\n", " raise RuntimeError(f'Cannot append to non-leaf {the_leaf}')\n", " # Implicit else\n", " # self and leaf will be subtrees of a NEW inner node, which\n", " # will \"replace\" leaf (in particular, leaf \"stays\" a leaf):\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " def remove_me(self):\n", " \"\"\"Remove self from the tree; i.e., destroy connection from self.predecessor,\n", " and return root of rebalanced tree.\n", "\n", " NOTE: We want that all leaves _stay_ leaves during their\n", " whole lifetime, so the the _sibling_ of node \"self\" should be a leaf _again_\n", " after this operation!\n", " \"\"\"\n", " if not self.is_leaf():\n", " raise RuntimeError(f'Cannot remove non-leaf {self}.')\n", " # Implicit else:\n", " pre = self.predecessor\n", " if not pre:\n", " # self is actually the root: Removing it gives root = None!\n", " return None\n", " # Implicit else:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " def move_up_subtree(self, side, otherside):\n", " \"\"\"Move up subtree[side] (assumed to be not None!) and return it\n", " (this is the \"simple rotation\" according to Adelson-Velski and Landis).\n", "\n", " NOTE: This operation does not affect the \"leaf-ness\" of nodes!\n", " \"\"\"\n", "\n", " # Store informations for later use:\n", " node_predecessor = self.predecessor\n", " node_type = self.node_type\n", "\n", " # This subtree should \"move up\":\n", " up_mover = self.subtree[side]['root']\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return up_mover\n", "\n", " def rebalance_subtrees(self):\n", " \"\"\"Rebalance subtrees:\n", " Recall that for _every_ node we want to maintain the condition\n", " (ALL keys in the left subtree) <= node.key < (ALL keys in the right subtree),\n", " and balancing means maintaining the condition\n", " -1 <= (self.left_depth() - self.right_depth()) <= 1.\n", "\n", " NOTE: This operation consists of zero, one or two move_up_subtree-steps,\n", " so does not change the \"leaf-ness\" of nodes!\n", " \"\"\"\n", " # \"Bias\" of the left subtree:\n", " left_bias = self.subtree_depth('left') - self.subtree_depth('right')\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return self.move_up_subtree(side, otherside)\n", "\n", " def rebalance(self):\n", " \"\"\"Rebalance all nodes, ascending up to the root:\n", "\n", " NOTE: This operation consists of a sequence of\n", " rebalance_subtrees-steps, so does not change the\n", " \"leaf-ness\" of nodes!\n", " \"\"\"\n", " node_to_return = self\n", "\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " # Return the root:\n", " return node_to_return\n", "\n", " def find_append_pos(self, key):\n", " \"\"\"Find the position where to append key _as a leaf_:\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return None\n", "\n", " def find_extremum(self, left_or_right = 'left'):\n", " \"\"\"Find extremal key (minimal for 'left', maximal for 'right')\n", " in subtree rooted at self:\"\"\"\n", " node_to_return = self\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return node_to_return\n", "\n", " def append(self, new_data, initialize=default_initialize, update=default_update):\n", " \"\"\"Find the correct leaf according to new_data.key and append\n", " the corresponding new_data.data, either by updating the data in\n", " an existing leaf, or by appending a new leaf initialized with\n", " new_data.\n", "\n", " In any case, return the \"root of the rebalanced tree\" (assumed to\n", " be self, if no new leaf is appended) and the new leaf.\"\"\"\n", "\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return new_root, new_leaf\n", "\n", " # More useful functions:\n", " def find_root(self):\n", " \"\"\"Find the root of self, by moving upwards as far as possible.\"\"\"\n", " current = self\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " def find_predecessor_which_is(self, left_or_right = 'left'):\n", " \"\"\"Find first predecessor which is a left_or_right subtree.\"\"\"\n", " pred = self.predecessor\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " def find_neighbouring_leaf(self, side='left'):\n", " \"\"\"Find the neighbouring leaf\"\"\"\n", " other_side = mirror[side]\n", " if self.node_type == other_side:\n", " return self.predecessor.subtree[side]['root'].find_extremum(other_side)\n", " # Implicit else:\n", " # Find first node \"upwards\" where we can turn to the other side:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " def depth_first_traversal(self, the_func = default_df, nof_steps = 0):\n", " \"\"\"Depth-first tree traversal of the subtree rooted at self,\n", " also accounts for the number of steps already taken:\"\"\"\n", " the_func(self, nof_steps)\n", "\n", " # Proceed recursively\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", "\n", " # Traverse the tree rooted at self \"breadth-first\" and apply a function which\n", " # takes node, level_of_node as arguments\n", " def breadth_first_traversal(self, the_func = default_bf):\n", " \"\"\"Breadth-first traversal of the (sub-)tree rooted at self.\"\"\"\n", " # We use a queue for storing the nodes (in their order:\n", " # \"level by level, from left to right\":\n", " queue = deque()\n", " # Here, we also collect information about the level\n", " # and number of the node (in its level, from left to right).\n", " # Append (root, level=0) to the right:\n", " queue.append((self,0))\n", " # Traverse the tree:\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n" ] }, { "cell_type": "code", "execution_count": null, "id": "8339c3e2-61ca-477e-a9a9-44b840472973", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern! Das\n", "# ist hier ein bißchen umständlicher:\n", "INPUT_NUMMER = 1 # Bitte ändern auf die Nummer der vorigen Zelle! \n", "write_code(_ih[INPUT_NUMMER],'AVLNode')" ] }, { "cell_type": "markdown", "id": "598bb0c5", "metadata": {}, "source": [ "In einem Baum sollten alle Knoten vom selben Typ sein und dieselben Funktionen für Initialisierung, Update und Delete verwenden:" ] }, { "cell_type": "code", "execution_count": null, "id": "be7f778e", "metadata": {}, "outputs": [], "source": [ "# A class implementing AVL-Trees:\n", "class AVLTree:\n", " \"\"\"Class implementing AVL-trees: Basically, this class has a pointer to a\n", " root (AVLNode) and stores the functions to be used for initializing, updating\n", " and deleting nodes.\n", "\n", " Most of the functionality is already contained in AVLNode.\"\"\"\n", "\n", " def __init__(self,\n", " key_n_data,\n", " initialize = default_initialize,\n", " update=default_update,\n", " delete_function=default_delete\n", " ):\n", " \"\"\"Initialization of AVLTree\"\"\"\n", " self.root = AVLNode(key_n_data, initialize = initialize)\n", " self.initialize = initialize\n", " self.update = update\n", " self.delete_function = delete_function\n", "\n", " def __str__(self):\n", " \"\"\"String representation\"\"\"\n", " return f'AVLTree (root key = {self.root.key})'\n", "\n", " def append(self, new_data):\n", " \"\"\"Append new data (as a new leaf), update root.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n", " return the_leaf\n", "\n", " def remove(self, the_leaf):\n", " \"\"\"Delete (unconditionally) some leaf from the tree\"\"\"\n", " self.root = the_leaf.remove_me()\n", "\n", " def delete(self, the_key, the_item, delete_function=default_delete):\n", " \"\"\"Find the correct leaf according to the_key: If there\n", " is actually some node with the same key, call delete_func, which\n", " should give back a flag indicating whether the leaf actually should\n", " be removed: If so, reset root to root of rebalanced tree.\"\"\"\n", " # Ab hier bitte Code einfügen bzw. verändern!\n", " # ...\n" ] }, { "cell_type": "code", "execution_count": null, "id": "51489d1b-84f1-4505-aede-b601667bfe2a", "metadata": {}, "outputs": [], "source": [ "# Vergessen Sie nicht, Ihre Ausarbeitung zu speichern! Das\n", "# ist hier ein bißchen umständlicher:\n", "INPUT_NUMMER = 1 # Bitte ändern auf die Nummer der vorigen Zelle! \n", "write_code(_ih[INPUT_NUMMER],'AVLTree')" ] }, { "cell_type": "markdown", "id": "3c866b53", "metadata": {}, "source": [ "# Algorithmische Geometrie\n" ] }, { "cell_type": "code", "execution_count": null, "id": "26a7f3cd", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "10f38f07", "metadata": {}, "source": [ "# Appendix" ] }, { "cell_type": "code", "execution_count": null, "id": "d6e480d4", "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.7.13" } }, "nbformat": 4, "nbformat_minor": 5 }