{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 28 – Aufwand verschiedener Lösungsansätze vergleichen\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich vergleiche den Aufwand verschiedener Lösungsansätze miteinander.\n",
    "\n",
    "> Der Begriff **Aufwand** wird hier in einem **didaktisch reduzierten, anschaulichen** Sinn verwendet (Anzahl der geprüften Möglichkeiten bzw. Laufzeit) – eine formale Komplexitätstheorie folgt erst in der Oberstufe."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": [
     "sprachhilfe"
    ]
   },
   "source": [
    "## 🗣️ Sprachhilfe\n",
    "- „Es handelt sich um ein Problem/eine Probleminstanz, weil …“\n",
    "- „Der Ansatz prüft/wählt … und benötigt dabei …“\n",
    "- „Die Heuristik ist hier geeignet/nicht geeignet, weil …“"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📌 Merksätze\n",
    "\n",
    "- Der **Aufwand** eines Lösungsansatzes lässt sich anschaulich als **Anzahl der zu prüfenden Möglichkeiten** oder als **tatsächlich gemessene Rechenzeit** beschreiben.\n",
    "- Beim TSP (Brute-Force) wächst der Aufwand **faktoriell** mit der Anzahl der Städte: `(n-1)!`\n",
    "- Beim Rucksackproblem (Brute-Force) wächst der Aufwand **exponentiell** mit der Anzahl der Gegenstände: `2^n`\n",
    "- Greedy-Heuristiken prüfen dagegen **wesentlich weniger Möglichkeiten**; der Aufwand entsteht hier vor allem durch das Sortieren und das einmalige Durchlaufen der Gegenstände.\n",
    "- Schon bei mäßig größeren Probleminstanzen wird der Unterschied zwischen Brute-Force und Heuristik **drastisch** spürbar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Messung: Wachstum des Brute-Force-Aufwands (TSP)\n",
    "Die folgende Zelle misst, wie stark die Anzahl der zu prüfenden Rundreisen und die tatsächliche Rechenzeit mit der Anzahl der Städte wächst."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "from itertools import permutations\n",
    "\n",
    "def anzahl_und_zeit_bruteforce(anzahl_staedte):\n",
    "    staedte = list(range(anzahl_staedte))\n",
    "    start = time.time()\n",
    "    anzahl = 0\n",
    "    for _ in permutations(staedte[1:]):\n",
    "        anzahl += 1\n",
    "    dauer = time.time() - start\n",
    "    return anzahl, dauer\n",
    "\n",
    "print(f\"{'Städte':>7} | {'Anzahl Routen':>15} | {'Zeit (s)':>10}\")\n",
    "for n in range(2, 9):\n",
    "    anzahl, dauer = anzahl_und_zeit_bruteforce(n)\n",
    "    print(f\"{n:>7} | {anzahl:>15} | {dauer:>10.4f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – Tabelle interpretieren\n",
    "Betrachtet die Ausgabe oben:\n",
    "1. Um welchen Faktor wächst die Anzahl der Routen jeweils von `n` zu `n+1` Städten?\n",
    "2. Schätzt anhand des Musters (ohne es auszuführen!), wie lange die Berechnung bei **12 Städten** ungefähr dauern würde."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Antworten hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 – Rucksackproblem: Brute-Force vs. Greedy im Vergleich\n",
    "Erstellt für eine wachsende Anzahl an Gegenständen (z. B. 5, 10, 15, 18) eine Tabelle mit der Anzahl der von Brute Force geprüften Teilmengen (`2^n`). Vergleicht dieses Wachstum mit der Greedy-Heuristik, die die Gegenstände sortiert und anschließend einmal durchläuft. Die Code-Zelle kann optional zur Kontrolle ergänzt werden."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# OPTIONAL: Tabelle mit n und 2**n zur Kontrolle ausgeben\n",
    "for n in [5, 10, 15, 18]:\n",
    "    pass  # TODO: 2**n berechnen und ausgeben\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🚀 Zusatzaufgabe – Diagramm\n",
    "Falls ihr mit `matplotlib` vertraut seid: Stellt das faktorielle Wachstum (TSP) und das exponentielle Wachstum (Rucksack) grafisch gegenüber."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "\n",
    "n_werte = list(range(1, 11))\n",
    "faktoriell = [math.factorial(n) for n in n_werte]\n",
    "exponentiell = [2**n for n in n_werte]\n",
    "\n",
    "plt.plot(n_werte, faktoriell, marker=\"o\", label=\"Fakultät (TSP)\")\n",
    "plt.plot(n_werte, exponentiell, marker=\"o\", label=\"2^n (Rucksack)\")\n",
    "plt.yscale(\"log\")\n",
    "plt.xlabel(\"Anzahl n\")\n",
    "plt.ylabel(\"Anzahl Möglichkeiten (log-Skala)\")\n",
    "plt.legend()\n",
    "plt.title(\"Wachstum des Brute-Force-Aufwands\")\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "v3_revision": {
   "basis": "MINT-Lehrplan Informatik 10 (2026)",
   "didaktik": "fragend-entwickelnder Kern, kurzer Transfer, flexible Reserve",
   "lerngruppe": "11 SuS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
