Informatik: Theoretische Informatik; Weilburg XII/111 Berechenbarkeit (Eine Unterrichtsreihe für Q3)

Informatik: Theoretische Informatik; Weilburg XII/11 1

Berechenbarkeit

(Eine Unterrichtsreihe für Q3)


Gliederung

• Algorithmen mit exponentieller Laufzeit• Vergleich von exponentieller und polynomialer Laufzeit • P und NP Probleme• Berechenbarkeit

Beispiele und KlassifizierungÜberabzählbarkeit von ProblemenGrenzen der Berechenbarkeit (Halteproblem)

• Übungen

Das Abgeordnetenproblem

Die Abgeordneten eines Parlaments gehören n verschiedenen Ausschüssen an. Jeder Ausschuss tagt jede Woche genau einmal. Ist ein Abgeordneter Mitglied in zwei verschiedenen Ausschüssen, so dürfen diese nicht zur gleichen Zeit stattfinden. Wir möchten wissen, ob wir mit k verschiedenen Sitzungsterminen auskommen.Lösen Sie dieses Färbungsproblem für den folgenden Graphen mit 12 Ausschüssen (Knoten):


Der Algorithmus geht alle Färbemöglichkeiten durch und testet dabei jede einzelne, ob die Bedingung (zwei Knoten, die verbunden sind, haben nicht dieselbe Farbe) erfüllt ist.


Allgemeine Lösung mit einem Algorithmus

2

n

Für k=3 ergibt sich damit die folgenden Anzahl von Überprüfungen:

nnn3

2

1

nkFärbemöglichkeiten bei k Farben und n Ausschüssen:

Prüfung der Bedingung bei jeder Färbung:


ZeitkomplexitätGrundlage: Computer mit 1 Milliarde Rechenschritte pro Sekunde; k=3.

Knoten 12 20 30 50

Laufzeit 0,03 sec 11,04 min 2,84 Jahre ca. 27 Mrd. Jahre

Vergleich zwischen Polynomial- und Exponentiallaufzeit (in sec):

T(n) 20 30 40 50 100 1000

n 2*10-8 3*10-8 4*10-8 5*10-8 0,0000001 0,000001

n2 4*10-7 9*10-7 1,6*10-6 2,5*10-6 0,00001 0,001

n5 0,0032 0,0243 0,1024 0,3125 10 1000000

2n 0,001049 1,073742 1099,512 1125900 1,2*1021 1,1*10292


ZeitkomplexitätSelbst bei einem Rechner, der 1000mal schneller ist, würde sich das Problem nicht anders darstellen.

Bespiel: Bei T(n)=2n hat ein Rechner bei n=40 1099sec = 18Minuten benötigt. Welchen Umfang n bewältigt ein Rechner der 1000mal schneller ist in derselben Zeit?

4910991010

239

nn

Der Umfang nimmt nur um log2(1000)9,97 zu

Ergebnis: Man unterscheidet Algorithmen bezüglich ihrer Laufzeit folgendermaßen

berechenbar und durchführbar(polynomiale Laufzeit)

berechenbar, aber nicht durchführbar (exponentielle Laufzeit)


P und NP- Probleme

Die Komplexität der Lösungsalgorithmen eignet sich gut, um die Probleme in Klassen einzuteilen.

Def.: Alle Probleme, die in polynomialer Zeit mit deterministischen Algorithmen gelöst werden können heißen P-Probleme.

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nach jedem Schritt genau ein weiterer folgt und das Problem nach endlich vielen Schritten gelöst ist.

Def.: Ein Problem welches von einem nichtdeterministischen Algorithmus in polynomialer Zeit gelöst werden kann, heißt NP-Problem.


P und NP- Probleme

• es sind Lösungsverfahren mit exponentiellem Aufwand bekannt

• ein effizienterer Algorithmus ist bislang nicht bekannt

• die Lösung ist durch Raten (also nichtdeterministisch) zu ermitteln

• Da jedes P-Problem per se auch NP ist, sind die P-Probleme zumindest eine Teilmenge von NP-Problemen.

NP-Probleme haben meist folgende Eigenschaften:

Eine derzeit nicht gelöstes Problem ist die Frage, ob die beiden Klassen P und NP gleich sind, oder ob die P-Probleme eine echte Teilmenge der NP-Probleme sind.


