Verzeichnis der Diplomarbeiten in den Jahren 1964 - 1990

- Mit Kurzfassungen versehen -

Vorwort: Die in den Jahren 1964 und 1965 angenommen Diplomarbeiten wurden von mir als Stipendiat der Fritz-Thyssen-Stiftung vergeben.. Die formale Verantwortung lag bei Professor Dr. Johannes Dörr, dem ich für die Förderung meiner Projekte hier herzlich Danke

Die hier aufgeführten Diplomarbeiten enthalten auch die unter den Nummern 145, 146 und 147 von Bernd Becker als Privatdozent vergebene Arbeiten, da sie in das engere Umfeld der im SFB 124 bearbeiteten Themen gehören. Sie enthalten aber nicht alle am Lehrstuhl in dieser Zeitspanne vergebene Diplomarbeiten. Das Verzeichnis ist vermutlich nicht vollständig, da ich nicht sicher bin von jeder der vergebenen Diplomarbeiten heute (Juli 2005) noch ein Exemplar zu besitzen.

Die im folgenden Verzeichnis Diplomarbeiten aufgeführten Arbeiten enthalten auch einige der hier aufgeführten Diplomarbeiten, im Wesentlichen aber Arbeiten aus den Jahren nach 1990. Dieses Verzeichnis ist aber nicht vollständig und enthält auch keine von mir verfassten Kurzfassungen. Die meisten dieser Arbeiten liegen aber im Netz und sind durch Anklicken zugänglich.

1964

1.Entleutner Marianne: Einbettung von Streckenkomplexen in die Kugeloberfläche.

Staatsexamensarbeit im Sommer 1964 am Institut für Angewandte Mathematik der Universität des Saarlandes.

Zusammenfassung: Die Basis bilden die Definitionen von Streckenkomplexen und ihrer Zerlegung in k-fache Zusammenhangskomponenten, die Definition von kombinatorischen 2-dimensionalen Mannigfaltigkeiten. Es wird gezeigt, dass ein Graph genau dann auf eine Kugeloberfläche einbettbar ist, wenn das für seine 2-fach zusammenhängenden Komponenten gilt. Unter Verwendung des Jordanschen Kurvensatzes wird ein Entscheidungsverfahren für die Planarität der Graphen angegeben. Komplexitätsaspekte werden nicht behandelt.

2.Steinhauer Hansgeorg: Untersuchung von Streckenkomplexen mittels eines Rechenautomaten. Staatsexamensarbeit angefertigt am Institut für Angewandte

Mathematik der Universität des Saarlandes im Sommer 64.

Zusammenfassung: Motivation: Verdrahtungsprobleme. Verwandt mit 1. Zerlegung in Komponenten wird unter Effizienzgesichtspunkten behandelt.

1965

3.Göhring Wolf: Vergleich von Lernprozessen. Diplomarbeit am Institut für Angewandte Mathematik der US (Universität des Saarlandes) Januar 65 eingereicht.

Zusammenfassung: Es wird der von Wolfgang Händler eingeführte Lernprozess verglichen mit Lernprozessen auf Basis von Markovprozessen.

4. Heinrich, Walter: Formale Eigenschaften von Programmiersprachen. Diplomarbeit am IAM (Institut für angewandte Mathematik) der US Mai 65.

Zusammenfassung: Es werden durch endliche Relationen erzeugte assoziative Systeme betrachtet, Post'sche Systeme und Chomskysprachen und die in diesem Zusammenhang bewiesenen Entscheidbarkeits- und Nichtentscheidbarkeitsresultate in einheitlicher Form dargestellt.

5. Stucky, Wolffried: Untersuchungen über den Zustandsgraphen von Schwellenelementen mit Rückkopplung im Autonomen Fall. Diplomarbeit am IAM der US Mai 65.

Zusammenfassung: Es handelt sich um die Untersuchung endlicher Automaten, die sich durch Schwellenelemente realisieren lassen. Die Motivation kam aus Anwendungen zur Zielerkennung beim Einsatz von Radargeräten.

1966

6.Schneider, Walter: Lineare fehlerkorrigierende optimale Codes. Diplomarbeit am IAM der US März 66

Zusammenfassung: Es wird ein Algorithmus angegeben, der zu vorgegebener Blocklänge du Anzahl der korrigierbaren Fehler einen einfachsten linearen fehlerkorrigierendenCode berechnet. Der Algorithmus wurde auf der X! Electrologica implementiert und erprobt. Es wurden neue zu den quasiperfekten (15,7,2) und (21,12,2)) Bose-Chauduri äquivalente Codes gefunden, die zu (17,7,2)-Codes bzw. (22,13,2)-Codes erweitert werden konnten..

7. Langendörfer, Horst: Der C-Operator von McCarthy, Diplomarbeit am IAM der US Juni 1966.

Zusammenfassung: McCarthy hat den von ihm so benannten C-Operator in die Programmierung eingeführt; er ordnet Prädikaten und Funktionen in bestimmter Anordnung eine neue Funktion zu. Der Operator hat als bedingter Ausdruck in ALGOL Verwendung gefunden. Die von McCarphy „angeführte Theorie lässt einige Wünsche offen.“ Langendörfer definiert diesen Operator als Operation auf der Menge der Turingmaschinen und untersucht das so erhaltene formale System. Der C-Operator erweist sich dem mu-Operator äquivalent. Er ist aber nicht universell in dem Sinn, dass sich zwei Turingmaschinen, die jeweils eine Menge aufzählen durch ihn so verbinden lassen, dass man eine Maschine erhält, die die Vereinigung der Mengen aufzählt.

8. Schnorr, Claus-Peter: Untersuchungen von Contextfreien Sprachen nach algebraischen Gesichtspunkten. Diplomarbeit am IAM der US.

Zusammenfassung: Darstellung der contextfreien Sprachen durch formale Potenzreihen nach Schuetzenberger (Classification of Chomsky Languages, Proceedings of IFIP Congress 1965)). Das Ziel besteht in einer Klassifikation der c.f.-Sprachen relativ zu gewissen die Ableitungsstruktur erhaltenden Transformationen. Diese sind orientiert an Funktoren zwischen den zu den erzeugenden Grammatiken gehörigen X-Kategorien . Weiter unter sucht Schnorr Unterklassen der c.f. Sprachen, die eine „Matrixdarstellung“ besitzen. Er kann einige Unterklassen der c.f.-Sprachen charakterisieren, die solche Darstellungen zulassen.

9. Walter, Hermann: Stabilitätsuntersuchungen an stückweise affinen Abbildungen mit Anwendungen in der Theorie der lateralen Inhibitation. Diplomarbeit am IAM der US.

Zusammenfassung: W. Reichardt vom MPI für Kybernetik in Tübingen fand, dass sich die Signalverarbeitung im Auge des Krebses Limulus durch die Iteration einer stückweise affine Abbildung in Verbindung mit Schwellen zur Hinderung von schwachen Signalen beschreiben ließ. Das ist die laterale Inhibitation im rückgekoppelten Fall. Reichert hatte den 1-dimensionalen Fall durch eine Integralgleichung modelliert und diskutiert. Walter untersucht in seiner Diplomarbeit die Stabilität der Iteration von stückweise affinen Abbildungen. Walter zeigt im Wesentlichen: Sind die Eigenwerte der beteiligten Matrizen echt kleiner 1 und ist die stückweise affine Abbildung stetig, dann ist die Iteration stabil.

10. Raach, Ernst: Vergleich verschiedener Verfahren zur Konstruktion von Normalformen von Matrizen. Staatsexamensarbeit am IAM der US.

Zusammenfassung: Hintergrund: Systeme linearer Differentialgleichung. Es werden verschiedene Normalformen von Matrizen hinsichtlich ihrer Effizienz (Laufzeit und Präzision) bei der Implementierung auf Rechenlagen diskutiert und experimentell erprobt.

11. Koetz, Werner: Lineare Sprachen. Diplomarbeit m IAM der US.

Zusammenfassung: Es werden die linearen Chomsky-Sprachen feiner klassifiziert und hinsichtlich der Komplexität ihres Wortproblems diskutiert . Interessant ist der Sonderfall der gleichförmig linearen Sprachen, die auch durch eine einfache Erweiterung des endlichen Automaten akzeptier werden können.

12. Kihm, Gunter: Das topologische Problem der gedruckten Schaltung. Diplomarbeit am IAM der US.

Zusammenfassung: Die Arbeit behandelt das Problem, die „Verdrahtung“ einer elektronischen Schaltung möglichst planar vorzunehmen. Gegeben ist also ein Streckenkomplex (Graph), der unter Berücksichtigung von gewissen Nebenbedingungen in die Ebene eingebettet werden soll. In jedem Fall soll das so geschehen, dass vorgegebene Anschlusspunkte am Rand der Platine liegen oder auf dem Weg zum Rand nur möglichst wenige Brücken erforderlich sind. Ist der Graph 2-fach zusammenhängend, ist die Freiheit auf die Wahl des Randzyklus eingeschränkt. Ist der Zusammenhangsgrad geringer, ist die Freiheit größer. Die Arbeit gibt liefert abschließend Programme, die die gestellten Aufgaben für die praktisch (in einem Labor von Telefunken) vorliegenden Probleme hinreichend effizient lösen. Basis der Arbeit: Hotz: Einbettung von Streckenkomplexen in die Ebene; Mathematische Annalen 1966

1967 13.Gothier, Wolfgang: Über elementare formale Systeme und deren Zusammenhang mit Semi-Thue-Systemen. Diplomarbeit am IAM der US.

Zusammenfassung: Die Arbeit vergleicht die von R.M. Smullyan 1961 eingeführten „Elementary Formal Systems“ mit den Semi-Thue-Systemen und beweist deren Äquivalenz.

14. Frick, Helmut: Sätze zum Zusammenhang zwischen der Theorie der abstrekten Automaten und der Algebra. Diplomarbeit in Mathematik am Mathematischen Institut der Universität Tübingen.

Zusammenfassung: Die verschiedenen existierenden Definition für endliche Automaten werden hier dadurch erweitert, dass die endlichen Automaten als Algebren aufgefasst und behandelt werden. Es ergeben sich daraus keine neuen Anregungen für die Weiterentwicklung der Theorie.

15. Blatt, Hans-Peter: Näherungsweise Berechnung der Tschebyscheff Approximation durch diskrete Stützstellen. Diplomarbeit am IAM der US.

Zusammenfassung: Die Berechnung der T-Approximation von berechenbaren stetigen Funktionen ist nur in Sonderfällen direkt möglich. Das iterative Approximationsverfahren von Remez(1931) benötigt die Extrema der Fehlerfunktion und ist deshalb numerisch nicht geeignet. Hier wird nun ein Verfahren von Stiefel verwendet, das zu vorgegebenen Stützstellen das Polynom exakt berechnet. Ziel der Arbeit: Berechnung geeigneter Stützstellen, so dass man mit wenigen Stützstellen auskommt und exakte Fehlerschranken erhält. Insbesondere: T-Approximation von Polynomen hohen Grades durch solche niedren Grades. Das Verfahren wurde auf der X1 Electrologica implementiert.

16. Claus, Volker: Der Homomorphiebegriff bei stochastischen Automaten. Diplomarbeit am IAM der US.

Zusammenfassung: Die Motivation für die Untersuchung dieser Automaten wird aus zwei verschiedenen Quellen gespeist: Physikalische Systeme sind stets mit einer gewissen Unsicherheit bei den Zustandsübergängen behaftet, und Monte Carlo Methoden, die in vielen Fällen gute Approximationen schwer berechenbarer Funktionen liefern.

In der Arbeit werden die aus der Theorie der endlichen Automaten bekannten Konzepte auf die Klasse der stochastischen Automaten übertragen: Äquivalenzbegriff und Homorphiebegriff. Diese Übertragung gelingt vollständig unter einer sehr schwachen Voraussetzung. Zwei stochastische Automaten sind äquivalent (akzeptieren genau die gleichen Eingabemengen), genau dann wenn es eine Kette von Homorphismen gibt, die beide Automaten verbinden.

1968

17. Spaniol, Otto: Intervallarithmetik unter wahrscheinlichkeitstheoretischen Gesichtspunkten. Diplomarbeit am IAM der US.

Zusammenfassung: Zunächst wird die Moore’sche Intervallarithmetik(1965) definiert und auf die Gültigkeit der Körperaxiome hin überprüft. Die Arbeit charakterisiert die Sonderfälle, in denen zumindest das Distributivgesetz gilt. Der umfangreichere Teil der Arbeit gilt der erweiterten Intervallarithmetik von Apostolatus und Kulisch, die allerdings in Teilen abgeändert wird, da diese Arithmetik numerische Schwierigkeiten mit sich bringt. Numerisch einfache Abschätzungen der Intervallgrenzen sind sehr großzügig. Aus diesem Grund wird eine wahrscheilichkeitstheoretische Verteilung der im Rahmen der Berechnung möglichen exakten Werte hergeleitet. Allerdings erfordert die Berechnung dieser Verteilung einen hohen algorithmischen Aufwand.

18. Backes, Siegward: Eine geometrische Theorie der Linearen Optimierung. Diplomarbeit an dem IAM der US.

Zusammenfassung: Die Arbeit stellt zunächst das Simplexverfahren vor. In Grenzfällen können aufgrund von Rundungseffekten Endlosschleifen auftreten. Es wird eine Variante des Verfahrens entwickelt, bei der diese Rundungseffekte keinen Einfluss haben.

19. Both, Willibald: Zielerkennung in Radarsignalfolgen mittels binärerer Digitalisierung und Filterung. Diplomarbeit am IAM der US.

Zusammenfassung: Die Arbeit geht zurück auf Hotz, G.:Digital Filters of Threshold Elements, Proceedings of IFIP Congress 62, die von einer Behörde der USA für einige Jahre als geheim eingestuft worden war. Später wurde es im Auftrag von Eurocontrol weitergeführt. Siehe auch Diplomarbeit von Stucky. Die Arbeit behandelt die binäre Digitalisierung der Echoimpulse des Radars in Verbindung mit Filtern aus Schwellenelementen unter Anwendung des Likelyhood-Quotiententestes. Das erarbeitete Verfahren wurde praktisch an Radardaten, die von Eurocontrol und dem Forschungsinstitut für Funk und Mathematik, Werthhhoven zur Verfügung gestellt wurden.

20. Schlicker, Georg: Klassen von Sprachen und Linear Beschränkte Automaten. Diplomarbeit am IAM der US.

Zusammenfassung: Es wird eine Hierarchie von Chomsky-Sprachen in eine Hierarchie von linearbeschränkten Automaten eingebettet und Abschlusseigenschaften untersucht.

21. Klar, Gunter: Algebraische Codes mit veränderbarer Redundanz. Staatsexamensarbeit am IAM der US:

Zusammenfassung: Verschiedene Nachrichten mögen verschiedene Anforderungen an die Störsicherheit eines Übertragungskanals stellen. Zahlenko0lonnen ohne Redundanz erfordern eine hohe, Texte in einer natürlichen Sprache eine geringere Übertragungssicherheit. Es werden in der Diplomarbeit Konstruktionen von Automaten zur Kodierung und Dekodierung von Nachrichten behandelt, die sich leicht auf verschiedene Sicherheitsstufen umstellen lassen.

22. Böhle, Heidemone: Spezielle Untersuchungen an X-Kategorien. Diplomarbeit am IAM der US.

Zusammenfassung: Die Ableitungsstruktur von Grammatiken lässt sich durch X-Kategorien erfassen: Hotz, G. Eindeutigkeit und Mehrdeutigkeit formaler Sprachen, EIK 2 (1966), und sie spielt eine wichtige Rolle in der Definition der strukturellen Äquivalenz formaler sprachen. Hotz, G. Homorphie und Äquivalenz formaler Sprachen. 3. Kolloq. Über Automatentheorie 1965, Birkhäuser Verlag Basel (1967). Die Diplomarbeit untersucht Fragen wie die Entscheidbarkeit der Surjektivität oder Injektivität von Grammatik Funktoren. Damit im Zusammenhang stehen Fragen nach Ableitungszyklen. Böhle zeigt, dass diese Zykelfreiheit . Diese ist für die freien X-Kategorien entscheidbar, nicht aber z.B. für die Klasse der Sprachen vom Erweiterungstyp.

23. Graeber, Karl-Albrecht: Eine kategorientheoretische Definition der Berechenbarkeit. Diplomarbeit am IAM der US.

Zusammenfassung: Funktionale Programmiersprachen finden ein zunehmendes Interesse aufgrund ihrer leichteren Verständlichkeit. In dieser Arbeit wird gezeigt, dass sich jede berechenbare Funktion im Rahmen der freien D-Kategorien funktional definieren lässt.

24. Bartholomes, Friedrich: Homomorphismen und Reduktionen linearer Sprachen. Diplomarbeit am IAM der US

Zusammenfassung: Eine Ausarbeitung dieser Diplomarbeit wurde als Band 32 in der Reihe Lecture Notes in Operations Research and Mathematical Systems 1970 publiziert. Die Zusammenfassung bezieht sich auf diesen Band.

Die im Fall der deterministischen endlichen Automaten einfache Theorie, die garantiert, dass minimale endliche Automaten isomorph sind und alle äquivalente Automaten durch Ketten von Homorphismen ineinander übergeführt werden können, lässt sich schon bei Einbeziehung der nichtdeterministischen Automaten nur eingeschränkt übertragen. In dieser Arbeit wird untersucht, in wie weit eine Übertragung dieser Theorie auf lineare Sprachen und Verallgemeinerungen der linearen Sprachen zu gekoppelten linearen Sprachen möglich ist. Letztere Klass führt aus der Klasse der kontextfreien Sprachen heraus, die es nicht gestatten schon recht triviale Sprachen zu modellieren. Die Übertragung gelingt mit den Einschränkungen, die wir schon vom nichtdeterministischen endlichen Automaten her kennen durch die Modellierung der Ableitungen als Morphismen freier monoidalen Kategorien und Funktoren zwischen diesen Kategorien.

25. Fischer, Wolfgang: Wahrscheinlichkeitsfunktionen auf X-Kategorien. Diplomarbeit am IAM der US.

Zusammenfassung: Es werden auf der Menge der durch die Elemente der freien X-Kategorien repräsentierten Ableitungen formaler Sprachen Wahrscheinlichkeitsverteilungen definiert, um eine Aussage über die mittlere Laufzeit von Algorithmen zur Entscheidung von Wortproblemen abzuschätzen. Die Arbeit enthält in diesem Zusammenhang interessante Resultate. Das Forschungsprogramm konnte aber nicht in vollem Umfang realisiert werden.

1969.

