Neuronale Netze und Fuzzy-Systeme
Softwarepraktika Wintersemester 2000/2001
Neuronale Netze und Fuzzy-Systeme
Softwarepraktika Wintersemester 2000/2001 |
|
Alle Themen können auch mehrfach vergeben werden. Allerdings sollte dann die Programmiersprache unterschiedlich sein oder, bei Verwendung einer anderen Programmiersprache als Java, für unterschiedliche Oberflächen (MS Windows oder Unix/X11) entwickelt werden, damit nicht so leicht eine Gruppe von einer anderen abschreiben kann.
(2-4 Personen)
Ein iteriertes Funktionensystem (IFS) ist eine Menge kontrahierender affiner Abbildungen, die einen kompakten metrischen Raum auf sich selbst abbilden. (Damit wissen die Mathematiker Bescheid; alle anderen können noch etwas weiterlesen.) Iterierte Funktionensysteme können benutzt werden, um Fraktale zu zeichnen, und bilden die Grundlage für fraktale Bildkomprimierung.
Ein bekanntes Beispiel eines iterierten Funktionensystems ist Barnsley's Farnblatt:
Diese Graphik zeigt den Attraktor des Funktionensystems:
 |
 |
 | |
 |
|
 | |
 |
|
 | |
 |
|
 |
(Quelle des Bildes und der Gleichungen) |
Aufgabe des Softwarepraktikums ist es, eine graphische Oberfläche für iterierte Funktionensysteme zu programmieren, in der sich die Funktionensysteme bequem eingeben, speichern, laden, und ausführen lassen. Durch Zuordnung von Farben zu den einzelnen Funktionen sollten auch farbige Bilder erzeugt werden können. Weiter sollte es möglich sein, die Graphik mit Koordinatenachsen zu versehen und in die erzeugte Graphik hineinzuzoomen. Auch wäre es wünschenswert, wenn bestimmte nichtlineare Funktionen (speziell Abbildungen der Gaußschen Zahlenebene auf sich selbst) verwendet werden können.
Je nach Teilnehmerzahl kann die Aufgabe analog zum blinden Uhrmacher (siehe unten) erweitert werden, indem man die Parameter der Funktionen als Gene auffaßt. Dadurch ergäbe sich u.U. eine bequeme Möglichkeit, iterierte Funktionensysteme mit ansprechenden Attraktoren zu finden.
Vergabe: Bisher einmal in Java vergeben.
| zurück zum Seitenanfang | 
|
(2-3 Personen)
Jahrhundertelang haben Mathematiker immer wieder versucht, Euklids fünftes Postulat (auch bekannt als Parallelenaxiom) aus seinen anderen Postulaten und Axiomen zu beweisen, ehe Nikolai Iwanowitsch Lobatschewski und Farkas Bolyai um 1830 unabhängig voneinander zeigen konnten, daß die Verneinung des Postulats zu einem konsistenten mathematischen System führt. Die entstehende nicht-euklidische Geometrie wird auch hyperbolische Geometrie genannt. Für die ebene hyperbolische Geometrie hat Jules Henri Poincaré ein erstaunlich einfaches Modell gefunden: Das Unendliche wird mit dem Rand eines Kreises identifiziert, und Geraden sind Kreisbögen, die den Kreisrand senkrecht schneiden. Eine schöne Anschauung liefern die Kreislimit-Bilder von Maurits Cornelis Escher, wie z.B. der unten gezeigte Holzschnitt Kreislimit III aus dem Jahre 1959.
Aufgabe des Softwarepraktikums ist es, ein einfaches Zeichenprogramm für dieses Modell der ebenen hyperbolischen Geometrie zu erstellen. Es sollte mit dem zu erstellenden Programm auch möglich sein, einfache Parkettierungen der hyperbolischen Ebene zu erzeugen, die der oben gezeigten von M.C. Escher ähnlich sind.
Vergabe: Bisher noch nicht vergeben.
| zurück zum Seitenanfang |
|
(2-4 Personen)
Im Jahre 1986 veröffentlichte Richard Dawkins sein Buch "The Blind Watchmaker" (der blinde Uhrmacher), in dem er ein gleichnamiges, von ihm geschriebenes Computerprogramm beschrieb, mit dem einfache Evolutionsprozesse anschaulich gemacht werden können. Dieses Programm stützt sich auf eine Idee des Biologen Aristid Lindenmayer, der ein einfaches formales Modell zur Beschreibung des Wachstums von Pflanzen entwickelte, die sogenannten Lindenmayer-Systeme. Das Prinzip der Lindenmayer-Systeme kann an dem folgenden Beispiel leicht abgelesen werden. Man beginnt z.B. mit einem einfachen Strich, dem "Pflanzenstamm". Dann wird in jedem Zeitschritt jeder (Teil-)Strich mit zwei "Ästen" versehen (siehe untenstehende Abbildung links). Nach einigen Schritten erhält man eine Struktur, die bereits etwas an eine Pflanze erinnert.
|
 |