Grenzen der BerechenbarkeitLange Zeit glaubten Philosophen und Mathematiker, dass jedes mathematische Problem algorithmisch lösbar sei.

Zwei mathematische Probleme im Vergleich:

Eine gerade Zahl n4 hat die Goldbach-Eigenschaft, wenn sich die Zahl als Summe zweier Primzahlen darstellen lässt.

Beispiel:

10 = 7 + 3

Man startet mit einer beliebigen Zahl. Ist die Zahl ungerade, so ist die Folgezahl das Dreifach der Zahl, erhöht um 1. Ist die Zahl gerade, so ist die Folgezahl die Hälfte dieser Zahl.

Die Startzahl heißt wundersam, falls die Folge irgendwann auf die 1 stößt.

Beispiel:

516 8 4 2 1


Exkurs – wundersame Zahlen

Wenn man den Algorithmus mit beliebig großen Zahlen ausprobiert, stellt man fest, dass er eine wild aussehenden Zahlenfolge durchlaufen kann, die erstaunlich hohe Werte annimmt und unvorhersehbar schwankt. Dabei wurde nie eine Periodizität festgestellt, mit der man eine Eingabe als nichtwundersam identifizieren könnte.

Algorithmus für wundersame Zahlen:

1. Solange x1 mache folgendes

1.1 falls x gerade ist, setze x x/2

1.2 falls x ungerade ist, setze x 3x+1

2. halte an.

Die wundersamen Zahlen sind damit ein seit über 60 Jahren ungelöstes Problem aus der Zahlentheorie


Entscheidbarkeit

Def.: Ein Problem ist eine Funktion f: IN IN

In unseren Beispielen wäre f eine Funktion mit der Wertemenge {0,1}. 1 bedeutet, dass die Zahl die jeweilige Eigenschaft hat; 0, dass die Funktion die Eigenschaft nicht hat. Ein solches Problem heißt auch Entscheidungsproblem.Im Fall des Goldbachproblems gibt es einen Algorithmus, der feststellt, ob eine Zahl die Goldbacheigenschaft hat oder aber nicht. Das Goldbachproblem ist damit entscheidbar.

Im Fall der wundersamen Zahl gibt es bis jetzt nur einen Algorithmus, der bei wundersamen Zahlen zur Ausgabe 1 kommt. Gibt man eine unwundersame Zahl ein, kommt der Algorithmus zu keinem Ende. Das Problem der wundersamen Zahlen ist damit semi-entscheidbar.


Gibt es mehr Probleme als Programme?

• Für die Lösung eines Problems muss der Funktionswert berechnet werden, dazu benötigt man einen Algorithmus.

• Der Algorithmus besteht aus Buchstaben, Zahlen und Sonderzeichen, diese sind letztendlich eine Folge aus 0 und 1, also ist ein Programm eine Zahl aus IN. Somit gibt es nur so viele Programme wie Zahlen in IN.

• Wie viele Probleme, d.h. wie viele Funktionen f: IN IN gibt es?

• Da allein der Definitionsbereich eine Teilmenge von IN ist, gibt es mindestens so viele Funktionen wie Teilmengen von IN.

Def.: Die Menge aller Teilmengen von M heißt die Potenzmenge P(M)


Abzählbar und überabzählbar

Def.: Eine Menge M ist „gleichmächtig zu IN“, wenn man die Elemente von M durchnumerieren kann: M = {m1, m2, m3, ...}. Statt ‘M ist gleichmächtig zu IN’ sagen wir auch: ‘M ist abzählbar unendlich’.

Gegeben sei die Menge A ={a, b, c}a) Bestimmen Sie P(A). (Auch die leere Menge ist eine Teilmenge

von A.)b) Füge der Menge A ein weiteres Element hinzu und bestimme für

die so entstehende Menge A’ wiederum die Menge aller Teilmengen!

c) Eine Menge M habe n Elemente. Wie viele Teilmengen hat M?

Fazit: |P(M)|=2n