26. Schmidt, Volker: Schaltwerke zur Umwandlung von Dual- oder Gray-Code-Zahlen in dual codierte Dezimalzahlen. Diplomarbeit zur Erlangung des Diploms in Physik an der US.

Zusammenfassung: Es werden Schaltkreise zur Lösung der im Thema der Arbeit genannten Aufgabe entwickelt, ihre Korrektheit bewiesen und technisch realisiert. Die Laufzeit und Kosten werden in Abhängigkeit von der Stellenzahl der umzuwandelnden Zahlen abgeschätzt.

27. Heine, Rolf: Isomorphie endlicher symmetrischer Graphen – Untersuchungen über ein Entscheidungsverfahren. Diplomarbeit am IAM der US.

Zusammenfassung: Es wird ein Algorithmus angegeben, die Isomorphie von orientierten symmetrischen Graphen zu entscheiden. Eine präzise Abschätzung der Laufzeit gelingt nicht. Aber auf Basis der algorithmischen Lösung zahlreicher Beispiele werden Graphiken erzeugt, die eine exponentielle Laufzeit des Algorithmus deutlich belegen.

28. Gräber Wolfgang: Push-down Automaten und Contextfreie Sprachen. Diplomarbeit am IAM der US.

Zusammenfassung: Die Arbeit schließt an Schnorrs Diplomarbeit an und sie baut wesentlich auf den Ansätzen und Resultaten von Schützenberger auf. Die Arbeit stellt die Theorie der c-.f. auf der Basis von Monoiden Gruppen Homomorphismen und inversen Homomorphismen dar.

29. Bouillon, Gerd: Minimisierung boolescher Funktionen. Diplomarbeit am IAM der US.

Zusammenfassung: Es werden die bekannten Algorithmen von Roth und McCluskey effizient implementiert und an Beispielen erprobt.

1970

30. Becker, Heinrich: Zur Axiomatik der µ-Rekursivität. Diplomarbeit am IAM der US

Zusammenfassung: Es geht um eine Algebraisierung des Berechenbarkeitsbegriffes. Es wird der µ-Operator durch die Forderung des Abschlusses der berechenbaren Funktionen unter der Invertierung einer Funktion er4setzt. Dies wurde auch schon von Julia Robinson versucht, aber nicht konsequent. Weiter wird auch das Schema der primitiven Rekursion ersetzt. Bei J.R. besteht eine Unklarheit: Sie präzisiert nicht, ob die Inversion nur für bijektive Funktionen zugelassen werden soll oder auch die Rechtsinverse surjektiver Funktionen. Es wird gezeigt, dass man sich auf das Invertieren bijektiver Funktionen beschränken kann und dass Rechtsinverse von berechenbaren surjektiven Funktion nicht berechenbar sein müssen. (Leider ist mir durch die Entwicklung des Studiengangs Informatik dieser Ansatz für viele Jahre aus den Augen geraten. Erst im Zusammenhang mit der Einbettung der Theorie der Berechenbarkeit in eine Theorie der analytischen Funktionen wird der Witz sichtbar)

31. Becker, Werner: Maximale und synchronisierende Kodes. Staatsexamensarbeit am IAM der US

Zusammenfassung: Zusammenfassende Darstellung einer Arbeit von M. P. Schuetzenberger Es werden Vermutungen Schuetzenbergers über den Zusammenhang beider Klassen von Kodes untersucht. Schuetzenberger hat diese Vermutungen für einige Sonderfälle bewiesen.

Basis der Arbeit: Charakterisierung der Untergruppen von Monoiden durch minimale Quasiideale. Auf dieser Basis werden notwendige und hinreichende Bedingungen für die Maximalität von allgemeinen und von Präfixkodes untersucht. Spezielles neues Resultat über synchrone Kodes.

Es wird eine Konstruktion für die Klasse aller maximalen endlichen Präfixkodes angegeben. Basis für die Vermutung: Alle Kodes können in Präfixkodes umgewandelt werden und alle maximalen endlichen Präfixkodes sind synchron. (hierbei spielen auch einige Sätze von Shannon herein.)

32. Dittrich Renate: Eingeschränkte elementare formale Systeme Diplomarbeit am IAM der US

Zusammenfassung: Die Arbeit überträgt die von Chomsky eingeführten Klassen formaler Sprachen auf die elementaren formalen Systeme von Smullyan. Feinere Klassifikationen der Chomskyklassen lassen sich nicht so ohne weiteres übertragen. Es werden aber intuitiv verwandte Sprachklassen definiert und diskutiert. Weiter werden Beziehungen zu den linear beschränkten Automaten behandelt.

33. Kaufholz, Gerd: Der programmierbare endliche Automat Diplomarbeit am IAM der US

Zusammenfassung: Es handelt sich um einen 2-Band endlichen Automaten; eines der beiden Bänder wird als Programmband interpretiert. Es wird also nicht nach der Menge der Bänderpaare gefragt, die ein endlicher Automat akzeptieren kann, sondern nach der Menge der akzeptierten Bänder zu gegebenem Programmband. In anderen Worten: Das Interesse gilt den Projektionen der durch Zweibandautomaten akzeptierten Mengen und zwar mit Interesse an den über dem Programmband liegenden Mengen. Es wird gezeigt, dass diese Mengen regulär sind.

Es werden k-Universalautomaten eingeführt. Das sind Automaten deren akzeptierte Sprachklassen nur durch Aufnahme eines k+1-ten Zustandes vergrößert werden können. Es gibt keine universellen Einwegeautomaten. Für Zweiwegeautomaten bleibt diese Frage offen.

34. Sinn, Ulrich: Grundlagen der Informationstheorie; ein Beweis des Fundamentalsatzes für Gruppenkodes; Darstellung und Leistungsfähigkeit von Produktkodes. Diplomarbeit am IAM der US

Zusammenfassung: Es wird ein Beweis des Fundamentalsatzes der Informationstheorie (binär-symmetrische Kanäle mit endlichem Gedächtnis) für den Sonderfall der Gruppenkodes gegeben. Dieser Beweis und die Verknüpfung von Gruppenkodes zu Produktkodes sind das zentrale Thema der Arbeit. Die Gruppenkodes bleiben weit unter der Entropieschranke. Von Elias eingeführt. Die hier vorliegende Weiterführung dieses Ansatzes in dieser Arbeit wurde leider durch eine Arbeit von Wenig vorweggenommen.

35. Wunn, Gerd: Minimale lineare und affin-lineare Realisierungen von Permutationen. Diplomarbeit am IAM der US

Zusammenfassung: Es werden Zähler untersucht, die durch lineare Schaltwerke erzeugt werden. Die interessierende Fragestellung: Wie zeigt man, dass ein linearer Zähler nicht durch einen kleineren ersetzt werden kann. Es werden einige in diesem Zusammenhang interessante Resultate erzielt, aber das gestellte Problem bleibt offen.

1971

36. Breyer, Christiane: Erkennung von einfachen Fehlern bei Zählern. Diplomarbeit am IAM der US.

Zusammenfassung: Fehler, die in der Hardware auftreten, die an schwer zugänglichen Stellen eingesetzt wird (z.B. Weltraum), sollten nicht unbedingt zum Ausfall des Systems führen. Die Arbeit behandelt einen einfachen Sonderfall: Zähler, die durch ein lineares Schaltwerk realisiert werden und die gegen das Auftreten von Einzelfehlern gesichert sein sollten. Es werden zuverlässige Zähldekaden konstruiert und Zähler, die durch parallel laufende, homomorphe Zähler ergänzt werden.

37. Fox, Maria: Mathematische Modelle einer Infektionskrankheit. Diplomarbeit am IAM der US.

Zusammenfassung: Es handelt sich um die Untersuchung der Ausbreitung von Infektionen unter der verschiedenen Modellannahmen. Einfachstes Modell: Die Größe einer Anfangspopulation mit einer frisch infizierten Teilmenge ist gegeben. Der zeitliche Zuwachs an Infizierten ist proportional zu der der zu diesem Zeitpunkt noch nicht infizierten und der Anzahl F der Infizierten, die zu diesem Zeitpunkt den Erreger ausscheidenden. Dieser Fall lässt sich durch eine Differentialgleichung modellieren, wie bekannt war. Das Besondere: Die Anzahl der Ausscheidenden ist gegeben durch die Anzahl der in einem Zeitintervall fester Größe in einer um eine Konstante nachhinkenden Vergangenheit. Interessante Resultate: Es erkranken nicht alle. Die Anzahl der Infizierten strebt gegen eine asymptotischen Wert <F. Das Modell wurde verfeinert durch die Annahme, dass sich Elemente der Population begegnen müssen, um sich zu infizieren und dass die Wahrscheinlichkeit hierfür von der geometrischen Struktur des Raumes (der möglichen Bahnen der Individuen) abhängig ist. Dieser Fall wurde durch eine Monte Carlo Simulation für verschiedene Szenarien bearbeitet.

38. Franz, Karl-Otto: Untersuchungen über den Aufwand bei der LR(0)-Analyse Diplomarbeit am IAM der US.

Zusammenfassung: Es wird ein in meiner Vorlesung skizziertes Verfahren zur Konstruktion eines PDA zur Analyse von LR(0)-Sprachen näher untersucht. Es wird die Größe des steuernden endlichen Automaten in Abhängigkeit von der Größe der zugrunde liegenden Grammatik abgeschätzt.

39. Heise, Dieter: Über die Verwendung von speziellen Schwellenelementen als logische Gatterbausteine. Diplomarbeit in Physik an der math. nat. Fakultät der US.

Zusammenfassung: Es geht um die physikalische Realisierung von Schwellenelementen ohne dabei auf die verfügbaren logischen Operationen zurückzugreifen. Die Arbeit entstand in Kooperation mit dem Lehrstuhl Eckart und wurde im elektrologischen Praktikum durchgeführt.

Vorgabe für den Entwurf war die Kompatibilität des Schwellenelementes mit existierenden Gattern. Das Resultat wurde durch den Aufbau verschiedener Schaltungen hinsichtlich Schaltgeschwindigkeit und Belastbarkeit getestet.

40. Rixecker, Ulrich: Der Pushdowntransducer Diplomarbeit am IAM der US

Zusammenfassung: Ausgangspunkt der Arbeit: D. Scott: Some Definitional Suggestions for Automata Theory . Am Beispiel des Pushdown Automaten untersucht Rixecker inwieweit der Kalkül dazu taugt eine übersichtliche Theorie aufzubauen. Das Resultat ist gespalten: die Theorie wird wesentlich schwerfälliger. Bei der Anwendung zur Konstruktion konkreter Automaten könnte der Kalkül unter der Voraussetzung einiger Normierungen der entstehenden Programme hilfreich sein.

41. Kemp, Rainer: Binäre und unäre Ausdruckssprachengrammatiken im Zusammenhang mit LR(k) – Grammatiken. Diplomarbeit am IAM der US.

Zusammenfassung: Es handelt sich um die Untersuchung von Ausdrücken mit unären und binären Operationen, die getypt sind; d.h. es wird unterschieden ob eine Addition auf ganzen Zahlen oder auf Gleitkommazahlen operieren soll. Die Substitution von Variablen eines bestimmten Typs durch einen Ausdruck, der nicht geklammert ist, kann zu Ausdrücken führen, deren Auswertung aufgrund von Prioritätsregeln zu Typkonflikten führt. Diese Konflikte kann man vermeiden, indem man die Substitutionen mit Kontextbedingungen versieht. Es stellt sich die Frage in wie weit man diese Kontextbedingungen durch eine Vergrößerung der Menge der Zustandsvariablen auffangen kann, sodass man LR(k) – Sprachen erhält. Kemp klärt diese Fragen vollständig in seiner umfangreichen Arbeit. Zusätzlich gibt er Abschätzungen über die Größe der resultierenden LR(0) – Automaten.

42. Kopp, Herbert: Zur Theorie der Programmiersprachen. Diplomarbeit am IAM der US.

Zusammenfassung: Die Arbeit baut auf meiner Vorlesung: Grundlagen einer Theorie der Programmiersprachen: I. Rekursive und nichtrekursive Unterprogrammtechniken. II. Typen Operationen, Ausdrücke auf.

Es werden in der Arbeit hinreichende und notwendige Bedingungen für in meiner Vorlesung definierte Sprachklassen dazu angegeben in wie weit die Programme alle primitiv rekursiven oder alle µ-rekursive Funktionen zu berechnen gestatten. Es wird weiter eine Interpretationstechnik angegeben, die mit einem übersehbaren Speicherplatzbedarf auskommt. Die hierfür erforderlichen Voraussetzungen sind aber nicht für all Programme der definierten Sprachen erfüllt.

43. Zumkeller, Reinhard: Eine kategorielle Beschreibung der gekoppelten Ersetzungen. Diplomarbeit am IAM der US. (Jan. 71)

Zusammenfassung: Diese Arbeit behandelt Fragen, die auch schon in der Diplomarbeit von Bartholomes behandelt wurden. Die dort betrachteten gekoppelten Ersetzungen werden etwas allgemeiner behandelt. Die dort angedeutete Theorie wird auch auf die Verallgemeinerung übertragen. Es werden Abschlusseigenschaften dieser Sprachklasse und effiziente Analysemethode untersucht und entwickelt. Interessante Beispiele runden die Arbeit ab.

44. Lippe, Wolfram: Realisierung eines Verfahrens zur schnellen Multiplikation großer Zahlen. Diplomarbeit am IAM+I (=Institut für Angewandte Mathematik und Informatik)

Erste Diplomarbeit in Informatik in Saarbrücken, vielleicht sogar in der BRD

Zusammenfassung: Grundlage der Arbeit waren Multiplikationsverfahren von Karacuba(1962), Toom(1963) und Schönhage(1966) . Schönhagens Konstruktion wird in allen Details dargestellt und durch Mikroprogramme beschrieben, um die Verwendung des originellen Verfahrens zur Multiplikation großer Zahlen als Standartverfahren in Computern zu untersuchen.

1972

45. Heise, Brigitte: Darstellung der Automatentheorie im Kalkül von Dana Scott. Diplomarbeit in Mathematik am IAM+I der US.

Zusammenfassung: In der Arbeit werden Sätze, die D. Scott nur skizziert oder ganz unterdrückt hat, ausführlich bewiesen. Der Bezug zwischen den Automatentypen und der Scottschen Darstellung in Form von Programmen werden ausführlich diskutiert, um die Grenzen zwischen entscheidbar und nichtentscheidbar in diesem Modell deutlich sichtbar zu machen.

46. Huwig, Hagen: Einige Sätze über Stackautomaten im Kalkül von D. Scott. Diplomarbeit am IAM+I der US im Fach Mathematik.

Zusammenfassung: Es wird der 2-Weg-deterministische Stackautomath untersucht. Es wird gezeigt, dass es zu jedem linear beschränkten Automaten ein Programm für den 2-Wege-St. gibt, so dass beide die gleiche Sprache akzeptieren. Wie Knuth gezeigt hatte, gibt es zu jeder context-sensitiven Sprache einen 2-Weg-Stack, der diese akzeptiert. Huwig zeigt die Entscheidbarkeit des Halteproblems für den 2-Weg-Stack und gibt eine Normalform an, die für jede Eingabe anhält. Stets wird der Automat in Scotts Sprache gefasst.

47. Paul, Wolfgang: Verschiedene Realisierungen des Streamingkonzepts und damit verbundene Optimierungsfragen. Diplomarbeit in Informatik am IAM+I in Informatik der US.

Zusammenfassung: Ausgangspunkt der Arbeit: Beobachtung, dass die CPU des Computers wesentlich schneller ist, als der Zugriff auf die damals verwendeten Kernspeicher. Die Problemstellung der Arbeit: Den durch dieses Missverhältnis in den Operationszeiten entstehenden Leerlauf der CPU durch geeignete Organisation der Programmauswertung für interessante Aufgabenklassen zu vermeiden. Paul untersucht in seiner Arbeit, das zu diesem Zweck entwickelte Streamingkonzept. Dieses Konzept beruht auf der Idee mehrere Speicher einzurichten, die parallel betrieben werden können.

Zur Modellierung der CPU definiert er einige Mikroprogramme, mit denen er Listenoperationen beschreiben kann, d.h. Elemente zweier Listen elementweise mit einer Operation zu verknüpfen und um diese Operationen in einem möglichst ununterbrochenen Datenstrom zu betreiben. Er gibt mehrere Modelle an, für die er das effizient tun kann. Er schätzt für ein Modell den Gewinn an mittlerer Leistung ab und wendet die Resultate speziell auf die Matrixmultiplikation an.

48: Pfahl, Rudolf M.: Entropie standartregulärer Mengen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Übergänge im Zustandsgraph für diese Mengen werden als stochastische Matrix modelliert. Die Entropie ergibt sich dann als Logarithmus des größten Eigenwertes der Matrix.

1973

49. Alt, Helmut: Äquivalenz von einfachen Programmen Diplomarbeit am IAM+I der US.

Zusammenfassung: Es wird das Äquivalenzproblem für Programme behandelt, die nur eine Folge von Zuweisungen sind. Auf der rechten Seite der Zuweisungen dürfen formale Ausdrücke stehen.

Die Arbeit behandelt zunächst den Fall, dass die rechten Seiten auch nur aus Variablen bestehen, die aber verschieden Typen haben dürfen. Z.B. Floatingpoint zu Integer, was eine Rundungsoperation bewirkt. Für diesen Fall lassen sich die minimalen Programme berechnen. Für den allgemeinen Fall wird ein endliches Relationensystem angegeben, das die Äquivalenz dieser Programme vollständig beschreibt. (Die Arbeit konnte nicht publiziert werden, da J. W. de Bakker die gleiche Untersuchung zuvor publiziert hatte: LNMS 1971)

50. Bous, Hermann: Modell eines automatisierten Bibliotheksystems, Teil 1. Diplomarbeit am IAM+I der US.

51. Eibner, Alois: Modell eines automatisierten Bibliotheksystems, Teil 2. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um ein größeres Projekt, das Bous und Eibner gemeinsam bearbeitet haben. Beide waren in gleicher Weise beteiligt. Die Trennung in Teil 1 und Teil 2 ist relativ willkürlich.

Das erstellte System unterstützt die Ausleihe und die Verwaltung der Bibliothek. Das Programmpaket, das die Ausleihe unterstützt, kann auch vom Benutzer der Bibliothek zur Unterstützung von Recherchen aufgerufen werden. Das zweite Paket dient zur Änderung und Ergänzung von Dateien, zur Unterstützung der Katalogerstellung und von Statistiken. Das System wurde für die UB geschrieben. COBOL wurde als Programmiersprache verwendet.

