Eine kurze Einfuhrung in die Informatik

Irene Rothe

Sommer 2009

Was ist Informatik? Informatik ist das Losen von Problemenmit Hilfe des Rechners.

Was fur Probleme konnten wir haben, die ein Rechnerprogramm fur uns losen soll? Zum

Beispiel die folgenden:

• Wie werde ich schnell sehr reich?

• Wie bekomme ich meine CD-Sammlung sortiert?

• Wie erhalte ich die kurzeste Autofahrstrecke zwischen allen Stadten in Deutschland

mit mehr als 20.000 Einwohnern?

• Ein Dieb bricht in einem Kaufhaus ein und will in seinem Rucksack Waren von

maximalem Gesamtwert wegschleppen. Welche Waren soll er einpacken?

• Ist eine beliebige gegebene Zahl eine Primzahl?

• Kommen inπ irgendwann mal 99 Siebenen hintereinander vor?

• Kann ein Compiler sich selbst ubersetzen?

• Wie berechne ich eine ganzzahlige Losungenx, y, z der Gleichung

x4 + y2 − z + 27x − 8z = 0?

• Wie kann ich auf mein Bankkonto sicher ubers Internet zugreifen?

• Wie kann ich auf fremde Bankkonten zugreifen und mir selbst das Geld von anderen

uberweisen?

1

Obige Probleme haben unterschiedliche Eigenschaften. Bedauerlicherweise gibt es vie-

le Probleme, die gar nicht mit einem Rechner losbar sind. Warum und welche Eigenschaf-

ten des Problems eine Losung mit dem Rechner zunichte machen, ist ein wichtiges Gebiet

der Informatik (Berechenbarkeit).

Ebenso gibt es eine Menge Probleme, die nicht invernunftigerZeit mit dem heutigen

Typ Rechner (mit Strom und Transistoren arbeitend) zu losen sind (Komplexit at). Aber

das ist fur manche Probleme sogar gut fur uns (Kryptografie ).

Am Ende bleiben dann die Probleme ubrig, mit denen wir einenRechner futtern konnen.

Das sind die Probleme, fur die wirAlgorithmenfinden, was ganz einfach so etwas wie eine

Anleitung ist: eine klare und endliche Beschreibung von Tatigkeitsschritten, die mecha-

nisch ausgefuhrt werden konnen.

• Was machen wir mit diesen Problemen?

• Warten wir bis jemand mehr uber diese Probleme herausfindet?

• Oder suchen wir selbst nach einer Losung und werden beruhmt?

• Sind alle Probleme gleich gut losbar oder kann man sich manchmal mit Annahe-

rungslosungen behelfen?

Weitere wichtige Fragen tauchen beim Programmieren auf:

• Wird das Rechnerprogramm irgendwann fertig mit Rechnen undgibt ein Ergebnis

aus?

• Stimmt das erhaltene Ergebnis? Kann der Losung getraut werden? Hat das Programm

korrekt gerechnet?

Bringen wir ein bisschen Ordnung in obigen und allen anderenProblemen und teilen

sie ein in

• nicht losbare Probleme,

• mit mathematischen Hilfsmitteln aber nicht mit dem Rechnerlosbare Probleme,

• losbare, aber fur heutige Rechner nicht bewaltigbare Probleme und

• effizient mit einem Rechner losbare Probleme.

2

1 Nicht entscheidbare Probleme

Problem Programm-Uberprufungssystem

Ein Programm ist ein in einer Programmiersprache formulierter Algorithmus. In Program-

men sind sehr oft Fehler, weil Menschen eben Fehler machen. Deshalb ware ein Programm-

Uberprufungssystem eine wunderbare Sache.

Gesucht ist eine vollstandig automatisches Programmuberprufungssystem, dasjedes

beliebigesgegebenes Programm uberpruft und mit der Aussage PROGRAMM RICHTIG

oder einer Fehlerliste endet, wo z.B. auf eine Endlosschleife aufmerksam gemacht wird.

Das Programm-Uberprufungssystem ist selbst ein Programm. Wenn es selbst ein Pro-

gramm ist, dann konnte es sich auch gut selbst uberprufen. Das Programm-Uberprufungs-

system soll ja furalle Programme funktionieren. Hier steigt ein ungutes Gefuhl auf, dass

es so irgendwie nicht geht. Das fuhlt sich an, wie sich selbst an den Haaren aus dem

Sumpf ziehen. Weiterhin konnten wir das Programm-Uberprufungssystem selbst zu ei-

nem neuen Programm umbasteln, dass genau das Gegenteil von dem alten Programm-

Uberprufungsssystem tut. Es lauft unendlich lange (verfangt sich in einer Endlosschlei-

fe), wenn das alte Programm-Uberprufungssystem mit der Antwort RICHTIG endete und

gibt die Aussage RICHTIG aus, wenn eine Endlosschleife entdeckt wurde. Das so entstan-

dene neue Programm sollte auch von dem Programm-Uberprufungssystem nach Fehlern

untersucht werden konnen. Wer soll diesen Fehler aber finden? Das ursprungliche, ultima-

tive Programm-Uberprufungssystem sicher nicht. Mehr Informationen zu diesem Problem

kann in Buchern der Theoretischen Informatik unterHalteproblemgefunden werden.

Bemerkung: Ein vollautomatisches Programm-Uberprufungssystem wird es also nie

geben. Wenn man aber Einschrankungen an die zu uberprufenden Programme macht, kann

man fureinfacheProgramme Algorithmus-Uberprufungsprogramme bauen, die nach Feh-

lern suchen und einige auch finden wurden.

Ein Problem, dass nicht entscheidbar ist, ist das folgende Problem:

Problem Diophantische Gleichungen

Gegeben ist z.B. das folgende Gleichungssystem:

x3 + 5y − 7z = uv2

u + v − y4 = z3 + 4

3

(x − y)2 − u = v − 1

Gesucht sind ganzzahlige Losungenx, y, z, u, v, die diese Gleichungen erfullen.

1970 hat Matijassewitsch mit 22 Jahren gezeigt, dass niemals ein allgemeines Losungs-

verfahren fur Diophantische Gleichungenf(x1, ..., xn) = 0 mit ganzzahligen Koeffizienten

und gesuchten ganzzahligen Losungen gefunden werden kann.

Hier ist noch ein nicht offenes (nicht losbares?) Problem:

Problem Suche nach Teilfolgen in der irrationalen Eulerzahl e

Es ist eine Zahlenfolge gegeben, und wir mochten wissen, obdiese Folge irgendwo ine

vorkommt. Fur die Berechnung vone gibt es Algorithmen, z.B. die Taylorreihenentwick-

