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



Download 2,57 Mb.
Pdf ko'rish
bet23/50
Sana11.09.2021
Hajmi2,57 Mb.
#171395
1   ...   19   20   21   22   23   24   25   26   ...   50
Bog'liq
Grundlagen der Wirtschaftsinformatik mit 16 Tabellen

Tabelle 2.1. Maximal l¨

osbare Problemgr¨

oße

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


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 bezeichnet man als polynomial,


20

2. Informatik und Informations- und Kommunikationstechnik

alle mit einer Laufzeitkomplexit¨

at von O(p



n

) f¨


ur ein konstantes 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

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



3

).



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



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

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 

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

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



ur diese Problemstel-

lung existieren Verfahren mit einem Zeitaufwand von O(n

2

), wobei 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,

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




Download 2,57 Mb.

Do'stlaringiz bilan baham:
1   ...   19   20   21   22   23   24   25   26   ...   50




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish