Oberseminarvorträge
|
|
|
|
|
Dienstag, 9. Juli 1996, 14 Uhr c.t.
(Raum C-221)
Kolmogorov-Beweise im Vergleich zu
herkömmlichen Beweismethoden
Nicola Waje
Unter der Kolmogorov-Komplexität (KC) eines Wortes versteht man den Anteil an tatsächlicher Information, die in ihm enthalten ist. Bestimmte Eigenschaften der KC machen sie attraktiv für Beweisführungen verschiedenster Art in der Komplexitätstheorie und anderen Bereichen. Dazu gehören:
- die KC eines Objekts (z.B. eines Bitstrings oder eines Wortes) hängt nicht von der Art und Weise seiner Darstellung bzw. Beschreibung ab, sondern nur von dem Objekt selbst;
- betrachtet man alle Worte einer Länge, wird mindestens eines als kolmogorov-zufällig bezeichnet, weil die in ihm enthaltene Information nicht kürzer dargestellt werden kann, als es selbst lang ist.
Anwendungen finden sich unter anderem in den Bereichen:
- Formale Sprachen
- Maschinentheorie
- Algorithmenkomplexität
- Kombinatorik etc.
Die KC wird bei diesen Beweisen entweder zusätzlich benutzt oder, bei bereits bestehenden Beweisen, der gesamte Beweis durch einen neuen ersetzt.
In dem Beitrag zum Oberseminar sollen Beweise der letzteren Sorte vorgestellt, näher erläutert und gegebenenfalls mit dem Original vergleichen werden.
Dienstag, 25. Juni 1996, 14 Uhr c.t.
(Raum C-221)
Topologie der Nebenläufigkeit
Stefan Haar
C.A. Petri hat eine Reihe von Untersuchungen durchgeführt bzw. angeregt, wie das Verhalten Elementarer Netzsysteme (ENS) auf einer höheren mathematischen Abstraktionsebene als dem Tokenspiel selbst beschrieben bzw. festgelegt werden kann. Dabei sind bisher zumeist Relationen als Grundbausteine verwendet worden:
- Binäre Ähnlichkeitsrelationen in der Concurrency-Theorie (CT) (Petri,... Stehr, Kummer) sowie in dem Entwurf einer Theorie der vollständigen Signalordnungen (COS) von Petri, die die CT durch Hinzunahme von Alternativbeziehungen verallgemeinert;
- Halbordnungen in der Theorie der Prozesse (u.a. Best/Fernàndez) und den Event Structures (Winskel)
- Zyklische Ordnungen (Genrich, ..., Stehr)
Die Rückbindung an die allgemeine Netztheorie ermöglicht Beweisführungen und Konstruktionen mittels Netzmorphismen.
- Durch topologische Eigenschaften können Quotientenbildungen charakterisiert werden, die Untereinheiten zusammenfassen (Abstraktionen).
- Konflikt- und Konfusionssituationen sind als Resultate spezieller Summenmorphismen einbezogen.
Dienstag, 18. Juni 1996,14 Uhr c.t.
(Raum C-221)
Untersuchung von Elliptischen Kurven für die
Tauglichkeit zur Hardwareakzeleration
von Kryptoverfahren
Frank Bohnsack
Die Entwicklung in der Technik hat die Herstellung von schnellen Computern ermöglicht, die Angriffe auf bestehende Kryptoverfahren (bisher als sicher anzunehmende Schlüssellänge: 512 Bit) erleichtern werden. Um weiterhin eine hohe Sicherheit gewährleisten zu können, muß die Schlüssellänge weiter erhöht werden, was einen höheren Rechenaufwand, und damit auch einen Geschwindigkeitsverlust, zur Folge hat. Eine Verdopplung der Schlüssellänge beim RSA-Verfahren bedeutet ein Faktor 4 beim Hardwareaufwand und einen Geschwindigkeitsverlust um den Faktor 2.
Mit Elliptischen Kurven, soweit es bis heute bekannt ist, wird die gleiche Sicherheit erzielt, auch wenn die Schlüssellänge geringer ist. Ein zusätzlicher Vorteil der Elliptischen Kurven ist, daß die Größe der Zahlen, die notwendig ist, um einen gewissen Sicherheitsstandard zu gewährleisten, langsamer wächst als bei Kryptoverfahren, die Intergerwerte verwenden.
Krytosysteme, die Elliptische Kurven verwenden, basieren auf einer anderen mathematischen Grundoperation. Diese ist allerdings sehr komplex, wie das mathematische Modell der Elliptischen Kurven zeigt.
Ziel der geplanten Arbeiten ist die Erstellung eines Simulationsprogramms zur Untersuchung der Eignung von Elliptischen Kurven im allgemeinen, aber auch zur Analyse des Zeit-/Platzbedarfs. Dabei sind für den Endlichen Körper Primzahlen im Bereich von 232 geplant. Das entwickelte Simulationsprogramm soll einer Hamburger Firma dazu dienen zu entscheiden, ob dieses Verfahren für Low-Security-Verfahren eingesetzt werden kann.
Dienstag, 11. Juni 1996,14 Uhr c.t.
(Raum C-221)
Agentenorientierte Programmierung mit Petrinetzen
Frank Wienberg
Agentenorientierte Programmierung wird von Y. Shoham als Nachfolgerder Objektorientierten Programmierung vorgeschlagen. Die Spezialisierung auf bestimmte Nachrichtentypen, die aus der Sprachakt-Theorie entliehen sind und die Erweiterung um "mentale Zustände" der Objekte, die damit zu "Agenten" werden, zeigt die Nähe zur KI, insbesondere zu Unterdisziplinen wie Multiagentensysteme und VKI (Verteilte KI).
Da der von Shoham vorgeschlagene Agenten-Interpreter Konzepte wie Nebenläufigkeit und Ressourcenverwaltung benötigt, bietet sich eine Darstellung als Petri-Netz an. Dafür benötigt man allerdings Ansätze, wie typische KI-Mechanismen (Wissenbasis, Resolution, Unifikation) in Petrinetzen dargestellt werden können.
Dienstag, 4. Juni 1996, 14 Uhr c.t.
(Raum C-221)
Termersetzung in Aussagenlogik
und rationalen Audrücken
Julia Maas
Ein Termersetzungssystem stellt ein spezielles Reduktionssystem dar, dessenzugrundeliegende Menge aus den Termen über einer festen Signatur besteht.Ein Termersetzungs- oder auch Regelsystem ist ein gerichtetes Gleichungssystem, das in natürlicher Weise eine Reduktionsrelation auf den Termen definiert. Es dient zum Rechnen und Schließen in gleichungsdefinierten Strukturen und betont infolgedessen eine operationale Sichtweise von Gleichungsspezifikationen.
Nach Einführung der zunächst abstrakt beschriebenen Begriffe werden Reduktionstechniken auf spezielle Termersetzungssysteme angewendet; als konkrete Beispiele dienen die Aussagenlogik, Mengenalgebra und rationale Ausdrücke. Dies geschieht im wesentlichen durch die Angabe von Regelsystemen, die im Anschluß auf bestimmte Eigenschaften wie Konfluenz und Termination hin untersucht werden. Es werden dabei Kriterien vorgestellt, die dem Nachweis dieser Eigenschaften dienen, sowie Methoden angedeutet, mit denen sich Regelsysteme gegebenfalls derart vervollständigen lassen, daß sie die geforderten Voraussetzungen erfüllen. Abschließend wird kurz auf die durch Kommutativität und Assoziativität von Operatoren entstehende Problematik eingegangen, die zum Begriff der Termersetzung modulo AC führt.
Dienstag, 21. Mai 1996, 14 Uhr c.t.
(Raum C-221)
Ungefähre Performanzmasse nebenläufiger Algorithmen
Wolfgang A. Meyenberg
Sowohl nebenläufige Algorithmen wie auch parallele Architekturen können durch gefärbte Petrinetze dargestellt werden. Durch Transformationen können beide Netze in ein Netz überführt werden, welches die Implementation des Algorithmus auf der Architektur darstellt. Für dieses Netz wird ein lokales Performanzmaß dargestellt, welches die Auslastung von Funktionseinheiten angibt und somit Hinweise für lokale Optimierungen des Algorithmus geben kann.
Dienstag, 14. Mai 1996,14 Uhr c.t.
(Raum C-221)
Entwurf gefärbter Netze mit OMT
Die Modellierung komplexer Systeme erfolgt im allgemeinen mit Hilfe einer oder mehrerer Techniken. Eine relativ entwickelte und anerkannte objektorientierte Technik ist die "Object Modelling Technique" (OMT). Sie wurde erstmals 1991 in Buchform veröffentlicht und liegt seit 1994 auch in deutscher Übersetzung vor.
Petrinetze werden benutzt, um Systeme zu beschreiben. Die Vorteile der Modellierung mit Netzen liegen u.a. in der graphischen Repräsentation der Netze, ihrer mathematischen Fundierung und den damit verbundenen Analysemethoden, ihrer Simulationsfähigkeit sowie ihrer besonderen Eignung, nebenläufige Vorgänge darzustellen.
Die "Object Modelling Technique" dagegen ist informell erklärt. Dies führt zu einer Reihe von Schwächen der Technik, die durch die Verwendung von Netzen als Notation überwunden werden könnten.
Der Vortrag basiert auf einer Diplomarbeit, in der untersucht wird, ob und gegebenenfalls wie mit Hilfe der "Object Modelling Technique" Modelle entworfen und diese in gefärbte Petrinetze transformiert werden können.
Dienstag, 7.Mai.1996, 14 Uhr c.t.
(Raum C-221)
Darstellung von objektorientierten
Konzepten mit Petrinetzen
Christoph Maier
Objektorientierte Programmierung zeichnet sich durch das Prinzip der Kapselung und die Möglichkeit zur Wiederverwendung bestehender Software aus. Ein Objekt kapselt wie ein abstrakter Datentyp seine Variablen und die Funktionen, die darauf arbeiten. Die Wiederverwendung erfolgt durch die Komposition von Objekten und durch Vererbung zwischen Objektklassen.
Um diese Vorteile bei dem Entwurf von Netzen nutzen zu können, wird ein Ansatz vorgestellt, der die zentralen Konzepte der Objektorientierung auf Netze abbildet. Dabei werden keine speziellen Beschriftungssprachen verwendet, sondern gefärbte Petrinetze benutzt, erweitert um Test- und Inhibitorkanten. Im einzelnen werden folgende Konzepte auf Netze abgebildet: Objekt, Klasse, Nachricht, Beziehung und Vererbung.
Das statische Modell der Objektorientierten Analyse kann so auf ein Netz abgebildet und damit operationalisiert werden. Dadurch eröffnen sich auch in dieser Richtung Vorteile. Modelle der Objektorientierten Analyse können simuliert und mit Methoden der Petrinetz-Theorie analysiert werden.
Dienstag, 30.April.1996, 14 Uhr c.t.
(Raum C-221)
Prototyping mit Petrinetzen
Markus Meyer
Beim Entwurf komplexer Informatiksysteme stößt man mit herkömmlichen Phasenmodellen schnell an Grenzen, da sie mit ihren Phasen nur einen Ausschnitt der Realität erfassen. Als Antwort auf die Schwächen der herkömmlichen Modelle wurde das Software Prototyping entwickelt.
Beim Prototyping werden Rückkoppelungsprozesse explizit vorgesehen und in diese Prozesse auch die Gruppe der Benutzer bewußt einbezogen, die implizit als Experten des Fachgebietes erachtet werden. Hieran knüpft die entwickelte Architektur an.
Die Verständlichkeit der entworfenen Prototypen wird für Systemingenieure, Anwender und Benutzer erhöht. Gleichzeitig werden Systemingenieure durch diese Architektur beim Entwurf und der Dokumentation eines zu entwerfenden Prototyps unterstützt.
Dienstag, 23. April 1996, 14 Uhr c.t.
(Raum C-221)
Structural equivalence of P/T nets
Marc Voorhoeve
Universität Eindhoven
An equivalence relation, called structural bisimilarity, is given for labeled Place-Transition nets. In contrast to behavioral bisimilarity of nets, this equivalence only depends upon the structure of the nets considered, that is, their places and transitions and the way these are connected. It does not involve any conversion to transition systems. Algorithms are given for reducing a net to its normal form and deciding whether two given nets are bisimilar. A behavioral characterization of structural net bisimilarity is given. A net induces an ordered process space by considering markings as states, steps as state transitions and bag inclusion as the partial ordering. Structural bisimilarity of nets is equivalent to order-preserving (noninterleaving) bisimilarity of their induced process spaces.
Dienstag, 16. April 1996, 14 Uhr c.t.
(Raum C-221)
Petri Net Synthesis from High Level Model:
Principles and Implementation
Fabrice Kordon
Université Paris 6
Lab. MASI
In diesem Vortrag stellt Hr. Kordon seinen Beitrag zu dem geplanten MATCH - Buch vor (Veröffentlichung im Rahmen des EG-Projekts "Modelling and Analysis of Time Constrained and Hierarchical Systems" (MATCH)).
Letzte Änderung: 17:40 19.05.2011 Impressum