Dieses Semester (Wintersemester 2009/2010) besuche ich bei Frau Fehr die Vorlesung über Übersetzerbau (oder neudeutsch Compilerbau). Obwohl die Vorlesung zu einer studentenunfreundlichen Uhrzeit stattfindet, probiere ich dennoch erstens immer hinzugehen und zweitens dabei eine Mitschrift anzufertigen, die Sinn ergibt. Diese Mitschrift werdet ihr dann an dieser Stelle finden.

1. Vorlesung: Einführungen zu Compilern, grober Aufbau.
2. Vorlesung: Wir beschäftigen uns nun mit der Syntaxanalyse, die in den Compilern durchgeführt wird. Dazu gucken wir uns nochmals kontextfreie Grammatiken an.
3. Vorlesung: Es ging um syntaxgerichtete Übersetzung und Syntaxschemata.
4. Vorlesung: Es ging um die Syntaxanalyse des Parsers und wie man prädiktive Syntaxanalyse betreiben kann
5. Vorlesung: Wir haben die bisher besprochenen Komponenten zu einem vollständigen Front-End eines Übersetzers kombiniert.
6. Vorlesung: Die lexikalische Analyse war heute Thema.
7. Vorlesung: Wir haben uns die Interaktion zwischen Lexer und Parser angeschaut und wie man Fehlerbehandlung schon im Lexer betreiben kann.
8. Vorlesung: Wir haben uns mit regulären Definitionen beschäftigt.
9. Vorlesung: Wir haben uns überlegt, wie man Token durch endliche Automaten erkennen kann.
10. Vorlesung: Der Lexer-Generator Lex wurde vorgestellt.
11. Vorlesung: Syntaxanalyse im Parser (höchst unvollständig ;-))
12. Vorlesung:  Wir haben uns Techniken angesehen, wie man Nichtterminismus Eliminieren kann. Ein Beispiel ist die Eliminierung der Linksrekursion oder die Linksfaktorisierung.
13. Vorlesung: Wir haben die deterministische Top-Down-Syntaxanalyse betrachtet und wie man FIRST- und FOLLOW-Mengen bildet.
14. Vorlesung: Als Fortsetzung der Top-Down-Analyse haben wir eine Parse-Tabelle aufgestellt und geguckt, wie man damit eine Fehlerbehandlung betreiben kann.
15. Vorlesung: Es ging weiter mit der Parse-Tabelle. Dann haben wir noch mit der Bottom-Up-Analyse angefangen.
16. Vorlesung: Weiter mit Bottom-Up-Analyse. Und wir haben uns die Shift-Reduce-Analyse angeschaut.
17. Vorlesung: Die einfache LR-Syntaxanalyse (Simple LR-Parser) war Thema.
18. Vorlesung: Struktur und Aufbau der Parse-Tabelle bei SLR
19. Vorlesung: Semantische Analyse und syntaxgerichtete Definitionen war Thema.
20. Vorlesung: Wir haben uns die topologische Sortierung von SDDs angeschaut.
21. Vorlesung: Wir haben uns als weitere Anwenund syntaxgerichteter Definitionen Syntaxbäume angeschaut.
22. Vorlesung: Statt einem Syntaxbaum erstellen wir nun einen DAG (directed acyclic graph)
23. Vorlesung: Wir beginnen mit dem Abschnitt Zwischencode-Erzeugung. Als einen Vertreter davon betrachten wir den 3-Adress-Code
24. Vorlesung: Wir schauen uns an, wie man 3-Adress-Code für imperative Programmiersprachen erzeugen kann.
25. Vorlesung: Laufzeitumgebungen sind das Thema.
26. Vorlesung: Codeerzeugung und Kosten von Befehlen
27. Vorlesung: Grundblöcke und Flussgraphen
28. Vorlesung: Lebendigkeit und nächste Verwendung mit dem Blick auf Code-Optimierung

Download der Übersetzerbau Mitschrift

Letztes Update am 7.09.2010 12:06

Im Wintersemester 2008/2009 besuchte ich die Mustererkennungsvorlesung und dazu gibt es natürlich auch wieder eine Mitschrift (handschriftlich).

