Alda - User contributions [en]

Talk:Main Page

2008-07-07T17:01:18Z

Alter: /* Zu Übung 11 */

== Änderungsvorschläge ==

=== zum Übungsbetrieb ===

Bitte die Email-Adressen der Tutoren eintragen, so wie es schon für Thomas Gerlach der Fall ist.
:Ich hatte jetzt nur die von Daniel (Do Gruppe) parat, habe sie mal eingetragen [[Special:Contributions/83.189.36.163|83.189.36.163]] 13:41, 13 April 2008 (UTC)

Die Übungen sind ja auch mal wieder extrem einfach und beanspruchen fast grkeine Zeit... Ich sitze jetzt schon so ziemlich den ganzen Tag der zweiten Aufgabe und keine Ende in sicht... als ob wir sonst keine Uni hätten.

==Zu Übungsblatt 2:==
In-place sortieren bei selection- und quick-sort ist mir ja noch einsichtig - aber bei merge-sort? ist der algorithmus nicht so spezifiziert, dass man eine neue liste/ein neues array aufbaut? oder sollen wir einfach noch ne kapsel-funktion schreiben, und die neu-aufgebaute liste am ende auf die ausgangsliste verweisen lassen; das wäre zwar kein in-place sortieren im eigentlichen sinne, aber anders kann ich es mir gerade nicht vorstellen.
:Also ich denke eher, dass das ein Fehler in der Aufgabenstellung ist. Quick und Merge in-place ist doch schon ziemlich kontroproduktiv...
::U. Köthe: In-place war in der Aufgabe nicht so gemeint, dass die Algorithmen intern keinen zusätzlichen Speicher verwenden dürfen, sondern dass das sortierte Array am Ende das unsortierte überschreiben soll.

Vllt. hilft das ja noch jemandem, der mit seinem quick-sort nicht zu Rande kommt: hab die Erfahrung gemacht, dass es keine korrekten Ergebnisse liefert, wenn man die repeat-untils aus der Spezifikation aus der Vorlesung einfach in whiles mit umgekehrter Bedingung macht (also aus repeat...until a[j]<=a[p] etwa while a[j]>a[p]) - python hat zwar keine repeat-untils, aber mit einem while True...und einem den Block abschließenden if a[j]<=a[p]:break kann man das simulieren, und dann kann man einfach die spezifikationen in python eintippen.

== Spam ==

Ich schlage vor einfach mal alle nicht deutsch(sprachig)en IPs zu verbieten, da die Bots wohl aus USA/AU kommen (http://www.who.is/whois-ip/ip-address/208.17.80.5/).
Ausserdem vorsicht beim reverten, vorhin sind da ein paar Einträge verlorengegangen.

Eine weitere Möglichkeit besteht darin, die Website unter Passwortschutz zu stellen und das Passwort in der Vorlesung bekanntzugeben. Dieses Passwort muss ja kein großes Geheimnis sein, sondern soll nur Bots daran hindern, die Seite zu manipulieren.

Finde ich alles nicht so sinnvoll. Reicht es nicht, dass man sich registrieren muss? Hat den weiteren Vorteil das man den Autoren mal Namen zuordnen kann... [[User:Thorben|Thorben]]

== Zu Übung 11 ==

Bevor man in gnuplot Kreise zeichnen kann muss der Befehl: "set parametric" ausgeführt werden. Solche Sahcen sind einfach nur extrem zeitraubend...--[[Special:Contributions/84.57.250.56|84.57.250.56]] 17:29, 5 July 2008 (UTC)

Gibt es einen überschaubaren Weg, um den Mittelpunkt eines Dreieckumkreises zu berechnen? Das beschäftigt mich schon sehr lange, obwohl es doch eigentlich nur ein Detail sein sollte. Geometrisch ist es ja recht einfach über die Mittelsenkrechten, aber wie man aus den Koordinaten der Eckpunkte dazu kommt, wird mir genausowenig klar wie das ähnliche Problem bei der Koch-Schneeflocke.

:Die ganze Aufgabe besteht aus solchen Details die sie nicht schwerer machen, aber sie einfach unglaublich viel Zeit braucht. Mit Zerkel und Lineal vielleicht einfach... Um den Mittelpunkt des Umkreises aus zwei Mittelsenkrechten zu berechnen musst du deren Gleichungen gleichsetzen (Die Koordinaten des Schnittpunkts sind ja für beide Linien genau gleich), also z.B.:

m1: y = 2x + 3
m2: y = -0,5x + 1

2x + 3 = -0,5x + 1
2,5x = -2
x = -2/1,5

:Diese Gleichung kann in Python einfach berechnet werden (da sie ja immer die gleiche Form hat...) wenn du m (also die Steigung) und b (also den y-Achsenabschnitt) der Mittelsenkrechten kennst, also etwa:

x = (m2.bisector.b - m1.bisector.b) / (m1.bisector.m - m2.bisector.m)

:Dann setzt du das x in eine der Gleichungen ein, und hast somit den Schnittpunkt gefunden.--[[User:Alter|Alter]] 17:01, 7 July 2008 (UTC)

Talk:Main Page

2008-05-19T19:31:45Z

Alter:

Talk:Main Page

2008-05-16T14:59:02Z

Alter:

Talk:Main Page

2008-05-13T18:19:42Z

Alter:

Talk:Effizienz

2008-05-12T13:52:29Z

Alter: Weiterführende Links

== Weiterführende Links ==

* Deutsche Wikipedia: http://de.wikipedia.org/wiki/Landau-Symbole
* linux-related.de: http://www.linux-related.de/index.html?/coding/o-notation.htm

Talk:Main Page

2008-05-12T13:40:17Z

Alter: Undo revision 742 by 61.155.41.165 (Talk)

Talk:Main Page

2008-05-12T10:43:06Z

Alter:

Talk:Main Page

2008-05-11T11:53:08Z

Alter:

Effizienz

2008-05-10T10:30:46Z

Alter:

(Vorlesung 7.5.:)

== Laufzeit ==
Die Laufzeit ist für den Benutzer ein wichtiges Kriterium.
Schwierigkeit bei der Bestimmung: Die Laufzeit hängt von vielen Faktoren ab die evtl. nicht kontrollierbar sind:
* Prozessor/Auslastung des Systems
* Speicher/Cache/Bus
* Compiler/Optimierer des Compilers (Compiler auf verschiedene Architekturen optimiert?)
* Geschick des Programmierers
* Daten (Beispiel Quicksort: Best case und worst case[Vorsortierter Input] stark unterschiedlich)
All diese Faktoren sind untereinander abhängig.

Laufzeitvergleiche sind mit Vorsicht zu interpretieren.
Generell sollten bei Vergleichen möglichst wenige Parameter verändert werden, z.B.
* gleiches Programm(gleiche Kompilierung), gleiche Daten, andere Prozessoren
oder
*gleiche CPU, Daten, andere Programme (Vergleich von Algorithmen)

Beobachtung: Durch Laufzeitmessung ist schwer festzustellen, ob ein Alg prinzipiell besser ist als ein anderer.

== Komplexität ==
Komplexitätsbetrachtungen ermöglichen den Vergleich der prinzipiellen Eigenschaften von Algorithmen unabhängig von einer Implementation, Umgebung etc.

Eine einfache Möglichkeit ist das Zählen der Aufrufe einer Schlüsseloperation. Beispiel Sortieren:
* Anzahl der Vergleiche
* Anzahl der Vertauschungen

=== Beispiel: Selection Sort ===

for i in range(len(a)-1):
max = i
for j in range(i+1, len(a)):
if a[j] < a[max]:
max = j
a[max], a[i] = a[i], a[max] # swap

*Anzahl der Vergleiche: Ein Vergleich in jedem Durchlauf der inneren Schleife. Es ergibt sich folgende Komplexität:
*:Ingesamt <math>\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1}1 = \frac{N}{2} (N-1) \!</math> Vergleiche.

