Skip to main content
main-content

Über dieses Buch

Dieser Band enthält die Beiträge einer Ringvorlesung Highlights aus der Informatik an der Universität Dortmund, in der Wissenschaftler, die durch ihre Forschung und didaktischen Fähigkeiten ausgewiesen sind, Glanzlichter aus der neueren Informatikforschung aufbereiteten und sie so Studenten und interessierten Laien zugänglich gemacht haben. Dabei wird das ganze Spektrum von tiefliegenden theoretischen Ergebnissen über anwendungsorientierte Entwicklungen bis zur überraschenden Lösung altbekannter kombinatorischer Probleme behandelt. Die Autoren zeigen kenntnisreich und bisweilen humorvoll, wie aufregend aktuelle Forschung sein kann!

Inhaltsverzeichnis

Frontmatter

Highlights aus der Informatik — ein Überblick

Zusammenfassung
Nach einer Erläuterung der Ziele der Aufsatzsammlung sollen Kurzbeschreibungen der Aufsätze Appetit auf das in sechzehn Gängen präsentierte Menü „Highlights aus der Informatik“ machen.
Ingo Wegener

Automatische Zusammenstellung von Fahrgemeinschaften

Zusammenfassung
Es fahren zu viele Autos auf den Straßen. Oft werden sie nur als Transportmittel zur Arbeitsstätte eingesetzt, wo sie unproduktiv den ganzen Tag herumstehen und anderweitig nutzbare Flächen belegen. Fahrgemeinschaften (abgekürzt FGMs), die aus drei oder vier Personen bestehen, könnten eine deutliche Entlastung bewirken.
Volker Claus, Friedhelm Buchholz

Gewußt oder gesucht: Spieltheorie für Menschen und für Maschinen

Zusammenfassung
Was können wir vom Computer als Spieler lernen?
Diese bewußt zweideutige Frage soll exostisches Randgebeit der Informatik einführen: die Kunst, Computer zum Spielen zu bringen. Bevor man untersucht, wie diese Leistung zu erbringen ist, taucht aber die Frage „war-um denn?“ auf. Eine Antwort darauf ist zugegebenermaßen dieselbe, die das Erklimmen der Eiger Nordwand erklärt: „Um zu zeigen, daß man es kann.“
Wir suchen in diesem Artikel nach einer befriedigenderen Antwort. Wir versuchen anhand einiger Episoden aus der Entwicklung des Computer-schachs zu interpretieren, was erreicht worden ist. Wir vergleichen dies mit der Leistung menschlicher Experten, versuchen einige Unterschiede zu verstehen und kommen zum Schluß nochmals auf die verzwickte Frage zurück: Was hat die Wissenschaft gelernt aus einem Experiment, das seit der Frühzeit der Computer vor fast einem halben Jahrhundert etwas chaotisch, aber mit großer Hingabe von Hunderten von faszinierten Bastlern und Wissenschaftlern geführt worden ist?
Jürg Nievergelt

Ein effizienter verteilter Algorithmus zur Spielbaumsuche

Zusammenfassung
Die menschliche Intelligenz spiegelt sich auch in der Fähigkeit wider, Entscheidungen unter Berücksichtigung zukünftiger Entwicklungen zu treffen. Daher werden in der Informatik seit vielen Jahren Algorithmen untersucht, die eine solche Vorausschau in die Zukunft ermöglichen und dann aufgrund von Abschätzungen der Ergebnisse der einzelnen Handlungsalternativen eine Alternative auswählen. Strategische Spiele erfordern eine derartige Leistung, wenn der Ausgang einer Folge von eigenen Handlungen unter Berücksichtigung der Interventionen eines Gegners abgeschätzt werden muß. Auch wegen ihrer klaren Definitionen bieten sich daher immer wieder Spiele, wie z.B. Schach, als Testumgebung für solche Algorithmen an. Den Blick in die Zukunft ermöglicht dabei die Spielbaumsuche.
Rainer Feldmann, Burkhard Monien, Peter Mysliwietz

Knight moves — was macht der Springer allein auf dem Schachbrett?