lunge =∑∞

n=0

1

n!= 2.7181.... Wir berechnen alsoe immer um eine Stelle mehr und testen,

ob die gegebene Folge vorkommt. Ist z.B. die Folge 7182 gegeben, mussen wire nur bis zur

4. Stelle nach dem Komma berechnen, um zu sehen, dass die gegebene Folge tatsachlich in

e vorkommt. So lange wir wissen, bis zu welcher Stelle wire berechnen mussen, kann ein

Rechner dies auch in endlicher Zeit fur uns erledigen, da wir genau die Anzahl der Berech-

nungsschritte zahlen konnen. Bei manchen gegebenen Zahlenfolgen (wie eben) haben wir

Gluck, und die Folge kommt sehr weitvorn in e vor. Aber bei anderen gegebenen Folgen

kann das vielleicht sehr lange dauern, z.B. bei der Folge, die aus 99 Neunen hintereinander

besteht. Das Unangenehme an der Sache ist: Wir wissen nicht,wie lange wir auf ein Er-

gebnis warten mussen. Dae unendlich viele Zahlen ohne Perioden (Wiederholungen von

Zahlen ab einer bestimmten Kommastelle) nach dem Komma stehen hat, also eine irratio-

nale Zahl ist, kann die Suche nachUbereinstimmung vone mit der gegebenen Folge sehr,

sehr lange dauern, eventuell auch unendlich lange.

Bemerkung: Der Test, ob eine bestimmte Zahlenfolge eineAnfangsfolgevon e ist,

ist sehr wohl losbar. Ist z.B. die Zahlenfolge 271628 gegeben, berechnen wire bis zur 5.

Stelle nach dem Komma und uberprufen, ob die Zahlenfolge mit e ubereinstimmt. Das

ware bei obiger Folge der Fall und bei z.B. 272 nicht. Fur andere gegebene Folgen mussen

wir vielleicht sehr viele Stellen vone berechnen, aber immer konnen wir die Anzahl der

Berechnungsschritte genau vorher benennen, namlich in Abhangigkeit von der gegebenen

Folge. Und das sind immer endlich viele Schritte.

Jedes Problem kann so umgeformt werden, dass die Losung eine JA- oder NEIN-

Antwort ist (man denke nur an das Kinderspiel, wo man Tiere nur durch Ja/Nein-Fragen

4

errat). Diese Probleme heißenEntscheidungsprobleme. Erhalt man garantiert eine Losung,

die JA oder NEIN lautet, ist das Problementscheidbar. Erhalt man am Ende ein Ja und ein

Weiß-ich-nicht oder weder noch, sind die Problemesemi-entscheidbaroderunentscheid-

bar.

2 Der Begriff des Algorithmus

Intuitiv sind Problemeberechenbar, wenn wir eine Vorschrift zur Losung des Problems

aus einzelnen Anweisungen finden, die klar und eindeutig formuliert sind und deren An-

zahl endlich ist. Diese Vorschrift ist einAlgorithmus. Es besteht die Annahme, dass nur

berechenbare Probleme auf einem Rechner gelost werden konnen. Bis jetzt hat noch nie-

mand ein Problem gefunden, dass wir als intuitiv berechenbar empfinden, fur das aber keine

Anweisungsfolge gefunden wurde.

Uns interessieren jetzt nur noch Probleme, die mit einem Rechner losbar sind. Es muss

also ein Algorithmus gefunden werden, so dass der Rechner von Anweisung zu Anweisung

immer weiß, was er als nachstes tun soll. Das durfen nur endlich viele (aber durchaus sehr

viele) Schritte sein, und am Ende muss ein Ergebnis ausgegeben werden.

So ein Algorithmus wird oft in einer Programmiersprache formuliert. Die Program-

miersprache (Java, C++, C, Perl, php, ...) konnen nur berechenbare Probleme behandeln.

Algorithmusist ein intuitiver Begriff, der gleichgesetzt werden kann mit berechenbar

odervon einer Maschine ausfuhrbar. Ein Algorithmus ist ein:

• schrittweises Verfahren zur Bestimmung eines Ergebnissesausgehend von einer Ein-

gabegroße oder Eingabegroßen.

• Diese Anweisungsschritte mussen eindeutig formuliert sein, so dass sie der Rechner

ausfuhren kann.

• Es durfen nur endlich viele Anweisungen sein, dass heißt, der Algorithmus muss

irgendwann zu einem Ende mit Ergebnis kommen.

5

3 Ineffiziente berechenbare Probleme

Fur viele Probleme findet man, so sehr man sich auch anstrengt, nur sehr lang rechnende

(in Abhangigkeit von der Eingabegroße) Algorithmen. Oftmals braucht der Rechner fur die

Losung solcher Probleme langer, als unser Universum existiert (das Universum existiert ca.

1010 Jahre =365 ∗ 1011 Tage =876 ∗ 1012 Stunden =5256 ∗ 1013 Minuten =31536 ∗ 1013

Sekunden, was ca.3∗1017 Sekunden sind). So viel Zeit hat niemand, und es scheint nutzlos

zu sein, den Rechner uberhaupt zu bemuhen.

Man konnte sich auf die Suche nach einem praktikableren, also schnelleren Algorith-

mus machen. Aber bei einer bestimmten Art von Problemen scheint das einfach nicht

zu gelingen. Das laßt allerdings nicht die Schlussfolgerung zu, es gabe nicht doch einen

schnelleren Algorithmus, aber aus irgendwelchen Grundenist es der Menschheit bis heute

nicht gelungen, einen effizienten Algorithmus zu finden oderzu beweisen, dass es keinen

Zweck hat, nach einem zu suchen, weil es ihn nicht gibt.

Manchmal ist man aber auch froh, dass es bis jetzt keinen effizienten Algorithmus gibt,

z.B. zum Entschlusseln unserer Online-Banking-Daten. Dawiederum ware es wohltuend

zu wissen, dass niemand im stillen Kammerlein einen effizienten Entschlusselungsalgorith-

mus gefunden hat und am Werke ist, in dieser Minute unser Geldabzuheben.

Problem Handelssreisender

Stellen wir uns vor, wir wollen 20 Stadte in Deutschland so bereisen, dass wir den kurzesten

Weg zwischen den Stadten insgesamt fahren und am Ende wieder zu Hause ankommen.

Fur dieses Problem ist kein viel besserer Algorithmus bis heute bekannt, als alle Verbin-

dungsmoglichkeiten entfernungsmaßig auszurechnen unddann die kurzeste Strecke aus

diesen einzelnen Entfernungssummen zu suchen. Bei 20 Stadten gabe es20!/2 = 20 ∗ 19 ∗