*Anzahl der Vertauschungen: Eine Vertauschung pro Durchlauf der äußeren Schleife:
*:Insgesamt <math>N-1 \!</math> Vertauschungen

Die Komplexität wird durch die Operationen bestimmt, die am häufigsten ausgeführt werden, hier also die Anzahl der Vergleiche. Die Anzahl der Vertauschungen ist kein geeignetes Kriterium für die Komplexität von selection sort, weil der Aufwand in der inneren Schleife ignoriert wird.

=== Fallunterscheidung: Worst und Average Case ===

Die Komplexität ist in der Regel eine Funktion der Eingabegröße (Anzahl der Eingabebits, Anzahl der Eingabeelemente). Sie kann aber auch von der Art der Daten abhängen, nicht nur von der Menge, z.B. vorsortierte Daten bei Quicksort. Um von der Art der Daten unabhängig zu werden, kann man zwei Fälle der Komplexität unterscheiden:

* Komplexität im ungünstigsten Fall
*: Der ungünstigste Fall ist die Eingabe gegebener Länge, für die der Algorithmus am langsamsten ist. Der Nachteil dieser Methode besteht darin, dass dieser ungünstige Fall in der Praxis vielleicht gar nicht oder nur selten vorkommt, so dass sich der Algorithmus in Wirklichkeit besser verhält als man nach dieser Analyse erwarten würde. Beim Quicksort-Algorithmus mit zufälliger Wahl des Pivot-Elements müsste z.B. stets das kleinste oder größte Element des aktuellen Intervalls als Pivot-Element gewählt werden, was äußerst unwahrscheinlich ist.
* Komplexität im durchschnittlichen/typischen Fall
*: Der typische Fall ist die mittlere Komplexität des Algorithmus über alle möglichen Eingaben. Dazu muss man die Wahrscheinlichkeit jeder möglichen Eingabe kennen, und berechnet dann die mittlere Laufzeit über dieser Wahrscheinlichleitsverteilung. Leider ist die Wahrscheinlichkeit der Eingaben oft nicht bekannt, so dass man geeignete Annahmen treffen muss. Bei Sortieralgorithmen können z.B. alle möglichen Permutationen des Eingabearrays als gleich wahrscheinlich angenommen werden, und der typische Fall ist dann die mittlere Komplexität über alle diese Eingaben. Oft hat man jedoch in der Praxis andere Wahrscheinlichkeitsverteilungen, z.B. sind die Daten oft "fast sortiert" (nur wenige Elemente sind an der falschen Stelle). Dann verhält sich der Algorithmus ebenfalls anders als vorhergesagt.

Wir beschränken uns in dieser Vorlesung auf die Komplexität im ungünstigseten Fall. '''Exakte''' Formeln für Komplexität sind aber auch dann schwer zu gewinnen, wie das folgende Beispiel zeigt:

=== Beispiele aus den Übungen (Gemessene Laufzeiten für Mergesort/Selectionsort) ===

* Mergesort: <math>\frac{0,977N\log N}{\log 2} + 0,267N-4.39 \!</math>
*: andere Lösung: <math>1140 N\log(N) - 1819N + 6413 \!</math>
* Selectionsort: <math>\frac{1}{2}N^2 - \frac{1}{2N} - 10^{-12} \!</math>
*: andere Lösung: <math>1275N^2 - 116003^N + 11111144 \!</math>

Aus diesen Formeln wird nicht offensichtlich, welcher Algorithmus besser ist.
Näherung: Betrachte nur '''sehr große Eingaben''' (Meist sind alle Algorithmen schnell genug für kleine Eingaben). Dieses Vorgehen wird als '''Asymptotische Komplexität''' bezeichnet (N gegen unendlich).

=== Asymptotische Komplexität am Beispiel Polynom ===

Polynom: <math>ax^2+bx+c=p\!</math>

<math>x \!</math> sei die Eingabegröße, und wir betrachten die Entwicklung von <math>p \!</math> in Abhängigkeit von <math>x \!</math>.

* <math>x=0 \!</math>
*: <math>p=c \!</math>
* <math>x=1 \!</math>
*: <math>p=a+b+c \!</math>
* <math>x=1000 \!</math>
*: <math>p=1000000a+1000b+c \approx 1000000a\!</math>
* <math>x \to \infty \!</math>
*: <math>p \approx x^2a\!</math>