Zusammenfassung
Springerkreise sind Zugfolgen des Springers auf dem Schachbrett, mit denen er jedes Feld genau einmal erreicht und zum Ausgangsfeld zurückkehrt. Sie faszinieren seit über 400 Jahren auch solche Menschen, die sich nicht hauptsächlich mit Schach, Mathematik oder Informatik befassen. Nach einem historischen Rückblick wird beschrieben, wie es nun gelungen ist, die exakte Zahl der Springerkreise zu bestimmen. Wichtiger als die Zahl ist die Methode ihrer Berechnung. Es werden für die Hardwareverifikation entworfene Datenstrukturen eingesetzt. Damit wird gezeigt, daß diese Datenstrukturen die Lösung endlicher Probleme aus sehr unterschiedlichen Gebieten unterstützen.
Martin Löbbing, Ingo Wegener

Molekulare Bioinformatik

Eine interdisziplinäre Herausforderung
Zusammenfassung
Der rapide anwachsende Umfang an Daten und Erkenntnissen in der Molekularbiologie, der durch die vor knapp zehn Jahren begonnenen Genomsequenzierungsprojekte sowie die Fortschritte bei der experimentellen molekularen Strukturaufklärung erzeugt wird, stellt eine beträchtliche Herausforderung auch an die Informatik dar. Schon bei der Genomsequenzierung selbst fallen wichtige Informatikprobleme an. Die größte Herausforderung besteht jedoch in der Unterstützung der Interpretation genomischer Information. Hier gilt es, außerordentlich umfangreiche und in hohem Maße unstrukturierte Daten zu analysieren und aus ihnen biologische Erkenntnisse abzuleiten. Die Daten liegen zunächst in der Form von Sequenzen, d. h. Strings vor. Nach den ersten Interpretationsschritten sind jedoch auch dreidimensionale Strukturdaten von Biomolekülen zu analysieren. Schließlich spielen die Wechselwirkungen zwischen Biomolekülen eine zentrale Rolle, die zu Reaktionsketten und -netzwerken zusammengefaßt den Metabolismus lebender Organismen ausmachen. Informatiker werden zur Bewältigung dieser Herausforderung nur dann wesentlich beitragen können, wenn sie selbst sich dabei engagieren, ihre Methoden in die molekularbiologische Anwendung einzubringen, und damit eigene Kompetenz in diesem hochaktuellen Anwendungsgebiet erwerben. Das bedeutet auch, neue Probleme, Methoden und Validierungsverfahren zu entwickeln, die auf diese Anwendung zugeschnitten sind.
Thomas Lengauer

LEDA — Eine Plattform für kombinatorisches und geometrisches Rechnen

Zusammenfassung
LEDA ist eine Bibliothek von Sofwarekomponenten für kombinatorische und geometrische Probleme. Die wichtigsten Eigenschaften der Bibliothek sind die umfangreiche Sammlung von effizienten Datentypen und Algorithmen, deren präzise und dennoch lesbare Spezifikation, und ihre leichte und elegante Benutzbarkeit. Auf diese Weise stellt LEDA eine Plattform für kombinatorisches und geometrisches Rechnen dar, die den Schritt vom Algorithmus zum ausführbaren Programm erheblich erleichtert. Damit macht LEDA die theoretischen Resultate über effiziente Datenstrukturen und Algorithmen auch für Sofwareentwickler nutzbar, die keine Experten auf diesem Gebiet sind.
Kurt Mehlhorn, Stefan Näher

Hierarchischer Entwurf komplexer Systeme

Zusammenfassung
Der Aufbau von Rechnern wird in der Regel durch Blockdiagramme erläutert und für einzelne Blöcke dieser Diagramme wie z.B. Prozessoren geschieht das auf gleiche Weise. So tut man dies in schrittweiser Verfeinerung, bis man an die Grenze des Interesses des Lesers stößt. Diese Grenze mag bei den Gattern liegen, sie kann aber auch darüber oder darunter liegen. Beim Chipentwurf interessiert man sich eventuell auch für den Aufbau der Gatter aus Transistoren oder gar für physikalische Eigenschaften der Transistoren.
Günter Hotz, Armin Reichert

Zeit und Raum in Rechnernetzen

