Komplexität und praktische Grenzen

Complexity and Practical Limits

Informatik Klasse 12 14 Aufgaben

InformatikKomplexitätWirkungsgradKerncurriculum

Manche Probleme sind lösbar, aber ihre besten bekannten Algorithmen wachsen exponentiell: Pro zusätzlichem Element verdoppelt sich die Arbeit (2ⁿ), und keine denkbare Hardware holt das ein — nachrechenbar an Rundreise- und Passwortbeispielen. Effizient lösbar (polynomiell, Klasse P) ist zu unterscheiden von „Lösung schnell prüfbar" (Klasse NP); ob beide zusammenfallen, ist die offene P-NP-Frage. Die produktive Wendung: Moderne Verschlüsselung funktioniert gerade deshalb, weil bestimmte Probleme praktisch unlösbar sind, und Heuristiken liefern gute statt perfekter Lösungen.

Voraussetzungen (1)

Algorithmen-Effizienz und Laufzeit

Klasse 11

›

Leicht

Multiple Choice #1 18s ▶ Testen

Ein Algorithmus hat die Laufzeit O(2ⁿ). Was passiert mit der Rechenzeit, wenn die Eingabe um EIN Element wächst?

● Sie verdoppelt sich ungefähr
○ Sie wächst um einen festen Betrag
○ Sie bleibt fast gleich

Exponentiell heißt multiplikativ — jedes weitere Element verdoppelt die Arbeit. Von n = 50 auf n = 60 wächst die Zeit um den Faktor 2¹⁰ ≈ 1000.

Wahr / Falsch #2 18s ▶ Testen

Ein tausendmal schnellerer Computer macht einen exponentiellen Algorithmus für deutlich größere Eingaben praktikabel.

✓ Falsch

Falsch — Faktor 1000 ≈ 2¹⁰ schafft bei O(2ⁿ) nur etwa zehn zusätzliche Elemente. Gegen exponentielles Wachstum hilft bessere Hardware fast nichts; es braucht bessere Algorithmen oder Abstriche.

Lückentext #3 20s ▶ Testen

Ein Passwort aus Kleinbuchstaben wird um EIN Zeichen verlängert. Um welchen Faktor wächst die Anzahl der Möglichkeiten beim Durchprobieren? (Alphabet: 26 Buchstaben)

✓ Antwort: 26

Jede zusätzliche Stelle multipliziert die Möglichkeiten mit 26 — deshalb macht Länge Passwörter so viel stärker als Sonderzeichen allein.

Multiple Choice #4 20s ▶ Testen

Das Rundreiseproblem (kürzeste Tour durch n Städte) per Durchprobieren aller Reihenfolgen: Warum scheitert das schon bei wenigen Dutzend Städten?

● Die Anzahl der Touren wächst schneller als exponentiell — schon 25 Städte ergeben mehr Touren, als ein Rechner in Jahrmillionen prüfen kann
○ Die Entfernungen lassen sich nicht genau genug messen
○ Computer können keine Landkarten verarbeiten

Die Tourenzahl wächst fakultätsartig: bei n Städten (n − 1)!/2 Touren. 25 Städte ergeben 24!/2 ≈ 3 · 10²³ Touren — bei einer Milliarde Touren pro Sekunde rund 10 Millionen Jahre. (Bei 20 Städten wären es noch knapp 2 Jahre.) Das Problem ist lösbar, aber das vollständige Durchprobieren ist praktisch aussichtslos.

Multiple Choice #5 20s ▶ Testen

Ein Schlüssel hat 128 Bit. Ein Angreifer probiert pro Sekunde 10¹² Schlüssel. Wie lange braucht er, um alle durchzuprobieren?

○ Etwa 128 Sekunden
● Etwa 10¹⁹ Jahre
○ Etwa ein Jahr

128 Bit ergeben 2¹²⁸ ≈ 3,4 · 10³⁸ Schlüssel. Bei 10¹² pro Sekunde sind das ≈ 3,4 · 10²⁶ Sekunden, also rund 10¹⁹ Jahre — weit mehr als das Alter des Universums. Darauf ruht die Sicherheit: Mit Schlüssel ist die Rechnung leicht, ohne Schlüssel kennt man nur Verfahren, deren Aufwand mit der Schlüssellänge explodiert. Bewiesen ist diese Schwere nicht — die praktische Grenze wird zum Schutzschild.

Wahr / Falsch #6 15s ▶ Testen

