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 Entiwcklungszeiten 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
- 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.
- 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 LaTeX | Sven 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; Generatorfunktionen
4. Ausnahmebehandlung
| Raphael Krusenbaum
Jochen Plattner
| Rahmann
Rahmann | 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.
| Zusammenfassung; Hinweise zu Ausarbeitungen
| Sven Rahmann
| -/-
|
Weitere mögliche Themen in Zukunft- Datenstrukturen: balancierte Bäume: AVL-Baum
- Datenstrukturen: balancierte Bäume: B-Baum und Varianten (B*, B+)
- Datenstrukturen: disjunkte Mengen (Partitionen)
- Ordnungsstatistiken in erwarteter und garantierter Linearzeit
- Graphenalgorithmen: der A*-Algorithmus
- DP-Algorithmen: optimale Matrixmultiplikation
- DP-Algorithmen: längste gemeinsame Teilsequenz
- DP-Algorithmen: optimale binäre Suchbäume
- 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
|
