Grundlagen der funktionsorientierten Programmierung mit SCHEME

Kommunikation mit Scheme

1. Einführung in die Kommunikation mit Scheme

   • Syntax und Semantik
   • Sonderform define

2. Prozeduren

   • Prozedurabstraktionen
   • Unbenannte Prozeduren

3. Datentypen

   • Zahlen, Zeichen, Zeichenketten, Wahrheitswerte
   • Symbole

Einfache Daten- und Programmstrukturen

1. Listen

   • Listen und Paare

2. Bedingte Ausdrücke

   • Grundform
   • Alternative
   • Fallauswahl

3. Rekursionen

   • Selbstähnlichkeiten
   • Rekursionen als universelles Konzept zur Problemlösung
   • Zum Weiterarbeiten: Fraktale

4. Echte und endständige Rekursionen

   • Quadratzahlen
   • Turm von Hanoi

5. Komplexe Anwendungen: Numerische Listen

   • Zum Weiterarbeiten:
     • Vergleichsoperatoren
     • Minimum-Sortieren

Höhere Daten- und Programmstrukturen

1. Mehrfachrekursionen

   • Zum Weiterarbeiten: Superminimum

2. Prozeduren höherer Ordnung (I)

   • Prozeduren nehmen Prozeduren entgegen
   • Zum Weiterarbeiten: Primzahlfilter

3. Prozeduren höherer Ordnung (II)

   • Prozeduren geben Prozeduren zurück
   • Zum Weiterarbeiten: Kurvendiskussion

4. Streams

   • Zum Weiterarbeiten: Von Fröschen und Tischlampen

5. Projekt Zahlenfolgen

   • Arithmetische, geometrische sowie weitere spezielle Zahlenfolgen und ihre Grenzwerte
   • ausgewählte Schülerlösungen

Theoretische Grundlagen und Symbolverarbeitung

1. Der Lambda-Kalkül

   • Definition von λ-Ausdrücken
   • Rechenregeln für λ-Ausdrücke
   • Zum Weiterarbeiten: Currying und Y-combinator

2. Projekt CAS

   • Symbolische Differenzieren und Vereinfachen von Termen

Algorithmen und ihre Effizienz

1. Der Algorithmusbegriff

   • Der Euklidische Algorithmus
   • Das Sieb des Eratosthenes
   • Zum Weiterarbeiten:
     • Lösen quadratischer Gleichungen
     • Das Heron-Verfahren
     • Das NIM-Spiel
     • Der Morsecode (zum Vergleich: Morsecode als Java-Programm)

2. Sequenzielle Suche

   • Zufallszahlen

3. Binäre Suche

   • Raten einer Zahl
   • Zum Weiterarbeiten: Extremwertsuche nach dem Verfahren des Goldenen Schnitts

4. Zeitaufwand und asymptotische Ordnung

   • \mathcal{O}-Notation

5. MinSort

   • Theoretische und empirische Aufwandsbetrachtungen

6. QuickSort

   • Empirische Aufwandsbetrachtungen
   • Teile-und-herrsche-Algorithmen
   • Zum Weiterarbeiten: MergeSort

7. Grenzen beim Problemlösen

   • Algorithmisch und praktisch unlösbare Probleme
   • P-Probleme und NP-Probleme

8. Ausgewählte Algorithmen der Kryptologie

   • Das Cäsar-Verfahren
   • Das Vigenère-Verfahren
   • Das RSA-Verfahren

Literatur

• [1] H. Abelson, G. J. Sussman: Struktur und Interpretation von Computerprogrammen - Eine Informatik-Einführung, Springer-Verlag Berlin Heidelberg, 2001
• [2] L. Engelmann (Herausgeber): Duden - Informatik, Lehrbuch S II, Duden Paetec GmbH, Berlin 2006
• [3] R. H. Güting: Datenstrukturen und Algorithmen, B. G. Teubner Verlag, Stuttgart 1992
• [4] C. Landfried: Entwicklung und Erprobung lehrplangerechter Unterrichtsmaterialien für den Informatik-Unterricht in der Sekundarstufe II, Diplomarbeit, Görlitz 2004
• [5] R. Sedgewick: Algorithmen, Addison-Wesley (Deutschland) GmbH, 1998
• [6] Chr. Wagenknecht: Algorithmen und Komplexität, Fachbuchverlag Leipzig im Carl Hanser Verlag, München Wien 2003
• [7] Chr. Wagenknecht: Programmierparadigmen - Eine Einführung auf der Grundlage mit Scheme, B. G. Teubner Verlag, Wiesbaden 2004
• [8] Chr. Wagenknecht: Rekursionen - Ein didaktischer Zugang mit Funktionen, Dümmler Verlag, Bonn 1994
• [9] J. Ziegenbalg: Algorithmen - Von Hammurapi bis Gödel, Spektrum Akademischer Verlag GmbH, Heidelberg Berlin Oxford 1996