Highlights aus der Informatik

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!

Highlights aus der Informatik — ein Überblick.- Automatische Zusammenstellung von Fahrgemeinschaften.- 2.1 Vorbemerkung.- 2.2 Formalismen.- 2.3 Motivation und Systemaufbau.- 2.4 Verkehrswissen und Straßengraphen.- 2.5 Weg- und Umwegsuche.- 2.6 Zuordnungen.- 2.7 Ausblick.- Gewußt oder gesucht: Spieltheorie für Menschen und für Maschinen.- 3.1 Spiele als Samen der Wissenschaft.- 3.2 Macht oder Ohnmacht roher Rechenleistung.- 3.3 Mensch und Maschine als Informationsverarbeiter.- 3.4 Schachtheorie für Menschen.- 3.5 Das Shannon-Turing Rezept für Computer als Spieler.- 3.6 Theorien und ihre Ausführenden am Werk.- 3.7 Der Plan als Kern menschlicher Strategie.- 3.8 Das Wettrennen Mensch gegen Maschine.- 3.9… und die Moral von der Geschieht?.- Ein effizienter verteilter Algorithmus zur Spielbaumsuche.- 4.1 Schach: eine Herausforderung für die Informatik.- 4.2 Spielbaumsuchverfahren.- 4.3 Zugzwangs parallele Spielbaumsuche.- 4.4 Effizienzbetrachtungen.- 4.5 Schlußfolgerungen.- Knight moves — was macht der Springer allein auf dem Schachbrett?.- 5.1 Schach und Informatik.- 5.2 Knight moves - die Faszination des Springers.- 5.3 Ein historischer Rückblick.- 5.4 Springerkreise und der Fehler im Pentium Dividierer.- 5.5 OBDD-Techniken zur Lösung endlicher Probleme.- 5.6 Die Anzahl der Springerkreise.- 5.7 Schlußfolgerungen.- Molekulare Bioinformatik.- 6.1 Molekularbiologische Voraussetzungen.- 6.2 Forschungsgebiete.- 6.3 Sequenzalignment.- 6.4 Vorhersage von Proteinstrukturen.- 6.5 Analyse molekularer Wechselwirkungen.- 6.6 Analyse metabolischer Netzwerke.- 6.7 Diskussion.- LEDA — Eine Plattform für kombinatorisches und geometrisches Rechnen.- 7.1 LEDA — Überblick und Beispiele.- 7.2 Größe der Bibliothek.- 7.3 Implementierung.- 7.4 Programmüberprüfung.-7.5 Schlußfolgerungen.- Hierarchischer Entwurf komplexer Systeme.- 8.1 Die Elemente der Sprache 2dL.- 8.2 Interpretation von Netzen.- 8.3 Operationen auf der Menge der Netze.- 8.4 Interpretationen als Funktoren.- 8.5 Erzeugendensysteme.- 8.6 Der Verfeinerungsfunktor.- 8.7 Einige Bemerkungen über das System CADIC.- 8.8 Komplexitätsbetrachtungen.- Zeit und Raum in Rechnernetzen.- 9.1 Die Bedeutung Verteilter Systeme.- 9.2 Lokales und globales Wissen.- 9.3 Kommunikationsverzögerungen.- 9.4 Unzuverlässige Komponenten und Kommunikation.- 9.5 Consensus.- 9.6 Byzantinisches Agreement in synchronen Systemen.- 9.7 Consensus in asynchronen Systemen.- 9.8 Zeit-Synchronisation.- Kommunikation in parallelen Rechnernetzen.- 10.1 Das Routingproblem.- 10.2 Netzwerke.- 10.3 Store-and-Forward-Routing.- 10.4 Wormhole-Routing.- Parallelisierung aller APL-Operationen.- 11.1 Ziele.- 11.2 Zielmaschine.- 11.3 APL-Werte.- 11.4 Speicherung von APL-Werten.- 11.5 Routing.- 11.6 Reshape.- 11.7 Parallel Prefix-Berechnung.- 11.8 Sortieren.- 11.9 Zusammenfassung.- Suchen und Konstruieren durch Verdoppeln.- 12.1 Lernen Boolescher Funktionen.- 12.2 Aufspannende Bäume kleiner Kreuzungszahl.- 12.3 Kleinster umschließender Kreis.- Mathematik des Software-Engineering.- 13.1 Zur wissenschaftlichen Fundierung des Software-Engineering.- 13.2 Mathematische Modelle von Systemen und Systemansichten.- 13.3 Beschreibungsformalismen im Software-Engineering.- 13.4 Entwicklungsmethode.- 13.5 Schlußfolgerungen.- Zufalls-Primzahlen und Kryptographie.- 14.1 Ringe und Körper.- 14.2 Primzahlen.- 14.3 Zufall.- 14.4 Geheimnisse.- 14.5 Anmerkungen.- Theoretische Aspekte neuronaler Netzwerke.- 15.1 Neuronale Netzwerke.- 15.2 Binäre neuronale Schaltkreise.- 15.3 Analoge neuronale Schaltkreise.- 15.4 Lernalgorithmen.-15.5 Zusammenfassung.- Interaktive Beweise.- 16.1 Was ist ein Beweis?.- 16.2 Die Klasse IP.- 16.3 Graphenisomorphie.- 16.4 Zero-Knowledge.- 16.5 Bit Commitment.- 16.6 Schlußbemerkungen.- Wie man Beweise verifiziert, ohne sie zu lesen.- 17.1 Probabilistisch verifizierbare Beweise.- 17.2 Das Resultat NP = PCP(log n,1).- 17.3 Ideen zum Beweis.- 17.4 Approximationsprobleme.- 17.5 APX-schwere Probleme.- 17.6 Jenseits von APX.- 17.7 Das Cliquenproblem.- Die Autoren.