1. Vorlesung: Ausblick in Mustererkennung anhand von Viola-Jones (siehe Paper)
2. Vorlesung: KNN (k nearest neighbours) Algorithmus
3. Vorlesung Clustering (k-means) und unüberwachtes Lernen
4. Vorlesung: EM-Algorithmus (Expectation Maximization) und Lineare Regression
5. Vorlesung: PCA (Principal Component Analysis) und der Algorithmus von Oja
6. Vorlesung: Fisher’s linear discriminant
7. Vorlesung: Perzeptrons und Perzeptronlernen (Dank an Lisa für ihre Mitschrift!)
8. Vorlesung: Verallgemeinerung des Perzeptron-Lernalgorithmus (Neuronale Netze) mit Backpropagation
9. Vorlesung: Backprop-Algorithmus mit Matrizen und Verfeinerungen mit Silva & Almeida, Momentum und RPROP.
10. Vorlesung: Blind source separation (independent component analysis)
11. Vorlesung: Non-negative matrix factorization
12. Vorlesung: Entscheidungsbäume und ID3-Algorithmus
13. Vorlesung: Über Merkmalsextraktionen und bekannte Features
14. Vorlesung: Boosting

Download der Mustererkennungsmitschrift (27 MB da Scan!)

Letzten Montag hatte ich meine erste mündliche Diplomprüfung in Datenbanksysteme (Gedächnisprotokoll siehe Spline) und so peu à peu werden die nächsten folgen. In meiner Vorbereitung für DBS ist dabei eine ziemlich lange stichpunktartige Zusammenfassung des ganzen Stoffs entstanden, die ich hier gerne der Allgemeinheit zu Verfügung stellen möchte. Auch wenn ich nur jedem raten kann, solche Zusammenfassungen selber anzufertigen, da man (oder zumindest ich) bei dieser Arbeit schon am meisten lernt.

• Stoffzusammenfassung für die Datenbanksystem-Prüfung in anwendungsorientierter Informatik
• Zusammenfassung für die Telematik-Prüfung in technischer Informatik

Für die weiteren Prüfungen (Höhere Algorithmik etc.) plane ich auch solche Zusammenfassungen und werde die Materialienliste also nach und nach erweitern.

Letztes Update am 31.10.2009 9:49

Das Semester ist jetzt zwar fast vorbei, dennoch wollte ich es nicht versäumen, noch meine (handschriftliche) Mitschrift der Computer Vision Vorlesung im Sommersemester 2009 online zu stellen.

1. Vorlesung: Farbsegmentierung
2. Vorlesung: Farbtabellen mit KD-Bäumen
3. Vorlesung: Radiale Verzerrung bzw. Entzerrung
4. Vorlesung: Lokalisierung im Raum anhand 3 bzw. 4 Punkten
5. Vorlesung: Fortsetzung zu Lokalisierung, diesmal mit EM-Algorithmus. Quaternionen angeschnitten.
6. Vorlesung: Fortsetzung zu Quaternionen, Rotation und homogene Koordinaten dazu.
7. Vorlesung: Stereo Vision und Tiefeninformation
8. Vorlesung: Optischer Fluss (Optical Flow)
9. Vorlesung: SIFT Features (nicht im Skirpt enthalten, da Slides)
10. Vorlesung: Hough-Transformation und Harris-Corner-Detector

Download Computer Vision Mitschrift (ca. 14MB, da Scan!)

Letztes Update am 24.08.2009 22:03

Hier werde ich meine Mitschriften zur Vorlesung “Höhere Algorithmik” im Wintersemester 2008/2009 der Allgemeinheit zu Verfügung stellen.