52. Weidner, Wolfgang: Untersuchungen über eine Arbeit von D. Knuth. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Diplomarbeit sollte den Inhalt zweier Arbeiten von Knuth zum Thema Semantik kontextfreier Sprachen auf Basis des Konzepts der X-Kategorien, d.h. freier monoidalen Kategorien darstellen. Der Ansatz ist nahe liegend. Man hat nur auf Schwierigkeiten zu achten, die Rekursionen erzeugen können. Das kann man mit erfassen, indem man statt Funktionen Relationen in den Interpretationen verwendet und im Übrigen Konstruktionen, wie bei der Modellierung von Knoten auf Basis der freien D-Kategorien.

53. Weber, Marc: Zur Semantik von Programmiersprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Grundlagen der Arbeit bilden meine drei technischen Berichte Grundlagen einer Theorie der Programmiersprachen I, II, und III. Weiter wird auf Langmaaks Vorlesung Programmiersprachen zurückgegriffen. In der Arbeit wird ein Compiler für die definierten Programmiersprachen angegeben und seine Korrektheit bewiesen.

54. Kammer, Daniele: Ackermann gestufte Komplexitätsklassen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Der hier definierte Ackermannoperator erzeugt auf strikt wachsende einstellige Funktionen angewendet Funktionen, die alle aus dieser Funktion durch primitive Rekursion erzeugte Funktionen asymptotisch majorisiert. Darüber hinaus majorisiert sie auch die Zeit- und Bandkomplexität dieser Funktionen. Es werden Hierarchiesätze für Funktionsklassen bewiesen und interessante offene Fragen formuliert.

55. Gräber, Stefan: Strategien beim Mühlespiel. Diplomarbeit am IAM+I der US.

Zusammenfassung: Das Mühlespiel wird als Beispiel eines 2-Personennullsummenspiels behandelt. Implementiert wird aus Knappheit an Ressourcen nur ein verkürztes Mühlespiel. Das Spiel ist zu Ende, wenn alle Steine gesetzt sind. Sieger ist derjenige, der die meisten Mühlen gewonnen hat. Die gewonnene Strategie wird auf der CD 3300 implementiert.

56. Fischer, Andreas: Aufbau und Organisation einer Programmothek. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es wird der Rahmen der Organisation des Betriebssystem der CD 3150 zur Verwaltung von Programmen in folgender Hinsicht erweitert. Neben dem Kode des Programms, seines Namens und Speicherort soll eine vollständige Information über seine Verwendbarkeit als Unterprogramm, eine umfassende Dokumentation

seines Anwendungsbereichs, seiner Laufzeit und seines Speicherbedarfs verwaltet werden.

57. Feil, Werner: Der programmierbare endliche Automat mit zwei 1-dimensionalen Programmbändern und der programmierbare endliche Automat mit einem 2-dimensionalen Programmband. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit ist eine Weiterführung der Diplomarbeit von Gerd Kaufholz. Feil zeigt, dass beide Automatentypen in dem Sinn universelle endliche Automaten enthalten, als sie bei festem Programm nur reguläre Mengen akzeptieren und es zu jeder regulären Menge Programme gibt, so dass der Automat genau diese Menge akzeptiert. Im Fall des 2-dimensionalen Bandes genügt dazu ein Automat mit nur 2 Zuständen.

1974

58. Kett, Bernd-Josef: Analyse und Simulation von Schaltwerken. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit entstand im Rahmen des elektronischen Praktikums, das von den Lehrstühlen Eckart(Physik) und Dörr(Angewande Mathematik) gemeinsam getragen wurde. Es geht um eine im physikalischen Sinn treue Simulation des Verhaltens von einfachen Bausteinen und Schaltwerken. Diese Simulationen sollen den experimentellen Aufwand zur Erprobung elektronischer Schaltungen verringern. Hierbei spielen nicht nur die Verdrahtung und die Länge der Leitungen eine olle, sondern auch die Anordnung der Komponenten auf einer Platine. Diese Simulationen sind natürlich immer nur Approximationen. Die verschiedenen Gründe für Schwierigkeiten durch die Simulationen verlässliche Resultate zu erhalten werden in der Arbeit sorgfältig herausgearbeitet, so dass gut sichtbar wird, was das erstellte Simulationsprogramm leisten kann und was nicht.

59. Schwetschke, Thomas: Untersuchungen zur Analyse von Sprachen, die durch (m,0) – Grammatiken erzeugt werden. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die (m,0) – Grammatiken definieren eine Unterklasse der LR(0) – Sprachen. Die Arbeit knüpft an die Diplomarbeit von Rainer Kemp an und verwendet die dort definierten A – minimalen und Z – minimalen Automaten. Es wir ein Algorithmus angegeben zu entscheiden, ob eine LR(0) – Grammatik durch eine (m,0) – Grammatik ersetzt werden kann. Es wird eine dritte Normalform angegeben, die zu Automaten führt, die einen Kompromiss zwischen den beiden oben genannten Typen bilden. Der Z-minimale LR -Automat ist i.a. kein (m,0)-Automat. Der von rechts eingesetzte (m,0) – Automat mag kleiner sein als der von links arbeitende.

60. Sessler, Christoph: Beschreibung einer einfachen Programmiersprache und Skizzierung eines Compilers dieser Sprache unter Verwendung der Theorie der Programmiersprachen von G. Hotz Diplomarbeit am IAM+I der US.

Zusammenfassung: Bei dieser Sprache handelt es sich um Kandzia-Langmaacks simple Algol. Diese Sprache wird exakt definiert auf Basis meines Ansatzes. Es wird für die Sprache ein Compiler angegeben und seine Korrektheit bewiesen.

61. Tomahogh, Dieter: Eine Methode zur Konstruktion overflowfreier Fanodekoder. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um ein Dekodierverfahren aus der Kommunikationstheorie. Die Dekodierung kann exakt erst dann vorgenommen werden, wenn das gesamte zu dekodierende Wort vorliegt. Das führt bei Speicherbeschränkungen zu Problemen, den Overflowproblemen. Tomahogh gibt für die Klasse der betrachteten Kodes ein Dekodierungsverfahren an, das nur zu lokalen Fehlern führt.

1975

62. Hertel, Joachim: Übersetzung von Ableitungsbäumen in linearer Darstellung. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es werden verschiedene Übersetzungskonzepte formaler Sprachen untersucht. Diese Konzepte verallgemeinern die syntax- gerichtete Translation und den zugehörigen Pushdown-Assembler. Eine Verallgemeinerung besteht darin, unterbäume von Syntaxbäumen zu vertauschen und Terminalzeichen „beliebig“ zu ersetzen. Es wird die Idee von Thatcher diskutiert, Ableitungsbäume zu linearisieren, um dann auf diese Linearisierung die oben erwähnten Übersetzungen anzuwenden. Das bedeutet Ableitungsbäume zu löschen, zu vertauschen oder zu vervielfältigen. Hertel beweist, dass diese Konzepte weiterführen als die des Pushdown-Assemblers. Die Arbeit ist algorithmisch orientiert. Eine alternative Beschreibung dieser Konzepte, die kontextfreie Sprachen in kontextfreie Sprachen überführen, besteht in der Konstruktion einer X-Kategorie, die neben den kontextfreien Produktionen als zusätzliche Erzeugende die Diagonalisierung, Vertauschung und Projektion enthält. Die Verbindung zwischen beiden Sprachen wird dann durch einen X-Funktor beschreibbar und verstehbar.

63. Jäger, Helmut: Analyse kontextfreier Sprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit befasst sich mit der syntaktischen Analyse von Sprachen in verschiedenen Unterklassen der kontextfreien Sprachen. Der erste Teil der Arbeit ist eine Ausarbeitung meiner Vorlesung. Der zweite Teil bringt neue Resultate, die die Komplexität der Analyse einer Unterklasse der linearen Sprachen und einer Unterklasse der deterministischen kontextfreien Sprachen betrifft.

64. Commentz, Beate: Platzkomplexität des Äquivalenzproblems endlicher Automaten. Diplomarbeit am IAM+I der US.

Zusammenfassung: In der Arbeit werden die verschiedenen Typen endlicher Automaten, deterministisch, nichtdeterministisch, einwege- und zweiwege- Automaten hinsichtlich der Platzkomplexität ihres Äquivalenzproblems untersucht. Es handelt sich um eine einheitliche, systematische und schöne Bearbeitung dieses Problems. Betreut durch Mehlhorn, der in dieser Zeit den Ruf auf den Lehrstuhl Langmaack erhielt.

65. Fischer, Klaus: Entwurf und Simulation eines Programmierbaren und Mikroprogrammierbaren Kleinrechners. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um eine sehr umfangreiche Diplomarbeit, die von Kaufholz betreut und Kett und Konrad unterstützt wurde. Fischer entwirft einen Rechner, dessen Struktur sehr flexibel ist. Basisoperationen, darunter die arithmetischen können parallel ausgeführt werden. Die Flexibilität beruht auf der Steuerung des Ablaufes durch Mikroprogramme. Der Benutzer hat die Möglichkeit den Rechner durch die Einführung weiterer Befehle, für die er Realisierungen durch Mikroprogramme angibt, an seine persönlichen Bedürfnisse anzupassen. Der Rechnerentwurf wurde durch umfangreiche Simulation auf seine Korrektheit hin getestet.

66. Krebs, Peter: Die Konstruktion eines Computer-Lexikons mit optimalem Zugriffsbaum. Diplomarbeit am IAM der US.

Zusammenfassung: Zu einer geordneten Datenmenge und einer Wahrscheinlichkeitsverteilung über dieser Menge, die die Zugriffshäufigkeit auf die Elemente der Menge beschreibt, soll eine Datenstruktur angegeben werden, die zu optimalen Zugriffszeiten führt. Das gelingt durch die Konstruktion von Zugriffsbäumen unter Rückgriff auf elementare Sätze der Informationstheorie.(Resultate von Kuhn und Tucker und von Knuth werden verwendet). Interessante offene Fragen: Wird durch Sammlung von Anfragen und deren Vorsortierung die Antwortzeit kürzer? Kann man die dynamische Anpassung der Bäume and Veränderungen der Quellen „stetig“ vornehmen?

67. Liebel, Werner: Formale Potenzreihen über Monoidprodukten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Liebel knüpft an eine Arbeit von M. Fliess an, der die von M.P. Schützenberger entwickelte Theorie zur exakten Beschreibung einiger Probleme der Theorie der formalen Sprachen verallgemeinerte. Diese Verallgemeinerung besteht darin, dass anstelle eines endlich erzeugten freien Monoids direkte Produkte von solchen Monoiden zugelassen werden. Liebel definiert akzeptable formale Potenzreihen über diesen Monoiden und beweist einen verallgemeinerten Satz von Jungen – Schützenberger.

Abschuss verschiedener Klassen von Potenzreihen unter dem Hadamarprodukt. Die Arbeit wurde von Kopp betreut.

68. Axel Pink: Diskussion einiger Ergebnisse aus J.E. Savage: Complexity of Decoders: I – Classes of Decoding Rules und Versuch diese auf eine Klasse von Dekodierungsvorschriften für zyklische Kodes zu anzuwenden.

Zusammenfassung: Die Arbeit setzt die Resultate von Savage in Beziehung zu einer Arbeit von C. Shannon über The synthesis of two terminal circuits aus dem Jahr 1949. Die Resultate von Savage werden dazu benutzt die Komplexität von speziellen Funktionen zu vergleichen.

Der zweite Teil der Arbeit beweist auf dieser Basis untere und obere Schranken für die Meggitt – Dekodierer.

1976

69. Günther, Eugen: LR(k)-Algorithmus von R. Kemp für A-minimale Automaten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit schließt an die Diplomarbeit und Dissertation von Kemp an, der diese Arbeit auch betreut hat. Der von Kemp angegebene Analysator mit minimaler Analysezeit (A-minimaler Akzeptor) wird in ein Algolprogramm umgesetzt. Der Schwerpunkt dieser Arbeit liegt in der gut lesbaren Umsetzung dieses von Kemp in knapper Form dargestellten Akzeptors und in einem Korrektheitsbeweis des Algolprogramms.

70. Höh, Fred: Der LR(k) – Algorithmus von R. Kemp für Z – minimale Automaten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit von Höh ergänzt die Arbeit von Günther, indem sie ein Algolprogramm entwickelt, erprobt für die Z – Variante des von Kemp angegebenen Algorithmus zur Konstruktion eines zustandsminimalen LR(k) –Analysators für LR(k) – Sprachen. Die Korrektheit des Algolprogramms wird bewiesen.

71. Estenfeld, Klaus: Ein funktorieller Zusammenhang zwischen einer beliebigen kontextfreien Sprache und der Greibachsprache. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Greibachsprache ist universell in dem Sinn, dass sich jede kontextfreie Sprache als Bild der Greibachsprache unter einem inversen Homomorphismus zwischen freien Monoiden darstellen lässt. Estenfeld zeigt, dass eine Grammatik zu der Greibachsprache gibt, so dass sich die freie X-Kategorie der Ableitungen der vorgegebenen kontextfreien Sprache durch einen X-Funktor in die zur konstruierten Grammatik der Greibachsprache gehörige X-Kategorie abbilden lässt. Es gibt also auch eine in dem erläuterten Sinn universelle Grammatik.

72. Bormann, Gerhild: Klassifizierung von optimalen Algorithmen zum Transponieren quadratischer Matrizen. Diplomarbeit am IAM+I der US:

Zusammenfassung: Motivation: Transformation von Matrizen, die aufgrund ihrer Größe nicht in den Hauptspeicher passen. Die Elementaroperationen bestehen in der Ersetzung von k Zeilen der Matrix durch Zeilen, die durch eine Permutation ihrer Elemente auseinander hervorgehen. Die Arbeit schließt an eine Arbeit von Paul, in der er optimale Algorithmen zur Lösung dieser Aufgabe angegeben hat. Paul hat diese Arbeit auch betreut. Die vorliegende Diplomarbeit stellt dieses Resultat ausführlich dar und realisiert einen solchen Algorithmus durch ein Algolprogramm, das auf dem TR440 lief und getestet wurde.

73. Messerschmidt, Jan: Untersuchungen an Klammersprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Messerschmidt untersucht verschiedene Varianten von Klammersprachen: Dycksprachen und allgemeinere Formen die sich dadurch ergeben, dass Klammern nicht immer sich gegenseitig eindeutig bestimmende Paare ergeben, wie wir das in Programmiersprachen vorfinden. Messerschmidt gibt platzoptimale Algorithmen zur Lösung des Wortproblems an, implementiert diese Algorithmen und beweist die Korrektheit der Programme. Beide Leistungen waren originell.

74. Breder, Michael: Implementierung und Speicherverwaltung dynamischer Zeichenketten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es gab zu dieser Zeit keine höhere Programmiersprache, die dynamisch sich verändernde Zeichenstrings verwalten konnte. Es gab zwei sehr elementare Sprachen ohne Blockstrukturen und ohne Prozeduren, die solch Strings verwalten konnten: COMIT und SNOBOL Die Erweiterungen von Fortran und Algol konnten nur Strings konstanter Länge verwalten. PL/I enthielt Blockstrukturen und Prozeduren, erlaubte aber auch keine dynamischen Strings. Im Rahmen des Sonderforschungsbereichs Elektronische Sprachforschung wurde von meiner Arbeitsgruppe eine universelle Programmiersprache COMSKEE entwickelt mit mehreren für die Textverarbeitung wichtigen Datentypen und Operationen. Hierzu gehörte auch der dynamische Datentyp String über vorgegebenem Alphabet. Dieser Datentyp und die zugehörigen Operationen wie Konkatenation, verschiedene Relationen, Löschen von Teilworten, Inversen usw. wurden von Breder im Rahmen seiner Diplomarbeit wohldefiniert und implementiert und die Korrektheit der Implementation bewiesen.

75. Theobald, Konrad R.: Theorie der Berechenbarkeit von Computerprogrammen auf der Grundlage der Topologie. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit beruht auf einer Idee D. Scotts: Programmiersprachen mit Typen für komplexe Strukturen und ihre Semantik in einfacher Weise auf Basis einer Topologie zu definieren, die von den endlichen Teilmengen der natürlichen Zahlen und einigen Abschlusseigenschaften, wie Konvergenz monotoner Folgen, erzeugt wird. Auf diesem topologischen Raum werden stetige Funktion definiert und Kodierungen dieser Funktionen durch endliche Mengen. Auf dieser Basis werden Operatoren auf Funktionsmengen definiert, Rekursion und Äquivalente zum µ-Operator. Der Vorteil der Konstruktion besteht darin, dass man Hierarchien von Konstruktionen durch eine Konstruktion ersetzt. Die Arbeit selbst war sehr gut, aber der Ansatz baut Sprachen doch zu problemfern, so dass wir den Ansatz nicht weiter verfolgten. Die Arbeit wurde von Herrn Kemp betreut.

76. Schmidt, Bernd: Die mit k linear beschränkten Zählern berechenbaren Funktionen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit wurde angeregt durch Resultate von Hartmanis und Monien. Sie führt diese auch in einem gewissen Umfang weiter. Es wird die Leistungsfähigkeit einer Klasse von Maschinen untersucht, die zum Beispiel. im Zusammenhang mit dem LBA-Problem eine Rolle spielen (Monien). Es handelt sich um endliche Automaten mit einem unären Eingabeband und k Leseköpfen, die wie Hartmanis zeigte gleich mächtig sind, wie log – Platz beschränkte Turingmaschinen. Schmidt zeigt, dass die von ihm untersuchten k-Zählerautomaten, die von der Anwendung her plausibler motiviert sind, ebenso mächtig sind und darüber hinaus, dass man für k=7 bereits die gesamte Funktionsklasse erhält.

77. Schwang, Dietrich: Über die Leistungsfähigkeit eines Dekodierverfahrens für das direkte Produkt zweier linearer Kodes. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es werden zwei Dekodierverfahren verglichen: Das Syndromdekodierverfahren, das alle Fehler in einer Hammingkugel um die Originalnachricht auf diese Abbildet und ein Dekodierverfahren das an dem Produkt von Kodes orientiert ist. Das erstere ist sehr aufwendig, letzteres ist einfacher, aber in seiner Leistungsfähigkeit schwerer abzuschätzen. Schwang vergleicht beide Dekodierverfahren hinsichtlich Kodelänge und der übertragenen mittleren Informationsrate. Die Arbeit wurde von Kopp betreut.

1977