(Bildquelle) |
Je nach den genauen Regeln, die zum Zeichnen verwendet werden, kann man Strukturen erhalten, die Pflanzen erstaunlich ähnlich sehen, wie die beiden folgenden Beispiele zeigen:
|
|
(Bildquelle) |
Zur Veranschaulichung von Evolutionsprozessen benutzte Richard Dawkins ein einfaches Lindenmayer-System, das, wie das obige Beispiel, Strukturen aus Linienzügen zeichnet. Die Parameter (Tiefe der Rekursion, Länge der Zweige, Winkel zwischen den Zweigen etc.) dieses Systems stellte er durch 9 "Gene" dar. Das Programm arbeitet nun wie folgt: Es wird mit einem zufälligen Satz von Genen begonnen und die zugehörige Struktur gezeichnet. Außerdem werden zufällige Mutationen an den Genen vorgenommen und eine gewisse Anzahl (Dawkins verwendete ursprüglich 8) von Varianten der ursprüglichen Struktur ebenfalls gezeichnet. Aus diesen wählt der Benutzer eine aus. An den Genen dieser Variante werden wieder Mutationen vorgenommen und die sich ergebenden Varianten gezeichnet. Durch den so vom Benutzer ausgeübten "Selektionsdruck" entstehen nach einigen Generationen z.T. sehr ansprechende Strukturen. Eine Auswahl zeigt das folgende Bild aus Dawkins Buch:
Aufgabe des Softwarepraktikums ist es, ein Programm wie das Dawkinsche "Blind Watchmaker" zu schreiben, das aber nicht nur einfache Linien benutzt, sondern auch andere geometrische Formen (Kreise, Ellipsen, Vielecke) zuläßt. Außerdem sollen die Formen farblich variieren können.
Vergabe: Bisher einmal in Java und einmal in C++ vergeben.
| zurück zum Seitenanfang |
|
(3-4 Personen)
Das Soma-Puzzle ist eine Art dreidimensionales Tangram-Spiel. Beim Tangram wird bekanntlich ein Quadrat in sieben Teile zerschnitten, und das Spiel besteht darin, aus diesen Teilen andere Figuren zu legen. Analog wird beim Soma-Puzzle ein Würfel in sieben Teile zerschnitten, und das Spiel besteht darin, aus diesen Teilen andere Figuren zusammenzusetzen.
Erfunden wurde das Soma-Puzzle von Piet Hein, als er eine Vorlesung von Werner Heisenberg über Quantenmechanik hörte. Während Heisenberg über einen in Würfel eingeteilten Raum sprach, erkannte Piet Hein, daß man aus einem Satz aller unregelmäßigen Körper, die aus nicht mehr als vier Würfeln bestehen, einen größeren Würfel zusammensetzen kann. Ein Körper gilt als unregelmäßig, wenn er mindestens eine Höhlung oder innere Ecke hat. Die sieben unregelmäßigen Körper aus höchstens vier Würfeln sind daher die folgenden:
Aus diesen Körpern läßt sich ein 3x3x3 Würfel zusammensetzen. Aber auch die folgenden Figuren können aus diesen Teilen aufgebaut werden:
Aufgabe des Softwarepraktikums ist es, ein Programm zu schreiben, das herausfindet, ob (und wenn ja wie) sich eine gegebene Figur aus den sieben Soma-Teilen zusammensetzen läßt. Dazu muß insbesondere eine Oberfläche geschaffen werden, mit der sich aus Würfeln aufgebaute Figuren komfortabel eingeben lassen.
Vergabe: Bisher einmal in C/C++ vergeben.
| zurück zum Seitenanfang |
|
(2-4 Personen)
Entscheidungsbäme sind eine sehr beliebte Art von Klassifikatoren, da sie schnell aus Daten gelernt werden können und der Klassifikationvorgang auf Plausibilität geprüft werden kann. Eine kurze Einführung zu Entscheidungsbäumen gibt dieser Aufsatz.
Damit die durch einen Entscheidungsbaum gefundenen Klassifikationsregeln leicht überblickt werden können, sollte ein Entscheidungsbaum visualisiert werden. Dazu bietet es sich an, die Klassenverteilung in den Knoten des Entscheidungsbaumes durch Torten- oder Streifendiagramm darzustellen.
Als Beispiel betrachten wir einen einfachen Entscheidungsbaum für die im Bereich des maschinellen Lernens sehr bekannten Irisdaten, der in der folgenden Form von einem am Institut für Wissens- und Sprachverarbeitung der Otto-von-Guericke-Universität entwickelten Entscheidungsbaum-Lernprogramm ausgegeben wird:
(
dtree(iris_type) =
{ (petal_length|2.45)
<:{ Iris-setosa: 50 },
>:{ (petal_width|1.75)
<:{ Iris-versicolor: 49,
Iris-virginica : 5 },
>:{ Iris-versicolor: 1,
Iris-virginica : 45 }}};
(vollständige Entscheidungsbaumdatei)
Dieser Entscheidungsbaum könnte z.B. wie folgt visualisiert werden:
Jeder Kreis steht für einen Knoten des Entscheidungsbaums. Die Farben geben die Klassen an: Iris Setosa - grün, Iris Versicolor - rot, Iris Virginica - blau. Die inneren Tortendiagramme zeigen die Klassenverteilung an dem zugehörigen Knoten, die äußeren wiederholen die Klassenverteilung des Elternknotens, so daß man die Veränderung durch die Aufspaltung nach den Werten des Testattributes gut sehen kann.
Aufgabe des Softwarepraktikums ist es, ein Programm zu schreiben, das einen Entscheidungsbaum in der oben angegebenen Form einliest und wie oben angedeutet graphisch darstellt. (Statt Tortendiagrammen sollte man auch Streifendiagramme - ein schmalerer Streifen oben für die Verteilung im Elternknoten und ein breiterer für die Verteilung im Knoten selbst - wählen können.) Wenn möglich, sollte das Programm auch die Kanten beschriften oder wenigstens in einem kleinen Kasten ("Balloon-Help") die Bedingung der Kante ausgeben, wenn man mit dem Mauszeiger in die Nähe der Kante kommt. (Das oben erwähnte Entscheidungsbaum-Lernprogramm und einige Beispieldateien werden zur Verfügung gestellt.)
Vergabe: Bisher einmal in Borland Delphi vergeben.
| zurück zum Seitenanfang |
|
Trotz einer Vielzahl von Datenbankprogrammen werden Daten häufig in Form von Textdateien gespeichert. Einer der Gründe hierfür liegt darin, daß diese Dateien mit jedem Texteditor angesehen und bearbeitet werden können. Da das genaue Format jedoch nicht generell festgelegt ist, ist eine Weiterverarbeitung der Daten mit anderen Programmen oft erschwert. Programme (wie z.B. Excel, vgl. Bild) haben daher Importfunktionen, mit denen das genaue Format angegeben werden kann.
Im OttoMiner-Projekt der Arbeitsgruppe von Prof. Kruse im Institut für Wissens- und Sprachverarbeitung soll ein Data-Mining-System entwickelt werden, in dem verschiedene Data-Mining-Verfahren integriert werden. Ein sinnvolle Erweiterung dieses Systems ist eine Importfunktion für solche tabellenförmigen Textdateien.
Im Softwarepraktikum ist ein interaktiver Assistent zu entwerfen und implementieren, der es ermöglicht, die Formatierung von Daten zu bestimmen und Tabellen einzulesen. Die Bestimmung der Formatierung aus einer Datei sollte soweit möglich automatisiert werden.Vergabe: Bisher noch nicht vergeben.
| zurück zum Seitenanfang |
|