Ein praktisch unlösbares Problem ist dasselbe wie ein prinzipiell unentscheidbares Problem.

✓ Falsch

Falsch — praktisch unlösbar heißt „lösbar, aber untragbar langsam"; unentscheidbar heißt „durch kein Programm lösbar, egal wie langsam". Zwei verschiedene Grenzen.

Multiple Choice #7 20s ▶ Testen

Ein Paketdienst muss täglich eine gute Route durch 80 Orte finden — optimal ist praktisch unerreichbar. Was tun Informatiker in solchen Fällen?

● Heuristiken einsetzen, die schnell eine gute (nicht beweisbar beste) Route liefern
○ Das Problem für unlösbar erklären und würfeln
○ Auf schnellere Computer warten

Der Standard-Umgang mit harten Problemen — Näherungsverfahren und Faustregeln liefern in Sekunden Lösungen, die nah am Optimum liegen.

Lückentext #8 12s ▶ Testen

Laufzeiten wie n oder n² heißen polynomiell, Laufzeiten wie 2ⁿ heißen ___.

✓ Antwort: exponentiell

Die Trennlinie der Komplexitätstheorie — polynomiell gilt als effizient, exponentiell als praktisch unbrauchbar für große Eingaben.

Mittel

Multiple Choice #1 20s ▶ Testen

Was zeichnet die Problemklasse P aus?

● Probleme, die ein Algorithmus in polynomieller Zeit lösen kann — sie gelten als effizient lösbar
○ Probleme, die nur Profis lösen können
○ Probleme, die parallel gelöst werden müssen

Polynomiell (n, n², n³ …) wächst zahm genug, dass größere Eingaben beherrschbar bleiben — die praktische Trennlinie zu exponentiell.

Multiple Choice #2 25s ▶ Testen

Was zeichnet die Klasse NP anschaulich aus?

● Eine vorgelegte Lösung lässt sich schnell PRÜFEN — auch wenn das FINDEN einer Lösung womöglich sehr lange dauert
○ Diese Probleme kann kein Computer lösen
○ Die Probleme brauchen keinen Speicher

Beispiel Rundreise: Ob eine vorgelegte Tour kürzer als 500 km ist, prüft man im Nu — eine solche Tour zu FINDEN ist das Schwere. Prüfen leicht, Finden schwer: das ist NP.

Wahr / Falsch #3 15s ▶ Testen

Die Frage, ob P = NP gilt — ob also jedes schnell prüfbare Problem auch schnell lösbar ist — ist bis heute unbeantwortet.

✓ Wahr

Richtig — sie ist das berühmteste offene Problem der Informatik, mit einem Millionenpreis dotiert. Die meisten Fachleute vermuten P ≠ NP, bewiesen ist es nicht.

Multiple Choice #4 25s ▶ Testen

Ein Verfahren prüft alle Teilmengen einer n-elementigen Menge. Wie viele sind das — und was folgt daraus?

● 2ⁿ — schon bei n = 80 mehr Fälle, als ein Rechner in Jahrtausenden durchprobieren kann
○ n² — das ist gut machbar
○ n! geteilt durch 2 — also die Hälfte aller Fälle

Jedes Element ist drin oder draußen — 2ⁿ Kombinationen. 2⁸⁰ ≈ 1,2 · 10²⁴: selbst bei einer Billion Fällen pro Sekunde rund 38 000 Jahre. (2⁶⁰ dagegen schafft so ein Rechner in knapp zwei Wochen.) Vollständiges Durchsuchen von Teilmengen ist der Prototyp exponentieller Verfahren.

Wahr / Falsch #5 15s ▶ Testen

Für ein Problem in NP gilt: Wer eine Lösungsidee (ein „Zertifikat") vorgelegt bekommt, kann sie in polynomieller Zeit auf Richtigkeit prüfen.

✓ Wahr

Richtig — genau das ist die Definition von NP über das schnelle Prüfen vorgelegter Lösungen.

Multiple Choice #6 25s ▶ Testen

Sudoku in Riesengröße gilt als hartes Problem: Lösungen sind schnell zu prüfen, aber kein bekannter Algorithmus findet sie für alle Fälle schnell. Zu welcher Klasse gehört es damit sicher?

● NP — ob es auch in P liegt, weiß niemand
○ P — Sudokus stehen ja in Zeitungen
○ Weder P noch NP

Schnelle Prüfbarkeit sichert NP-Mitgliedschaft. Ob ein schneller Lösungsalgorithmus existiert, ist gerade die offene P-NP-Frage.