FHNW: algd1
Algorithmen und Datenstrukturen 1 @ FHNW (FS 16)
Algorithmen und Datenstrukturen 1 @ FHNW (FS 16)
Invariante
Eine Invariante ist eine Aussage, die über die Ausführung bestimmter Programmbefehle hinweg gilt. Sie ist also vor und nach diesen Befehlen wahr, sie ist demnach nicht veränderlich, also invariant. Invarianten können zum Beweis der Korrektheit von Algorithmen verwendet werden.
Schleifeninvariante
Eine Schleifeninvariante ist eine Sonderform der Invariante, die vor, während und nach der Ausführung einer Schleife in einem Algorithmus gültig ist. Sie ist damit unabhängig von der Zahl ihrer derzeitigen Durchläufe. Eine Schleifeninvariante wird zur formalen Verifizierung von Algorithmen benötigt und hilft zudem, die Vorgänge innerhalb einer Schleife besser zu erfassen.
Korrektheit eines Algorithmus
Ein Algorithmus heisst korrekt, wenn er seiner Spezifikation genügt:
- Wenn er zu allen Inputs, die Vorbedingungen genügen, die Outputs erzeugt, welche die Nachbedingung erfüllen.
Spezifikation eines Algorithmus
Umfasst die Vorbedingungen und Nachbedingungen eines Algorithmus / Funktion. Ohne eine Spezifikation kann keine Aussage über die Korrektheit gemacht werden.
Beispiel:
\(f : N \longrightarrow N \\ \forall x \in [0,10] : f(x) = x!\)
Wie ist ein Selection Sort aufgebaut?
int last = array.length-1;
for (int first = first < last; first++) {
int j = first;
int min = array[ j ];
for (int x = first + 1; x <= last; x++) {
if (array[ x ] < min ) {
j = x;
min = array[ x ];
}
}
array[ j ] = array[ first ];
array[ first ] = min;
}
Wie funktioniert der Selection-Sort Algorithmus? (Sprachlich erklären)
Prinizipiell hat das Array einen sortierten und einen unsortierten Teil. Der sortierte Teil muss um 1 grösser werden und der unsortierter Bereich wird eins kleiner.
Die Idee:
- Im unsortierten Bereich das kleinste Element suchen.
- Das 1. Element aus dem unsortierten Bereich durch das gefundene Element austauschen (swapping)
- Solange iterieren bis das Array sortiert ist.
Wikipedia: https://en.wikipedia.org/wiki/Selection_sort
Wie lautet die Komplexität des Selection Sorts?
Wir gehen vom Worst-Case Szenario aus. Das kleinste Element liegt jeweils am Ende.
- 1. Iteration: n-1
- 2. Iteration: n-2
... - n-1 Iteration: 1
Diese Reihe lässt sich auf folgende Formel umwandeln:
\(\sum _{{k=1}}^{n-1}k=(n-1)+(n-2)+\dotsb +1={\frac {n(n-1)}{2} \approx {\frac {n^2}{2}}} \)
Die Asymptotische Komplexität: \(O(n^2)\)
-
- 1 / 7
-
Cartes-fiches
Invariante
Eine Invariante ist eine Aussage, die über die Ausführung bestimmter Programmbefehle hinweg gilt. Sie ist also vor und nach diesen Befehlen wahr, sie ist demnach nicht veränderlich, also invariant. Invarianten können zum Beweis der Korrektheit von Algorithmen verwendet werden.
Schleifeninvariante
Eine Schleifeninvariante ist eine Sonderform der Invariante, die vor, während und nach der Ausführung einer Schleife in einem Algorithmus gültig ist. Sie ist damit unabhängig von der Zahl ihrer derzeitigen Durchläufe. Eine Schleifeninvariante wird zur formalen Verifizierung von Algorithmen benötigt und hilft zudem, die Vorgänge innerhalb einer Schleife besser zu erfassen.
Korrektheit eines Algorithmus
Ein Algorithmus heisst korrekt, wenn er seiner Spezifikation genügt:
- Wenn er zu allen Inputs, die Vorbedingungen genügen, die Outputs erzeugt, welche die Nachbedingung erfüllen.
Spezifikation eines Algorithmus
Umfasst die Vorbedingungen und Nachbedingungen eines Algorithmus / Funktion. Ohne eine Spezifikation kann keine Aussage über die Korrektheit gemacht werden.
Beispiel:
\(f : N \longrightarrow N \\ \forall x \in [0,10] : f(x) = x!\)
Wie ist ein Selection Sort aufgebaut?
int last = array.length-1;
for (int first = first < last; first++) {
int j = first;
int min = array[ j ];
for (int x = first + 1; x <= last; x++) {
if (array[ x ] < min ) {
j = x;
min = array[ x ];
}
}
array[ j ] = array[ first ];
array[ first ] = min;
}
Wie funktioniert der Selection-Sort Algorithmus? (Sprachlich erklären)
Prinizipiell hat das Array einen sortierten und einen unsortierten Teil. Der sortierte Teil muss um 1 grösser werden und der unsortierter Bereich wird eins kleiner.
Die Idee:
- Im unsortierten Bereich das kleinste Element suchen.
- Das 1. Element aus dem unsortierten Bereich durch das gefundene Element austauschen (swapping)
- Solange iterieren bis das Array sortiert ist.
Wikipedia: https://en.wikipedia.org/wiki/Selection_sort
Wie lautet die Komplexität des Selection Sorts?
Wir gehen vom Worst-Case Szenario aus. Das kleinste Element liegt jeweils am Ende.
- 1. Iteration: n-1
- 2. Iteration: n-2
... - n-1 Iteration: 1
Diese Reihe lässt sich auf folgende Formel umwandeln:
\(\sum _{{k=1}}^{n-1}k=(n-1)+(n-2)+\dotsb +1={\frac {n(n-1)}{2} \approx {\frac {n^2}{2}}} \)
Die Asymptotische Komplexität: \(O(n^2)\)