Für sehr große Eingaben verlieren also b und c immer mehr an Bedeutung, so dass am Ende nur noch a für die Komplexitätsbetrachtung wichtig ist.

== O-Notation ==
* Intuitiv: Für große N dominieren die am schnellsten wachsenden Terme.
* Formale Definition:
*: Asymptotische Komplexität: Für zwei Funktionen f(x) und g(x) definiert man
*::<math>f(x) \in \mathcal{O}(g(x))</math>
*:(sprich "f ist in \mathcal{O}(g)" oder "f ist von derselben Größenordnung wie g") genau dann wenn es eine Konstante <math>c</math> und ein Argument <math>x_0</math> gibt, so dass
*::<math>\forall x > x_0:\quad f(x) \le c g(x)</math>.
*:Die Idee hinter dieser Definition ist, dass g(x) eine wesentlich einfachere Funktion ist als f(x), die sich aber nach geeigneter Skalierung (Multiplikation mit c) und für große Argumente x im wesentlichen genauso wie f(x) verhält. Man kann deshalb in der Algorithmenanalyse f(x) durch g(x) ersetzen. <math>f(x) \in \mathcal{O}(g(x))</math> spielt für Funktionen eine ähnliche Rolle wie der Operator ≤ für Zahlen: Falls a ≤ b gilt, kann bei einer Abschätzung von oben ebenfalls a durch b ersetzt werden.
=== Ein einfaches Beispiel ===

[[Image:Sqsqrt.png]]

Rot = <math>x^2 \!</math>
Blau = <math>\sqrt{x} \!</math>

<math>\sqrt{x} \in \mathcal{O}(x^2)\!</math> weil <math>\sqrt{x} \le c x^2\!</math> für alle <math>x < x_0 = 1 \!</math> und <math>c = 1\!</math>, oder auch für <math>x < x_0 = 4 \!</math> und <math>c = 1/16</math> (die Wahl von c und x0 in der Definition von O(.) ist beliebig, solange die Bedingungen erfüllt sind).

=== Komplexität bei kleinen Eingaben ===

Algorithmus 1: <math>\mathcal{O}(N^2) \!</math>
Algortihmus 2: <math>=\mathcal{O}(N\log{N}) \!</math>

Algorithmus 2 ist schneller (Von geringerer Komplexität), aber bei vielen wiederholten kleinen Eingaben ist Algorithmus 1 schneller.

=== Eigenschaften der O-Notation(Rechenregeln) ===

# Transitiv:
#: <math>f(x) \in \mathcal{O}(g(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) \in \mathcal{O}(h(x)) \!</math>
# Additiv:
#: <math>f(x) \in \mathcal{O}(h(x)) \land g(x) \in \mathcal{O}(h(x)) \to f(x) + g(x) \in \mathcal{O}(h(x)) \!</math>
# Für Monome gilt:
#: <math>x^k \in \mathcal{O}(x^k)) \land x^k \in \mathcal{O}(x^{k+j}), \forall j \ge 0 \!</math>
# Multiplikation mit einer Konstanten:
#: <math>f(x) \in \mathcal{O}(g(x)) \to cf(x) \in \mathcal{O}(g(x))\!</math>
#: andere Schreibweise:
#: <math>f(x) = cg(x) \to f(x) \in \mathcal{O}(g(x))\!</math>
#: Beispiel: <math>ax^2+bx+c \in \mathcal{O}(x^2)\!</math>
#: Folgerung für Polynome: <math>a_0+a_1x + ... + a_nx^n \in \mathcal{O}(x^n)\!</math>
# Logarithmus:
#: <math>a, b \neq 1\!</math>
#: <math>\log_{a}{x} \in \mathcal{O}(\log_{b}{x})\!</math>
#: Die Basis des Logarithmus spielt also keine Rolle.
#: Beweis hierfür:
#: <math>\log_{a}{x} = \frac{\log_{b}{x}}{\log_{b}{a}}\!</math>
#: <math>c = \log_{b}{a}\!</math>
#: <math>c\log_{a}{x} = \log_{b}{x}\!</math>, wird hier die Regel für Multiplikation mit einer Konstanten angewendet fällt der Konstante Faktor weg.
#: Insbesondere gilt auch <math>\log_{a}{x} \in \mathcal{O}(\log_{2}{x})\!</math>, es kann also immer der 2er Logarithmus verewendet werden.

== O-Kalkül ==

# <math>f(x) \in \mathcal{O}(f(x))\!</math>
# <math>\mathcal{O}(\mathcal{O}(f(x))) \in \mathcal{O}(f(x))\!</math>
# <math>k\mathcal{O}(f(x)) \in \mathcal{O}(f(x))\!</math>
# <math>\mathcal{O}(f(x))+c \in \mathcal{O}(f(x))\!</math>
# Sequenzregel:
#: <math>g(x) \in \mathcal{O}(f(x)) \to \mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(f(x))\!</math>, oder <math>f(x) \in \mathcal{O}(g(x)) \to \mathcal{O}(f(x)) + \mathcal{O}(g(x)) \in \mathcal{O}(g(x))\!</math>
#: Informale Schreibweise: <math>\mathcal{O}(max(f(x), (g(x))\!</math>
# Aufruf, Verschachtelungsregel:
#: <math>\mathcal{O}(f(x)) * \mathcal{O}(g(x)) \in \mathcal{O}(f(x) * g(x))\!</math>

=== O-Kalkül auf das Beispiel des Selectionsort angewandt ===
Selectionsort: <math>f(N) = \frac{N^2}{2} - \frac{N}{2} \in \mathcal{O}(\frac{N^2}{2}) \in \mathcal{O}(N^2)\!</math>

Oder via Multiplikationsregel:
<math>\mathcal{O}(f(x))*\mathcal{O}(g(x)) \in \mathcal{O}(f(x)*g(x))\!</math>
: Äußere Schleife: <math>\mathcal{O}f(x)\!</math>
:: <math>f(N) = N/2 = \mathcal{O}(N)\!</math>
: Innere Schleife: <math>\mathcal{O}g(x)\!</math>
:: <math>g(N) = N-2 = \mathcal{O}(N)\!</math>

