{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DS 23 – Problem, Probleminstanz und abstrahierte Darstellung\n",
    "**Informatik 10 – MINT-Zweig | Informatisches Problemlösen**\n",
    "\n",
    "## Lernziel\n",
    "Ich unterscheide zwischen einem Problem und einer Probleminstanz und untersuche kleine, abstrahiert dargestellte Probleminstanzen, um strukturelle Eigenschaften zu erkennen.\n",
    "\n",
    "> **Hinweis:** In diesem Themenfeld steht laut Lehrplan die **Auseinandersetzung mit Problemstrukturen und Lösungsstrategien** im Vordergrund – die Umsetzung in einer Programmiersprache ist **nicht** vorgesehen. Python-Zellen in diesem und den folgenden Notebooks sind daher **optional** und dienen nur zur Veranschaulichung."
   ]
  },
  {
   "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",
    "- Ein **Problem** ist eine allgemeine Fragestellung mit \"Leerstellen\" (z. B. \"Finde die kürzeste Route zwischen beliebigen Städten\").\n",
    "- Eine **Probleminstanz** ist eine konkrete Ausprägung dieses Problems mit festen Werten (z. B. \"Finde die kürzeste Route zwischen genau diesen 5 gegebenen Städten mit diesen Entfernungen\").\n",
    "- Probleminstanzen werden häufig **abstrahiert dargestellt**, um sie handhabbar zu machen, z. B. als:\n",
    "  - **Tabelle** (z. B. Entfernungstabelle zwischen Orten)\n",
    "  - **Graph** (Knoten = Objekte, Kanten = Beziehungen/Entfernungen)\n",
    "  - **Liste** (z. B. Liste von Gegenständen mit Gewicht und Wert)\n",
    "- Das Untersuchen mehrerer **Varianten** einer Probleminstanz hilft, **Symmetrien** und Muster zu erkennen, die spätere Lösungsstrategien vereinfachen können."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💡 Beispiel: Problem des Handlungsreisenden (TSP) als Graph\n",
    "**Problem:** Finde für eine beliebige Menge von Städten mit gegebenen paarweisen Entfernungen die kürzeste Rundreise, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt.\n",
    "\n",
    "**Probleminstanz:** 4 Städte A, B, C, D mit folgender Entfernungstabelle:\n",
    "\n",
    "| | A | B | C | D |\n",
    "|---|---|---|---|---|\n",
    "| A | – | 10 | 15 | 20 |\n",
    "| B | 10 | – | 35 | 25 |\n",
    "| C | 15 | 35 | – | 30 |\n",
    "| D | 20 | 25 | 30 | – |\n",
    "\n",
    "Diese Tabelle ist eine **abstrahierte Darstellung** – sie enthält nur die für das Problem relevanten Informationen (Entfernungen), keine Straßennamen, keine Geographie etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 1 – Problem oder Probleminstanz?\n",
    "Entscheidet für jede Aussage, ob es sich um ein **Problem** (allgemein) oder eine **Probleminstanz** (konkret) handelt, und begründet kurz:\n",
    "\n",
    "1. \"Packe möglichst wertvolle Gegenstände in einen Rucksack mit maximal 10 kg Tragkraft, wobei diese fünf Gegenstände zur Verfügung stehen: ...\"\n",
    "2. \"Packe möglichst wertvolle Gegenstände in einen Rucksack mit begrenzter Tragkraft.\"\n",
    "3. \"Finde den kürzesten Weg von Saarbrücken nach Trier im gegebenen Straßennetz.\"\n",
    "4. \"Finde in einem beliebigen Graphen den kürzesten Weg zwischen zwei beliebigen Knoten.\" "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Antworten hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 📝 Übung 2 – Symmetrien erkennen\n",
    "Betrachtet die Entfernungstabelle aus dem Beispiel oben.\n",
    "1. Welche strukturelle Eigenschaft erkennt ihr an der Tabelle bezüglich `Entfernung(A,B)` und `Entfernung(B,A)`? Was bedeutet das für die Anzahl der Rundreisen, die ihr tatsächlich unterscheiden müsst?\n",
    "2. Wie viele **verschiedene** Rundreisen (unter Berücksichtigung dieser Symmetrie) gibt es bei 4 Städten? Zählt systematisch."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*(Eure Antworten hier)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🐍 Optionale Veranschaulichung mit Python\n",
    "Die folgende Zelle listet alle möglichen Rundreisen für die obige Probleminstanz auf – nur zur Veranschaulichung, keine Pflichtaufgabe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "staedte = [\"A\", \"B\", \"C\", \"D\"]\n",
    "start = staedte[0]\n",
    "restliche = staedte[1:]\n",
    "\n",
    "rundreisen = list(permutations(restliche))\n",
    "print(f\"Anzahl möglicher Rundreisen (ohne Symmetriebetrachtung): {len(rundreisen)}\")\n",
    "for reise in rundreisen:\n",
    "    print(start, \"->\", \" -> \".join(reise), \"->\", start)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🚀 Zusatzaufgabe\n",
    "Formuliert selbst ein Problem und eine dazu passende Probleminstanz aus einem Kontext eurer Wahl (z. B. Stundenplanung, Einkaufstour, Gruppeneinteilung)."
   ]
  }
 ],
 "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
}
