Lehre‎ > ‎

Proseminar "DAP mit Python"

Wintersemester 2012/13

Inhalt:
In den DAP-Vorlesungen in den ersten Studiensemestern werden Java und C/C++ gelehrt. Es gibt aber zahlreiche andere Sprachen, die sich in der Praxis durch die Möglichkeit auszeichnen, schnell prototypische Anwendungen zu entwickeln. Python verwendet keine Typdeklarationen und zeichnet sich durch kurzen Code und hohe Lesbarkeit aus. Die Ausführungsgeschwindigkeit ist gegenüber C geringer, da der Code interpretiert wird, aber die Entwicklungszeiten sind in Python deutlich schneller.
Das Proseminar soll interessante Datenstrukturen und Algorithmen aus DAP1+2 und ggf. dem Softwarepraktikum wieder aufgreifen und dabei vertiefen. Die Algorithmen sollen von den Studierenden selbst in Python dargestellt und programmiert werden; dabei sollen v.a. Python-typische Sprachelemente eingesetzt werden. In den ersten Vorträgen werden dazu zunächst die wesentlichen Elemente der Sprache präsentiert.

Termin im Semester: Fr 8:30-10:00 in OH14/304

Formalitäten

  • Das Proseminar findet im Wintersemester 2012/13 statt.
  • Mailingliste: Eine Mailingliste proseminar-dapy.cs@lists.tu-... ist eingerichtet. Sie können diese Liste verwenden, um allen Teilnehmern eine Nachricht zu schicken. Bitte nutzen Sie Ihren TU-Account, da wir andere Mails blockieren.
  • Präsentationstechniken: Für Bachelor-StudentInnen ist ein zusätzlicher Kursteil (1 SWS) über Präsentationstechniken verpflichtend. Den TeilnehmerInnen dieses Proseminars wird empfohlen, den Kurs "Präsentationstechniken" von Renate Thies zu belegen. Sie können aber auch einen anderen Kurs belegen. Sie erhalten den Proseminarschein insgesamt erst, wenn Sie den Präsentationskurs erfolgreich abgelegt haben.
  • Themenbetreuung: Zur Vorbereitung auf Ihre Präsentation können Sie die unten angegebene Literatur verwenden. In jedem Fall setzen Sie sich bitte mit Ihrem Betreuer / Ihrer Betreuerin in Verbindung und besprechen die Einzelheiten, nachdem Sie sich einen Überblick über ihr Thema verschafft haben.
  • Wichtige Hinweise: Beachten Sie unbedingt die Hinweise zu Seminar-Ausarbeitungen und die allgemeinen Hinweise zu Vorträgen!
  • 45-minütiger Vortrag:
    • Benutzen Sie ein Tool Ihrer Wahl.
    • Abgabe einer ersten Version 2 Wochen vor Ihrem Vortrag. Bitte das .pdf an Ihre/n Betreuer/in schicken.
    • 30 Minuten Vortrag + 5 Minuten Python-Demo + 10 Minuten Diskussion
    • 25 Minuten Vortrag + 10 Minuten Python-Demo + 10 Minuten Diskussion (für programmierlastigere Themen)
    • Der Vortrag geht zu ca. 50% in die Note ein.
  • Inhaltlich vollständige Ausarbeitung:
    • Für Ihre Ausarbeitung benutzen Sie ein subversion repository, das noch angegeben wird.
    • Die Ausarbeitung muss mit LaTeX erfolgen.
    • Abgabe einer ersten Version spätestens 2 Wochen nach Ihrem Vortrag ins subversion repository laden. (Darf auch gerne schon vor Ihrem Vortrag geschehen.)
    • Nach der Korrektur seitens der Betreuer haben Sie 2 Wochen Zeit, Verbesserungen einzuarbeiten.
    • Die Ausarbeitung geht zu ca. 50% in die Note ein.

Voraussichtlicher Zeitplan