18∗...∗2∗1/2 verschiedene Verbindungsmoglichkeiten (man teilt durch2, weil es bei einer

gefundenen Reise egal ist, wie rum man sie fahrt) und damit genauso viele Entfernungen,

was 2432900000000000000/2 Moglichkeiten entspricht. Nehmen wir an, dass unser Rech-

ner fur eine Berechnung10−9 Sekunden braucht dann, wurde dieses Programm immer noch

1216450000 Sekunden brauchen, was ungefahr 40000000 Minunten = 660000 Stunden =

27500 Tage = 75 Jahre waren. Hier kann uns auch ein 10 mal schnellerer Rechner nicht

viel glucklicher machen. So lange will niemand warten, um sich die garantiert kurzeste

Strecke zwischen 20 Stadten berechnen zu lassen. Es gibt einige sehr clevere Algorithmen,

6

die relativ vernunftig bis zu 2000 Stadten arbeiten, aberum Telefonnetze u.a. zu berechnen

ist eine Eingabengroße von 2000 viel zu wenig, um wirklich fur die Praxis nutzlich zu sein.

Eine Anwendung fur das gleiche Problem: Stellen wir uns vor, ein Bohrer soll Lotlocher

auf einer Leiterplatte bohren, wobei wir naturlich gerne hatten, dass der Bohrer so wenig

Zeit wie moglich verschwendet, um sich von Bohrposition zuBohrposition zu bewegen. Da

kommt schnell eine Bohrlochzahl von mehreren Tausenden zusammen. Man behilft sich in

solchen Fallen mit Approximationsalgorithmen, mit denenman gute Naherungslosungen

berechnet. Diese sind weit besser, als wenn man zufallig die nachste Position des Boh-

rers auswahlt. Bei diesen Approximationsalgorithmen haben wir aber eben keine Garantie,

dass sie diebesteLosung berechnet. Es ist moglich, dass eine bessere Reihenfolge fur die

Bohrungen gefunden werden kann.

Problem Rucksackpackungen

Ein Dieb bricht in ein Kaufhaus mit 1000 Waren ein. Er hat sicheinen sehr großen Ruck-

sack mitgebracht von einer bestimmten Große. Er will nun indiesen Rucksack Diebesware

von maximalem Wert einpacken. Er muss also aus den 1000 Warenwelche auswahlen, so

dass sie insgesamt in seinen Rucksack passen, dass aber der Wert der Waren auch hubsch

hoch ist, um nicht zu sagen, so hoch wie moglich. Sicher kanner erst mal auf alle Waren

verzichten, die sowieso nicht in seinen Rucksack passen, danach bleiben vielleicht noch

500 Waren ubrig. Welche wahlt er aus? Er konnte vorher zu Hause ein Programm laufen

lassen, dass diese Waren fur ihn auswahlt. Aber hier muss er mit Enttauschung feststellen,

dass das Programm sehr lange braucht, und das Kaufhaus bis dahin vielleicht schon pleite

ist. Der ineffiziente Algorithmus wurde einfach alle Moglichkeiten fur Warenkombinatio-

nen durchprobieren. Also eine der 500 Waren beliebig wahlen und aus den Waren, die noch

in den Rucksack passen wurden, zufallig weitere wahlen und jeweils den Gesamtwert be-

rechnen. Das wirkt ahnlich aufwendig wie das Handelsreisendenproblem. Programmierbar

ist dieser Algorithmus ohne Frage, aber man hatte nur Lust,auf Ergebnisse fur ein sehr

kleines Kaufhaus zu warten.

7

4 Wie bestimmt man die Laufzeit eines Algorithmus?

Ein Algorithmus besteht aus einzelnen Anweisungen. Diese Anweisungen werden einmal

oder mehrmals ausgefuhrt. Wie oft sie ausgefuhrt werden,ist abhangig von der der Ein-

gabe. Hat man einen speziellen Rechner im Auge, kann man in seinen technischen Daten

nachlesen, wie lange sein Prozessor fur eine Anweisung braucht. Dann muss man also

nur alle im Falle der Ausfuhrung des Algorithmus ausgefuhrten Anweisungen zahlen und

multipliziert sie mit der Zeit, die eine Anweisung dauert.

Bemerkung: Es wird angenommen, dass jede Anweisung konstante Rechenzeit braucht.

Wie entscheiden wir, was ein effizienter und was ein ineffizienter Algorithmus ist?

Im taglichen Leben haben wir uber die Jahre ein Gefuhl entwickelt, welche Geldanlage

wir von den folgenden auswahlen wurden:

t t t

Geld Geld Geld

Abbildung 1: Entwicklung von Geldanlagen.

Bei Geldanlagen vergeht die Zeit und wichtig ist fur uns dasGeld, das sich vermehrt.

Deshalb ist die Zeit die Eingabe und das Geld die Ausgabe der Geldentwicklungsfunktion.

Bei Algorithmen ist die Zeit die Große, die uns als Ergebnisinteressiert und die Eingabe

sind positive ganze Zahlen, z.B. Anzahl der zu ordnenden Bucher, Anzahl der Waren im

Kaufhaus, Anzahl von Stadten, Große des Zahlenschlussels bei einer Verschlusselung, ...

Von welchen Algorithmen der folgenden wurden wir die Finger lassen, da sie irrsinnig

lange rechnen?

Das linke Bild zeigt die Laufzeit eines ineffizienten Algorithmus und das ganz rech-

te Bild die vernunftige Laufzeit eines effizienten Algorithmus. Bei drei Algorithmen, die

Dinge sortieren sollen, hatte man beispielsweise folgende Laufzeiten in Abhangigkeit von

der Anzahl der zu sortierenden Dinge (z.B. Bucher oder Namen):

8

t t t

n n n

Abbildung 2: Aufwand von Algorithmen.

Anzahlderzu 10 50 100 1000

sortierendenDinge

Laufzeitfunktion : logn 1 1, 69 2 3

(linkesBild)

Laufzeitfunktion : n 10 50 100 1000

(mittleresBild)

Laufzeitfunktion : n2 100 2500 10000 1000.0000

Laufzeitfunktion : 2n 1024 1015 1030 riesig

(rechtesBild)

Laufzeitfunktion : n! 3.628.800 3.1064 riesig riesig

Rechnen wir das auf einen realen Rechner um, sind die Algorithmen mit Laufzeit2n und

n! vollkommen unpraktikabel.

Wo ist die Grenze? Ab welcher Laufzeitfunktion sagen wir, dass der Algorithmus inef-

fizient ist?

