Uni Bonn, Inst. für Informatik III, Vorlesung `Fortgeschrittene Algorithmen und Datenstrukturen in Haskell' (SS 98)

Institut für Informatik III
Universität Bonn
Datenbanken * Informationssysteme * Softwaretechnologie * Mustererkennung * Bildverarbeitung * Künstliche Intelligenz * Robotik

Fortgeschrittene
Algorithmen und Datenstrukturen
in Haskell
(Sommersemester 1998)

Dr. Ralf Hinze

INDEX: Motto Vorlesung Vorlesungsfolien Vorlesungsskript Programme Literatur Links

Motto

Some people think that mathematics is a serious business that must always be cold and dry; but we think mathematics is fun, and we aren't ashamed to admit the fact.
Ronald L. Graham, Donald E. Knuth, Oren Patashnik
Concrete Mathematics

I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don't think we are. I think we're responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don't become missionaries. Don't feel as if you're Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don't feel as if the key to successful computing is only in your hands. What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.
Alan J. Perlis

Inhalt der Vorlesung

Es gibt Algorithmen, die sind schön, aber nicht effizient und es gibt Programme, die sind effizient, aber nicht schön. Kommt beides zusammen, macht Informatik Spaß. In der Vorlesung stelle ich Algorithmen und Datenstrukturen vor, die Spaß machen. Die Palette der ins Auge gefaßten Themen ist reichhaltig:

Wir untersuchen verschiedene Datenstrukturen zur Repräsentation von Sequenzen, Prioritätswarteschlangen, Mengen und endlichen Abbildungen. Alle vorgestellten Datenstrukturen sind persistent, d.h. nach einem Update kann auch die "alte" Kopie weiterverarbeitet werden.
Wir werden sehen, was Zahlensysteme mit Datenstrukturen zu tun haben und wie man n+1 in konstanter Zeit berechnet kann.
Wir schauen uns die Technik des "data structural bootstrapping" an, und werden klären, was es bringt, wenn eine Datenstruktur sich selbst enthält.
Wir stellen die Frage "Was macht einen guten Sortieralgorithmus aus?" und versuchen die schwierigere Frage "Welcher Sortieralgorithmus ist für die Praxis zu empfehlen?" zu beantworten.

Zu folgenden Themen hat leider die Zeit nicht mehr gereicht ;-).

Wir machen eine Wissenschaft aus der Frage, wie man Daten textuell aufbereitet ("pretty printing") und wie man Texte formatiert.
Wir behandeln verschiedende Verfahren zur Datenkompression.
Wir beantworten die Frage, wie man nach Namen sucht, deren Schreibweise man vergessen hat ("approximative Suche").
Wir sehen uns an, was Digitalrechner im Innersten zusammenhält (Schaltkreise für Addition und Multiplikation).

Für die Notation der Algorithmen verwenden wir nicht wie sonst üblich Pseudo-Code, sondern die funktionale Programmiersprache Haskell, denn: die vorgestellten Programme auszuprobieren, macht auch Spaß ;-).