Vorlesung Algorithmik 2: Grundlagen der funktionalen und logischen Programmierung (G. Görz)

Zeit und Ort: Di. 8:15-9:45, H7 (Sommersemester 2007)

Für die Übungen zu Algorithmik 2 gibt es eine eigene Seite

Ergebnisse der Prüfung Algorithmik 2 am 14.03.2008 gibt es für die Informatiker hier und für die Wirtschaftsinformatiker hier. Bitte beachten Sie den Termin für die Klausureinsicht am 19.03.2008!

Diese Vorlesung war eine Pflichtveranstaltung im Diplomstudiengang Informatik und wird nach der Umstellung zum Bachelorsystem ab WS 2007 mit diesem Inhalt nicht mehr angeboten!

Prüfungen werden für Wiederholer (Informatiker, Wirtschaftsinformatiker, Computerlinguisten) noch bis zum Sommer 2009 durchgeführt.

Fragen zu Inhalt und Organisation der Vorlesung und Übungen bitte an:

: Bernhard Schiemann, 852-8984; schiemann@informatik.uni-erlangen.de; Sprechstunde: n.V., Raum 03.007, Haberstr. 2

Lehrbücher zur Vorlesung

Scheme: Abelson/Sussman: Structure and Interpretation of Computer Programs.
Cambridge, Mass.: MIT Press, 2nd edition, 1996
Dort findet man den kompletten Text im HTML-Format, weitere Übungsaufgaben,
den Programmcode aus dem Buch, etc. Von Letzteren gibt es auch eine lokale Kopie:; Code mit Aufgaben und Lösungen aus diesem Buch.; Springer/Friedman: Scheme and the Art of Programming
Cambridge, MA etc.: MIT Press and McGraw Hill, 1989; Friedman et al.: Essentials of Programming Languages
Cambridge, MA etc: MIT Press, 2001
Eine anspruchsvolle Einführung in fundamentale Konzepte von Programmiersprachen auf der Basis von Scheme; der Programmcode aus dem Buch ist on-line verfügbar.; Felleisen et al.: How to Design Programs
Cambridge, MA etc: MIT Press, 2003
Eine sehr elementare Einführung in die Programmierung mit Scheme; der komplette Text des Buchs und viele Materialien sind on-line verfügbar.
Prolog: Nilsson/Maluszynski: Logic, Programming and Prolog.
Hoboken, NJ: Wiley & Sons, 2nd edition, 1996
(als pdf-Datei verfügbar!)
Dort ist auch eine Druckfehlerliste zu finden.; Pereira/Shieber: Prolog and Natural Language Analysis.
Stanford, CA: CSLI, Lecture Notes No. 10, 1987
(Millenium reedition von Microtone Publishing, Brookline, MA, 2002, on-line als pdf-Datei verfügbar!); Blackburn/Bos/Striegnitz: Learn Prolog Now!
(Online-Kurs)
Buchausgabe in der Reihe: Texts in Computing, Vol. 7. London: College Publications, 2006
Scheme und Prolog im Vergleich: Beckstein et al.: Grundlagen / Fortgeschrittene KI-Programmierung. [pdf] [ps.gz] Kap. 9 aus:
G. Görz (Hg.): Einführung in die Künstliche Intelligenz. Bonn: Addison-Wesley, 1993/1995.
Handapparat zur Vorlesung mit weiterführender Literatur: Nr. 24 in der Gruppenbibliothek Informatik

Folien zur Vorlesung

Einleitung: Übersicht -- Programmierstile und Programmiersprachen -- Scheme -- Prolog
(Folien 4auf1 [pdf])
Prozedurale Abstraktion 1: Top-Down-Entwicklung von Prozeduren Abstraktion -- Prozeduren -- Substitutionsmodell -- Vergleichsoperatoren -- Bedingte Ausdrücke
(Folien 4auf1 [pdf])
Prozedurale Abstraktion 2: Beispiel Newton-Verfahren -- Prozeduren und erzeugte Prozesse: Lineare Rekursion, Endrekursion, Baumrekursion (Rekursionstypen) -- Bemerkung zu Komplexitätsmassen: Beispiele Exponentiation, Primzahltest
(Folien 4auf1 [pdf])
Ergänzung: Ackermann-Funktion
(Folien 4auf1 [pdf])
Prozeduren als Objekte: Prozeduren höherer Ordnung
(Folien 4auf1 [pdf])
Datenabstraktion 1: Datentypen -- Hierarchische Datenstrukturen -- Paare und Listen
(Folien 4auf1 [pdf])
Datenabstraktion 2: Bäume und Formelmanipulation -- Implementation von Mengen
(Folien 4auf1 [pdf])
Ergänzung: Abstrakte Datentypen und Algebraische Spezifikation
(Folien 4auf1 [pdf])
Datenabstraktion 3: Datenabstraktion höherer Ordnung -- Generische Operationen -- Beispiel: Computeralgebra
(Folien 4auf1 [pdf])
Objekte mit innerem Zustand 1: Zustandsvariablen und das Umgebungsmodell der Auswertung -- Modifikation von Datenstrukturen -- Algorithmen auf Zeichenketten
(Folien 4auf1, Teil 1 [pdf])
(Folien 4auf1, Teil 2 [String-Algorithmen] [pdf])
Objekte mit innerem Zustand 2: Constraints -- Datenstrom-orientierte Verarbeitung und Generatoren
(Folien 4auf1 [pdf])
Kontrollabstraktion [ÜBERSPRUNGEN!]: Kontexte und Fortsetzungen (Continuations) -- Coroutinen
(Folien 4auf1 [pdf])
Grundlagen der logischen Programmierung 1: Anforderungen an ``Computational Logics'' -- Terme, Unifikation und Resolution -- Hornklauseln -- ``Pure Prolog'' -- Deklarative und Prozedurale Semantik
(Folien 4auf1 [pdf])
Grundlagen der logischen Programmierung 2: Terme und Unifikation -- Funktionen -- Rekursion und Iteration -- Listen -- Nichtlogische Erweiterungen, Cut, Negation
(Folien 4auf1 [pdf])
Ergänzende Themen: Datenabstraktion -- Suche -- Metaprogrammierung -- Generatoren und Ströme
siehe "Scheme und Prolog im Vergleich" [pdf]
Syntaktische Abstraktion [ÜBERSPRUNGEN!]: Macros in Scheme -- Objektorientierte Spracherweiterungen
(Folien 4auf1 [pdf])