Mathematische Begriffe

Damit es keine Unklarheiten bezüglich einiger Begriffe gibt, werden hier die wichtigsten erstmal definiert. Einige Definitionen sind nicht 100%ig korrekt aber ausreichend.

Algorithmus
Ein Algorithmus ist ein Verfahren, das ein gegebenes Problem löst. Ein Algorithmus kann in Sätzen, grafisch (z.B. Struktogramm) oder als Programmcode angegeben werden. In der Regel wird als Programmcode Pseudocode verwendet.


Iterative Algorithmen (vollständig)
Ein Algorithmus ist iterativ, wenn in seiner Realisierung (Programmcode) keine Rekursionen vorkommen.


Rekursive Algorithmen (vollständig)
Ein Algorithmus ist rekursiv, wenn in seiner Realisierung (Programmcode) nur Rekursionen (direkt oder indirekt), jedoch keine Schleifen (for, while, repeat, ...) vorkommen. Zu jedem iterativen Algorithmus kann ein äquivalenter rekursiver Algorithmus angegeben werden.


Halbiterative/Halbrekursive Algorithmen
Ein Algorithmus ist halbiterativ/halbrekursiv, wenn er weder iterativ noch rekursiv ist, jedoch hauptsächlich iterative/rekursive Merkmale besitzt.


Parallele Algorithmen
Ein Algorithmus heißt parallel (oder parallelisierbar), wenn eine Laufzeitoptimierung möglich ist, indem er auf einem Multiprozessorsystem implementiert wird. D.h. Teilaufgaben können von mehreren Prozessoren parallel abgearbeitet werden.



Sortieralgorithmus
Ein Sortieralgorithmus ist ein Algorithmus, der eine Menge von unabhängigen Schlüsselelementen in eine bestimmte Ordnung/Reihenfolge bringt. In der Regel liegt dieser Ordnung eine Größenrelation zugrunde. Liegt eine wohldefinierte Ordnung vor, so ist die Menge sortiert.


Totale Ordnung
Eine totale Ordnung liegt vor, wenn auf jedes Paar von Schlüsselelementen einer Menge eine der Vergleichsoperationen "<=", "<", ">=" oder ">" angewendet werden kann, d.h. ein Vergleich möglich ist.


Allgemeine Sortieralgorithmen
Ein Sortieralgorithmus ist allgemein, wenn ausschließlich die totale Ordnung der Schlüsselmenge zum Sortieren verwendet wird.


Spezielle Sortieralgorithmen
Ein Sortieralgorithmus ist speziell, wenn zusätzlich zur totale Ordnung weitere Eigenschaften der Schlüsselmenge ausgenutzt wird. Solche Eigenschaften sind z.B. die Endlichkeit, Beschränktheit oder rechnerinterne Darstellung der Schlüsselmenge.


Umhüllende Sortieralgorithmen
Ein Sortieralgorithmus ist umhüllend, wenn er einen anderen Sortieralgorithmus (geringfügig verändert) intern anwendet. Dadurch werden Eigenschaften, Laufzeiten oder Vorraussetzungen dieses Original-Algorithmus verbessert.

Stabile Sortieralgorithmen
Ein Sortieralgorithmus ist stabil, wenn beim Sortieren gleichwertige Schlüsselelemente (Element a ist weder kleiner noch größer als Element b) niemals gegeneinander vertauscht werden.


Instabile Sortieralgorithmen
Ein Sortieralgorithmus ist instabil, wenn er nicht stabil ist.


Out-of-Place Sortieralgorithmen
Ein Sortieralgorithmus heißt out-of-place, wenn das Ergebnis der Sortierung in einer neuen Menge zurückgegeben wird. Die Originalmenge wird dann im Allgemeinen nicht verändert.


In-Place Sortieralgorithmen
Ein Sortieralgorithmus heißt in-place, wenn er nicht out-of-place ist.


Äquivalente Sortieralgorithmen
Zwei Sortieralgorithmen sind äquivalent, wenn das zugrunde liegende Verfahren (die Idee) identisch ist. Die Realisierung (Implementierung) spielt dabei keine Rolle. Auch nicht, ob auf- oder absteigend oder von links nach rechts bzw. rechts nach links sortiert wird.