Zusammenfassung
Verteilte Rechnersysteme erweisen sich als eine attraktive Architektur mit einer Reihe von Vorteilen. Vor allem ist hier zu nennen die lokale Verfügbarkeit und die Möglichkeit des dezentralen Managements, so daß bei Ausfall einzelner Komponenten nicht zwangsläufig das gesamte System zum Stillstand kommen muß. Andererseits erzeugt gerade diese räumliche Trennung eine neuartige Synchronisationsproblematik. Wir diskutieren exemplarisch zwei Prototypprobleme: Konsistenz bei divergenter lokaler Information — auch Consensus oder das Problem der Byzantinischen Generäle genannt — und die zeitliche Synchronisation der lokalen Uhren in den einzelnen Knoten und gemeinsamer Aktionen. Grundlegend hierfür ist eine präzise Analyse, wie aus lokalem Wissen der einzelnen Komponenten globales Wissen über den Gesamtzustand des Systems gewonnen werden kann, und zwar durch den Austausch von Nachrichten und das Eintreffen oder Nichteintreffen von Ereignissen.
Rüdiger Reischuk

Kommunikation in parallelen Rechnernetzen

Zusammenfassung
Effiziente Kommunikationsmethoden in Netzwerken sind Grundvoraussetzung, um die Leistungsfähigkeit großer paralleler Rechnersysteme auszuschöpfen. Aus diesem Grund wurden und werden erhebliche Forschungsund Entwicklungsanstrengungen unternommen, derartige Kommunikationsmechanismen, sogenannte Router, zu analysieren und herzustellen. In diesem Aufsatz beschreiben wir die Grundideen der Beiträge der theoretischen, algorithmisch orientierten Forschung zur Entwicklung solcher Kommunikationsmethoden.
Friedhelm Meyer auf der Heide, Rolf Wanka

Parallelisierung aller APL-Operationen

Zusammenfassung
Die Sprache APL basiert auf einem äußerst eleganten Kalkül für Vektoren, Matrizen und Tensoren. APL-Operationen kommen inzwischen in vielen modernen Programmiersprachen vor. Ihre Parallelisierung ist daher nicht nur für Benutzer von APL von Interesse. Wir zeigen, daß sich alle APL-Operationen effizient parallelisieren lassen. Die wesentlichen Werkzeuge beim Beweis sind
1.
Zahlensysteme mit gemischter Basis für die Berechnung von Speicheradressen von Tensorelementen und
 
2.
ein auf Smoothing basierender Routing-Algorithmus.
 
Wolfgang J. Paul, Jürgen Sauermann

Suchen und Konstruieren durch Verdoppeln

Zusammenfassung
Es sollen hier Resultate aus drei verschiedenen Gebieten bewiesen werden. Ein Verfahren zum Lernen Boolescher Funktionen, wobei man möglichst wenige Fehler macht [7]. Eine Konstruktion für eine Schranke aus der kombinatorischen Geometrie [4] mit algorithmischen Anwendungen (siehe auch [13]). Und ein Algorithmus zur Optimierung X. Aus der Vielfalt der Ergebnisse ergibt sich bereits, daß weniger das Ziel als vielmehr der Weg dorthin unser zentrales Anliegen ist: Eine Beweismethode, die man als „iteratives Umgewichten“ oder „Suchen bzw. Konstruktion durch Verdoppeln“ bezeichnen kann. Dabei beginnen wir mit einer Menge Mo und ziehen daraus eine Teilmenge T0. Durch Verdoppeln der Elemente aus T0 erhalten wir eine Menge M1 (tatsächlich haben hier die Elemente nun Vielfachheiten). Dann ziehen wir eine Teilmenge T1 aus M1, verdoppeln alle Elemente in M1, die in T1 vorkommen, und erhalten dadurch M2, usw. Wie wir die Teilmengen bekommen, ergibt sich erst in den konkreten Beispielen. Mit dem Verdoppeln verfolgen wir unterschiedliche Ziele. In einem Fall verringert hohe Vielfachheit die Chance, in einer der Mengen Ti aufzutauchen. Das heißt, kein Element wird viel öfter als andere in den Iterationen gezogen werden. In einer anderen Anwendung hat M gute und schlechte Elemente—welche gut und welche schlecht sind, ist uns nicht bekannt. Es gelingt uns aber immer, Teilmengen Ti zu ziehen, die mindestens ein gutes Element haben, wir wissen aber nicht, welches. Verdoppeln erhöht die Chance, in späteren Ti’s aufzutreten. Da aber immer mindestens ein gutes Element verdoppelt wird, gewinnen diese schnell die Überhand und können dadurch identifiziert werden. Diese Skizze der Idee wird vielleicht erst im Rückblick verständlich, deutet aber schon den evolutionären Charakter der Verfahren an (Brönnimann und Goodrich nennen dies „algorithmischen Darwinismus“ [1]). In jedem Fall geht es uns aber nur um Methoden, in denen die Intuition auch durch Beweise untermauert werden kann.
Emo Welzl

