Differences

This shows you the differences between two versions of the page.

--- repds15:logbuch [2015/09/23 19:22] – [Tag 3] mario
+++ repds15:logbuch [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1
@@ Line 1: / Line 1: @@
-====== Logbuch ======
-===== Tag 1 =====
-  * Website der Vorlesung: http://www.thi.informatik.uni-frankfurt.de/lehre/ds/sose15.de
-  * Logbuch der Vorlesung: http://www.thi.informatik.uni-frankfurt.de/lehre/ds/sose15/logbuch/
-  * Literatursuche Uni-Bibliothek: https://www.ub.uni-frankfurt.de
-  * Username und Passwort (wenn noch nicht geändert) http://www.ub.uni-frankfurt.de/benutzung/passwort.html
-  * [[https://hds.hebis.de/ubffm/Record/HEB334230551|Survivalguide Bachelor, 2. Auflage, 2014]] als PDF verfügbar
-  * [[https://de.wikipedia.org/wiki/Pomodoro-Technik|Pomodoro-Technik]]
-  * Vokabelliste anfertigen, Übersicht verschaffen, Lernwegweiser erstellen (wie etwa [[http://www.sepl.informatik.uni-frankfurt.de/2014-ws/m-ps/skills.en.html|hier]]), Prioritäten setzen
-  * "Lernen heißt verstehen, nicht auswendig lernen!"
-  * Online-Whiteboard: [[https://www.twiddla.com|Twiddla]]
-  * [[repds15:uebungsaufgaben|Übersicht der Übungsaufgaben]]
-  * [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|Data Structure Visualizations]]
-  * [[http://people.ksp.sk/~kuko/gnarley-trees/|Gnarley Trees: Data Structure Visualizations (Java Application)]]
-  * [[repds15:hausaufgaben_loes|Hausaufgaben (mit Lösungen und Tipps)]] können von jedem auch ohne Wiki-Account bearbeitet, ergänzt und verbessert werden. Achtung: Dort können auch neue und weiterführende Aufgaben stehen, die [[repds15:hausaufgaben|hier bei den Vorbereitungshausaufgaben]] nicht aufgeführt sind.
-  * Themen, die wir nur ganz schnell angeschnitten haben, werden hier auf der Website ergänzt. Ich bemühe mich um besseres Zeitmanagement, damit das nicht mehr so nötig sein wird.
-  * $f = O(g)$ heißt "f ist asymptotisch $\leq$ g" (bzw. f wächst höchstens so schnell wie g).
-  * $f = \Omega(g)$ heißt "f ist asymptotisch $\geq$ g" (bzw. f wächst mindestens so schnell wie g).
-  * $f = \Theta(g)$ heißt "f und g wachsen asymptotisch gleich schnell"
-  * $f = o(g)$ heißt $f << g$ bzw. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
-  * $f = \omega(g)$ heißt $f >> g$ bzw. $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$
-  * Laufzeit-Hierarchie von $\Theta(1)$ bis $\Theta(n^n)$
-  * $n! = o(n^n)$, aber $\log(n!) = \Theta(\log(n^n)) = \Theta(n \log(n))$. **Achtung**: Beim Logarithmieren und Exponenzieren können sich die Hierarchie-Beziehungen ändern! Das seht ihr auch an $n/2 = \Theta(n)$, aber $2^{n/2} = o(2^n)$.
-  * Master-Theorem: nicht besprochen. Stattdessen: Rekursionsgleichung aufstellen, ein paar Mal einsetzen und dann eine geschlossene Formel "raten". Streng genommen müsstet ihr diese geschlossene Formel noch per vollständiger Induktion beweisen. Für die Klausur reicht sehr wahrscheinlich die Angabe der Lösung. Rekursionsgleichungen werden wir immer dann üben, wenn wir rekursiv programmieren.
-  * Zu Arrays, Listen, Stacks und Queues findet ihr Pseudocodes bei den [[repds15:hausaufgaben_loes#arrays|Hausaufgaben (mit Lösungen und Tipps)]].
-===== Tag 2 =====
-  * Pseudocode-Beispiele zu Arrays, Listen, Stacks und Queues besprochen
-  * [[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html|Visualisierungen von vielen Datenstrukturen]]
-  * Bei Listen immer auf den current-Zeiger aufpassen: ''L.movetofront()'', um den Zeiger auf das head-Element (an den Start) zurück zu setzen.
-  * Stack durch eine Liste simuliert: [[https://www.cs.usfca.edu/~galles/visualization/StackLL.html|Klick!]]
-  * Datenstrukturen für Bäume, Anzahl der Knoten in einem vollständigen binären Baum
-  * Die rekursive Definition eines Baums (Basisfall: Blatt, Rekursionsfall: Knoten mit Bäumen als Kinder) kann leicht in ein Standard-Schema für ein rekursives Programm übersetzt werden.
-<code>
-def rekursive_baumfunktion(Knoten v):
-    if "v ist ein Blatt":     // Basisfall
-        Rechne irgendeinen Wert ''value'' in Laufzeit O(1) aus
-        return value
-    else                      // Rekursionsfall
-        rufe rekursive_baumfunktion(...) rekursiv für die Kinder von v auf
-        benutze den Rückgabewert des rekursiven Aufrufs, um einen Wert ''value'' auszurechnen
-        return value
-</code>
-  * Beispiel für ein rekursives Programm auf Bäumen
-  * [[https://en.wikipedia.org/wiki/Tree_traversal|Wikipedia (en.) - Tree Traversal]]
-  * Topologische Sortierung
-  * Datenstrukturen für Graphen
-  * Breitensuche (BFS), Tiefensuche (DFS) auf Bäumen und allgemeinen Graphen: Wie hängt die Laufzeit von der verwendeten Datenstruktur ab?
-  * Kantentypen: Baumkanten, Querkanten, Vorwärtskanten und Rückwärtskanten: **Achtung**: Baumkanten sind für BFS und DFS auf gerichteten und ungerichteten Graphen definiert. Die anderen Kantentypen sind laut Skript (Algo 4.9) nur für die Tiefensuche auf gerichteten Graphen definiert. Zusatzinfo: Bei der BFS auf ungerichteten Graphen können nur Baumkanten und "Nichtbaumkanten" unterschieden werden, wobei diese Nichtbaumkanten noch am ehesten als Querkanten bezeichnet werden könnten. Bei DFS auf ungerichteten Graphen wäre eine Unterscheidung von Vorwärts- und Rückwärtskanten nicht möglich. Obwohl es im Skript keine formale Definition für Rückwärtskanten der Tiefensuche auf ungerichteten Graphen gibt, sagt Satz 4.3, dass in diesem Fall nur Baum- und Rückwärtskanten existieren. Die Folien sind hier klarer: Sie definieren einfach jede Nichtbaumkante als Rückwärtskante.
-  * Heaps: Darstellung eines Heaps als Array. ''insert(x)'', ''delete_min(x)'' und ''change_priority(wo, p)'' an einem Beispiel gezeigt. **Achtung, nicht verwechseln**: Bei Min-Heaps führt ''change_priority(wo, p)'' bei einer Erhöhung der Priorität zu ''repair_down()'' zum kleinsten Kind von H[wo], bei einer Verringerung zu ''repair_up()'' Bei Max-Heaps ist es genau umgekehrt. Der Reparatur-Aufwand ist jeweils durch die Tiefe des Heaps beschränkt: O(log(n)), wenn der Heap n Elemente enthält.
-  * Heaps können zum Sortieren verwendet werden, siehe Heapsort.
-===== Tag 3 =====
-  * (2,3)-Bäume, **Achtung**: Beim Löschen von Schlüsseln verhält sich [[https://www.cs.usfca.edu/~galles/visualization/BTree.html|die Animation]] etwas anders als die Implementierung aus der DS-Vorlesung. Einfügen funktioniert aber gleich.
-  * Achtung auch bei anderen Wörterbuch-Datenstrukturen aus der Visualisierungswebsite. Dort können Schlüssel mehrfach eingefügt werden. Das geht gemäß der Konvention aus der Vorlesung jedoch nicht. Es können noch weitere Unterschiede vorhanden sein, also glaubt nicht blind der Animation.
-  * Binäre Suchbäume, einfügen, löschen, Best-Case- und Worst-Case-Beispiele (Wie sehen solche Folgen aus?)
-  * AVL-Bäume, einfügen, Rotationen, Zick und Zack
-  * (a,b)-Bäume am Beispiel von (2,3)-Bäumen, Mindest-Tiefe, Höchst-Tiefe
-  * Hashing
-    - mit Verkettung: Worst-Case-Beispiele
-    - mit offener Adressierung
-      * mit linearem Austesten
-      * doppeltes Hashing
-  * Rekursive Programmierung, Schritt 1: Finde eine rekursive Definition der Datenstruktur (Basisfall und Rekursionsfall), Schritt 2: Beschreibe eine rekursive Funktion als Pseudocode mit dem Standardschema "if(Basisfall) .... else (rekursiver Aufruf)".
-  * Laufzeitanalyse: Rekursionsgleichungen aufstellen und durch iteratives Einsetzen lösen
-  * Datenstrukturen entwerfen, Bitvektor, Projekte bestehend aus mehreren Aufgaben nach Bearbeitungszeit priorisieren mithilfe eines Min-Heaps
-  * [[repds15:hausaufgaben_loes#stichwoerterhinweise_auf_bestimmte_datenstrukturen|Stichworte]] gesammelt: Welche Begriffe aus dem Aufgabentext weisen bei Modellierungsaufgaben auf eine bestimmte Datenstruktur hin?