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.

• Klasse 12
• Informatik Oberstufe: Von Algorithmen zur vernetzten Gesellschaft
• 4 Aktivitäten
• 35 Min.–50 Min.

Lernziele

1. Klassifizieren Sie gegebene Probleme anhand ihrer Laufzeitkomplexität in die Klassen P und NP.
2. Vergleichen Sie die Lösbarkeit von Problemen der Klasse P und NP unter Berücksichtigung theoretischer und praktischer Grenzen.
3. Analysieren Sie die Auswirkungen des P-NP-Problems auf konkrete Anwendungsbereiche wie die Kryptographie.
4. Bewerten Sie die Bedeutung der Komplexitätstheorie für die Entwicklung effizienter Algorithmen in der Informatik.

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.

Vorbereitung & Details

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.

Setup: Zwei sich gegenüberstehende Teams, Sitzplätze für das Publikum

Materials: Thesenkarte für die Debatte, Recherche-Dossier für jede Seite, Bewertungsbogen für das Publikum, Stoppuhr

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

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.

Vorbereitung & Details

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.

Setup: Flexibler Raum für verschiedene Gruppenstationen

Materials: Rollenkarten mit Zielen und Ressourcen, Spielwährung oder Token, Rundenprotokoll

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

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.

Vorbereitung & Details

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.

Setup: Zwei sich gegenüberstehende Teams, Sitzplätze für das Publikum

Materials: Thesenkarte für die Debatte, Recherche-Dossier für jede Seite, Bewertungsbogen für das Publikum, Stoppuhr

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

Fallstudienanalyse

⏱ 35 Min.·Einzelarbeit

Fallstudienanalyse: Kryptographie

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

Vorbereitung & Details

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.

Setup: Gruppentische mit Platz für die Fallunterlagen

Materials: Fallstudien-Paket (3-5 Seiten), Arbeitsblatt mit Analyseraster, Präsentationsvorlage

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

Dieses Thema unterrichten

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.

Was Sie erwartet

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

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Nach der Gruppenanalyse P- und NP-Beispiele lassen Sie die Schülerinnen und Schüler zwei Problembeschreibungen klassifizieren und ihre Entscheidung mit Laufzeit- oder Verifizierbarkeitsargumenten begründen.

Diskussionsfrage

Nach der Debatte P=NP? stellen Sie die Frage: 'Welche drei Bereiche würden sich am stärksten verändern, wenn P=NP morgen bewiesen würde?' Fordern Sie die Schüler auf, ihre Antworten mit Beispielen aus der Fallstudie Kryptographie oder anderen Aktivitäten zu stützen.

Kurze Überprüfung

Während der Simulation TSP-Modellierung geben Sie eine Liste von Problemen vor und lassen die Schülerinnen und Schüler die NP-vollständigen identifizieren. Sie sollen kurz erklären, warum diese nicht trivial lösbar sind – etwa durch Verweis auf die Modellierungsaktivität.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Gruppen auf, ein reales NP-Problem aus dem Alltag zu identifizieren und ein Modell dazu zu erstellen.
• Geben Sie Schülerinnen und Schülern, die unsicher sind, vorstrukturierte Beispiele mit Hinweisen zur Klassifizierung.
• Vertiefen Sie die Fallstudie Kryptographie durch einen Vergleich historischer Verschlüsselungsmethoden mit modernen Ansätzen.

Schlüsselvokabular

Polynomialzeit (P)	Eine Klasse von Entscheidungsproblemen, die von einem Algorithmus in Zeit gelöst werden können, die durch ein Polynom der Eingabegröße begrenzt ist. Diese Probleme gelten als effizient lösbar.
Nichtdeterministische Polynomialzeit (NP)	Eine Klasse von Entscheidungsproblemen, bei denen eine gegebene Lösung in Polynomialzeit überprüft werden kann. Dies bedeutet nicht, dass sie in Polynomialzeit gelöst werden können.
P-NP-Problem	Die zentrale offene Frage der theoretischen Informatik, ob für jedes Problem in NP auch ein Algorithmus existiert, der es in Polynomialzeit löst (also ob P = NP gilt).
NP-vollständiges Problem	Ein Problem, das sich in NP befindet und für das jedes andere Problem in NP in Polynomialzeit reduziert werden kann. Ihre Lösung würde beweisen, dass P = NP.