78. Auler, Peter: Eine Benutzerorientierte Datenbank für Bio-Messdaten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um eine Datenbank, die Messreihen aus der Genetik zur Belegung einer weitreichenden Hypothese von Kröger so abspeichern sollte, dass eine effiziente Überprüfung erleichtert werden sollte. Die Datenbank sollte auch an Fragestellungen, die sich durch alternative, auf anderen Grundlagen beruhenden, Messreihen ergeben, flexible anpassbar sein. Zur Verfügung stand dafür nur der Zentralrechner der Universität. Die Lösung bestand in der Konstruktion eines komplexen Suchgraphen, der die bestehenden Anforderungen bestens erfüllte, wie die folgenden Jahre der Anwendung zeigten.

79. Grau, Konrad: Simulation eines Algorithmus zur Analyse kontextfreier Sprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um ein Programm, das einen von mir angegebenen Analysealgorithmus umsetzt. Es werden zu jedem gelesenen Zeichen Teilgrammatiken berechnet, die in dynamische Arrays, deren Komponenten endliche Automaten sind, umgesetzt werden Der Test des implementierten Verfahrens ergibt als mittlere Laufzeit O(n^3)..

80. Rott, Wolfram: Speicherstrukturen in Datenbanken. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit gibt zunächst eine umfangreiche Literaturübersicht effiziente Datenstrukturen zur Verwaltung von Datenbanken bei gedächtnislosen Anfragequellen. Stärker in Einzelheiten gehend wird der Fall von Quellen mit ausgewogenen Verteilungen behandelt. Im letzten Abschnitt werden grammatikbasierte Strukturen hinsichtlich einer Anwendung in der Sprachverarbeitung behandelt.

81. Huynh, Thiet-Dung: Funktorieller Zusammenhang zwischen formalen Sprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es wird gezeigt, dass verschiedene Ansätze zur syntaxorientierten Übersetzungen formaler Sprachen äquivalent sind. Hierzu gehört die Äquivalenz von simple Syntax oriented Transductions und Übersetzungen, die durch X-Funktoren, d.h. monoidale Funktoren zwischen Ableitungskategorien definiert werden und die Äquivalenz zwischenallgemeinen an der Syntax orientierten Transductions und funktoriellen Übersetzungen, die hinsichtlich der Monoidverknüpfung keine Homorphismen sind, sondern gewissen eingeschränkten Permutationsregeln unterworfen sind.

1978

82. Schmitz, Klaus-Dirk: Ein benutzerorientiertes Datenbanksystem nach dem Relationenmodell zur Aufnahme pathologischer Befunddaten. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit gehört zu dem Projekt, aus dem auch die Arbeit von Eulenstein 83. hervorgegangen ist, und sie wurde von Helmut Jäger 63. betreut, der nach Homburg in die Medizin übergewechselt war.

Die Schwierigkeiten eine effiziente und auch relevante Datenbank für medizinische Zwecke zu erstellen liegt in der gar nicht eindeutigen Nomenklatur und Interpretation der Erscheinungsbilder der Patienten begründet. Wenn eine Datenbank überhaupt nützlich sein soll, dann müssen die Patientendaten zeitlich und möglichst Objektiv eindeutig repräsentiert werden. Die Datei muss fortgeschrieben werden können und Möglichkeit zu Querverweisen bieten. Basis beider Arbeiten war eine Sprache SNOP, die vier Kategorien (Listen von Bezeichnungen, die z.B. Namen betroffener Körperteile oder Strukturveränderungen) enthält, die in den USA entwickelt wurde. Schmitz entwirft und implementiert die zugehörige Datenbanksprache. Die Arbeit entstand in Kooperation mit dem Kollege n Kopetzky von dem pathologischen Institut der US

83. Eulenstein, Michael: Die Entwicklung eines Verfahrens zur Aufnahme pathologischer Diagnosen in eine Benutzerorientierte Datenbank. Diplomarbeit am IAM+I, der US.

Zusammenfassung: In diesem Teil, des bereits unter 82. behandelten Projekts wird die Übersetzung der Patientendaten in die Datenbanksprache vorgenommen. Beide Arbeiten entstanden in enger Kooperation. Die Aufteilung erfolgte unter dem Gesichtspunkt, dass zwei verschiedene Diplomarbeiten vorliegen müssen.

84. Schmauch, Cosima: Übersetzung von Normaltransformationen mithilfe von Push-Down-Transduktoren. Diplomarbeit am IAM+I der US.

Zusammenfassung: Normalformen machen Grammatiken übersichtlicher und sie gestatten es auch die Ableitungen, d.h. die grammatikalische Struktur von Wörtern einfacher darzustellen. Die Möglichkeit verschiedener Normalformen wirft natürlich die Frage auf, in wie weit diese Strukturen von den verschiedenen Normalformen abhängen; lässt sich zum Beispiel die Multiplizität der Interpretationen bei Normalformentransformationen erhalten. Diesem Fragenkreis ist diese Diplomarbeit und die folgende von Ruth Messerig zuzuordnen. In dieser Arbeit werden Push-Down-Transducer angegeben, die für drei verschiedene, von mir eingeführte Normformen, die Ableitungen bezüglich der verschiedenen Normalformen ineinander übersetzen. Die Arbeit wurde von Rockford J. Ross betreut.

85. Messerig, Ruth: Die Invarianz der LL(k)-Eigenschaft unter einigen Normalformtrans-formationen. Diplomarbeit an der US.

Zusammenfassung: Die Motivation ist die gleiche wie für die Arbeit von Ruth Messerig. Hier gilt das Interesse aber nicht der Klasse aller kontextfreien Sprachen, sondern nur den LL(k)-Sprachen, also einer Unterklasse der LR(k)-Sprachen. Es werden die Auswirkungen der drei sch oben erwähnten Normalformentransformationen daraufhin untersucht, ob sie die LL(k)-Eigenschaft erhalten. Resultate: Die Transformation tau1 erhält die LL(k)-Eigenschaft, sie mag aber das k verkleinern und sie vermag auch nicht LL(k)-Grammatiken in solche überzuführen. Die beiden anderen Transformationen erhalten zwar die Eindeutigkeit überführen aber nicht immer eine LL(k)-Grammatik in eine LL(k’)-Grammatik. Die Arbeit wurde von Rockford J. Ross betreut.

86. Kunz, Adolf: Schleifenoptimierung durch Intervalle. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit entstand im Zusammenhang mit der Entwicklung der im Rahmen des SFB 100 entwickelten Programmiersprache Comskee und eines zugehörigen Compilers. Das Besondere an dieser Sprachen waren die Datentypen, die für diesen Anwendungsbereich erwünscht waren. In dieser Diplomarbeit wurde zu den Programmen der Flussgraph konstruiert, und es wurden auf Basis der Analyse dieses Graphs gewisse Programmtransformationen vorgenommen, die die Laufzeit reduzierten. Die Arbeit wurde von E. Bertsch betreut.

87. Becker, Hans-Jürgen: Optimierung von symbolischen Maschinenprogrammen. Diplomarbeit am FAM+I(=Fachbereich für Angewandte Mathematik und Informatik) der US.

Zusammenfassung: Diese Arbeit gehört ebenfalls in das Umfeld der Compilerkonstruktion für die im SFB 100 entwickelte linguistisch orientierte Programmiersprache Comskee. Der Flussgraph wurde konstruiert und hinsichtlich seiner Zerlegbarkeit in einfache Komponenten analysiert. Diese Komponenten wurden hinsichtlich ihrer Zerlegbarkeit in gemeinsame Segmente zwecks Einsparung von Speicherplatz und Laufzeit analysiert. Kurz, die Analyse erfolgte nach allen Regeln der Kunst und wird in Kode umgesetzt. Auch diese Arbeit wurde von E. Bertsch betreut und trug wie 86. wesentlich zum Compiler für die erste Comskee-Version bei.

88. Simon, Hans-Ulrich: Wortprobleme bei Gruppen und kontextfreie Analyse. Diplomarbeit am IAM der US.

Kurzfassung: Es geht um die Frage des Speicherbedarfs, der zur Lösung des Wortproblems von freien Gruppen, einem einfachen Sonderfall des Wortproblems kontextfreier Sprachen erforderlich ist und auch hinreicht. Der Gruppenring freier Gruppen ist eng verwandt mit der universellen kontextfreien Sprache von S. Greibach. Aus diesem Grund ist eine nähere Untersuchung dieser Frage interessant.

Lipton hat in einer knapp geschriebenen Arbeit gezeigt, dass man asymptotisch mit einem Speicher der Größe log(n) auskommt. Simon verbessert die Laufzeit des Verfahrens von Lipton wesentlich, so dass die Produktkomplexität (time*space) seines Verfahrens nahezu optimal ist.

1979.

89. Halász, Vera M. : Der Zusammenhang zwischen der kontextfreien Analyse und der Multiplikation in Polynom- bzw. Matrizenringen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Man kann die Greibachsprache in Zusammenhang bringen mit der Matrixmultiplikation, erhält daraus aber keine interessante untere Schranke. In dieser Arbeit sollte versucht werden einen Zusammenhang mit der Auswertung von Polynomen oder Systemen von Polynomen herzustellen, um die in diesem Zusammenhang gewonnen unteren Schranken zu nutzen um untere Schranken für das Analyseproblem von formalen Sprachen zu gewinnen. Der Versuch war nicht wirklich erfolgreich.

1980 und 1981

90. Karst, Michael: Implementierung einer Normalformtransformation Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit steht im Zusammenhang mit den Arbeiten von Cosima Schmauch und Ruth Messerig. Die Transformationen von kontextfreien Grammatiken in Greibachnormalform oder verwandte Normalformen können zu wesentlich größeren Grammatiken führen. In dieser Arbeit wird eine, nämlich tau1, implementiert und anhand von Beispielen diskutiert. Karst hat ein Beispiel angegeben, das eine Grammatik aus 10 Produktionen aufbläht zu einer Grammatik aus 2500 Produktionen. Er hat klar herausgearbeitet, welche Konfigurationen zu diesen Explosionen führen und wie sie durch eine Vorbehandlung der Grammatik vermieden werden können.

91. Hoffmann, Luitwin: Schnelle Matrizenmultiplikation. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die existierenden Algorithmen für eine schnelle Matrixmultiplikationen sind nicht für jede Größe der Matrizen schneller. Für welche Größe sie schneller werden hängt auch von der Struktur des Rechners und der verwendeten Programmiersprache ab. Hoffmann hat in seiner Arbeit Compiler für Fortran und TAS auf der TR440 zur Untersuchung dieser Frage verwendet. Die Laufzeitgewinne, die seine Implementierungen für die Strassenmethode erzielten, setzten bei Fortran im Falle quadratischer Matrizen bei n=90, im Falle des Tasprogramms ab n=52. Für n=256 betrug der Laufzeitgewinn in betrachteten Beispielen 22% . Der zusätzlich benötigte Speicherplatz hielt sich in akzeptablen Grenzen.

92. Ries, Manfred: Implementierung und Speicherverwaltung des COMSKEE-Datentyps SET. Diplomarbeit am IAM+I der US.

Zusammenfassung: COMSKEE ist eine Programmiersprache die zur Bearbeitung von Problemen der Sprachanalyse und der Übersetzung von natürlichen Sprachen entwickelt wurde. Es handelt sich um eine universelle, blockstrukturierte Programmiersprache mit dynamischen Datentypen wie string und set. Der Compiler übersetzt in eine eigens auf das Ziel der Kodeerzeugung ausgerichtete Zwischensprache CIL (Comskee Intermediate Language). Die Übersetzung in den Montagekode war Thema der Diplomarbeit von J. Messerschmidt. Ries hat alle Laufzeitprogramme außer dem Datentyp string implementiert.

Es handelte sich um

• Ein- und Ausgabe von Daten des Typs number, bit, set,
• Konvertierung zwischen Datentypen string nach number, string nach bit, bit nach string,..
• Verwaltungs- und Dienstleistungsaufgaben
• Implementierung und Verwaltung dynamischer Mengen

Die Diplomarbeit beschränkt sich auf die Behandlung der Laufzeitprogramme für die Implementierung des Datentyps set. Zentral ist die Verwaltung der Mengen durch die Anlage von Bäumen. Die Elemente der Mengen sind nicht einzeln adressierbar, aber es gibt eine Schleife foreach die es erlaubt bei jedem Schleifendurchlauf ein bisher noch nicht betrachtetes Element aufzurufen. Als Operationen sind die in der Mengenlehre üblichen zugelassen.

93. Schütz, Jörg: Der Datentyp Baum. Diplomarbeit am IAM+I der US.

Zusammenfassung: Auch diese Diplomarbeit diente dem Forschungsprogramm des SFB 100. Für die automatische Sprachanalyse und Übersetzung spielt der Syntaxbaum von Sätzen eine große Rolle, sodass die Programmiersprache Comskee auch mit einem dynamischen Datentyp baum versehen wurde. Da die Syntax eines Satzes im Allgemeinen mehrdeutig ist oder doch während seiner Bestimmung mehrere Versionen zulässt, sollte auch ein Datentyp netz vorgesehen werden, der es gestattet, die angedeuteten Analyseprobleme durch die Überlagerung von Bäumen zu erfassen. Hierzu genügt benötigt man Bäume der Kanten Typenbezeichnungen und deren Knoten Operations oder Relationsbezeichnungen tragen. Auf diese Erweiterung musste die Spezifikation des Datentyps baum Rücksicht nehmen. Als Elementaroperationen sollten die Operationen in freien D-Kategorien vorgesehenen werden und Operationen die sich im Rahmen von Analysen von Beispielen als notwendig oder nützlich erweisen würden. Schütz hat in seiner Diplomarbeit wesentliche Teile dieser Aufgabe erledigt. Die Arbeit wurde von Klaus Estenfeld betreut.

94. Kolber, Nico: Ein Programmsystem zur formalen Manipulation von Grammatiken. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit beruht auf der von mir eingeführten Gruppeninvariante für kontextfreie, reduzierte Grammatiken, die die gleiche Sprache definieren. Eine Rolle spielen dabei auch die in diesem Zusammenhang betrachteten verschränkten Homomorphismen. Da das Wortproblem für die hier in Frage kommenden Gruppendarstellungen nicht entscheidbar sind, sollte in dieser Arbeit die von Fox eingeführten Invarianten für Gruppendarstellungen ins Spiel gebracht werden. Kolber überträgt die elementaren Ideale der Alexandermatrizen auf kontextfreie Grammatiken. Da diese Invarianten nicht leicht zu berechnen sind, wurde im Rahmen der Diplomarbeit ein Programm geschrieben, das dieses tut.

95. Speicher, Roland: Lokale Fehlererkennung und –Verbesserung. Diplomarbeit am IAM+I der US.

Zusammenfassung: Programmierungsfehler, die auf leichten Versehen oder Vergessen beruhen, sollen automatisch korrigiert oder dem Programmierer als Frage vorgelegt werden. Die Basis hierzu bildet die Spezifikation der Programmiersprachen durch LR(k)- oder LL(k)-Programmen. Lokal bedeutet eine Einschränkung auf Teilfolgen des Programms, die aus vier aufeinander folgenden unzerlegbaren Wörtern bestehen. Genauer: Die Korrektheit von xi wird beurteilt relativ zu der Möglichkeit der Sequenz x(i-2),x(i-1),xi,x(i+1) als Teilsequenz eines korrekten Programms zu erscheinen. Es werden in der Arbeit eine ganze Reihe von Fehlertypen angegeben, die sich durch diesen Ansatz abdecken lassen. Auch diese Arbeit entstand im Rahmen des Comskee-Projektes.

1982

96. Fissgus, Ursula: Darstellungssätze für Chomsky-0 und Chomsky-1 Sprachen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um den Versuch die eleganten auf Monoidhomomorphismen und Transductoren beruhenden Darstellungssätze von Schützenberger und Shamir für reguläre und kontextfreie Sprachen auf die oben genannten Klassen zu übertragen. Der Ansatz ist ähnlich dem von Goldstine aber unabhängig davon entstanden. Formal gründet sich die Arbeit auf den Darstellungen in dem Buch von Hotz, Estenfeld: Formale Sprachen. Hierin spielen Homomorphismen von freien in polyzyklische Monoide (syntaktische Monoide der Klammersprachen) eine entscheidende Rolle. In die Konstruktion der Darstellungen der hier behandelten Sprachklassen gehen schließlich auch Ergebnisse von Book, Nivat, Paterson und A.K. Salomaa mit ein.

97. Leibfried, Rolf: Schnelle Multiplikation großer Zahlen nach Schönhage und Strassen. Diplomarbeit in AM der US.

Zusammenfassung: Es handelt sich um eine ausführliche Darstellung des Algorithmus und seine Implementierung für sehr große Zahlen. Die Korrektheit des Programms wird bewiesen.

98. Kolla, Reiner: Untere Schranken für VLSI. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Komplexitätsmaße für die Realisierung von Schaltkreisen auf Chips sind vielfältig: Man kann die Anzahl der Gatter zählen, die die Realisierung eines Schaltnetzes erfordert, das eine vorgegebene boolesche Funktion mit n Eingängen und m Ausgängen mindestens erfordert, das Maß kann man auch auf die Fläche beziehen, die die Realisierung eines booleschen Netzes erfordert oder man kann auch die maximale Signallaufzeit ins Spiel bringen verbunden mit Möglichkeiten die Korrektheit des produzierten Chips effizient zu testen. Für die Realisierung spielen noch weitere Parameter eine Rolle. Kolla diskutiert verschiedene in der Literatur (Lipton, Sedgewick, Abelson, Brent, Kung, Thompson, Vuillemin, Savage, Preparata, Chazelle, Monier) betrachtete Komplexitätsmaße kritisch, um die Anzahl der Optimierungsparameter zu verringern. Es gelingt Kolla bekannte Komplexitätsabschätzungen zu verallgemeinern. Die Basis bilden Informationstheoretische Aspekte. Schließlich wendet er den allgemeinen Ansatz auf einige Beispiele an: eine Klasse von Gleichheitstests, das Pattern Matching, Faktorverifikation, Berechnung der Determinante einer binären Matrix. Für alle diese Beispiele erhält er nicht triviale neue untere Schranken.

99. Molitor, Paul: Kolmogorov - Komplexität. Diplomarbeit am IAM+I der US.

Zusammenfassung: Anlass für diese Arbeit war Ein Satz von Wolfgang Paul, der die Nichtexistenz von Simulationen gewisser Realzeit-Turing-Maschinen auf anderen Maschinen dieser Klasse zum Inhalt hatte. Die Arbeit baute auf dem Konzept der Programm-Komplexität auf, wie sie von Kolmogorov zur Fassung des Begriffs der zufälligen Folgen verwendet worden war. Vorlage war eine noch nicht ganz vollständige oder skizzenhafte Version des Beweises. Molitor zeigte: Turingmaschinen mit t-dimensionalen Bändern (t>2) und k Leseköpfen je Band lassen sich in Realzeit nicht auf einer Turingmaschine mit einem Band und k-mal so vielen Köpfen simulieren. Der Satz von Paul folgt aus diesem Resultat.

1983

100. Groh, Ursula: Optimale Einbettungen von Graphen mit festem Rand. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit knüpft an Hotz, Becker: On the optimal layout of planar graphs with fixed boundary an. Es werden Einbettungen von planaren Graphen berechnet, die die Summe der in einer Norm gemessenen Kanten minimieren. Ist der Graph dreifach zusammenhängend und der Rand konvex, dann ist dieses Layout für eindeutig bestimmt. Ist der Graph planar, dann zerlegt der Rand den Graphen in zwei planare Komponenten. Die Berechnung der optimalen für den Fall p=2 kann durch lokale Optimierung (man schiebt jeden Punkt in den Schwerpunkt seiner Nachbarn) approximiert werden. Im allgemeinen Fall kann man die optimale Einbettung durch das Gradientenverfahren (es konvergiert) approximieren. Falls ein Graph mit vorgegebenem konvexen Rand überhaupt ins Innere planar eingebettet werden kann, dann ist das Resultat der optimierung eine planare Einbettung. Der Beweis wird auf den Monodromiesatz reduziert. Die Arbeit wurde von Bernd Becker mitbetreut, und diese Betreuung konvergierte schließlich in der Ehe.

101. Eisel, Helmut: Über die optimale Einbettung von Bäumen bezüglich der

Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit t geht aus von: Fischer, Paterson: Optimal Tree Layout aus dem Jahr 1980. Es handelt sich um das folgende Problem: Es ist ein Graph gegeben, dessen Kanten s durch positive reelle Zahlen g(s) gewichtet sind. Es ist für eine Teilmenge der Knoten des Graphen eine Einbettung in einen k-dimensionalen reellen Raum vorgegeben. Gesucht ist eine vollständige Einbettung des Graphen in den Raum (ein Layout), so dass das Layout optimal ist hinsichtlich einer Kostenfunktion, die sich als Summe der Kosten der Kanten ergibt. Hierbei sind die Kosten K(µ(s)) einer Kante s gegeben durch das Produkt |µ(s)|*G(s); |µ(s)| ist die in einer Norm gemessene Länge der Kante µ(s). Die in der vorliegenden vorläufigen Version knappen Beweise für die Lösung des Optimierungsproblems in Zeit O(n*logn) für den Fall der Bäume werden detailliert ausgeführt für den Fall der . Die Arbeit wurde von Bern Becker betreut. Der Verfasser hat später die Informatik aufgegeben und ist berühmt als Virtuose und Leader seiner Klesmaband.

102. Harbusch, Katrin: Die syntaktische Mehrdeutigkeit der deutschen Sprache. Diplomarbeit am IAM+I der US.

Zusammenfassung: Zunächst beschreibt die Arbeit einen Analysealgorithmus für kontextfreie Sprachen, der als Resultat einer Analyse alle wesentlich verschiedene Analysebäume in einer kompakten Notation erzeugt. Der Analysator wurde in der Programmiersprache Comskee geschrieben. Das Programm wurde unter Verwendung einer (nicht vollständigen) Grammatik der deutschen Sprache angewendet zur Analyse der syntaktischen Mehrdeutigkeiten in dem Abkommenstext (/TX/) der Europäischen Gemeinschaft. Es war erstaunlich wie viele Mehrdeutigkeiten entdeckt wurden, die dem „semantisch“ denkenden Menschen nicht auffielen.

Diese Arbeitsrichtung hat Karin Harbusch auf einer Stelle von W. Wahlster weiterverfolgt.

103. Kuske Harald: Praktische Erfahrungen bei der Entwicklung eines BOOTSTRAP – COMPILERS für die Programmiersprache Comskee. Diplomarbeit am IAM+I der US.

Zusammenfassung: Kuske hat einen BOOTSTRAP - Compiler für Comskee entwickelt. Es sollte ein Compiler geschrieben werden, der es leicht machte Comskee auf andere Rechner zu portieren. Der bestehende Compiler gliederte sich in die drei Pässe: Pass 1 Lexikalische Analyse, Erkennung von Identifiern, Aussieben von Leersymbolen. Pass 2: Syntaktische Analyse, Generierung eines maschinenunabhängigen Zwischencodes CIL. Pass 3: Übersetzung des von Pass 2 gelieferten Zwischencodes in den Code der realen Maschine. Erhält der von Kuske erstellte Compiler sich selbst als Eingabe, dann erzeugt er einen Zwischencode aus CIL, der dann auf einen anderen Rechner migriert wird. Die Arbeit beschreibt diese Prozesse detailliert, berichtet über Schwierigkeiten, die überwunden wurden und über bisher übersehene Fehler im vorhandenen Compiler. Die Arbeit wurde von Jan Messerschmidt betreut.

104. Lambert, Hans: Formales Differenzieren – Ein Programmsystem zur formalen Differentiation von Ausdrücken der Programmiersprache BASIC. Staatsexamensarbeit für das Lehramt an Gymnasien.

Zusammenfassung: Im Rahmen der Arbeit wurde ein Programm erstellt, das Ausdrücke über den arithmetischen Operationen, den trigonometrischen Funktionen und der Exponentialfunktion formal differenziert und darüber hinaus für vorgegebene Werte auch auszuwerten gestattet. Die erzielten Ausdrücke sind bereinigt; d.h. sie werden nach der formalen Differentiation vereinfacht: Sie enthalten keine überflüssigen Konstanten. Die Arbeit wurde von Herrn Arz betreut.

105. Pink, Editha: Attributierung von Netzen, die Synaxdiagramme von kontextfreien Grammatiken überlagern. Diplomarbeit am IAM+I der US.

Zusammenfassung: Syntaxdiagramme sind leichter i.a. leichter verständlich als die zugehörige Grammatik. Die Ableitungsbäume über Grammatiken werden eindeutig durch Wege in den Syntaxgraphen repräsentiert, die unsere Konstruktion den Grammatiken zuordnet. Alle diese zu einem Wort gehörigen Wege lassen sich durch ein Netz repräsentieren, dessen Breite durch die Anzahl der Knoten des Syntaxgraphen beschränkt ist und dessen Länge gleich der Länge des Wortes ist. In der Arbeit wird die Frage behandelt, ob die von Knuth eingeführte Attributierung sich in natürlicher Weise auf die Syntaxdiagramme übertragen lässt. Frau Pink zeigt, unter welchen Voraussetzungen das möglich ist, und wie sich die Attributierung durch die Konstruktion eines Überlagerungsnetzes auswerten lässt. Frau Pink zeigt, dass die von links nach rechts sequentiell auswertbaren Attributierungen Verallgemeinerungen der für den Fall der LL(k)-Sprachen bekannten von links nach rechts auswertbaren Attributierungen sind.

Weiter charakterisiert Frau Pink die Klasse der c.f. Sprachen, für die das Problem durch k sequentielle Kellerautomaten analysiert werden kann, wenn k die Breite des Graphs ist. Darüber hinaus gibt sie ein Programm an, das es erlaubt die Konstruktionen effizient umzusetzen.

106. Reding, Helene: Kompositazerlegung. Diplomarbeit am IAM+I der US.

Zusammenfassung: Frau Reding behandelt zunächst das abstrakte Problem, zu einem gegebenen Wortschatz W und einem vorgegebenen Wort w zu entscheiden, ob w in dem von W erzeugten Monoid hinsichtlich der Konkatenation liegt. Im positiven Fall sind alle möglichen Zerlegungen von w über W anzugeben.

Das praktische Problem der Kompositazerlegung der deutschen Sprache ist wesentlich komplizierter, da dabei z.B. auch Einfügungen von Fugenzeichen und die Behandlung von Endungen bei der Komposition mit betrachtet werden müssen. Frau Reding hat viele solcher Fälle, die bei der Zerlegung eine Rolle spielen, zusammengetragen und ein Programm geschrieben das die zugehörigen Kompositazerlegungen berechnet. Das Programm wurde an Texten der EG – Behörde getestet.

107. Sparmann, Lutz: Overrun-Probleme bei Kanalprozessoren. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit entstand in Zusammenarbeit mit Dr. Gerd Kaufholz IBM Deutschland – Entwicklung und Forschung. Bei der Benutzung des gleichen Kanals zur Kommunikation zwischen verschiedenen Komponenten eines Computers können Staus auftreten, die dadurch, dass vorgesehene Warteräume überfüllt werden zu Datenverlusten führen. Sparmann hat ein Simulationssystem entworfen, das die Kapazitäten der in diesem Zusammenhang erstellten Organisationen testet.

1984

108. Osthof, Georg: Der Minimale Kreis um eine endliche Punktmenge. Diplomarbeit am IAM+I der US.

Zusammenfassung: Osthof gibt einen Algorithmus an, der zu k Punkten in der Ebene einen minimalen Umkreis berechnet. Es gab eine Lösung des Problems, in dem der Sonderfall, dass dieser Kreis nur durch zwei Punkte der Menge geht, übersehen wurde. Eine Arbeit, die diesen Sonderfall behandelte, war ungenau, was die Laufzeitabschätzung der Konstruktion anging.

Osthof gibt eine saubere und sehr gut lesbare Lösung dieses Problems durch einen Algorithmus mit einer Laufzeit O(k*log k)

109. Niedner, Michael: Ein paralleles Kommunikationsschema für das Rechnernetz eines n-dimensionalen Würfels. Diplomarbeit am IAM+I der US

Zusammenfassung: Die Arbeit beruht auf einer Arbeit von L.G. Valiant: A Scheeme for fast parallel communication Es handelt sich um einen probabilistischen Routingalgorithmus für den Austausch von Nachrichten zwischen Knoten des n-dimensionalen Würfels. Diese Arbeit definiert ein schönes Kommunikationsschema, das für große n den Austausch im Mittel in O(n) Schritten bewältigt. ( in einer Zeiteinheit darf nur ein Paket über eine Kante gehen). Die Fälle 1 bis 10 werden durch eine Simulation überprüft und bestätigen das asymptotische Resultat für diesen endlichen Fall. Niedner stellt die Arbeit ausführlich dar und bestätigt die von Valiant für den endlichen Fall mitgeteilten Resultate bis auf 2 Stellen hinter dem Komma.

Die Arbeit wurde von Ulrich Simon betreut.

110. Lohmann, Dietrich: Array-Konstruktionen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Ziel der Arbeit war es einen Compiler für eine von Messerschmidt/Wilhelm vorgeschlagene Datenstruktur für Comskee zu implementieren. Die Arbeit umfasste auch die Darstellung der Syntax und Semantik im Programm zur Festlegung der Datenstruktur. Lohmann erzeugt einen optimierten 3-Adress-Code. Verschiedene Phasen des Übersetzungsprozesses werden an Beispielen illustriert. Für seine Programme gibt Lohmann auch Korrektheitsbeweise an (nicht Verifikationen auf Basis einer formalen Spezifikation). Die Arbeit wurde durch Jan Messerschmidt betreut.

111. Weiler, Ulrike: Relationen auf regulären Mengen Diplomarbeit am IAM+I der US.

Zusammenfassung: Frau Weiler stellt zunächst bekannte Resultate dar, die reguläre Sprachen, ihre syntaktischen Monoide und die zugehörigen Minimalautomaten miteinander verbinden. Sodann verallgemeinert sie diese Resultate auf die von mir eingeführten k-dimensionalen syntaktischen Monoide. Weiterhin betrachtet sie die Konvergenz von Minimalautomaten für ein Anfangsstück regulärer Sprache gegen den Minimalautomaten der vorgegebenen regulären Sprache. Man erhält das k-dimensionale syntaktische Monoid einer Sprache , indem man für und definiert

und .

Diese Kongruenz enthält zwar nicht mehr Information über L als im Falle k=1, gestattet es aber ein Maß für die Nichtkommutativität des syntaktischen Monoids im Fall k=1 anzugeben. (Das direkte Produkt lässt sich auf verschiedene Weisen definieren) Freu Weiler zeigt, dass sich das k-dim. Syntaktische Monoid in Schritten aus dem 1-dimensionalen konstruieren lässt. Die Arbeit wurde von Ulrich Simon betreut.

112. Schmitt, Franz-Josef: Rechtwinklige Verdrahtung optimaler Layouts. Diplomarbeit am IAM+I der US.

Zusammenfassung: Herr Schmitt entwickelt ein Programm zur Berechnung des optimalen rechtwinkligen Layouts von Chips bei vorgegebener Lage der Knoten des Graphs. Die Realisierung erfolge mittels der Programmiersprache Comskee. Die Erprobung des Programms lieferte befriedigende Resultate.

113. Scheuermann, Rita: Ein Algorithmus zur Lösung des maximalen Flussproblems. Diplomarbeit am IAM der US.

Zusammenfassung: V ist die Menge der Knoten, E die Menge der Kanten des Flussgraphs. Der Arbeit liegt der originelle und komplizierte Algorithmus von Z. Galil und A. Naamad zugrunde. Knappe Beweise werden ausgearbeitet und fehlende ergänzt. Der Algorithmus wird implementiert und die Korrektheit bewiesen. Die Arbeit wurde von Ulrich Simon intensiv betreut.

114. Pfeiffer, Susanne: Der Datentyp Sentence. Diplomarbeit am IAM+I der US.

Zusammenfassung: Frau Auler geb. Pfeiffer erweiterte die Programmiersprache Comskee durch einen Datentyp, der Strings mit Leerzeichen und Zeilenwechsel, wie sie für Sätze typisch sind, durch ein Relationensystem beschreibt (Hierzu sehe man meine Einführung in die Informatik). Es treten dabei konzeptionelle Schwierigkeiten auf, die die Behandlung von Sonderzeichen betreffen. ZU dieser Datenstruktur gehören Operationen die diesen Datentyp mit anderen Datentypen verbinden. Dabei muss man z.B. die Konkatenation von Worten zu Worten unterscheiden von der zu Sätzen. Die Arbeit wurde von Jan Messerschmidt betreut.

115. Neufing, Wolfgang: Programmassoziierte Netze. Diplomarbeit am IAM+I der US.

Zusammenfassung: In dieser Diplomarbeit greifen wir wieder das schon in der Diplomarbeit von Helmut Alt behandelte Thema auf: Man erkenne die Teile eines Programms, die parallel zueinander ausgewertet werden können. Hier wurde in die Diskussion mit eingebracht, welche Möglichkeiten zur parallelen Ausführung von Operationen die vorliegende Hardware bietet, in deren Kode das Programm übersetzt werden soll. Die zugrunde liegende Programmiersprache ist speziell gewählt. Die rechten Seiten der Wertzuweisungen sind in polnischer Notation geschrieben, es sind kellerartige Speicher vorhanden. Neufang berechnet den Flussgraph des Programms und eine Zerlegung in Basisblöcke. Dazu werden Schaltkreise als Ausdrücke in X-Kategorien konstruiert. Das Ziel unabhängige Programmteile zu identifizieren wird allerdings nur für die Basisblöcke erreicht. Die zur Konstruktion der Graphen verwendete Sprache ist Comskee, das es in einfacher Weise erlaubt Netze zu verknüpfen. Die Arbeit wurde von Ulrich Simon betreut.

116. Hemmen, Manfred: Ein Scheduling-Problem auf gerichteten, azyklischen Graphen mit Baumstruktur. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es werden Programmablaufpläne für Mehrprozessorsysteme im Falle einheitlicher Ausführungsdauer mit Nachfolgerrestriktionen konstruiert. Im allgemeinen Fall ist das Problem NP-vollständig. Hier werden deshalb nur die Fälle betrachtet, in denen die Nachfolgerrestriktion einen Baum erzeugt. Hierfür gab es eine Lösung von T.C.Hu seit 1961. Hemmen folgt diesem Ansatz, geht aber bei dem Beweis der Optimalität der Konstruktionen eigene Wege. Den Algorithmus hat er in Pascal implementiert. Betreut wurde die Arbeit von Ulrich Simon.

117. Barth, Klaus: Layout und Verdrahtung von Zwei-Terminal-Netzen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit behandelt das Layoutproblem auf einem Rechteckgitter mit Anschlüssen auf sich gegenüber liegenden Seiten eins Rechtecks. Das Gitter steht in einer k-fachen Überlagerung zur Verfügung. Die Lösung verwendet einen Algorithmus von Preparata und Lipski. Die Längen der Pfade sind nicht minimal und nicht balanciert. Barth gibt eine Lösung an, die längere Pfade auf Kosten kürzerer verkürzt. Bezahlen muss er diese Optimierung durch eine Erhöhung der Anzahl der Ebenenwechsel. Die Arbeit wurde von Bernd Becker betreut.

1985

118. Marzinkewitsch, Reiner: Iterative Monoide. Diplomarbeit am IAM+I der US.

Zusammenfassung: Wir betrachten hier wieder die k-dimensionalen Monoide wie in der Diplomarbeit 110 von Ulrike Weiler. Die verschiedenen Möglichkeiten das k-fache direkte Produkt zu definieren beschreiben wir durch ein binäres k-Tupel s und das zugehörige Monoid mit M(s). Allerdings sind hier die syntaktischen Monoide von kontextfreien Sprachen und gewisse ihrer Untermonoide N, die eine Maximalitätsbedingung erfüllen, Gegenstand der Untersuchung. Zwischen diesen Monoiden wird eine Verallgemeinerung der Konjugiertheit von Untergruppen definiert. Die so definierten klassen von Untermonoiden repräsentieren „Muster“, die in formalen Sprachen auftreten können und sind so geeignet Verwandtschaften formaler Sprachen auszudrücken, die sich eventuell in Grammatiken umsetzen lassen. Verfeinerungen der Theorie, auf die ich in der Zusammenfassung nicht eingehen kann, führen bei kontextfreien Sprachen zu Invarianten gegenüber den sprachenerhaltenden Grammatiktransformationen. Reiner Marzinkewitsch widerlegt die Vermutung, dass im Falle kontextfreier Sprachen der Index der Konjugationsklassen endlich ist. Die Sprachklasse, für die das zwar gilt, ist aber echt größer als die Klasse der regulären Mengen. In die Arbeit gingen auch Diskussionen mit Luc Boasson ein.