1. Vorlesung: Einführung in Algorithmen und Effizienz anhand von ein paar Sortieralgorithmen.
2. Vorlesung: Fortsetzung von der vorhergehenden Stunde.
3. Vorlesung: Wir haben mit Berechnungsmodellen angefangen, im speziellen mit Turinmaschinen und RAMs.
4. Vorlesung: Weiter im Text mit Berechnungsmodellen und wie man sie vergleichen kann. Und noch ein paar Bemerkungen zum Suchen und Sortieren
5. Vorlesung: Nachdem wir uns zu Ende über das Suchen und Sortieren Gedanken gemacht haben, haben wir mit dem Auswahlproblem angefangen.
6. Vorlesung: Wir haben uns ein deterministisches Auswahlverfahren angeguckt und dann mit Binärsuche und als Verbesserung dazu die Interpolationssuche angeschaut.
7. Vorlesung: Wir haben die Suchverfahren mit der Quadratischen Binärsuche abgeschlossen.
8. Vorlesung: Das neue Kaptiel heißt Datenstrukturen. Wir widmen uns dem Wörterbuchproblem und gucken uns sortierte Arrays, Hashing, binäre Suchbäume, AVL-Bäume und BB[α]-Böume an.
9. Vorlesung: Weiter mit dem Wörterbuchproblem und (a,b)-Bäumen, Rot-Schwarz-Bäumen und schlussendlich Tries. Optimale binäre Suchbäume wurden angerissen, damit geht es nächstes mal weiter.
10. Vorlesung: Es ging weiter mit den optimalen Suchbäumen. Wir haben zum Aufbau von solchen Bäumen einen Algorithmus kennengelernt.
11. Vorlesung: Abschließend zu optimalen Suchbäumen haben wir den Algorithmus analysiert und gesehen, wie man ihn optimieren kann. Dann haben wir mit dem Vereinige-Finde-Problem (oder auch Union-Find) angefangen.
12. Vorlesung: Wir haben Union-Find analysiert und per Pfadkompression weiter verbessert.
13. Vorlesung. Es wurde mit Graphen angefangen. Nach vielen Definitionen ging es auch kurz um Travsersierungen und topologisches Sortieren. Danke an Gero, der mir seine Tafelbilder zu Verfügung gestellt hat.
14. Vorlesung: Wir haben angeguckt, wie man mit dem Algorithmus von Kruskal minimal spannende Bäume baut und wie Dijkstra kürzeste Wege findet.
15. Vorlesung: Wir haben uns mit dem Floyd-Warshall-Algorithmus beschäftigt, der das All-Pairs-Shortest-Path-Problem löst.
16. Vorlesung: Nach den Wegproblemen folgen nun die Flüsse in Netzen. Wir haben den Ford-Fulkerson-Algorithmus kennen gelernt, der den maximalen Fluss berechnet.
17. Vorlesung: Weiter mit Ford-Fulkerson.
18. Vorlesung: Zuende mit Ford-Fulkerson und dann gleich noch Edmonds-Karp hinterher, der ein wenig anders als Ford-Fulkerson funktioniert.
19. Vorlesung: Als letztes zum Thema Graphen haben wir uns das bipartite Matching angeschaut. Das neue Kapitel ist nun String Matching.
20. Vorlesung: String Matching haben wir fortgeführt und und den Algorithmus von Knuth-Morris-Pratt weiter angeschaut. Und dann dazu auch noch Suffixbäume.
21. Vorlesung: Wir haben das Kapitel String Matching abgeschlossen und mit NP-Vollsändigkeit angefangen.
22. Vorlesung: Wir haben uns die Klassen P und NP angeschaut und definiert, was polynomzeit Reduktion ist.
23. Vorlesung: Wir haben definiert, was NP-schwer und NP vollständig bedeutet und gezeigt, dass CSAT (Schaltkreiserfüllbarkeit) ein NP vollständiges Problem ist.
24. Vorlesung: Wir haben uns weitere NP vollständige Probleme angeschaut. Es kam SAT …
25. Vorlesung: … 3-SAT, CLIQUE …
26. Vorlesung: … UK (Unabhängige Knotenmenge), ÜK  (überdeckende Knotenmenge), SUBSET-SUM und GHK (gerichteter Hamiltonscher Kreis).
27. Vorlesung:  Wir haben uns andere Komplexitätsklassen angeschaut. Darunter waren Co-NP, PSPACE und EXPTIME.
28. Vorlesung: Approximationsalgorithmen heißt das neue Kapitel. wir widmen uns zunächst Delta-TSP mit der Baumheuristik.
29. Vorlesung: Wir lernen die Christofides-Heuristik für Delta-TSP kennen und zeigen, warum das normale TSP nicht approximierbar ist.
30. Vorlesung: Wir lernen einen PTAS (polynomial time approx scheme) für SUBSET-SUM kennen.

Anmerkung: Die letzten drei Vorlesungen sind noch nicht überarbeitet! Aber da sicherlich einige schon jetzt reinschauen wollen um für die Klausur zu lernen, stelle ich es schon online. Ich versuche aber noch vor Freitag meine Notizen durchzugehen und zu überarbeiten. Ich wünsche schonmal allen viel Erfolg beim Lernen und vor allem bei der Klausur!

Edit (12.02.09, 15.00): Nun sind auch die letzten drei Vorlesungen überarbeitet!

Download Höhere Algorithmik Mitschrift

Letztes Update am 11.05.2009 18:49