Die theoretische Informatik hat definiert, wenn die Laufzeitfunktion als Polynom dar-

gestellt werden kann, alsonk mit k >= 1 und n als Eingabegroße, dann spricht man von

einemeffizientenAlgorithmus. Die Laufzeitfunktionen konnen z.B. wie folgt aussehen:

n2, log n, n3

Die Eingabegroßen bleibt in der Basis und laßt bei steigender Eingabegroße die Lauf-

zeitfunktion nichtgar zu schnellwachsen. Das ist naturlich Geschmackssache, da z.B.n1000

auch eine sehr lange Laufzeit bedeutet.

Ist die Laufzeitfunktion aber exponentiell, alsokn mit k > 1 und n als Eingabe, dann

9

ist der Anstieg der Funktion bei wachsender Eingabegroße noch viel rasanter als eben, und

wir haben einen ineffizienten Algorithmus vor uns. Die Laufzeitfunktionen konnen, dann

z.B. wie folgt aussehen:

2n, n!, 1.41n, 2√

n

Die Eingabegroßen geht in den Exponenten ein und laßt deshalb die Laufzeitnoch viel

schnellerwachsen.

Wie man die Laufzeit fur sehr komplizierte Algorithmen mathematisch berechnet oder

bestmoglich abschatzt, ist Aufgabe der Algorithmik.

Fur alle effizient losbaren Probleme hat die theoretischeInformatik die KlasseP de-

finiert. Fur einige ineffizient losbaren Probleme wurde die KlasseNP definiert. Sie spielt

eine besondere Rolle.NP enthalt alle effizient losbaren Probleme und alle effizient aber

nichtdeterministisch losbaren Probleme. Ein nichtdeterministisch losbares Problem besitzt

nur eine Art von einem Algorithmus. An bestimmten Stellen gibt es in der Problemlosungs-

vorschriftmehrereMoglichkeiten, wie weitergerechnet werden kann. Damit kann naturlich

kein Rechner arbeiten, der braucht am Ende eines Schrittes nur eineMoglichkeit fur den

nachsten Schritt. Will man diesen Nichtdeterminismus loswerden, muss man alle Moglich-

keiten an den Verzweigungsstellen hintereinandersetzen und landet bei einem superpoly-

nomialen Algorithmus. Der ist ineffizient, aber dafur ein Algorithmus.NP steht also fur

nichtdeterministische Polynomialzeit. Ob in NP wirklich Probleme liegen, die nicht auch

in polynomialer Zeit berechenbar sind, ist bis heute nicht bewiesen. Zur Zeit gibt es dar-

in jede Menge Probleme, fur die noch kein effizienter Algorithmus (ein Algorithmus, der

in polynomialer Zeit deterministisch rechnet) gefunden wurde, wie das Handelsreisenden-

problem, das Rucksackproblem und noch viele andere Probleme mehr. Dies ist eins der

beruhmtesten offenen Probleme der theoretischen Informatik:

Ist P = NP?

Das heißt soviel wie: Gibt es fur alle bis jetzt nur ineffizient losbaren Probleme ausNP

nicht doch einen effizienten Algorithmus?

Oder kann das Gegenteil gezeigt werden, dass es unmoglich ist, effiziente Algorithmen

fur Probleme aus NP zu finden, womit dannP 6= NP gelten wurde.

Besonders interessant ist, dass es in der KlasseNP Probleme gibt, die effizient (in

polynomialer Zeit) in einander uberfuhrt werden konnnen. Das heißt, fande man einen ef-

fizienten Algorithmus fur eins dieser Probleme, wurde dieser alle anderen Problem dieser

Art auch losen. Diese Unterklasse vonNP nennt man dieNP-vollstandigen Probleme.

10

Zum Beispiel ist das Rucksachproblem und das Problem des Handelsreisenden so ein Fall.

Konnte man das Problem des Handlesreisenden effizient losen, kann man dieselbe Algo-

rithmusidee fur das Rucksackproblem verwenden und fur viele andere Problem mehr.

Weiter gibt es noch solch widerborstigen Probleme, wo wedergezeigt werden kann,

dass sie NP-vollstandig sind, noch ist bis jetzt ein effizienter Algorithmus bekannt. So ein

Problem ist das

Faktorisierungsproblem

Gegeben sei eine NichtprimzahlN , und gesucht sind 2 Primzahlen (naturliche Zahlen, die

nur durch sich selbst und 1 teilbar sind)p undq mit N = p ∗ q.

Bemerkung: Bis jetzt war die Eingaben die Anzahl von Elementen, z.B. Stadte, oder

Waren. Beim Faktorisierungsproblem oder weiter unten beimPrimzahlproblem ist die Ein-

gabe eine Zahl. Das Schwierige des Problems hangt von der Große der naturlichen Zahl

ab. Die Große der Zahl wird umgerechnet in die Anzahl der Bits (0 und 1), die die Zahl in

Binardarstellung an Speicher in Anspruch nimmt. Diese Anzahl ist nun die Eingabegroße.

Ein ahnlich schweres Problem war das Primzahlproblem, dessen Komplexitat lange

offen war.

Primzahlproblem

Fur eine gegebene naturliche Zahl soll festgestellt werden, ob sie eine Primzahl ist oder

nicht. Ein ineffizienter, sehr alter und beruhmter Algorithmus ist dasSieb des Eratosthe-

mes:

• Beginnend bei 2 streicht man jede zweite der 2 folgenden nat¨urlichen Zahlen.

• Danach streicht man ab der 3 jede dritte Zahl,

• ab der 5 jede funfte Zahl (die 4 wurde schon gestrichen, als man jede zweite Zahl der

2 folgend wegstrich) und immer so weiter.

Am Ende bleibt eine Folge von Primzahlen ubrig. Die Laufzeit dieses Algorithmus ist su-

perpolynomial, also ineffizient. Primzahlen sind z.B. in der Kryptografie sehr wichtig, wie

wir im nachsten Abschnitt sehen werden. Zahlen testet man auf die Primzahleigenschaft

11

heutzutage mit probabilistischen Algorithmen (benutzen im Laufe ihrer Rechnung Zufalls-

zahlen), die effizient rechnen, aber fur eine gegebene Zahlnur mit Sicherheit sagen, dass

sie keine Primzahl ist, ansonsten nur mit sehr hoherWahrscheinlichkeitsagen, dass sie

eine Primzahl ist. In extrem wenigen Fallen wird von einer Zahl behauptet, dass sie ei-

ne Primzahl ware, aber eigentlich gar keine ist. In der Praxis sind alle zufrieden, weil der

Algorithmus sehr schnell rechnet. Theoretisch außerst uberraschend war es, als 2002 M.