119. Mense, Dietmar: Über die Komplexität von Permutationen – Die Entropie bei konstanter und variabler Blocklänge – Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit knüpft an Arbeiten von H.-J. Stoß, W.J. Paul, T. Klinger und S. Reisch und eigene Arbeiten an. Stoß verwendete ein Maß für die Unordnung, die eine Permutation der Zeichen eines Wortes schafft, die sich als Entropie interpretieren ließ. Darauf bauen alle die zitierten Arbeiten auf. Diese Entropie konnte Stoß unter einer scharfen Einschränkung an die für eine Turingmaschine zulässigen Programme als Untere Schranke für diese Programmlängen nachweisen. W.J. Paul hat mit einer Verallgemeinerung dieses Ansatzes promoviert und seine Studenten T. Klinger und S. Reisch haben den Faden weiter gesponnen, indem sie die Entropie der Permutationsaufgabe etwas allgemeiner definierten, sodass sie für eine große Klasse von Fällen bessere untere Schranken erzielten. Dietmar Mense geling es dieses interessante Resultat über einen anderen Weg wesentlich einfacher zu erreichen.

120. Schwöppe, Doris: FASIC 85 ein Frage- und Antwortsystem mit natürlichsprachlicher Eingabe, implementiert in Comskee. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Autorin hatte in einer Reiseagentur gearbeitet und war daran interessiert ihre Diplomarbeit über ein Thema in diesem Umfeld zu schreiben. Ihre Aufgabe bestand darin ein automatisches Auskunftssystem zur Verfügbarkeit von Ferienhäusern zu entwickeln. Die Arbeit hat sie mit einem sehr schönen System abgeschlossen.

Es waren drei Problembereiche zu bearbeiten: Das Verstehen der geschriebenen Deutschen Sprache in dem eingeschränkten Diskursbereich, Die Entwicklung einer kundenspezifischen Dialogstrategie und drittens eine Katalogorganisation, die eine effiziente Beratung ermöglicht. Das Kernproblem war das erste der drei Probleme. Das leichteste war das dritte, das eine Lösung fand, indem in den Baum, der die Ferienhäuser nach Landschaften, der darin vorhandenen Orte und den in den Häusern verfügbaren Räumen, ihrer Ausstattung usw. durch Querverweise so ergänzte, dass Angebote in Nachbarorten oder entsprechenden Landschaften ohne große Suchzeiten gemacht werden konnten.

Zur Lösung der beiden ersten Probleme trugen Beratungen durch Mitarbeiter von linguistischen Teilprojekten des SFB 100, Elektronische Sprachforschung bei. Das System wurde unter Verwendung der Programmiersprache Comskee implementiert. Es war nicht zum Gebrauch für Kunden perfekt genug, wohl aber zur Unterstützung von Mitarbeitern in Reisebüros geeignet.

121: Stutz, Harry: Konstruktion geradliniger Layouts von planaren Graphen. Diplomarbeit am IAM+I der US:

Zusammenfassung: Harry Strutz sollte ein Programm schreiben, das Graphen, wenn sie planar sind, „schön“ in die Ebene einbettet. Hierbei sollte er den von R. Tarjan angegebenen Planaritätstest verwenden. Das war eine schwierige Aufgabe, denn schon der Planaritätstest ist sehr kompliziert und recht knapp dargestellt. Schön sollte heißen, dass die Knoten des Graphen auf dem Blatt einigermaßen gleichverteilt auftreten, was dann, wenn man Kanten durch Strecken repräsentiert, problematisch ist. Das im Rahmen der Diplomarbeit erstellte Programm hat im Gegensatz zu Tarjans Algorithmus eine quadratische Laufzeit, was durch die schönen Einbettungen belegt durch zahlreiche Beispiele) wettgemacht wird. Die erforderlichen Beweise sind alle klar und gut lesbar.

1986

122. Soukup, Holger: Untersuchung von CMOS-spezifischen Unterbrechungsfehlern am Beispiel des schnellen Multiplizierers. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit entstand im Rahmen des SFB 124 und einer Kooperation mit der Firma Siemens. Holger Soukoup verallgemeinert Resultate von Bernd Becker über das Prüfen und Testen von Schaltkreisen bei Stuck – at – Fehlern auf den für die CMOS -Technologie wichtigen und umfassenden Fall der stuck – open – Fehler. Es lagen für diese Untersuchung keine Vorbilder vor. Es wird in der Arbeit zum ersten Mal ein effizienter Test für eine Klasse komplexer Schaltkreise gegenüber diesem Fehlertyp vorgeschlagen. Die Arbeit wurde von Becker und Kolla betreut.

123. Sparmann, Uwe: Entwurf und Test eines Schaltkreises für das Pattern-Matching. Diplomarbeit am IAM+I der US.

Zusammenfassung: Im Rahmen des SFB 124 und einer Kooperation mit der Firma Siemens haben wir intensiv das Problem bearbeitet, den VLSI – Entwurf für Schaltkreise so durchzuführen, dass das Resultat nach der Produktion gegen die häufigsten Produktionsfehlertypen schnell testbar ist. Herr Sparmann hat mit seiner Arbeit hierzu einen sehr schönen Beitrag geleistet. Betreut wurde die Arbeit von Rainer Kolla.

Es geht um die Konstruktion eines Chips, der das Patternmatching leistet: Für ein binäres Bytemuster der Länge m soll festgestellt werden, ob es in einem String der Länge s vorkommt. Hier wird ein Algorithmus gewählt, der zu einem Schaltkreis führt mit einer Tiefe logarithmisch in s und einem Platzbedarf . Darauf aufbauend wird ein Schaltkreis angegeben, der für variables s < t mit festem t den Test relativ zu dem Mehrfach – stuck – open und stuck - at Fehlermodell aufgrund von Eingaben vollständig in Bezug auf beide Fehlertypen vollständig testbar ist. Darüber hinaus zeigt Sparmann, dass dazu mindestens Tests notwendig sind.

124. Schäfer, Thomas: Ein Algorithmus zur Entscheidung der Surjektivität spezieller Grammatikhomomorphismen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um die Analyse eines schon von Schnorr angegebenen Algorithmus. Das Thema gehört in das Umfeld des SFB 100, nämlich der Syntax – orientierten Übersetzungen natürlicher Sprachen. In der Terminologie der formalen Sprachen handelt es sich um Übersetzungen, die durch Abbildungen der Grammatik in die Ableitungsmenge der zweiten Sprache induziert werden, d.h. um Funktoren zwischen den X-Kategorien, die die Ableitungsstrukturen repräsentieren. Thomas Schäfer betrachtet einen Sonderfall: Grammatik wird auf Grammatik abgebildet, d.h. die Funktoren sind längenerhaltend. Grammatiken heißen Äquivalent, wenn sie durch eine Folge solcher surjektiven Transformationen, die eine alternierende Richtung haben, ineinander übergeführt werden können. In der Arbeit wird ein Algorithmus angegeben, der die Äquivalenz von Grammatiken entscheidet. Die Laufzeit ist in vielen Fällen geringer als die des Schnorrschen Algorithmus. Schäfer Charakterisiert aber auch die Fälle, in denen beide Algorithmen gleich Laufzeit besitzen. Experimente legen die Vermutung nahe, dass das Äquivalenzproblem in linearer Zeit in Abhängigkeit von der Größe der Grammatiken entscheiden lässt. Die Arbeit wurde von Thomas Kretschmer betreut.

125. Lang, Mathias: Die algebraische Mehrgittertheorie und der schnelle iterative Löser AMG01. Diplomarbeit am IAM+I der US.

Zusammenfassung: Das Interesse an der im Thema genannten Klasse von Algorithmen vorwiegend zur Lösung von Randwerdproblemen partieller elliptischer Differenzialgleichungen verwendet rührt von der Hoffnung her, diese Methoden auch zur Lösung von Optimierungsproblemen im Zusammenhang mit der planaren Einbettung von Graphen mit vorgegebenem Rand und Kostenfunktionen verwenden zu können - Ein Problem aus dem Rahmen des SFB 124 -. Der Ursprung dieser Algorithmen liegt in der Geometrie. Die AMG – Algebraische Multi-Gridmethoden – sind Abstraktionen dieser Methoden. Das Interesse an diesen Methoden rührte von unserem Versuch her, stabile Gleichgewichtslagen von verallgemeinerten Federmodellen mit sehr vielen Knoten zu berechnen, indem man zunächst Vergröberungen der Netze optimiert, um dann für die erhaltenen planaren Zellen der Einbettung nach Einfügung der bei der Vergröberung entfernten Knoten das entsprechende Problem zu lösen. Durch eine geeignete Folge von Vergröberungen und Verfeinerungen in diesen Prozess hoffte ich ein effizientes Verfahren zu approximativen Lösungen unserer Optimierungsverfahren zu erhalten. Leider gab es noch keine für uns brauchbaren Konvergenzaussagen zu diesen Verfahren. Marthas Lang zeigte an Beispielen, dass bekannte Verfahren überhaupt nicht oder nur sehr langsam konvergieren. Er untersucht spezielle Versionen, wie den V – Zyklus und den W - -Zyklus und analysiert ihr Komplexitätsverhalten. Er entwickelt einen Algorithmus, der exzellent konvergiert, aber algorithmisch zu aufwendig ist. Es gelingt ihm aber eine Approximation dieses Verfahrens anzugeben, das sehr gut Resultate liefert. Hilfreich war die Unterstützung durch Ursula Becker, die Diskussionen mit Heribert Blum, Klaus Stüben und John Ruge.

126. Jungfleisch, Jürgen: Das Konzept der Entropie bei verschiedenen Anwendungen. Diplomarbeit am IAM+I der US.

Zusammenfassung: In der Arbeit führt die bereits in der Diplomarbeit von Dietmar Mense und weiterer dort aufgeführter Arbeiten. Es wird die Anwendung der Idee, durch die Konstruktion geeigneter Informationsquellen zu gegebenen Klassen von Konstruktionsaufgaben mittels der Entropie interessante untere Schranken zu gewinnen, weitergeführt. Hier werden drei verschiedene Aufgaben betrachtet: Untere Schranken für die Höhe von Permutationsnetzwerke auf Gittern, Anzahl der Operationen „Add. mod. 2“ bei der Realisierung spezieller booleschen Funktionen, Berechnung reeller Funktionen mit n Extremwerten. Die Resultate der Arbeit sind vorwiegend negativ: Es konnten mit dem Konzept der Entropie hier keine überzeugenden unteren Schranken gewonnen werden.

127. Doan, Quang Danh: Umsetzung geometrischer Eingaben in Prozeduren. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit schildert zunächst den Netzkalkül, der unserer im SFB 124 entwickelten Programmiersprache CADIC zum Entwurf von Layouts zugrunde liegt. Beim Schaltungsentwurf geht man im Falle komplexerer Systeme im Allgemeinen zunächst von einer geometrischen Gliederung des zu entwerfenden Schaltkreises aus. Die Umsetzung dieser Gliederung in CADIC-Programme sollte automatisch erfolgen. Die Geometrie kann man mit einem geeigneten Eingabegerät auf den Computer Übertragen. Herr Doan definiert geeignete Datenstrukturen zur Repräsentation der Geometrie und ihrer Umsetzung in CADIC-Programme. Auch einen Compiler, der das leistet, hat er im Rahmen dieser Arbeit erstellt.

128. Bühler, Herta: Korrektheitsbeweise von rekursiv beschriebenen logisch-topologischenNetzen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Beim Entwurf von Klassen von Schaltkreisen (SFB 124), für die man eine parametrisierte Darstellung hat, die in es gestattet jeden zu einem Parameter gehörigen Schaltkreis zu berechnen, sollte man mit einem Korrektheitsbeweis für die Darstellung der gesamten Klasse auskommen, anstelle für das Layout jedes einzelnen Falles einen solchen Beweis zu führen. Dabei muss man in Kauf nehmen, dass die einzelnen Individuen nicht in jeglicher oder der in diesem Fall entscheidenden Hinsicht optimal sind. In diesen Fällen kann man hoffen mit Optimierungsverfahren, deren Korrektheit bewiesen ist, eine Anpassung an den vorliegenden Fall vorzunehmen. Diese Idee steht im Hintergrund dieser Diplomarbeit. Hier soll die in diesem Zusammenhang wichtige Frage behandelt werden, wie man die Korrektheit von Realisierungen beweist, die sich rekursiv im Rahmen unseres Netzkalküls, der auf dem Konzept der freien Bikategorie, einer Verallgemeinerung der monoidalen Kategorie, beruht, darstellen lassen.

So definiert die Arbeit zunächst diese freie Bikategorie, behandelt die Frage der Semantik. Während man im Fall der freien X- und D-Kategorie mit Funktoren in Kategorien von Abbildungen gut auskommt, ist es hier einfacher einen Relationenkalkül zugrunde zu legen. Zum Abschluss der Arbeit zeigt Frau Bühler an zwei nicht ganz einfachen Beispielen, nämlich der parametrisierten Darstellung von schnellen Addieren und Multiplizierern, dass dieses Konzept zumindest zum Beweis der Korrektheit dieser Klassen von Entwürfen gut geeignet ist. Die Arbeit wurde von Reiner Kolla betreut.

129. Brühl, Herbert: Untere Schranken für geometrische Probleme. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es geht um die Berechnung unterer Schranken für Berechnungen über den reellen Zahlen. Diese Arbeit verwendet Konzepte oder Resultate von M. Ben-Or, J.M. Steele und A.C. Yao und R. Rivest. Unmittelbar beruht sie auf Ergebnissen von W. J. Jaomczyk. Die Arbeit wurde von Thomas Kretschmer und Hans Georg Osthof betreut.

Programme lassen sich durch Berechnungsbäume repräsentieren, die universelle Überlagerungen des Berechnungsgraphs des jeweiligen Programms bilden. Die Anzahl der Verzweigungen auf einem Pfad dieser Bäume liefert eine untere Schranke für die Anzahl der Rechenschritte, die das Programm für diesen Pfad benötigt. Indem man die Minimalzahl der Verzweigungen auf den Pfaden für jegliches Programm abschätzt, das die gleiche Funktion berechnet, erhält man eine untere Schranke für die Laufzeit aller Programme, die die gleiche Funktion berechnen. Die Idee geht auf M. Rabin zurück.

In dieser Arbeit wird gezeigt, dass die Lösung des Entscheidungsproblems für die Einfachheit eines Polygons mit n Ecken im dreidimensionalen Raum Operationen erfordert. Es werden weiter scharfe untere Schranken für das Durchmesserproblem gezeigt, für das Problem ob alle Punkte einer Menge auf ihrer konvexen Hülle liegen und die Bestimmung des minimalen Abstandes zweier Punktmengen. Der Schlüssel für die Beweise bildet die von Jaromczyk eingeführte Slicertechnik. (Schnitte einer geeigneten algebraischen Kurve mit der zu entscheidenden Mannigfaltigkeit. Der Logarithmus der Anzahl der Zusammenhangskomponenten liefert die untere Schranke)

130. Bertrand, Jean-Paul: Schichtzuweisung unter dem Aspekt der Kontaktminimierung. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeit entstand im Zusammenhang mit der im SFB 124 entwickelten Programmiersprache CADIC. Der Entwurf eines Layouts zur Realisierung von Chips erfordert die Platzierung der aktiven Schaltelemente und deren Verbindung durch den Strom leitende Pfade. Hierfür stehen meist mehrere Schichten zur Verfügung, da sich nicht jeder Verdrahtungsgraph planar realisieren lässt. Die Anzahl der Schichten möchte man klein halten und bei gegebener Schichtzahl die notwendigen Übergänge von einer Schicht in eine andere. Der Verbindungsgraph wird hier auf ein Gitter platziert und der Schichtwechsel findet nur in Gitterpunkten statt. Es war bekannt, dass das Problem das Layout mit einer Minimalzahl von Schichtwechseln zu realisieren NP-vollständig ist, wenn drei Schichten zur Verfügung stehen (W. Lipski). Im Fall von vier Schichten lässt sich jedes Layoutproblem lösen (M. Brady und D. Brown). Allerdings bleibt die Frage der effizienten Optimierbarkeit im Falle von mehr als drei Schichten offen. In der Arbeit wird das Problem der Kontaktminimierung für n Schichten, n >0 behandelt. Die Idee zur effizienten Lösung des Falles n=2 wurde bereits durch Paul Molitor auf der STACS 87 vorgestellt, hier wird die Idee im Detail durchgeführt. Für den Fall n>3 wird gezeigt, dass das Optimierungsproblem in NP liegt, wodurch dieses 1982 gestellte Problem seine Lösung fand. Die Arbeit wurde von Reiner Kolla betreut.

131. Bergmann, Peter: Abschätzung des Kommunikationsaufwandes bei Scheduling. Diplomarbeit am IAM+I der US.

Zusammenfassung: Ein Schedule besteht aus einem Plan, der auf Prozessoren zu bearbeitende Problemen, für die eine partielle Ordnung hinsichtlich der möglichen Bearbeitungsreihenfolgen für diese Probleme enthält sowie die Zeit, die zur Bearbeitung erforderlich ist. Das klassische Schedulingproblem besteht in der Aufgabe, die Bearbeitungszeit für die die Gesamtheit der Aufgaben auf den zur Verfügung stehenden gleichen Prozessoren zu minimieren (E.G. Coffman und R.L. Graham 1972, J.D. Ullman, W. Poguntke).

In dieser Arbeit wird das Problem etwas weiter gefasst. Die zur Verfügung stehenden Prozessoren sind vernetzt und die entstehenden Kosten werden geprägt durch eine zwischen den Rechnern erforderliche Kommunikation.

Die Resultate: Die Lösungen zu dem klassischen Problem können bei den betrachteten Erweiterungen unbrauchbar werden. Das erweiterte Schedulingproblem ist schon für den Fall zweier Prozessoren NP-vollständig. Neben weiteren überraschenden Resultaten dieser Art, wird ein Algorithmus zur Approximation von optimalen Lösungen des erweiterten Problems angegeben. Das Problem einen gegebenen Schedule durch lokale Vertauschungen von Prozessoren im Netz zu verbessern, ist schon für Kreise in NP.

1987

132. Kirchhoff, Rainer: Kontrastverstärkung und Grauwertreduktion – eine experimentelle Untersuchung. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Aufgabenstellung: Ein schwarz-weiß Bild mit m Abstufungen in seinen Grauwerten soll in ein schwarz-weiß Bild mit n<m Abstufungen umgewandelt werden. Das ist ein Problem, das beim Drucken häufig auftritt. Kirschhoff sollte untersuchen in wie weit sich die Methoden der lateralen Inhibition zu diesem Zweck verwenden lassen. Wie eine optimale Lösung auszusehen hätte ist schwer zu sagen. So stellt die Arbeit die Theorie zur lateralen Inhibition knapp dar. Verschiedene Möglichkeiten, das Problem anzugehen werden diskutiert und experimentell an Beispielen erprobt. Die Widergabe der Beispiele leidet unter den Möglichkeiten hinsichtlich eines Ausdrucks, der den vorgegebenen Stufungen entspricht.

