Programme zu Sortiernetzen

Syntax: Ein Netz wird beschrieben durch eine Zeichenkette wie

[1,2][3,4][1,3][2,4][2,3] -- der einfache 4-Sortierer

Konvention für Kommentare: alles außerhalb eckiger Klammern wird ignoriert. Siehe Beispiele: Odd-Even-Sort für 8 Elemente, Odd-Even-Sort für 16 Elemente

Aufgaben (Literatur: Knuth: Aort of COmputer Programming, Band 3, Abschn. 5. 3. 4)

(?) Eine Netzbeschreibung lesen und ein dazugehörendes Standard-Netzwerk ausgeben. (Standard: alle Komparatoren zeigen nach oben.) (Das ist Aufgabe 16 in Knuth.)
(?) Eine Netzbeschreibung und eine Eingabe-Belegung lesen und davon ein schönes Bild malen (als PostScript-File).
(Glück/Adams) Eine Netzbeschreibung lesen und mit 0-1-Prinzip testen, ob es wirklich alle Eingaben sortiert. Falls nein, eine Gegenbeispiel ausgeben. Aufgabe 34 in Knuth lösen.
(?) Argument: n, Ausgabe: Beschreibung eines bitonischen Sortiernetzes für n Eingänge.
(?) Argument: n, Ausgabe: Beschreibung eines Odd-Even-Sortiernetzes für n Eingänge.
Hier sehen sie ein schnell gehacktes Haskell-Programm dafür. Benutzen Sie das als Grundlage.
(?) Aufgabe 48 aus Knuth implementieren (Parameter m und n variierbar).
(?) Eine Netzbeschreibung lesen und daraus durch Anlegen von minus oder plus Unendlich an einen Eingang ein kleineres Netz bauen (und ausgeben).
(?) Effiziente Netze für > 8 Eingaben finden. (Würfeln oder Nachdenken und obige Programme benutzen.)

Falls Sie eine Teilaufgabe bearbeiten wollen, bitte Mail an mich, und ich trage Sie hier ein. Falls gewünscht auch mit email-Adresse, da könne Sie sich untereinander synchronisieren.

Zur Implementierung: Bitte schön modular, und alles sollte auch als reine Kommandozeilenversion laufen (also keine Abhängikeiten von systemspezifischen Grafikroutinen!).

Ich würde ja am liebsten sagen, alles in Haskell, und dann einen Abstrakten Datentyp "Netz" festlegen, aber ... bitte die Programme (egal, in welcher Sprache Sie programmieren) so organisieren, daß sie Beschreibungen von stdin lesen, nach stdout schicken, so daß das alles mit Shell-Skripten kombinier- und steuerbar ist.

http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de