:<math>\mathcal{O}(f(N))*\mathcal{O}(g(N)) \in \mathcal{O}(f(x)*g(x))\!</math>

::<math>\mathcal{O}(N)*\mathcal{O}(N) \in \mathcal{O}(N*N) \in \mathcal{O}(N^2)\!</math>

Nach beiden Vorgehensweisen erreichen wir also den Schluss, dass der Selectionsort die asymptotische Komplexität <math>\mathcal{O}(N^2)\!</math> besitzt.

=== Zusammenhang zwischen Komplexität und Laufzeit ===
Wenn ein Rechenschritt 1ms dauert erreichen verschiedene komplexe Algorithmen folgende Leistungen

{| class="wikitable" style="text-align:left"
|+
|-
! Komplexität !! Operationen in 1s !! Operationen in 1min !! Operationen in 1h
|-
! <math>\mathcal{O}(N)</math>
| 1000 || 60.000 || 3.600.000
|-
! <math>\mathcal{O}(n\log{N})</math>
| 140 || 4895 || 204094
|-
! <math>\mathcal{O}(N^2)</math>
| 31 || 244 || 1897
|-
! <math>\mathcal{O}(N^3)</math>
| 10 || 39 || 153
|-
! <math>\mathcal{O}(2^N)</math>
| 9 || 15 || 21
|}

=== Exponentielle Komplexität ===
Der letzte Fall (<math>\mathcal{O}(2^N)</math>) ist von exponentieller Komlexität, das bedeutet eine Verdopplung des Aufwands bewirkt nur, dass die maximale Problemgröße um eine Konstante wächst. Algorithmen mit exponentieller Komplexität heißen '''ineffizient'''.

Dagegen bewirkt bei einer Komplexität von <math>\mathcal{O}(N^3)</math> ein verdoppelter Aufwand immer noch eine Steigerung der maximalen Problemgörße um den Faktor <math>\sqrt[3]{2}</math>.

Talk:Main Page

2008-05-10T09:22:25Z

Alter: Undo revision 638 by 218.104.219.203 (Talk)

Effizienz

2008-05-08T13:08:47Z

Alter:

Effizienz

2008-05-08T12:51:47Z

Alter: New page: (Vorlesung 7.5.:) == Laufzeit == Die Laufzeit ist für den Benutzer ein wichtiges Kriterium. Schwierigkeit bei der Bestimmung: Die Laufzeit hängt von vielen Faktoren ab die evtl. nicht k...

File:Sqsqrt.png

2008-05-08T12:51:19Z

Alter:

Talk:Main Page

2008-05-07T22:12:48Z

Alter: Undo revision 576 by 59.151.53.82 (Talk)

Talk:Main Page

2008-05-07T17:42:28Z

Alter: /* Spam */ new section

Talk:Main Page

2008-05-07T17:40:41Z

Alter: Wieder zu unbespammter Version reverted...

Talk:Main Page

2008-05-05T14:03:19Z

Alter: Spam gelöscht, reverted

Einführung

2008-04-23T17:40:05Z

Alter: /* Definition von Datenstrukturen */

== Definition von Algorithmen ==