133. Kopp, Thomas: Möglichkeiten der Grauwertreduktion bei digitalisierten Bildern. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um eine Frage, die mit dem Thema der vorhergehenden Diplomarbeit eng zusammen hängt. Bilder sollen in Speichern aufbewahrt werden. Da das sehr viel Speicherplatz erfordert, ist man ein einer Datenkompression interessiert, die die wesentliche Information des Bildes enthält. Die Informationstheorie liefert untere Schranken dafür, wie weit eine Reduktion verlustfrei überhaupt möglich ist. So stellt die Arbeit zunächst elementare Grundlagen der Informationstheorie dar. Konzepte zur Datenkompression werden dann mit diesen Methoden beurteilt. Die erarbeiteten Algorithmen werden in Comskee implementiert und die Korrektheit der Implementierung wird bewiesen. Die Aufgabenstellung resultierte aus einer Kooperation mit der Firma Dialogika. Die Aufgabe war für eine Diplomarbeit zu schwer. Die Theorie der Bildverarbeitung steckte noch in den Kinderschuhen.

1988

134. Hümbert, Annerose: Die Kombination des Setup Problems und des Ein – Maschinen – Scheduling Problems. Diplomarbeit am IAM+I der US.

Zusammenfassung: Es handelt sich um die Untersuchung des Einmaschinen-Schedulingproblems mit gewichteter mittleren Ausführungsdauer und den Versuch das Set-Up Problem (Anzahl der zusätzlicher Datentransfer minimieren) mit ins Spiel zu bringen. Die Arbeit gibt den Stand der Literatur hinsichtlich beider Probleme wieder. Anschließend versucht sie beiden Optimierungsproblemen gerecht zu werden, was ihr in einem Sonderfall auch gelingt. Die Fragestellung geht auf Ulrich Simon zurück, der die Arbeit auch betreut hat.

135. Schömer, Elmar: Fehlertolerantes Routing auf dem n-dim. Würfel. Diplomarbeit am IAM+I der US.

Zusammenfassung: Der von L.G. Valiant angegebene Routing-Algorithmus zur Übermittlung von Nachrichtenpaketen anstelle einer permanenten Reservierung einer Leitung ließ erwarten, dass er nicht nur im Mittel sehr effizient ist, sondern auch eine hohe Robustheit gegenüber von dem Ausfall von einzelnen Knoten hinsichtlich ihrer Rolle in der Informationsweitergabe. Elmar Schömer konnte meine Vermutung in vollem Umfang bestätigen: Fehlerhafte Prozessoren im Netz werden lokal umgangen. Auf dem n-dim. Würfel kommt man bei der hier angegebenen Strategie im Mittel höchstens auf einen Verzögerungsfaktor der Größe 3. Die Arbeit wurde von Bernd Becker und Ulrich Simon betreut.

136. Serf, Bernd: Probleme bei der Simulation kombinatorischer Schaltkreise unter Ausnutzung von Hierarchie. Diplomarbeit am IAM+I der US.

Zusammenfassung: Die Arbeitsweise und Korrektheit großer Schaltkreise ist nur dann übersehbar, wenn ihr Aufbau einfachen Gesetzmäßigkeiten folgt. Die Diplomarbeit betrifft das Problem, die logische Korrektheit der Entwürfe – Laufzeitbetrachtungen werden nicht mit einbezogen - solcher Schaltkreise durch Simulationen zu testen. Die Umsetzung hierarchischer, eventuell mittels rekursiver Verfeinerungen definierten Netzen in Programme, in denen die rekursiven Verfeinerungen als rekursive Prozeduren auftreten, ist nicht einfach. Bernd Serf löst das Problem, indem er zunächst das Netz so transformiert, dass es zwar in dieser Form nicht zu einer unmittelbaren Realisierung taugt, dafür aber in ein Programm übersetzt werden kann, dessen Testergebisse auch für das ursprüngliche Netz Gültigkeit haben. Diese Transformation und Übersetzung in das erwähnte Programm wurde im Rahmen der Diplomarbeit auch implementiert. Betreut wurde diese Arbeit durch Rainer Kolla.

137. de la Hamette, Luc: Automatische Leitungsgenerierung für CADIC. Diplomarbeit am IAM+I der US.

Zusammenfassung: Bei der Montage von Moduln auf Chips werden gewöhnlich die Verbindungsleitungen um die Module herumgeführt. Manchmal ergibt sich auch die Möglichkeit einen Kanal durch einen Modul hindurch zu verwenden. In der Arbeit wurde die folgende Frage bearbeitet: Kann man beim Layoutentwurf in dem Fall, dass das die Module definierende Netz vorliegt, in effizienter Weise und mit Platzgewinn das Layout so planen, dass man die Möglichkeit von Tunnel durch Module zum Zwecke von Platzeinsparungen mit einbezieht. Herr de la Hammette gibt einen Algorithmus an, der dieses Problem löst, wenn der Entwurf des Chips als Comskee-Programm vorliegt, das den Chip den Modulen entsprechend in hierarchischer Form beschreibt. Seinen Algorithmus hat er im Rahmen der Diplomarbeit auch implementiert. Die Arbeit wurde von Paul Molitor betreut.

138. Müller, Reinhard: Platzierungsvorgaben für Standardzellen aus CADIC-Beschreibungen. Diplomarbeit am IAM+I der US.

Zusammenfassung: Das im Forschungsbereich von Siemens entwickelte Entwurfssystem VENUS stand uns zu Studienzwecken zur Verfügung. Im Rahmen eines Praktikums wurde eine Schnittstelle zwischen CADIC und VENUS entwickelt. Diese Schnittstelle verschenkte Informationen über die Geometrie, die in CADIC aufgrund seines Grundkonzeptes stets vorhanden sind. Reinhard Müller ergänzte diese Schnittstelle, sodass die in VENUS vorgesehenen Möglichkeiten einer Clusterbildung genutzt wurden. Hierzu musste der Ausgangsschaltkreis automatisch so aufgeschnitten werden, dass die Clustervorgaben von VENUS zu effizienten Flächenzuweisungen verwendet werden konnten. Diese Konstruktion wurde an Beispielen erprobt. Der Laufzeitgewinn betrug bis zu 10%. Im Falle eines Multiplizierers war kein Gewinn messbar.

139. Burch, Thomas: Ein graphisches Eingabesystem für CADIC. Diplomarbeit am IAM+I der US.

Zusammenfassung: Der Entwurf von Schaltkreisen wird in vielen Fällen durch Diagramme begleitet, die auch eine Verteilung der Komponenten des geplanten Layouts über den Chip nahe legen. Es liegt deshalb nahe, diese Diagramme auf den Rechner zu übertragen, um sie Automatisch weiter zu verarbeiten. Das wird auch schon durch die geometrische Natur von CADIC nahe gelegt – CADIC hatte sein Vorbild in den von mir eingeführten freien X-Kategorien, deren Vorstellung von den Zopfgruppen Artins geprägt war. Thomas Burch hat in seiner Diplomarbeit die mit der Diplomarbeit Quang Dang Doans begonnenen Arbeiten fortgeführt. Allerdings war es aus verschiednen Gründen erforderlich das ganze System neu zu schreiben. Thomas Burch gibt eine ausführliche Darstellung der mit dieser Konstruktion verbundenen Probleme. Er schätzt zudem die für die Übersetzung der graphischen Eingabe nach CADIC erforderlichen Laufzeiten ab. Die Diplomarbeit ist ein sehr schönes Beispiel für eine gelungene Umsetzung theoretischer Überlegungen in ein korrektes praktisch verwendbares System.

1989.

140. Dorndorf, Winfried: DEZENT, Ein Informationssystem mit dezentraler Erfassungs- und Anwendungskomponente bei zentraler Speicherung. Diplomarbeit am Fachbereich für Informatik (FI) der US.

141. Nagel, Reinhard: Anwendungskomponente zum Datenbanksystem DEZENT. Diplomarbeit am FI der US.

Zusammenfassung: Beide Diplomarbeiten stellen ein umfangreiches Unternehmen dar, das an sich den Rahmen von Diplomarbeiten übersteigt. Das Vorhaben geht auf eine Anfrage des Kollegen Rolf Hachmann, des Leiters unseres Institutes für Vor- und Frühgeschichte zurück: Das Institut hat sehr große Datenmengen zu verwalten, sie zu erhalten, zu ergänzen und weiterzuführen. Hier sollte es doch vielleicht möglich sein durch die Entwicklung geeigneter Software den Einsatz des Computers zu erleichtern. Zum Einsatz kam das System COMSKEE , das mit seinem Datentyp Wörterbuch (eine spezifizierbare Datenbank) für diese Aufgaben als besonders geeignet erschien.

Die Anfrage führte zur Entwicklung des Systems DEZENT durch Winfried Dorndorf und Reinhard Nagel die durch Manfred Ries von der Seite der Informatik betreut wurden. Auf Seite des Institutes für Vor- und Frühgeschichte erfolgte die Betreuung durch den Kollegen Jan Lichardus und Dr. Francois Bertemes.

Winfried Dorndorf beschäftigt sich in seiner Diplomarbeit mit der Konstruktion der Verwaltung der Datenbasis und der Benutzerschnittstelle.

Reinhard Nagel behandelt die Anwendungskomponente:

· Definition einer Sprache zur Formulierung der Benutzeranfragen an die Datenbank. Den Anfragen der Benutzer muss das System durch die Verwendung der einschlägigen Terminologie entgegenkommen.

· eine abstrakte Datenstruktur zur Verwaltung der so genannten Materialgruppen, die in der Archäologie eine Rolle spielen

· grafische Darstellungen (Diagramme, Piktogramme)

Das System überprüft die Eingaben auf syntaktische und in gewissem Umfang auch auf semantische Korrektheit: z.B. Konzentrationen eines chemischen Elementes können nicht über 100% liegen.

Das Projekt war ein voller Erfolg. Die Software wurde auch in dem entsprechenden Institut der Akademie der Wissenschaften in Moskau verwendet.

Finanziert wurde es durch das von Kollegen Helge Scheidig initiierte I.I.I.-Projekt, in dem Siemens die Universität des Saarlandes über einige Jahre großzügig unterstützte.

142. Hinsberger, Uwe: Zellenbasierte Dimensionierung kombinatorischer Schaltkreise. Diplomarbeit am FI der US.

Zusammenfassung: Die Diplomarbeit enthält einen interessanten neuen Vorschlag der die rechnergestützte physikalische Realisierung integrierter Schaltungen betrifft. Es geht um die Optimierung von Fläche und Zeitverhalten. Es werden damals für die Standartoperation Realisierungen durch eine Basiszelle vorgeben, die in allen Entwürfen zu nutzen sind. Diese Universalität führt in vielen Anwendungsfällen zu Überdimensionalisierungen. Uwe Hinsberger bringt nun folgenden Idee ins Spiel: Man verwendet zwar weiter universell verwendbare Bausteine, zu denen aber mehrere geometrisch verschiedene Realisierungen und Erweiterungen hinsichtlich ihrer Leistung vorgegeben werden. Damit erhält man einen größeren Spielraum zur Optimierung des Platzbedarfs, was sich auch Vorteilhaft auf das Schaltverhalten auswirkt. Natürlich hat man das durch ein schwierigeres Optimierungsverfahren zu bezahlen.

Die Arbeit gibt eine sehr umfassende Übersicht über den Stand der Kunst und eine sehr weitgehende Klärung der Komplexitätsprobleme, die mit durch diese Optimierungen aufgeworfen werden. Für die Lösung des Problems in dem Sonderfall der verzweigungsfreien Schaltkreise gibt er einen effizienten Algorithmus an. Die Korrektheit aller Algorithmen wird bewiesen. Man darf bei seinem Verfahren mit Laufzeitgewinnen von 50 bis 60% bei Investitionen in Fläche in der Höhe von 8-37%.

Die Arbeit wurde von Reiner Kolla betreut.

143. Kiefer, Bernd: Schichtzuweisung auf Schaltkreisfeldern. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit entstand im Rahmen des SFB 124.

Schaltnetze, die Schaltfunktionen realisieren, sind meist nicht planar, sodass man zu ihrer Realisierung mehr als eine ebene Schicht auf einem Chip benötigt. Kontakte, die Knoten zwischen verschiednen Ebenen verbinden, sind in der Fertigung fehleranfälliger als Kontakte zwischen Knoten in der gleichen Ebene. Hieraus resultiert ein Optimierungsproblem mit dem Ziel die Anzahl der Ebenenwechsel der Verdrahtung zu minimieren. Die in dieser Hinsicht optimalen „Verdrahtungen“ haben aber leider auch ihren Preis, der sich in einer Verlängerung der Leiterbahnen und damit eventuell in einer Reduzierung der Schaltgeschwindigkeit oder einer Erhöhung des Flächenbedarfes auswirkt. Die von uns entwickelte Entwurfssprache CADIC erlaubt die Beschreibung parametrisierter Entwürfe, speziell in hierarchischer Form. Damit stellte sich die Frage, für den gesamten Parameterraum gültige Realisierungen anzugeben, die den oben genannten Entwurfskriterien weitgehend genügen. Herr Kiefer hat in seiner Arbeit für einen Sonderfall dieser Fragestellung sehr schöne Resultate erzielt: Der Hierarchische Entwurf führt zu 2-dimensional periodischen Feldern. Man löst das Einbettungsproblem für den Fundamentalbereich nicht für die Ebene, sondern für den Torus und erhält die Gesamtlösung durch „Abwicklung“ des Torus. Kiefer zeigt aber auch, dass das Bestehen auf der hierarchischen Lösung zu erhöhten Kosten führen kann, so dass sich eine Nachbearbeitung des speziellen Falles auszahlen kann.

Die Arbeit wurde von Paul Molitor betreut.

144. Vogelgesang, Bernd: Entwurf einer weitgehend maschinenunabhängigen Codeerzeugung für COMSKEE. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit entstand im Rahmen des SFB 100.

Der Compiler für linguistische Arbeiten entwickelte Programmiersprache COMSKEE musste nach der Anschaffung neuer Maschinen stets wieder portiert werden. Die zur Unterstützung dieser Aufgabe entwickelte Zwischensprache CIL erwies sich aber aufgrund der Weiterentwicklung der Assemblersprachen zunehmend als nicht optimal für diesen Zweck. eine weitere Zwischensprache CAM entwickelt wurde, die eine Brücke zwischen CIL und den Assemblern bildet. Der Übergang von CAM zum Assembler ist sehr effizient. Der Übergang von CIL zu CAM fast Unabhängig von der Zielmaschine. Diese Entwicklung erwies sich als außerordentlich befriedigend.

Die Arbeit wurde von Manfred Ries und Thomas Kretschmer betreut..

145. Nikolaus, Andreas: Informatik: Rechenanlagen. Diplomarbeit am FI der US.

Zusammenfassung: Es handelt sich um die Ausarbeitung meiner Vorlesung Rechenanlagen in den Wintersemestern 1983/84 und 1987/88.

Es wird ein abstraktes Modell einer Rechenanlage entwickelt, welches wohldefiniert ist und im mathematischen Sinn beweisbare Aussagen zulässt. Der erste Schritt besteht in der Herleitung einer Maschinenstruktur, die durch konkrete, elementare Programmieraufgaben motiviert wird.

Es werden anschließend die technisch realisierbaren Grundbausteine beschrieben, die zur Realisierung der Maschine verwendet werden. Es wird eine Konstruktion der Maschine angegeben, deren Korrektheit bewiesen wird. Entscheidend ist hierbei die Entwicklung eines Simulationsbegriffes. Die Maschine wird stufenweise ausgebaut. Die Verbindung der Versionen wird durch den Nachweis der Simulierbarkeit der Folgeversion auf der Vorgängerversion hergestellt. Hierdurch wird die Korrektheit der Maschinenerweiterungen auf die Korrektheit des Originals zurückgeführt.

Es wird in Verbindung mit einem einfachen Betriebsystem eine einfache Prozedurtechnik realisiert. Jedes Unter Programm erhält von dem Betriebssystem einen Speicherbereich zugewiesen, den es nicht verlassen kann. Die Daten holt das übergeordnete Programm ab, sodass das Unterprogramm kein Unheil anrichten kann.

Herr Nikolaus hat die Vorlesung sehr sorgfältig ausgearbeitet. Zum Gelingen haben auch die kritische Diskussion des Textes mit Gisela Pitsch, Prof. Volker Claus und Dr. Paul Molitor beigetragen. Allen möchte ich an dieser Stelle nochmals danken.

Von Privatdozent Bernd Becker vergebene und betreute Arbeiten 145, 146 und 147, die in den Kontext der in meinem Teilprojekt des SFB 124 behandelten Problemkreis gehören.

146. Krieger, Rolf Nikolaus: Ein strukturbasiertes Verfahren zur Fehlersimulation kombinatorischer Schaltkreise. Diplomarbeit am FI der US.

Zusammenfassung: Die Produktion von Chips ist nur begrenzt zuverlässig. Man hat die Wahl zwischen weniger dicht gepackten Schaltungen, was zu Verringerungen der Schaltgeschwindigkeit und eventuell einer Erhöhung des Energieverbrauches führt, und dichter gepackten Chips mit einer geringeren Ausbeute an korrekten Produkten. In jedem Fall ist ein Test hinsichtlich der Korrektheit des Produktes erforderlich. Das wirft die Frage auf, ob man Vorteile erzielen kann, wenn man nicht nur die Komplexität (Größe, Nichtplanarität,..) von Schaltkreisen reduziert, sondern bei dem Entwurf auch eine Testbarkeit in vertretbarer Zeit im Auge behält.

In der vorliegenden Arbeit geht es um die Berechnung von Testeingaben für den statischen Test des Schaltkreises. Der besondere Aspekt, der hier betrachtet wird, besteht in der Berechnung möglichst kleiner Testmengen, die durch Simulationen der wahrscheinlichsten Fehlermengen gewonnen werden sollen. Speziell wird der von Antreich und Schulz betrachtete Aspekt einer Reduktion des Schaltkreises zum Zweck einer beschleunigten Fehlersimulation untersucht: In speziellen Fällen werden sich lokale Fehler nicht an den Ausgängen zeigen oder sie zeigen sich auch dann am Ausgang, wenn man gewisse Teile der Schaltung überbrückt. Die Ausnutzung dieser Effekte kann man zur Beschleunigung der Fehlersimulationen nutzen, wenn diese Eigenschaften einen in gewissem Umfang generellen Charakter haben Herr Krieger hat diesen Aspekt gesehen und in diesem Zusammenhang „Schaltkreisreduktionen“ eingeführt, die sich in Linearzeit durchführen lassen und die, wie international als in diesem Zusammenhang als relevante Testbeispiele akzeptierte Schaltkreise zeigen, zu wesentlichen Laufzeitgewinnen führen können.

147. Hahn, Ralf: Methoden zur Fehlersimulation kombinatorischer Schaltkreise. Diplomarbeit am FI der US.

Zusammenfassung: Die Fehlersimulation von Schaltkreisen kann verkürzt werden, indem man Fehlerdominanz ins Spiel bringt. Der Test auf einen Fehler an bestimmter Stelle mag unter der Annahme der Hypothese, dass nur Einzelfehler existieren, zugleich ein Test auf Fehler an zahlreichen verschiedenen anderen Fällen darstellen. Herr Hahn zeigt, dass ein vollständiger Dominanztest NP-vollständig ist und deshalb i.A. praktisch nicht vollständig realisiert werden kann. Das Konzept der Fehlerdominanz war nicht neu. Herr Hahn hat aber eine interessante Klasse von Sonderfällen definiert, für die diese Berechnung effizient durchführbar ist. Er schätzt darüber hinaus auch den Gewinn an Rechenzeit ab, der sich bei der Fehlersimulation auf Basis einer Vorberechnung der Dominanzen ergibt.

148. Spanier, Uwe: Automatische Pfadgenerierung für CADIC. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit ergänzt unser Chipentwurfsystem CADIC durch eine Komponente. Diese Arbeit führt eine Arbeit von Reiner Kolla weiter.

Unsere Entwurfsprache beruht im Kern auf den von mir eingeführten Beschreibungen der Schaltkreise durch bikategorielle Ausdrücke und hierarchische Verfeinerungen dieser Ausdrücke durch Konstrukte der gleichen Natur. Diese Schaltkreisrepräsentationen werden in Abhängigkeit von dem gegebenen konkreten Parameter in Syntaxgraphen umgesetzt, wie schon in bereits aufgeführten Diplomarbeiten beschrieben wurde, und weiter in den daraus konstruierten zugehörigen erweiterten planaren Graph. Dieser planare Graph, das logisch-topologische Netz, enthält alle für die Konstruktion des konkreten instantiierten Schaltkreises erforderlichen Informationen. Auf Basis dieses Graphs erzeugt die von Uwe Spanier konstruierte Komponente ein konkretes Layout durch Positionierung der der Komponenten und der Verbindungspfade zwischen Ein- und Ausgängen dieser Komponenten.

1990

149. Grünewald, Birgit: Entwurf eines Chips zur Berechnung von Ausgleichsparabeln. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit war technisch sehr schwierig. Die Entwicklung eines solchen Chips bis zur Fertigungsreife hätte auch bei einer Ausstattung mit allen für einen solchen Zweck erforderlichen Werkzeugen mindestens ein „Mannjahr“ erfordert und hätte somit den Rahmen einer Diplomarbeit überschritten.

Das Ziel der Arbeit bestand darin, unser Entwurfssystem CADIC einem weitreichenden Test zu unterziehen. Selbst bei Verzicht auf die Ausnutzung aller Möglichkeiten, wie z.B. einer hochgradige Parallelität der Berechnung, hätte in den Chipentwurf eine Gleitkommaarithmetik integriert werden müssen.

Frau Grünewald diskutiert verschiedene Lösungsmöglichkeiten, die sich z.B. aus der Annahme des Vorhandenseins einer Zellenbibliothek ergeben, die den Entwurf gewisser Komponenten überflüssig machen würden. Das bringt natürlich sehr viele Verzweigungen ins Spiel; man denke dabei nur an Testbarkeitsfragen.

Die Arbeit war für die Weiterentwicklungen unseres Teilprojektes des SFB 124 aber sehr wichtig, da sie eine Fülle von Anregungen zur Weiterentwicklung von CADIC ergab. Die Arbeit wurde durch Reiner Kolla betreut.

150. Kiel, Detlef: VLSI-Architekturen zur Verwaltung von Wörterbüchern – Analyse und Entwürfe. Diplomarbeit am IF der US.

Zusammenfassung: Das Suchen in großen Verzeichnissen oder Wörterbücher ist ein sehr häufiger Prozess in Computeranwendungen, so dass sich die Frage stellt, ob man für diesen Zweck speziell ausgelegte Hardware entwickeln sollte. Dieser Frage ist diese Diplomarbeit gewidmet. Es geht also um die Frage, ob es sich lohnt bekannte Suchalgorithmen zu parallelisieren. Man kann das zum Beispiel tun, indem man das gesamte Wörterbuch auf verschiedene Speicher so verteilt, dass die Zugriffshäufigkeit auf alle gleich hoch ist und so dass in jedem Speicher jeder Anfangsbuchstabe mit gleicher Häufigkeit verlangt wird. Jede Anfrage sendet man an jeden der Speicher und erzielt damit einen gewissen leicht abschätzbaren Gewinn in der Suchzeit. Diese Idee kann man rekursiv verfeinern. In der Arbeit wird dieser Ansatz informationstheoretisch diskutiert, und verschiedene Realisierungen werden untersucht und mittels CADIC als Chipentwurf realisiert.

151. Heckler, Christian: Obere und untere Schranken beim zwei- und dreidimensionalen VLSI-Entwurf. Diplomarbeit am FI der US.

Zusammenfassung: Ein wesentliches Problem beim Chipentwurf besteht darin einen vollständigen logischen Entwurf so auf einem vorgegebenen ebenen Gitter einzubetten, dass das Maximum der für die Schaltgeschwindigkeit wesentlichen Distanzen klein wird. Es stellt sich in diesem Zusammenhang die Frage, wie groß in dieser Hinsicht der Gewinn sein würde, wenn uns zur Realisierung ein räumliches Gitter der selben Maschenweite zur Verfügung stünde. Die Untersuchung dieser Frage ist der Gegenstand dieser Diplomarbeit. Im Hintergrund stehen auch entsprechende Fragen von Prozessornetzwerken und des Verständnisses der 3-dimensionalen Architektur des Gehirns.

Herr Heckler beweist einige in diesem Zusammenhang interessante asymptotische Aussagen:

· Benötigt man im 2-dim. Fall eine Fläche der Größe , so genügt im 3-dim.Fallein Volumen der Größe .

· 2-dim. Layouts lassen sich effizient in gute 3-dim. Layouts übersetzen.

· Unterscheidet man zwischen aktiven und nicht aktiven Knoten, dann ist der Sonderfall, dass alle aktiven Knoten in derselben Ebene liegen von Interesse (1-aktiv Fall). Hierzu zeigt Heckler: Im 1-aktiven Fallen ist nur eine begrenzte Schichtzahl von Interesse. Es gibt Fälle, in denen der viel-aktiv Fall keinen Vorteil von dem 1-aktivfall erbringt.

152. Groh, Markus: Bewegen eines rechtwinkligen Objektes durch eine Szene mit isothetischen Hindernissen zur Anwendung bei der VLSI-Verdrahtung. Diplomarbeit am FI der US.

Zusammenfassung: Es lässt sich leicht ein Zusammenhang zwischen dem Verdrahtungsproblem von Chips und dem Problem der kollisionsfreien Bewegung eines Polyeders von einem vorgegebenen Startpunkt zu vergebenem in einer mit Poliedern besetzten Ebene herstellen.

Markus Groh verwendet das bekannte Konzept des zur Poliederverteilung gehörigen Sichtbarkeitsgraphs und die Konstruktion des zu den Poliedern gehörigen Voronoidiagrams, um Lösungen des Problems zu konstruieren. Besondere Aufmerksamkeit wird dem isothetischen Sonderfall gewidmet (Alle Winkel der Polygone sind rechtwinklig und die Kannten aller Polygone liegen achsenparallel). Die Entfernung wird in der oder der gemessen. Im Fall, dass die Polieder Rechtecke sind, gibt es eine einfache effiziente Lösung. Schließlich wird eine Verbindung hergestellt zwischen der Bewegungsplanung und dem Chiplayout. Die Arbeit gibt eine gute Einführung in den aktuellen Stand der Forschung und diskutiert die ausführlich die mit diesen Fragen verbundenen Komplexitätsfragen.

Die Arbeit wurde von Elmar Schömer betreut.

153. Eickholt, Hans-Hermann: Entwicklung zweier VLSI-Multipliziererchips mit dem CAD-Entwurfssystem VENUS 1.43. Diplomarbeit am FI der US.

Zusammenfassung: Im Rahmen einer Kooperation mit der Firma Siemens wurde uns von der Firma ein Rechner vom Typ 7536 Venus zur Verfügung gestellt und das Chipentwurfsystem mit dem gleichen Namen. Herr Eickolt realisiert mit diesem System je einen Chipentwurf für zwei verschiedene Multiplizierer. Das war eine harte Aufgabe, da er sich zunächst einmal in das uns fremde System Einarbeiten musste. Er sollte Erfahrungen mit diesem System sammeln, um uns eine Basis für einen Vergleich von CADIC und Venus zu ermöglichen. Für unsere Vorhaben im SFB 124 war das in dieser Arbeit erstellte Resume von großem Interesse. Die Version Venus 1.43 wurde später durch die Version Venus 3 ersetzt, die benutzerfreundlicher war.

Die Arbeit wurde von Bernd Becker und Hans-Georg Osthof betreut.

154. Zimmer, Walter: Realisierung eines schnellen 1024-bit-Multiplizierers. Diplomarbeit am FI der US.

Zusammenfassung: Der im Zusammenhang mit den Erfordernissen der Kryptographie und auch anderen Anwendungen wachsende Bedarf sehr große Zahlen effizient zu multiplizieren motiviert diese Diplomarbeit. Die zu lösende Aufgabe besteht in einer Verteilung der Logik eines großen Multiplizierers auf mehrere Chips ohne dabei eine wesentliche Einbuße an Rechenleistung in Kauf nehmen zu müssen. Genauer: Lässt sich ein Multiplizierwerk, dessen Layout den Platz mehrer Chips belegt, so organisieren, dass man bei der Multiplikation von

n - stelligen Zahlen bei der Verwendung des Wallace - trees und der Idee von Luk und Vuillmin weiterhin mit der gleichen asymptotischen Laufzeit auskommt.

Walter Zimmer gib t eine Schema zur Lösung des Problems für beliebige n an, analysiert aber nur den Fall n = 1024 in allen Details. Hierbei muss er eine Annahme über die Verfügbarkweit von Pins (Aus-Eingangskontakte) machen, die in einigen Technologien zur Verfügung steht, aber damals noch nicht in der hier benötigten Größenordnung. Unter dieser Voraussetzung zeigt er, dass sein Problem in der Tat eine Lösung der erhofften Qualität besitzt.

Die Arbeit wurde von Paul Molitor betreut.

155. Weber, Wolfgang: Entwurf und Test einer Familie von schnellen Gleitkommeaddierern. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit bezieht sich auf das Zellenfehlermodell (höchstens eine Zelle ist fehlerhaft). Ein effizienter, vollständiger Test der produzierten Chips, auch unter dieser einschränkenden Annahme, ist i.a. nicht möglich. Somit stellt sich die Frage, ob man Chips ohne Einbußen an Effizienz und ohne einen zu hohen Preis für die zur Realisierung benötigte Fläche so entwerfen kann, dass sie hinsichtlich des betrachteten Fehlermodells schnell testbar sind. Es handelt sich dabei nicht um die Diskussion des Problems für ein festes n, sondern um einen parametrisierten Chipentwurf.

Die Resultate: Für die gesamte dem IEEE – Standart entsprechende parametrisierte Realisierung des Gleitkommaaddierers konnte auch mit der die Testbarkeit betreffenden Erweiterungen keine brauchbare universelle Lösung gefunden werden. Schon im Fall n = 16 wurde für eine Fehlerüberdeckung von 92% auf einem aktuellen Rechner eine Laufzeit von rund 40 Stunden benötigt. Durch relativ kleine Ergänzungen des Layouts in den betrachteten Sonderfällen n=32 und =64 konnten jedoch Tests angegeben werden, die eine Fehlerüberdeckung von 100% erzielten. Die Größe der Tests: 508 bzw. 803.

Die Arbeit schließt an die Dissertation von Uwe Sparmann an, der die Arbeit auch betreut hat. Das Resultat diente auch zur Realisierung der Gleitkommaarithmetik in einem Projekt am Lehrstuhl von Wolfgang Paul.

156. Pitsch, Gisela: Effiziente parallele Verfahren zur Entscheidung des Wortproblems bei Dycksprachen. Diplomarbeit am FI der US.

Zusammenfassung: Es geht darum für Klammersprachen das Wortproblem unter effizienter Ausnutzung der in einem Netz vorhandenen Rechnerkapazität zu lösen. Optimale Lösungen für das auf realen Netzen nicht effizient simulierbare PRAM existierten. Gisela Pitsch betrachtet ein System von Rechnern, dessen Knoten als die Ecken eines k-dimensionalen Würfels repräsentiert werden können. Sie betrachtet verschiedene Ansätze zur Lösung des Problems und bestimmt die Laufzeiten im ungünstigsten Fall und die mittlere Laufzeit. Für den letzteren Fall greift sie auf Resultate von Rainer Kemp zurück.

Abschließend behandelt sie auch den Fall von Klammern, die nicht zwischen öffnenden und schließenden Versionen unterscheiden. Dieser Fall liegt den kontextfreien Sprachen wesentlich näher. Die Lösung des Problems gelingt in diesem Fall (für eine einzige Klammersorte) durch die Einführung einer assoziativen Operation zwischen Intervallpaaren. Die Arbeit wurde von Elmar Schömer betreut.

157. Müller, Birgit: Ausnutzung funktionaler Eigenschaften von Operationen zur Erhöhung der Verfügbarkeit von Rechnern. Diplomarbeit am FI der US.

Zusammenfassung: Die Aufgabenstellung: Ein Computer der nicht ohne Weiters austauschbar ist, da er an einem schwer zugänglich Ort im Einsatz ist, erleidet einen Fehler in seiner Logik. Es stellt sich die Frage, wie erkennt man Fehlfunktionen und wie kann man sie möglicherweise umgehen. Ein Beispiel: Das Multiplizierwerk liefert für die Eingabe a,b ein falsches Resultat. Der Fehler wir z.B. durch eine parallel laufende homomorphe Arithmetik erkannt. Ein Lösung des Problems könnte darin bestehen, ein zu wählen und den Ausdruck zu berechnen, für den die Arithmetik ein korrektes Resultat liefert. Die Arbeit behandelt für spezielle Fehlermodelle, die skizzierte Fragestellung.

Die Aufgabenstellung war von mir. Die Betreuung hat Rainer Kolla nach kurzer Zeit vollständig übernommen.

158. Muth, Wolfgang: Vergleich der Comskee-Strings und –Wörterbücher mit in C++ nachgebildeten Datentypen. Diplomarbeit am FI der US.

Zusammenfassung: Im Rahmen des SFB 100, Elektronische Spracherkennung hatte wir die Programmiersprache COMSKEE entwickelt, für einige Datentype und die damit verbunden Operationen charakteristisch waren. Es gab zu dieser Zeit keine Programmiersprache, die in gleicher Weise an den Bedürfnissen einer anspruchsvollen Textverarbeitung orientiert war. Zentral waren die Datentypen string und dictionary (=wörterbuch) und die damit verbunden Operationen, die sehr effizient und ohne Größenbeschränkungen realisiert wurden. Als die Sprachen C und C++ aufkamen stellte sich natürlich die Frage, ob wir aufgrund der universellen Verbreitung dieser Sprachen COMSKEE durch diese Sprachen ersetzen sollten oder ob wir C++ als Basis verwenden sollten, um COMSKEE darauf aufzusetzen. Der Beantwortung dieser Frage ist diese Diplomarbeit gewidmet. Die in der Arbeit vorgenommene Implementierung erwies, dass diese beiden Datentypen und die darauf aufbauenden Operationen vergleichbar effizient liefen, wie in COMSKEE. Die Arbeit setzt sich auch mit der den Möglichkeiten des Systems LEDA auseinander, das wenige Jahre zuvor von Kurt Mehlhorn begonnen wurde.

Die in der Arbeit implementierten Datentypen wurden auch in CADIC verwendet.

Die Arbeit wurde von Paul Molitor betreut.

159. Mechenbir, Dirk: Kompaktieren von Layouts. Diplomarbeit am FI der US.

Zusammenfassung: Die Arbeit gehört in eine Serie von Arbeiten, von denen einige in der Reihe dieser Diplomarbeiten bereits besprochen wurden. Hier geht es um das Layout eines Chips auf Basis eines fest vorgegebenen Randes und des logisch-topologischen Entwurfes des Schaltnetzes durch einen Ausdruck in CADIC. Zunächst wird ein planares Layout erzeugt, dessen Knoten so verteilt sind, dass die in einer min-max gemessene Größe minimal wird. Danach werden die Knoten des Netzes durch Bausteine ersetzt. Es wird getestet, ob die Planarität erhalten wurde und im positiven Fall wird der für das Layout vorgegebene Rand iterativ so weit zusammengezogen, das das Layout die Planaritätsforderung erfüllt. Das auch unter der Nebenbedingung, dass die Kanten des Netzes eine vorgegebene Dicke haben. Es kommen weiter noch einige Feinheiten hinzu, die ich hier nicht erwähnt habe. Das Resultat ist ein effizienter Algorithmus, den Dirk Mechenbir auch implementiert hat.

Die Arbeit wurde von Hans-Georg Osthof betreut. Es haben auch weitere Kollegen Mechenbirs durch Diskussionen beitragen müssen. Mechenbir hofft aber, wie er in der Einleitung seiner Arbeit schreibt, dass diese auf seinen Kopf kein Preisgeld ausgesetzt haben.

160. König, Joachim: Leitungsverfeinerung in CADIC. Diplomarbeit am FI der US.

Zusammenfassung: Diese behandelt eine Erweiterung von CADIC, welche die Möglichkeit betrifft auch die Verbindungsleitungen rekursiv zu verfeinern. Hierzu führen wir parametrisierte Typen ein, die sich zusammen mit der Rekursiven Verfeinerung von Komponenten des Layouts mit Verfeinern. Das bedingt einige Änderungen in den bereits oben diskutierten Layoutverfahren. Joachim König berichtet über seine Arbeiten zur Erweiterung der Spezifikation von CADIC und über die dadurch notwendigen Ergänzungen der zur Interpretation von CADIC – Spezifikationen gehörigen Software.