Intelligente Suchverfahren
Ein Kurs mit funktionaler Modellierung
Eine funktionale Programmiersprache
Ein Ziel des Kurses ist also die Einarbeitung in die funktionale Modellierung mit der Programmiersprache Scheme.
Sie basiert auf LISP, der ältesten, für die KI entwickelten Programmiersprache.
Hinter dem Namen LISP versteckt sich list processing language, alles ist also eine Liste und wir müssen uns daher mit vielen Klammern anfreunden.
KI
Inhaltlich geht es um einen Teilbereich der KI, die Intelligenten Suchverfahren.
Dabei geht es auch um die Frage, was Suchverfahren von direkten Lösungsverfahren unterscheidet.
Neben besonderen Möglichkeiten der Informatik, werden aber auch ihre Grenzen erkennbar und wie man dennoch zu akzeptablen Ergebnissen kommen kann.
Präsentationen
- P00-1 Funktionen.pdf
- P00 Grundlegende Schemefunktionen.pdf
- P00-a1-KI Aufgabenfolien.zip Folien für Aufgabenbeispiele
- P00-b Rekursion mit Scheme.pdf Verallgemeinerung
- P00-b1 Rekursion laenge.pdf Rekursion am Beispiel Länge einer Liste
- P00-b1-1 Stack bei laenge.pdf Veranschaulichung des Stacks dabei
- P00-b2 Rekursion anhaengen.pdf Beispiel: Anhängen an eine Liste
- P00-c Endrekursion Arbeitsweise.pdf Beispiel: Umkehren einer Liste
- Dazu zwei Projekte Endrekursion_scm_und_py.zip
Scheme erkennt Endrekursion, Python nicht! Demonstriert am Beispiel: Umkehren einer Liste - P00-c1-1 Stack bei Endrekursion.pdf Das Programm verwendet
nur die oberste Ebene auf dem Stack! - P00-d Endrekursion mit Scheme.pdf Verallgemeinerung
- P00-e Datenstruktur LinkedList.pdf
- Speziell zu Racket:
- lang racket.pdf Erläuterungen zum "Sprachenwirrwar" bei Racket
- Einsatz der einfachen Grafik.pdf
- Einfaches GUI-Beispiel.pdf
Texte
- KI-00-a Scheme Grundlagen.pdf
und Programme dazu: KI-00-a Programme.scm - KI-00-b Aufrufprotokoll_Laenge_einer_Liste.pdf
- KI-00-c Aufrufprotokoll_zu_anhaengen_normal_rekursiv.pdf
- KI-00-d Arbeitsblatt schrittweise Erarbeitung.pdf
- KI-00-e Rekursionsdemo-Fakultaet.pdf einfaches Beispiel: Fakultät
Allgemeine Projekte
- breakpoint.scm
eine hilfreiche Datei zur komfortablen Ausgabe und zum Debugging
binden Sie diese in ihre Projekte mit der Zeile (load "breakpoint.scm") ein. - laufzeit-messung.scm
eine Datei zur Messung der Laufzeit von Auswertungen
binden Sie diese in ihre Projekte mit der Zeile (load "laufzeit-messung.scm") ein. - zufall.scm Zufälliges
Beachten Sie beim Einbinden von Dateien mit load den Dateipfad.
Wenn Sie die Datei beispielsweise in einem übergeordneten Ordner abgelegt haben,
lautet der Aufruf von (beipielsweise) breakpoint.scm
entsprechend
(load "../breakpoint.scm")
Material zum Kurs
Das Material zum Kurs ist abschnittsweise, auf mehrere Seiten verteilt abgelegt.
- Startseite "Intelligente Suchverfahren"
- Material zu Scheme
- Einstieg in den Kurs
- Tiefensuche
- Breitensuche
- Kürzester Weg
- Minimales Versorgungsnetz
- Probleme
- A-Stern
- Genetische Algorithmen
Spezielle Projekte
- Aufgaben.zip zu einfachen Grundproblemen mit Listen
- P00-a1-KI Aufgabenfolien.zip Folien für die Aufgabenbeispiele
- Loesungen.zip
- Loesungen-mit-breakpoint.zip Lösungen mit den eingebauten
beiden Funktionen bkpt und break-value aus der Datei breakpoint.scm - Muster Rekursion.zip Musterprogramme für Rekursion
- Sortieren-durch-Einfuegen.zip auch das geht einfach.
Aufrufprotokoll ist eingebaut. ACHTUNG: Durch break-value geht die Endrekursion verloren! - verbinde-endrekursiv.zip Verbinden zweier vorsortierter Listen zu einer
- Projekte Vergleich-py-scm.zip Endrekursion bei Scheme und Python, sowie Funktion remove gegenüber Methodenaufruf bei Python
Literaturbeispiele
- Friedmann: Scheme and the Art of Programming
- Abelson, Sussman: Structure and Interpretation of Computer Programs
- Herbert Klaeren, Michael Sperber: Die Macht der Abstraktion
Racket Entwicklungsumgebung
Software
Die mit Python entwickelte Software zum Erstellen von Graphen finden Sie im Abschnitt zur Software.
Programmierumgebung: Racket