Informatik · Klasse 12

Ideen für aktives Lernen

Komplexitätstheorie: P und NP

Aktives Lernen wirkt hier besonders gut, weil die Komplexitätstheorie abstrakte Konzepte wie Polynomialzeit und Verifizierbarkeit mit konkreten, greifbaren Problemen verbindet. Durch Simulationen und Debatten werden theoretische Grenzen der Berechenbarkeit für die Lernenden erfahrbar und verständlich.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren und Vernetzen
• KMK: Sekundarstufe II - Beurteilen und Bewerten

• 35–50 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• Debatte
• 45 Min. · Kleingruppen

Gruppenanalyse: P- und NP-Beispiele

Teilen Sie reale Probleme aus wie Sortieren (P) und Sudoku (NP) aus. Gruppen klassifizieren sie, begründen mit Laufzeitbeispielen und präsentieren. Schließen Sie mit Plakatierung ab.

Warum sind manche Probleme trotz moderner Hardware nicht in akzeptabler Zeit lösbar?

Moderationstipp

Fordern Sie die Gruppen bei der Gruppenanalyse auf, ihre Beispiele zunächst auf Kärtchen zu notieren, um die Klassifizierung durch Umordnen zu visualisieren.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern zwei Problembeschreibungen (z.B. Sortieren einer Liste, Finden des kürzesten Weges in einem Graphen). Bitten Sie sie, zu jedem Problem zu entscheiden, ob es wahrscheinlich zu P oder NP gehört, und ihre Entscheidung kurz zu begründen, indem sie auf die Laufzeit oder Überprüfbarkeit eingehen.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Entscheidungsfähigkeit

Aktivität 02

• Planspiel
• 50 Min. · Partnerarbeit

Planspiel: TSP-Modellierung

Nutzen Sie Karten mit Städten. Gruppen finden heuristische Touren, messen Zeit und vergleichen mit optimaler Lösung. Diskutieren Sie NP-Härte durch Skalierung.

Differentiieren Sie zwischen Problemen der Klasse P und NP.

Moderationstipp

Verteilen Sie beim TSP-Modellierungsspiel zunächst kleine Graphen, bevor Sie zu komplexen Beispielen übergehen, um Frustration zu vermeiden.

Worauf zu achten ist

Stellen Sie die Frage: 'Wenn morgen bewiesen würde, dass P=NP ist, welche drei Bereiche der Informatik oder der Gesellschaft würden sich dadurch am dramatischsten verändern und warum?' Fordern Sie die Schüler auf, ihre Antworten mit Beispielen zu untermauern.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Aktivität 03

• Debatte
• 40 Min. · Ganze Klasse

Debatte: P=NP?

Teilen Sie Klasse in Für- und Gegenpositionen. Jede Seite bereitet Argumente vor, inklusive Kryptographie-Beispiele. Moderierte Runde mit Abstimmung.

Analysieren Sie die Bedeutung des P-NP-Problems für die Kryptographie und die Informatik.

Moderationstipp

Setzen Sie bei der Debatte klare Redezeiten pro Position, um eine ausgewogene Diskussion zu gewährleisten.

Worauf zu achten ist

Zeigen Sie eine Liste von Problemen (z.B. Sudoku lösen, Primfaktorzerlegung, kürzeste Pfadfindung, Textsuche). Bitten Sie die Schüler, die Probleme zu identifizieren, die typischerweise als NP-vollständig gelten, und kurz zu erklären, warum sie nicht trivial lösbar sind.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Entscheidungsfähigkeit

Aktivität 04

• Fallstudienanalyse
• 35 Min. · Einzelarbeit

Fallstudienanalyse: Kryptographie

Analysieren Sie RSA-Verschlüsselung. Individuen recherchieren NP-Aspekte, teilen in Runde und bewerten Auswirkungen bei P=NP.

Warum sind manche Probleme trotz moderner Hardware nicht in akzeptabler Zeit lösbar?

Moderationstipp

Lassen Sie bei der Fallstudie Kryptographie die Schülerinnen und Schüler zunächst eigene Schlüssel generieren, bevor sie deren Sicherheit diskutieren.

Worauf zu achten ist

Geben Sie den Schülerinnen und Schülern zwei Problembeschreibungen (z.B. Sortieren einer Liste, Finden des kürzesten Weges in einem Graphen). Bitten Sie sie, zu jedem Problem zu entscheiden, ob es wahrscheinlich zu P oder NP gehört, und ihre Entscheidung kurz zu begründen, indem sie auf die Laufzeit oder Überprüfbarkeit eingehen.

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Unterrichten Sie dieses Thema durch eine Mischung aus hands-on Modellierung und konzeptioneller Reflexion. Vermeiden Sie trockene Definitionen – stattdessen sollten Schülerinnen und Schüler selbst erleben, wie sich Laufzeiten bei wachsender Eingabe verändern. Nutzen Sie grafische Darstellungen wie Laufzeitdiagramme, um exponentielles Wachstum sichtbar zu machen. Akzeptieren Sie, dass Unsicherheit wie bei P=NP einen wichtigen Teil des Lernprozesses darstellt und nicht als Wissenslücke interpretiert werden sollte.

Erfolgreiches Lernen zeigt sich darin, dass Schülerinnen und Schüler P- und NP-Probleme sicher klassifizieren, ihre Entscheidungen begründen und die praktischen Konsequenzen exponentiellen Wachstums erklären können. Sie sollten zudem die Bedeutung der offenen Frage P=NP für die Informatik reflektieren.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Gruppenanalyse P- und NP-Beispiele beobachten Sie...

  Verweisen Sie auf die praktischen Tests mit Sudoku oder dem Rucksackproblem: Lassen Sie die Gruppen schnell überprüfen, ob eine gegebene Lösung korrekt ist, aber bewusst lange nach Lösungen suchen. So wird der Unterschied zwischen Verifizierbarkeit und Lösbarkeit erfahrbar.

• Während der Debatte P=NP? beachten Sie...

  Nutzen Sie die Unsicherheit als Lerngelegenheit: Die Gruppen sollen explizit benennen, welche Annahmen zu ihren Schlussfolgerungen führen. Betonen Sie, dass mathematische Beweise oft Jahrzehnte in der Entwicklung sind.

• Während der Simulation TSP-Modellierung beobachten Sie...

  Zeigen Sie auf, wie Dijkstras Algorithmus für kürzeste Pfade polynomial läuft – selbst bei großen Graphen. Lassen Sie die Schülerinnen und Schüler die Laufzeitunterschiede zwischen exakter Lösung und Heuristiken selbst messen.

---

In dieser Übersicht verwendete Methoden

• Debatte
• Planspiel
• Fallstudienanalyse