Grundlagen der funktionsorientierten Programmierung mit SCHEME

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Kommunikation mit Scheme 1.1 Einführung in die Kommunikation mit Scheme 1.2 Prozeduren 1.3 Datentypen 2 Einfache Daten- und Programmstrukturen 2.1 Listen 2.2 Komplexe Anwendungen: Prozeduren mit Zeichenketten und Listen 2.3 Bedingte Ausdrücke 2.4 Rekursionen 2.5 Echte und endständige Rekursionen 2.6 Komplexe Anwendungen: Numerische Listen 2.7 Komplexe Anwendungen: Von musizierenden Chinesen und Schüttelwörtern 3 Höhere Daten- und Programmstrukturen 3.1 Mehrfachrekursionen 3.2 Prozeduren höherer Ordnung (I) 3.3 Prozeduren höherer Ordnung (II) 3.4 Streams 3.5 Projekt Zahlenfolgen 4 Theoretische Grundlagen und Symbolverarbeitung 4.1 Der Lambda-Kalkül 4.2 Projekt CAS 5 Algorithmen und ihre Effizienz 5.1 Der Algorithmusbegriff 5.2 Sequenzielle Suche 5.3 Binäre Suche 5.4 Zeitaufwand und asymptotische Ordnung 5.5 MinSort 5.6 QuickSort 5.7 Grenzen beim Problemlösen 5.8 Ausgewählte Algorithmen der Kryptologie 6 Literatur 7 Impressum

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. Komplexe Anwendungen: Prozeduren mit Zeichenketten und Listen

   • Selektoren für Zeichenketten
   • Benutzernamen und Passwörter
   • Kfz-Kennzeichen
   • Zum Weiterarbeiten: Allgemeine zufällige Kfz-Kennzeichen

3. Bedingte Ausdrücke

   • Grundform
   • Alternative
   • Fallauswahl

4. Rekursionen

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

5. Echte und endständige Rekursionen

   • Sprachelement let
   • Quadratzahlen
   • Glücksrad
   • Turm von Hanoi
   • Zum Weiterarbeiten: Der zerbrochene Stab

6. Komplexe Anwendungen: Numerische Listen

   • Zum Weiterarbeiten:
     • Vergleichsoperatoren
     • Minimum-Sortieren

7. Komplexe Anwendungen: Von musizierenden Chinesen und Schüttelwörtern

   • Drei Chinesen mit dem Kontrabass...
   • Schüttelwörter
   • Zum Weiterarbeiten:
     • Palindrom-Sätze
     • Zickzack-Verschlüsselung

Höhere Daten- und Programmstrukturen

1. Mehrfachrekursionen

   • Die Fibonaccizahlen
   • 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

   • Verzögerte Evaluation
   • Zum Weiterarbeiten: Von Fröschen und Tischlampen

5. Projekt Zahlenfolgen

   • Arithmetische, geometrische sowie weitere spezielle Zahlenfolgen und ihre Grenzwerte

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 Newton-Verfahren
     • Das Heron-Verfahren
     • Primfaktorzerlegung
     • π-Bestimmung mit der Monte-Carlo-Methode
     • Lotto 6 aus 49
     • Paritätsprüfung eines Bitmusters
     • Die Punktladung im inhomogenen elektrischen Feld
     • Das NIM-Spiel
     • Der Morsecode (zum Vergleich: Der Morsecode als Java-Programm)

2. Sequenzielle Suche

   • Zufallszahlen
   • Zum Weiterarbeiten: Würfeln mit mehreren Würfeln

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
   • Zum Weiterarbeiten: GnomeSort

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

Impressum

Neben den Programmierumgebungen DrScheme / DrRacket bildet das vorliegende Unterrichtsmaterial seit 2008 die Arbeitsgrundlage des Informatik-Grundkurses der Jahrgangsstufe 11 am Geschwister-Scholl-Gymnasium Löbau.
Es wurde komplett auf den JavaScript-basierten Interpreter SchemeJS umgestellt und sollte uneingeschränkt in allen auf der Startseite angegebenen Web-Bowsern lauffähig sein.
Bei Problemen, Hinweisen oder Kritiken ist der Kontakt zum Autor sehr erwünscht:

Veit Berger
Geschwister-Scholl-Gymnasium
Pestalozzistraße 21
02708 Löbau
Email: bergervei@gsg-loebau.lernsax.de