Agrawal, N. Kayal und N. Saxena sehr elegant bewiesen, das der Primzahltest doch ein ef-

fizient losbares Problem ist, also inP liegt. Der Primzahlbeweis soll so einfach und genial

sein, dass man sich fragen konnte, ob nicht auch fur andereineffiziente Algorithmen doch

noch effiziente Algorithmen gefunden werden konnten.

5 Nutzliche ineffizient berechenbare Probleme

In der Kryptografie werden zum Verschlusseln von Nachrichten Algorithmen benutzt, de-

ren Entschlusselungsalgorithmen fur nicht legale Interessenten bis heute nur ineffiziente

Laufzeiten haben. In der modernen Kryptografie geht es darum, dass sich 2 Menschen

Nachrichten schicken wollen, ohne dass jemand, der alles mitlesen kann, sie versteht. Ei-

ne Person A, nennen wir sie ALICE, will an eine andere Person B, z.B. BOB, eine ver-

schlusselte Nachricht schicken, die nur BOB entschlusseln kann.

Allgemeiner Verschlusselungsablauf

SENDER EMPFANGER

Klartext Geheimtext

ALICE BOB

+ Schlussel −−−−−−− > + Schlussel

+ Algorithmus + Algorithmus

−−−−−−− −−−−−−−−

= Geheimtext = Klartext

12

Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus

selbst abhangen, sondern nur von der Geheimhaltung des Schlussels.

Wie einigt man sich uber den Schlussel? Die Paradoxie besteht darin, dass der Schlussel

selbst auch ein Geheimnis ist. Wie kann ohne ein Treffen von ALICE und BOB ein Schlussel

festgelegt werden, mit dem BOB an ALICE Nachrichten schicken kann, die niemand an-

deres verstehen kann?

Die Diffie-Hellman-Vorhangeschloßidee

ALICE will eine geheime Nachricht an BOB schicken:

1. ALICE legt eine Nachricht in eine Eisenkiste, verschließt diese mit einem Schlussel

und behalt diesen.

2. ALICE schickt die Eisenkiste mit der Post.

3. BOB hangt ein eigenes Vorhangeschloß an die Kiste und behalt den Schlussel zu

seinem Schloß.

4. BOB schickt die Kiste zuruck an ALICE mit der Post.

5. ALICE nimmt ihr Schloß von der Kiste ab und schickt die Kiste mit der Post an BOB

zuruck.

6. BOB muß nun nur noch sein eigenes Vorhangeschloß offnenund kann die Nachricht

lesen.

Kein Schlussel wurde ausgetauscht und trotzdem konnte niemand anderes außer BOB die

Nachricht von ALICE lesen!

Bemerkung: Das Packchen musste allerdings dreimal hin und her wandern.

Gucken wir uns dieselbe Idee mit Zahlen zur Schlusselvereinbarung zwischen ALICE

und BOB an: ALICE will mit BOB einen gemeinsamen Schlussel festlegen mit Hilfe der

Funktion7xmod11

1. ALICE wahlt eine Zahl (z.B. 3), nennt sieA und halt sie geheim.

2. BOB wahlt eine Zahl (z.B. 6), nennt sieB und halt sie auch geheim.

13

3. ALICE berechnet mit ihrer ZahlA 7Amod11 = 73mod11 = 343mod11 = 2 = α.

4. BOB berechnet mit seiner ZahlB 7Bmod11 = 76mod11 = 117649mod11 = 4 = β.

5. ALICE schicktα an BOB.

6. BOB schicktβ an ALICE.

7. ALICE nimmt BOBs Zahlβ und berechnetβAmod11 = 43mod11 = 64mod11 = 9

8. BOB nimmt ALICEs Zahlα und berechnetαBmod11 = 26mod11 = 64mod11 = 9

9 ist der gemeinsame Schlussel, den beide nun zum Verschlusseln von Nachrichten benut-

zen konnen. Niemand sonst kann diesen Schlussel in vernunftiger Zeit berechnen, auch

wenn erα, β und7xmod11 kennt, wenn A und B sehr groß gewahlt wurden.

Bemerkung: Auch hier wurden Nachrichten dreimal hin und her gesendet,bis der

Schlussel zustande kam.

Was hat es mit der FunktionY XmodZ auf sich? Diese Funktion ist eine sogenannte

Einwegfunktion, d.h. sie istfast nichtumkehrbar. Es ist allerdings offen, ob es Einwegfunk-

tionen wirklich gibt. Vorstellen kann man sich das wie bei der Telefonbuchsuche, wenn man

nach einer bestimmten Telefonnummer suchen wurde, um die Adresse zu erfahren. Das ist

ein sehr aufwendiges Vorgehen, weil im Grunde genommen das Telefonbuch von Anfang

bis Ende durchsucht werden musste. Die FunktionY XmodZ heißt diskreter Logarithmus.

Ein anderer Kandidat einer Einwegfunktion wird im RSA-Verfahren (benannt nach den

Erfindern R. Rivest, A. Shamir, L. Adleman) zum Verschlusseln von Nachrichten verwen-

det. Hierbei wird die Idee ausgenutzt, das jeder in einen Briefkasten etwas durch den Schlitz

werfen kann, aber nur der mit dem Schlussel den Briefkastenoffnen kann. Das Verfahren ist

ein asymmetrisches Verfahren und gehort zur Public-Key-Kryptografie. Zum Verschlusseln

und Entschlusseln werden verschiedene Schlussel benutzt, einer davon ist allen bekannt, al-

so offentlich. Diesmal wird das Faktorisierungsproblem ausgenutzt.

Das folgende Beispiel erklart den Verlauf des RSA-Verfahrens.

RSA-Verfahren

BOB will an ALICE die wichtige Nachrichtm = 2 (Text wird durch Zahlen codiert, z.B.

kann 2 bedeutet, dass ALICE das Heiratsangebot annimmt) verschlusselt schicken:

14

1. ALICE wahlt zwei Primzahlenp und q und berechnetn = p ∗ q, z.B. p = 3 und

q = 11, womit n = 3 ∗ 11 = 33 ist.

2. ALICE berechnt eine Zahld wie folgt d = (p − 1)(q − 1). Fur unser Zahlenbeispiel

ist d = 2 ∗ 10 = 20.

3. ALICE wahlt weiterhin zwei Zahlene und f so, dasse ∗ f/d den Rest 1 hat, z.B.

e = 7 undf = 3, weil 21/20 den Rest 1 hat.

4. ALICE veroffentlich die beiden Zahlenn unde als ihre offentlichen Schlussel, mit

Hilfe derer man ihr geheime Nachrichten schicken kann. Die Zahl f ist ihr privater

Schlussel, den sie niemals herausgibt.

5. BOB besorgt sich diese beiden offentlichen Zahlenn und e (also 33 und 7) und

verschlusselt seine Nachrichtm wie folgt: me/n. Den Rest dieser Berechnung, be-

zeichnet mitk, schickt er an ALICE. Fur unser Zahlenbeispiel istk der Rest von

27/33, also 29.

6. ALICE entschlusselt die geheime Nachricht von BOB mit ihrem privaten Schlussel

wie folgt: kf/n. Der Rest ist die Nachricht, die BOB ihr verschlusselt schicken woll-

te, also293/33 = 24389/33 = 739 mit Rest 2, was die Nachrichtm ist.

Im wirklichen Leben sind die privaten und offentlichen Schlussel viel großer, mindestens

im Bereich von10500. Die Primzahlen werden gewahlt, indem irgendeine Zahl zufallig

gewahlt wird und uberpruft wird, ob sie eine Primzahl ist. Ist sie keine, wird der Vorgang

wiederholt. Es gibt genugend viele Primzahlen. Bis zur naturlichen Zahln gibt es ungefahr

1/log n Primzahlen, was bedeutet, dass ungefahr nachlog n vielen Versuchen (was wirklich

nicht viel ist) eine Primzahl gefunden ist.

Bemerkung: Hier ist es nicht notig, dass Nachrichten mehrmals hin undher wandern

mussen, um einen geheimen Schlussel zu beschließen. Beimonline-Banking wird dieses

Verfahren benutzt, um einen Schlussel fur eine symmetrische Verschlusselung fur den wei-

teren Bankverkehr zwischen Kunden und Bank fest zu legen.

15

6 Effiziente berechenbare Probleme

Effizient losbare Probleme sind Probleme, fur die Algorithmen gefunden werden konnen,

die in polynomialer Zeit ein Ergebnis berechnen. Die Eingabegroße geht bei der Rechen-

zeit in die Basis der Laufzeitfunktion ein und nicht in den Exponenten. Weiterhin haben

solche Polynomialzeitalgorithmen die schone Eigenschaft, dass sie beliebig hintereinan-

der ausfuhrbar und kombinierbar sind und immer noch ein Polynomialzeitalgorithmus am

Ende entsteht (Abgeschlossenheit unter Addition, Multiplikation und Komposition).

Bemerkung: Fur kleine Eingabegroßen konnen ineffiziente Algorithmen dennoch sinn-

voll sein.

6.1 Sortieren

Sortieren ist ein grundlegendes Problem in der Informatik.Man sagt, Rechner verbrin-

gen 25% ihrer Zeit damit. Die Aufgabe besteht darin, gegebene Elemente in die richtige

Reihenfolge zu bringen. Es gibt bein gegebenen Elementenn! verschiedene Reihenfol-

gen der Elemente, wobei nur eine die richtige (gewunschte)Reihenfolge ist. Das Ergebnis

beim Sortieren - eine sortierte Liste - wird z.B. bei der Suche benutzt. Alle Suchalgo-

rithmen gehen von einer sortierten Liste aus. Die Dinge mussen jeweils einemSchlussel

zugeordnet sein, und fur die Schlussel muss es eine klar definierte Ordnung geben (nume-

risch/alphabetisch). Aber es mussen nicht allen! Falle der verschiedenen Sortierungen auf

die eine richtige durchsucht werden. Sortieren von Elementen ist ein effizient losbares Pro-

blem. Es gibt sehr viele effiziente Algorithmen, manche sindbesser und andere schlechter.

Zum Beispiel benutzen die meisten Menschen einen von beidenfolgenden Algorithmen

zum Sortieren von Skatkarten.

Sortieren durch Auswahlen (Selection)

1. Man wartet, bis alle Karten ausgeteilt sind und nimmt dannden ganzen Stapel mit

einmal auf.

2. Dann sucht man jeweils den großten Kartenwert, und tauscht diese Karte an die letzte

Stelle.

3. Diese letzte Karte ist dann schon an der richtigen Stelle.Dasselbe macht man dann

16

mit den ubrigen Karten. Die nachst kleinere Karte wird an die vorletzte Stelle ge-

tauscht und immer so weiter.

Wie lange diese Art des Sortierens braucht, hangt naturlich sehr von der Sortierung der

Karten ab.

Beispiel - Selection-Sort: gegebene Zahlenfolge: 9 5 1 6 2 4 3

1. Runde - großte Zahl nach rechts tauschen: 3 5 1 6 2 4 9

2. Runde - nachstgroßere Zahl an die vorletzte Stelle tauschen: 3 5 1 4 2 6 9

3. Runde: 3 2 1 4 5 6 9

4. Runde: 1 2 3 4 5 6 9

Sortieren durch Einfugen (Insertion)

1. Man nimmt die erste ausgeteilte Karte sofort auf die Hand.

2. Jede weitere ausgeteilte Karte fugt man je nach Reihenfolge entweder vor die Karte,

die man schon auf der Hand halt, oder dahinter.

3. Hat man mehr als eine Karte auf der Hand, fugt man jede weitere Karte entweder vor

die erste Karte aller Karten auf der Hand, oder hinter die letzte Karte oder zwischen

2 Karten, je nachdem in welche Lucke die neue Karte gehort.

4. Das macht man so lange, bis alle Karten aufgenommen wurden.

Beispiel - Insertion-Sort: gegebene Zahlenfolge: 9 5 1 6 2 4 3

1. Runde - Hinzunahme der 9: 9

2. Runde - Hinzunahme der 5: 5 9

3. Runde - Hinzunahme der 1: 1 5 9

4. Runde - Hinzunahme der 6: 1 5 6 9

5. Runde - Hinzunahme der 2: 1 2 5 6 9

17

6. Runde - Hinzunahme der 4: 1 2 4 5 6 9

7. Runde - Hinzunahme der 3: 1 2 3 4 5 6 9

Eine total einfache Art, Dinge zu sortieren, fuhrt der Bubble-Sort-Algorithmus.

Sortieren durch Vertauschen: Bubble-Sort

1. In einer gegebenen Liste von zu ordnenden Elementen tauscht man beginnend beim

ersten Element 2 benachbarte Elemente, wenn das erstere Element großer als das

folgende ist.

2. Dies macht man solange, bis keine Vertauschungen mehr notig sind.

Der Name kommt von der Tatsache, dass sich verschieden großeaufsteigende Blasen

(”Bubbles“) in einer Flussigkeit quasi von alleine sortieren, da großere Blasen die kleineren