Datum
Thema
Vortragende/r
Betreuer
Do 27.09.
Empfohlener Präsentationskurs (10:00 - 18:00, OH14, Raum 202)
Renate Thies
 
Mo 01.10.
Empfohlener Präsentationskurs (10:00 - 18:00, OH14, Raum 202)Renate Thies
 
  -- Beginn Wintersemester 2012/13 --  
Fr 12.10.
Einführung: Die Python Shell, einfache BeispieleSven Rahmann
Fr 19.10.Einführung in die Literaturrecherche (UB!):
Raum 126b im 1.OG der Zentralbibliothek, 8:30 Uhr
Hans-Georg Becker
Gabriele Schönfelder

Fr 26.10.Wissenschaftliches Schreiben mit LaTeXDominik Kopczynski 
Fr 02.11.1. Syntax, Imperative Programmierung, Funktionsdefinitionen, Namespaces, Module
2. Grundlegende Datentypen (int, float, str, list, tuple, dict, ...)
Tim Garstecki
Todor Nikolov
Wohlers
Wohlers
Fr 09.11.3.Objektorientierte Programmierung (class, Konstruktor, Attribute, Methoden, Vererbung)
4. Ausnahmebehandlung (try, except, finally), Kontextmanager (with-Anweisung)
Sven Rahmann
Andreas Beckmann
Wohlers
Wohlers
Fr 16.11.5. Funktionale Elemente (Funktionen-Funktionen, lambda, map, functools, Dekoratoren)
6. Generatorfunktionen (yield), Generatorausdrücke, List comprehensions
Kevin Chwalek
Henning Brockmann
Wohlers
Wohlers
Fr 23.11.7. Kommandozeilenprogramme (argparse, ArgumentParser)
8. Sortierverfahren: Bucketsort, Countingsort, Radixsort
Daniel Scholtyssek
Patrick Wolf
D'Addario
D'Addario
Fr 30.11.9. Sortierverfahren: Python's sort-Funktion (Timsort, Mergesort)
10. Datenstrukturen: balancierte Bäume: AVL-Baum
Malte Baumann
Sigo Rosenkranz
D'Addario
D'Addario
Fr 07.12.11. Datenstrukturen: balancierte Bäume: B-Baum und Varianten (B*, B+)
12. Datenstrukturen: disjunkte Mengen (Partitionen)
Christian Schnieder
Marc Walocha
D'Addario
D'Addario
Fr 14.12.13. Datenstrukturen: Red-Black Trees
14. Graphenalgorithmen: der A*-Algorithmus
Thomas Pathmann
Stefan Kinzel
Kopczynski
Kopczynski
Fr 21.12.15. Graphenalgorithmen: Bestimmung starker Zusammenhangskomponenten (Tarjan)
16. DP-Algorithmen: längste gemeinsame Teilsequenz
Abdullah Ates
Menno Esen
Kopczynski
Kopczynski

 -- Weihnachten / Neujahr -- frei vom 22.12.12 bis zum 06.01.13 --

Fr  11.01.17. Clusteringalgorithmen: k-nearest-neighbor
18. Zusammenfassung
Sabrina Friesenborg
Sven Rahmann
Kopczynski
Fr  18.01.

  
Fr  25.01.

  
Fr  01.02.


 

Verbleibende Themenvorschläge:

  1. Ordnungsstatistiken in erwarteter Linearzeit
  2. Ordnungsstatistiken in garantierter Linearzeit
  3. DP-Algorithmen: optimale Matrixmultiplikation
  4. DP-Algorithmen: optimale binäre Suchbäume
  5. Hashing mit offener Adressierung

Literaturhinweise

  • Ihre eigenen DAP1/2- und SoPra-Aufzeichnungen, sowie Übungsblätter.
  • Python3-Dokumentation
  • Mark Pilgrim. Dive into Python 3. Apress, 2010.
  • Paul Barry. Head First Python. O'Reilly, 2010.
  • Brian K. Jones, David Beazley. Python Cookbook, 3rd edition. O'Reilly, Dec. 2011.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.  Introduction to Algorithms, 3rd edition. MIT Press, 2009.



Sommersemester 2012


Inhalt:
In den DAP-Vorlesungen in den ersten Studiensemestern werden Java und C/C++ gelehrt. Es gibt aber zahlreiche andere Sprachen, die sich in der Praxis durch die Möglichkeit auszeichnen, schnell prototypische Anwendungen zu entwickeln. Python verwendet keine Typdeklarationen und zeichnet sich durch kurzen Code und hohe Lesbarkeit aus. Die Ausführungsgeschwindigkeit ist gegenüber C geringer, da der Code interpretiert wird, aber die Entwicklungszeiten sind in Python deutlich schneller.
Das Proseminar soll interessante Datenstrukturen und Algorithmen aus DAP1+2 und ggf. dem Softwarepraktikum wieder aufgreifen und dabei vertiefen. Die Algorithmen sollen von den Studierenden selbst in Python dargestellt und programmiert werden; dabei sollen v.a. Python-typische Sprachelemente eingesetzt werden. In den ersten Vorträgen werden dazu zunächst die wesentlichen Elemente der Sprache präsentiert.

Formalitäten
  • Das Proseminar findet im Sommersemester 2012 statt.
  • Vorbesprechung: Mittwoch, 01.02. um 10 ct in OH14/E04 (Fakultätssitzungsraum)
    Wer zu diesem Termin aus triftigen Gründen nicht kommen kann, aber trotzdem teilnehmen möchte, muss sich bei mir vorher per e-mail mit Begründung entschuldigen lassen. Andernfalls wird sie/er automatisch vom Proseminar ausgeschlossen.
    (3 vorher angemeldete TeilnehmerInnen sind nicht erschienen und wurden ausgeschlossen. Die Plätze wurden mit Nachrückern besetzt.)
  • Mailingliste: Eine Mailingliste proseminar-dapy.cs@lists.tu-... ist eingerichtet. Sie können diese Liste verwenden, um allen Teilnehmern eine Nachricht zu schicken. Bitte nutzen Sie Ihren TU-Account, da wir andere Mails blockieren.
  • Präsentationstechniken: Für Bachelor-StudentInnen ist ein zusätzlicher Kursteil (1 SWS) über Präsentationstechniken verpflichtend. Den TeilnehmerInnen dieses Proseminars wird empfohlen, den Kurs "Präsentationstechniken" von Renate Thies zu belegen. Der Kurs findet am Mi 28.3. und Fr 30.3. ganztägig statt (ca. 10-17 Uhr). Der Raum wird über die Mailingliste bekannt gegeben.
    Alle TeilnehmerInnen, die unten in der Zeitplan-Tabelle aufgeführt sind, sind automatisch für diesen Kurs angemeldet. Bitte geben Sie Renate Thies und Sven Rahmann Bescheid (@tu-dortmund.de), wenn Sie nicht an dem Kurs teilnehmen! Sie müssten in diesem Fall selbst einen anderen Kurs finden! Sie erhalten den Proseminarschein insgesamt erst, wenn Sie den Präsentationskurs erfolgreich abgelegt haben.
  • Themenbetreuung: Zur Vorbereitung auf Ihre Präsentation können Sie die unten angegebene Literatur verwenden. In jedem Fall setzen Sie sich bitte mit Ihrem Betreuer / Ihrer Betreuerin in Verbindung und besprechen die Einzelheiten, nachdem Sie sich einen Überblick über ihr Thema verschafft haben.
  • Seminartermin im Semester: Do 8:30 - 10:00, OH16/205
  • Wichtige Hinweise: Beachten Sie unbedingt die Hinweise zu Seminar-Ausarbeitungen und die allgemeinen Hinweise zu Vorträgen!
  • Ausarbeitung: Für Ihre Ausarbeitung benutzen Sie ein subversion repository, das noch angegeben wird. Die Ausarbeitung muss mit LaTeX erfolgen.