Lösung:P(A)={ {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} |P(A)|=8fügt man ein Element d hinzu, verdoppelt sich die Anzahl der Elemente.


Beweis durch Widerspruch

Annahme: P(IN) ist abzählbar unendlich

Satz: P(N) ist nicht abzählbar unendlich.

• Man kann die Teilmengen von IN durchnumerieren P(IN) = {T1, T2, T3, ...}

• Die Nummer i einer Teilmenge kann nun als Zahl in der Teilmenge Ti vorkommen oder nicht.

• Fassen wir alle Zahlen zusammen, die in ihrer entsprechenden Teilmenge nicht enthalten sind: D = {iIN: iTi}.

• D ist eine Zahlenmenge, also DIN. Damit muss D eine der Teilmengen T sein, z.B. sei D = Tn.

• Was ist nun mit der Zahl n? • Ist nD, so ist n Tn. Folgt: D Tn .• Ist nD, so ist nTn. Folgt: D Tn • Beides steht im Widerspruch zu D = Tn. • Die Annahme ist demnach falsch. • Resultat: Die Potenzmenge der natürlichen Zahlen ist nicht abzählbar


Fazit

• Die Menge aller Programme ist eine unendliche Teilmenge von IN, also abzählbar.

• Die Menge aller Probleme ist mindestens so groß wie die Potenzmenge von IN, also nicht abzählbar.

• Es gibt mehr Probleme als Programme.

Die Menge der Algorithmen reicht nicht aus, um jede Funktion zu berechnen. Es gibt also nichtberechenbare Funktionen bzw. unlösbare Probleme

Ein typisches algorithmisch unlösbares Problem ist das Halteproblem


Das Halteproblem

Hinter dem Halteproblem verbirgt sich die Frage, ob ein Algorithmus formuliert werden kann, der für ein gegebenes beliebiges Programm mit einer gegebenen Eingabe überprüft, ob dieses Programm terminiert oder nicht.Die Problematik des Halteproblems ist den Schülern seit dem Umgang mit while-Schleifen oder Rekursion vertraut.

Turing hat 1936 bewiesen, dass ein solcher Algorithmus nicht existiert


Das Halteproblem

Das Problem ist eine Funktion f: IN IN mit

sonst

enthälteifeEndlosschleinePfallsPf

,0

,1)(

Angenommen es gebe einen Algorithmus, der imstande wäre f(P) zu berechnen und würde damit einer Variablen endlos den Wert true oder false zuweisen:

Haelt(P, x) //weise nach Test endlos den Wert true oder false zu wenn endlos=true dann Ausgabe(„Das Progamm enthält eine Endlosschleife“) sonst Ausgabe(„Das Progamm enthält keine Endlosschleife“)


Das Halteproblem

Das Programm Haelt kann man jetzt ein klein wenig verändern:Seltsam(P, x) //weise nach Test endlos den Wert true oder false zu wenn endlos=true dann Gebeaus(„Das Progamm enthält eine Endlosschleife“) sonst Gebeaus(„Das Progamm enthält keine Endlosschleife“) und solange 1==1 führe aus keine Aktion

Der Unterschied zwischen den beiden Programmen ist lediglich die eingebaute Endlosschleife.

Wendet man nun Seltsam auf Seltsam an. Was kann passieren?1. Angenommen Seltsam terminiert endlos = false das Programm geht in eine Endlosschleife.2. Angenommen Seltsam terminiert nicht endlos = true Ausgabe „Das Progamm terminiert nicht“ und das Programm stoppt

Wir erhalten also jeweils einen Widerspruch Es gibt keinen Algorithmus Haelt


Zusammenfassung


Quellen:

• Battenfeld u.a.: Theoretische Informatik – Planung eines Kurses in der Jahrgangsstufe 13I, 1996

• David Harel: Das Affenpuzzle und weitere bad news aus der Computerwelt, 2002

• Duden: Informatik Abitur – Basiswissen Schule, 2003 • Niedermeier, Rolf u.a.: Das Knotenüberdeckungsproblem, Log in 146/147,

S53ff • Steinert, Markus: Grenzen der Berechenbarkeit, Log in 168 S.42ff• Schwill, Andreas: Praktisch unlösbare Probleme, Log in 14, S. 16ff• Hromkovic, Juraj: Sieben Wunder der Informatik, 2006

Documents

Informatik: Theoretische Informatik; Weilburg XII/111 Berechenbarkeit (Eine Unterrichtsreihe für Q3)