Seminar Theoretische Informatik: Funktionale Programmierung

• Seminar, Prof. Dr. Kreitz, Brede, Richter, Di. 10:00-12:00, 3.04.1.03

In diesem Seminar werden vertiefende Themen der theoretischen Informatik und angrenzender Bereiche der Mathematik anhand von ausgewählter Literatur besprochen.

Das Thema des SS 2013 ist "Funktionale Programmierung und Algorithmenentwurf". Funktionale Programmiersprachen bieten die Möglichkeit, Programme sehr nah an ihrer Spezifikation zu schreiben. Allerdings sind auf diese Art implementierte Algorithmen nicht notwendigerweise auch effizient -- das Seminar beschäftigt sich daher mit der strukturierten Verfeinerung solcher spezifikationsnaher Programme. Dabei sollen sowohl die theoretischen Hintergründe beleuchtet, als auch Beispiele implementiert werden.

Die Vortragsthemen stammen aus Richard Birds "Pearls of Functional Algorithm Design". Zu Beginn des Seminars wird es eine kurze Einführung in die (im Buch verwendete) Programmiersprache Haskell geben.

1. Making a century (Kap. 6)
2. Building a tree with minimum height (Kap. 7)    
   
3. Removing duplicates (Kap. 10)
4. Ranking suffixes (Kap. 12)
5. The Burrows-Wheeler transform (Kap. 13)         
   
6. The Boyer-Moore algorithm (Kap. 16) (inkl. All the common prefixes, Kap. 15)
7. The Knuth-Morris-Pratt algorithm (Kap. 17)
8. Planning solves the Rush Hour problem (Kap. 18)
9. The Countdown problem (Kap. 20)
10. Hylomorphisms and nexuses (Kap. 21)
11. Inside the convex hull (Kap. 23) (inkl. Three ways of computing determinants, Kap. 22)
12. Rational arithmetic coding (Kap. 24)
13. The Schorr-Waite algorithm (Kap. 26)

Vorträge

• 21.05.                   Hannes:       Thema 5   -    The Burrows-Wheeler transform
• 28.05.  + 04.06.  Tim, Nuria:   Thema 10  -   Hylomorphisms and nexuses
• 11.06.                   Joerg:           Thema 11  -   Inside the convex hull
• 25.06.                   Moritz:           Thema 12   -  Rational arithmetic coding
• 02.07.                   Sven:             Thema  13  -  The Schorr-Waite algorithm
• 09.07.                   Margrit:          Thema 9    -   The Countdown problem

Literatur

• Richard Bird, "Pearls of Functional Algorithm Design", Cambridge University Press, 2010

Hintergrund:

• Richard Bird, Oege De Moor, "The algebra of programming", Prentice Hall, 1997
• Jeremy Gibbons, "Calculating Functional Programs"

Propaganda:

• John Hughes, "Why functional programming matters", 1984/90/91
  
• Sebastian Sylvan, "Why Haskell matters"
  

Literatur zu Haskell:

• Richard Bird, "Introduction to Functional Programming using Haskell", Prentice Hall, 1998
  
• Justin Bailey, The Haskell Cheatsheet
• Miran Lipovaca, "Learn You a Haskell for Great Good!", No Starch Press, 2011
• Kees Doets, Jan van Eijck, "The Haskell Road to Logic, Maths, and Programming", Kings College Pubn, 2004
• Bryan O'Sullivan, Don Stewart, John Goerzen, "Real World Haskell", O'Reilly Media, 2008
• Graham Hutton, "Programming in Haskell", Cambridge University Press, 2007
• Simon Thompson, "Haskell: The Craft of Functional Programming", Addison-Wesley Longman, Amsterdam, 3. Auflage, 2011

Haskell-Ressourcen:

• http://www.haskell.org
• Haskell-Wiki
• Benutzerhandbuch zum Compiler ghc
• Hackage, Cabal - Haskell-Projekte
• Hoogle
  
• Haddock, Dokumentation wichtiger Standardbibliotheken:
  
• • Prelude
  • Data.List
  • ...
    
• ...
  

• Testen mit Quickcheck

• Die Standardisierung von Haskell: "Haskell 98 Language and Libraries - The Revised Report", 2002

• Literate Programming