Die hier vorgestellten Algorithmen sortieren in der Regel aufsteigen und von rechts nach links.



Menge von Schlüsselelementen
Eine Menge von Schlüsselelementen ist keine Menge im üblichen Sinne, sondern eine Datenstruktur, in der mehrere Schlüsselelemente untergebracht sind. Die Positionen der Elemente sind unterscheidbar. Solche Strukturen sind u.a. Felder, Listen oder Bäume.



Asymptotische Laufzeit (bc-wc-ac-ec)
Eine Laufzeit eines Algorithmus gibt an, wie sich dieser in Abhängigkeit von gewissen Parametern verhält. Solche Parameter sind i.a. die Anzahl und Größe von Ein- und Ausgabeelementen. Es gibt best-case-Laufzeiten (bc - bester Fall - asymptotisch unteren Schranke - Ω), worst-case-Laufzeiten (wc - schlechtester Fall - asymptotisch oberen Schranken - Ο) und average-case-Laufzeiten (ac - mittlerer Fall - Θ). Sind die Ω- und Ο-Laufzeit identisch, so können diese als every-case-Laufzeit (ec - jeder Fall - asymptotische Schranke - Θ) zusammengefasst werden.


empirische Laufzeit (e)
Eine Laufzeit ist empirisch, wenn sie mittels Laufzeitmessungen experimentell ermittelt wurde. Eine theoretische Herleitung muss nicht unbedingt vorhanden sein (wäre aber schön). Es darf sich nicht um eine Abschätzung der Form Ω, Θ oder Ο handeln, d.h. die Konstanten müssen erkennbar sein.


polynomiale Laufzeit (Polynomialzeit)
Eine Laufzeit ist polynomial, wenn gilt "T(n) = Θ(na)" für ein beliebiges a >= 0.


konstante Laufzeit
Eine polynomiale Laufzeit ist konstant, wenn gilt a == 0, d.h. "T(n) = Θ(1)".


lineare Laufzeit
Eine polynomiale Laufzeit ist linear, wenn gilt a == 1, d.h. "T(n) = Θ(n)".


quadratische Laufzeit
Eine polynomiale Laufzeit ist quadratisch, wenn gilt a == 2, d.h. "T(n) = Θ(n²)".


kubische Laufzeit
Eine polynomiale Laufzeit ist kubisch, wenn gilt a == 3, d.h. "T(n) = Θ(n³)".


exponentielle Laufzeit (Exponentialzeit)
Eine Laufzeit ist exponentiell, wenn gilt "T(n) = Θ(an)" für ein beliebiges a > 1.


logarithmische Laufzeit
Eine Laufzeit ist logarithmisch, wenn gilt "T(n) = Θ(log(n))" für eine beliebige Basis.


asymptotisch optimale Algorithmen
Algorithmen sind asymptotisch optimale, wenn es nicht möglich ist einen Algorithmus zu konstruieren, der das selbe Problem löst und eine bessere asymptotische Laufzeit besitzt. D.h. wenn die asymptotisch untere Schranke der Laufzeit zur Lösung des Problems erreicht ist. Ein allgemeiner Sortieralgorithmus ist asymptotisch optimal, wenn seine Laufzeit "T(n) = Ω(nlog(n))" beträgt.



Asymptotische Speichernutzung
Für Speichernutzungen gelten zur Laufzeit analoge Definitionen. Vollständig iterative Algorithmen besitzen stets eine konstante Speichernutzung, sofern keine zusätzlichen Datenstrukturen verwendet werden.
Mathematische Symbole und Formeln

Informatik ist, wie viele Naturwissenschaften, stark mathematisiert. Eine Laufzeitabschätzung wäre ohne mathematische Formeln und Methoden gar nicht möglich. Damit man die Laufzeit- und Speichernutzungsabschätzung zu den einzelnen Algorithmen nachvollziehen kann, habe ich hier die dazu nötigen mathematischen Umformungen zusammengefasst. Einige mathematische Symbole werden von älteren Browsern nicht unterstützt. Bitte verwenden Sie daher mindestens Internet Explorer 4.0, Netscape 6.0 oder Opera 5.0.

