Vertragstheorie Eine Einführung mit finanzökonomischen Beispielen und Anwendungen 2005, XVI, 218 S. Basler, Herbert Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistischen Methodenlehre

Tabelle 2.1. Maximal l¨

osbare Problemgr¨

oße

n in Abh¨angigkeit von Laufzeitkom-

plexit¨

at und Rechenzeit

Rechenzeit

Komplexit¨

at 1 Sekunde auf altem Computer 1 Sekunde auf neuem Computer

n

n

alt

= 1000

n

neu

= 2

.000 = 2 · n

alt

n

2

n

alt

= 31

,6

n

neu

= 44

,7 =

√

2

· n

alt

2

n

n

alt

= 10

,0

n

neu

= 11

,0 = n

alt

+ 1

Tabelle 2.2. Ver¨

anderung der maximal l¨

osbaren Problemgr¨

oße

n in Abh¨angigkeit

von Laufzeitkomplexit¨

at und Computergeschwindigkeit

Der entsprechende Zusammenhang ist in Tabelle 2.2 veranschaulicht, in-

dem der Effekt einer Verdopplung der Rechnergeschwindigkeit hinsichtlich

der Problemgr¨

oßen, die in einer Sekunde berechenbar sind, dargestellt wird.

Dabei wird die Annahme zu Grunde gelegt, dass in einer Millisekunde auf

dem alten Computer eine, auf dem neuen Computer dagegen zwei Elemen-

taroperationen ausgef¨

uhrt werden k¨

onnen. Man erkennt, dass bei einer expo-

nentiellen Laufzeitkomplexit¨

at eine Steigerung der Rechnergeschwindigkeit

die l¨

osbare Problemgr¨

oße nur geringf¨

ugig erh¨

oht. Hieraus leitet sich aus ei-

ner praktischen Sichtweise eine Klassifikation von Laufzeitkomplexit¨

aten bzw.

Algorithmen in zwei Gruppen ab. Alle Algorithmen mit einer Laufzeitkomple-

xit¨

at von maximal O(n

k

) f¨

ur ein konstantes k bezeichnet man als polynomial,

---

20

2. Informatik und Informations- und Kommunikationstechnik

alle mit einer Laufzeitkomplexit¨

at von O(p

n

) f¨

ur ein konstantes p bezeichnet

man als exponentiell. W¨

ahrend exponentielle Algorithmen auch mit schnel-

leren Rechnern f¨

ur große Probleme in der Regel nicht mehr brauchbar sind,

werden die polynomialen Verfahren zusammenfassend als effizient bezeichnet.

Bei den bisherigen Darlegungen stand die Komplexit¨

atsabsch¨

atzung f¨

ur

einen gegebenen Algorithmus

”

nach oben“ im Mittelpunkt. Eine interessan-

te Verallgemeinerung besteht darin, Komplexit¨

atsabsch¨

atzungen f¨

ur Proble-

me anstatt f¨

ur Algorithmen anzugeben. So besitzt der Standardalgorithmus

f¨

ur die Multiplikation zweier n × n Matrizen eine Komplexit¨at von O(n

3

).

W¨

ahrend die Frage, ob es auch schneller geht, durch Angabe und Unter-

suchung eines entsprechenden Algorithmus teilweise beantwortbar ist, erfor-

dert eine Komplexit¨

atsabsch¨

atzung

”

nach unten“ andere Techniken. Untere

Schranken werden als Ω(. . .) angegeben. Da eine Matrizenmultiplikation alle

n

2

Matrixelemente der Ergebnismatrix erzeugen muss, ergibt sich eine trivia-

le untere Schranke von Ω(n

2

). Eine Zielsetzung der Komplexit¨

atstheorie ist

es, die exakte Laufzeitkomplexit¨

at von Problemstellungen, die ¨

uber Θ(. . .)

ausgedr¨

uckt wird, zu bestimmen.

8

W¨

ahrend die Bestimmung der exakten Problemkomplexit¨

at im Bereich

der polynomialen Funktionen oft eher von theoretischem Interesse ist, ist

es f¨

ur viele Problemstellungen offen, ob sie ¨

uberhaupt effizient l¨

osbar sind

(d. h. mit einem Algorithmus mit polynomialer Laufzeit). Mit

P bezeichnet

man die Komplexit¨

atsklasse aller Probleme, die effizient l¨

osbar sind. Alle bis-

her angesprochenen konkreten Probleme (Sortieren, Matrizenmultiplikation

usw.) liegen in

P. Auch folgende Problemstellung ist effizient l¨osbar: Man

betrachte den in Abbildung 2.1 dargestellten Graphen, der ein Verkehrsnetz-

werk repr¨

asentiere. Die Knoten repr¨

asentieren Standorte, die eingezeichne-

ten Verbindungen stellen die existierenden Verkehrswege mit den entspre-

chenden Entfernungen dar. Das K¨

urzeste-Wege-Problem (vgl. u. a. Domschke

und Drexl (2005)) besteht darin, den k¨

urzesten Weg von einem gegebenen

Start- zu einem gegebenen Zielstandort zu bestimmen. Beispielsweise sei der

k¨

urzeste Weg vom Knoten 1 zum Knoten 8 gesucht. F¨

ur diese Problemstel-

lung existieren Verfahren mit einem Zeitaufwand von O(n

2

), wobei n die

Anzahl der Knoten bezeichnet.

Das Rundreiseproblem (Problem des Handlungsreisenden, Traveling-

Salesman-Problem)

ist relativ ¨

ahnlich zum K¨

urzeste-Wege-Problem: F¨

ur

einen gegebenen Graphen (der wie beim K¨

urzeste-Wege-Problem Standorten

und Verkehrsverbindungen mit ihren Entfernungen entspricht) ist eine Rund-

reise durch alle Standorte zu bestimmen, so dass die insgesamt zur¨

uckgelegte

Strecke (Gesamtstrecke) minimal ist. F¨

ur die optimale L¨

osung dieser Prob-

lemstellung sind jedoch nur exponentielle Algorithmen bekannt. Ein weiteres

solches Problem, f¨

ur das keine effizienten Algorithmen bekannt sind, ist das

8

Die exakte Laufzeitkomplexit¨

at der Matrizenmultiplikation ist unbekannt,

w¨

ahrend zumindest entsprechende Algorithmen mit einem Aufwand von

O(n

2,376

) bekannt sind; vgl. Cormen et al. (2004).

---

2.1 Theoretische Grundlagen

21

4

2

3

3

3

5

4

3

5

3

7

6

3

3

1

2

4

5

8