”uberholen“. Dieser Algorithmus ist sehr simpel, aber nicht schnell. Im besten Fall (best

case) liegt eine sortierte Liste vor, was nach einem Durchlauf festgestellt werden kann. Der

schlechteste Fall (worst case) ware eine ruckwarts sortierte Liste, wo bei jedem Durchlauf

das kleinste Element nur eine Position nach vorne ruckt.

Beispiel - Bubble-Sort: gegebene Zahlenfolge: 9 5 1 6 2 4 3

1. Runde: 5 1 6 2 4 3 9

2. Runde: 1 5 2 4 3 6 9

3. Runde: 1 2 4 3 5 6 9

4. Runde: 1 2 3 4 5 6 9

Der am haufigsten verwendete, sehr schnelle Sortieralgorithmus ist der Quicksort-Algorithmus.

Quicksort-Algorithmus

1. In der Liste der zu sortierenden Elemente wird ein beliebiges Element als Referen-

zelement festgelegt, z.B. das letzte Element in der gegebenen Liste, wir nennen es

R.

18

2. Danach wird von links nach rechts in der Liste nach einem Element gesucht, dass

großer als das ReferenzelementR ist. Dieses merkt man sich, als z.B.A.

3. Nun wird von rechts nach links nach einem Element in der Liste gesucht, das kleiner

als das ReferenzelementR ist, aber rechts vonA in der Liste liegt. Findet man so ein

Element, so nennen wir esB.

4. Hat man zwei ElementeA undB gefunden, tauscht man sie aus und beginnt wieder

bei Schritt 1.

5. Konnte man nurA finden, tauscht manA gegen das ReferenzelementR aus. Das

Referenzelement steht nun schon genau an der richtigen Stelle in der Liste. An die-

ser Stelle wird die Liste geteilt. Man erhalt eine Liste mitden Elementen vor dem

Referenzelement und eine Liste mit den Elementen nach dem Referenzelement.

6. Mit diesen beiden neuen Listen beginnt man jeweils wiederbei Schritt 1 und fahrt

solange damit fort, bis man bei Listen mit einem oder keinem Element angelangt ist.

Die Technik der Aufteilung der Liste von Elementen in zwei Teillisten heißtTeile- und

Herrsche. Gunstig ist es, wenn immer ungefahr zwei gleich große Teillisten entstehen.

Die Technik, dass auf die zwei entstandenen Teillisten immer dasselbe Prinzip angewendet

wird, heißtRekursion.

Beispiel - Quicksort: gegebene Zahlenfolge: 9 5 1 6 2 43 (Referenzelement ist fett

dargestellt)

• Ausgangsliste: 9 5 1 6 2 43

1. Tausch von 9 und 2: 2 5 1 6 9 43

2. Tausch von 5 und 1: 2 1 5 6 9 43

3. Es konnte nurA=5 gefunden werden, keinB, das rechts vonA liegt. Deshalb

wird das Referenzelement 3 gegen 5 ausgetauscht: 2 1 3 6 9 4 5

• Das ehemalige Referenzelement 3 steht jetzt an der richtigen Stelle in der Liste. Die

Ausgangsliste wird nun zum ersten Mal geteilt bei 3.

• Es entstehen zwei Teillisten: 2 1 und 6 9 4 5

19

• Linke Teilliste: 21 (Tausch von 2 und 1 und man ist fertig)

• Rechte Teilliste: 6 9 45

1. Tausch von 6 und 4: 4 9 65

2. Es konnte nurA=9 gefunden werden, keinB, deshalb wird das Referenzele-

ment 5 gegen 9 ausgetauscht: 4 5 6 9

• Die 5 steht jetzt an der richtigen Stelle in der Liste. Die Liste wird wiederum beim

ehemaligen Referenzelement 5 geteilt.

• Es entstehen wiederum zwei neue Teillisten: 4 und 6 9

• Die linke Teilliste ist eine Einerliste, es ist also nichts mehr zu tun.

• Die rechte Teilliste ist auch schnell erledigt: 69.

• Somit wurde die gesamte Liste sortiert: 1 2 4 5 6 9

Berechnet man die Laufzeit von diesen Algorithmen bei einerdurchschnittlich ver-

mischten gegebenen Liste von Elementen, kommt der Quicksort-Algorithmus am besten

weg. Die Laufzeit wird beschrankt von der FunktionO(n log(n)), die also mit zunehmen-

den Elementen der zu sortierenden Liste nur langsam wachst.

6.2 Suchalgorithmen

Gesucht wird immer in sortierten Listen. Hier zwei Beispiele fur einen Suchalgorithmen:

Sequenzielle Suche

1. Gestartet wird mit dem ersten Element der Liste.

2. Ist dies nicht das gesuchte Element, uberpruft man das nachste Element in der Liste

solange, bis das gesuchte Element gefunden wurde.

Hat man Pech, sucht man bei einer Liste von Elementen bis zum Ende, das heißt, das

gesuchte Element kam gar nicht vor. Hat man Gluck, ist das gesuchte Element gleich das

erste.

Sucht man einen Namen in einem Telefonbuch, macht man das ublicherweise wie folgt:

20

Binare Suche

1. Man wahlt das mittlere Element der Liste und

2. pruft, ob der gesuchte Wert in der vorderen oder in der hinteren Halfte der Liste liegt,

also ob der gesuchte Wert kleiner oder großer als dieses mittlere Element ist.

3. Liegt das gesuchte Element in der vorderen Halfte, so geht man wie eben beginnend

mit Schritt 1 mit der vorderen Halfte als Ausgangsliste vor.

4. Genauso geht man vor, wenn das Element in der hinteren Halfte liegt.

5. Dies wiederholt man solange, bis das gesuchte Element gefunden wurde oder klar

ist, dass es gar nicht in der gegebenen Liste vorkommt.

7 Algorithmenentwurfstechniken

Da ist ein Problem und gesucht ist ein Algorithmus. Wie findetman einen Algorithmus?

Das einfachste ist immer die Suche nach der sogenannten HOLZHAMMERLOSUNG. Ist

die gefunden und der Rechner tut, was diese Losung vorschl¨agt, konnen wir immer noch

nach besseren, d.h. effizienteren Algorithmen, suchen. Dabei kann der Holzhammeralgo-

rithmus wunderbar zum Testen gut sein.

Aber auch die Suche nach dem einfachsten Algorithmus kann sehr schwer sein.

Einige Techniken, um Algorithmen zu entwerfen, sind folgende:

• Greedy-Algorithmen

• Rekursive Algorithmen

• Teile und Herrsche

• Backtracking

7.1 Greedy-Algorithmen

