Sommer Sitzung 03

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 3

Thema	Stichworte	Material
Überblick	Nach grundlegenden Datenstrukturen (welche? – LinkedList, Stack, Queue, ArrayList) heute grundlegende Algorithmen: Sortieren und Suchen. Warum Sortieren und Suchen? – Datenaufbereitung und Datenzugriff, so durch Interpration und Kontextualisierung aus Daten Information machen, d.h. diese Probleme bilden Grundlage und Fundament der Informationsverarbeitung	Beispiele und Literatur: Home
Sortieren	Wie Sachen sortieren? – Viele Arten, heute Einstieg	91,23,88,93,20,37
1. Insertion sort: Implementierung	Wie lernt man sortieren, einfache Art bei Karten? – z.B. iterativer Ablauf: immer 1.) eine nehmen, 2.) einsortieren; wie implementieren? – s. Code; Datenstrukturen: hier nicht in-Place, welche Liste für unsortierte, welche für sortierte? – Lesen: ArrayList oder Stack; Einfügen: LinkedList	s. Code; Tafel: sortierte Liste
2. Insertion sort: Schleifeninvarianten	Korrektheit: Schleifeninvarianten (Sachen, die immer stimmen: am Anfang, während der Schleife, nach Durchlauf), hier? – n Sortierte Elemente korrespondieren mit n Elementen in Liste vor aktuellem Element, d.h. in einfach: die Ergebnisliste/-hand ist immer sortiert	s. Code; 3 Teile der Invariante: init, maintain, terminate
3. Insertion sort: Laufzeitanalyse	Laufzeit abhängig von? – Input n und Vorsortierung, wann und wie best case? – n, weil für Abheben und Einfügen jeweils n Elemente, dann konstanter Zugriff (Lesen in ArrayList, Einfügen akt. Stelle in LinkedList); wann und wie worst case? – n², wenn sortierte Liste komplett durchlaufen wird um Einfügestelle zu finden, d.h. Insertion sort hat O(n²): quadratisch	s. Code; erste Kurve: O(n²); Ende: 20,23,37,88,91,93
Suchen	Wir haben eine erste Ordnungsebene in unsere Daten gebracht – quasi vorbereitet für weiteres Verarbeitung	—
1. Lineare Suche	Vorgehen, Laufzeit? – O(n)	s. Code; zweite Kurve: O(n)
2. Binäre Suche: konzeptuell	Wie verbessern? – CD-Regal, Bibliothek, Mayersche? – Ausnutzen: bereits sortiert; Grundidee: in die Mitte gehen, entweder Treffer oder links von der Mitte neue Mitte suchen oder rechts von der Mitte neue Mitte suchen; Strategie: Teile-und-Herrsche (woher? – Römisches Reich); drei Schritte: divide, conquer, combine; rekursive Natur: mach mit den Teilen das Gleiche wie mit dem Ganzen; Abbruchbedingung: abgesucht, Rekurrenzrelation: weitersuchen; bisherige Algorithmen: iterativ; Binäre Suche auch iterativ möglich	Tafel: Intervalle, immer halbieren, auf gesuchten Wert einschränken (z.B. Suche nach 88): left0 – right0; left1 – right1; left2 – right2
3. Rekursion allgemein	Implementierung von Rekursion und Divide-and-Conquer-Idee für einfaches Beispiel; Aufruf einer Methode aus sich selbst heraus; Bsp. Fakultät: n!=1*2*3*...*n und 0!=1 (s. Code); Rekursionstiefe wie intern regeln? – Stack, Stack Overflow: häufiger Fehler, deshalb z.B. größte Website zum Thema Programmieren danach benannt	s. Code: factorial(int i) = i == 0 ? 1 : i * factorial(i - 1); Startbedingung? – i == 0 ? 1, Combine? – i *, Conquer? – factorial, Divide? – (i - 1)
4. Rekursive Binäre Suche	Immer Mitte – wie berechnen? – früher: (left + right) / 2; Problem? – für sehr große Werte: overflow, vgl. Literatur-Link in Home; Alternative? – z.B. left + (right - left) / 2, so erst kleiner machen, dann addieren; mit gesuchtem verlgeichen, aktuelles left, right anpassen, je nachdem, aber immmer ohne aktuelle Mitte, rekursiv aufrufen: binarySearch(i, vals, left, mid - 1) bzw. binarySearch(i, vals, mid + 1, right); Erster Aufruf? – ganze Liste: binarySearch(i, vals, 0, vals.size() - 1)	s. Code
5. Binäre Suche: Laufzeitanalyse	Laufzeit im Verhältnis zur Eingabe? – je größer, desto mehr lohnt das Halbieren (je größer, desto mehr muss man nicht prüfen: mit 1 Vergleich können wir 2 Einträge durchsuchen, mit 2 Vergleichen 4 Einträge, mit 3 Vergleichen 8 Einträge – mit k Vergleichen können wir 2^k Einträge durchsuchen (Ausgangsbedingung: 2 Elemente mit 1 Vergleich durchsuchen: 2¹), d.h. z.B. mit k=10 1024, mit k=20 über eine Million k=30 über eine Milliarde – Gewinn wächst also exponentiell, d.h. Laufzeit nimmt umgekehrt exponentiell ab, d.h. die Laufzeit wächst wie? – logarithmisch: O(log_2 n) weil log_2(n)=k (k Schritte um n Elemente zu durchsuchen) und 2^k=n (n Elemente durchsuchen mit 2^k Vergleichen); durch einfachen gedanklichen Trick einen echten Unterschied gemacht: der Algorithmus wird proportional zur Problemgröße immer schneller!	Tafel: dritte Kurve: O(log n) und letzte Woche? – konstant, O(1), d.h. bisher 4 Komplexitätsklassen: konstant/logarithmisch/linear/quadratisch; und quasi das Gegenteil zu logarithmisch: exponentiell, O(n^k); d.h. 5 Kurven, Klassen von Laufzeitkomplexität
Comparable	Andere Sachen Sortieren als Zahlen? – Interface das für spezielle Objekte je nach Ordnung Zahlen gibt; Comparable implementieren, compareTo statt ==, <, >; == (return 0), this < that (return -1), this > that (return 1); ansonsten identisch konzeptuell; Beispiel: Book, sortieren erst nach Autor, dann nach Titel	s. Code
Hausaufgabe	InsertionSort-Alternative; Rekursion: Fibonacci; Binäre Suche für Book	Sommer-Aufgabe-02