Θ-Notation
f(x) = Θ(g(x)) genau dann wenn f(x) = Ω(g(x)) und f(x) = Ο(g(x))


Ω-Notation
f(x) = Ω(g(x)) genau dann wenn f(x) >= c*g(x) für eine gewisse Konstante c (c > 0) und einen Startwert x0


Ο-Notation
f(x) = Ο(g(x)) genau dann wenn f(x) <= c*g(x) für eine gewisse Konstante c (c > 0) und einen Startwert x0


Logarithmus-Umformung 1
"alog(b*c)" ist äquivalent zu "alog(b) + alog(c)"


Logarithmus-Umformung 2
"c^(alog(b))" ist äquivalent zu "b^alog(c)"


Logarithmus-Umformung 3
"alog(b)" ist äquivalent zu "1/(blog(a))"


Interpretation von for-Schleifen
"for i:= a to b do { ... }" wird interpretiert als "∑(i=a..b, ...)"


Indexvertauschung in ∑-Formeln
"∑(i=a..b, ...)" ist wegen der Kommutativität der Addition äquivalent zu "∑(i=b..a, ...)"


Indexsubstitution in ∑-Formeln
"∑(i=a..b, f(i))" ist mit der Funktion j(i) bzw. i(j) äquivalent zu "∑(j=c..d, f(j))" mit c = j(a), d = j(b) und f(j) = f(i(j))


spezielle ∑-Formel 1
"∑(i=1..n, i)" ist äquivalent zu "n*(n+1)/2"


spezielle ∑-Formel 2
"∑(i=1..n, i²)" ist äquivalent zu "n*(n+1)*(2n+1)/6"


spezielle ∑-Formel 3
"∑(i=0..n, qi)" ist äquivalent zu "(1-qn+1)/(1-q)"


Summenabschätzung
Summen über momotone Funktionen lassen sich i.R. mittels des zugehörigen Integrals asymtotisch abschätzen. Sei "∑(i=m..n, Θ(f(i))), m beliebig aber fest, f(x) >= 0, fast überall stetig und monoton (x ε R, x >= m)" und F(x) sei die zu f(x) gehörige Stammfunktion. Dann gilt "∑(i=m..n, Θ(f(i))) = Θ(F(n))".

Implizit folgt damit aus "Formeltransformation 1" und "k = 1" "T(n) = Θ(F(n))". Insbesondere gilt dies für f(i)/F(n): c/n, i/n², i²/n³, logi/nlogn, qi/qn, ...


Formeltransformation 1
"T(n) = k*T(n-1) + f(n), T(m) = c, m beliebig aber fest" (offene Form) ist äquivalent zu "T(n) = kn-m*c + ∑(i=1+m..n, kn-i*f(i))" oder "T(n) = kn-m*c + ∑(i=0..n-m-1, ki*f(n-i))" (geschlossene Form).


Formeltransformation 2
"T(n) = a*T(n/b) + f(n), T(m) = c, m beliebig aber fest, a >= 1, b > 1" (offene Form) ist äquivalent zu "T(n) = ∑(i=0..blog(n/m/b), ai*f(n/bi)) + a^(blog(n/m))" (geschlossene Form).


Master-Theorem, Fall 1
Aus "Formeltransformation 2" und "f(n) = Ο(n^((bloga)-e)), e > 0" folgt "T(n) = Θ(n^(bloga))".


Master-Theorem, Fall 2
Aus "Formeltransformation 2" und "f(n) = Θ(n^(bloga))" folgt "T(n) = Θ((n^(bloga))*logn)".


Master-Theorem, Fall 3
Aus "Formeltransformation 2" und "f(n) = Ω(n^((bloga)+e)), a*f(n/b) <= c*f(n), e > 0, c < 1, n > b" folgt "T(n) = Θ(f(n))".