Medizinische Universität zu Lübeck
|
Institut für
Theoretische Informatik
Medizinische Universität zu Lübeck |
Lübecker Hochschultag
Software Demonstrationen11. November 1999Stand Nr. 28
GRAPHitty Graphen und Algorithmen zum 'Anfassen'
Präsentationen
Ein Streifzug durch die Grundlagen der Informatik
Informationen
GRAPHitty
GRAPHitty ist ein Tool zur Visualisierung von Graphen und Algorithmen. Es
kann zum einen in der Forschung bei der Entwicklung neuer Algorithmen,
zum anderen in der Lehre zum Verständnis und zur Animation bekannter
Algorithmen dienen. Das Tool wurde im Rahmen einer Semesterarbeit und
einem darauf aufbauenden Software Projekt von Studenten und
wissenschaftlichen Mitarbeitern entwickelt. Vorkompilierte Versionen
sind über die GRAPHitty Homepagehttp://www.tcs.mu-luebeck.de/Software/GRAPHitty/2.0
für die Plattformen Linux und Win95/98/NT kostenlos zu erhalten.
Algorithmisches Lernen
Patternsprachen werden generiert durch endliche Zeichenketten, die man als Pattern bezeichnet.
Ein Pattern besteht aus Buchstaben über einem endlichen Alphabet A wie beispielsweise {a,b,c,d,e,f,g},
sowie einer Patternvariablen x . Das Patternbeispielsweise erzeugt alle Worte w, die sich ergeben, wenn man x durch einep = a b x b x x c x
beliebige endliche Zeichenkette über dem Aphabet A ersetzt.
So erzeugt die Ersetzung von x durch de das WortPatternsprachen haben vielfältige Anwendungen, so lassen sich mit diesem Modellw = a b de b de de c de.
beispielsweise bestimmte Gesetzmässigkeiten in der Molekularbiologie beschreiben.Ein Lern-Algorithmus zum Erlernen einer unbekannten Patternsprache erhält eine Folge von
Beispielen W1, W2, W3, ......
Nach Erhalt eines neuen Beispiels Wi berechnet der Algorithmus als Hypothese Hi ein Pattern, durch das die bislang gesehene Beispiele generiert worden sein könnten.
Ziel ist es, mit möglichst wenigen Beispielen und möglichst geringem Rechenaufwand das korrekte Pattern zu finden.Das hier präsentierte System folgt einem neu entwickelten Ansatz, um die Lernaufgabe möglichst effizient im average case zu lösen. Zu jedem Zeitpunkt merkt sich der Algorithmus das gemeinsame Präfix und Suffix aller Beispiele sowie ein ausgewähltes typisches Beispiel.
Hypothesen werden berechnet durch Fakorisierung der Beispiele bezüglich geeigneter
Symmetrien und eines Kompatibilitätstests zwischen Paaren von Faktorisierungen.WEB Animation
Der Algorithmus kann entweder mit einer selbstgewählten Folge von Beispielen
getestet werden oder nach Auswahl eines Patterns mit einer Folge von Beispielen,
die zufällig erzeugt werden gemäß einer gewählten Wahrscheinlichkeitsverteilung.
Interaktiv können die einzelnen Lernschritte des Algorithmus beobachtet werden.
Sobald der Algorithmus das Pattern gefunden hat, wird dies entsprechend signalisiert.Das System kann unter http://www.tcs.mu-luebeck.de/Software/PatLearn/Learn1/Learn1.html
getestet werden.
2-Keller-Automaten
Jegliche Informationsverarbeitung beinhaltet, daß Daten eingelesen und
weiterverarbeitet werden. Ob nun Programme vom Computer übersetzt und
ausgeführt werden, oder digitale Film, Musik und Bilddaten angezeigt oder
weiterverarbeitet werden, stets müssen die Daten in einem Format vorliegen,
auf das unsere Programme aufsetzen können. Diese minimalen Voraussetzungen
sind rein syntaktischer Natur, etwa: jede Zeile muss mit 0 beginnen, oder in
jeder dritten Zeile müssen die Anfangskürzel des Herstellers stehen, oder
zwischen "if" und "then" muss eine Bedingung stehen.
Mit anderen Worten: es ist in der Regel notwendig, daß die Daten bestimmten syntaktischenAnforderungen genügen.
Je nachdem wie komplex die Syntax dabei aufgebaut ist, benötigen wir dazu Rechenkapazität. In unserer Forschungsarbeit suchen wir hier nach
mathematisch präzisen Syntaxbeschreibungen und Programmen,
die die Syntax testen. Dazu haben wir hier ein Programm entwickelt, das
bei Eingabe einer solchen Syntaxbeschreibung einen Automaten ausgibt ---
einen Zweikellerautomaten.Kellerautomat heißt dabei ein Automat, der ein Speichermedium besitzt, in dem
das zuletzt gespeicherte Datum zuerst wieder gelesen wird. Selbstverständlich
hat ein Zweikellerautomat zwei solche Speichermöglichkeiten. In unserem Modell
verlangen wir, daß die Eingabe in einem der beiden Kellerspeicher steht und
dass die Grösse der gespeicherten Daten insgesamt in einem gewissen Sinn mit
jedem Rechenschritt abnimmt. Dadurch wird unter anderem eine hohe Effizienz
(lineares Zeitverhalten) garantiert.Dieser Zweikellerautomat liegt jetzt als Demonstrationsprogramm vor.
Man kann eine Syntaxbeschreibung eingeben, daraus wird automatisch ein
Zweikellerautomat erzeugt. Dieser testet alle Eingaben auf Korrektheit
bezüglich der beschriebenen Syntax. Der Automat kann dabei in seiner
Arbeitsweise beobachtet werden. So steht in dem einen Keller die Eingabe und
während der Bearbeitung werden die Symbole von einen in den anderen Keller
kopiert und dabei verändert. Sind beide Keller schliesslich leer, war die
Eingabe syntaktisch korrekt.Das System kann unter: Zweikellerautomat und TPDAsim getestet werden.
Datenkompression
Wir präsentieren einige der in der Praxis am häufigsten eingesetzten Verfahren
zur digitalen Datenkompression:
sowohl verlustfreie als auch verlustbehaftete allgemeine Komprimierungsmethoden sowie
spezifische Algorithmen für Text-, Fax-, Bild-, Video- und Audiokomprimierung.Vorgestellt werden unter anderem die Verfahren:
Lempell-Ziv, JPEG und MPEG .
Speicherhierarchien und Datenkonsistenz
in ParallelrechnernParallelrechner erschliessen aufgrund ihrer hohen Leistungsfähigkeit
neue Anwendungsbereiche. Voraussetzung für die Lösung eines rechenintensiven
Problems ist seine Parallelisierung, d.h. die Aufteilung in Teilaufgaben,
so daß alle vorhandenen Prozessoren simultan beschäftigt werden können.
Damit bei einer Parallelisierung keine gravierenden Effizienzverluste
durch Synchronisation und Datenaustausch zwischen den Prozessoren
auftreten, müssen diese Aufgaben optimiert werden, wobei die
Architektureigenschaften des Parallelrechners detaillierter berücksichtigt
werden müssen.Das Institut beschäftigt sich mit der Modellierung speichergekoppelter
Parallelrechner (global shared memory) und untersucht unter anderem
die Speicherhierachien dieser Architekturen.
Neue Techniken wie gelockerte Datenkonsistenz, Cachingverfahren, Prefetching
zur Beschleunigung des Datenzugriffs werden analysiert.Diese Forschungsarbeiten werden an einigen Beispielen illustriert.
Kombinatorische Optimierung
An einigen praktischen Aufgabenstellungen wird die
kombinatorische Explosion bei der Lösung von
Optimierungsproblemen aufgezeigt, die verhindert, daß ein Optimum durch
einfache Suchstrategien in akzeptabler Zeit gefunden werden kann: NP-Vollständigkeit.
Das Institut untersucht alternative Lösungsansätze.
Visuelle Kryptologie
Eine informationstheoretisch absolut sichere Methode zur vertraulichen Übertragung von Daten - etwa per FAX - wird präsentiert. Es basiert auf Pixelbasis und nutztDiskriminanzfähigkeiten des menschlichen Auges aus.
Sortier-Netzwerke
Sortieren ist eins der wichtigsten Basisprobleme in der Datenverarbeitung.
Wir illustrieren neuartige Designs für average-case effiziente Netzwerke.
Erstellt 02. November 1999, Claudia Mamat