Alltagsbeispiel

Unser ganzes Leben lauft in der Regel nach der Greedy-Methode ab. Wir treffen vernunfti-

gerweise immer die im Moment optimalst erscheinende Entscheidung fur unseren nachsten

21

Lebensschritt. Da die Zeit nicht zuruckdrehbar ist, sind dies Schritte, die nicht ruckgangig

zu machen sind, auch wenn die damalige Entscheidung sich alsFehlentscheidung entpuppt.

Anderes typisches Beispiel:

Auf Geldbetrage unter 1 EUR soll Wechselgeld herausgegeben werden. Zur Verfugung ste-

hen ausreichend viele Munzen mit den Werten 50, 20, 10, 5, 2,1 Cent. Das Wechselgeld

soll aus so wenig Munzen wie moglich bestehen, z.B.

78 Cent =50 + 20 + 5 + 2 + 1.

Greedy-Prinzip:

• Wir nehmen jeweils immer die großte Munze aus 50, 20, 10, 5,2, 1 Cent, so dass noch

nicht der Zielbetrag erreicht wird und ziehen diesen Munzbetrag von dem Zielbetrag

ab.

• Das machen wir solange, bis der Restbetrag gleich Null ist.

Eine Kassiererin geht genau nach diesem Algorithmus vor. Unsere deutsche Munzein-

teilung ist so gewahlt, dass der Algorithmus immer die beste Losung berechnet. Ange-

nommen wir hatten die Munzen mit Werten 11, 5, und 1 gegebenund der Zielwert sei 15.

Obiger Greedy-Algorithmus wurde folgendes Ergebnis berechnen:

15 = 11 + 1 + 1 + 1 + 1

Die beste Losung, also die mit den wenigsten Munzen, ist aber:15 = 5 + 5 + 5

Greedy-Algorithmen berechnen nur einlokalesOptimum.

Greedy-Algorithmenschritte allgemein:

• Wahl derjenigen Alternative unter mehreren gegebenen, dieaktuell optimal erscheint

• diese Wahl kann nie mehr ruckgangig gemacht werden

• man braucht eine Bewertungsfunktion, um die beste Alternative fur die Losung des

Teilproblems zu finden

22

Der Vorteil solcher Algorithmen sind kurze Laufzeiten, da der Losungsraum auf einem

wohldefinierten und geradlinigen Pfad durchlaufen wird.

Der Nachteil ist, dass die erhaltene Losung nicht die besteLosung sein muss.

Dieses Algorithmusprinzip wird fur ineffizient losbare Probleme verwendet, um Annahe-

rungslosungen zu berechnen, z.B. zur Berechnung einer Rundreise fur den Handelsreisen-

den oder zur Berechnung einer Rucksackpackung fur den Kaufhausdieb.

7.2 Rekursive Algorithmen

Beispiel Turm von Hanoi:

Gegeben sind 3 Stabe, wobei auf Turm 1 n Scheiben unterschiedlicher Große liegen. Die

Stabe 2 und 3 sind leer. Ziel ist es, alle Scheiben von Stab 1 nach Stab 3 zu bewegen. In

einem Arbeitsschritt darf die oberste Scheibe eines Scheibenturms entfernt und oben auf

einen anderen Turm gelegt werden. Niemals darf eine große Scheibe auf einer kleineren

liegen.

Arbeitsanleitung der alten Weisen im Kloster von Hanoi:

Tragt zuerst alle Scheiben bis auf die untereste zu dem Turm 2. Zu diesem Zwecke

bedient euch des gleichen Verfahrens wieder. Dann konnt ihr die letzte Scheibe zu ihrem

Zeile, Turm 3 tragen. So dies getan ist, holet die anderen Scheiben vom Turm 2 und bringt

sie zu ihrem Ziele, auch hierzu konnt ihr wieder die namliche Methode verwenden.

Rekursive Algorithmen sind also Algorithmen, die sich selbst aufrufen. Solche Algo-

rithmen werden sehr typisch im Zusammenhang mit dem Teile und Herrsche Prinzip ver-

wendet.

7.3 Teile und Herrsche

Alltagsbeispiel

Der Quick-Sort-Algorithmus aus dem vorherigen Kapitel istein typischer Vertreter vom

Teile und Herrsche Prinzip. Man benutzt diesen Entwurf besonders da, wo das Problem

durch seine Große schwierig wird.

23

Prinzip:

• Teile: Rekursive Ruckfuhrung auf identisches Problem mit kleinerer Eingabemenge.

• Herrsche: Wenn das Problem klein genug ist, lost man das Problem.

Teile und Herrsche Schritte allgemein:

1. Teile das gegebene Problem in mehrere getrennte Teilprobleme auf,

2. Lose (Beherrsche) diese Teilproblemeeinzelnund

3. Setzedie Losungen des ursprunglichen Problems aus den Teillosungen zusammen.

4. Wende dieselbe Technik auf jedes der Teilprobleme an, dann auf deren Teilprobleme

usw., bis die Teilprobleme klein genug sind, dass man eine L¨osung explizit angeben

kann.

Es ist wichtig, dass jedes Teilproblemvon derselben Artist wie das ursprungliche Problem,

so dass es mit demselben Algorithmus gelost werden kann.

7.4 Backtracking-Algorithmen

Alltagsbeispiel

Backtracking benutzt man im Alltag, wenn man auf der Suche nach einer Adresse ist via

einer ungenauen Wegbeschreibung. Wahrend der Suche hat man Momente, wo man rea-

lisiert, dass eine bestimmte eingeschlagene Route nicht zur Adresse fuhren wird. In der

Regel geht man dann den Weg soweit zuruck, bis man zu einem Punkt kommt, wo man

einen neuen Versuch in eine andere Richtung unternimmt. Daswird man dann solange so

durchziehen (außer man fragt jemanden nach dem Weg), bis manbei der gesuchten Adresse

angelangt ist.

Das Backtracking-Prinzip erlaubt also, Teillosungen ruckgangig zu machen, wenn diese

nicht zur Losung des Gesamtproblems fuhren, und neue Alternativen auszuprobieren. Dies

geschieht uber rekursive Aufrufe. Teillosungen konnenbis zu einer bestimmten Schritttiefe

ruckgangig gemacht werden, das heißt, man kann Sackgassen wieder verlassen.

Typische Einsatzgebiete von Backtracking:

24

• Labyrinth-Suche

• Spielprogramme (Schach)

• Planungsprobleme, Konfigurationen

Auch wenn es noch so viele Entwurfstechniken gibt, braucht man bei der Suche nach

einem Algorithmus Intuition und Kreativitat.

25