Literaturhinweise
  • Ihre eigenen DAP1/2- und SoPra-Aufzeichnungen, sowie Übungsblätter.
  • Python3-Dokumentation
  • Mark Pilgrim. Dive into Python 3. Apress, 2010.
  • Paul Barry. Head First Python. O'Reilly, 2010.
  • Brian K. Jones, David Beazley. Python Cookbook, 3rd edition. O'Reilly, Dec. 2011.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.  Introduction to Algorithms, 3rd edition. MIT Press, 2009.

Zeitplan

Datum
Thema
Vortragende/r
Betreuer/in
Mi 28.3
Präsentationstechniken (ganztägig, s.o.)
Renate Thies
-/-
Fr 30.3.
Präsentationstechniken (ganztägig, s.o.)
Renate Thies
-/-
Do 05.4.
Einführung in die Literaturrecherche (UB!)
Hans-Georg Becker
-/-
Do 12.4.
Ausarbeitungen mit LaTeXSven Rahmann
-/-
Do 19.4.
1. Grundlagen, imperative Programmierung
2. Objektorientierte Programmierung
Oliver Köhler
Ali Güney
Rahmann
Rahmann
Do 26.4.
3. Funktionale Elemente; GeneratorfunktionenRahmannRahmann
Do 03.5.
5. Kontextmanager (with-Anweisung)
6. Sortierverfahren: Heapsort
Sabrina Friesenborg
Maximilian Krämer
Rahmann
D'Addario
Do 10.5.
7. Sortierverfahren: Mergesort
8. Sortierverfahren: Quicksort
Marco Hartwecker
Steffen Augustin
D'Addario
D'Addario
Do 17.5.
-- Himmelfahrt --
  
Do 24.5.
9. Python's sort-Funktion
10. Graphenalgorithmen: DFS und BFS
Daniel Smit
Alexander König
Rahmann
D'Addario
Do 31.5.
11. Graphenalgorithmen: Kruskal
12. Graphenalgorithmen: Prim
Eric Fiege
Jan Mühlig
D'Addario
D'Addario
Do 07.6.
-- Fronleichnam --
  
Do 14.6.
13. Graphenalgorithmen: Dijkstra
14. Graphenalgorithmen: Floyd-Warshall
Tobais Holz
Philip Zweihoff
Kopczynski
Kopczynski
Do 21.6.
15. Graphentests: Bipartitheit
16. Graphentests: 2-Zusammenhang
Dennis/Jan? Gaidel
Lutz Thrun
Kopczynski
Kopczynski
Do 28.6.
17. Datenstrukturen: Skiplisten
18. Codierung: Huffman Coding
Sergei Penner
Tanja Bock
Kopczynski
Rahmann
Do 05.7.
19. Grafikalgorithmen: Bézier Kurven
20. Clusteringalgorithmen: K-Means
Eric Ruider
Sascha Schwabbauer
Kopczynski
Rahmann
Do 12.7.
4. Ausnahmebehandlung
Zusammenfassung; Hinweise zu Ausarbeitungen
Jochen Plattner
Sven Rahmann
Rahmann
-/-

Weitere mögliche Themen in Zukunft
  1. Datenstrukturen: balancierte Bäume: AVL-Baum
  2. Datenstrukturen: balancierte Bäume: B-Baum und Varianten (B*, B+)
  3. Datenstrukturen: disjunkte Mengen (Partitionen)
  4. Ordnungsstatistiken in erwarteter und garantierter Linearzeit
  5. Graphenalgorithmen: der A*-Algorithmus
  6. DP-Algorithmen: optimale Matrixmultiplikation
  7. DP-Algorithmen: längste gemeinsame Teilsequenz
  8. DP-Algorithmen: optimale binäre Suchbäume
  9. Zahlentheoretische Algorithmen: Grundlagen; Faktorisierung; Primzahltests; RSA-Verschlüsselung



Proseminar "Algorithmen mit Python", Sommersemester 2009

  • Das Seminar findet im Sommersemester 2009 statt.
  • Vorbesprechung: Freitag 09.01.2009, 10:00 (s.t.!), in OH14, R.202. Wer zu diesem Termin aus triftigen Gründen nicht kommen kann, aber trotzdem teilnehmen möchte, muss sich bei mir vorher per e-mail mit Begründung entschuldigen lassen. Andernfalls wird sie/er automatisch vom Proseminar ausgeschlossen. Hier gibt es die Folien zur Vorbesprechung.
  • Allgemeine Hinweise zu Proseminaren (Anmeldung, Vortragserstellung, Ausarbeitung, etc.): hier
  • Präsentationstechniken: Für Bachelor-StudentInnen ist ein zusätzlicher Kursteil (1 SWS) über Präsentationstechniken] verpflichtend. Dieser Kursteil wird im Sommersemester von Prof. Vahrenhold (Veranst.-Nummer 49992) angeboten und steht nur den Teilnehmern seines und dieses Proseminars offen. Details hier.
  • Literaturrecherche: Im Rahmen dieses Proseminars wird es einen Termin zur Einführung in die Literaturrecherche in der Universitätsbibliothek geben. Dieser ist verpflichtend!
  • Ausarbeitung: Für Ihre Ausarbeitung checken Sie die aktuelle Skript-Version aus dem Subversion-Repository svn://ls11svn.cs.uni-dortmund.de:1011/rahmann/proseminar-python-ss2009 aus; fügen Ihre Dateien hinzu und checken eine aktualisierte Version wieder ein (svn checkout; svn add; svn commit). Beachten Sie unbedingt die Hinweise zu Seminar-Ausarbeitungen und die allgemeinen Hinweise zu Proseminaren!
Das Proseminar hat zwei Ziele. Zum einen soll die Sprache Python erlernt werden; dies geschieht in den ersten Vorträgen, die sich zum Teil auf bereits bekannte Algorithmen aus DAP1 und DAP2, wo diese mit Java bzw. C/C++ erlernt wurden, beziehen. Zum anderen sollen in den späteren Vorträgen neue Algorithmen erarbeitet und am Beispiel von Python vorgestellt werden.
Warum Python? Python ist eine interpretierte Skript-Sprache, die auf dem Prinzip des "duck typing" beruht. Das bedeutet, dass (anders als in Java oder C) Variablen keinen vorbestimmten Typ haben müssen; Deklarationen entfallen also. Es wird erst zur Laufzeit, wenn man beispielsweise eine Methode aufruft, geprüft, ob das aufrufende Objekt überhaupt über diese Methode verfügt. Dies sieht auf den ersten Blick seltsam aus, erlaubt aber in vielen Fällen, Programme zu schreiben, die man wie Pseudocode aus einem Algorithmenbuch lesen kann.
Python ist im Grunde objektorientiert, so dass die aus DAP1 und DAP2 bekannten OOP-Konzepte Anwendung finden. Der Vorteil ist jedoch, dass man davon (insbesondere bei kurzen Programmen, wenn man nur mal "Hello world" ausgeben will) keinen Gebrauch machen muss. Ausserdem können Elemente funktionaler Programmierung verwendet werden (z.B. lambda, map, reduce). Ende 2008 wird Python 3 (eine neue, zu vorherigen Sprachversionen teilweise inkompatible Version) herauskommen. Die Ausarbeitungen des Proseminars sollen in jedem Fall auf der neuen Version basieren. Jedes Proseminar-Thema ist entweder eher sprachorientiert oder eher algorithmenorientiert. Genaueres wird bei der Vorbesprechung erklärt.

Teilnehmer/innen, Termine, Themen

Termin im Semester: jeden Montag 12-14 Uhr in OH14, R202.
Kein Treffen am Ostermontag; daher Beginn am 20.04.2009!

Es wird erwartet, dass jede/r Code in Python schreibt und auch im Proseminar vorstellt.
Themen beziehen sich entweder auf ein Algorithmisches Problem aus [1] oder bestimmte Sprachelemente von Python [2],[3],[4].
Wenn im Vortrag Code gezeigt wird, muss dieser lauffähig sein, darf aber den Umfang von einer Folie nicht überschreiten.


Datum/Zeit Thema Literatur Vortragende/r
09.01.2009, 10:00 Vorbesprechung
Prof. Rahmann, Prof. Vahrenhold, Herr Pasternak
27+28.03.09 Kurs Präsentationstechniken
Prof. Vahrenhold
20.04. Hinweise zur Ausarbeitung
Prof. Rahmann
27.04. + 04.05. Teilnehmer-Kurzvorträge zum Kursteil Präsentationstechniken
alle
11.05. Bibliothekstermin
Frau Schönfelder (UB)
18.05. 1. Philosophie von Python; Duck typing, OOP [2] Sarah Risse
18.05. 2. Sequenzdatentypen in Python [2], 4-9; [3], 20, online Katharina Diekmann
25.05. 3. Iteratoren und Generator Functions [2], 13+17, online Daniel Noack
25.05. 4. Funktionale Elemente von Python [2], 17, online Christian Andersen
08.06. 5. Heapsort und Prioritäts-Warteschlangen [1], 6 Jan Jansen
08.06. 6. DP: Optimale binäre Suchbäume [1], 12 und 15.5 Jakob Bossek
15.06. 7. Ordnungsstatistiken in erwarteter Linearzeit [1], 9.1 und 9.2 Ulrich Gabor
15.06. 8. Ordnungsstatistiken in garantierter Linearzeit [1], 9.3 David Gräff
22.06. 9. Huffman-Codes [1], 16.3; [8], 5. Tom Eckelmann
22.06. 10. Der A*-Algorithmus nach Absprache Robert Kirberich
06.07. 11. Zahlentheoretische Algorithmen I [1], 31.1 bis 31.3. Tobias Paulini
06.07. 12. Das RSA-Verschlüsselungssystem [1], 31.7. Leonhard Küper
13.07. 13. Primzahtests [1], 31.8. Matthias Kuchem
13.07. 14. Faktorisierung von Zahlen [1], 31.9. Michael Nimbs

DP: Matrix-Ketten-Multiplikation; Längste gemeinsame Teilsequenz [1], 15.2, 15.4

Datenstrukturen für disjunkte Mengen (Partitionen) [1], 21

Zahlentheoretische Algorithmen II [1], 31.4. bis 31.6.

Literatur (Sommersemester 2009)

Die Algorithmen stammen aus dem bekannten Algorithmik-Buch [1].
Die Sprachelemente von Python und ihre Benutzung lernt man vollständig aus [2], [3], [4]; allerdings noch nicht für die neue Version Python 3.0!
Dazu ist die Konsultation der online-Dokumentation [http://www.python.org] notwendig.
Weiterführende Literatur (die für das Proseminar nicht notwendig ist, aber hilfreich sein kann) ist [5],[6],[7].

[1]
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduction to Algorithms, 2nd edition
MIT Press, 2001

[2]
Mark Lutz
Learning Python, 3rd Ed.
O'Reilly, 2007

[3]
Mark Lutz
Programming Python, 3rd Ed.
O'Reilly, 2006

[4]
Alex Martelli, Anna Martelli Ravenscroft, und David Ascher
Python Cookbook, 2nd Ed.
O'Reilly, 2005/2008

[5]
Bradley N. Miller und David L. Ranum
Problem Solving with Algorithms and Data Structures Using Python
Franklin Beedle & Associates, 2005

[6]
Hans P Langtangen:
Python Scripting for Computational Science, 3rd Ed.
Springer, 2008

[7] Weblinks:
http://www.python.org/
http://www.ece.uci.edu/~chou/py02/python.html
http://www.cs.luther.edu/~bmiller/Papers/paper20.pdf
http://www.brpreiss.com/books/opus7/public/front.pdf

[8]
David J.C. MacKay
Information Theory, Inference, and Learning Algorithms
Cambridge University Press, 2003/2004



Comments