Post on 18-Sep-2018
transcript
1. April 2010 | Referent | Kurztitel der Präsentation (bitte im Master einfügen) | Seite 1
Platzhalter für Bild, Bild auf Titelfolie hinter das Logo einsetzen
Vorkurs Informatik SoSe 14 – Algorithmen 102.04. - 10.04.2014
Dr. Werner Struckmann / Markus Reschke
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 2
Ziel des Vorkurses Informatik – Algorithmen
● Grundlegende Einführung in algorithmisches Denken Was ist ein Algorithmus? Was sind Berechnungsschritte? In welcher Reihenfolge sollen sie ausgeführt werden? Eingaben, Ausgaben, Zwischenergebnisse…
● anhand von Beispielen: Sortierverfahren, Graphenalgorithmen.
Zielgruppe
Studierende, die wenige informatische Vorerfahrungen haben. Insbesondere, wenn Sie
keinen Grund- oder Leistungskurs Informatik belegt haben, keine Programmiererfahrung haben.
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 3
Handlungsvorschriften
● Viele Dinge im Leben werden nach einem festgelegtem Schema durchgeführt. Diese Schemata regeln, welche Schritte mit welchen Objekten in welcher Reihenfolge (beispielsweise nacheinander, wiederholt oder bedingt) gemacht werden.
● Beispiel: Wie heben Sie Geld am Geldautomaten ab?
● Von der Handlungsvorschrift zum Algorithmus...
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 4
Rezept für Vanillekipferl
● 200g Mehl● 250g Butter● 180g Zucker● 200g fein gemahlene Mandeln ● 1 Päckchen Vanillezucker● Zubereitung: ● Aus den Zutaten einen Teig kneten. Eine etwa walnussgroße Menge Teig in der
Hand rollen und ein Hörnchen formen. Diese nicht zu dicht auf ein mit Backpapier ausgelegtes Blech legen und im vorgeheizten Backofen bei schwacher Hitze (ca. 150°C) für ca. 10-15 Minuten goldbraun backen.
● Solange sie noch warm sind mit einem Gemisch aus 1 Tasse Puderzucker und 1 Päckchen Vanillezucker bestäuben.
● Abkühlen lassen und in einer gut verschließbaren Dose aufbewahren.
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 5
Ausführungsvorschrift Vanillekipferl
● Implizit können wir dem Rezept folgende Handlungsvorschrift entnehmen:
Nimm eine Schüssel Fülle 200g Mehl hinein Fülle 250g Butter hinein Fülle 180g Zucker hinein Fülle 200g fein gemahlene Mandeln hinein Fülle 1 Päckchen Vanillezucker hinein Knete den Inhalt der Schüssel, bis ein glatter Teig entsteht
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 6
Ausführungsvorschrift Vanillekipferl
● Fortsetzung:
Forme aus walnussgroßen Stückchen Teig kleine Hörnchen und lege sie auf ein mit Papier ausgelegtes Blech
Schalte den Backofen auf 160°C Warte 10 Minuten Schiebe Blech in den Backofen Stelle eine Mischung aus einer Tasse Puderzucker und einer Packung
Vanillezucker her Warte 10-15 Minuten bis Vanillekipferl goldbraun Nimm Blech aus dem Backofen heraus Bestäube die warmen Kipferl mit Mischung aus Puder- und Vanillezucker
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 7
Intuitives Algorithmusverständnis
● Gegeben sei ein „Problem“ oder eine „Problemklasse“.
● Ein Algorithmus ist eine Handlungsvorschrift zum „Lösen“ des Problems, wobei
die Handlungsvorschrift erkennbar einen Anfang und ein Ende hat *
und aus einzelnen Schritten besteht, für die jeweils klar ist, was mit welchen Dingen zu tun ist
und die Reihenfolge der Schritte festlegt.
● Ein Problem, für dessen Lösung ein Algorithmus existiert, heißt berechenbar.
● * Die Beschreibung ist ein endlicher Text, die Ausführung der Handlungsvorschrift dagegen muss nicht enden.
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 8
Vanillekipferl als Algorithmus Nimm eine Schüssel Fülle 200g Mehl hinein Fülle 250g Butter hinein Fülle 180g Zucker hinein Fülle 200g fein gemahlene Mandeln hinein Fülle 1 Päckchen Vanillezucker hinein Knete den Inhalt der Schüssel, bis ein glatter Teig entsteht Forme aus walnussgroßen Stückchen Teig kleine Hörnchen und lege sie auf
ein mit Papier ausgelegtes Blech Schalte den Backofen auf 160°C Warte 10 Minuten Schiebe Blech in den Backofen Stelle eine Mischung aus einer Tasse Puderzucker und einer Packung
Vanillezucker her Warte 10-15 Minuten bis Vanillekipferl goldbraun Nimm Blech aus dem Backofen heraus Bestäube die warmen Kipferl mit Mischung aus Puder- und Vanillezucker
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 9
Ein Algorithmus?
● “Engagement, Teamgeist und das permanente Streben nach Perfektion sind wichtige Bausteine unseres Erfolgs. Und unserer Philosophie. Mit technologischer Kompetenz und Innovationskraft bringt XX bewegende Ideen auf die Straße. Der schnellste Sportwagen der Welt, das größte und stärkste Diesel-Aggregat, das je in einen PKW eingebaut wurde oder das sparsamste Automobil aller Zeiten sind nur einige Beispiele, wie XX mit technischen Revolutionen neue Maßstäbe setzt.”
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 10
Beispiele für Algorithmen
Koch- und Backrezepte Bedienungsanleitungen (z.B. für Handys) Notenfolgen zum Musizieren Waschmaschinenprogramme Sortierverfahren Abfolge in Produktionsstraßen Berechnungsverfahren:
ggT bestimmen Funktionen ableiten
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 11
Der Algorithmus - Präzisierung
● Ein Algorithmus ist eine wohldefinierte Rechenvorschrift, die eine (eventuell leere) Menge von Eingaben verwendet und eine Menge von Ausgaben erzeugt.
● Ein Algorithmus ist also eine Abfolge von Berechnungsschritten, die die Eingabe in die Ausgabe umwandelt.
Der Algorithmus muss durch einen endlichen Text in einer wohldefinierten Sprache beschrieben sein.
Die Objekte der Berechnung müssen klar sein. Die elementaren Operationen müssen mechanisch ausführbar sein. Die Reihenfolge der Operationen muss feststehen.
Der Algorithmusbegriff
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 12
Darstellung von Algorithmen
Man kann einen Algorithmus beispielsweise als Text Pseudocode oder in einer Programmiersprache als Flussdiagramm (Programmablaufplan) Struktogramm (Nassi-Shneiderman-Diagramm) …
● darstellen.
Im Rahmen dieses Vorkurses werden wir Struktogramme nach Nassi-Shneiderman verwenden, wie sie auch in DIN 66261 festgelegt sind.
● Ein aus verschiedenen Strukturblöcken zusammengesetzte Struktogramm ist im Ganzen rechteckig, d.h. genauso breit wie sein breitester Strukturblock.
Darstellung von Algorithmen
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 13
Sinnbilder:
Sinnbilder für Programmablaufplan nach DIN66001-1966
Sinnbild Bennenung und Bemerkung
Operation, allgemein (process)
Verzweigung (decision)
Unterprogramm (prefdefined process)
Ein- und Ausgabe (input/output)
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 14
Sinnbilder:
Sinnbilder für Programmablaufplan nach DIN66001-1966
Sinnbild Bennenung und Bemerkung
Schleifenbegrenzung (loop limit)Anfang
Schleifenbegrenzung (loop limit)Ende
Ablauflinie (flow line)Vorzugsrichtungen (Pfeil optional):a) von oben nach untenb) von links nach rechts
Zusammenführen (junction)Ausgang sollte durch einen Pfeil gekennzeichnet werden
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 15
Beispiel für Programmablaufplan nach DIN66001-1966
Begin
Ende
Dreckwäsche in die
Waschmaschine
Waschmittelin die
Waschmaschine
Wäschezusammenlegen
Wäschein den
Trockner
Waschmaschineanstellen
Warten
Trockneranstellen
Warten
Wäschein den Schrank
räumen
Fertig? Fertig?
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 16
Jede Anweisung wird in einen rechteckigen Strukturblock geschrieben.
Strukturblöcke können untereinander gestellt werden.
Die Strukturblöcke werden nacheinander von oben nachunten durchlaufen.
Linearer Ablauf (Sequenz):
Anweisung 1
Anweisung 2
Anweisung 3
Anweisung 4
Struktogramme
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 17
Vanillekipferl als Struktogramm
Nimm eine Schüssel
Fülle 200g Mehl hinein
Fülle 250g Butter hinein
Fülle 200g fein gemahlene Mandeln hinein
Fülle 1 Päckchen Vanillezucker hinein
Fülle 180g Zucker hinein
Knete den Inhalt der Schüssel, bis ein glatter Teig entsteht
Forme aus walnussgroßen Stückchen Teig kleine Hörnchen und lege sie auf ein mit Papier ausgelegtes Backblech
Schalte Backofen auf 150°C
Warte 10 Minuten
Schiebe Blech in den Backofen
Stelle eine Mischung aus einer Tasse Puderzucker und einer Packung Vanillezucker her
Nimm Blech aus Backofen heraus
Bestäube die noch warmen Kipferl mit Mischung aus Puder- und Vanillezucker
Struktogramme
Warte 10-15 Minuten
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 18
Wenn die Bedingung zutreffend (wahr) ist, wird der Anweisungsblock 1 durchlaufen. Trifft die Bedingung nicht zu (falsch), wird der Anweisungsblock 2 durchlaufen. Ein Anweisungsblock kann aus einer oder mehreren Anweisungen bestehen. Austritt erfolgt nach unten nach Abarbeitung des jeweiligen Anweisungsblocks.
Anweisungsblock 2
Bedingung
Anweisungsblock 1
Wahr Falsch
Struktogramme
Zweifache Auswahl (alternative Verarbeitung)
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 19
Zweifache Auswahl (alternative Verarbeitung)
Füge einen Eßlöffel Mehl hinzu
Fülle ein Päckchen Vanillezucker hinzu
...
Ist der Teig fest?
Fortfahren
Ja Nein
Knete den Inhalt der Schüssel, bis ein glatter Teig entsteht
Struktogramme
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 20
Fortfahren
...
Wird Mehl für das Rezept benötigt?
Fortfahren
Ja Nein
Ist Mehl vorrätig
Ja Nein
Setze Mehl auf Einkaufsliste
...
Struktogramme
Verschachtelte zweifache Auswahl
18.03.2013 | Konzepte der Informatik | Seite 21
Fallauswahl
● Besonders bei mehr als drei abzuprüfenden Bedingungen geeignet. Der Wert von "Variable" kann bedingt auf Gleichheit wie auch auf Bereiche (größer/kleiner bei Zahlen) geprüft werden und der entsprechend zutreffende "Fall" mit dem zugehörigen Anweisungsblock wird durchlaufen.
Struktogramme
Variable
Wert(ebereich) 1 Wert(ebereich) 2 Wert(ebereich) nsonst
Anweisungs-
block 2
Anweisungs-
block n
Alternativblock
(optional)
Anweisungs-
block 1
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 22
Abweisende (vorprüfende – kopfgesteuerte) Schleife
● Wiederholungsstruktur mit vorausgehender Bedingungsprüfung:● Zuerst wird die Bedingung ausgewertet: Ergibt sie wahr, wird der Schleifenkörper
(Anweisungsblock) einmal ausgeführt. Danach wird zum Beginn der Schleife zurückgekehrt und erneut mit der Prüfung der Bedingung begonnen.
● Ergibt die Auswertung der Bedingung falsch, wird unterhalb des Schleifenkörpers fortgefahren (ohne ihn auszuführen).
● Häufig benutzt man eine Bedingung, deren Wahrheitswert sich im Laufe der Zeit verändert, z.B. indem Variablen im Schleifenkörper verändert werden, die in der Bedingung vorkommen. Man führt also die Anweisungen im Schleifenkörper solange aus, bis die Bedingung nicht mehr zutrifft.
Struktogramme
...
Anweisungsblock
Bedingung
...
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 23
Nimm das Blech aus dem Ofen
Schiebe das Blech in den Backofen
...
Kontrolliere jede Minute
Solange Kipferl im Backofen noch nicht goldbraun
...
Struktogramme
Abweisende Schleife - Beispiel
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 24
Durchführung
● Probieren Sie diesen Algorithmus doch zu Hause einmal aus.
● Wir würden uns im Laufe des Vorkurses über einen Nachweis der erfolgreichen Durchführung freuen!
Struktogramme
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 25
Einführung
● Sortieren als eines der Standardprobleme der Informatik Verschiedenste Algorithmen
Unterschiedliche Laufzeiten Schlecht im Extremfall, gut im Mittel
● Wichtige Unterschiede zum menschlichen Sortieren Um sich einen Überblick über mehrer Elemente zu verschaffen, müssen sie
einzeln angesehen und Zwischenergebnisse gebildet werden. Jedes "sich Merken" oder "Ablegen" muss in eigens angelegten
Speicherstellen stattfinden. Unterschiedliche Arten des Zugriffs auf das n-te Element.
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 26
Algorithmus zur Feststellung der kleinsten Zahl in einer Liste
Eingabe: Eine Liste von Zahlen
(dargestellt durch einen verdeckt liegenden Stapel mit Zahlenkarten)
Ausgabe: Die kleinste in der Liste vorkommende Zahl
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 27
Struktogramm für die Feststellung der kleinsten Zahl in einem Stapel
Sortieren
Für jede weitere Karte aus dem Stapel
Schreibe die Zahl auf der ersten Karte des Stapels auf die Leerkarte (Sie ist ja in jedem Fall erstmal die kleinste, da wir nur die eine Karte kennen)
Zahl der Karte < der bisher kleinsten Zahl?
Ja Nein
Schreibe die Zahl als bisher kleinste gefundene Karte auf die Leerkarte
Fahre fort
Lege eine Leerkarte zum Merken der kleinsten bisher gefundenen Zahl (lokale Variable)
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 28
Algorithmus?
● Ist das beschriebene Verfahren ein Algorithmus?
Das Verfahren ist in einer endlichen Beschreibung durch ein Struktogramm beschrieben.
Die Objekte der Berechnung sind die Zahlen des Stapels.
Die elementaren Operationen sind das Vergleichen von zwei Zahlen und das Ablegen des Wertes in einer lokalen Variable. Diese sind mechanisch ausführbar.
Die Reihenfolge der Operationen ist ebenfalls durch das Struktogramm festgelegt.
Das Verfahren ist ein Algorithmus.
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 29
Suche der kleinsten Zahl - Liste
● Zahlen nicht mehr als Stapel, sondern als Liste● Zahlen liegen aufgedeckt auf dem Tisch● Zahlen haben eine Position in der Liste, beginnend bei 1● Wir können vorne oder hinten etwas an die Liste anhängen● Wir können Zahlen auch aus der Liste rausnehmen
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 30
Struktogramm für die Feststellung der kleinsten Zahl und deren Position in einer Liste
Sortieren
Für jedes Element aus der Liste
Setze die momentan kleinsten Zahl auf das erste Element der Liste
Listenelement < der momentan kleinsten Zahl?
Ja Nein
Setze die momentan kleinste Zahl auf das Listenelement
Fahre fort
Setze Position der momentan kleinsten Zahl auf 1
Setze die Position der momentan kleinsten Zahl auf die Position der momentan betrachteten Zahl
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 31
Selection-Sort
● Sortieren mit der Suche des Minimums einer Liste● Grobe Idee:
● Wir legen eine neue Liste an
● Das Minimum und dessen Positon wird in der zu sortierenden Liste gesucht
● Das Minimum wird an die neue Liste angehängt
● Das Element an der Stelle des Minimums wird gelöscht
● Wir sind fertig, wenn die zu sortierende Liste leer ist
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 32
Selection-Sort
● Eine zusätzliche neue Liste ist nicht nötig● Idee:
Man benutzt eine Hilfsvariable, die die Position angibt, ab der die Liste bereits sortiert ist. Diese Position teilt die Liste in einen linken, sortierten Teil (Positionen kleiner der Hilfsvariable) und einen rechten, unsortierten Teil (Positionen größer gleich der Liste)
Zu Beginn zeigt die Hilfsvariable auf das erste Element, die komplette Liste ist also unsortiert (Positionen größer gleich der Hilfsvariable).
Solange der Zeiger nicht auf dem letzten Element steht, tue folgendes: Suche im unsortierten Teil des Feldes das kleinste Element Vertausche dieses Element mit dem Element dessen Position der
Hilfsvariable entspricht Versetze die Hilfsvariable um eine Position nach rechts (erhöhe sie um
eins)
Sortieren
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 33
Selection-Sort
● Ausgangsituation:
Sortieren
5 2 9 3 1
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 34
Selection-Sort
● Zum Ende der 1. Iteration:
Sortieren
5 2 9 3 1
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 35
Selection-Sort
● Zu Beginn der 2. Iteration:
Sortieren
2 9 3 51P
ositi
on
des
ers
ten
u
nso
rtie
rte
n W
ert
es
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 36
Selection-Sort
● Während der 2. Iteration:
Sortieren
392 51P
ositi
on
des
ers
ten
u
nso
rtie
rte
n W
ert
es
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 37
Selection-Sort
● Zu Beginn der 3. Iteration:
Sortieren
2 9 3 51
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 38
Selection-Sort
● Während der 3. Iteration:
Sortieren
2 9 3 51
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 39
Selection-Sort
● Zu Beginn der 4. Iteration:
Sortieren
2 3 9 51
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 40
Selection-Sort
● Während der 4. Iteration:
Sortieren
2 3 9 51
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 41
Selection-Sort
● Am Ende der 4. Iteration:
● Das Abbruchkriterium (Hilfsvariable auf dem letzten Element der Liste) ist erfüllt und die Liste damit sortiert.
Sortieren
2 3 5 91
Pos
itio
n d
es e
rste
n
un
sort
iert
en
We
rte
s
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 42
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position ab der noch sortiert werden muss
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 43
Selection-Sort – Austauschoperation
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 44
Selection-Sort – Austauschoperation
Sortieren
5 2 9 3
1 Leerkarte (1), Position des ersten unsortierten Wertes
Leerkarte (2), Zwischenspeicher für Austauschoperation
Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
1
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 45
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 46
Selection-Sort – Austauschoperation
Sortieren
5 2 9 3
1 Leerkarte (1), Position des ersten unsortierten Wertes
Leerkarte (2), Zwischenspeicher für Austauschoperation
5 Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
1
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 47
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 48
Selection-Sort – Austauschoperation
Sortieren
5 2 9 3
1 Leerkarte (1), Position des ersten unsortierten Wertes
5 Leerkarte (2), Zwischenspeicher für Austauschoperation
5 Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
1
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 49
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 50
Selection-Sort – Austauschoperation
Sortieren
1 2 9 3
1 Leerkarte (1), Position des ersten unsortierten Wertes
5 Leerkarte (2), Zwischenspeicher für Austauschoperation
5 Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
1
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 51
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 52
Selection-Sort – Austauschoperation
Sortieren
1 2 9 3
1 Leerkarte (1), Position des ersten unsortierten Wertes
5 Leerkarte (2), Zwischenspeicher für Austauschoperation
5 Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
5
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 53
Selection-Sort – Struktogramm
Lege eine Leerkarte (2) als Zwischenspeicher für die Austauschoperation
Lege eine Leerkarte (1) zum Merken der Position bis vor die sortiert ist
Schreibe die 1 auf Leerkarte (1) (das gesamte Feld ist unsortiert)
Sortieren
Solange der Leerkarte (1) nicht der Position des letzten Elements der Liste entspricht
Suche im unsortierten Teil des Feldes (rechts des Zeigers) das kleinste Element und speichere die Position auf Leerkarte (3)
Erhöhe den Wert auf Leerkarte (1) um eins
Sichere den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) im Zwischenspeicher für die Austauschoperation (Leerkarte 2)
Überschreibe den Wert der ersten noch nicht sortierten Karte (Position auf Leerkarte (1)) mit dem gefundenen kleinsten Wert (Position auf Leerkarte (3))
Lege eine Leerkarte (3) als Zwischenspeicher für die Position des kleinsten Elements
Überschreibe die ursprüngliche Position des kleinsten Wertes (Position auf Leerkarte (3)) mit dem Wert im Zwischenspeicher für die Austauschoperation
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 54
Selection-Sort – Austauschoperation
Sortieren
1 2 9 3
2 Leerkarte (1), Position des ersten unsortierten Wertes
5 Leerkarte (2), Zwischenspeicher für Austauschoperation
5 Leerkarte (3), Zwischenspeicher für die Position des kleinsten Elements
5
02.04.2014 | Vorkurs Informatik – Algorithmen 1 | Seite 55
Selection-Sort
● Ist das beschriebene Verfahren ein Algorithmus?
Das Verfahren ist in einer endlichen Beschreibung durch ein Struktogramm gegeben.
Die Objekte der Berechnung sind die Zahlen der Liste. Die Operationen sind:
Finden der kleinsten Zahl einer Menge: Dies sind mechanisch ausführbar und nicht elementar, aber durch ein Struktogramm näher beschrieben und in elementare Schritte unterteilt.
Schreiben und Lesen von Karten. Dieses ist mechanisch ausführbar und elementar.
Die Reihenfolge der Operationen ist ebenfalls durch das Struktogramm festgelegt.
Das Verfahren ist ein Algorithmus.
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 56
Bubble Sort
● In einer Wassersäule sind verschieden große Luftblasen. Die unterste Luftblase steigt nun langsam auf. Während sie an kleineren problemlos vorbeikommt, wird sie durch größere gestoppt. Durch den Zusammenprall setzt sich die größere Luftblase in Bewegung, bis auch diese gestoppt wird oder am oberen Säulenende ankommt. Nun setzt sich abermals die unterste Luftblase in Bewegung. Wenn die Wassersäule eine endliche Anzahl Luftblasen enthält, dann kann irgendwann keine Luftblase mehr aufsteigen, da sich über jeder Luftblase eine größere Luftblase befindet.
● Die Luftblasen sind nun von unten (klein) nach oben (groß) sortiert.
● Wir werden diese Idee auf eine Liste von Zahlen übertragen. Der Wert der Zahl repräsentiert die Größe der Luftblase. Der Anfang der Liste ist das untere Ende der Wassersäule, das Ende der Liste ist das obere Ende der Wassersäule.
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 57
Bubble Sort
5 3 9 2 1● 1. Iteration
● Die Liste wird von vorne beginnend durchlaufen und die ersten beiden Elemente werden miteinander verglichen. Ist das erste Element größer als das zweite Element, dann folgt ein Vertauschen, denn die größeren Luftblasen können an den kleineren vorbei.
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 58
Bubble Sort
● 1. Iteration
● Die kleineren Luftblasen stoßen die größeren Luftblasen an und stoppen selbst dabei. Es findet hier also kein Vertausch der Zahlen „5“ und „9“ statt. Nun wird die „9“ weiter aufsteigen.
53 9 2 1
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 59
Bubble Sort
● 1. Iteration
● Der nächste Vergleich führt wieder zu einem Vertauschen, da die Luftblase mit der Größe 9 an der kleineren Luftblase mit der Größe 2 vorbeikommt und weiter aufsteigen kann.
53 2 9 1
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 60
Bubble Sort
● 1. Iteration
● Der letzte Vergleich führt wieder zu einem Vertauschen. Die Luftblase mit der Größe 9 ist als größte Luftblase an die Oberfläche der Wassersäule gestiegen. Wir fahren mit der nächsten Iteration fort.
53 2 1 9
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 61
Bubble Sort
● 2. Iteration
● Die Luftblase mit der Größe 3 stößt die größere Luftblase an und bleibt selbst dabei stehen. Die größere Luftblase steigt weiter auf, es findet kein Vertauschen statt.
53 2 1 9
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 62
Bubble Sort
● 2. Iteration
● Am Ende der zweiten Iteration bleibt die Luftblase der Größe 5 an der Luftblase mit der Größe 9 hängen.
23 1 5 9
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 63
Bubble Sort
● 3. Iteration
● Nach der dritten Iteration sind die größten drei Elemente aufsteigend sortiert.
12 3 5 9
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 64
Bubble Sort
● 4. Iteration
● Die vierte Iteration sortiert die letzten beiden Elemente. Danach ist die Liste aufsteigend sortiert.
21 3 5 9
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 65
Bubble Sort
● Hinweis: a sei die Anzahl der zu sortierenden Zahlen
Solange j <= a - 1
j-te Zahl > j+1te Zahl?
Tausche Zahl j mit Zahl j+1
Fahre fort
Solange i <= a - 1
Ja Nein
Sortieren
Setze i auf 1
Reserviere eine Hilfsvariable i für die äußere Schleife
Reserviere eine Hilfsvariable j für die innere Schleife
Setze j auf 1
Erhöhe j um eins
Erhöhe i um eins
18.03.2013 | Konzepte der Informatik | Seite 66
Bubble Sort
● Ist das beschriebene Verfahren ein Algorithmus?
Das Verfahren ist in einem endlichen Text durch ein Struktogramm beschrieben.
Die Objekte der Berechnung sind die Zahlen der Liste.
Die Operationen sind das Vergleichen und Vertauschen zweier Zahlen. Diese sind mechanisch ausführbar.
Die Reihenfolge der Operationen ist ebenfalls durch das Struktogramm festgelegt.
Das Verfahren ist ein Algorithmus.
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 67
Aufwandsabschätzung
● Um den zu leistenden Aufwand für die Durchführung eines Algorithmus' zu bestimmen, muss man sich zuerst die Problemgröße bewusst machen. Sie stellt ein Maß dar, wie schwierig bzw. umfangreich die Aufgabe bzw. das Problem ist.
● Üblicherweise wird die Problemgröße mit n benannt.
● Für Sortieralgorithmen ist die Problemgröße die Anzahl der zu sortierenden Elemente.
Sortieren
18.03.2013 | Konzepte der Informatik | Seite 68
Aufwandsabschätzung
● Für einfache Sortierverfahren ist der Aufwand meist quadratisch zur Problemgröße.
● Zu beachten ist hierbei, dass diese Abschätzung nicht allzu genau genommen werden darf, da konstante Faktoren nicht beachtet werden.
● Wenn wir also von quadratischem Aufwand sprechen, so kann es genauso gut 100*n² sein, als auch 0,5*n² oder auch (n - 1)².
● Es geht aber auch besser...
Sortieren