Jahresbericht 1995

Publikationen

Jahresbericht 1995

Humboldt-Universität zu Berlin
Institut für Informatik

3. Projektforschung

Lehr- und Forschungseinheit

Automaten- und Systemtheorie

Prof. Dr. rer. nat. habil. Peter Starke: Tel.: (030) 20 18 12 85, e-mail: starke@informatik.hu-berlin.de

Mitarbeiter:

Dr. Louchka Popova-Zeugmann
Dr. Klaus-Peter Neuendorf
Dipl.-Inf. Karsten Schmidt
Dipl.-Inf. Lutz Pogrell
Dipl.-Ing. Petra Kämpfer

Sekretariat:

Annegrete Baumann: Tel.: (030) 20 18 12 84,

Tutoren:

Mathias Müller
Jan Richling
Stephan Roch
Alexander Schneiderheinze
Ines Schwenzer

Petrinetze haben sich im letzten Jahrzehnt als wichtigstes Hilfsmittel zur Beherrschung des Entwurfs großer Systeme erwiesen. Dabei sind sowohl Fertigungssysteme als auch Informations- und Kommunikationssysteme eingeschlossen. Als Hauptvorteile der Anwendung von Petrinetzen beim System- Entwurf werden gewöhnlich ihre Anschaulichkeit und ihre Analysierbarkeit genannt.

Die Anschaulichkeit der Netz-Konzepte erleichtert den Übergang von einer verbalen Systembeschreibung bzw. Anforderungscharakteristik zu einer formalen Systemspezifikation als (eventuell zusätzlich beschriftetes) Petrinetz-Modell. Die Analysierbarkeit des Petrinetz-Modells gewährleistet seine Verifizierbarkeit, nämlich die Möglichkeit, die Erfülltheit der Spezifikation nicht nur durch Simulation des Modells zu widerlegen (d. h. Entwurfsfehler oder Widersprüche in der Spezifikation zu finden), sondern auch durch Analyse zu beweisen. Hierbei kommt die Theorie der Petrinetze zum Tragen, soweit sie in Form rechnergestützter Werkzeuge zur Analyse von Petrinetzen materialisiert vorliegt.

Das Anliegen der Lehr- und Forschungseinheit besteht darin, die Anwendungen der Netztheorie in den verschiedenen Zweigen der Volkswirtschaft dadurch zu verbreitern und zu befördern, daß Werkzeuge zur Arbeit mit Netzen, insbesondere zur Analyse, zur Verfügung gestellt werden und daß Forschungen betrieben werden, deren Resultate die Analysemöglichkeiten erweitern. Darunter fallen neben der Effektivierung bekannter Verfahren auch die Untersuchung neuer Klassen von Netz-Modellen (wie der Algebraischen Petri-Netze) und zugehöriger Analysemethoden bis zur (mindestens) versuchsweisen Implementation. Dazu gehört auch, daß die Forschungseinheit sich solcher Netzbegriffe annimmt, die in den Ingenieurwissenschaften ad hoc verwendet werden (z. B. zeitbewertete Petri-Netze), und sie theoretisch fundiert und damit einer systematischen Analyse zugänglich macht.

Projektbeschreibungen

Projekt: Verteilte Algorithmen, Spezifikationen durch Netzschemata, Analyse von Netz-Schemata

Ansprechpartner: Prof. Dr. Peter Starke

Beteiligte Mitarbeiter:

Dipl.-Inf. Karsten Schmidt
Mathias Müller
Ines Schwenzer

Projektförderung:

Deutsche Forschungsgemeinschaft im Sonderforschungsbereich 342, Teilprojekt YE1 "Werkzeuge und Methoden für die Nutzung paralleler Rechnerarchitekturen"

Zusammenarbeit:

Teilprojekt A3 des Sonderforschungsbereichs 342 der TU München

Im Rahmen dieses Projektes wird ein Werkzeug zur symbolischen Analyse von algebraisch spezifizierten Petrinetz-Schemata entwickelt. Das Werkzeug ist so konzipiert, daß es sich mit geringem Aufwand in verschiedenste Entwicklungsumgebungen integrieren läßt, aber auch eigenständig arbeiten kann. Ausgangsdaten für die Analyse können von Dateien gelesen werden oder per Editor direkt erzeugt und manipuliert werden. Die Dateieingabe erfolgt in programmiersprachenähnlicher Notation und kann leicht mit Texteditoren oder automatisch generiert werden.

Die Arbeit des Werkzeuges wird durch einen Kommandointerpreter gesteuert. Der Befehlssatz umfaßt die Erzeugung und Manipulation von Daten, die Generierung von Ausgaben auf Bildschirm und Dateien, die Definition eigener, komplexer Kommandos unter Verwendung von Strukturierungskonzepten (IF, WHILE, sowie natürlich die Aufrufe von Analysealgorithmen.

Die Kommandosprache ist leicht erweiterbar, so daß auch künftig Analyseverfahren leicht ergänzt werden können. Derzeitig werden folgende Analysemethoden unterstützt:

Die Erzeugung eines zum gegebenen algebraischen Netzmodell äquivalenten Platz-Transitions-Netzes. Damit sind alle für letztere Netzklasse verfügbaren Analysemethoden auch für algebraische Netze zugänglich.

Die Verifikation gegebener Platz- und Transitionsvektoren daraufhin, ob sie Systeminvarianten beschreiben. Invarianten gestatten einige Rückschlüsse auf Systemeigenschaften und gelten als eine der wichtigsten Analysemethoden der Petrinetz-Theorie.

Ein Nichterreichbarkeitstest mit P-Invarianten. P-Invarianten haben die Eigenschaft, daß ihr Produkt mit allen erreichbaren Systemzuständen immer denselben Wert liefert. Daher können alle Zustände, die einen anderen Wert bei der Multiplikation mit einer P-Invariante liefern als der Anfangszustand, als nicht erreichbar klassifiziert werden. Umgekehrt kann es aber passieren, daß ein Zustand nicht erreichbar ist, obwohl er denselben Wert bei Multiplikation mit einer P-Invariante hat wie der Anfangszustand.

Gegenwärtig wird an der Implementation parametrisierter Erreichbarkeitsanalyse sowie an der Berechnung von Invarianten gearbeitet. Die wesentlichen theoretischen Grundlagen für diese Methoden stehen dafür zur Verfügung (siehe Veröffentlichungen). An der Implementation beteiligen sich zwei studentische Hilfskräfte.

Projekt: Eine petrinetz-basierte Entwicklungs- und Programmierumgebung

Ansprechpartner: Prof. Dr. Peter Starke

Beteiligte Mitarbeiter:

Dipl.-Inf. Lutz Pogrell
Alexander Schneiderheinze

Projektförderung:

Deutsche Forschungsgemeinschaft

Zusammenarbeit:

Universität Hildesheim (E. Best) und
Universität Oldenburg (H. Fleischhack).

PEP, petrinetz-gestützte Entwicklung und Programmierung, ist ein Programmsystem, das zwei der heute meistgenutzten Konzepte in der verteilten Programmierung vereint, Prozeßalgebra und Petrinetze. Die flexible parallele Programmiersprache B (PN) 2 (Basic Petri Net Programming Notation) ist eine der Grundlagen des Projektes. Im Rahmen unseres Teilprojektes wird die Integration des Petrinetz- Analysewerkzeuges INA (Integrated Net Analyser) in das PEP-Projekt sowie die Erweiterung der Analysekomponente vorgenommen.

Programmierwerkzeug inatcl

inatcl ist die Integration des Petri-Netz-Analysewerkzeuges INA in die interpretierte Programmiersprache tcl (Tool Command Language). Durch Kombinieren von objektorientiertem Ansatz mit einem Callback- Konzept werden maximale Flexibilität und Ausnutzung der vollen Leistungsfähigkeit von INA erreicht. Mit dem Programm tkina wird eine neue graphische Benutzeroberfläche für INA entwickelt.

Projekt: Zeitabhängige Systeme

Ansprechpartner: Prof. Dr. Peter Starke

Beteiligte Mitarbeiter:

Dr. Louchka Popova-Zeugmann

Projektförderung:

Bei der DFG beantragt als Teilprojekt des Projektes "Analyse und Optimierung des Laufzeitverhaltens paralleler Software".

Zusammenarbeit:

Brandenburgische Technische Universität Cottbus, Prof. Dr. Monika Heiner,
Technische Universität Ilmenau, Prof. Dr. Wolfgang Fengler, Universität Rostock, Dr. -Ing. Herwig Unger

Im Rahmen dieses Projekts werden auf der Basis der Petrinetze Werkzeuge zur Modellierung von zeitabhängigen Systemen entwickelt, in denen die genaue Dauer der einzelnen Prozesse a priori nicht vorgegeben werden kann. Für die neudefinierten Beschreibungsmittel werden Analysemethoden entwickelt, um qualitative und quantitative Aussagen über ein System treffen zu können: Beschränktheit, Lebendigkeit, deadlocks; bzw. Berechnung der kürzesten bzw. längsten Dauer von Prozessen in dem System.

Einige neuentwickelte Algorithmen sind bereits implementiert: ein Transformationsprogramm simuliert die neudefinierten Dauer-Intervall-Petrinetze durch Intervall- Petrinetze (Time PN) und übergibt die Netzinformation an den PN-Analysator INA. Hier wird die qualitative und quantitative Analyse ausgeführt.

Projekt: PAMUM - Petrinetz-Analyse mit Maple und Mathematica

Ansprechpartner: Dr. Klaus-Peter Neuendorf

Beteiligte Mitarbeiter:

Dr. Klaus-Peter Neuendorf
Jan Richling

Zusammenarbeit:

Dr. Jörg Desel, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe

Das Projekt PAMUM hat die Realisierung einer Entwicklungsumgebung zur Modellierung und Analyse von Petrinetzen in einem Computeralgebrasystem zum Ziel. Es werden dabei die verschiedenen vom CAS bereits zur Verfügung gestellten Datentypen und Algorithmen verwendet und bezüglich ihrer Leistungsfähigkeit verglichen. Insbesondere werden daher lineare und zahlentheoretische Analysemethoden, wie modulo-Invarianten, Smith-Normalform und Gitterreduktion sowie die Methode der Gröbner-Basen eingesetzt.

Sonstige Themen

Rechnergestützte Werkzeuge zur Analyse von Petrinetz-Modellen, die in der Lehr- und Forschungseinheit entwickelt werden:

INA: Integrated Net Analyser
Analyse von P/T-Netzen, gefärbten Netzen und zeitbewerteten Netzen
Ansprechpartner:
- Prof. Dr. Peter Starke
- Dipl. -Inf. Lutz Pogrell
- Karsten Lüttge
inatcl:
Ansprechpartner: Dipl. -Inf. Lutz Pogrell
IVAN
Invariantenanalyse algebraischer Netze
Ansprechpartner: Dipl. -Inf. Karsten Schmidt
PAMUM
Petri-Netz-Analyse mit Maple und MATHEMATICA
Ansprechpartner: Dr. Klaus-Peter Neuendorf
YANED
Graphischer Editor für verschiedene Typen von Petri-Netzen
Ansprechpartner: Dipl. -Inf. Lutz Pogrell

Veröffentlichungen und Vorträge

K.-P. Neuendorf: The Gödel Model of Petri Nets. In Petri Net Newsletter 46.
J. Desel, K.-P. Neuendorf, M. Radola: Proving non-reachability by modulo-invariants. To appear in Theoretical Computer Science.
K.-P. Neuendorf: Petri Nets with Prescribed Invariants. In Petri Net Newsletter 49.
K.-P. Neuendorf: Construction of Petri Nets with Prescribed Properties. Workshop on CSP, Warschau, 1995.
L. Pogrell: inatcl - Analyse von Petrinetzen in tcl. Referenzhandbuch zum Programm.
L. Pogrell: inatcl - eine flexible Schnittstelle zu INA. 2. Workshop Algorithmen und Werkzeuge für Petrinetze. Oldenburg, 10. - 11. Oktober 1995.
L. Pogrell: Theoretische Grundlagen und Implementation der Methode der sturen Mengen (DA, 1995).
L. Popova-Zeugmann: A New Discrete Algorithm for the Computing a Reachability Graph of a weakly defined Time Petri Net. Workshop Algorithmen und Werkzeuge für Petrinetze. Oldenburg, Oktober 1995. (Extended abstract in Bericht Nr. AIS 22 - Oktober 1995, FB Informatik, Universität Oldenburg).
L. Popova-Zeugmann: On Liveness and Boundedness in Time Petri Nets. Workshop on Concurrency, Specification and Programming. Warschau, Oktober 1995.
K. Schmidt: Symmetries of Petri Nets. Vortrag am Laboratoire MASI der Universität Paris VI.
K. Schmidt: On the Computation of Place Invariants for Algebraic Petri Nets. In J. Desel (Ed.): Workshop on Structures in Concurrency Theory. Berlin, Mai 1995, S. 310 - 325. Workshops in Computing. Springer Verlag.
K. Schmidt: Parameterized Rechability Trees for Algebraic Petri Nets. In G. de Michelis, M. Diaz (Eds.): Proceedings of the 16th International Conference on Application and Theory of Petri Nets. Torino, Italy, Juni 1995, S. 392 - 411. Lecture Notes in Computer Science 935, Springer Verlag.
K. Schmidt: Symmetrieberechnung. Workshop Algorithmen und Werkzeuge für Petri-Netze, Oldenburg, Oktober 1995, (noch nicht erschienen).
K. Schmidt: Symmetry Calculation. Workshop on Concurrency, Specification and Programming, Warschau, Oktober 1995. Bericht der Universität Warschau, S. 147 - 161.
K. Schmidt: Symbolic Analysis of Algebraic Petri Nets. Int. Conference on intellectual systems and computer sciences. Moskau (November 1995), (noch nicht erschienen).
P. Starke: A Memo on Time Constraints in Petri Nets. Informatik-Bericht Nr. 46, August 1995.
P. Starke: Time-Deadlocks in Timed Net Models. Workshop CS&P 95, Warschau, Oktober 1995.

Weitere Aktivitäten

Gutachtertätigkeit

K.-P. Neuendorf, L. Popova-Zeugmann, K. Schmidt: für die 16. Internationale Konferenz Application and Theory of Petri Nets, 1995.
P. Starke: Überarbeitung der Skripte zur Vorlesung Logische Grundlagen der Informatik.

Lehr- und Forschungseinheit

Algorithmen und Komplexität

Leiter:

Prof. Dr. math. Hans Jürgen Prömel: Tel.: (030) 20 18 12 95, e-mail: proemel@informatik.hu-berlin.de

Mitarbeiter:

Dipl.-Math. Thomas Emden-Weinert
Dr. sc. Ernst-Günter Giessmann
Dr. David A. Grable
Dipl.-Ing. Norbert Herold
Dr. rer. nat. Stefan Hougardy
Dipl.-Math. Petra Knieper (Graduiertenkolleg)
Dipl.-Math. Bernd Kreuter
Dipl.-Math. Ralf Oelschlägel
Dr. rer. nat. Anand Srivastav
Dipl.-Math. Anusch Taraz

Sekretariat:

Eva Sandig: Tel.: (030) 20 18 12 94, e-mail: sandig@informatik.hu-berlin.de

Tutoren:

Gunnar Beck
Clemens Gröpl
Mirjam Kunze
Till Nierhoff
Mark Proksch

Zentrale Forschungsgegenstände am Lehrstuhl für Algorithmen und Komplexität sind der Entwurf und die Analyse effizienter Algorithmen. In der Komplexitätstheorie werden Probleme hinsichtlich verschiedener Komplexitätsmaße wie Laufzeit oder Speicherplatz klassifiziert. Algorithmen zur Lösung von Problemen, die sich durch eine besonders kurze Laufzeit bzw. einen besonders geringen Speicherplatz auszeichnen, werden effizient genannt. Eine wichtige Grundlage für die Entwicklung eines effizienten Algorithmus ist ein genaues Verständnis der dem Problem zugrundeliegenden Struktur. Es hat sich gezeigt, daß diese Strukturen sehr häufig als Graphen oder Hypergraphen modelliert werden können. Ein Schwerpunkt der Forschung am Lehrstuhl ist die Untersuchung zufälliger Graphen und Hypergraphen und die Anwendung der dabei erzielten probabilistischen und asymptotischen Resultate beim Entwurf und der Analyse von Graphenalgorithmen. Des weiteren werden in diesem Zusammenhang randomisierte und approximative Algorithmen systematisch studiert.

Eine Umsetzung der theoretischen Erkenntnisse in Algorithmen für praxisrelevante Probleme findet derzeit beim Verifizieren von VLSI-Schaltkreisen und im Rahmen eines weiteren Drittmittelprojektes bei der Lösung großer kombinatorischer Optimierungsprobleme im Bereich der Luftfahrtindustrie statt. Bei letzterem Vorhaben steht die Entwicklung paralleler Algorithmen im Vordergrund.

Projektbeschreibungen

Projekt: PARALOR - Parallele Algorithmen zur Lösung großer kombinatorischer Optimierungsprobleme

Ansprechpartner: Dipl. -Math. Thomas Emden-Weinert

Projektförderung: Bundesministerium für Bildung und Forschung

Die Lösung kombinatorischer Optimierungsprobleme ist in vielen Bereichen von Wirtschaft und Technik der Schlüssel zur Steigerung der Effizienz technischer Abläufe, Verbesserung der Produktqualität und Verringerung von Produktions- und Materialkosten. In diesem Verbundprojekt, das gemeinsam mit der Universität Paderborn, der Universität Köln und der Deutschen Lufthansa durchgeführt wird, werden Verfahren zur Flugplanoptimierung entwickelt bzw. weiterentwickelt und auf Parallelrechnern implementiert.

Zur Lösung der dabei auftretenden kombinatorischen Optimierungsprobleme wird eine Reihe unterschiedlicher Verfahren auf ihre Effizienz hin untersucht. Durch die enge Kooperation mit der Lufthansa ist eine direkte Überprüfung der praktischen Einsetzbarkeit der entwickelten Verfahren gewährleistet.

Projekt: Effiziente Algorithmen zur formalen Verifikation von VLSI-Designs

Ansprechpartner: Dr. Anand Srivastav

Projektförderung: Deutsche Forschungsgemeinschaft (Projekt im DFG-Schwerpunktprogramm Effiziente Algorithmen für Diskrete Probleme und ihre Anwendungen‘)

Heutzutage werden komplexe VLSI-Chips zunehmend an sicherheitskritischen Stellen eingesetzt, wie zur Kontrollsteuerung von lebenserhaltenden Systemen in der Medizin, bei Automobilen, in Flugzeugen und als Verkehrsleitsysteme. Die Logik solcher Schaltkreise muß daher mit größtmöglicher Sicherheit die von ihr erwarteten Funktionen erfüllen. Absolute Sicherheit kann nur ein mathematischer Beweis bieten. Die enorme Komplexität von VLSI-Schaltkreisen und die damit verbundene Explosion der kombinatorischen Möglichkeiten machen aber einen Beweis von Hand‘ praktisch unmöglich. Vielmehr kommt es darauf an, einen Algorithmus zu entwerfen, der die Realisierung eines Schaltkreises gegen die vorgegebene Spezifikation effizient testet.

In der industriellen Praxis ist die Simulation des Schaltkreises das zur Zeit dominierende Verifikations- Verfahren. Während die Logiksynthese und das physikalische Layout mit Hilfe kombinatorischer Algorithmen, die in den letzten 10 Jahren entwickelt wurden, schnell und effizient durchgeführt werden können, ist die Simulation einzelner Chips und erst recht eines Prozessors absolut zeitkritisch und beansprucht ca. 30 - 40% des Designprozesses.

Das Ziel des Forschungsprojekts ist es, mit Methoden der Algorithmischen Diskreten Mathematik, insbesondere der Kombinatorischen Optimierung, und probabilistischen Ansätzen neue Verfahren für die Verifikation von VLSI-Designs aufzuzeigen und diese an konkreten VLSI-Chips aus der Industriepraxis zu erproben.

Projekt: Probabilistische Argumente und algorithmische Probleme in Graphen und Hypergraphen

Ansprechpartner: Dr. David A. Grable

Projektförderung: Deutsche Forschungsgemeinschaft

Nachdem probabilistische Argumente seit langem erfolgreich in der Graphentheorie benutzt werden, um die Existenz von Strukturen mit bestimmten Eigenschaften nachzuweisen, hat sich das Interesse in den letzten Jahren zunehmend den algorithmischen Möglichkeiten dieser Methoden zugewendet.

Das Ziel des Forschungsprojekts ist es, Untersuchungen über Existenz- und Abzählprobleme in Graphen und Hypergraphen weiterzutreiben und die gewonnenen Ergebnisse auf algorithmische Fragestellungen anzuwenden. Im Vordergrund steht hierbei insbesondere die Anwendung von probabilistischen und asymptotischen Resultaten bei dem Entwurf und der Analyse von Färbungsalgorithmen.

Projekt: Graphen, Zufall und Algorithmen

Ansprechpartner: Dr. Stefan Hougardy

Projektförderung: Deutscher Akademischer Austauschdienst

Zusammenarbeit: University of Oxford

Im Rahmen des Projektes wird die Zusammenarbeit auf dem Gebiet der zufälligen Graphen und Algorithmen zwischen der Humboldt-Universität zu Berlin und der University of Oxford fortgesetzt und intensiviert. Hierbei steht die chromatische Zahl im Mittelpunkt des Forschungsinteresses.

Ziel ist es, ein besseres Verständnis für diesen Graphenparameter zu gewinnen, effiziente Algorithmen zur Berechnung der chromatischen Zahl unter bestimmten Nebenbedingungen zu entwickeln und das erworbene Wissen insbesondere auch zur Lösung verschiedener Probleme der Informatik und des Operations Research einzusetzen.

Sonstige Themen

Forschungsseminar Berlin - Poznan in Diskreter Mathematik

Ansprechpartner: Dr. David A. Grable

Zusammenarbeit: Adam-Mickiewicz-Universität Poznan

Seit Oktober 1995 findet regelmäßig ein gemeinsames Forschungsseminar mit einer Gruppe von Wissenschaftlern der Adam-Mickiewicz-Universität Poznan statt. Das Seminar wird abwechselnd in Poznan und Berlin abgehalten. Ziel dieses Seminars ist es, die Zusammenarbeit beider Gruppen auf den Gebieten zufällige Graphen, Ramsey-Theorie und randomisierte Algorithmen zu intensivieren.

Graduiertenkolleg Algorithmische Diskrete Mathematik

Ansprechpartner: Prof. Dr. Hans Jürgen Prömel

Beteiligte Mitarbeiter: Petra Knieper

Projektförderung: Deutsche Forschungsgemeinschaft

Zusammenarbeit: Graduiertenkolleg an der Freien Universität. Es wird gemeinsam getragen von der Freien Universität Berlin, der Humboldt-Universität zu Berlin, der Technischen Universität Berlin und dem Konrad-Zuse-Zentrum Berlin.

Aus den klassischen Gebieten wie Kombinatorik oder Graphentheorie hat sich die Diskrete Mathematik unter Einbeziehung des algorithmischen Standpunktes zu einem Themenkreis entwickelt, der Aspekte der Grundlagen, wie auch der angewandten Wissenschaften vereint. Im Zentrum des Graduiertenkollegs stehen Themen, die in integraler Weise Fragen und Methoden aus Mathematik und Informatik verknüpfen, wie z. B. Bewegungsplanung, Mustererkennung, algorithmische Geometrie. Flankiert werden sie durch Grundlagengebiete wie Kombinatorik, Graphenalgorithmen und Graphentheorie, Geometrie und anwendungsorientierte Themen wie Numerik und Optimierung.

Veröffentlichungen und Vorträge

Publikationen

D. Archdeacon, D. A. Grable: The genus of a random graph. Discrete Mathematics 142 (1995), S. 21- 37.
D. A. Grable, K. T. Phelps, V. Rödl: The minimum independence number for designs. Combinatorica 15 (1995), S. 175-185.
D. A. Grable: The diameter of a random graph with bounded diameter. Random Structures and Algorithms 6 (1995), S. 193-199.
S. Hougardy, H. J. Prömel, A. Steger: Probabilistically checkable proofs and their consequences for approximation algorithms. Discrete Mathematics 136 (1994), S. 175-223.
S. Hougardy: Even and odd pairs in linegraphs of bipartite graphs. European Journal of Combinatorics 16 (1995), S. 17-21.
S. Hougardy: On the P4-structure of perfect graphs. Shaker-Verlag, Aachen, 1995.
H. J. Prömel, A. Steger: Random l-colorable graphs. Random Structures and Algorithms 6 (1995), S. 21-37.
A. Srivastav, P. Stangier: Weighted fractional and integral k-matching in hypergraphs. Discrete Applied Mathematics 57 (1995), S. 255-269.

Preprints

D. A. Grable, K. T. Phelps: Random methods in design theory: a survey. Zur Publikation eingereicht.
D. A. Grable: Nearly-perfect hypergraph packing is in NC. Zur Publikation eingereicht.
D. A. Grable, A. Panconesi: Nearly optimal distributed edge colouring in O (log log n) rounds. Zur Publikation eingereicht.
D. A. Grable: On random greedy triangle packing. Zur Publikation eingereicht.
R. Hayward, S. Hougardy, B. Reed: Recognizing P4-structure. Oktober 1995.
S. Hougardy, V. B. Le, A. Wagler: Wing triangulated graphs are perfect. Preprint No. 434, Technische Universität Berlin, Januar 1995. Zur Publikation eingereicht.
S. Hougardy: Perfect graphs with unique P4-structure. Preprint, Oktober 1995. Zur Publikation eingereicht.
Y. Kohayakawa, B. Kreuter, A. Steger: An extremal problem for random graphs and the number of graphs with large even-girth. Humboldt-Universität zu Berlin, Februar 1995. Zur Publikation eingereicht.
B. Kreuter: Threshold functions for asymmetric Ramsey properties with respect to vertex colorings. Humboldt-Universität zu Berlin, September 1995. Zur Publikation eingereicht.
C. Michel, H. Schroeter, A. Srivastav: TSP and matching in printed-circuit-board assembly. Juli 1995. Zur Publikation eingereicht.
A. Srivastav, P. Stangier: On complexity, representation and approximation of multicommodity flows. November 1995.
A. Srivastav: Derandomised algorithms in combinatorial optimization. Habilitationsschrift, Oktober 1995.
A. Srivastav, P. Stangier: Tight approximation algorithms for resource constrained scheduling and bin packing. September 1995. Zur Publikation eingereicht.
F. Buijs, E. Frank, T. Lengauer, R. Oelschlägel, K. Pahnke, F. Rammig, G. Scarbata, R. Selent: Optimierte Modellübergänge bei der Synthese digitaler Informationsverarbeitungssysteme (OMSI). Schlußbericht zum BMFT-Verbundprojekt, Juni 1995.

Vorträge

Thomas Emden-Weinert
- Parallele Algorithmen bei der Flugplanung. Tag der Informatik, Humboldt-Universität zu Berlin, November 1995.
  Ernst-Günter Giessmann
- Elektronische Unterschriften und sichere Verschlüsselungen. Tag der Mathematik, Freie Universität Berlin, Mai 1995.
- Elektronische Dokumente und sichere Verschlüsselungen. URANIA Berlin, September 1995.
- Grenzen der Anschaulichkeit in der Geometrie. Lehrerweiterbildung, Berlin, November/ Dezember 1995.
David A. Grable
- More-than-nearly-perfect Packings in Hypergraphs. The Seventh International Conference on Random Structures and Algorithms, Atlanta, USA, Mai 1995.
- Random Methods in Design Theory. The 15th British Combinatorial Conference, Stirling, Großbritannien, Juli 1995.
- Random Greedy Triangle Packing. Adam Mickiewicz University, Poznan, Polen, Oktober 1995.
Stefan Hougardy
- Certificates for perfect graphs. 15. Berliner Algorithmentag, Berlin, Juni 1995.
- Graphs with unique P4-structure. 5me Colloque International Graphes et Combinatoire, Marseille, Frankreich, September 1995.
- On the P4-structure of perfect graphs. Dissertationsverteidigung, Humboldt-Universität zu Berlin, Oktober 1995.
- On the P4-structure of perfect graphs. Kolloquium über Kombinatorik, Technische Universität
Braunschweig, November 1995.
- P4-structure. Oxford University, Großbritannien, Dezember 1995.
Petra Knieper
- Parallele Konstruktion von (-Approximationen in der Algorithmischen Geometrie. Kolloquium über Kombinatorik, Braunschweig, November 1995.
Bernd Kreuter
- Threshold functions for Ramsey properties involving two cycles. The Seventh International Conference on Random Structures and Algorithms, Atlanta, USA, Mai 1995.
- Probabilistische Ramseysätze. Kolloquium über Kombinatorik, Braunschweig, November 1995.
- Probabilistic Ramsey Theorems. Oxford University, Großbritannien, Dezember 1995.
Hans Jürgen Prömel
- Probabilistische Argumente in der Diskreten Mathematik. Jahrestagung der DMV, Ulm, September 1995.
- Die Probabilistische Methode. Herbstschule Zufällige Strukturen und Algorithmen, Buckow, Oktober 1995.
- Algorithmen, Komplexität und Zufall. Antrittsvorlesung an der Humboldt-Universität zu Berlin, Berlin, November 1995.
- Wie man Beweise verifizieren kann, ohne sie zu lesen: Eine neue Charakterisierung der Klasse NP mit überraschenden Konsequenzen für Optimierungsprobleme. Universität Dortmund, Dezember 1995.
Anand Srivastav
- Parallele Berechnung von Diskrepanzen und (-Approximationen. Workshop Komplexitätstheorie, Universität Dortmund, März 1995.
- Tight approximation algorithms for scheduling and bin packing. Twente Workshop on Graphs and Combinatorial Optimization, Universität Twente-Enschede, Niederlande, Juni 1995.
- Effiziente Algorithmen für die Verifikation von VLSI-Design. DFG-Kolloquium, St. Augustin, Juni 1995.
- TSP and matching in printed-circuit-board assembly. European Symposium on Operations Research, Jerusalem, Israel, Juli 1995.
- On derandomized algorithms in combinatorial optimization. Workshop on Probabilistic Algorithms and Algorithmic Probability, Universität Twente-Enschede, Niederlande, November 1995.
- Effiziente Algorithmen zur Verifikation von Schaltkreisen. Tag der Informatik, Humboldt- Universität zu Berlin, November 1995.
Anusch Taraz
- Szemerédis Regularitätslemma. Studentenkonferenz Mathematik im Rahmen der Jahrestagung der Deutschen Mathematiker-Vereinigung, 21.-22. September 1995 in Ulm.

Editorentätigkeit

H. J. Prömel (gemeinsam mit W. Deuber und B. Voigt): Trends in Discrete Mathematics. Topics in Discrete Mathematics, Volume 9, North-Holland, Amsterdam, 1995.
H. J. Prömel: Mitglied des Editorial Boards der Zeitschriften Random Structures and Algorithms und Combinatorics, Probability and Computing.

Weitere Aktivitäten

Tagungen/Workshops

Herbstschule Zufällige Strukturen und Algorithmen des Graduiertenkollegs Algorithmische Diskrete Mathematik, 9. - 11. Oktober 1995 in Buckow, Märkische Schweiz (Leiter: Hans Jürgen Prömel).: Teilnehmer waren 32 Studenten und Doktoranden aus dem gesamten Bundesgebiet sowie als Dozenten Prof. Dr. Tom Trotter (Arizona State University), Prof. Dr. Colin McDiarmid (University of Oxford), Prof. Dr. Friedhelm Meyer auf der Heide (Universität Paderborn), Prof. Dr. Angelika Steger (Universität Duisburg).

15. Berliner Algorithmentag, 9. Juni 1995.: Der Berliner Algorithmentag ist eine zweimal jährlich stattfindende Veranstaltung der Technischen Universität Berlin, der Freien Universität Berlin, der Humboldt-Universität zu Berlin und des Konrad-Zuse-Zentrums für Informationstechnik Berlin. Der 15. Berliner Algorithmentag wurde vom Institut für Informatik der Humboldt-Universität zu Berlin organisiert, Hauptvortragender war Prof. Dr. Colin McDiarmid aus Oxford.

Gäste am Lehrstuhl

Prof. Dr. Colin McDiarmid: University of Oxford, Mathematical Institute, Department of Statistics,: Oxford, Großbritannien. Juni 1995.
Prof. Dr. Walter Deuber: Universität Bielefeld, Fakultät für Mathematik. Juni 1995.
Prof. Dr. Joel Spencer: Courant Institute of Mathematical Sciences, New York University, New York, USA. Juni 1995.
Prof. Dr. Bruce Reed: Equipe Conbinatoire, CNRS, Université Pierre et Marie Curie, Paris,: Frankreich. Oktober 1995.
Prof. Dr. Elefterie Olaru: Universitatea din Galati, Catedra de Matematica, Galati, Rumänien. Oktober bis Dezember 1995.
Prof. Dr. Ingo Wegener: Universität Dortmund, Fachbereich Informatik. November 1995.
Prof. Dr. Peter Gritzmann: Universität Trier, Diskrete Mathematik. November 1995.

Dissertationen

Diplomarbeiten

Marc Oliver Bettzüge: Dünne H-freie Graphen. Januar 1995.
Udo Konitzer: Über Kürzeste-Wege-Algorithmen mit O (n2 log c n)-erwarteter Laufzeit. Januar 1995.
Steffen Sledz: Erkennung und Optimierung arithmetischer Strukturen in Datenflußgraphen - Generierung von Allokationsvorschlägen. Januar 1995.
Helmar Prehn: Die Berechnung von Signalverzögerungen in Modulgeneratoren. Januar 1995.
Anusch Taraz: Szemerédis Regularitätslemma. April 1995.
Petra Knieper: Die Algorithmischen Aspekte des Hypergraphen 2 - Färbungsproblem. April 1995.
Thomas Uhlig: Ein uniformes Plazierungsverfahren für Layoutobjekte unterschiedlicher Formen und Größe. Juni 1995.
Stephan Hasselberg: Färbungsparameter von Graphen. August 1995.
Christoph Hundack: Extremale und asymptotische Betrachtungen H-freier Graphen. Oktober 1995.

Lehr- und Forschungseinheit

Systemanalyse

Leiter:

Prof. Dr. Joachim Fischer: Tel.: (030) 20 18 12 33, e-mail: fischer@informatik.hu-berlin.de

Mitarbeiter:

Dr. Klaus Ahrens
Dr. Eckhardt Holz
Dr. Andreas Prinz
Dipl.-Math. Manfred Hagen
Projektmitarbeiter (Drittmittelstellen):
Dr. Evgeni Dimitrov
Dipl.-Inf. Nils Fischbeck
Dipl.-Math. Dietmar Gellermann
Dipl.-Inf. Mario Kolberg
Dipl.-Inf. Gerd Kurzbach
Dr. Stefanie Lau
Dipl.-Inf. Martin von Löwis of Menar
Dr. Reneé Mundstock
Dipl.-Inf. Ralf Schröder
Dipl.-Math. Maciej Wasowski
Dipl.-Ing. Dorota Witaszek

Sekretariat:

Marita Albrecht: Tel.: (030) 20 18 12 31, e-mail: albrecht@informatik.hu-berlin.de

Tutoren:

Frank Bielig
Olaf Kath
Henrik Kinnemann
Andreas Kuntzagk
Matthias Schwalbe
Magdalena Wasowska

Am Lehrstuhl Systemanalyse steht die Untersuchung komplexer dynamischer Systeme sowohl zeitdiskreter und zeitkontinuierlicher als auch kombinierter Natur mittels Computersimulation im Mittelpunkt von Lehre und Forschung. Traditionell werden dabei objektorientierte Entwurfs- und Implementierungsmethoden entwickelt und eingesetzt. Der Bereich Telekommunikation stellt gegenwärtig das Hauptanwendungsgebiet dar.

Projektbeschreibungen

Projekt: Entwicklung einer universellen Prozeßbibliothek in C++

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter:

Frank Bielig
Prof. Dr. Joachim Fischer
Dorota Witaszek

Zusammenarbeit: Mit Partnern von OpenSite, MultiServ, TERMO, INSYDE

Die technologische Basis aller Simulationswerkzeuge am Lehrstuhl bildet eine (vom PC bis zur Workstation) portable Kernbibliothek von Leichtgewichtsprozessen in C++. Diese ermöglicht einen konsequent objektorientierten Aufbau aller darauf aufsetzenden Anwendungen in den verschiedenen Projekten des Lehrstuhls. Gegenwärtig wird an einer neuen Version der Basisbibliothek gearbeitet, um bei Einhaltung der bisher definierten Schnittstellen die Effizienz und Robustheit des Kerns (Speicher- und Prozeßverwaltung) weiter zu verbessern. Auf der Basis einer Analyse von Simulationssystemen mit ähnlichen Grundansätzen ist die Kernbibliothek weiter zu konsolidieren, wobei die Grundfunktionalität beibehalten werden soll. Darüber hinaus werden ein hierachischer Prozeßverwaltungsapparat implementiert und Kombinationen mit kommerziellen Simulationswerkzeugen (z. B. SES Workbench) untersucht.

Projekt: Allgemeine objektorientierte Simulationssoftware in C++

Ansprechpartner: Prof. Dr. Joachim Fischer

Beteiligte Mitarbeiter:

Dr. Klaus Ahrens
Maciej Wasowski
Dorota Witaszek

Zusammenarbeit: Mit Partnern von OpenSite, MultiServ, TERMO, INSYDE

Eine Anwendung der Prozeßkernbibliothek besteht in der Implementation von sogenannten allgemeinen universellen Simulationssystemen in C++. Hier werden am Lehrstuhl sowohl rein diskrete (ODEM) und rein kontinuierliche (CADSIM), als auch kombinierte allgemeine Simulationssysteme entwickelt (COMBINEDSIM). Die Quellen der Systeme ODEM und CADSIM und der Prozeßkernbibliothek sind auf dem ftp-Server des Instituts unter ftp.informatik.hu-berlin.de: /pub/local/simulant/odem frei verfügbar. Neben dem Einsatz in der Lehre sind diese Bibliotheken vorrangig für eine Adaption im Kontext verschiedener Projekte einsetzbar, bei denen insbesondere auch der Aspekt kontinuierlicher Vorgänge eine wesentliche Rolle spielt. Die Arbeiten sollen künftig auf die Stream-Modellierung im Multi-Media-Bereich orientiert werden.

Projekt: OpenSITE

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter:

Martin von Löwis of Menar
Gerd Kurzbach
Ralf Schröder

Zusammenarbeit: mit Partnern in unterschiedlichen Anwendungsprojekten

OpenSITE (Open SDL Integrated Tool Environment) ist eine Entwurfs-, Analyse- und Transformationsumgebung für Spezifikationen in SDL‘92 in Kombination mit unterschiedlichen Datentypspezifikationstechniken. Basis dieser Werkzeugumgebung ist ein Austauschformat (Common Representation), das mit der Eingabesprache des Meta-Werkzeugs Kimwitu definiert ist. Kimwitu stellt Funktionen für den transparenten Austausch von Informationen über die Spezifikation zwischen verschiedenen (Front-End/Back-End-) Programmen bereit. Diese Informationen sind unabhängig von der konkreten syntaktischen Repräsentation der Spezifikation, die in grafisch- oder programmiersprachlich- orientierter Form vorliegen kann. Damit sind sowohl die Anwendungen verschiedener SITE-Komponenten als auch ihre Weiterentwicklung unabhängig von der bisher realisierten Ausbaustufe. Die SITE-Umgebung ist damit insbesondere offen für ihrer Anbindung und Benutzung durch Werkzeuge anderer Hersteller.

Implementiert sind bisher folgende Komponenten:

ein standardkonformer Syntax- und Semantikanalysator von SDL‘92-Spezifikationen in Kombination mit ASN.1-Datentypspezifikationen,
ein X11-basierter syntaxorientierter Text-Editor für SDL in Kombination mit ASN.1,
ein Pretty-Printer für SDL/PR,
ein Codegenerator von SDL nach C+ mit entsprechenden Bibliotheken zur automatischen Erzeugung von sowohl Simulations- als auch Zielcode,
Debug-Werkzeuge zur Unterstützung von Simulationsexperimenten und zum Test generierter Softwareprototypen.

An einer Integration der interaktiven SITE-Komponenten unter Nutzung einer CORBA-Plattform wird derzeit gearbeitet.

Projekt: Petrinetz-basierte Analyse von SDL-Spezifikationen

Ansprechpartner: Dr. Evgeni Dimitrov

Petrinetzbasierte Analysemethoden stellen einen wichtigen Beitrag für den Nachweis allgemeiner dynamischer Eigenschaften von SDL-Spezifikationen verteilter Systeme aus dem Telekommunikationsbereich, wie Verklemmungsfreiheit, dar. Auf Grund der Mächtigkeit der SDL-Semantik wurden Erweiterungen gegenüber den klassischen Petrinetzen vorgenommen: Zuordnung von Datenstrukturen zu Plätzen und von Zeitangaben und Guard-Funktionen zu Transitionen. Dadurch können solche Aspekte von SDL, wie Signalparameter und lokale Prozeßvariablen, die dynamische Erzeugung von Prozessen sowie das Verhalten von Signaleingabepuffern, lokalen Uhren und Übertragungskanälen adäquat zur SDL-Semantik und kompakt auf Netzebene modelliert werden. Die Realisierung dieses Ansatzes basiert auf einer automatischen Transformation der Ausgangsspezifikation in ein Netzmodell, einer Generierung und Analyse des Erreichbarkeitsgraphen des Netzes und einer Rücktransformation der Ergebnisse auf SDL- Niveau. Die entsprechenden Software-Komponenten sind im Rahmen der Entwicklungsumgebung OpenSITE integriert worden. Erste Untersuchungen von zwei Anwendungsbeispielen (INRES- und Sliding- Window-Protokoll) haben die praktische Relevanz dieses Ansatzes bestätigt.

Projekt: OOSPEC

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter: Dr. Reneé Mundstock

Projektförderung:

Deutsche Telekom AG,
AiF (Arbeitsgemeinschaft industrieller Forschungsvereinigungen e. V.)

Zusammenarbeit:

Deutsche Telekom AG,
Forschungs- und Technologiezentrum Darmstadt

Im Projekt OOSPEC wurden Spezifikationen für zwei Prototypapplikationen verteilter multimedialer Dienste (Videolibrary und Teleswitching) erstellt, simuliert und verbessert. Dabei setzte man zunächst kommerzielle SDL-Werkzeuge eingesetzt, die den veralteten Sprachstandard von 1988 unterstützen. Davon ausgehend überarbeitete man die Spezifikationen unter Verwendung von SDL 92 und den am Lehrstuhl entwickelten Werkzeugen auf objektorientierter Grundlage. Zugleich wurden allgemeine Techno- logien zum Einsatz objektorientierter Entwurfsmethoden erarbeitet und angewendet. Das Projekt ist abgeschlossen. Sowohl die erstellten Spezifikationen als auch die ent- wickelte Methodologie sind Ausgangspunkt weiterer Arbeiten im Projekt TERMO.

Projekt: MultiServ

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter:

Gerd Kurzbach
Ralf Schröder

Projektförderung:

Deutsche Telekom AG, AiF (Arbeitsgemeinschaft industrieller Forschungsvereinigungen e. V.)

Zusammenarbeit:

Deutsche Telekom AG
Forschungs- und Technologie-Zentrum Darmstadt,
AT&T Niederlande,
TU Ilmenau

MultiServ ist Bestandteil eines gemeinsamen Forschungsprojektes der Deutschen Telekom AG und AT&T Niederlande unter dem Namen PLATINUM, in dem prototypische Implementationen für Multimedia-/ Multiparty-Dienste (Video Library, Teleswitching) entwickelt werden. Aufgabe des Lehrstuhls ist die Erstellung, Anwendung und Anpassung von Werkzeugen zur Transformation von SDL92- und ASN.1- Spezifi- kationen nach C+. Zum Einsatz kommen dabei projektspezifische Implementationen von Werkzeugkomponenten aus OpenSITE. Das Projekt ist abgeschlossen. Ergebnisse fließen sowohl in das Nachfolgeprojekt TERMO als auch in den weiteren Ausbau von OpenSITE ein.

Projekt: TERMO

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter:

Nils Fischbeck
Mario Kolberg
Gerd Kurzbach
Martin von Löwis of Menar
Ralf Schröder

Projektförderung:

Deutsche Telekom AG,
AiF (Arbeitsgemeinschaft industrieller Forschungsvereinigungen e. V.)

Zusammenarbeit:

Deutsche Telekom AG
Forschungs- und Technologie-Zentrum Darmstadt,
AT&T Niederlande,
TU Ilmenau

In Fortsetzung der Arbeiten aus den Projekten OOSPEC und MultiServ wird im Rahmen von TERMO die Integrationsphase des übergeordneten Projektes PLATINUM unter- stützt. Die Schnittstellen zu den u. a. im Vorläuferprojekt MultiServ entstandenen SDL-Basisbibliotheken (Simulationsbibliothek und Zielcodebibliothek) sind zu vereinheit- lichen, um fortan eine Konzentration auf einen einzigen Codegenerator erreichen zu können. Darüber hinaus werden im Projekt TERMO vom Lehrstuhl spezielle Protokoll- schichten zur Realisierung von Multimedia-/Multiparty-Diensten in SDL92 spezifiziert, getestet und in prototypische Implementationen überführt. Eine CORBA-basierte Ent- kopplung einer gleichzeitig zu schaffenden Nutzeroberfläche für einen SDL-Simulator vom Simulator selbst ist ebenfalls Bestandteil der im Projekt zu erbringenden Leistungen.

Weitere Forschungsprojekte in Fortsetzung von TERMO, bei denen insbesondere eine Orientierung auf die Architekturen CORBA, TINA und ODP von vorrangiger Bedeutung ist, sind in Vorbereitung.

Projekt: Ein Konzept von Standardbasisklassen für multiple objektorientierte Programmiersprachen

Ansprechpartner: Dr. Klaus Ahrens

Beteiligte Mitarbeiter: W. Dietmar Gellermann

Projektförderung:

Deutsche Telekom AG,
AiF (Arbeitsgemeinschaft industrieller Forschungsvereinigungen e. V.)

Zusammenarbeit:

Deutsche Telekom AG,
Forschungs- und Technologiezentrum Berlin

Anliegen dieses Projektes ist die Untersuchung objektorientierter Programmiersprachen auf Compilerbasis (insbesondere C++) hinsichtlich ihrer Eignung, Smalltalk-Programme in diese zu transformieren. Dazu ist von einem Sprachvergleich ausgehend eine

Technologie zur Transformation zu entwickeln und deren Funktionstüchtigkeit an einem Prototyp zu demonstrieren. Auf der Basis von angestrebten struktur- und funktions- äquivalenten Klassenbibliotheken spezifischer Anwendungsbereiche des Auftraggebers soll eine Programmiermethodik entwickelt werden, die insbesondere Vorzüge von Smalltalk und C++ zu kombinieren gestattet. Eine Fortsetzung der Arbeiten in Richtung automatischer Sprachtransformationen wird gegenwärtig geprüft.

Projekt: Base Specification and Description Language BSDL

Ansprechpartner: Dr. Andreas Prinz

Beteiligte Mitarbeiter:

Dr. Andreas Prinz
Dr. Stefanie Lau

Die Spezifikationssprache SDL besitzt aufgrund ihrer historischen Entwicklung eine formale Semantik, die auf einer Mischung unterschiedlicher, nicht integrierter, mathematischer Modelle basiert. Dadurch ist diese formale Semantik als Grundlage für die formale Verifikation von SDL-Spezifikationen ungeeignet. Darüber hinaus ist auch eine beabsichtigte Weiterentwicklung der Sprache bis zum Jahre 2000 mit der ITU- Forderung verbunden, eine Harmonisierung der Sprachkonzepte in Kombination mit der Entwicklung einer kompakteren Semantik voranzutreiben. Einen wesentlichen Beitrag dazu soll die Entwicklung der Sprache BSDL (Base Specification and Description Language) liefern. BSDL ist objektorientiert, beruht auf dem Modell kommunizierender Zustandsautomaten und besitzt einen einheitlichen semantischen Rahmen für die Beschreibung von Objektorientierung (für Prozeß- und Datentypen), von zeitlichen Aspekten, Prozessen, Kommunikation, Abstraktion sowie Parallelität und Nichtdeterminismus. Zur Definition der formalen Semantik von BSDL wird Object-Z, eine objektorientierte Erweiterung der Spezifikationssprache Z, benutzt. Aufgrund dieser Eigenschaften bietet sich BSDL einerseits als Basissprache zur Beschreibung der formalen Semantik von Spezifikationssprachen für verteilte Systeme an und soll andererseits als Ausgangs- sprache für die Weiterentwicklung von SDL dienen. Darüber hinaus soll die Sprachkonzeption von BSDL die Anbindung anderer Spezifikations- und Datentypbeschreibungssprachen ermöglichen. Die derzeit vorliegende Sprachversion von BSDL enthält eine vollständige Beschreibung der abstrakten Syntax und der informalen Semantik. Gegenwärtig wird an der Vervollständigung der formalen Semantik von BSDL gearbeitet und die vorliegende Sprachversion an Beispielen evaluiert. Parallel dazu werden erste Schritte in Richtung einer Werkzeugentwicklung für BSDL unternommen.

Projekt: INSYDE - Integrated Methods for Evolving System Design

Ansprechpartner: Dr. Eckhardt Holz

Beteiligte Mitarbeiter:

Dr. Stefanie Lau
Maciej Wasowski
Dorota Witaszek

Projektförderung:

ESPRIT-III-Projekt, finanziert durch die Kommission der Europäischen Gemeinschaften

Zusammenarbeit:

VERILOG S. A., Toulouse/Frankreich;
ALCATEL Bell Belgium, Antwerpen/Belgien;
INTRACOM S. A., Peania/Griechenland;
Dublin City University, Dublin/Irland;
Vrije Universiteit Brussel, Brüssel/Belgien

Das Ziel des Projekts INSYDE ist die Entwicklung einer Methodologie und eines zugehörigen Werkzeugsatzes für die Analyse und das Design von hybriden Hardware-Software-Systemen durch eine Integration der objektorientierten Analysemethode OMT mit den bereichsspezifischen Entwurfs- und Spezifikationstechniken SDL und VHDL. Die Validierung der integrierten hybriden Entwürfe soll durch Computersimulation erfolgen. Die INSYDE-Methodologie ist an ausgewählten Beispielen aus dem Bereich der Telekommunikation (Video-On-Demand) und des Hardwareentwurfs (Kompressions-Chip für Videobilder) zu demonstrieren. Die Aufgaben des Lehrstuhls liegen in der Entwicklung einer Methodologie sowie der Entwicklung von Prototypen für die Co-Simulation und die OMT-SDL/VHDL-Transformatoren. Darüber hinaus ist der Einsatz von INSYDE in beiden Applikationen hinsichtlich einer Methodologieverbesserung zu bewerten. Die wichtigsten im Jahr 1995 vom Lehrstuhl erzielten Ergebnisse sind:

Ausarbeitung der kompletten INSYDE-Methodologie (mit den Schritten Analyse, Systementwurf, detaillierter Entwurf, Validierung und Hardware-Software-Co-Simulation)
Abschluß der formalen Spezifikation der OMT-Designsprache (OMT*)
Erarbeitung und Erprobung von Co-Simulationsverfahren
Ausarbeitung von Synchronisationsmechanismen zur SDL-VHDL-Simulatorkopplung.

Bild 3.3 gibt einen schematischen Überblick über die einzelnen Phasen der Entwicklung und Validierung hybrider Hardware-Software-Systeme mit INSYDE.

Projekt: Internationale Standardisierung

Ansprechpartner: Prof. Dr. Joachim Fischer

Beteiligte Mitarbeiter:

Dr. Eckhardt Holz
Dr. Stefanie Lau
Dr. Andreas Prinz

Zusammenarbeit:

ITU-T (International Telecommunication Union -Telecommunications Sector);
ISO (International Standardisation Organisation);
OMG (Object Management Group);
DIN (Deutsches Institut für Normung e. V.)

Die Aktivitäten des Lehrstuhls im Bereich der Standardisierung konzentrieren sich auf die Themenbereiche "Formale Spezifikation mit SDL‘92" sowie "Modellierungstechniken und Methoden für offene verteilte Systeme". Dazu werden Ergebnisse anderer Projekte des Lehrstuhls in den Standardisierungsprozeß eingebracht, aber auch strategische Zielsetzungen für die Forschung aus aktuellen Standardisierungsaktivitäten mit identifizierten ungelösten Problemen abgeleitet. Die konkreten Projekte im Rahmen der Standardisierung betreffen:

ISO/ITU-T/DIN (OMG)
Formalisierung der Viewpoint-Beschreibungssprachen des Referenzmodells für offene verteilte Verarbeitung (RM-ODP) mit SDL‘92,
formale Spezifikation des ODP-Traders und Ableitung von Konformitätstestmethoden,
Verbindung von SDL‘92 mit Interfacebeschreibungssprachen (OMG-IDL, TINA- ODL)
ITU-T
Entwicklung einer objektorientierten Entwurfsmethodologie für SDL 92 basierend auf den Ergebnissen des INSYDE-Projektes,
Entwicklung einer neuen formalen Semantik für SDL (BSDL/SDL2000),
Kombination von SDL 92 mit ASN.1 (incl. der Erarbeitung einer formalen Semantik),
Harmonisierung und Vereinfachung von SDL 92-Sprachelementen.

Veröffentlichungen und Vorträge

J. Fischer, E. Dimitrov, U. Taubert: Analysis and formal Verification of SDL‘92 Specifications using Extended Petri Nets. In: Informatik-Bericht 43, Humboldt-Universität zu Berlin, 1995.
J. Fischer, E. Dimitrov: Verification of Formal Specifications using Extended Petri Nets. Proceedings of the 20th International Conference "Information Technologies and Programming", Plovdiv, Bulgarien 1995, S. 66-73.
J. Fischer, E. Dimitrov: Verification of SDL Protocol Specifications using Extended Petri Nets. Proceedings of the Workshop on Petri Nets and Protocols of the 16th International Conference on Application and Theory of Petri Nets, Turin, Italien 1995, S. 1-12.
J. Fischer, E. Dimitrov: Verification of SDL 92 Specifications using Extended Petri Nets. Proceedings of the 15 th International Symposium on Protocol Specifcaton, Testing and Verification, Warschau, Polen 1995, S. 455-458.
U. Behnke, M. Geipl, G. Kurzbach, R. Schröder, N. Fischbeck, R. Mundstock: Development of broadband ISDN telecommunication services using SDL‘92, ASN.1 and automatic code generation. In Participants proceedings FORTE 95, Montreal, Quebec, Kanada 1995.
Jin Ye: Specification and Simulation of TDM/CDMA VSAT Integrated Service Satellite Communication. In: Informatik-Bericht 42, Humboldt-Universität zu Berlin, 1995.
M. Born, J. Fischer, M. Winkler: Formal Language Mapping from CORBA IDL to SDL 92. In: Informatik-Bericht 44, Humboldt-Universität zu Berlin, 1995.
J. Fischer, S. Lau, A. Prinz: A Short Note About BSDL - Semantic Issues for SDL. SDL-Newsletter 18, Januar 1995.
D. Witaszek, E. Holz, S. Lau, M. Wasowski, J. Fischer: A Methodology for Object-Oriented Analysis and Design Using OMT and SDL 92. In: Informatik-Bericht Nr.49, Humboldt-Universität zu Berlin, November 1995.
E. Holz, M. Wasowski, D. Witaszek, S. Lau: Design of Hybrid Hardware/Software Systems with INSYDE. Proceedings of the IEE Colloquium "Partitioning in Hard ware-Software Codesigns"; London, Februar 1995.
M. Wasowski, D. Witaszek, J. Fischer, E. Holz, S. Lau, O. Kath: Co-Simulation of Hybrid SDL and VHDL Specifications. Proceedings of the "9th European Simulation Multiconference"; Prag, Tschechische Republik, Juni 1995.
Fischer, A. Prinz, M. Wasowski, O. Kath: Simulation of VHDL specifications in C+. Proceedings of the 5th International IMACS Symposium "System Analysis & Simulation"; Berlin, Juni 1995.
K. Ahrens, J. Fischer, F. Bielig: DESPAC+ - Discrete Event Simulation in C+. Proceedings of the 5th International IMACS Symposium "System Analysis & Simulation"; Berlin, Juni 1995.
M. Wasowski, V. Mariatos: An Object-Oriented Methodology for Hardware-Software Codesign. Journal of EUROMICRO 95, Como, Italien, September 1995.
D. Witaszek, E. Holz, M. Wasowski, S. Lau, J. Fischer: A Development Method for SDL‘92 Specifications Based on OMT. Proceedings of the "7th SDL Forum"; Oslo, Norwegen, September 1995.
J. Peeters, M. Jadoul, E. Holz, M. Wasowski, D. Witaszek, J. P. Delpiroux: HW/SW Co-Design and the Simulation of a Multimedia Application. Proceedings of the ESS‘95 7th European Simulation Symposium, Erlangen, Oktober 1995.
D. Sinclair, E. Holz, D. Witaszek, M. Wasowski: Validation of Hybrid Systems by Co-Simulation. Proc. of the DIMACS Workshop on Verification and Control of Hybrid Systems, New Jersey, USA, September 1995.

Weitere Aktivitäten

Standardisierungsbeiträge (DIN, ITU-T, ISO)

Teilnahme an folgenden internationalen Standardisierungskonferenzen:
- ITU-T SG 10 Rapporteurs Meeting in St. Petersburg, April 1995.
- ISO/ITU-T JTC1/SC21/WG7 Editing Meeting in Helsinki, Mai 1995
- ITU-T SG 10 Q6-Expert Meeting in Lutterworth, Juni 1995
- ISO/ITU-T JTC1/SC21/WG7 Meeting in Ottawa, Juli 1995
- ITU-T SG 10 Meeting in Genf, September 1995
- OMG Meeting in Makuhara, November 1995
E. Holz: Formalization of the Computational Language with SDL-92 (Part4-1). Contribution to ISO/ ITU-T Meeting Helsinki, Finnland, Mai 1995.
E. Holz: Formalization of the Computational Language with SDL-92 (Part4-2). Contribution to ISO/ ITU-T Meeting Ottawa, Kanada, Juli 1995.
D. Witaszek, E. Holz, S. Lau, M. Wasowski, J. Fischer: A Methodology for Object-Oriented Analysis an Design Using OMT and SDL‘92. Temporary Document, ITU SG10 Q.6 Expert Meeting (Source: Humboldt University Berlin, Dept. of Computer Science), Genf, Schweiz, September 1995.
A. Prinz, S. Lau, J. Fischer: BSDL - a Way to a Simplified SDL. Temporary Document, ITU SG10 Q.6 Expert Meeting (Source: Humboldt University Berlin, Dept. of Computer Science), Genf, Schweiz, September 1995.
S. Lau, A. Prinz: BSDL: The Language - Version 0.2. Temporary Document, ITU SG10 Q.6 Expert Meeting (Source: Humboldt University Berlin, Department of Computer Science), Genf, Schweiz, September 1995.
D. Witaszek, E. Holz, S. Lau, J. Fischer: Use of the OMT Statechart and automation of the SDL design. Temporary Document, ITU SG10 Q.6 Meeting (Source: Humboldt University Berlin, Department of Computer Science), Toulouse, Frankreich, November 1995.
M. Born, M. Winkler, J. Fischer: Formal language mapping from CORBA IDL to SDL‘92 in Combination with ASN.1. November 1995.
M. Born, M. Winkler: SDL specification of the ODP Trading Function. November 1995.
S. Niedrig, S. Rademann: ANNEX D and H of Trader Document. November 1995.
M. Born, M. Winkler: ANNEX E, F and G of Trader Document. November 1995.
M. Born, M. Winkler: Proposal for an improvement of SDL 92. November 1995.

Werkzeugvorführungen

E. Holz: INSYDE-Demonstration, "COST 247 Meeting", Warschau, Polen, Juni 1995.
R. Schröder: OpenSITE-Demonstration; "SDL‘95 with MSC in CASE", Oslo, Norwegen, September 1995.
R. Schröder: OpenSITE-Demonstration; "Forte 95", 8th International Conference on Formal Description Techniques for Distributed Systems and Communication Protocols, Quebec, Kanada, Oktober 1995.

Projektberichte

N. Fischbeck: Die Schicht SUA/GUA. Zwischenbericht im Projekt TERMO, Forschungsprojekt mit dem Forschungs- und Technologiezentrum Darmstadt der Deutschen Telekom AG und der Humboldt- Universität zu Berlin, Oktober 1995, (nur beschränkt zugänglich).
G. Kurzbach, R. Schröder: SDL-Werkzeugentwicklung und Einsatz zur Generierung von C++- Zielcode. Abschlußbericht zum Projekt MULTISERV, Forschungsprojekt mit dem Forschungs- und Technologiezentrum Darmstadt der Deutschen Telekom AG und der Humboldt-Universität zu Berlin, November 1995, (nur beschränkt zugänglich).
E. Holz, M. Wasowski, D. Witaszek, S. Lau, et. al.: INSYDE - Application Guidelines. ESPRIT P8641, Report D-1.2 (152 S.), Mai 1995.
E. Holz, M. Wasowski, D. Witaszek, S. Lau, et. al.: INSYDE - Final Methodology. ESPRIT P8641, Report D-1.3, Dezember 1995.

Studienarbeiten

M. Born, S. Niedrig, S. Rademann, M. Winkler: Computational Modellierung des ODP-Traders mit SDL/ASN.1. Oktober 1995.
A. Hoffmann: An OMT Model of the Vending Machine. März 1995.
O. Kath: Simulation von VHDL-Spezifikationen. Dezember 1995.

Dissertationen

Andreas Vogel: Entwurf, Realisierung und Test von ODP-Systmen auf der Grundlage formaler Beschreibungstechniken. November 1995.

Diplomarbeiten

Ulrich Kunitz: ODP-Spezifikation eines verteilten Verzeichnisdienstes. März 1995.
Nils Fischbeck: Automatisches Layout von SDL/GR. April 1995.
Simone Niedrig, Silke Rademann: Eine Methodik für den ODP-Konformitätstest und deren Anwendung auf den ODP-Trader. Dezember 1995.

Lehr- und Forschungseinheit

Systemarchitektur

Leiter:

Prof. Dr. Christoph Polze: Tel.: (030) 20 18 12 32, e-mail: polze@informatik.hu-berlin.de

Mitarbeiter:

Dr. Barbara Burkhard
Dr. Jens-Peter Redlich
Dipl.-Inf. Sven Wischnowsky

Rechnerbetriebsgruppe:

Dr. Jan-Peter Bell
Ing. Gabriele Bärwolff
Dipl.-Ing. Wolfgang Gandre
Frank Wozobule

Sekretariat:

Marita Albrecht: Tel.: (030) 20 18 12 31, e-mail: albrecht@informatik.hu-berlin.de

Tutoren:

Dirk Balfanz
Harald Böhme
Robert Magnus
Dirk Verworner
Uwe Erpel
Henrik Pletat
Oliver Becker
Frank Hesse
Wolf-Dietrich Materna

Am Lehrstuhl Systemarchitektur steht die Architektur von Softwaresystemen im Blickfeld. Die Allgemeinheit der Thematik zwingt zu Auswahl und Spezialisierung. Auf Grund der besonderen Forschungsinteressen werden Projekte zur Telekommunikation und zum Management in verteilten Systemen bearbeitet. Diese Projekte prägen auch das Angebot in der Lehre. Fester Bestandteil des Lehrangebots sind Vorlesungen und Praktika zu UNIX. Betriebssysteme sind als Softwaresysteme komplex genug, um daran Fragen der Systemarchitektur zu studieren. Seit Bestehen des Instituts gehört die Betreuung des hausinternen Rechnernetzes zum Verantwortungsbereich des Lehrstuhls. Die Rechnerbetriebsgruppe sichert den laufenden Betrieb des Netzes. Die Erfahrungen des Rechnerbetriebs werden in Vorlesungen und Seminaren an die Studenten herangetragen. Besonders interessierte Studenten wirken als Tutoren in der Rechnerbetriebsgruppe mit.

Projektbeschreibungen

Projekt: Management Architecture for teleCommunication Services (MACS)

Ansprechpartner: Dr. Barbara Burkhard

In diesem Projekt werden Probleme im Zusammenhang mit dem Management flexibler, verteilter Telekommunikationsanwendungen untersucht. Solche Anwendungen bestehen aus interagierenden Objekten und zeichnen sich vor allem dadurch aus, daß erst zur Laufzeit bestimmt wird, welche Objekte auf welchen Systemen zu einer gewünschten Anwendung konfiguriert werden (late binding). Wir entwickeln eine Managementarchitektur, die dem Rechnung trägt und außerdem verschiedene Sichten (Views) auf eine Anwendung bzgl. Management unterstützt. Als Entwicklungsgrundlage benutzen wir eine SMALLTALK- basierte Verteilte Umgebung (FOCS - Flexible Objectoriented teleCommunication Services), die am Lehrstuhl entwickelt und implementiert wurde.

Zur Zeit werden im Rahmen von Studienarbeiten folgende Teilprobleme behandelt:

Definition und Implementation von Dienstelementen und ihren Managementschnittstellen
Erzeugung von graphischen Managementinterfaces
Definition der Management Views
Entwicklung eines Tools zur Erzeugung von Verträgen zur Dienstnutzung.

Projekt: Flexible Objectoriented teleCommunication System (FOCS)

Ansprechpartner: Dr. Jens-Peter Redlich

Projektförderung: Humboldt-Forschungsfonds

Das Projekt Flexible Objectoriented teleCommunication System (FOCS) wurde im Juli 1995 erfolgreich abgeschlossen. Ziel des Projektes war es, eine Technologie für die Programmierung verteilter objektorientierter Systeme zu entwickeln, die es den Applikationen gestattet, sich dynamisch an mit unterschiedlichen Ressourcen ausgestattete Einsatzumgebungen anzupasssen. Eine prototypisch hergestellte Entwicklungsumgebung ermöglicht experimentelle Analysen von FOCS-Konzepten und die Implementation von Beispielanwendungen. Die Leistungsfähigkeit von FOCS-basierten Anwendungen wurde verschiedenen Interessentenkreisen in mehreren Demos vorgeführt. Die im Rahmen dieses Projektes entwickelten Konzepte bilden die Grundlage für das Ende 1995 begonnene Nachfolgeprojekt MINT (Mobile Intelligent Network Terminal).

Projekt: Mobile Intelligente Netzwerk-Terminals (MINT)

Ansprechpartner: Dr. Jens-Peter Redlich

Aufbauend auf dem in den Vorjahren entwickelten System FOCS (Flexible Object-oriented teleCommunication Services) wird im Rahmen des Projektes MINT eine Architektur für verteilte Systeme entwickelt, die es dem Endnutzer erlauben soll, sich ein beliebiges Endgerät auszusuchen, sich mit diesem an einen (fast) beliebigen Ort der Erde zu begeben und dort seine gewohnte Arbeitsumgebung bereitgestellt zu bekommen. In Abhängigkeit vom ausgewählten Endgerät und von den am jeweiligen Einsatzort real vorhandenen Ressourcen (z. B. Netzwerkzugänge, Displays, Tastaturen, Drucker) wird diese eine jeweils andere konkrete Gestalt annehmen müssen. Die von ihr bereitgestellte Funktionalität, d. h. die Menge der angebotenen Teledienste, soll jedoch stets dieselbe bleiben. Um dies zu erreichen, definiert der Nutzer seine Arbeitsumgebung abstrakt, ohne dabei auf konkrete Endgeräte oder auf Ressourcen aus der Einsatzumgebung Bezug zu nehmen. Technologische Grundlage dafür bildet die Spezifikation von Dienstanbietern über sogenannte ServiceIDs, die im Rahmen des Vorgängerprojektes FOCS entwickelt wurde. Später, d. h. mit einem konkreten Endgerät und in einer konkreten Einsatzumgebung, wird vermöge einer Dienstvermittlungskomponente nach dem Vorbild des FOCS-Brokers bzw. des ODP-Traders für jedes abstrakte Element der virtuellen Arbeitsumgebung eine reale Entsprechung gefunden. Dabei kann es notwendig werden, daß Datenströme konvertiert werden müssen, natürlich ohne dabei die Semantik der Daten zu verändern. Ein Beispiel dafür ist der Teledienst "Email", wenn diesem kein Display, sondern lediglich ein Telefon zur Verfügung steht. In diesem Fall müssen dem Nutzer die für ihn eingegangenen Nachrichten vorgelesen werden. Das Projekt befindet sich noch in der Aufbauphase. Durch Bereitstellung eines Prototypen soll jedoch innerhalb kurzer Zeit das experimentelle Verifizieren der entwickelten Architekturkonzepte möglich sein.

Rechnerbetriebsgruppe: Veränderungen der rechentechnischen Ausstattung des Instituts seit Herbst 1994

Ansprechpartner: Dr. Jan-Peter Bell

1. Ablösung des MX500 durch einen Workstationpool

Im Wintersemester 1994/95 wurde der seit 1990 benutzte Siemensrechner MX500, der nur mit alphanumerischen Terminals ausgerüstet war, durch einen Pool moderner grafikfähiger Workstations ersetzt. Im einzelnen wurde dafür folgende Technik installiert:

20 Workstations SUNsparc5:: 70 MHz, 32-MB-Hauptspeicher, 20"-Farbmonitor, 500 MB Festplatte
2 Server SUNsparc20:: 50 MHz, 32-MB-Hauptspeicher, 17"-SW-Monitor, FDDI, 3-GB-Festplatte

2. NFS-Fileserver für studentische Daten

Zum Wintersemester 1995/96 wurde ein neuer Fileserver für studentische Daten in Betrieb genommen. Dadurch wurde sowohl die Kapazität als auch der Netzwerkdurchsatz erhöht. Die Daten sind in den automatischen Back-up-service des Rechenzentrums einbezogen.

SUNserver1000:

18-GB-Festplattenkapazität, 2 CPU‘s, 256-MB-Hauptspeicher, 6 Netzwerkzugänge, FDDI

- Subnetz 20.0 - zentrale Rechner
- Subnetz 22.2 - SUN-Pool 1
- Subnetz 20.2 - SUN-Pool 2
- Subnetz 22.3 - IBM-Pool
- Subnetz 21.0 - DEC-Pool

3. LINUX-Pool

Zu Beginn des Wintersemesters 1995/96 konnte ein PC-Pool für LINUX in Betrieb genommen werden. Dieser gibt den Studenten die Möglichkeit, das häufig zu Hause genutzte Betriebssystem LINUX auch am Institut zu nutzen und notwendige Tests durchzuführen. Der Pool besteht aus folgenden Geräten:

1 LINUX-Server:: Pentium 90 MHz, 32-MB-Hauptspeicher, 1-GB-Festplatte, CD-ROM, 17"-Farbmonitor
4 LINUX-Workstations:: AMD486DX4 100 MHz, 16-MB-Hauptspeicher, 420-MB-Festplatte, 17"-Farbmonitor

4. Modernisierung von 10 PCs aus dem PC-Pool

Der PC-Pool des Instituts bestand aus 20 Siemens-PCs 386SX aus dem Jahre 1990. Davon konnten im Laufe des Jahres 1995 zehn modernisiert werden. Im einzelnen wurden folgende Komponenten modernisiert: Prozessor auf AMD486DX4 100 MHz, Hauptspeicher auf 8-MB-RAM, moderne Grafikkarte und neuer 17"- Farbmonitor. Damit sind alle für die Ausbildung genutzten Programme wieder lauffähig.

5. Datenprojektor

Zur Verbesserung der Projektionsmöglichkeiten von Daten wurde im Raum 427 ein Datenprojektor Typ Liesegang 1024 installiert. Der Projektor erlaubt die Projektion von Daten on-line. Ein PC ist ständig angeschlossen. SUN-Rechner und MAC-Rechner sind anschließbar. Das Gerät ist auch für die Projektion von Videos geeignet.

6. Terminalserver

Im Wintersemester 1994/95 wurde mit dem Aufbau eines Terminalservers begonnen, der den Studenten und Mitarbeitern die Möglichkeit gibt, die Rechner des Instituts via Telefon zu benutzen. Im Laufe des Jahres wurden insgesamt 6 ZyXEL-Modems Type U-1496EG+ und 6 ELSA-Modems Type MicroLink 28.8TQV installiert. Für die einzelnen Modemtypen wurden Sammelnummern geschaltet.

Folgende Dienste werden z. Z. angeboten: Telnet, Login, SLIP, PPP.

Das Gerät wird von Mitarbeitern und Studenten intensiv genutzt.

Nutzung des Terminalservers:
    
    Zeitraum Nutzer Verbindungen Dauer
     4/95   81      342     138  h
     5/95   151     3015    1215 h
     6/95   165     2755    1161 h
     7/95   166     2890    1249 h
     8/95   160     3136    1249 h
     9/95   187     3858    1077 h
    10/95   199     3781    1193 h

7. Erneuerung des FTP-Servers

Der aus dem Jahre 1991 stammende FTP-Server wurde ständig erweitert und damit zunehmend technisch unzuverlässiger. Im Sommer 1995 wurde der neue FTP-Server SUNsparc5/110 mit 32-MB-Hauptspeicher, 8-GB-Festplatte und DAT-Laufwerk in Betrieb genommen. Er hatte noch 1995 eine Auslastung von:

   Zeitraum Files Mbyte Systeme    täglich Files Mbyte
    4/95    13 683 3 415 546 441 110
    5/95    11 524 2 485 708 360 77
    6/95    17 415 4 673 1078 562 150
    7/95    22 999 5 002 2284 852 185
    8-11/95 62 054 16 141 7482 660 171

8. Erneuerung des NEWS-Servers

Im Sommer 1995 konnte der veraltete NEWS-Server durch einen neuen NEWS- Server des Typs SUNsparc5/110 (32-MB-Hauptspeicher, 4-GM-Festplatte) ersetzt werden. Durch den neuen Rechner konnten die Verweilzeiten für wichtige News-Gruppen verlängert werden. Z. Z. werden ca. 6300 Gruppen angeboten. Der NEWS-Server versorgt 150 Workstations mit NEWS. Täglich werden ca. 800 Artikel ge- lesen.

9. Aufbau des WWW-Servers

Der WWW-Server ist zu einem festen Bestandteil des Instituts geworden. Er erlaubt den Zugriff auf viele Datenbestände des Instituts und anderer Server in der Welt. Nutzung des WWW-Servers:

Zeitraum Dateien Mbyte Systeme  täglich Dateien Mbyte
    5/95    296 306 1 093 4 923 10 217  37
    6/95    336 319 1 376 6 956 11 211  45
    7/95    301 816 1 278 8 582 9 736   41
    8/95    312 252 1 133 10 022 9 785  35
    9/95    382 769 1 486 12 553 12 759     49
    10/95   420 720 1 765 15 497 13 573 56

10. Netzwerkinfrastruktur

Die Netzinfrastruktur wurde vervollständigt, drei Server an den FDDI-Ring angeschlossen. Beide zentralen Router wurden mit FDDI-Adaptern ausgestattet, so daß der Durchsatz zwischen den einzelnen Netzsegmenten verbessert werden konnte. Weiterhin wurden fünf FDDI-Adapter für Workstations beschafft, die die Anbindung weiterer Lehrstühle an den FDDI-Ring ermöglichen.

Eine ATM-Teststrecke zum Hauptgebäude wurde in Betrieb genommen. Der ATM-Switch wurde auf 12 155-MBit/sec-Ports aufgerüstet, so daß dem weiteren ATM-Ausbau nichts im Wege steht. Weiterhin wurden 2 ATM-Adapter für Workstations beschafft. Damit kann ein lokaler ATM-Pool für Testzwecke eingerichtet werden.

11. Modernisierungen und Erweiterungen in den Lehrstühlen

Die rechentechnische Ausrüstung der einzelnen Lehrstühle konnte im Jahre 1995 verbessert werden. Am Lehrstuhl Automaten- und Systemtheorie wurde ein Workstationpool mit 10 SUN-Workstations in Betrieb genommen werden. Am Lehrstuhl Rechnerorganisation und -kommunikation konnte das ATM-Testfeld eingeweiht werden. Die Beschaffung eines weiteren Workstationpools für den Lehrstuhl Künstliche Intelligenz steht unmittelbar vor dem Abschluß. Außerdem wurden an einzelnen Lehrstühlen Workstations und PC‘s gekauft.

Veröffentlichungen und Vorträge

V. Tsaoussidis, M. Flasza: A Service-oriented Management System. Proceedings of the Engineer‘s Conference at Networld + INTEROP 95, Las Vegas, Nevada, März 1995.
J.-P. Redlich: FOCS - Eine Plattform für die Entwicklung flexibler Teledienste. Vorstellung der Dissertation, Universität Karlsruhe, Institut für Telematik, 3.5.1995.
H. Böhme: Module unter Linux. Linux/Internet-Kongress, 11.-12. Mai 1995, Berlin.
J.-P. Redlich: Personalisierte Teledienste mit FOCS. Universität Osnabrück, Institut für Mathematik und Informatik, 22. 5. 1995.
D. Balfanz: Contracts in a Commercial Teleservice Environment. Vortrag, First International Workshop on High Speed Networks and Open Distributed Platforms, 13.-15. Juni 1995, St. Petersburg.
B. Burkhard; J.-P. Redlich: Management of Flexible, Personalized Teleservices. Vortrag, First International Workshop on High Speed Networks and Open Distributed Platforms, 13.-15. Juni 1995, St. Petersburg.
J.-P. Redlich: Eine objektorientierte Architektur für die Entwicklung von flexiblen Telekommunikations-Anwendungen. Dissertation, Humboldt-Universität zu Berlin, Juli 1995, Fortschritt-Bericht VDI-Verlag, Reihe 10, Nr. 378: Informatik.
C. Polze: Folien zum Kurs Software-Architektur UNIX. Informatik-Bericht Nr. 47, August 1995.
J.-P. Redlich: Orts- und endgeräteunabhängige Kommunikationsdienste. ENC-Heidelberg, IBM, 24.10.1995.
J.-P. Redlich: Ein Architekturkonzept für selbstadaptierende Applikationen. UNIX/MAIL 5/95.
B. Burkhard: Das Projekt MACS. Vortrag zum Tag der Informatik der Humboldt-Universität, 9.11.1995
B. Burkhard: MACS - Eine Architektur zum Management verteilter Anwendungen. Universität Karlsruhe, Institut für Telematik, Dezember 1995.
S. Wischnowsky: Computer Supported Cooperative Work. Forschungsseminar 2.11.1995
B. Burkhard: Application management implemented as a distributed application - the MACS project. Poster, eingereicht zur IFIP/IEEE International Conference on Distributed Platforms (ICDP‘96), 27.2. - 1.3.1996, Dresden.
M. Beck; H. Böhme; M. Dziadzka; U. Kunitz; R. Magnus; D. Verworner: Linux-Kernel- Programmierung. Algorithmen und Strukturen der Version 1.2, Addison-Wesley Publishing Company, 3. Auflage 1995.

Weitere Aktivitäten

Vorführung des Prototypsystems FOCS (Beleg von Funktionalität, Flexibilität, Adaptierbarkeit sowie der Audiokomponente). Institutsintern mit den Gästen Prof. Goos, Prof. Popescu-Zeletin. Januar 1995.
Demonstration des Systems FOCS für Vertreter von ALCATEL. Januar 1995.
Demonstration von Schreiner‘s Compiler Development Kit. März 1995.
Demonstration (remote) von FOCS in Karlsruhe (Institut für Telematik). Mai 1995.
Demonstration (remote) von FOCS in Osnabrück (Institut für Mathematik und Informatik). Mai 1995.
Forum über den Einsatz von Plan 9 im produktiven Betrieb an der Universität Osnabrück (Dr. H.-P. Bischof). November 1995.
Studentisches Seminar zu Linux über beide Semester.

Studienarbeiten

Ingo Noka: SMS (Subscription Message Service) - Ein Protokoll zum Nachrichtenaustausch auf der Basis von Abonnements. Juni 1995.
Oliver Becker: Graphische Komposition von Dienstbausteinen in FOCS - Der FOCS-Composer. August 1995.
Robert Magnus: Xtuto - Ein Tutorial für XRN. September 1995.
Tzvetan Petrov: IBM-Terminalemulator für IBM ARTour. September 1995.

Dissertationen

Vassilios Tsaoussidis: Information Processing in a Service-Oriented Management System. März 1995.
Jens-Peter Redlich: Eine objektorientierte Architektur für die Entwicklung von flexiblen Telekommunikations-Anwendungen. Juli 1995

Diplomarbeiten

Dirk Balfanz: Eine vertragsbasierte Architektur für die Kostenabrechnung in flexiblen Telekommunikationssystemen. Juni 1995.
Uwe Erpel: Dynamische Präsentationssteuerung in multimedialen Systemen. Juli 1995.
Henry Krause: Die Programmierung Verteilter Systeme mit Teleagenten. September 1995.
Tzvetan Petrov: Remote printing in mobilen, heterogenen Netzen. Dezember 1995.

Lehr- und Forschungseinheit

Softwaretechnik und Theorie der Programmierung I

Leiter:

Prof. Dr. Wolfgang Reisig: Tel.: (030) 20 18 12 20, e-mail: reisig@informatik.hu-berlin.de

Mitarbeiter:

Dr. Jörg Desel
Prof. Dr. Bodo Hohberg
Dr. Ekkart Kindler
Dipl.-Inf. Hagen Völzer
Dr. Rolf Walter

Sekretariat:

Birgit Heene: Tel.: (030) 20 18 12 19, e-mail: heene@informatik.hu-berlin.de

Tutoren:

Dipl.-Inf. (FH) Karsten R. Heidtke
Tobias Vesper
Juliane Dehnert
Hagen Völzer
Thomas Ritz

Jörn Freiheit

Gastwissenschaftler:

Dr. Christel Baier (Universität Mannheim)
Prof. Irina Lomazova (Universität Pereslavl, Rußland)
Dott. Katia Petruni (Universität Mailand, Italien)
Prof. Dr. Thiagarajan (SPIC Science Foundation Madras, Indien)
Prof. Stefan Tiberiu Letia (Universität Cluj-Napoca, Rumänien)

Den Forschungsschwerpunkt des Lehrstuhls bilden derzeit verteilte Algorithmen, insbesondere ihre Modellierung und der Beweis ihrer Korrektheit. Neue theoretische Konzepte werden zum verteilten Management verteilter Ressourcen für Kommunikationsprotokolle und für Konsensalgorithmen eingesetzt. Mittelfristig entsteht eine Technik, um verteilte Algorithmen intuitiv und formal einfach zu modellieren und zu analysieren.

Projektbeschreibungen

Projekt: Modellierung und Verifikation verteilter Algorithmen

Ansprechpartner: Prof. Dr. Wolfgang Reisig

Beteiligte Mitarbeiter:

Dr. Rolf Walter
Dr. Ekkart Kindler
Dr. Jörg Desel
Hagen Völzer
Juliane Dehnert
Jörn Freiheit

Projektförderung:

DFG-Projekt "Verteilte Algorithmen",
Esprit-Working-Group CALIBAN,
Teilprojekt YE1 des Sonderforschungsbereiches 342 der TU München

Zusammenarbeit: TU München, Sonderforschungsbereich 342: Prof. Dr. Javier Esparza, Dominik Gomm, Angelika Mader

Verteilte Algorithmen werden in der Literatur im wesentlichen programmiersprachlich beschrieben und informell verifiziert. Konzepte und Methoden zur formalen Darstellung und zur formalen Verifikation verteilter Algorithmen werden in diesem Projekt entwickelt.

Konzepte zur Modellierung verteilter Algorithmen sind nur zusammen mit angepaßten, einfachen, intuitiven Beweistechniken erfolgreich. Solche Techniken wurden und werden in diesem Projekt entwickelt. Dabei wird nicht ein möglichst ausdrucksstarker Formalismus angestrebt, sondern wenige einfache Konzepte mit einer Ausdruckskraft, die für die üblichen verteilten Algorithmen ausreichen. In der Literatur vorhandene Techniken, verteilte Algorithmen zu verifizieren, werden auf Petrinetze übertragen, dort untersucht und gegebenenfalls spezialisiert.

Erste Ergebnisse des Projektes zeigen, daß die formale Strenge des Ansatzes die intuitive Verständlichkeit der so formulierten Algorithmen nicht beeinträchtigt, sondern im Gegenteil erhöht: Sicherheits- und Lebendigkeitseigenschaften sind für verteilte Algorithmen klassische theoretische Konzepte, die der partiellen bzw. totalen Korrektheit in sequentiellen Algorithmen entsprechen. Diese Konzepte wurden für nichtsequentielle Abläufe verallgemeinert, Übertragbares wurde festgehalten und Grenzen aufgezeigt [Kindler 95c].

Nichtsequentielle Abläufe sind wesentlich, um intuitiv einfache Begriffe zu formalisieren. So wurde ein "Rundenbegriff" gebildet [Walter 95a, Reisig 95a], der intuitiv einfach ist, die wesentliche Idee eines Algorithmus verdeutlicht und die Verifikation unterstützt. In [Kindler et al. 95a] wurde ein spezielles Fairness-Konzept eingeführt und gezeigt, wie verschiedene Mutex-Algorithmen sich einheitlich unter Verwendung von Ableseregeln und Beweisgraphen korrekt beweisen lassen.

In [Desel et al. 95c] wurde vorgeführt, wie durch den Wechsel zwischen verschiedenen ungewöhnlichen Sichtweisen auf einen verteilten Algorithmus ein existierender Korrektheitsbeweis wesentlich vereinfacht werden kann. In [Walter 95a] wurde eine Reihe von nichttrivialen, aber kleinen verteilten Algorithmen untersucht und mit einem zusammenhängenden Verifikationsformalismus korrekt bewiesen. Vergleichbare Konzepte sind in [Reisig 95a] zusammengefaßt. Erste Fallstudien [Völzer 95a] zeigen, daß die vorgeschlagenen Konzepte auch auf High-level-Petrinetzmodelle übertragbar sind und welche neuen Verifikationstechniken für große Algorithmen vielversprechend sind.

Ausblick: Grössere verteilte Algorithmen müssen mit High-level-Petrinetzmodellen modelliert werden. In diesem Projekt wird nach weiteren, speziellen High-level-Konzepten gesucht, die die Modellierung und Verifikation von Netzwerkalgorithmen unterstützen. Eine Reihe von Algorithmen (Mutex-, Cross-talk-, Echo-Algorithmus) bilden die Basis für komplexere Algorithmen. Weitere solche Basisalgorithmen zu benennen, die typische Teilaufgaben klassischer verteilter Algorithmen lösen, ist ein Forschungsproblem.

Projekt: Konsens-Algorithmen

Ansprechpartner: Prof. Dr. Wolfgang Reisig

Beteiligte Mitarbeiter: Hagen Völzer

Projektförderung: DFG-Projekt "Konsens-Algorithmen".

Zusammenarbeit: Lehrstuhl Rechnerorganisation und Kommunikation, Prof. Dr. Miroslaw Malek

Die zunehmende Verfügbarkeit preiswerter Kommunikationstechniken beschleunigt den Übergang von zentralen zu verteilten Rechnerkonfigurationen. Dabei bildet Konsens ein herausragendes Paradigma. Ziel des Projektes ist es, Konsenstechniken weiterzuentwickeln. Anhand von Fallstudien werden Prinzipien herausgearbeitet, die typischerweise in den Algorithmen vorkommen und Techniken zum Beweis der Korrektheit von Konsensalgorithmen entwickelt.

Projekt: Modularität und Kompositionalität

Ansprechpartner:

Prof. Dr. Bodo Hohberg
Dr. Ekkart Kindler

Projektförderung: Teilprojekt YE1 des Sonderforschungsbereiches 342 der TU München

Zusammenarbeit: TU München, Sonderforschungsbereich 342, Gruppe des Teilprojekts A3

Verteilte Systeme sind häufig in eine Umgebung eingebettet, auf deren Ereignisse bzw. Eingabe das verteilte System reagiert. Solche Systeme nennt man reaktiv. Das Verhalten von reaktiven Systemen kann meist nur in Abhängigkeit von bestimmten Anforderungen an das Verhalten der Umgebung erfüllt werden und wird auch deshalb häufig in der Form "wenn die Umgebung erwartetes Verhalten zeigt, dann gewährleistet das System gewünschte Eigenschaften" beschrieben. Diese Art der Verhaltensbeschreibung nennt man Rely-guarantee-Spezifikation. Damit ist es auch möglich, verteilte Systeme aus Komponenten zusammenzusetzen und aus ihren Verhältnisbeschreibungen das Verhalten des Gesamtsystems zu gewinnen (Kompositionalität).

Bisher wurden überwiegend die theoretischen Grundlagen für kompositionale Beweismethoden untersucht. In [Kindler 95b] wurde das Zusammenspiel einer einfachen Kompositionsregel mit einer anderen Beweisregel, der Substitutionsregel, untersucht. Es zeigt sich, daß die Kombination beider Regeln große Sorgfalt erfordert. In der Dissertation [Kindler 95c] wurde ein kompositionales Petrinetzmodell eingeführt. Aufbauend auf diesem Modell lassen sich Systemkomponenten im Rely-Guarantee-Stil spezifizieren. Eine Spezifikation kann in Spezifikationen für Teilkomponenten zerlegt werden, die dann unabhängig voneinander implementiert werden können.

Werkzeuge können ebenfalls von einer Zerlegung in Komponenten profitieren. Untersucht wird eine Möglichkeit, die Komplexität der Analysealgorithmen dadurch zu verringern, daß der wesentliche Teil der Analyse in einem ersten Schritt getrennt für die Komponenten ausgeführt wird. Der erste Schritt liefert für die Komponenten Verhaltensbeschreibungen, die kompositional sind. Bei einer Wiederverwendung muß der erste Schritt nicht wiederholt werden.

Projekt: Kausalitätsbasierte Beweismethoden

Ansprechpartner: Dr. Ekkart Kindler

Zusammenarbeit:

TU München, Sonderforschungsbereich 342, Prof. Dr. Rudolph Bayer, Andreas Listl, Dominik Gomm und
Humboldt-Universität zu Berlin, Prof. Johann-Christoph Freytag, Ph. D. und Mitarbeiter

In den vorangegangenen Jahren hat sich gezeigt, daß man die kausalen Abhängigkeiten von Ereignissen in einem Systemablauf benutzen kann, um Eigenschaften von Systemen zu spezifizieren. Hier bieten sich Petrinetze, deren Abläufe in natürlicher Weise die kausalen Abhängigkeiten von Ereignissen beschreiben, zur Modellierung solcher Systeme an. Es hat sich herausgestellt, daß sich dieses kausalitätsbasierte Spezifizieren insbesondere zur Beschreibung und Verifikation von Datenkonsistenzprotokollen eignet. In diesem Jahr wurde das in den Fallstudien benutzte Petrinetzmodell formalisiert und das Ablaufmodell geeignet erweitert. Auf dieser Basis wurden einige Beweismethoden formalisiert. Wichtigstes Anliegen dieses Projekts bleibt die Entwicklung einer entsprechenden Methodik.

Projekt: Konzeption, theoretische Fundierung und Validierung einer anwendungsbezogenen Petrinetztechnologie

Ansprechpartner:

Prof. Dr. Wolfgang Reisig
Dr. Rolf Walter

Beteiligte Mitarbeiter:

Prof. Dr. Bodo Hohberg
Dr. Ekkart Kindler

Zusammenarbeit:

TU Berlin, Prof. Dr. Herbert Weber, Prof. Dr. Hartmut Ehrig und
Universität der Bundeswehr München, Prof. Dr. R. Onken, W. Ruckdeschel

In der Hardware- und Softwareindustrie wächst das Interesse an Entwurfsmethoden, die eine zuverlässige formale Grundlage haben. Nur solche Methoden können die Korrektheit komplexer Systeme und ihre Anpaßbarkeit an veränderte Anforderungen gewährleisten. Eine Basis dafür sind Petrinetze. In vielen Varianten sind Petrinetze in den letzten Jahren in Projekten industrieller Größe erfolgreich eingesetzt worden. Ihre Akzeptanz in der Praxis stiege erheblich, wenn einheitliche Vorgehensweisen gefunden würden und die theoretische Forschung über Petrinetze mehr praktische Anforderungen berücksichtigte. Ziel des Forschungsprojektes ist es, die grundlegenden Konzepte und deren orthogonale Komposition zu vereinfachen und zu erweitern. Entstehen soll ein Petrinetz-Baukasten, der eine systematische Zusammenfassung von Resultaten der anwendungsorientierten Grundlagenforschung darstellt und den Transfer theoretischer Ergebnisse in die Praxis unterstützt.

Projekt: Linear-Algebraische Analysealgorithmen für Petrinetze

Ansprechpartner:

Dr. Jörg Desel
Dr. Rolf Walter

Projektförderung: ESPRIT-Working-Group CALIBAN

Zusammenarbeit:

TU München: Prof. Dr. Javier Esparza, Micaela Radola und
Humboldt-Universität Berlin, Lehrstuhl für Automaten und Systemtheorie: Dr. Klaus-Peter Neuendorf

Mit dem Konzept der Stellen- und Transitionen-Invarianten wurden schon in den 70er Jahren Methoden der linearen Algebra für den Nachweis dynamischer Eigenschaften von Petrinetzen verwendet: Jedem Netz wird ein lineares Gleichungssystem zugeordnet, aus dessen Lösungen solche Eigenschaften ableitbar sind.

In den letzten Jahren konnten zunehmend weitere, tieferliegende Konzepte der linearen Algebra zur Analyse von Petrinetzen nutzbar gemacht werden. Dazu gehören lineare Ungleichungssysteme, Gleichungssysteme über Mod-n-Körpern und auf dem Rang von Matrizen aufbauende Eigenschaften.

In diesem Projekt werden linear-algebraische Methoden zusammengestellt und auf verschiedenartige Fragestellungen beliebiger und spezieller Petri-Netze angewendet. Insbesondere wird untersucht, wie sich die Eigenschaften verteilter Algorithmen in linear algebraischer Form darstellen und beweisen lassen. Dies betrifft nicht nur die Verwendung von Invarianten zum Beweis von Sicherheitseigenschaften sondern auch linear algebraisch basierte Konzepte zur Untersuchung von Progress- und Lebendigkeitseigenschaften. Diese Forschungsansätze sind insbesondere im Rahmen der ESPRIT-Working-Group CALIBAN verfolgt worden. Eine Zusammenfassung findet sich im Tagungsband der an der Humboldt-Universität organisierten Abschlußtagung des Projektes [Desel 95b].

Projekt: Simulation mit verteilten Abläufen

Ansprechpartner: Dr. Jörg Desel

Projektförderung: DFG-Projekt Verifikation von Informationssystemen durch Auswertung halbgeordneter Petrinetzabläufe

Zusammenarbeit: Universität Karlsruhe (TH): Dr. Andreas Oberweis

Die Verifikation von Informationssystemen bzw. ihrer formalen Modelle durch Simulation scheitert oft an der großen Anzahl verschiedener Ausführungsfolgen. Dies giltverstärkt für verteilte Informationssysteme: Die Anzahl der Abläufe wächst dort exponentiell mit dem Grad der Nebenläufigkeit. Die systematische Konstruktion und Analyse der entsprechend den Kausalitätsbeziehungen halbgeordneten Abläufe überwindet dieses Problem. In diesem Projekt werden Modelle von Informationssystemen und ihre Abläufe durch höhere Petrinetze beschrieben. Für die Formulierung von dynamischen Systemeigenschaften wird eine anschauliche graphische Spezifikationssprache verwendet, deren Ausdrücke im Netzmodell integriert sind und die ohne Verwendung eines zusätzlichen Formalismus der temporalen Logik auskommt. Es werden Spezifikationen unterstützt, die kausal aufeinanderfolgende Ereignisse (bzw. lokale Zustände) fordern oder verbieten, was in herkömmlichen, auf Sequenzen und globalen Zuständen basierenden Spezifikationsmethoden nicht möglich ist. Ziel des Projekts wird sein, im Rahmen einer Methodik zur evolutionären Informationssystementwicklung werkzeugunterstützt Systemeigenschaften formulieren zu können und diese (halb-) automatisch durch Simulation und Analyse der Abläufe zu verifizieren.

Projekt: Specification and Implementation of Distributed Algorithms for Massively Parallel Systems, based on Petri Nets

Ansprechpartner: Prof. Dr. Wolfgang Reisig

Beteiligte Mitarbeiter: Dr. Jörg Desel

Projektförderung: Bundesministerium für Bildung, Wissenschaft, Forschung und Technologie

Zusammenarbeit: Technical University Santiago, Chile, Prof. César Fernandez, Dr. Mauricio Solar

Verteilte Algorithmen werden in der Literatur im wesentlichen programmiersprachlich beschrieben. Es wird an Hand von Fallstudien untersucht, wie der Entwurf verteilter Algorithmen für massiv parallele Rechnersysteme durch die Verwendung von Petrinetzen verbessert werden kann. Weiter wird die anschließende Implementation betrachtet. Ziel ist es, eine Entwurfstechnik herauszuarbeiten und ihre Adäquatheit durch die Fallstudien zu belegen.

Projekt: Algorithmen und Werkzeuge für Petrinetze

Ansprechpartner: Dr. Jörg Desel

Beteiligte Mitarbeiter:

Prof. Dr. Bodo Hohberg
Dr. Ekkart Kindler

Projektförderung: Teilprojekt A3 des Sonderforschungsbereichs 342 der TU München

Zusammenarbeit:

Universität Karlsruhe (TH), Dr. Andreas Oberweis und
Universität Oldenburg, Prof. Dr. Michael Sonnenschein

Viele Werkzeuge für Petrinetze erlauben nur das Editieren und Durchspielen (Simulation) von Netzen. Theoretiker dagegen studieren z.T. nie implementierte Verfahren für die Petrinetz-Analyse, oft in eingeschränkten Netzklassen. Es fehlt sowohl an Werkzeugunterstützung für die Theoretiker, mit denen sie prototypisch ihre Charakterisierungen und Algorithmen erproben und vergleichen können, als auch an Theorieunterstützung für Werkzeugentwickler und -anwender, denn oft können theoretische Erkenntnisse bei konkreten Anwendungen nicht unmittelbar genutzt werden. Zum Projektthema wurde in Zusammenarbeit mit der Humboldt-Universität an der Universität Oldenburg ein Workshop veranstaltet, auf dem ca. 20 Arbeiten vorgestellt wurden und an dem etwa 60 Forscher teilnahmen. Auf dieser Tagung wurde eine in diesem Projekt entwickelte Grobkonzeption einer neuartigen Werkzeugumgebung vorgestellt, die auch im Programmieren nichtversierten bzw. nichtinteressierten Theoretikern erlaubt, algorithmische Ideen zur maschinellen Analyse prototypisch zu implementieren und zu bewerten. Schwerpunkte dieser Konzeption sind der konsequent objekt-orientierte Aufbau und die Verwendung existierender sehr komfortabler Oberflächen. Diese Ideen basieren auf Erfahrungen, die bei der Entwicklung eines Petrinetz-Werkzeuges für algebraische Netze im Sonderforschungsbereich 342 gemacht wurden. Aufgrund der Vielzahl von verschiedenen Netzmodellen und bereits existierender Werkzeuge gibt es hier noch viele offene Fragen.

Projekt: Free-Choice-Petrinetze

Ansprechpartner: Dr. Jörg Desel

Zusammenarbeit: TU München, Prof. Dr. Javier Esparza

Free-Choice-Petrinetze stellen einen besonders guten Kompromiß zwischen Ausdruckskraft und Komplexität der Analyse dar. Während für Free-Choice-Petrinetze eine Vielzahl nichttrivialer Charakterisierungen dynamischer Eigenschaften gezeigt werden konnte, gelten nur wenige dieser Eigenschaften noch für leichte Verallgemeinerungen dieser Klasse. Die Forschungsarbeiten an diesem Projekt fanden ihren Abschluß mit dem unter [Desel et al. 95a] angegebenen Buch.

Veröffentlichungen und Vorträge

Publikationen

[Desel et al. 95a] J. Desel, J. Esparza: Free Choice Petri nets. Cambridge Tracts in Theoretical Computer Science No. 40, Cambridge University Press, 1995.
[Desel 95b] J. Desel (Herausgeber): Structures in Concurrency Theory. Proceedings of the International Workshop on Structures in Concurrency Theory (STRICT). Berlin, Springer-Verlag, 1995.
[Desel et al. 95c] J. Desel, E. Kindler, T. Vesper, R. Walter: A Simplified Proof for a Self-Stabilizing Protocol: A Game of Cards. Information Processing Letters 54, 1995.
[Desel et al. 95d] J. Desel, E. Kindler, R. Walter: The Game of Tokens: A Collection of Proofs. Petri Net Newsletter No. 48, Mai 1995.
[Desel et al. 95e] J. Desel, J. Esparza: Shortest paths in reachability graphs. Journal of Computer and System Science 51, No. 2, 314-323, 1995.
[Desel 95f]. J. Desel (Herausgeber): Structures in Concurrency Theory (STRICT). Collection of Abstracts, Hildesheimer Informatik-Berichte Nr.11/95, Universität Hil- desheim, Institut für Informatik, 1995.
[Desel 95g] J. Desel, A. Oberweis: Verifikation von Informationssystemen durch Auswertung halbgeordneter Petrinetz-Abläufe: theoretische Untersuchungen, Methodik und Werkzeuge - eine Projektübersicht. Forschungsbericht des Instituts für Angewandte Informatik und Formale Beschreibungsverfahren der Universität Karlsruhe (TH), Nr. 324, 1995.
[Desel 95h] J. Desel, H. Fleischhack, A. Oberweis, M. Sonnenschein: 2. Workshop Algorithmen und Werkzeuge für Petrinetze. Workshop der GI-Fachgruppe 0.0.1 "Petrinetze und verwandte Systemmodelle", Bericht der Arbeitsgruppe Informatik-Systeme, FB Informatik, Universität Oldenburg,1995.
[Kindler et al. 95a] E. Kindler, R. Walter: Message Passing Mutex. In Proceedings Structures in Concurrency Theory, Workshops in Computing, Springer-Verlag, Mai 1995.
[Kindler 95b] E. Kindler: Invariants, composition, and substitution. Acta Informatica 32, Juni 1995.
[Kindler 95c] E. Kindler: Modularer Entwurf verteilter Systeme mit Petrinetzen. EDITION VERSAL 1, W. Reisig (Hrsg.), Bertz Verlag, 1995.
[Kindler 95d] siehe [Desel et al. 95c]
[Kindler 95e] siehe [Desel et al. 95d]
[Kindler et al. 95f] E. Kindler, R. Walter: Arc-Typed Petri Nets. Informatik-Bericht Nr. 50, Humboldt- Universität zu Berlin, Dezember 1995.
[Reisig 95a] W. Reisig: Correctness Proofs of Distributed Algorithms. In K. P. Birman et al. (Ed.): Theory and Practice in Distributed Systems Lecture Notes in Computer Science 938, 164 - 177, Springer- Verlag, 1995.
[Reisig 95b] W. Reisig: Petri Net Models of Distributed Algorithms. In Leeuven, J. van (Ed.): Computer Science Today: Recent Trends and Developments. /Invited contribution. Lecture Notes in Computer Science 1000, 441 - 454, Springer-Verlag, 1995. auch: Informatik-Bericht Nr. 48, Humboldt- Universität zu Berlin, August 1995.
[Völzer 95a] H. Völzer: Verifikation Verteilter Algorithmen mit Algebraischen Netzen. Diplomarbeit an der Humboldt-Universität zu Berlin, Oktober 1995.
[Walter 95a] R. Walter: Petrinetzmodelle verteilter Algorithmen - Beweistechnik und Intuition. EDITION VERSAL 2, W. Reisig (Hrsg.), Bertz Verlag, 1995.
[Walter 95b] R. Walter: Races in Rounds (Cover Picture Story). Petri Net Newsletter No. 48, 3-6, 1995.
[Walter 95c] siehe [Kindler et al. 95a]
[Walter 95d] siehe [Kindler et al. 95f]

Vorträge

Dr. Jörg Desel
- A game of cards. Kolloquium des Institut für Informatik der Universität Hildesheim, Mai 1995.
- Place/transition systems. International course on Petri nets, Campina Grande (Brasilien), November 1995.
- Invariants of Petri nets. International course on Petri nets, Campina Grande (Brasilien), November 1995.
- Free-choice systems. International course on Petri nets, Campina Grande (Brasilien), November 1995.
- Anwendungen linearer Methoden bei Petrinetzen. Kolloquium des Institutes für Informatik der HUB, Dezember 1995.
Dr. Ekkart Kindler
- Der Berliner Sommerhit: Das Bierdeckelproblem. Workshop SFB 342 TP A3/A6/YE2, TU München, Januar 1995.
- Message Passing Mutex: International Workshop on Structures. In: Concurrency Theory, Berlin, Mai 1995.
- Distributed Algorithms: Modelling and Analysis with Petri Nets. Advanced Tutorial, Turin, Italien, Juni 1995.
- Modularer Entwurf verteilter Systeme. Promotionsvortrag, TU München, Juli 1995.
- Serialisierbarkeit leicht gemacht. Humboldt-Universität zu Berlin, Tag der Informatik, Berlin, November 1995.
Dr. Rolf Walter
- Distributed Algorithms: Modelling and Analysis with Petri Nets. Advanced Tutorial, Turin, Italien, Juni 1995.
- Distributed Algorithms: Modelling and Analysis with Petri Nets. Advanced Tutorial, Durham, USA, Oktober 1995.
Prof. Wolfgang Reisig
- Proving Progress Properties of Distributed Algorithms. Eingeladener Vortrag, Universität Helsinki, Finnland, März 1995.
- Informal Introduction to Petri Nets. Advanced Tutorial, Turin, Italien, Juni 1995.
- Distributed Algorithms. Advanced Tutorial, Turin, Italien, Juni 1995.
- Verteilte Algorithmen: Modellierung und Analyse mit Petrinetzen. Kolloquiumsvortrag, TU München, November 1995.
- Informal Introduction to Petri Nets. Advanced Tutorial, Campina Grande, Brasilien, November 1995.
- Distributed Algorithms. Advanced Tutorial, Campina Grande, Brasilien, November 1995.

Weitere Aktivitäten

Mitglied in Programmkomitees

Dr. Jörg Desel
- Programmkomitee-Vorsitz: STRICT: Structures in Concurrency Theory. Berlin, Mai 1995.
- XVI International Conference on Application and Theory of Petri Nets. Turin, Juni 1995.
Prof. Dr. Wolfgang Reisig
- Petri Nets and Performance Models (PNPM). 1995.
- STRICT: Structures in Concurrency Theory. Berlin, Mai 1995.
- Co-Chair: 17. International Conference on Application and Theory of Petrinets. Osaka, Japan, 1996.
- Advanced course on Petrinets. Dagstuhl 1996.
- Workshop on Discrete Event Systems (WODES) 96. Edinburgh, 1996.

Gutachter für Zeitschriften

Dr. Jörg Desel
- ACTA Informatica
- Theoretical Computer Science (TCS)
- Zentralblatt für Mathematik
Dr. Ekkart Kindler
- Acta Informatica
Dr. Rolf Walter

- Theoretical Computer Science (TCS)
  Gutachter für Konferenzen
Dr. Jörg Desel
- Application and Theory of Petri Nets
- Hawaii International Conference on System Sciences
- International Colloqium on Automata, Languages and Programming (ICALP)
- Mathematical Foundation of Computer Science (MFCS)
- Parallel Architectures and Languages Europe (PARLE)
- Symposium on Theoretical Aspects of Computer Science (STACS)
Dr. Ekkart Kindler
- Petrinetz-Konferenz 1995
- IFIP Working Conference 1995
Dr. Rolf Walter
- Petrinetz-Konferenz 1995

Sonstiges

Dr. Jörg Desel
- Koordinator der TU München für ESPRIT-Basic-Research-Projekt CALIBAN: Causal Calculi Based on Nets.
- Projektleiter an der Humboldt-Universität Berlin für das ESPRIT-Basic-Research-Projekt CALIBAN.
- Stellvertretender Sprecher der Fachgruppe 0.0.1 der Gesellschaft für Informatik: Petrinetze und verwandte Systemmodelle.
- Verantwortlicher Redakteur der von der Gesellschaft für Informatik herausgegebenen Zeitschrift Petri Net Newsletter.
- Gründungsmitglied der GI-Arbeitsgruppe Petrinetze und Informationssysteme in der Praxis.
- Mitorganisator des Workshops Algorithmen und Werkzeuge für Petrinetze. Oktober 1995 in Oldenburg.
- Mitglied des Sonderforschungsbereiches SFB 342: Methoden und Werkzeuge für die Nutzung paralleler Rechnerarchitekturen.
- Projekleiter und Hauptantragsteller des DFG-Projektes: Verifikation von Informationssystemen durch Auswertung halbgeordneter Petrinetz-Abläufe.
- Organisation und Durchführung der Internationalen Tagung STRICT: Structures in Concurrency Theory.
Prof. Dr. Wolfgang Reisig
- Steering-Komitee Conference on Application and Theory of Petri Nets.
- Mitglied der EG-Arbeitsgruppe Formal Methods in Europe.
- Vertreter der HUB im Fakultätentag Informatik.
- Mitglied im Graduiertenkolleg Kooperation und Ressourcenmanagement in verteilten Systemen, München.
- Gutachter für verschiedene Zeitschriften, Fachtagungen und NSF.

Dissertationen

Ekkart Kindler: Modularer Entwurf verteilter Systeme mit Petrinetzen. Juli 1995.
Rolf Walter: Petrinetzmodelle verteilter Algorithmen - Beweistechnik und Intuition. Juli 1995.
Dominik Gomm: Modellierung und Analyse verzögerungsunabhängiger Schaltungen mit Petrinetzen. Dezember 1995.

Diplomarbeiten

Hagen Völzer: Verifikation Verteilter Algorithmen mit Algebraischen Netzen. Oktober 1995.

Lehr- und Forschungsgebiet

Softwaretechnik und Theorie der Programmierung II

Leiter:

Prof. Dr. Klaus Bothe: Tel.: (030) 201812 78, e-mail: bothe@informatik.hu-berlin.de

Mitarbeiter:

Dr. Frank Müller
Dipl.-Phys. Ulrich Sacklowski
Dipl.-Math.-Inf. Dragan Macos (Promotionsstudent)

Sekretariat:

Ulrike Scholz: Tel.: (030) 20 18 12 77, e-mail: uscholz@informatik.hu-berlin.de

Tutoren:

Jan Wendler
Daniel Schulz
André Baresel

Die gegenwärtigen Arbeitsschwerpunkte der Gruppe sind: Programmiersprachen, Compilerbau und Softwaretechnik. Im Zentrum aktueller Aktivitäten steht der Compilerbau. Hier werden Projekte zur Quelltexttransformation, zur Codeoptimierung sowie zur funktionalen Programmierung verfolgt. Einen weiteren Schwerpunkt bilden parallele, verteilte und responsive Umgebungen. In der Ausbildung wurden Lehrveranstaltungen zum Compilerbau, zur funktionalen Programmierung sowie zur Softwaretechnik angeboten.

Projektbeschreibungen

Projekt: Methoden der Spezifikation, Implementation, Bewertung und Integration von Quelltextcompilern und ihre Anwendung in der Softwaretechnik

Ansprechpartner: Prof. Klaus Bothe

Beteiligte Mitarbeiter: Dragan Macos

Projektförderung: Senat, nach dem Nachwuchsförderungsgesetz (NaFöG)

Das Projekt zielt auf die Auswertung, den Vergleich und die Verallgemeinerung von Untersuchungen zu Quelltextcompilern. Quelltextcompiler sind spezielle Compiler, die Programme einer höheren Programmiersprache in Programme einer anderen höheren Programmiersprache überführen.

Seit Ende der 80er Jahre werden Quelltextcompiler in einer Vielzahl von Einzelprojekten untersucht, wobei folgende offene Probleme auftreten, auf deren Lösung unsere Aktivitäten gerichtet sind:

Durch die Konzentration auf Einzelentwicklungen existieren keine verallgemeinernden Untersuchungen zur Bewertung und zum Vergleich von Quelltextcompilern. Somit fehlt auch jede Orientierung für Nutzer von Quelltextcompilern, insbesondere dann, wenn mehrere Produkte zur Auswahl stehen.

Ebensowenig wurden Forschungsaktivitäten zur systematischen Entwicklung eines Quelltextcompilers von seiner Spezifikation bis hin zu seiner Implementation (u. U. über allgemeine bzw. spezielle Softwarewerkzeuge) geleistet. So fehlen beispielsweise weitestgehend Versuche, die realisierte Transformation nutzergerecht und vollständig zu spezifizieren.

Das Potential von Quelltextcompilern über den compilertechnischen Aspekt hinaus bleibt weitestgehend unerschlossen (z. B. für das Reverse Engineering, für Tutorsysteme zur Unterstützung des Umstiegs zwischen höheren Programmiersprachen).

Gegenwärtige Aktivitäten der Gruppe in diesem Projekt sind:

1. Untersuchungen zur Implementation funktionaler Programmiersprachen durch
Quelltexttransformation (Dragan Macos).
2. Untersuchungen in Diplomarbeiten zur Transformation
- zwischen funktionalen Programmiersprachen
- zwischen funktionalen und prozeduralen Programmiersprachen
- zwischen prozeduralen Programmiersprachen.
3. Möglichkeiten der Transformation von Smalltalk-Programmen in Stand-Alone-
Programme.

Projekt: Codeoptimierung

Ansprechpartner: Dr. (USA) Frank Müller

Teilprojekt 1: Methoden der Codeduplizierung

Das Projekt untersucht Methoden zur Vermeidung von (a) bedingten und (b) unbedingten Sprüngen mittels Codeduplizierung. Die Konzepte wurden erarbeitet, implementiert und ausgewertet bzgl. der Anzahl der ausgeführten Instruktionen und des Cache-Verhaltens (siehe Publikationen). Derzeit wird untersucht, wie sich die Methoden zu (a) und (b) gegenseitig beeinflussen und kombinieren lassen.

Teilprojekt 2: Portables Instruktionsscheduling für optimierende Compiler auf modernen Rechnerarchitekturen (RISC und superskalar)

Ein optimierendes Compiler-Back-End soll durch eine Spezifikation von Prozessoreigenschaften ergänzt werden, die eine portable Implementation von Varianten des Instruktionsscheduling erlaubt. Das Instruktionsscheduling wird im Hinblick auf Caches und superskalare Architekturen durchgeführt, d.h., für Caches wird eine Reduzierung der Cache-Miss-Rate und für superskalare Architekturen die parallele Nutzung aller funktionalen Einheiten angestrebt. Das Projekt befindet sich in der Planungsphase.

Projekt: Parallele, verteilte und responsive Umgebungen

Ansprechpartner: Dr. (USA) Frank Müller

Teilprojekt 1: Programmierkonzepte für parallele und verteilte Umgebungen

Es werden Konzepte des Shared-memory-Modells zur Synchronisation in parallelen Systemen sowie deren Abbildung auf verteilte Systeme untersucht. Dazu wurde eine POSIX-Threads-Bibliothek (Pthreads) konzipiert und implementiert. Die Pthreads-Bibliothek wird von ca. 300 Anwendern weltweit genutzt. Weiterhin wurde sie bereits zur Unterstützung von Ada 95 Tasks im Rahmen des Gnu-Ada-Translators (GNAT) eingesetzt und wird z. Z. noch weiterentwickelt. In diesem Zusammenhang soll untersucht werden, ob eine hinreichend effiziente Implementierung von Ada 95 Tasks (d. h. einem shared-memory Modell) in einer verteilten Umgebung möglich ist.

Teilprojekt 2: Echtzeitsysteme: Analytische Bestimmung der Laufzeiten und Betriebs- systemunterstützung für responsive Systeme und Realzeitsysteme

Das Projekt konzentriert sich auf zwei Schwerpunkte. Erstens werden Methoden zur analytischen Bestimmung der Worst-case-Laufzeit von Echtzeit-Tasks untersucht, insbesondere für moderne RISC- Architekturen mit Pipelines und Caches. Die Laufzeiten dienen als Grundlage zum Scheduling der Tasks in einem Echtzeitsystem. Zweitens ist ein Echtzeit-Micro-Kernel (aus der Pthreads-Bibliothek für Sun SPARC VME Boards, siehe vorheriges Projekt) entwickelt worden, der ein deterministischeres Zeitverhalten als ein UNIX-Kernel aufweist. Dieser Kernel kann sowohl als Testumgebung zur Bewertung der Zeitanalysen benutzt werden als auch für Weiterentwicklungen zur spezifischen Unterstützung von Echtzeit- Betriebssystemen. Die Untersuchung beider Schwerpunkte wird im Hinblick auf responsive Systeme erweitert.

Veröffentlichungen und Vorträge

K. Bothe: Compilation von Pascal nach C: Transformationsregeln. Buchmanuskript, 1995.
K. Bothe: Quelltextcompiler und ihre Bedeutung in der Softwaretechnik. Arbeitspapier, 1995.
K. Bothe: Dealing with Non-toy-sized Projects in an Early Phase of Computer Science Curriculum - Made Possible by Object-Orientation (angenommen 1995).
D. Macos: Implementation of a Lisp-to-Pascal Translator. Arbeitspapier, 1995.
D. Macos: Eine abstrakte Datenstruktur für die Implementation der nicht-strikten Auswertung im prozeduralen Programmierparadigma. Arbeitspapier, 1995.
F. Müller und D. B. Whalley: Fast Instruction Cache Analysis via Static Cache Simulation. Simulation Symposium, Phoenix, USA, April 1995, S. 105-114.
F. Müller und D. B. Whalley: Avoiding Conditional Branches via Code Replication. ACM SIGPLAN Conference on Programming Language Design and Implementation, San Diego, USA, Juni 1995, S. 56-66.
F. Müller: Compiler Support for Software-Based Cache Partitioning. ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, San Diego, USA, Juni 1995, S. 137-145.
F. Müller, V. Rustagi und T. P. Baker: "MithOS - A Real-Time Micro-Kernel Threads Operating System", IEEE Real-Time Systems Symposium, Pisa, Italien, Dezember 1995.

Lehr- und Forschungseinheit

Datenbanken und Informationssysteme

Leiter:

Prof. Johann-Christoph Freytag, Ph. D.: Tel.: (030) 20 18 12 79, e-mail: freytag@dbis.informatik.hu-berlin. de

Mitarbeiter:

Dr. Johann Obermaier
Dipl.-Inf. Ulrike Jaeger
Dipl.-Inf. Stefan Manegold
Dipl.-Inf. Michael Stillger
Dipl.-Inf. Florian Waas
Dipl.-Ing. Heinz Werner

Sekretariat:

Ulrike Scholz: Tel.: (030) 20 18 12 77, e-mail: uscholz@informatik.hu-berlin.de

Tutoren:

Marc Ewert
Miroslaw Flasza
René Marx
Dieter Scheffner
Torsten Trzewik
Caroline Trzonnek

Durch die Lehr- und Forschungseinheit werden die Bereiche Datenmodellierung, Datenbanken und Datenbanksysteme sowie der Bereich Transaktionssysteme in Forschung und Lehre vertreten. In der Forschung stehen die Bereiche Anfragebearbeitung, Aktivitätsmanagement in Datenbanksystemen, Anwendungen und Datenbanken sowie neue Datenmodelle im Vordergrund. Dem Gebiet der Anfragebearbeitung und -optimierung für parallele Datenbanksysteme wird dabei besondere Aufmerksamkeit gewidmet.

Projektbeschreibungen

Projekt: EXPLORE - Anfragebearbeitung und -optimierung in parallelen Datenbanksystemen

Ansprechpartner: Dr. Johann K. Obermaier

Beteiligte Mitarbeiter:

Dipl.-Inf. Stefan Manegold
Dipl.-Inf. Michael Stillger
Dipl.-Inf. Florian Waas

Projektförderung: Deutsche Forschungsgemeinschaft

Relationale Datenbanksysteme haben sich in den vergangenen zehn Jahren zur Datenverwaltung durchgesetzt. Mit ihrem vermehrten Einsatz wird auch der Bedarf nach Steigerung ihrer Leistungsfähigkeit immer wichtiger. Ursachen hierfür sind sowohl die immer umfangreicheren Datenmengen, die in einem Datenbanksystem zu verwalten sind, als auch die komplexeren Anfragen über diese Daten und die erweiterte Funktionalität der DB-Schnittstelle.

Der Optimierer in einem Datenbanksystem erzeugt aus einer deklarativen Anfrage einen effizienten prozeduralen Anfrageausführungsplan. Unter Berücksichtigung der Parallelität nimmt die Komplexität des Lösungssuchraums drastisch zu. Optimiereransätze aus nichtparallelen Datenbanksystemen sind deshalb nur eingeschränkt bertragbar. Im Rahmen von EXPLORE (EXtensible ParalleL Optimization REsearch) sollen grundsätzliche Fragestellungen zur Optimierung in parallelen Datenbanksystemen untersucht werden.

In EXPLORE wird ein erweiterbarer und adaptiver Optimiereransatz verfolgt: Der Optimierer soll an veränderten oder neuen, sich möglicherweise verndernde Ausührungsumgebungen einfach angepaßt werden können. Weiterhin soll es möglich sein, ihn um neue logische Operationen und verschiedene Algorithmen dafür erweitern zu können. Ebenso wichtig ist es auch, zusätzliche Optimierungsverfahren einfügen zu können sowie eine Auswahlstrategie zur Verfügung zu stellen, die zwischen diesen unterschiedlichen Verfahren auswählen kann.

Zwei Aspekte werden in EXPLORE besonders betrachtet: Optimierung als Bestandteil der Abarbeitung, d. h. dynamische Optimierung und Parallelisierungsmöglichkeiten des Optimierungsvorgangs selbst.

Teilbereich exSPECt: Spezifikationsmethoden für parallele Anfragebearbeitung: Um mögliche Ansatzpunkte für die Optimierung von Anfragen an parallele DBS finden und bewerten zu können, ist zunächst eine Analyse der Abarbeitung in Form einer formalen Spezifikation nötig. Im Fall einer sequentiellen Verarbeitung kann die benötigte Komponentenspezifikation durch sog. relationen-algebraische Ausdrücke formuliert werden, die das Eingabe-Ausgabe-Verhalten definieren. Bei einer Abarbeitung in einer parallelen Umgebung kommen jedoch weitere Aspekte hinzu, die durch die relationale Algebra nicht mehr abgedeckt werden können: Die Gruppierung von Operatoren zu Prozessen sowie die Organisation der jeweils erforderlichen Interprozeßkommunikation.

Teilbereich Kostenmodellierung: Der Einfluß gegebener System-Parameter wie Architektur, Hardwaredaten, Datenvolumen und -verteilung, Komplexität der Anfrage auf die Effizienz der Anfragebearbeitung soll untersucht werden. Ziel ist es, die gegebenen Parameter bezüglich ihres Einflusses zu klassifizieren und für jede Klasse Regeln für die Anwendung statischer wie auch dynamischer Optimierungsstrategien zu finden. Ausgangspunkt hierfür ist ein einheitlicher Rahmen bestehend aus Ausführungs- und Kostenmodell. Das Ausführungsmodell soll unabhängig von der Systemarchitektur sein. Das Kostenmodell soll alle relevanten Kostenfaktoren beachten und somit die Kosten, die bei der Abarbeitung eines Anfrageplanes anfallen, adäquat vorhersagen. Durch Anwendung auf bereits in der Literatur untersuchte Spezialfälle sowie durch Simulation sind diese Vorhersagen zu verifizieren.

Teilbereich Suchstrategien: Ein weiterer Teilbereich ist die Konzeption und die Implementierung von neuen Suchstrategien aus dem Bereich des "evolutional computation". In dieser Arbeit soll ein Vergleich zu den bekannten Algorithmen Iterativ Improvement, Simulated Annealing und Treshold Accepting gezogen werden, die in einem prototypisch implementierten, parallelen Optimierer für Join-Ordnungen vorhanden sind. Die Flexibilität und der systeminhärente parallele Charakter der Genetischen Algorithmen läßt diesen Ansatz vielversprechend aussehen.

Projekt: Aktive Datenbanksysteme

Ansprechpartner: Dipl.-Inf. Ulrike Jaeger

Das Projekt AIMS (Aktives Informations Management System) befaßt sich mit Techniken zur effizienten Situationserkennung in aktiven Datenbanken.

In den letzten Jahren ist zu beobachten, daß Anwendungen und Basissysteme sich von monolithischen Implementierung zu einem modularen Ansatz entwickeln. Immer komplexer werdende Systeme werden als eine Menge modularer Aufgaben verstanden, die eine explizite Steuerung und Kooperation benötigen. Erweiterte Transaktionskonzepte und Workflow-Management-Systeme bieten interessante Ansätze zur Spezifikation und Implementation komplexer Anwendungen. In diesem Zusammenhang können Sprachmächtigkeit und Techniken aktiver Datenbankmanagementsysteme (DBMS) eingesetzt werden. Sie erlauben die Definition von Regeln der Form "IF Situation THEN Action". Wurden sie ursprünglich hauptsächlich für transaktionsgebundene Integritätsüberwachung entwickelt, erlauben neuere Konzepte die Implementierung von Reaktionen auf transaktionsübergreifende und komplexe Situationen.

Besonders interessant sind Anwendungen, in denen weniger der reguläre Ablauf, sondern vielmehr die Reaktion auf komplexe, seltener auftretende Ausnahmesituationen in langlebigen Prozessen mit Hilfe aktiver DBMS implementiert werden sollen. Eine komplexe Situation wird in aktiven Datenbanken spezifiziert als ein algebraischer Ausdruck über einfache und kombinierte Ereignis- und Kontextinformation. Zur Laufzeit werden Ereignis- und Situationsinformationen nicht nur über Transaktionsgrenzen, sondern über die gesamte Lebensdauer der Anwendung aufgehoben und verarbeitet.

Die Komplexität der Situationserkennung ergibt sich daher einerseits aus der Anwendung selbst, die sich auf komplexe Ausnahmesituationen spezialisiert, andererseits aus der bei langlebigen Prozessen auftretenden großen Informationsmenge, die beobachtet und verarbeitet werden muß. Die Zuverlässigkeit der Situationserkennung hängt davon ab, daß keine der gesuchten Situationen übersehen wird. Über längere Zeiträume hinweg entstehen dadurch große Mengen von unvollständigen Situationsinformationen, die vielleicht niemals in die spezifiziertkritische Situation einmünden. Gleichzeitig wird gefordert, daß keine irrelevanten Informationen mitverarbeitet werden, insbesondere keine irrelevanten Situationen, die Regel-Aktionen auslösen. Deshalb ist es für die Effizienz der Situationserkennung von entscheidender Wichtigkeit, die relevante Informationsmenge und damit auch die Relevanzprüfungen auf ein handhabbares Maß einzuschränken und den Zugriff durch speziell geeignete Datenstrukturen zu erleichtern.

Projekt: Optimizer Conformance Testing

Ansprechpartner: Dipl.-Inf. Michael Stillger

In dieses Projekt werden Methoden und Kozepte zur systematischen Evaluierung von Anfrageoptimierern in relationalen Datenbanksystemen entwickelt und implementiert. Im Gegensatz zur Nutzung von Benchmarkmethoden, bei denen Anfragen bzw. Relationen zur Überprüfung statisch vorgegeben werden, sollen in diesem Projekt die Möglichkeiten geschaffen werden, den Entwicklern von Datenbanksystemen bzw. Datenbankadministratoren ein flexibles "Werkzeug" zu schaffen, mit dessen Hilfe Testumgebungen erzeugt werden können, die den individuellen Bedrfnissen der Anwendungsumgebung entsprechen. Diese Testumgebung kann individuell spezifiziert und nach Kritierien generisch aufgebaut werden, die sowohl optimiererspezifische als auch anwendungsrelevante Parameter widerspiegeln.

In diesem Projekt werden zur Umsetzung dieser Ziele im wesentlichen drei Komponenten entwickelt, die den Grundstein einer Testumgebung legen sollen:

1. Datenbank-Generator: Über einen graphischen Editor soll der Benutzer sowohl ein Datenbankschema nach seinen Kriterien entwerfen können als auch die notwendigen Daten beschreiben, die in den einzelnen Relationen zu speichern sind.

2. Query Generator: Mit Hilfe einer Spezifikationssprache werden Mengen von Anfragen durch Angabe verschiedener Eigenschaften beschrieben, die dann vom Generator für beliebige Datenbankschemata erzeugt werden können. Durch die unterschiedlichen Spezifikationsmöglichkeiten kann der Optimierer für Anfragen getestet werden, die für eine Anwendung besonders wichtig und für die Leistungsföhigkeit der Anwendung kritisch sind. Neben syntaktischen Eigenschaften der zu erzeugenden Anfragen können auch Eigenschaften der in der Datenbank gespeicherten Daten mit in die Anfragegenerierung einbezogen werden.
3. Automatische Auswertungskomponente: Mit der Anfragebearbeitung und -ausführung sollen Daten, die beispielsweise Auskunft über den gewählten Ausführungsplan, dessen Kosten und die tatsächliche Ausführungszeit geben, gesammelt und anschließend ausgewertet werden. Ziel ist es, diese Auswertung weitgehend rechnergesteuert durchzuführen und Ergebnisse in graphischer Form anzuzeigen. Damit soll dem Benutzer die Möglichkeit gegeben werden, vorhandene Schwächen des Datenbanksystems für bestimmte Anfragen- und Datenbankschemata zu erkennen und zu analysieren. Bei der Analyse ist es wichtig, Informationen ber den Optimierungsprozeß selber miteinzubeziehen und die Auswertungskomponente so zu gestalten, daß der Benutzer durch unterstützende Erklärungen Maßnahmen zur Verbesserung des Leistungsverhaltens des Datenbanksystems vornehmen kann.

Projekt: Datenbanken und Anwendungen

Ansprechpartner: Prof. Johann-Christoph Freytag, Ph. D.

Beteiligte Mitarbeiter:

Dipl -Phys. Volker Gaede
Miroslaw Flasza
Oliver Bronkalla
André Bergholz
Torsten Trzewik

Zusammenarbeit:

Prof. O. Günther, Institut für Wirtschaftsinformatik der Humboldt-Universität zu Berlin,
Prof. G. Peyke, Institut für Geowissenschaften der Humboldt-Universität zu Berlin,
Dr. Stefan Heymann, Charité/MDC der Humboldt-Universität zu Berlin,
IBM Almaden Research Center, CA, USA

Mit dem zunehmenden Einsatz von Datenbanktechnologien in verschiedenen Anwendungsbereichen wird es immer notwendiger, Datenbanksysteme auf ihre Verwendungsfähigkeit hin zu überprüfen. Dabei soll festgestellt werden, inwieweit die exisiterenden Konzepte und Systeme den Anforderungen der einzelnen Anwendungsgebiete gerecht werden. Weder relationale noch objektorientierte Datenbanksysteme in ihrer jetzigen Form sind Garanten für eine erfolgreiche Nutzung entwickelter Datenbanktechnologie.

Anhand konkreter Anwendungen soll in diesem Projekt untersucht werden, welche zusätzlichen Konzepte und Datenbankkomponenten für eine bessere Unterstützung der Anwendungen notwendig sind. Dabei stand im vergangenen Jahr exemplarisch das Anwendungsgebiet der "Geo-Informationssysteme" im Vordergrund. Insbesondere werden für Probleme der Anfragebearbeitung und -optimierung mit der Entwicklung von Approximationsverfahren und mit einer erweiterten Geo-Algebra neue Lösungen angeboten.

Weiterhin werden existierende Datenbanksysteme mit neuen Funktionalitten auf ihre Einsatzmöglichkeiten hin untersucht. Die Datenbankgruppe ist in diesem Zusammenhang einer der weltweiten Beta-Test-Site für das neue IBM-Datenbankprodukt DB2/Solaris, bei dem sowohl seine Stabilität als auch der Umgang mit großen Datenmengen und die Verwendung von benutzerdefinierten Datentypen und -funktionen im Vordergrund stehen.

Projekt: CONTESSA (Constraints and Extended Support for Storage and Access)

Ansprechpartner: Prof. Johann-Christoph Freytag, Ph. D.

Projektförderung: ESPRIT Working Group 8666

Zusammenarbeit:

Dr. M. Wallace, IC PARC, London, England;
Dr. G. Kuper, M. Freeston, ECRC, München;
Prof. O. Günther, Humboldt-Universität zu Berlin;
Prof. J. Bocca, Universität Birmingham, England;
Prof. F. Afrati, Technische Universität Athen, Griechenland;
Dr. R. de By, Universität Twente, Enschede, Holland;
Dr. A. Podelski, DFKI Saarbrücken;
Prof. A. Frank, Technische Universität Wien

Das Hauptthema dieser Arbeitsgruppe ist die Integration von "Constraint Programming" und Datenbanksystemen. Da komplexere Anwendungen verbesserte Strukturierungs- und Operationsmöglichkeiten brauchen, soll eine solide Grundlage für die Nutzung erweiterter Datenbanktechnologie geschaffen werden, die Konzepte von Einschränkungen (Constraints) zur Darstellung von Information und ihrer Manipulation einschließt. Motiviert wird die Arbeit der Arbeitsgruppe durch Anwendungen im technischen Bereich, insbesondere Geo-Informationssysteme, bei denen eine alternative Informationsdarstellung zu einer mächtigeren Funktionalität und einem verbesserten Leistungsverhalten führen kann. Auf Grund des erfolgreichen Einsatzes der "Constraint Logic Programming"-Technologie in technischen Bereichen mit komplexen Optimierungsproblemen erscheint es wünschenswert, Konzepte dieses Bereiches mit Datenbankkonzepten zu integrieren.

Veröffentlichungen und Vorträge

J. C. Freytag: Query Conformance Testing. Vortrag an der Universitt Cottbus, Februar 1995.
J. C. Freytag: Query Conformance Testing. Vortrag an der Universitt Passau, Februar 1995.
J. C. Freytag: Einsatz objektorientierter Datenbanksysteme in geographischen Informationssystemen, eingeladener Vortrag auf dem 50. Geographentag, Potsdam, Oktober 1995.
J. C. Freytag: Einsatz objektorientierter Datenbanksysteme in geographischen Informationssystemen. Karlsruher Geo-Informatik-Report (eingereicht).
J. C. Freytag: Query Optimization in Parallel Databases. Dagstuhl-Workshop "Object-Orientation with Parallelism and Persistance", April 1995.
U. Jaeger, J. C. Freytag: An annotated Bibliography on Active Databases. Short Version, ACM SIGMOD Records, Vol. 24, No. 1, März 1995.
M. Stillger, J. C. Freytag: Testing the Quality of a Query Optimizer. IEEE Bulletin of the Technical Committee on Data Engineering, Vol. 18, No. 3, September 1995, S. 41 ff.
A. Bergholz, J. A. Schenk, S. Heymann, J. C. Freytag: An Entity-Relationship Approach to Biological Sequence Data. Kurzbeitrag zur Konferenz Complex Genetic Diseases, Max-Delbrck Centrum fr molekulare Medizin, September 1995.
M. Spiliopoulou, J. C. Freytag: Modelling Resource Utilization in Pipelined Query Execution. Technical Report, Dezember 1995
U. Jaeger: SMILE - A Framework for Lossless Situation Detection Proc. 5th Workshop on Information Technologies and Systems WITS, Aachener Informatik-Berichte, S. 110-119, Dezember 1995

Weitere Aktivitäten

Prof. Johann-Christoph Freytag, Ph. D.
- Mitglied des Programmkomitees der IEEE Date Engineering Konferenz, Taipei, Taiwan. März 1995.
- Mitglied des Programmkomitees der VLDB (Very Large Database)-Konferenz, Zürich. September 1995.
- Teilnahme am Dagstuhl-Workshop Object-Orientation with Parallelism and Persistance. April 1995.
- Teilnahme an der GI-Fachtagung Datenbanksysteme in Büro, Technik und Wissenschaft. Dresden, März 1995.
- Teilnahme an der ACM Sigmod Konferenz, San Jose, Mai 1995.
- Organisation und Teilnahme am CONTESSA-Workshop Constraint Databases. Lermoos, sterreich, April 1995.
- Organisation und Teilnahme am CONTESSA-Workshop Constraint Databases and Their Applications. Friedrichshafen, September 1995.
Dr. Johann Obermaier
- Teilnahme an der GI-Fachtagung Datenbanksysteme in Büro, Technik und Wissenschaft. Dresden, März 1995.
- Teilnahme am CONTESSA-Workshop Constraint Databases and Their Applications. Friedrichshafen. September 1995.
- Teilnahme an der VLDB (Very Large Database)-Konferenz, Zürich. September 1995.
Dipl.-Inf. Ulrike Jaeger
- Teilnahme an der VLDB (Very Large Database)-Konferenz, Zürich. September 1995.
Dipl.-Inf. Michael Stillger
- Teilnahme an der GI-Fachtagung Datenbanksysteme in Büro, Technik und Wissenschaft. Dresden, März 1995.

Gäste am Lehrstuhl

Dr. Jim Gray, San Francisco, USA: Vortrag Parallelism, the New Imperative in Computer Architecture. März 1995.
Prof. Betty Salzberg, North-Eastern University, Boston, MA, USA: Vortrag Access Methods for Temporal Data: A Survey. Mai 1995.
Prof. Peter Lockemann, Universität Karlsruhe: Vortrag Datenbankfunktionen: Vom System zum Eigenleben. Mai 1995.
Prof. Alfons Kemper, Universität Passau: Vortrag Optimierung deklarativer Anfragen in Objektbanken. Dezember 1995.
Prof. Winfried Lamersdorf, Universität Hamburg: Vortrag Zugang zu Daten und Diensten in offenen verteilten Systemen. Dezember 1995.

Studienarbeiten

Oliver Bronkalla: Installation des geographischen Informationssystems GRASS. Juni 1995.
Nikola Dimitrov: Realisierung einer Kopplung von EXODUS-Datenbankkernsystemen über das Programmiermodell LINDA. November 1995.
Peter Groer: Das Datenbanksystem GENESIS: Test und Anwendung unter Berücksichtigung der Erweiterbarkeitsmöglichkeiten. November 1995.

Sonstiges

Austragung des 2. Berliner Datenbanktages, Oktober 1995.

Diplomarbeiten

Przemyslaw Rychlewski: Versionsverwaltung für Softwarekomponenten in einem semantischen Netz. In Zusammenarbeit mit der Sietec Systemtechnik GmbH&OHG, Berlin. Mai 1995.
Katja Kleffe: Anwendungen neuer Transaktionskonzepte in Datenbanken - Analyse unterschiedlicher Escrow-Algorithmen in Bezug auf ihr Laufzeitverhalten. In Zusammenarbeit mit der Sietec Systemtechnik GmbH&OHG, Berlin. Mai 1995.
Peter Fleischer: Basisfunktionalität von Geoinformationssystemen - eine GeoAlgebra. Juli 1995.

Lehr- und Forschungseinheit

Künstliche Intelligenz

Leiter:

Prof. Dr. sc. nat. Hans-Dieter Burkhard: Tel.: (030) 20 18 12 14, e-mail: hdb@informatik.hu-berlin.de

Mitarbeiter:

Dr. phil. habil. Wolfram Heitsch
Dipl.-Inf. Ralf Kühnel
Dr. Gabriela Lindemann-von-Trzebiatowski
Dipl.-Inf. Mario Lenz
Dipl.-Inf. Petra Pirk
Dipl.-Math. Olga Schiemangk

Sekretariat:

Renate Zirkelbach: Tel.: (030) 20 18 12 13, e-mail: zirkel@informatik.hu-berlin.de

Tutoren:

Martin Lukowsky
Dirk Wieczorek
Stefan Roepcke
Martin Meyka
Thomas Lehmann

Gastwissenschaftler:

Prof. Dr. Do Duc Giao (Universität Hanoi)
Prof. Andres Soto Villaverde (Universität Havanna)

Verständnis wächst mit aktiver Auseinandersetzung: Etwas zu machen, zu beherrschen, bedeutet zugleich besseres Verstehen. Angewandt auf die Erforschung geistiger Prozesse führt das zur Nachbildung intelligenten Verhaltens mit Maschinen. So ist äKünstliche Intelligenz unter zwei Aspekten zu sehen: Modellierung von Intelligenz mit dem Ziel, sie besser zu verstehen, und Ausnutzung maschineller Leistungsfähigkeit zur Erledigung intelligenter Aufgaben. In der Lehr- und Forschungseinheit wird die Nutzung von äErfahrungswissen (Fallbasiertes Schließen) und die Zusammenarbeit intelligenter Systeme (Verteilte KI, Agenten-orientierte Techniken) untersucht. Anwendungsbereiche sind z. B. Aufgaben aus der Medizin und der Technik.

Projektbeschreibung

Projekt: Diagnose technischer Systeme

Ansprechpartner:

Dipl.-Inf. Petra Pirk
Dipl.-Inf. Ralf Kühnel

Projektförderung: Deutsche Forschungsgemeinschaft, im Projekt "Fallbasierte Fehlerdiagnose für technische Systeme"

Zusammenarbeit:

Prof. Dr. Bernd Neumann, Universität Hamburg;
Aktiengesellschaft für Prozeßsteuerungs- und Informationssysteme Berlin (PSI)

Thema: Untersuchungen zur Verwendung von Methoden der Künstlichen Intelligenz bei der Auswertung von Falldaten für die technische Fehlerdiagnose.

Existierende Techniken zur Fehlerdiagnose an technischen Systemen beruhen im wesentlichen auf einer adäquaten Modellierung des technischen Systems oder - im Falle von regelbasierten Expertensystemen - auf einem konsolidierten Erfahrungsschatz. Für komplexe und heterogene Anlagen sind solche Diagnoseverfahren nicht immer möglich oder sinnvoll. Hier bietet eine Sammlung konkreter Fehlerfälle die Alternative der fallbasierten Diagnose.

Im Projekt werden Grundlagen zur fallbasierten Fehlerdiagnose an technischen Systemen untersucht. Falldaten über Fehler und ihre Ursachen werden durch menschliche Experten rechnergestützt erfaßt. Eine Diagnose erfolgt dann durch Auswertung dieser Falldaten, z. B. durch Verallgemeinerung und Vergleich.

Die Untersuchungen konzentrieren sich auf Methoden zur strukturierten Repräsentation von Falldaten und auf Grundlagen fallbasierten Schließens (räumliches und zeitliches Schließen, Repräsentation elektrischer Domänen). Zur Erfassung von Fällen wurde das System "Fallexperte-D" entwickelt. Die aktuelle Arbeit untersucht Diagnosefälle und ihre Modellierung für Störungen und Probleme in Rechnernetzen. Die Modellierung zeitlicher Zusammenhänge erfolgt im Rahmen mehrwertiger Logiken.

Projekt: Künstliche Intelligenz - Anwendungen in der Medizin

Ansprechpartner:

Prof. Dr. Hans-Dieter Burkhard
Dr. Gabriela Lindemann-von-Trzebiatowski

Beteiligte Mitarbeiter:

Stefan Roepcke
Martin Meyka
Thomas Lehmann
Susanne Wesener
Wernfried Lengert
Carsten Grumm
Tzvetanka Poriazova

Zusammenarbeit:

Rechenzentrum der Charité, Humboldt-Universität zu Berlin;
Zentrallabor der Charité, Humboldt-Universität-Berlin;
Fraunhofer Institut, Institut für Software und Systemtechnik, Berlin;
Urologie und Kardiologie der Charit, Humboldt-Universität zu Berlin

Thema: Agenten-orientierte Programmierung zur kooperativen Befundung medizinischer Daten in einem verteilten Kommunikationssystem.

Die Kommunikation innerhalb eines Krankenhauses (Charité) soll von Agenten gesteuert werden. Agenten sind für die Verteilung der Informationen an die relevanten Stellen zuständig. Ein Informationsnetz verbindet zunächst das Rechenzentrum (Agentenzentrale), eine diagnostische Einrichtung und eine Station. Folgende Aufgaben sind z. B. durch Agenten auszuführen:

Agentenzentrale: Transformation von Formaten, Protokollumsetzung, Prüfung auf Mehrfachanforderung diagnostischer Leistungen, Anlegen, Verwalten und Archivieren von Krankenakten, zentrale Datenbasis, Termin- und Ausführungskontrolle.
Diagnostische Einrichtung: Validierung, Verifizierung von Untersuchungsanträgen, Materialeingang, Meßwerte, Übergabe von Teilbefunden, Gesamtbefund, Vollständigkeitsprüfung, Terminüberwachung.
Stationsarbeitsplatz: Stabilitätssicherung, Kommunikationssteuerung, Nachrichten verteilen, aufbereiten und präzisieren, laufende Aktualisierung.

Projekte: Techniken des Fallbasierten Schließens

Ansprechpartner:

Prof. Dr. Hans-Dieter Burkhard
Dipl.-Inf. Mario Lenz
Prof. Dr. Do Duc Giao

Zusammenarbeit:

Institut für Psychologie der Humboldt-Universität zu Berlin;
GMD - FIRST Berlin

Thema: Fallbasiertes Schießen zur Diagnoseunterstützung in der Urologie.

Anwendungen des Fallbasierten Schließens erscheinen kognitiv adäquat gerade im Bereich der Medizin. Kernpunkt sind Untersuchungen zur Fallmodellierung über medizinische Domänen, die Definition der Ähnlichkeit von medizinischen Fällen, der Aufbau einer Falldatenbasis (vorerst Urologie), die sich an assoziativen Speicherstrukturen orientiert, um insbesondere ein schnelles Fallretrieval und die Adaption von Fällen zur Diagnoseunterstützung zu realisieren. Im Rahmen einer Studie zu effektiven Speicherstrukturen, die von Datenbanken zu konnektionischen Ansätzen (Neuronale Netze) reicht, wurden Möglichkeiten einer Fallrepräsentation mit schnellem Zugriff untersucht. Die Einbettung eines Fallbasierten Systems zur Diagnoseunterstützung in der Urologie soll in das Rechnernetz der Charit durch den agenten-orientierten Ansatz realisiert werden.

Retrievaltechniken

Das fallbasierte Schließen orientiert sich an der Arbeitsweise von Experten auf vielen Gebieten: Ärzte, Rechtsanwälte, Mechaniker arbeiten häufig "kasuistisch": Zwar ist für die Bewertung von Problemsituationen auch Hintergrundwissen z. B. in Form von Modellen, Regeln etc. notwendig, jedoch kommt dies nur im Kontext eines bestimmten Problemfalles zur Anwendung. Ein Schwerpunkt der Forschungstätigkeit stellt die Entwicklung von Retrievaltechniken dar, die die Effizienz von Datenbankanfragen mit der Flexibilität von Assoziativspeichern verbinden. Dabei werden netzartige bottom-up-Techniken entwickelt, implementiert und erprobt (Case-Retrieval-Netze). Weitere Ansätze basieren auf Techniken des Lernens und des effektiven Aufbaus von Suchbäumen.

Anwendungen

Fallbasierte Reiseberatungssysteme: Ziel ist die Reaktion mit konkreten Angeboten auf nur vage und unvollständig formulierte Zielvorstellungen. Die Antworten erfolgen in der Reihenfolge der höchsten Ähnlichkeit zwischen der Anfrage und den gespeicherten Datensätzen. Falls bestimmte Wünsche nicht realisierbar sind, macht das System entsprechende Ersatz-Vorschläge nach der gleichen Strategie. Die eingesetzen Case-Retrieval-Netze erlauben prinzipiell die Variation von Ähnlichkeit und Relevanz sogar zur Laufzeit.

Fallbasierte Unterstützung der Immobilienbewertung: In Zusammenarbeit mit der Hypo-Bank wird ein Projekt durchgeführt, das die Anwendbarkeit fallbasierter Techniken bei der Bewertung von Immobilien überprüfen soll. Hintergrund dieses Ansatzes ist das sogenannte "Vergleichswertverfahren", das auf diesem Gebiet Anwendung findet und in Form eines prototypischen fallbasierten Systems implementiert werden soll.

Projekt: Entwicklung agentenorientierter Techniken

Ansprechpartner:

Prof. Dr. Hans-Dieter Burkhard
Dipl.-Inf. Ralf Kühnel
Prof. Andres Soto Villaverde

Beteiligte Mitarbeiter:

Sven Brückner
Martin Lukowsky
Dirk Wieczorek

Zusammenarbeit:

Universität Havana;
Universität Plovdiv;
Aktiengesellschaft für Prozeßsteuerungs- und Informationssysteme Berlin (PSI);
Daimler-Benz AG, Berlin

Der Programmierer eines Agenten soll mentale Kategorien Wissen, Fähigkeiten, Verpflichtungen, Ziele usw. für die Modellierung benutzen können und bei ihrer Auswertung in geeigneter Form unterstützen. Agenten auf unterschiedlichen Rechnern sollen untereinander kooperieren (Impementierung verteilter heterogener Systeme).

CBB: Mit dem System CBB wird ein Mittel zur Programmierung von Agenten bereitgestellt. Damit soll man Anwendungen im Bereich von wissensbasierten offenen Systemen, also Systemen mit dynamischer Struktur, dezentraler Steuerung, lokaler Information (Wissensbasis), asynchroner Kommunikation und kontinuierlicher Bereitschaft programmieren können.

Bedienung mathematischer Software für Modellierung chemischer Prozeße: Ziel ist die Bestimmung zutreffender Modelle und Parameter für die Beschreibung chemischer Prozesse passend zu experimentell gewonnenen Daten. Der aufwendige Prozeß soll durch programmierbare Agenten (Spezialisten und Operatoren) automatisiert werden.

Projekt: Theoretische Untersuchungen in der Verteilten Künstlichen Intelligenz

Ansprechpartner:

Prof. Dr. Hans-Dieter Burkhard
Dr. phil. habil. Wolfram Heitsch
Dipl.-Inf. Ralf Kühnel

Zusammenarbeit: Universität Warschau

Modelle für Multi-Agenten-Systeme

Während Zustandsbetrachtungen für die Beschreibung einzelner Agenten bevorzugt werden, spielen Aktionen und Ereignisse eine vorrangige Rolle bei der Untersuchung von Beziehungen zwischen den Agenten. Die mentalen Begriffe (z. B. belief, desire, intention) lassen sich auch auf dieser Ebene formalisieren. Damit ergeben sich Zusammenhänge zwischen den mentalen Begriffen unter den verschiedenen Gesichtspunkten (global, lokal, individuell) einerseits und dem Verhalten des gesamten System bzw. der einzelnen Agenten andererseits. Unser Ansatz stellt die Ereignisfolgen (histories) in den Mittelpunkt. Systembeschreibungen und Agentenbeschreibungen erfolgen im Rahmen formaler Sprachen. Dabei wird die Technik des nondeterministic interleaving zugrunde gelegt, und es ergibt sich ein vergleichsweise einfacher Formalismus.

Wissensrepräsentation und Inferenz für Agenten

Bezogen auf sein Anwendungsgebiet muß der Agent Bereichs- und Handlungswissen verwalten. Verfolgt werden Ansätze auf Grundlage der Prädikatenlogik erster Stufe sowie einer mehrwertigen Logik.

Implementiert wurde ein auf dem widerlegungsvollständigen Tableaukalkül basierender Theorembeweiser (in PROLOG). Modifikationen dienen der effizienteren Verarbeitung und der Implementierung von nichtmonotonen Logiken. Im Falle der Wissensrepräsentation in der minimalen terminologischen Logik arbeitet der Theorembeweiser als Entscheidungsalgorithmus. Um Inferenzprobleme in einem einheitlichen Rahmen zu untersuchen, wird eine mehrwertige Logik unter Verwendung der mathematischen Struktur des Zweifachverbandes aufgebaut. Zweifachverbände werden zur semantischen Begründung logischen Schließens herangezogen. An einer entsprechenden Inferenzprozedur für mehrwertige Logiken wird gearbeitet.

Veröffentlichungen und Vorträge

H.-D. Burkhard: How to define agent properties - or: What is a fair agent? In: C. Castelfranchi and J.-P. Müller (Eds.): From Reaction to Cognition. Lecture Notes in Computer Science (Subseries LNAI) 957, Springer, 1995, pp. 28-41.
H.-D. Burkhard: Agent-oriented programming in open systems. In: M. Wooldridge, N. R. Jennings (Eds.): Intelligent Agents. Lecture Notes in Computer Science (Subseries LNAI) 890, Springer, 1995, pp. 291-306.
H.-D. Burkhard: Case Based Reasoning. Vortrag: University of Economics Poznan, 23. März 1995.
H.-D. Burkhard: Ein Formalismus für Multi-Agenten-Systeme. Vortrag: Otto-von-Guericke- Universität Magdeburg, 14. März 1995.
H.-D. Burkhard: Retrieval im Fallbasierten Schließen. Kolloquium "Künstliche Intelligenz‘", Vortrag: Technische Universität Berlin, 2. Mai 1995.
H.-D. Burkhard: Fallbasiertes Schließen und Neuronale Netze. Vortrag: Kolloquium äKünstliche Intelligenz‘ , Technische Fachhochschule Berlin, 10. Mai 1995.
H.-D. Burkhard: Fallbasiertes Schließen und Kognitive Modelle. Vortrag: Kolloquium Psychologie, Humboldt-Universität zu Berlin, 17. Mai 1995.
H.-D. Burkhard: Case Retrieval Nets and Cognitive Modelling. Vortrag: Workshop "From AI to Cognitive Science, and Back" , KI95, Bielefeld, September 1995.
H.-D. Burkhard: A Multi-Agent System for Mathematical Modeling. Vortrag: 4. Workshop Concurrency, Specification & Programming, Warsaw, Oct. 1995.
H.-D. Burkhard: Case Retrieval Nets. Technik Report, Humboldt-Universität zu Berlin, 1995.
H.-D. Burkhard: Case Retrieval Nets and Cognitive Modelling - Ext. Abstract. Work- shop "From AI to Cognitive Science, and Back‘", In L. Dreschler-Fischer, S. Pribbenow (Eds.): KI-95 Activities: Workshops, Posters, Demos, Gesellschaft für Informatik, 1995, S. 53-54.
H.-D. Burkhard: Models of Multi-Agent Systems using Abstract Languages. Proceedings VIIth Conference on Logic and Computer Science (LIRA‘95), Novi-Sad, Sept. 1995, S. 7-8.
H.-D. Burkhard: Theoretical Foundations of Agent-Oriented Programming. Vortrag: University Havana, 21.-30. November 1995.
H.-D. Burkhard: Agent Oriented Techniques from the DAI Viewpoint. Vortrag: University of the West Indies, Trinidad-Tobago, 28. November 1995.
H.-D. Burkhard: Models of Multi-Agent Systems using Abstract Languages. Vortrag: DFKI Saarbrücken, 6. Dezember 1995.
H.-D. Burkhard: Fairness in Multi-Agenten-Systemen. Vortrag: Universität Leipzig, 12. Dezember 1995.
H.-D. Burkhard: Case Retrieval Nets and Cognitive Modelling, Technik Report, Humboldt-Universität zu Berlin, 1995.
H.-D. Burkhard: Another Look to BDI. Technik Report, Humboldt-Universität zu Berlin, 1995.
S. Brückner, D. Wieczorek: Biotische Verhaltenssteuerung und Selbstentwicklung im Agenten- Orientierten Programmieren. GFAI-Workshop äBiologieorientierte Informatik.
M. Lenz, H.-D. Burkhard: Retrieval ohne Suche? In: Bartsch-Spörl, B., Janetzko, D. und Wess, S. (Hrsg.): Fallbasiertes Schließen - Grundlagen und Anwendungen (Proceedings Workshop auf der XPS-95), Kaiserslautern, 1995, S. 1-10.
M. Lenz: Lazy Induction Triggered by CBR. In: Aamodt, A. and Komorowski, J. (Eds.): SCAI‘95: Proceedings 5th Scandinavian Conference on AI. IOS Press (Series on Frontiers in AI and Applications), 1995.
M. Lenz, H. Ladewig: Fallbasierte Unterstützung bei der Immobilienbewertung. In: Wirtschaftsinformatik, Schwerpunktheft Fallbasierte Entscheidungsunterstützung, H. 1, Erscheint 1996.
M. Lenz: IMTAS: Intelligent Multimedia Travel Agent System. In: Schertler, W., Schmid, B., Tjoa, A. M. and Werthner, H.: Information and Communications Technologies in Tourism, Proceedings ENTER-96, Erscheint beim Springer-Verlag 1996.
M. Lenz, E. Auriol, H.-D. Burkhard, M. Manago, P. Pirk: CBR für Diagnose und Entscheidungsunterstützung. Künstliche Intelligenz, 10 (1), Schwerpunktheft Fallbasiertes Schließen, Erscheint 1996.
G. Lindemann-von-Trzebiatowski, H.-D. Burkhard, A. Fellien, B. Messer, Th. Weckend: Case-Based and Agent-Oriented Techniques for Multimedia Medical Workplaces. KI-95 In L. Dreschler-Fischer, S. Pribbenow (Eds.): KI-95 Activities: Workshops, Posters, Demos. Gesellschaft für Informatik, 1995, S. 239- 241.
G. Lindemann-von-Trzebiatowski, H.-D. Burkhard, R. Klaus, B. Messer, Th. Weckend: Towards an Integrated Multimedia Medical Workplace via Agent-Oriented Approaches. In H.-D. Burkhard, P. Starke, L. Czaja (Eds.): Proceedings 4. Workshop Concurrency, Specification & Programming, Warsaw, October 1995, S. 51-54.
G. Lindemann-von-Trzebiatowski, B. Messer: Zur Funktionalität von Agenten-orientierten Software-Komponenten zur Unterstützung von Arztarbeitsplätzen speziell in der Urologie und Kardiologie. Bericht, Humboldt-Universität zu Berlin, 1995.
G. Lindemann-von-Trzebiatowski: Das Kooperalionsprojekt äVadeMed. Vortrag: Technische Universität Ilmenau, Institut für Biomedizin und Informatik, 1995.
M. Lukowsky, D. Wieczorek, S. Brückner: CBB - an Agent Development Tool. DIMAS‘95 - Krakow, 1995.
P. Pirk, H.-D. Burkhard: Fallbasiertes Schließen: Chance oder Gefahr? Poster: 19. Jahrestagung KI95, Bielefeld, September 1995.
A. Soto, H.-D. Burkhard: A Multi-Agent System for Mathematical Modeling. In H.-D. Burkhard, P. Starke, L. Czaja, Eds.: Proc. 4. Workshop Concurrency, Specification & Programming, Warsaw, October 1995, S. 190-203.
D. Wieczorek, M. Lukowsky, S. Brückner: Agent Development and Control System. In H.-D. Burkhard, P. Starke, L. Czaja, Eds.: Proc. 4. Workshop Concurrency, Specification & Programming, Warsaw, October 1995, S. 190-203.

Weitere Aktivitäten

Prof. Dr. Hans-Dieter Burkhard
- Vorsitzender des Konzils der Humboldt-Universität zu Berlin.
- Mitglied im Fakultätsrat der Mathematisch-Naturwissenschaftlichen Fakultät II.
- Sprecher der Berliner Interessengemeinschaft Künstliche Intelligenz (BIG-KI).
- Stellvertretender Sprecher der Fachgruppe 1.1.6 (Verteilte Künstliche Intelligenz) der Gesellschaft für Informatik.
- Mitglied in den Programmkomitees XPS 95, DIMAS 95, CS&P95, KI-95 Work-shop: Organisationsaspekte in Multiagentensystemen.
Mario Lenz
- Fallbasierte Unterstützung der Produktionsplanung. Ausstellungsexponat CeBIT-95.
Dr. Gabriela Lindemann-von-Trzebiatowski
- Mitglied im Fakultätsrat der Mathematisch-Naturwissenschaftlichen Fakultät II.
- Frauenbeauftragte des Instituts für Informatik.

Diplomarbeiten

Holger Paetsch: Anwendung eines dynamischen Neuronalen Netzes zur Klassifikation von Objekten in Grauwertbildern (Thema: Dr. Voigt, GFHI Berlin)
Ulrich John: Verteilte Produktionsplanung (Thema: Prof. Dr. Geske, GMD - FIRST Berlin)
Udo Kruschwitz: Die Spezieller- und die Erweiterungs-Relation als Strukturierungsmittel der Datenbasis-TELEX (Thema: Prof. Dr. Kunze Computerlinguistik, Humboldt-Universität zu Berlin)

Lehr- und Forschungseinheit

Datenanalyse

Leiter:

Prof. Dr. Egmar Rödel: Tel.: (030) 20 18 12 86, e-mail: roedel@informatik.hu-berlin.de

Mitarbeiter:

Dr. Klaus Dohmen
Dr. Wolfgang Kössler

Sekretariat:

Annegrete Baumann: Tel.: (030) 20 18 12 84, e-mail: baumann@informatik.hu-berlin.de

Tutor:

Thorsten Koch

Die Lehr- und Forschungseinheit vertritt die Gebiete "Stochastische Aspekte der Informatik" und "Computergestützte Statistik".

Projektbeschreibungen

Projekt: Optimierung und Simulation

Ansprechpartner: Prof. Dr. Egmar Rödel

Es werden randomisierte Algorithmen zur Lösung komplexer Optimierungsaufgaben entwickelt, getestet und miteinander verglichen. Insbesondere wurden adaptive randomisierte Such-Algorithmen untersucht, d. h. Algorithmen, bei denen man mit jeder Näherung den Zielfunktionswert fast sicher verbessert. Diese Algorithmen sind besonders wichtig, da ihre Komplexität lediglich linear von den Problemdimensionen abhängt. Es zeigt sich jedoch, daß ihre numerische Implementation außerordentlich schwierig ist. Obwohl diese Algorithmen fast sicher gegen das Optimum konvergieren, kann die Konvergenzgeschwindigkeit in konkreten, im allgemeinen ungünstig konfigurierten Problemstellungen sehr langsam sein. Ein typisches Beispiel hierzu illustrieren die Diagramme für ein konvexes Optimierungsproblem.

Projekt: Simulated Annealing

Ansprechpartner: Dr. Klaus Dohmen

Beim Simulated Annealing-Algorithmus handelt es sich um ein einfach zu implementierendes stochastisches Approximationsverfahren zur Lösung umfangreicher kombinatorischer Optimierungsprobleme, die u. a. im VLSI-Design und in der Bildverarbeitung auftreten.

Neben praktischen Aspekten wie dem Implementieren von Programmen und dem statistischen Auswerten von Programmabläufen stehen theoretische Fragen, etwa nach der Konvergenz des Algorithmus und den Beziehungen zur Mathematischen Physik, im Mittelpunkt des Interesses. Grundlage hierfür ist die Theorie der Markoff‘schen Ketten.

Veröffentlichungen und Vorträge

E. Rödel: Projektions on Conver Cones with Applications in Statistics. Submitted to COMPSTAT 96.
K. Dohmen: A Broken - Circuits-Theorem für hypergraphs. Archiv der Mathematik 64 (1995), S. 159 - 162.
K. Dohmen: A Contribution to the chromatic theory of uniform hypergraphs. Results in Mathematics 28 (1995), S. 49 - 52.
K. Dohmen: Verallgemeinerungen des Broken-Circuits-Theorems. Vortrag im Rahmen des Kolloqiums über Kombinatorik an der TU Braunschweig im November 1995.

Lehrstuhl Datenbanken und Informationssysteme

Lehr- und Forschungseinheit

Rechnerorganisation und Kommunikation

Leiter:

Prof. Dr. Miroslaw Malek: Tel.: (30) 20 18 12 69, e-mail: malek@informatik.hu-berlin.de

Team Berlin

Mitarbeiter:

Prof. Dr. Dieter Hammer
Dr. Günter Dollny
Dr. Andreas Polze
Dr. Siegmar Sommer
Dipl.-Phys. Dieter Neumann
Dipl.-Ing. Sven Palme
Dipl.-Ing. Matthias Werner
Dipl.-Ing. Günther A. Hoffmann

Technische Unterstützung:

Christine Henze
Steffan Wollny
Steffen Tschirpke

Sekretariat:

Jana Mrohs: Tel.: (030) 20 18 12 68, e-mail: mrohs@informatik.hu-berlin.de

Team Austin

Mitarbeiter:

Guillaume Brat, M. S.
Myoungchul Yoon, M. S.
Stephen Serafin, B. S.

Sekretariat:

Marianne Walk: Tel.: (+ 1 - 512) 4 71 57 04, e-mail: walk@pine.ece.utexas.edu

Die internationale Forschungsgruppe Rechnerorganisation und Kommunikation hat sich auf verschiedene Aspekte der netzwerkbasierten Computersysteme spezialisiert. Unser Interesse liegt auf dem Gebiet des verteilten und parallelen Rechnens mit den Schwerpunkten Fehlertoleranz, Echtzeitfähigkeit, Kommunikation und Modellierung.

Die Gruppe besteht aus Wissenschaftlern und Mitarbeitern des Instituts für Informatik an der Humboldt-Universität zu Berlin und des Department of Electrical and Computer Engineering an der University of Texas at Austin.

Projektbeschreibungen

Projekt: High-Performance Responsive Computing

Ansprechpartner:

Dr. Andreas Polze
Dipl.-Ing. Matthias Werner

Projektförderung:

Office of Naval Research (USA),
Deutsche Forschungsgemeinschaft

Das Projekt vereint Forschungsarbeiten auf dem Gebiet der "Responsiven Systeme (CORE)" mit Arbeiten zum Thema "Paralleles Rechnen in Verteilten Umgebungen (SONiC)". Responsive Systeme erreichen Fehlertoleranz und Echtzeitverhalten durch Redundanz in Raum und Zeit. Workstations in einem Netz werden als unabhängige Einheiten mit unabhängigem Fehlerverhalten angenommen, die gleichzeitige oder wiederholte Ausführung eines Programmes auf verschiedenen Maschinen kann also als Maßnahme zur Tolerierung von Fehlern vorgesehen werden. Gleichzeitig können die miteinander kommunizierenden Workstations als paralleles System angesehen werden. Der durch Parallelverarbeitung in einer solchen Umgebung mögliche Geschwindigkeitsgewinn kann dabei benutzt werden, um den overhead des responsiven Systems zu verbergen.

(Bild 3.5: Wurzeln unserer Forschungsprojekte)

1. Responsive Systeme

Responsive Systeme sind Einzel- oder Multiprozessorsysteme, die bei Einhaltung definierter Fehler- und Lastannahmen den gewünschten Service innerhalb eines definierten Zeitraumes liefern, d. h. fehlertolerante und echtzeitfähige Systeme. Unser Ziel ist Forschung auf dem Gebiet des responsiven Rechnens mit realitätsnahen Anwendungen, wie Prozeßsteuerungen, Transportsystemen und anderen Gebieten mit signifikantem ökonomischen Einfluß und entsprechender Relevanz.

Schwerpunkte

Entwicklung von Grundlagen und Paradigmen für responsives Rechnen, Scheduling, Konsens- und Entscheidungsverfahren.
Entwurf und Implementation eines Software-Frameworks zur Unterstützung der Responsivität, einschließlich einer Reihe neuartiger Betriebssystemservices (CORE " COnsensus for REsponsiveness).
Responsivität durch dynamische Rekonfigurierung von Anwendersoftware.
Analyse, Modellierung, Simulation von responsiven Systemen.
Scheduling und Lastverteilung in responsiven Systemen.
Beispielanwendungen in den Gebieten Prozeßsteuerung, Transportsysteme und Bankwesen (transaction processing).

(Bild 3.6: Struktur unserer High-Performance Responsive Computing Umgebung)

Teilprojekt: "CORE" Consensus for Responsiveness

Ansprechpartner: Dipl. -Ing. Matthias Werner

Konsens ist ein zentrales Paradigma innerhalb unserers Ansatzes zum Entwurf responsiver Systeme: Synchronisation, Scheduling, Initialisierung, Terminierung und Konsistenz können als Konsensprobleme betrachtet werden. Deshalb ist Konsens die Grundlage des CORE-Projekts (COnsensus for REsponsiveness) das von der ROK-Gruppe entwickelt wird. Um Konsens unter einer Gruppe von teilweise redundant arbeitenden Rechnern zu erzielen, führen die Rechner, die einer Problemlösungsgruppe zugeordnet sind, Konsensprotokolle durch, wie z. B. Mehrheitsabstimmungen oder Byzantinisches Agreement. Diese Protokolle führen entweder dazu, daß das Ergebnis eines fehlerhaften Knotens maskiert oder der fehlerhafte Knoten diagnostiziert wird. Beides ist äquivalent.

Alle diese Protokolle haben eine Eigenschaft, die sich negativ auf ihren Einsatz in Echtzeitsystemen auswirkt: sie brauchen relativ viel Zeit. Deshalb entwickelten wir in diesem Jahr das Prinzip der "frühen Entscheidung" (early decision) und wendeten es auf Konsensprotokolle an. Eine "frühe Entscheidung" erhöht die Performance dadurch, daß ein Ergebnis geliefert wird, auch wenn das Protokoll noch nicht vollständig abgearbeitet ist oder sich noch nicht alle Gruppenmitglieder beteiligt haben. Dieser Ansatz unterscheidet sich vom Prinzip der "ungenauen Berechnung" (imprecise computation): es besteht keine Einschränkung auf lineare Berechnungen; auch ist ein Ergebnis nicht "ungefähr" richtig, sondern entweder (im Rahmen des benutzten Algorithmus) korrekt oder aber falsch. Einem Ergebnis, welches aufgrund eines Early-Decision-Protokolls ausgegeben wird, ist dabei ein Wert zugeordnet, der aussagt, mit welcher Wahrscheinlichkeit ein korrektes Resultat vorliegt. Die empfangende Instanz kann dann entscheiden, ob dieses Resultat verarbeitet wird, oder ob sie auf ein nächstes Resultat, das eine höhere Korrektheitswahrscheinlichkeit hat, wartet.

Um die Eigenschaft der Responsivtät nicht nur abstrakt zu postulieren und auf Betriebssystemebene zu implementieren, sondern auch konkret auschaulich zu machen und Erfahrungen mit Anwendungen zu sammeln, haben wir uns die Aufgabe gestellt, eine responsive Beispielapplikation zu implementieren. Unsere Wahl fiel auf die Implementieren eines "Robusten Orchesters", bei dem jedes Mitglied (Computer) ein Instrument eines Musikstückes spielt. Bei Ausfall eines Rechners soll sein Part online von einem anderen übernommen werden. Die Probleme der Responsivität - Fehlertoleranz und Echtzeitverhalten - lassen sich an diesem Beispiel sehr gut demonstrieren. Es liegt eine Vorimplementation des "Robusten Orchesters" vor, die zwar schon die meisten Grundprinzipien verwendet, jedoch noch an das CORE-System angebunden ist.

Teilprojekt: Scheduling-Server für Mach

Ansprechpartner: Zhang Cong, M. S.

Responsivität beinhaltet sowohl die Eigenschaft der Fehlertoleranz, als auch die der Echtzeitfähigkeit, also der Möglichkeit, unter bestimmten Lastannahmen Garantien über Laufzeiten geben zu können. Gängige Betriebssysteme sind in der Regel nicht echtzeitfähig. Die Grundlage jedes Echtzeit-Rechnens ist Scheduling. Um bekannte und bewiesene Scheduling-Strategien wie EDF (Earliest Deadline First) oder RMS (Rate Monotonic Scheduling) in unserer responsiven Umgebung einsetzen zu können, entwickeln wir einen Scheduling-Server, der solche Strategien realisiert.

(Bild 3.7: Phasenmodell der Programmausführung)

Als Grundlage dient die Fixed Priority Policy, die der MACH-Betreibssystemkernel zu Verfügung stellt. Der Scheduling-Server läuft mit einer sehr hohen Priorität. Er ermittelt die nach der jeweiligen Echtzeit- Strategie auszuführende Task. Deren Priorität wird stark angehoben (bis knapp unter die Server-Priorität). Anschließend geht der Server für eine bestimmte Zeit "schlafen". In dieser Zeit steht der geschedulten Echtzeit-Task die Rechenressourcen zur Verfügung. Nach Ablauf der Zeit (oder bei Beendigung der Task) wird der Scheduling Server wieder aktiv. Er senkt angehobene Prioritäten wieder und geht erneut "schlafen". Jetzt können Betriebssystemtasks und nichtechtzeitkritische Anwendungstask entsprechend der üblichen Strategie des MACH-Schedulers abgearbeitet werden. Durch diese Maßnahme wird gewährleistet, daß ohne direkten Eingriff ins Betriebssystem alle Betriebssystemfunktionen ausgeführt werden können, aber gleichzeitig für zeitkritische Anwenderprogramme bestimmte Garantien abgegeben werden können. Da auf diese Weise nur ein Teil der Rechenzeit als Echtzeit-Rechenzeit zur Verfügung gestellt wird, hat das Verhältnis von Systemzeit zu Echtzeit-Zeit einen entscheidenden Einfluß auf die Effektivität des Verfahrens. Daher wird sowohl durch umfangreiche Experimente als auch durch theoretische Betrachtungen versucht, optimale Parameter für dieses Schedulingverfahren zu finden.

2. Paralleles Rechnen in verteilten Umgebungen

Parallele Architekturen haben sich bisher nur in wenigen, speziellen Anwendungsfällen durchsetzen können. Gründe dafür sind die schwierige Programmierbarkeit und schlechte Softwareunterstützung für Parallelrechner sowie deren hohe Kosten. Zudem veraltet die spezielle Hardware paralleler Systeme schnell. Beachtliche Rechenleistungen können auch von vernetzten, kooperierenden Workstations erbracht werden, die heute schon in großer Zahl installiert sind. Wir beschäftigen uns mit netzwerkbasierten Parallelrechnern, die als Multicomputer-Systeme Workstations unter Benutzung schneller lokaler Netze integrieren.

Schwerpunkte

Untersuchung neuer Paradigmen für parallele Programmierung.
Neue Ansätze zur virtuellen Speicherverwaltung (objektbasiert, dynamisch konfigurierbar, verteilt).
Werkzeuge zur benutzergesteuerten Konfigurierung und dynamischen Rekonfigurierung paralleler Programme.
SONiC - Shared Objects Net-interconnected Computer: ein Programmiersystem zur Ausführung paralleler Programme in verteilten Umgebungen.

Teilprojekt: SONiC - Shared Objects Net-interconnected Computer

Ansprechpartner: Dr. Andreas Polze

Unter dem Titel "Shared Objects Net-interconnected Computer (SONiC)" werden neue Ansätze zum parallelen Rechnen in verteilten Umgebungen untersucht. Als Zielumgebung betrachten wir netzwerkbasierte Parallelrechner, die als Multicomputersysteme moderne PC‘s und Workstations unter Benutzung schneller Netze (ATM) integrieren. Solche Systeme können heutzutage hohe Rechenleistungen erbringen, sie erfordern allerdings neue Ansätze zur Programmierung und zur Speicherverwaltung.

Wir untersuchen Replicated Shared Objects als Programmierparadigma im Umfeld von SONiC. Auf Basis unserer Implementation eines objektbasierenden distributed shared memory lassen sich task-parallele Programme in Workstation-Netzen einfach realisieren. Unser Ansatz gestattet es, Kommunikations- und Synchronisationsoperationen innerhalb der replizierten Objekte zu kapseln. Damit bieten Replicated Shared Objects dem Anwendungsprogrammierer eine einfach benutzbare Schnittstelle.

Schwache Konsistenzprotokolle (entry consistency, release consistency) bilden die Grundlage für die Realisierung unserer Replicated Shared Objects. Damit wird in unserem System der Kommunikationsaufwand für die objektbasierte Speicherverwaltung minimiert. Nach unserem Ansatz übernehmen Objekte die Rolle von Speicherseiten in einer herkömmlichen Speicherverwaltung. Das Problem von false sharing unabhängiger Seiten kann dadurch eliminiert werden. Experimente in unser prototypischen Implementation des SONiC-Systems auf Basis des Betriebssystems Mach und Ethernet als Kommunikationsmedium zeigten ähnliche Resultate auf einem aus vier Workstations bestehenden SONiC- System wie auf einem Vier-Prozessor shared memory-Multicomputer (Sequent Balance). Dem Programmierer paralleler Anwendungen stellt SONiC eine Klassenbibliothek für shared Datenstrukturen und Synchronisationskonstrukte wie locks und barriers bereit. Ein remote execution service gestattet die Erzeugung paralleler Aktivitäten auf verschiedenen Knoten eines netzwerk-basierenden Multicomputers. Eine mit NeXTSTEP implementierte grafische Benutzeroberfläche gestattet auf einfache Weise die Konfiguration des SONiC-Systems auf einer Reihe von Workstations.

3. Modellierung und Simulation

Die Modellierung und Simulation paralleler/verteilter Rechnersysteme konzentriert sich auf die Schwerpunkte Fehlertoleranz, Echtzeitfähigkeit, Effektivität von Konfigurierungen und Last-/Kapazitäts- Untersuchungen. Dabei werden folgende Forschungsschwerpunkte bearbeitet:

Graphenmodelle, Petri-Netze und andere Methoden zur Rechen- und Kommunikationsmodellierung.
Modellierung und Simulation responsiver Computersysteme.
Modellierung und Simulation von Speicherverwaltungssystemen.
Modellierung und Simulation von Computernetzwerken.
Untersuchung von Hardware/Softwarekonfigurierbarkeit.
Kompositionalität.
Fehlerinjektion in verteilten Systemen.

Projekt: SPIDER

Ansprechpartner: Myungchul Yoon, M. S.

Unter dem Titel "SPIDER" wurde ein Konsistenzmodell, genannt address consistency model, für skalierbare distributed shared memory-Parallelrechner entwickelt und in einem Softwaresimulator implementiert.

(Bild 3.8: Klassenbibliothek von SONiC und CORE)

Konsistenzmodelle für die Speicherverwaltung spielen eine große Rolle in Bezug auf die Leistungsfähigkeit skalierbarer Shared-memory-Multiprozessorsysteme. Das Sequential-consistency-Modell erweitert den in Uniprozessorsystemen verwandten Ansatz atomarer Speicherzugriffe auf Multiprozessorsysteme. Dieses Modell ist klar und einfach benutzbar, es erweist sich jedoch als zu strikt für eine Reihe von Optimierungsansätzen. Es entstanden daher einige schwacher Konsistenzprotokolle, wie processor consistency, weak consistency und release consistency.

Das address consistency-Modell verringert die vom release consistency-Modell an die Reihenfolge von Zugriffen auf gemeinsamen Speicher gestellten Anforderungen weiter. Unter diesem Modell werden Synchronisationsoperationen stets mit einer Menge von virtuellen Speicheradressen assoziiert. Synchronisationsoperationen beziehen sich nur auf diese Adresse, nicht aber auf den gesamten Adreßraum. Anforderungen an die Ordnung von Speicherzugriffen gelten daher stets nur für eine spezielle Adresse.

Address consistency wurde im Hinblick auf eine einfache Realisierung in Hardware entwickelt. Gleichzeitig entstand ein Simulator, der zur Bewertung unseres Konsistenzmodells im Vergleich zu anderen Modellen bezüglich einer Reihe von parallelen Anwendungen herangezogen werden soll.

Projekt: Modellierung und Simulation Dynamischer Systeme

Ansprechpartner: Dipl.-Inf. Günther A. Hoffmann

Dynamische Systeme sind Systeme deren beobachtbarer Status sich mit der Zeit ändert. Typischerweise produzieren solche Systeme Ausgaben, die in Form von Signalen gemessen werden können. Ein fundamentales Problem besteht darin, diese Signale in Form eines Modells zu charakterisieren, insbesondere dann, wenn nur wenig oder kein a priori Wissen über die Dynamik des Systems vorhanden ist. Zur Zeit werden vor allem netzwerkbasierte-Multicomputersysteme und Finanzmärkte als Vertreter dynamischer Systeme untersucht.

Schwerpunkte

Quantitative Analyse und Modellierung dynamischer Systeme
Simulation spezifischer Aspekte ausgewählter Systeme

Quantitative Analyse und Modellierung dynamischer Systeme: Die quantitative Analyse dynamische Systeme wurde lange Zeit von linearen Modellierungsmethoden dominiert. Jüngste Forschungsergebnisse deuten jedoch darauf hin, da (mit nichtlinearen, datenbasierten Verfahren komplexe Zusammenhänge effektiver modelliert werden können. Solche Verfahren werden im allgemeinen als Methoden zur Funktionsapproximation bezeichnet, da basierend auf einer limitierten Anzahl von Beobachtungen, die generierende Funktion geschätzt wird. Methoden zur nichtlinearen, datenbasierten Funktionsapproximation sind z. B. Radiale Basis Funktionen (RBF) oder Multi Layer Perceptrons (MLP). Im Rahmen von Forschungsprojekten im Finanzbereich konnte die Überlegenheit dieser Verfahren bereits an realen Problemstellungen verifiziert werden. Neben Methoden zur Funktionsapproximation bieten probabilistische Modellierungsverfahren wie z. B. Hidden Markov Modellen (HMM) die Möglichkeit, Schwachpunkte von RBF und MLP zu überwinden. Z. B. können mit Hilfe von HMM komplette Wahrscheinlichkeitsverteilungen eines Prozesses geschätzt werden.

Zur Zeit wird der Einsatz von RBF und HMM zur Modellierung und Prognose von Lastverteilungen und optimalen Frequenzverhältnissen für Scheduling Server unter CORE als Anwendung im Bereich verteilte Kontrolle (Distributed Control) und netzwerkbasierte Multi-Computersysteme überprüft. Aufbauend auf bereits vorliegenden ermutigenden Forschungsergebnissen im Bereich der quantitativen Finanzanalyse sollen diese neuen probabilistischen Modellierungsmethoden auch in der Finanzmarktmodelierung und Prognose verifiziert werden.

Simulation spezifischer Aspekte ausgewählter Systeme: Die verteilte und parallele Verarbeitung von Daten erzeugt komplexe Abhängigkeiten der Systemkomponenten untereinander. Eine zentrale Kontrolle des Gesamtverhaltens ist aus unterschiedlichsten Gründen meist nicht akzeptabel oder einfach inpraktikabel. Ein Lösungsansatz besteht darin die Kontrolle des Systems auf die Einzelkomponenten zu verteilen. Die Einzelkomponenten konkurrieren und/oder kooperieren untereinander um Services und Resourcen, so da (z. B. Systemstabilität und Fehlertoleranz gewährleistet wird. Ein solcher Ansatz wird in der Literatur auch als Autonomes System bezeichnet. In diesem Kontext spricht man dann von interagierenden Agenten. Bei der Konzeption eines solchen Systems stellen sich Fragen von fundamentaler Bedeutung bezüglich Verhalten und Design.

In dieser Phase des Projektes soll die Theorie autonomer Systeme zur Simulation spezifischer Interaktionsmuster eingesetzt werden. Insbesondere sollen hier konsensbasierte Interaktion von Agenten und deren Auswirkung auf Systemstabilität und Auktionsmechanismen zur Preisformation untersucht werden. Es wird erwartet, da (Ergebisse aus dieser Arbeit im Bereich des Designs von effizienten Trading Procedures, automatisierter Trade Execution Systeme und im Bereich der netzwerkbasierten- Multicomputersysteme zur optimalen Verteilung von Resourcen eingesetzt werden können.

4. Testumgebungen

Projekt: MAST - Testbed for High-Performance Computing in Network-based Systems

Ansprechpartner:

Dr. Günter Dollny
Dr. Sigmar Sommer

Beteiligte Mitarbeiter:

Dipl.-Ing Steffen Tschirpke

(Bild 3.9: MAST - ein Prüfstand für Meß-, Analyse- und Simulationsexperimente)

Die Forschungsschwerpunkte des Lehrstuhls für Rechnerorganisation und Kommunikation erfordern eine eigenständige experimentelle Testumgebung im Rechnernetzwerkbereich. Die auf der ATM-Technologie basierende Kommunikationsplattform stellt die Installationsumgebung der Forschungsmodelle des High- Performance Responsive Computing. Die Verifikation der Forschungsansätze erfolgt durch Meß-, Analyse- und Simulationsexperimente im Testbed. Die erforderliche Variabilität des Hard- und Softwareprofils der Testumgebung wird über die installierten aktiven Komponenten des integrierten Netz- und Systemmanagement erzielt. Zusätzlich kann die Virtualität der Kommunikationsstruktur durch Parameter der Service-Semantik des ATM-Management gesteuert werden.

Projekt: Der verbindungslose Netzwerkdienst ISO CLNS

Ansprechpartner: Dr. Günter Dollny

Beteiligte Mitarbeiter:

Dipl.-Ing Olaf Riebe
Dipl.-Ing Sven Palme

Projektförderung: Deutsche Forschungsgemeinschaft

Projektaktivitäten 1995: Bestimmend war die Testkonzeption und Durchführung von Arbeiten zur Durchsatzbestimmung für CLNS-Backbone-Router im WIN. In einer LAN/WAN Testumgebung wurden Durchsatzmessungen an Routern der Hersteller 3Com, Cisco, TeleBit und Wellflett vorgenommen. Die ermittelten Resultate wurden im Rahmen des Projektes als DFN-Report vorgelegt. Die Informationsdienste im Rahmen des CLNS-Referenzzentrums wurden durch Installation eines projektgebundenen WWW- Servers verbessert. Der Abschluß des Projektes wird dem DFN-Verein im Jahresbericht für 1995 vorgelegt. Perspektivisch werden mit dem Auftraggeber fortführende Projektanträge zu IPv6 Security diskutiert, die eine zukünftige Projekttätigkeit in Rahmen des DFN vorbereiten sollen.

Veröffentlichungen und Vorträge

Publikationen

M. Malek (ed.): Responsive Computing. A Special Issue of Real-Time Systems, the International Journal of Time-critical Computing Systems, vol. 7, no.3 1994, Kluwer, 1995.
M. Malek, D. S. Fussell: Responsive Computer Systems: Steps Towards Fault-Tolerant Real-Time Systems. Kluwer, 1995.
M. Malek: Omniscience, Consensus, Autonomy: Three Tempting Roads to Responsiveness. In Proceedings of the 14th Symposium on Reliable Distributed Systems, Keynote Address, Bad Neuenahr, September 1995.
M. Malek, A. Polze, M. Werner: A Framework for Responsive Parallel Computing in Network-based Systems. In Proceedings of International Workshop on Advanced Parallel Processing Technologies, Bejing, September 1995.
M. Malek, A. Polze, M. Werner: A Framework for Responsive Parallel Computing in Network-based Systems. HUB Informatik-Berichte No. 51/95, ISSN: 0863-95 51, Berlin, Dezember 1995.
M. Malek, A. Polze: The Shared Objects Net-interconnected Computer (SONiC). HUB-Informatik-Berichte No. 52/95, ISSN: 0863-95 52, Berlin, Dezember 1995.
M. Malek, A. Polze, M. Werner: The Unstoppable Orchestra - a Responsive Distributed Application. HUB-Informatik-Berichte No. 53/95, Berlin, Dezember 1995.
A. Polze: Objektorientierung und lose gekoppelte Kommunikation als Basis für die Entwicklung offener, verteilter Anwendungssysteme. Dissertation am Fachbereich Mathematik und Informatik der Freien Universität Berlin (Okt. 1994), Fortschritt-Berichte VDI- Reihe 10 Nr. 349, Düsseldorf, VDI-Verlag 1995.
A. Polze: Objects, Replication and Decoupled Communication in Distributed Environments. In Proceedings of GI/ITG-Fachtagung "Kommunikation in Verteilten Systemen (KiVS‘95)", Chemnitz, February 1995.
A. Polze: Verteiltes Rechnen unter Mach. unix/mail 2/1995, Carl Hanser Verlag München.
A. Polze: Shared Objects Memory - Kommunikation unter Mach. unix/mail 3/1995, Carl Hanser Verlag München.
A. Polze, M. Malek: Parallel Computing in a World of Workstations. Proceedings of 7th IASTED/ ISMM International Conference on Parallel and Distributed Computing and Systems, Washington, October 1995, S. 72-75, IASTED-ACTA Press.
G. A. Hoffmann: Function Approximation with Learning Networks in the Financial Field and its Application to the Interest Rate Sector. Conference on Computational Intelligence for Financial Engineering (CIFEr); New York; April 1995.
G. A. Hoffmann: Function Approximation with Learning Networks and its Application to the Interest Rate Sector; Deutsche Bank Research; Mai 1995; Frankfurt/Main.

Vorträge

M. Malek: Responsiveness in Automotive and Communication Systems. International Computer Performance and Dependability Symposium (IPDS 95), Erlangen, April,1995.
M. Malek: CORE - A Framework for Responsive Computing. Ecole Franco-Polonaise, Poznan, Mai, 1995.
M. Malek: The Quest for Responsiveness over Three Eras of Computing. 15th International Symposium on Protocol Specification, Testing and Verification (PSTV‘95), Warsaw, Poland, June, 1995.
M. Malek: High Performance Responsive Computing. AT&T Bell Labs, Murray Hill, New Jersey, July, 1995.
M. Malek, Omniscience, Consensus, Autonomy - Three Tempting Roads to Responsiveness. Keynote Address at the 14th Symposium on Reliable Distributed Systems, Bad Neuenahr, Germany, September, 1995.
M. Malek, A. Polze, M. Werner: A Framework for Responsive Parallel Computing in Network-based Systems. International Workshop on Advanced Parallel Processing Technologies (APPT 95), Beijing, China, September, 1995.
M. Malek: Omniscience, Consensus, Autonomy - Three Tempting Roads to Responsiveness. Academica Sinica, Beijing, China, September, 1995.
M. Malek: CORE - Consensus for Responsiveness, Freie Universitt Berlin, Dezember, 1995.

Weitere Aktivitäten

Prof. Dr. Miroslaw Malek
- International Performance and Dependability Symposium (IPDS‘95), Panelist, Erlangen Nürnberg, April 24 - 26, 1995.
- The 15th International Symposium on Protocol Specification, Testing and Verification (PSTV‘95), Panelist and Program Committee Member, Warsaw, Poland, June, 1995.
- The 14th Symposium on Reliable Distributed Systems, Panelist and Program Committee Member, Bad Neuenahr, Germany, September 13-15, 1995.
- The Second International Conference on Massively Parallel Processing Using Optical Interconnections (MPPOI), Program Committee Member, San Antonio, Texas, USA, October 23 - 24, 1995.
- First Conference on Fault-Tolerant Systems: FTS‘95, Program Committee Member, I.I.T. Madras, India, December 20-22, 1995.
- The 4th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), The 10th IEEE International Parallel Processing Symposium (IPPS), Program Committee Member, Honolulu, Hawaii at April 15-16, 1996.
- International Conference on Configurable Distributed Systems, Program Committee Member, Annapolis, Maryland, USA, May 6-8, 1996.
- Analytical and Numerical Modelling Techniques Conference, Program Committee Member, Budapest, June 2-6, 1996.
- The 1996 IEEE International Workshop on Dependability in Advanced Computing Paradigms (DACP-96), Program Committee Member, Hitachi-City, Ibaraki, Japan, June 20-21, 1996.
- Second European Dependable Computing Conference (EDCC-2), Program Committee Member, Taormina, Italy, October 2 - 4, 1996.
- Youth Forum in Computer Science and Engineering (YUFORIC) Theme: Real-Time Technology and Applications, Program Committee Member, Tokyo, Japan, October 27, 1996.
- Member of the editorial boards of the Journal of Parallel and Distributed Computing and Real- Time Systems journal.
Myungchul Yoon
- Dreimonatiger Gastaufenthalt an der Humboldt-Universität im Sommersemester 1995.
Zhang Cong
- Einjähriger Gastaufenthalt an der Humboldt-Universität seit Juni 1995.
Günther A. Hoffmann
- Siebenmonatiger Gastaufenthalt am Massachusetts Institute of Technology; Boston, USA.

Kooperationen

Graduiertenkolleg "Kommunikationsbasierte Systeme" (Prof. Malek; gemeinsame Einrichtung des Fachbereichs Mathematik und Informatik der Freien Universität Berlin, des Fachbereichs Informatik der Technischen Universität Berlin und des Instituts für Informatik der Humboldt-Universität zu Berlin). Für die Anwendung der Informatik hat in den letzten Jahren die Realisierung nebenläufiger und verteilter Systeme eine immer größere wirtschaftliche Bedeutung erlangt und ist ein vorherrschender Bereich technischer Innovationen geworden. Die Ziele des Graduiertenkollegs bestehen in der Analyse solcher Systeme, ihrer formalen Beschreibung, Leistungs- und Zuverlässigkeitsbewertung sowie der Entwicklung von Konzepten, Methoden und Werkzeugen, die Ingenieure in der Konstruktion und Handhabung entsprechender Anwendersoftware unterstützen.
Verschiedene Kooperationen mit wissenschaftlichen Institutionen aus Europa, Japan und den USA.

Diplomarbeiten

Steffen Tschirpke: Konzepte einer Testumgebung für verteilte Rechnersysteme. April 1995.
Stefan Schröder: Untersuchungen der Einsetzbarkeit von allgemeinen und speziellen Meßmitteln bei Messungen in lokalen Rechnernetzwerken. April 1995.

Lehr- und Forschungseinheit

Signalverarbeitung/Mustererkennung

Leiter:

Prof. Dr.-Ing. Beate Meffert: Tel.: (030) 20 18 12 55, e-mail: meffert@informatik.hu-berlin.de

Mitarbeiter:

Dr.-Ing. Manfred Günther
Lothar Heese
Dr.-Ing. Olaf Hochmuth
Dr.-Ing. Gerald Kell
Dr.-Ing. Thomas Morgenstern
Dr.-Ing. Frank Winkler
Dipl.-Ing. Uwe Homann (Doktorand)
Dipl.-Ing. Stefan Ranguelov (Daimler-Benz-Stipendiat)
Doz. Dr. sc. techn. Günter Härtig
Dipl.-Ing. Karl-Heinrich Hauptvogel
Dr.-Ing. Michael Ritzschke
Dr.-Ing. Dietrich Schilder
Dr.-Ing. Gerhard Voigt
Dipl.-Ing. Olaf Jaeckel (Doktorand)
Dipl.-Ing. Kristian Weiland (Konrad-Adenauer-Stipendiat)

Sekretariat:

Sabine Dziwisz: Tel.: (030) 20 18 12 53, e-mail: dziwisz@informatik.hu-berlin.de

Tutoren:

Dirk Heinemann
Gunter Lepschies

Gastwissenschaftler:

Mingzhi Lu, M. Sc. (Universität Peking)

Das Fachgebiet Signalverarbeitung/Mustererkennung, vertreten durch die gleichnamige Professur im Umfeld der Technischen Informatik, befaßt sich mit der Erfassung, Verarbeitung und Auswertung von ein- und zweidimensionalen Signalen. In der Lehre werden die Signalverarbeitung, Mustererkennung und die Grundlagen und ausgewählte Anwendungen der Bildverarbeitung vertreten. Die Forschungsgegenstände sind vorrangig interdisziplinär und anwendungsorientiert.

Projektbeschreibungen

Projekt: Parallelisierung vereinheitlichter Bildverarbeitungsalgorithmen für die automatische Sichtprüfung technischer Objekte mit Hilfe verschiedener, dynamisch konfigurierbarer Prozessoren

Ansprechpartner: Prof. Dr.-Ing. Beate Meffert

Beteiligte Mitarbeiter:

Dr.-Ing. Olaf Hochmuth
Mingzhi Lu, M. Sc.
Dipl.-Ing. Stefan Ranguelov
Dipl.-Ing. Marius Scheiner
Dipl.-Ing. Thomas Schneider

Zusammenarbeit:

Universidad Politecnica de Cataluna, Barcelona (E);
Avicom GmbH, Berlin;
D-Research GmbH, Berlin

Zum gegenwärtigen Stand der Technik gehört, daß für fast alle Bildverarbeitungsaufgaben in der Industrie auf eine umfangreiche Werkzeugsammlung erprobter Bildverarbeitungsalgorithmen zurückgegriffen werden kann. Eine tatsächliche Realisierung ist jedoch wirtschaftlich nicht möglich, da die Algorithmen sehr umfangreiche Berechnungen (Fouriertransformation, Houghtransformation, Texturanalysen usw.) erfordern, die für den Echtzeiteinsatz in der Industrie ungeeignet sind. Untersuchungen von in die Praxis überführten Lösungen zum Themenkreis Sichtprüfung von Werkstücken zeigen, daß fast ausschließlich mit einfachsten Prozeduren gearbeitet wird, da lediglich dafür die gegenwärtige Prozessorleistung ausreicht. Nur eine deutliche Geschwindigkeitserhöhung auch für die komplexeren Bildverarbeitungsprozeduren ermöglicht es, über den derzeitigen Stand der industriellen Bildverarbeitung hinauszugehen.

Innerhalb des vorgeschlagenen Projektes soll jeweils eine Softwarebibliothek (Standardmikroprozessor, Mikrocontroller, Signal- und Grafikprozessor) für die Anforderungen einer extrem schnellen, industriellen Bildverarbeitung geschaffen und an typischen Applikationen getestet werden.

Projekt: Entwicklung eines Meßplatzes zur Impuls-Oszillometrie bei Neugeborenen

(Projektmitarbeit. Projektleitung: Dr. Gerd Schmalisch, Abt. Neonatologie der Kinderklinik der Charité)

Ansprechpartner: Prof. Dr.-Ing. Beate Meffert

Beteiligte Mitarbeiter:

Dr.-Ing. Olaf Hochmuth
Dipl.-Ing. Mario Schmidt

Projektförderung: Deutsche Forschungsgemeinschaft

An die Atemfunktionsdiagnostik im Neugeborenenalter werden seitens der Klinik hohe Anforderungen gestellt, die mit der verfügbaren Meßtechnik aber nicht erfüllbar sind. Neben den noch vorhandenen meßtechnischen Grenzen (Empfindlichkeit, Rückwirkungen auf den Gasaustausch, Einsatz unter Beatmung) versagen bisher übliche Untersuchungsmethoden häufig, da sie auf sehr einschränkenden Voraussetzungen aufbauen.

Mit der Impulsoszillometrie soll eine neue, nichtinvasive Methode zur Untersuchung der Atemmechanik entwickelt werden, die bei Kombination mit der Flow-Through-Technik weitgehend rückwirkungsfrei ist. Die Impulsoszillometrie kann bei pulmonalen Inhomogenitäten und Nichtlinearitäten eingesetzt werden. Infolge ihrer hohen zeitlichen Auflösung lassen sich auch Veränderungen der Atemmechanik während eines Atemzuges erfassen. Die bisher nur bei Erwachsenen verwendete Impulsoszillometrie läßt sich nicht unmittelbar auf Neugeborene übertragen. Die Besonderheiten der Atemfunktionsdiagnostik in dieser Altersgruppe erfordern neue systemtheoretische und meßtechnische Lösungen.

Projekt: TEGRA - System zur hochgenauen Temperaturmessung und zur Messung der Mikrogravitation an einer Kristallzüchtungsanlage für den Weltraumeinsatz

Ansprechpartner: Dr.-Ing. Frank Winkler

Beteiligte Mitarbeiter:

Dr.-Ing. Manfred Günther
Dr.-Ing. Gerald Kell
Dr.-Ing. Thomas Morgenstern

Projektförderung: Deutsche Agentur für Raumfahrtangelegenheiten (DARA), Bonn

Zusammenarbeit:

Deutsches Forschungsinstitut für Luft- und Raumfahrt (DLR), Köln;
BBT Materials Processing, Prag

Zur Vorbereitung, Durchführung und Auswertung von Kristallzüchtungsexperimenten unter schwerelosen Bedingungen ist die Kenntnis der wesentlichen Einflußgrößen Temperatur und verbleibende Gravitation notwendig. Die innerhalb des Projekts entwickelte Meßtechnik erlaubt eine geschlossene, experimentbezogene Datenerfassung mit hoher Genauigkeit.

Das Temperatur- und Gravitationsmeßgerät TEGRA ist Bestandteil einer neuen Kristallzüchtungsanlage CSK 4 der Firma BBT und wird im Rahmen des Raumflugprojektes EUROMIR ‘95 eingesetzt. Besonderheiten sind die hochgenaue Temperaturmessung bis 1400 C, die Programmierbarkeit und eine flexible Konfigurierbarkeit. Durch spezielle Algorithmen können ortsbezogene Temperaturmessungen für eine differentialkalorimetrische Auswertung des Experimentverlaufes herangezogen werden. Die wesentliche wissenschaftliche Leistung bei der Entwicklung von TEGRA besteht in der Herbeiführung eines Synergieeffektes, der durch das Zusammenspiel einer speziellen, überwiegend analog arbeitenden Hardware mit Softwarekomponenten zur Signalverarbeitung möglich wird. Aus der gezielten Eliminierung differentieller Linearitässfehler werden auch unter elektromagnetisch stark gestörten Umgebungsbedingungen extrem hohe Temperaturauflösungen (bis 2,5 mK) möglich.

Das Gerät befindet sich seit September 1995 im Kristall-Labor der russischen Raumstation MIR. Erste Experimente wurden bereits erfolgreich durchgeführt. Weitere Experimente zur Untersuchung unterkühlter Schmelzen und zu Materialverteilungen in Mischkristallen sind geplant.

Projekt: Optimierung von Datenerfassungs- und Speichertechniken für Anwendungen mit extremen Anforderungen

Ansprechpartner: Dr.-Ing. Frank Winkler

Beteiligte Mitarbeiter:

Dr.-Ing. Olaf Hochmuth
Thorsten Hummel
Dr.-Ing. Thomas Morgenstern

Projektförderung: British German Academic Research Collaboration (ARC)

Zusammenarbeit:

Loughborough University of Technology, Department of Electronics and Electrical Engineering

Datenerfassung und Datenspeicherung sind wesentliche Komponenten signalverarbeitender Systeme. An viele solcher Systeme werden heute Forderungen nach einer zuverlässigen Langzeitfunktion auch unter extremen Bedingungen erhoben. So erfordern zum Beispiel Anwendungen in schwer zugänglichen Gebieten oder auch portable Systeme eine hohe Leistungsfähigkeit bei großer Fehlertoleranz und geringer Leistungsaufnahme. Ziel dieser Zusammenarbeit ist die Erweiterung der theoretischen und praktischen Erkenntnisse und Erfahrungen auf den Gebieten des Entwurfs, der Entwicklung und der Implementation von Teilkomponenten für derartige Systeme.

Projekt: Duosensor zur simultanen Erfassung der akralen Wiedererwärmung und Wiederdurchblutung

Ansprechpartner: Dr.-Ing. Olaf Hochmuth

Beteiligte Mitarbeiter:

Dipl.-Ing. Marius Scheiner
Dipl.-Ing. Frank Schuster

Zusammenarbeit: Hautklinik, Charité

In der dermatologischen Diagnostik findet die Messung der akralen Wiedererwärmung und -durchblutung zunehmend Anwendung. Hierbei werden nach einer kontrollierten Abkühlung des Zeigefingers Temperatur und Durchblutung während seiner Wiedererwärmung registriert. Aus dem zeitlichen Verlauf dieser Daten können Erkenntnisse beispielsweise über Durchblutungsstörungen oder die Hautdicke gewonnen werden.

Das neu entwickelte Meßgerät Duosensor ermöglicht die gleichzeitige Erfassung von Oberflächentemperatur und Durchblutungszustand. Zur Bestimmung der Hauttemperatur wurde ein Infrarot-Thermoelement eingesetzt. Für die Durchblutungsmessung wurde ein Sensor verwendet, der auf dem Prinzip der Photoplethysmographie beruht. Zur Verlaufskontrolle einer Behandlung ist es notwendig, die Ergebnisse einzelner Messungen zu vergleichen, was hohe Anforderungen an die Reproduzierbarkeit der Messungen stellt. In diesem Zusammenhang ist es wichtig, daß die Steuerung der etwa 4 bis 5 Minuten dauernden Untersuchung vom Meßgerät selbst vorgenommen wird. Nach der Messung erfolgt die Berechnung zweier wichtiger Kennwerte für die akrale Wiedererwärmung und -durchblutung. Der zeitliche Verlauf beider Messungen wird auf einem Drucker ausgegeben.

Projekt: Modulares System zur mobilen drahtlosen Daten- und Identifikationsübermittlung

Ansprechpartner: Dr.-Ing. Frank Winkler

Beteiligte Mitarbeiter:

Dr.-Ing. Manfred Günter
Dr.-Ing. Gerald Kell
Prof. Dr.-Ing. Beate Meffert
Stefan Sachse
René Unruh

Zusammenarbeit: ESYS GmbH, Berlin

Für unterschiedliche Anwendungsfälle (z. B. mobile Umweltregistrierungen, Speditions- und Frachtgutüberwachung, Warenkennzeichnung und -identifikation, Erläuterung von Ausstellungsstücken, Statusfeststellungen und -abfragen) besteht die Notwendigkeit, durch miniaturisierte Systeme neben aktuellen Meßwerten Daten über gegenstandsspezifische Eigenschaften am Objekt zu registrieren und drahtlos mit unterschiedlichen Distanzen auszulesen und zu übermitteln. Derartige Lösungen gestatten es, bisher übliches manuelles Ablesen zu automatisieren. Bei der Entwicklung muß die Anwendung neuester Erkenntnisse des Schaltkreisentwurfs, der HF- und Funktechnik sowie energiesparender Schaltungen eine wesentliche Rolle spielen, um die zu entwickelnden Systeme in Miniaturausführung gestalten und auch für Langzeitaufgaben verwenden zu können. Ziel des Projektes ist es, für eine Vielfalt möglicher Anwendungen ein modulares elektronisches System zu entwickeln, welches Informationen zum gewünschten Zeitpunkt von definierten Stellen abruft, drahtlos oder/und über verschiedene Dienste und Netze (insbesondere ISDN) zum Zielpunkt überträgt und zentral eine Auswertung gestattet.

Projekt: Entwurf elektronischer Komponenten und integrationsfähiger Strukturen für physikalische Untersuchungen im Ultrakurzzeitbereich, insbesondere zur zeitlichen Digitalisierung im Pikosekundenbereich

Ansprechpartner: Dr.-Ing. Gerald Kell

Beteiligte Mitarbeiter:

Dipl.-Ing. Kristian Lauritsen
Dipl.-Ing. Hans-Jürgen Rahn
Dr.-Ing. Michael Wahl

Projektförderung: BiosQuant GmbH Unternehmen für Forschung und Entwicklung, Berlin

Die umfassende Zielstellung des Projektes läßt sich mit dem Entwurf elektronischer Komponenten umschreiben, die für eine Untersuchung solcher physikalischen Vorgänge geeignet sind, die in der Wechselwirkung von materiellen Strukturen mit einzelnen Photonen auftreten (beispielsweise in materialwissenschaftlichen oder quanten- mechanischen Arbeitsgebieten). Derartige Vorgänge laufen in aller Regel im Zeitbereich weniger Pikosekunden ab, wobei innerhalb kürzester Zeit eine enorme Menge an auszuwertenden Daten anfallen kann. Die elektronischen Komponenten müssen dieser Forderung Rechnung tragen, wobei neben der großen Datenverarbeitungs- geschwindigkeit auch extrem zeitstabile Sensor- und Aktorfunktionen eine Rolle spielen. Konkrete Ergebnisse der Kooperation können sowohl in der Konzeption sehr schneller Lasersysteme als auch in der Erfassung von Daten nach dem Prinzip der Einzelphotonenzählung, der zeitlichen Quantisierung und der Datenkompression bestehen. Ein erstes Beispiel befaßt sich mit dem Entwurf eines Schaltkreises zur zeitlichen Digitalisierung im Pikosekundenbereich.

Projekt: Entwicklung eines bewegungskompensierten Formatkonverters für HDTV

Ansprechpartner: Dr.-Ing. Frank Winkler

Beteiligte Mitarbeiter:

Dr.-Ing. Olaf Hochmuth
Oliver Lehm
Prof. Dr.-Ing. Beate Meffert
Dr.-Ing. Thomas Morgenstern
Kathrin Rümmler
Holger Wilke

Zusammenarbeit:

Heinrich-Hertz-Institut für Nachrichtentechnik Berlin (Dr.-Ing. M. Ernst, Dipl. -Ing. M. Karl)

Der neue Standard für hochauflösende Fernsehsysteme (HDI - High definition interlaced; HDTV - high definition television) folgt der EUREKA 95-Spezifikation. Durch eine höhere Auflösung von 1920 Spalten und 1152 Zeilen kann die Bildqualität deutlich verbessert werden. Mit der Erhöhung der Bildauflösung geht eine Änderung des Bildformates auf 16: 9 einher, was zu einem dem Gesichtsfeld besser angepaßten Bild führt. Für die Formatkonvertierung herkömmlicher Fernsehbilder im TVI-Format (television interlaced) in das HDTV-Format sind zahlreiche Signalverarbeitungsalgorithmen notwendig, wobei auf Grund der Echtzeitanforderungen hohe Ansprüche an die Verarbeitungsgeschwindigkeit gestellt werden. Für die Entwicklung leistungsfähiger Hardware zur Formatkonvertierung sind entsprechende Simulations- und Testwerkzeuge erforderlich. Im Rahmen von studentischen Arbeiten werden insbesondere Bildverarbeitungsalgorithmen sowie Hard- und Softwarekomponenten entwickelt und getestet.

Projekt: Bildverarbeitung für die Fehler- und Objekterkennung

Ansprechpartner: Doz. Dr. sc. techn. Günter Härtig

Beteiligte Mitarbeiter:

Thomas Glau
Dipl.-Ing. Kristian Weiland

Zusammenarbeit: HELIOWATT WERKE Elektrizitäts-Gesellschaft mbH, Berlin

Schwerpunkte jeder Klassifikationsaufgabe bestehen in der Definition von geeigneten Merkmalen zur numerischen Abbildung der Bildinformation und der Auswahl eines leistungsfähigen Klassifikationsalgorithmus. Da allgemeingültige Aussagen zur Realisierung der Merkmalsauswahl und zum Klassifikatorentwurf nur begrenzt ableitbar sind, werden oft empirische Verfahren angewendet.

Ziel der Untersuchungen ist es, ein nahezu universelles Werkzeug zu schaffen, das für eine beliebige Klassifikationsaufgabe aus einer umfangreichen Menge "potentieller" Merkmale und Klassifikatoren die jeweils geeignetsten selektiert, die dann für die eigentliche Implementation der Erkennungssoftware verfügbar sind. Das stark problemorientierte Software-Design soll hohe Erkennungsraten bei effektiver Nutzung der jeweils verfügbaren Rechenkapazität gewährleisten.

Teilaufgaben der Untersuchungen:

Deduktive Ermittlung problemspezifischer Merkmale und Klassifikatoren
Strukturierung der Merkmale durch Pipeline-Verarbeitung
Selektion signifikanter Merkmale aus einer umfangreichen Merkmalsmenge
Auswahl eines suboptimalen Klassifikators aus einer Menge "potentieller" Klassifikationsalgorithmen
Industrielle Applikation zur Fehlererkennung auf SMD-Platinen
Anwendung des Verfahrens für medizinische Diagnoseaufgaben.

Projekt: Prozeßmodelle für die Qualitätssicherung

Ansprechpartner: Doz. Dr. sc. techn. Günter Härtig

Beteiligte Mitarbeiter: Dipl.-Ing. Olaf Jaeckel

Zusammenarbeit: Fraunhofer-Institut für Zuverlässigkeit und Mikrointegration, Berlin

Probleme der statistischen Qualitätssicherung erfordern häufig ein mathematisches Modell der Abhängigkeit relevanter Zielgrößen von einer Vielzahl quantitativer Prozeßparameter. Eine deduktive Modellbildung auf der Basis einer theoretischen Systemanalyse ist häufig nicht durchführbar. Methoden der unvollständigen Induktion zur Gewinnung einer systemadquaten Modellstruktur gelten im Rahmen der experimentellen Prozeßanalyse als m&oml;gliche Alternative. Die interessierenden GMDH-Algorithmen (Group Method of Data Handling) erstellen iterativ Polynom-Modelle von Prozessen auf alleiniger Grundlage beobachteter Ein- und Ausgangsdaten sowie aufgabenabhängiger Selektionskriterien.

Schwerpunkte der Projektuntersuchungen sind:

Implementierung und Weiterentwicklung von GMDH-Algorithmen f¨r die Strukturadaption von Polynom-Modellen
Vergleich verschiedener Selektionskriterien für die Bewertung und Optimierung der Modellstruktur
Untersuchung der Störstabilität von GMDH-Algorithmen auf der Basis generierter Pseudozufallszahlen verschiedener Verteilungsmodelle
Anwendung des Verfahrens auf Labordaten aus der Lötbarkeits/Benetzbarkeitspürfung
Testung und Applikation der Softwarebibliothek für Datenauswertungen aus industriellen Qualitätssicherungsprozessen.

Projekt: Informationstheoretische Anstäze für die Signal- und Prozeßanalyse

Ansprechpartner: Doz. Dr. sc. techn. Günter Härtig

Beteiligte Mitarbeiter:

Torsten Richter
Dr.-Ing. Gerhard Voigt
Dipl.-Ing. Kristian Weiland

Zusammenarbeit:

imc Meßsysteme GmbH, Berlin;
Zentrum für Experimentelle Chirurgie, Charité, Berlin

Die Analyse und Identifikation stochastischer Prozesse nimmt einen breiten Raum in den gegenwärtig diskutierten Problemfeldern der Prozeßleittechnik ein. Der verfolgte Lösungsansatz besteht in der Entwicklung von Beschreibungsmitteln und Analysewerkzeugen für stochastische Signale und Prozesse. Ziel der Untersuchungen ist es, durch informationstheoretische Kenngrößen und Kennfunktionen ein Kalkül für Meßdaten- und Signalanalysen sowie Klassifikationsaufgaben zu entwickeln. Bei der Bearbeitung wird besonders auf die theoretische Einbettung der Betrachtungen in bestehende Systematiken der mathematischen Statistik und der Informationstheorie geachtet.

Untersuchungsschwerpunkte sind:

Berechnung informationstheoretisch begründeter Fehlergrenzen für Meßtheorie und Qualitätssicherung
Entwicklung unkonventioneller und problemunabhängiger Kennfunktionensysteme für stochastische Übertragungsglieder, qualitätsorientierte Prozeßanalyse und Korrelationsbetrachtungen
Vereinfachung der numerischen Komplexität von Merkmalsberechnungen im Bereich der automatischen Klassifikation und Meßdatenbeurteilung
Anwendung der informationstheoretischen Klassifikationsmerkmale bei der Geräuschanalyse an Elektro-Kleinmotoren
Applikation von informationstheoretischen Beschreibungsmitteln für Beurteilungen femorocoronaler Patch-Prothesen.

Projekt: Optische Signalübertragung und -verarbeitung

Ansprechpartner: Dr.-Ing. Dietrich Schilder

Beteiligte Mitarbeiter: Prof. Dr.-Ing. habil. Wolfgang Glaser (Institut für Elektrotechnik)

Zusammenarbeit: Forschungs- und Technologiezentrum der Deutschen Telekom

Nichtlineare Effekte im Übertragungsmedium Lichtwellenleiter (LWL) beeinflussen die Signalübertragung in optischen Vielkanalsystemen zur Breitbandkommunikation, beson- ders bei hoher optischer Leistung und hoher Übertragungsrate. Nichtlineare Effekte im LWL werden auch gezielt zur optischen Frequenzumsetzung genutzt, um Vermitt- lungsfunktionen für optische Signale zu realisieren.

Schwerpunkt der Untersuchungen war die Bestimmung des Polarisationseinflusses auf die Vierwellenmischung im nichtlinearen Einmoden-LWL auch bei Kopplung der Polarisationsmoden. Nach einem allgemeinen Modell der Übertragungsstrecke wurde ein Simulationsprogramm erarbeitet, das die auftretenden Effekte in Abhängigkeit von einer Vielzahl von technischen Parametern zu untersuchen gestattet. Parallel zu diesen Rechnungen wurden Experimente im Forschungsinstitut der Telekom durchgeführt.

Projekt: Entwicklungsumgebung für die Anpassung von BDE-Systemen

Ansprechpartner: Dr.-Ing. Michael Ritzschke

Beteiligte Mitarbeiter:

Thomas Bendrich
Peter Brockhausen

Zusammenarbeit: Lüth & Dümchen Automatisierungsprojekt GmbH, Berlin

Betriebsdatenerfassungssysteme (BDE-Systeme) stellen im Zusammenwirken mit der Produktionsplanung und Steuerung (PPS) einen wesentlichen Bestandteil von Konzepten des Computer Integrated Manufacturing dar, kommen aber auch in vielen anderen Bereichen zum Einsatz. Daraus ergeben sich hohe Anforderungen für diese Systeme hinsichtlich der Anpassungsfähigkeit an vorgegebene Systemstrukturen. Konsequent modularer Aufbau, Programmierbarkeit bzw Parametrierbarkeit der Datenerfassungs- und übertragungstechnik sowie eine leistungsfähige Datenauswertesoftware sind unerläßlich. Ziel des Projektes ist die Schaffung einer modularen und nutzerfreundlichen Entwicklungsumgebung (Programmbibliothek), die eine schnelle Anpassung sowohl der technischen Einrichtungen (Terminals, Controller, Anzeigeelemente usw.) als auch der Datenauswertesoftware für konkrete Einsatzfälle ermöglicht.

Projekt: Entwicklung einer Methodik zum Vergleich von Simulatoren anhand erzielter Simulationsergebnisse

Ansprechpartner: Dr.-Ing. Michael Ritzschke

Beteiligte Mitarbeiter:

Ingo Drogi
Dipl.-Ing. Thomas Grassow
Dirk Lehmann
Thomas Sprengler

Zusammenarbeit: Leitner & Gumpert OEG, Wien

Die Vielzahl der auf dem Markt verfügbaren Simulatoren erfordert vom Anwender ausführliche Studien, bevor er sich für die Nutzung eines bestimmten Simulators zur Lösung seiner Problemstellung entscheiden kann. Üblich ist die Aufstellung einer problemspezifischen Chekliste, auf deren Basis eine Bewertung und Auswahl anhand qualitativer Merkmale erfolgt. Die Zielstellung des Projektes besteht darin, für die Klasse der diskreten Simulatoren eine Methodik zu entwickeln, die den Vergleich der mit ausgewählten Referenzmodellen erzielten Simulationsergebnisse erlaubt und damit auch quantitative Aussagen ermöglicht.

Projekt: Versuchsanlage zur Unterdrückung vegetativer Symptome

Ansprechpartner: Dr.-Ing. Michael Ritzschke

Beteiligte Mitarbeiter:

Ingo Barleben
Dipl.-Ing. Karl-Heinrich Hauptvogel

Zusammenarbeit: Universitätsklinik für HNO, Universität Magdeburg

Das spinovestibulookuläre System ist für die Orientierung im Raum, zur Empfindung der Lage und der Bewegungen ausgelegt. Experimentelle Provokationen dieses Systems führen zu einer zwanghaften Augenbewegung (dem Nystagmus) und damit zu einer Scheinbewegung der Umgebung. Nystagmusformen treten bei verschiedenen Krankheiten auf und belasten die Patienten durch Schwindelerscheinungen und Übelkeitsgefühl sehr (insbesondere bei Ohrenerkrankungen). Es soll nun mittels einer zu entwickelnden Versuchsanlage geklärt werden, ob die Mitführung des Bildes der Umgebung entsprechend der Augenbewegung zu einer Aufhebung der Scheinbewegung der Umgebung und damit zu einer Entlastung der Patienten führt. In der Versuchsanlage wird die Augenbewegung mit Hilfe der Elektronystagmographie analysiert und das Ausgangssignal zur Steuerung eines Bildmusters vor dem Auge ausgenutzt.

Veröffentlichungen und Vorträge

T. Glau, G. Härtig: Erkennung und Klassifikation von SMD-Löt- und Bestückungsfehlern mit einem Bildverarbeitungssystem. Proceedings of 6th International DAAAM Symposium (DAAAM-6), S. 111-112, Krakow, Poland, Oktober 1995.
G. Härtig: Fehlergrenzen und Qualitätssicherung - Informationstheoretische Fehlerkenngrößen fr asymmetrische Verteilungsgesetze. Proceedings of 6th International DAAAM Symposium (DAAAM-6), S. 129-130, Krakow, Poland, Oktober 1995.
O. Hochmuth, G. Lepschies, B. Meffert: Glättung und Differentiation mit nur einem Operator. Berlin: Biomedizinische Technik 40 (1995), S. 332-336.
O. Jaeckel, G. Härtig: GMDH-Algorithmen als Mittel zur Strukturoptimierung von Polynom- Modellen. Proceedings of 6th International DAAAM Symposium (DAAAM-6), S. 147-148, Krakow, Poland, Oktober 1995.
O. Jaeckel, G. Härtig: Structure adaption of polynomial models and its application to the quality assessment of wettability. Proceedings of 18th International Spring Seminar on Electronic Technology (ISSE 95), S. 122-26, Temesvar, Czech. Republik, Juni 1995.
G. Kell, H.-J. Rahn: TIMEHARP - A Time Measurement Histogram Accumulating Realtime Processor. Poster: EURO-DAC‘95/EURO-VHDL‘95, EUROCHIP University Booth, U. K., September 1995.
B. Meffert, O. Hochmuth: Datenkompression für Signalverarbeitungsaufgaben in der Biomedizin. Proceedings 2. Workshop Loughborough University of Technology and Humboldt-University Berlin, Loughborough, U. K., Oktober 1995.
C. Mrowietz, F. Jung, K. Dörschel, H. Kiesewetter, B. Meffert, G. Müller: Meßbereich und Sensitivität verschiedener Laser-Doppler-Systeme: in-vitro Evaluierung. Poster: Jahrestagung der Deutschen Gesellschaft für Klinische Mikrozirkulation und Hämorheologie, Berlin, November 1995.
M. Scheiner, F. Schuster, O. Hochmuth: Duosensor zur simultanen Erfassung der akralen Wiedererwärmung und Wiederdurchblutung. Berlin: Biomedizinische Technik 40 (1995) Ergänzungsband, S. 385-386.
K. Weiland, G. Härtig: Information parameters for evaluation and estimation of processes in quality control. Proceedings of 18th International Spring Seminar on Electronic Technology (ISSE 95), S. 16-21, Temesvar, Czech. Republik, Juni 1995.
K. Weiland, G. Härtig: Geräuschanalyse an Elektromotoren - Ergebnisse informationstheoretischer Auswertungen. Proceedings of 6th International DAAAM Symposium (DAAAM-6), S. 353-354, Krakow, Poland, Oktober 1995.
F. Winkler, T. Hummel, E. Grass, T. Morgenstern: PSI - Programmable Sensor Interface. Poster. EURO-DAC‘95/EURO-VHDL‘95, EUROCHIP University Booth, U. K., September 1995.

Weitere Aktivitäten

Prof. Dr. Beate Meffert
- Mitglied im Kuratorium der Konsul Karl und Dr. Gabriele Sandmann Stiftung (KKGS-Stiftung)
- Mitherausgeberin der Zeitschrift "Das Hochschulwesen".

Dissertationen

Lu Tian: Beiträge zur globalen Bildverarbeitung im Transformationsbereich - Transformation, Skalierung, Filterung. Juli 1995.

Diplomarbeiten

Vladimir Atanaskovik: Untersuchung und Weiterentwicklung eines Verfahrens zur automatischen Fensterung von digitalen Röntgenbildern. Oktober 1995.
Thomas Grassow: Entwicklung von fertigungsorganisatorischen Testmodellen zum Vergleich diskreter Simulatoren. September 1995.
Hartmut Jung: Numerische Programmierung stochastischer Differentialgleichungen zur Bestimmung des Verhaltens von Makromolekülen in elektrischen Mikrofeldkäfigen. Oktober 1995. (In Zusammenarbeit mit dem Institut für Biologie der HUB).
Burkhard Kopp: Vergleich verschiedener Orthogonaltransformationen bezüglich ihrer Eignung für die eindimensionale Biosignalverarbeitung. Januar 1995.
Oliver Lehm: Verarbeitung und Darstellung zweidimensionaler Signale aus der Simulation von Baugruppen eines bewegungskompensierten Formatkonverters. Januar 1995.
Juan Martnez Serra (Universität Barcelona): Entwurf von Funktionselementen zur Bildkompression für das Bildverarbeitungsprogramm Ad Oculos. Juli 1995.
Jörg Mardaus: Ausarbeitung von organisatorischen, hard- und softwaretechnischen Lösungen zur intelligenten Speicherung und Archivierung von Produkt- und Prozeßdaten in einem Industriebetrieb. Februar 1995.
Torsten Richter: Programmsystem zur Identifikation, Klassifizierung und Verkopplung von Datenverteilungen durch informationstheoretische Kenngrößen. Dezember 1995.
Stefan Sachse: Entwicklung und Realisierung eines portablen funkgekoppelten digitalen Datenübertragungssystems. März 1995.
Mario Schmidt: Entwicklung eines Algorithmus zur qualitativen und quantitativen Auswertung von Atemzyklen bei Neugeborenen aus dem Flow- und Volumensignal. November 1995.
Frank Schuster, Marius Scheiner: Entwicklung und Aufbau eines mikrocontroller-gesteuerten Meßgerätes zur berührungslosen Bestimmung der Zeitkonstanten der akralen Wiedererwärmung und - durchblutung. Juni 1995.
Aureli Soria Frisch (Universität Barcelona): Der Einsatz von LabVIEW für Signalverarbeitungsaufgaben, insbesondere zur Erkennung gesprochener Ziffern auf der Basis digitaler Signalprozessoren. Dezember 1995.
Dörte Steinborn, und Stefan Aderhold: Untersuchungen gezielter Modifikationen zur Geräuschminderung an einem Kompaktgenerator. Juni 1995.
René Unruh: Entwicklung und Realisierung eines miniaturisierten Temperatur-Dataloggers für Langzeitmessungen. Oktober 1995.
Uwe Wassermann: Entwicklung und Erprobung eines Meßplatzes "Optoelektronisches Sensorsystem mit Fuzzy-Logik-Auswertung". Juli 1995.
Holger Wilke: Entwurf und Simulation eines universellen Videointerfaces für den DSP 96002 zur Echtzeitdarstellung von Bildsequenzen verschiedener TV- und HDTV-Formate. Januar 1995.

Konvertiert; Stand 19.05.96, J.B.