Mathematik des Software-Engineering

Zusammenfassung
Software-Engineering umfaßt technische wie organisatorische Aspekte. Aus technischer Sicht arbeiten wir beim Software-Engineering mit einer Entwicklungsmethode und Beschreibungsformalismen, mit Modellierungs- und Implementierungstechniken. Die Entwicklung eines Softwaresystems ist als Entwicklungsprozeß organisiert und wird durch CASE- Werkzeuge unterstützt. Wir zeigen im folgenden, wie geeignete Mathematik das Software-Engineering auf eine wissenschaftliche Grundlage stellen kann. Dadurch werden ein gründlicheres Verständnis für die Disziplin und auch eine mächtigere zielgerichtetere Werkzeugunterstützung für den Entwicklungsprozeß möglich. Um zu einer angemessenen mathematischen Fundierung zu gelangen, muß der wirtschaftliche und technische Nutzen mathematischer Konzepte im Bereich Software-Engineering klar identifiziert werden. Dazu ist es erforderlich, die Rolle von Mathematik und Logik im Software-Engineering sorgfältig zu analysieren. Wir beschreiben, wie Methoden des Software-Engineering durch die Mathematik fundiert werden können. Wir erläutern den Nutzen einer solchen mathematischen Grundlage. Dieser Nutzen geht weit über die sogenannten formalen Methoden für die Spezifikation und Verifikation von Software hinaus.
Manfred Broy

Zufalls-Primzahlen und Kryptographie

Zusammenfassung
Dieser Vortrag handelt von algorithmischen Problemen der elementaren Zahlentheorie und einer Revolution der Kryptographie in den siebziger Jahren. Es werden kaum Mathematik- und überhaupt keine Informatik-Kenntnisse vorausgesetzt.
Volker Strassen

Theoretische Aspekte neuronaler Netzwerke

Zusammenfassung
Wir betrachten neuronale Netzwerke mit diskreten oder analogen Gatterfunktionen. Selbst die Berechnungskraft relativ kleiner neuronaler Netzwerke beschränkter Tiefe ist, besonders in Hinsicht auf arithmetische Operationen, immens. Aber gerade diese Stärke ist auch ein Grund für die Schwierigkeit des Lernens von und mit „einfachen“ neuronalen Netzwerken.
Georg Schnitger

Wie man Beweise führen kann: interaktiv und ohne den Beweis zu Verraten

Zusammenfassung
Der Vorgang des Beweisens kann in einer interaktiven Weise zwischen zwei Parteien, dem Beweiser und dem Verifizierer, stattfinden. Durch das Verwenden von Zufallszahlen wird es möglich gemacht, daß derartige interaktive Beweise kürzer sein können als konventionelle. Ferner ist es möglich, daß der Verifizierer vollständig von der Tatsache überzeugt wird, daß der Be-weiser den Beweis (das kann zum Beispiel ein Passwort sein) kennt, ohne daß aus der Kommunikation zwischen Beweiser und Verifizierer auf den Beweis rückgeschlossen werden kann. Solche interaktiven Zero-Knowledge Beweise spielen eine wichtige Rolle in verschiedenen kryptographischen Anwendungen.
Uwe Schöning

Wie man Beweise verifiziert, ohne sie zu lesen

Zusammenfassung
Ein Traum eines jeden Studenten, Doktoranden und Professors: Die Richtigkeit eines komplizierten Beweises zu verifizieren, ohne ihn mühselig Zeile für Zeile zu lesen und zu verstehen.
Hans Jürgen Prömel, Angelika Steger

Backmatter

Weitere Informationen