Es gibt viele Definitionen von Algorithmen. Hier sind die Ergebnisse einer Google-Suche auf [http://www.google.de/search?hl=de&defl=en&q=define:Algorithm&sa=X&oi=glossary_definition&ct=title englisch] und auf
[http://www.google.de/search?hl=de&defl=de&q=define:Algorithmus&sa=X&oi=glossary_definition&ct=title deutsch]. Die Grundidee ist aber immer gleich:

Ein '''Algorithmus''' ist eine Problemlösung durch endlich viele elementare Schritte. Die Teile der Definition bedürfen näherer Erläuterung:

;Problemlösung: Damit ein Algorithmus ein Problem (genauer: eine Menge von gleichartigen Problemen) lösen kann, muss das Problem zunächst definiert (''spezifiziert'') werden. Die '''Spezifikation''' legt fest, ''was'' der Algorithmus erreichen soll, sagt aber nichts über das ''wie''. Die Spezifikation beschreibt somit relevante Eigenschaften des Systemzustands ''vor'' und ''nach'' der Ausführung des Algorithmus (sogenannte '''Vor-''' und '''Nachbedingungen'''), während der Algorithmus einen bestimmten ''Lösungsweg'' repräsentiert. Mit Hilfe der Spezifikation kann gezeigt werden, dass der Algorithmus tatsächlich eine Lösung des gestellten Problems liefert. Diese Frage untersuchen wir im Kapitel [[Korrektheit]].
;Endlich viele Schritte: Die Forderung nach endlich vielen Schritten unterstellt, dass jeder einzelne Schritt eine gewisse Zeit benötigt, also nicht unendlich schnell ausgeführt werden kann. Damit ist diese Forderung äquivalent zu der Forderung, dass der Algorithmus in endlicher Zeit zum Ergebnis kommen muss. Der Sinn einer solchen Forderung leuchtet aus praktischer Sicht unmittelbar ein. Interessant ist darüber hinaus die Frage, wie man mit möglichst wenigen Schritten, also möglichst schnell, zur Lösung kommt. Diese Frage untersuchen wir im Kapitel [[Effizienz]].
;Elementare Schritte: Im weiteren Sinne verstehen wir unter einem elementaren Schritt ein Teilproblem, für das bereits ein Algorithmus bekannt ist. Im engeren Sinne ist die Menge der elementaren Schritte durch die Hilfsmittel vorgegeben, mit denen der Algorithmus ausgeführt werden soll, also z.B. durch die Hardware oder die Programmiersprache. Wir gehen darauf im nächsten Abschnitt näher ein.

=== Zur Frage der elementaren Schritte ===

Welche Schritte als elementar angesehen werden können, hängt sehr stark vom Kontext der Aufgabe und den Hilfsmitteln zu ihrer Lösung ab. Ein interessantes Beispiel ist die Geometrie der alten Griechen, wo geometrische Probleme in der Ebene allein mit Zirkel und Lineal gelöst werden. In diesem Fall sind folgende elementare Operationen erlaubt:
* das Markieren eines Punktes (beliebig in der Ebene oder als Schnittpunkt zwischen bereits gezeichneten Linien),
* das Zeichnen einer Geraden durch zwei Punkte,
* das Zeichnen eines Kreises um einen Punkt,
* das Abgreifen des Abstands zwischen zwei Punkten mit dem Zirkel.
Auf der Basis dieser Operationen kann zum Beispiel kein Algorithmus für die Dreiteilung eines beliebigen Winkels definiert werden, während der Algorithmus für die Zweiteilung sehr einfach ist.

Eine völlig andere Menge von elementaren Operationen ergibt sich für arithmetische Berechnungen mit Hilfe des Abacus (Rechenbrett), der seit der Römerzeit in Europa weit verbreitet war. Hier werden Zahlen durch die Positionen von Perlen auf Rillen oder Drähten dargestellt und Berechnungen durch deren Verschiebung. Eine ausführliche Beschreibung der wichtigsten Abacus-Algorithmen findet sich unter [http://webhome.idirect.com/~totton/abacus/ The Bead Unbuffled] von Totton Heffelfinger und Gary Flom.

Die moderne Auffassung von elementaren Operationen wird durch die Berechenbarkeitstheorie (ein Teilgebiet der theoretischen Informatik) bestimmt. Verschiedene Mathematiker (darunter die Pioniere Alan Turing, Alonso Church, Kurt Gödel, Stephen Kleene und Emil Post) haben seit den 1930er Jahren versucht, den intuitiven Begriff der Berechenbarkeit einer Funktion zu formalisieren und sind dabei zu völlig verschiedenen Lösungen gelangt (z.B. Turingmaschine, Lambda-Kalkül, μ-Rekursion und WHILE-Programm). Interessanterweise stellte sich heraus, dass diese Lösungen alle die gleiche Mächtigkeit haben: Obwohl die elementaren Operationen jeweils ganz anders definiert sind, ist die Menge der damit berechenbaren Funktionen immer gleich. Die [http://en.wikipedia.org/wiki/Church_thesis Church-Turing-These] besagt, dass es prinzipiell unmöglich ist, eine mächtigere Definition von elementaren Operationen zu finden, aber dies ist unbewiesen. Am bequemsten für die Praxis sind die [http://de.wikipedia.org/wiki/WHILE-Programm WHILE-Programme], da sie sich direkt auf die heute gebräuchliche Hardware-Architektur abbilden lassen. Die elementaren Operationen eines WHILE-Programms lauten in erweiterter Backus-Naur Notation:
P ::= x[i] = x[j] + c
| x[i] = x[j] - c
| P; P
| WHILE x[i] != 0 DO P DONE
wobei <tt>c</tt> ein beliebiges ganzahliges Literal (eine ausgeschriebene ganze Zahl) und <tt>x[i]</tt> die Speicherzelle <tt>i</tt> bezeichnet. Alle Speicherzellen können ganze Zahlen aufnehmen und sind anfangs mit Null belegt. Darüber hinaus wird vorausgesetzt, dass mindestens soviele Speicherzellen vorhanden sind, wie der gegebene Algorithmus benötigt, und jede Speicherzelle groß genug ist, um die größte auftretende Zahl aufzunehmen. Beide Annahmen sind in der Praxis nicht immer erfüllt.

Die Zerlegung jedes Problems in Form eines WHILE-Programms (oder eines äquivalenten Formalismus der Berechenbarkeitstheorie) ist für unsere Zwecke aber zu feinkörnig: Sie würde bedeuten, dass alle Algorithmen auf einem sehr einfachen Prozessor in Assembler programmiert werden müssten. Statt dessen definiert man ''höhere Programmiersprachen'', die wichtige Algorithmen wie z.B. die arithmetischen Operationen mit ganzen Zahlen und Gleitkomma-Zahlen bereits als elementare Operationen enthalten. Weitere nicht ganz so wichtige Funktionen wie die Wurzel oder der Logarithmus werden in Programmbibliotheken angeboten, die standardmäßig mitgeliefert werden. In der Praxis betrachtet man eine Operation deshalb als elementar, wenn sie von einer typischen Programmiersprache oder einer typischen Standardbibliothek unterstützt wird. In dieser Vorlesung wählen wir die Operationen und Bibliotheken der Programmiersprache [http://www.python.org Python]. Wenn ein Algorithmus Anforderungen stellt, die nicht selbstverständlich sind, müssen sie als ''Requirements'' explizit angegeben werden. Wir werden darauf im Kapitel [[Generizität]] zurückkommen.

=== Zur Geschichte ===

{| border="0" cellspacing="0" cellpadding="5"
|-valign="top"
| Algorithmen wurden bereits im Altertum verwendet. Besonders die alten Griechen haben Pionierarbeit geleistet, z.B. auf dem Gebiet der Arithmetik (Euklidischer Algorithmus für den größten gemeinsamen Teiler von zwei Zahlen, Sieb des Eratosthenes zur Bestimmung von Primzahlen) und der Geometrie (Teilung einer Strecke oder eines Winkels nur mit Zirkel und Lineal). Der Begriff ''Algorithmus'' ist vom Namen des arabischen Gelehrten Muhammed Al Chwarizmi (ca. 783-850) abgeleitet, der in seinem Werk „Über das Rechnen mit indischen Ziffern“ (um 825) grundlegende Verfahren für das Rechnen im dekadischen Positionssystem beschrieben hat. Im 12. Jahrhundert wurde dieses Buch ins Lateinische übersetzt, und die Einleitung begann mit den Worten „Dixit Algorismi“ (Al Chwarizmi hat gesagt). Ab etwa 1200 wurden die neuen Rechenmethoden als „Algorismus de integris“ bzw. „Algorismus vulgaris“ (Rechnen mit ganzen Zahlen, d.h. Grundrechenarten und Wurzelziehen) sowie „Algorismus de minutiis“ (Bruchrechnung) zum festen Bestandteil der mathematischen Ausbildung im Rahmen der sieben freien Künste. Dabei diente der Begriff Algorithmus unrsprünglich vor allem zur Abgrenzung des schriftlichen Rechnens mit indischen/arabischen Zahlen (wie wir es noch heute in der Schule lernen) vom traditionellen mechanischen Rechnen mit Abacus und römischen Zahlen, das noch bis ca. 1500 in Europa vorherrschend blieb.

Die allgemeinere Bedeutung des Wortes Algorithmus als systematische Rechenvorschrift war jedoch ebenfalls schon früh gebräuchlich. Dies zeigt zum Beispiel der Titel des Buches „Algorismus proportionum“ (Rechenkunst mit Proportionen, ca. 1350) von Nicole Oresme, wo erstmals die Rechenregeln für Potenzen mit rationalen Exponenten beschrieben werden. Durch die steigenden Anforderungen des kaufmännischen Rechnens und der Navigation verbreitete sich die algorithmische Denkweise ab etwa 1500 rasch. Der Buchdruck machte mit Werken wie Adam Ries' „Rechenung auff der linihen und federn“ (d.h. mit Abacus und mit indischen/arabischen Zahlen, zuerst 1522) die grundlegenden Rechenalgorithmen einem breiten Bevölkerungskreis bekannt. Umfangreiche gedruckte Tafelwerke, z.B. der „Canon“ von G.J. Rhaeticus (1551) mit bis zu siebenstelligen Tabellen der trigonometrischen Funktionen, erlaubten es, komplizierte Berechnungen auf einfache Schritte (Addition, Subtraktion sowie Nachschlagen in der Tabelle) zurückzuführen. Unsere heutige Verwendung des Begriffs geht wohl auf Alonso Church's Aufsatz „An Unsolvable Problem of Elementary Number Theory“ (1936) zurück, wo die Berechenbarkeit einer Funktion mit der Existenz eines terminierenden Berechnungsalgorithmus gleichgesetzt wird.
| [[Image:Al-Khwarizmi.jpg]] Standbild Al Chwarizmis in Teheran
|}

== Definition von Datenstrukturen ==

Der Speicher eines Computers enthält eine Folge von Zeichen aus einem gegebenen Alphabet. Bei fast allen heutigen Computern ist dies eine Folge von Bits aus dem Alphabet {0,1}. Eine '''Datenstruktur''' ordnet eine Bitfolge in Gruppen und gibt jeder Gruppe eine Bedeutung. Der Gruppierungsprozess kann dann hierarchisch fortgesetzt werden.

Die selben Bits können somit völlig verschiedene Bedeutungen annehmen, ja nachdem in welcher Datenstruktur sie sich befinden. Man betrachte z.B. die Folge von 32 Bits:
11111100011000100110010101101110
Wenn wir diese Folge als eine einzige Gruppe betrachten und als positive ganze Zahl in Binärdarstellung (unsigned integer) interpretieren, ergibt sich die Dezimalzahl 4234306926. Interpretieren wir dieselbe Gruppe als vorzeichenbehaftete ganze Zahl in [http://de.wikipedia.org/wiki/Zweierkomplement Zweierkomplement]-Darstellung (signed integer), ergibt sich statt dessen die Dezimalzahl -60660370. 
Alternativ können wir die Folge in vier Gruppen zu 8 Bit gruppieren, und die Gruppen als Zeichencodes im Latin-1 Zeichensatz interpretieren. Wir erhalten die Zeichenkette "üben":
11111100 01100010 01100101 01101110 => üben
Interpretieren wir dieselben Gruppen hingegen als Farbe im RGBA System, erhalten wir ein halbtransparentes Rosa (Rot: 252, Grün: 98, Blau: 101, Alpha: 110). 
Eine weitere Interpretation ist diejenige als 32-Bit Gleitkommazahl gemäß [http://en.wikipedia.org/wiki/IEEE_floating-point_standard IEEE Standard 754] (float). Dabei wird die Folge in Gruppen zu 1 Bit, 8 Bit und 23 Bit eingeteilt:
1 11111000 11000100110010101101110
Die Gruppen werden als nicht-negative Binärzahlen gelesen, wobei die erste Gruppe das Vorzeichen <tt>s</tt> der Gleitkommazahl ist (0 bedeutet "+", 1 bedeutet "-"), die zweite ist ihr Exponent <tt>exp</tt> und die dritte die Mantisse <tt>m</tt> (Hier gilt <tt>s = 1</tt>, <tt>exp = 248</tt> und <tt>m = 6448494</tt>). Die Umrechnung in eine Gleitkommazahl erfolgt, gemäß IEEE Standard, nach folgender Formel: 
<tt>z = (1 - 2*s) * 2exp-127 * (1 + m * 2-23)</tt>. 
In Dezimaldarstellung ist dies rund <tt>-4.7020653*1036</tt>.

Im Sinne einer hierarchischen Gruppierung können wir jetzt z.B. eine Datenstruktur "Farbbild" definieren, indem wir viele RGBA-Werte zu einem 2-dimensionalen Array zusammenfassen. Eine Datenstruktur "komplexe Zahl" wird durch ein geordnetes Paar von Gleitkommazahlen gebildet, eine "Meßreihe" als Liste von ganzen Zahlen oder Gleitkommawerten (je nach Art der Messung), usw.

Die Bedeutung der einzelnen Gruppen ist dem Computer normalerweise nicht explizit bekannt. Vielmehr wird sie implizit durch die ''Menge der darauf ausführbaren Operationen'' definiert. Man bezeichnet die Verbindung einer Datenrepräsentation mit einer Menge von erlaubten Operationen als '''(Daten-)Typ''' oder als '''Klasse'''. Programmiersprachen, die ausgereifte Mechanismen zur Definition von Klassen bieten, werden als ''objekt-orientiert'' bezeichnet. Sprachen heißen ''streng typisiert'', wenn der Compiler bzw. Interpreter der Sprache sicherstellt, dass auf jeder Datenstruktur nur die jeweils explizit erlaubten Operationen ausgeführt werden (jeder Versuch, eine illegale Operation auszuführen, wird hier als Fehler signalisiert). Erfolgt diese Prüfung während der Compilierung (also während der Übersetzung des Quellcodes in eine Maschinensprache), spricht man von einer ''statisch typisierten Sprache''. Wird die Prüfung hingegen während der Ausführung des Programms durchgeführt, handelt es sich um eine ''dynamisch typisierte Sprache''. Python ist eine dynamisch-typisierte, objekt-orientierte Sprache. Streng typisiert ist sie allerdings nur für die vordefinierten Klassen. Bei benutzerdefinierten Klassen gibt es (wie bei den meisten anderen Programmiersprachen auch) Möglichkeiten, die erlaubten Operationen zu umgehen. Dies sollte man allerdings nur dann tun, wenn es einen wichtigen Grund gibt. Solange man sich nämlich auf die erlaubten Operationen beschränkt, ist eine große Menge von Fehlerquellen von vornherein ausgeschlossen.

Ein bestimmter Speicherbereich, der den Anforderungen an eine Klasse genügt (wo also die Bits in entsprechender Weise gruppiert und interpretiert werden), wird als '''Objekt''' dieser Klasse oder als '''Instanz''' bezeichnet. Jede Instanz hat eine eindeutige Identität, einen ''Schlüssel''. Innerhalb eines Programms wird dafür gewöhnlich die Speicheradresse des ersten Bytes der Instanz (also der Index der ersten Speicherzelle) verwendet. Dies ist besonders effizient, weil die Speicheradresse für jedes Objekt eindeutig und leicht feststellbar ist. Ist das Objekt hingegen als Datei gespeichert, benötigt man einen expliziten Schlüssel, z.B. den Dateinamen oder die URL.

Das Bitmuster selbst bzw. die daraus folgende Interpretation wird als '''Zustand''' oder '''Wert''' der Instanz bezeichnet. Daraus folgt, dass verschiedene Instanzen einer Klasse dennoch gleiche Werte haben können. Die Menge aller legalen Werte bilden den ''Wertebereich'' der Klasse. Werden Instanzen ausschließlich mit den explizit erlaubten Operationen ihrer Klasse manipuliert, können niemals illegale Werte entstehen. Es liegt auf der Hand, dass illegale Werte schwerwiegende Programmfehler darstellen, die man auf diese Weise vermeidet. [Computerviren tun genau das Gegenteil: Sie verwenden absichtlich verbotene Operationen, um dass Programm in einen illegalen, vom Angreifer gewünschten Zustand zu bringen. Dies ist möglich, weil nicht alle verbotenen Operationen automatisch als Fehler erkannt werden, siehe oben.]

Die meisten Programmiersprachen haben einen oder mehrere spezielle Typen für das Speichern von Objektschlüsseln. Die gebräuchlichsten Namen für diese Typen sind ''Zeiger'' (pointer), ''Referenz'' (reference) und ''Handle''. Wir verwenden das Wort '''Referenz'''. Ein Objekt der Klasse Referenz enthält also den Schlüssel eines anderen Objekts. Man sagt, dass die Referenz ''auf das andere Objekt verweist''. Diese Art der Indirektion ist uns heutzutage durch das Internet bestens vertraut: Jede WWW-Seite ist ein Objekt, und seine URL ist der dazugehörige Schlüssel. Hyperlinks und Lesezeichen (bookmarks) hingegen sind Referenzen, die mittels der URL auf andere Seiten verweisen.

Aus der Unterscheidung von Werten und Referenzen ergibt sich die wichtige Unterscheidung von ''Wertsemantik'' und ''Referenzsemantik''. Wird nämlich ein Objekt an eine Variable zugewiesen
x = anObject
so hängt die korrkte Verwendung der Variablen <tt>x</tt> davon ab, ob sie das Objekt in Form eines Wertes oder einer Referenz speichert. Im ersten Fall wird das Objekt selbst kopiert, und es entsteht ein neues Objekt mit neuer Identität, aber gleichem Zustand. Im andern Fall wird nur der Schlüssel kopiert, und die Referenz verweist nach wie vor auf das ursprüngliche Objekt. Ist <tt>x</tt> ein Wert, so verändert eine Manipulation von <tt>x</tt> nur das neue Objekt (das ursprüngliche bleibt erhalten). Ist <tt>x</tt> hingegen eine Referenz, wird immer das ürsprüngliche Objekt manipuliert (denn es gibt ja keine Kopie). Ob eine Variable einen Wert oder eine Referenz enthält, wird in jeder Programmiersprache anderes festgelegt. In Python gilt
* Zahlen (Typen <tt>bool</tt>, <tt>int</tt>, und <tt>float</tt>) werden immer als Werte gespeichert und kopiert.
* Alle anderen Typen werden als Referenzen gespeichert und kopiert.
* Für alle Typen kann Wertsemantik mit Hilfe des Python-Moduls [http://docs.python.org/lib/module-copy.html copy] erzwungen werden.
Das Verständnis von Werten und Referenzen wird in der 1. Übung vertieft.

Der Entwurf von Datentypen wird uns im Laufe der Vorlesung immer wieder beschäftigen.

[[Image:Dt dreieck.png]]

== Fundamentale Algorithmen ==

Einige Algorithmen werden praktisch bei jeder Klasse benötigt, unabhängig vom eigentlichem Verwendungszweck der Klasse. Es ist wichtig, diese fundamentalen Algorithmen zu kennen. Außerdem eignen sie sich gut zur Einführung der Grundprinzipien der Algorithmen-Spezifikation mittels Vor- und Nachbedingungen. Diese Bedingungen beschreiben Eigenschaften, die die Variablen des Systems ''vor'' bzw. ''nach'' der Ausführung des Algorithmus haben sollen. Damit man außerdem die Veränderungen durch den Algorithmus beschreiben kann, führt man zu jeder Variablen (z.B. <tt>x</tt>) eine Hilfsvariable (z.B. <tt>xo</tt>, sprich "x-old") ein. In den Hilfsvariablen wird der Zustand ''vor'' der Ausführung des Algorithmus gespeichert, so dass man diesen noch abfragen kann, wenn Variablen durch den Algorithmus verändert werden. Wenn der Algorithmus beispielsweise die Variable <tt>x</tt> inkrementiert (um eins erhöht), gilt die Nachbedingung <tt>x == xo + 1</tt> (darin ist <tt>x</tt> der neue, und <tt>xo</tt> der alte Wert der Variablen). Falls <tt>x</tt> hingegen nicht verändert wird, gilt <tt>x == xo</tt>. (Man beachte, dass dies in der Literatur nicht einheitlich gehandhabt wird -- einige Autoren verwenden z.B. <tt>x</tt> für den Zustand vor Ausführung des Algorithmus, und <tt>x'</tt> für denjenigen danach. Diese Syntax ist jedoch mit den meisten Programmiersprachen inkompatibel.)

Die wichtigste Gruppe von fundamentalen Funktionen sind die '''Konstruktoren''', die einen vorher unbenutzten Speicherbereich in eine Datenstruktur mit einem wohldefinierten Anfangswert transformieren. In Python haben die Konstruktoren im allgemeinen den gleichen Namen wie die dazugehörige Klasse, also z.B.
i = int() # erzeuge eine ganze Zahl mit Anfangswert 0
f = float() # erzeuge eine Gleitkommazahl mit Anfangswert 0
a = list() # erzeuge ein leeres Array
usw. (Man beachte, dass das Python-Array den Klassennamen <tt>list</tt> hat. Dies hat nichts mit verketteten Listen zu tun.) Konstruktoren ohne Argumente bezeichnet man als ''Standard-Konstruktoren'' (default constructors). Ja nach Typ gibt es meist noch weitere Konstruktoren, die Objekte mit anderen Anfangswerten erzeugen, z.B.
i = int(2) # erzeuge eine ganze Zahl mit Anfangswert 2
i = 2 # ebenso (abgekürzte Schreibweise)
f = float(1.5) # erzeuge eine Gleitkommazahl mit Anfangswert 1.5
f = 1.5 # ebenso (abgekürzte Schreibweise)
a = [i, f] # erzeuge ein Array mit Kopien der Werte von i und f
(Das Array <tt>a</tt> enthält Kopien der Werte, weil Zahlen immer mit Wertsemantik zugewiesen werden.) Die allgemeine Spezifikation eines Standard-Konstruktors lautet

<math>\begin{array}{ll}
\mathrm{Precondition: } & T \in \mathrm{Types}\\
\mathrm{Constructor: } & t = T() \\
\mathrm{Postcondition: } & t \in T
\end{array}</math>

Der Ausdruck <math>t \in T</math> besagt, dass t nach Ausführung des Konstruktors eine legale Instanz des Typs T (oder eine Referenz auf einen solche Instanz) sein muss. In Pythonsyntax kann dies folgendermassen geschrieben werden
import inspect # wir brauchen das inspect-Modul

if inspect.isclass(T): # prüfe, dass T ein Type ist
t = T()
assert isinstance(t, T)
Natürlich funktioniert der Code nur, wenn die Klasse <tt>T</tt> tatsächlich existiert und dafür ein Standardkonstruktor definiert wurde. Das Gegenstück zu Konstruktoren sind die '''Destruktoren''', die den Speicher der Datenstruktur wieder frei geben. Da Python automatisches Speichermanagment unterstützt, werden die Destruktoren automatisch aufgerufen. Wir können sie deshalb hier übergehen.

Sehr wichtig sind auch die '''Vergleichsoperatoren'''. Wir müssen dabei unterscheiden, ob auf Gleichheit der Referenzen (''identity'') oder auf Gleichkeit der Werte (''equality'') geprüft werden soll. In Python werden dazu die Operatoren <tt>is</tt> bzw. <tt>==</tt> verwendet. Die Negation erhält man durch <tt>is not</tt> bzw.
<tt>!=</tt>
a = [1, 2]
b = [1, 2]

a == b # True weil gleiche Werte
a != b # False weil Negation
a is b # False weil unterschiedliche Identität
a is not b # True weil Negation

(Beachte: beim Vergleich von Zahlen des gleichen Typs liefern <tt>is</tt> und <tt>==</tt> immer dasselbe Ergebnis.) Natürlich impliziert die Gleichheit der Schlüssel (Identität der Objekte) die Gleichheit der Werte.

Ebenso wichtig sind die '''Zuweisungen'''. Hier zeigt sich besonders der Unterschied zwischen Wert- und Referenzsemantik. Im Falle von Wertsemantik gilt

<math>\begin{array}{ll}
\mathrm{Preconditions: } & s,t \in T \\
& s \mathrm{\ is\ not\ } t \\
\mathrm{Assign\ by\ value: } & s = t \\
\mathrm{Postconditions: } & t \mathrm{\ is\ } t_o \\
& s \mathrm{\ is\ not\ } t \\
& s == t
\end{array}</math>

Das heisst, t darf sich nicht verändern, und s hat nach der Zuweisung den gleichen Wert wie t. Bei Referenzsemantik gilt sogar

<math>\begin{array}{ll}
\mathrm{Precondition: } & t \in T \\
\mathrm{Assign\ by\ reference: } & s = t \\
\mathrm{Postconditions: } & t \mathrm{\ is\ } t_o \\
& s \mathrm{\ is\ } t
\end{array}</math>

Dies entspricht dem Pythoncode
x = y
assert x is y
Die Wertsemantik muss man in Python explizit erzwingen
import copy # wir brauchen das copy-Modul

x = copy.deepcopy(y)
assert x == y
assert x is not y

Mit der Zuweisung eng verwandt ist die Funktion <tt>swap</tt>, die den Inhalt von zwei Variablen vertauscht:

<math>\begin{array}{ll}
\mathrm{Precondition: } & t \in T, s \in S \\
\mathrm{Algorithm\ swap: } & \mathrm{swap}(s, t) \\
\mathrm{Postconditions: } & t \mathrm{\ is\ } s_o \\
& s \mathrm{\ is\ } t_o
\end{array}</math>

Diese Funktion wird sich beim Sortieren als sehr nützlich erweisen, weil dort das Vertauschen von zwei Datenelementen eine Grundoperation ist. In Python kann man dies so implementieren:
t, s = s, t # swap
Dabei macht man sich zunutze, dass Python mehrere Variablen in einem einzigen Statement zuweisen kann.

File:Dt dreieck.png

2008-04-23T17:39:10Z

Alter: