Ingo Wegener - Böcker

This collection of articles is published in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, "Numbers and Combinations", "Information Theory" (channels and networks, combinatorial and algebraic coding, cryptology, with the related fields data compression, entropy theory, symbolic dynamics, probability and statistics), and "Complexity". Special attention was paid to the interplay between the fields. Surveys on topics of current interest are included as well as new research results. The book features surveys on combinatorics about topics such as intersection theorems, which are not yet covered in textbooks, several contributions by leading experts in data compression, and relations to natural sciences are discussed.

Numbers, Information and Complexity is a collection of about 50 articles in honour of Rudolf Ahlswede. His main areas of research are represented in the three sections, 'Numbers and Combinations', 'Information Theory (Channels and Networks, Combinatorial and Algebraic Coding, Cryptology, with the related fields Data Compression, Entropy Theory, Symbolic Dynamics, Probability and Statistics)', and 'Complexity'. Special attention was paid to the interplay between the fields. Surveys on topics of current interest are included as well as new research results. The book features surveys on Combinatorics about topics such as intersection theorems, which are not yet covered in textbooks, several contributions by leading experts in data compression, and relations to Natural Sciences are discussed.

In den vergangenen drei Jahrzehnten findet man sowohl in theo­ retisch ausgerichteten als auch in anwendungsorientierten Zeit­ schriften in zunehmendem Maße Beiträge zum Thema "Suchen". Dabei ist auffallend, daß sehr verschiedenartige Probleme als Suchpro­ bleme klassifiziert werden und daß Forscher der verschiedenen Fach­ richtungen häufig sehr wenig über Ergebnisse, die in ihnen nicht vertrauten Gebieten erzielt wurden, informiert sind. Mit diesem Buch wird ein Versuch unternommen, das umfangreiche Material so darzustellen, daß dem Leser ein schneller Einstieg in den Fragenkreis und ein möglichst umfassender Uberblick ermöglicht wird. Es war unser Ziel, die wesentlichen Arbeiten auf dem Gebiet nach neuestem Stand zu behandeln, aber wir erheben keinen Anspruch auf Vollständigkeit in irgendeinem Sinne, da schon der Rahmen dieses Buches einem solchen Verlangen nicht gerecht werden kann. Bei einigen Arbeiten, die es an sich verdient hätten, ausführlich dargestellt zu werden, haben wir uns deshalb auf die Angabe ihrer Ergebnisse beschränkt. Der interessierte Forscher wird so in den Stand versetzt, sich seinen Weg durch die Literatur selbst zu bahnen. Das Buch dürfte für den Experten als Nachschlagewerk nütz­ lich sein. Aber unser Hauptanliegen ist es, jedem Leser mit der Bereit­ schaft und der Fähigkeit zu abstraktem, formalen Denken einen Zu­ gang zu den grundlegenden Ideen, Methoden und Resultaten des Ge­ bietes zu ermöglichen, die noch nicht in Büchern erschienen sind, aber von ihrer Bedeutung her eine weitere Verbreitung verdienen.

Die Theoretische Informatik ist älter als die Praktische, Angewandte oder Techni­ sche Informatik. Daher ist sie als wissenschaftliche Disziplin bereits weiter ausgebaut als andere Bereiche der Informatik, und ihre Ergebnisse sind schwerer zugänglich, da sie auf ein größeres und tieferes Fundament aufbauen. Stark verästelte Theorien tendieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einführung in die Theoretische Informatik begegnen wir dieser Gefahr, indem wir die Orientierung moderner Theorien an den Anwendun­ gen in den Mittelpunkt stellen. Schon Novalis (1772~ 1801) hat darauf hingewiesen, daß die Theorie häufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so käme sie nie zustande. " Nicht immer sind die Anwendungen von Ergebnissen der Theoretischen Informatik so direkt zu sehen wie die Anwendungen anderer Zweige der Informatik. Dies gilt insbesondere für negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, daß es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, muß die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmöglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exi­ stenzaussagen oder Algorithmen mit exponentieller oder noch größerer Laufzeit sind häufig praktisch wertlos. Das Neue an der vorliegenden Einführung in die Theore­ tische Informatik ist die konsequent algorithmenorientierte Sichtweise (zum didak­ tischen Hintergrund siehe Wegener (1992)). Stets wurde bei positiven Resultaten eine Umsetzung in praktisch und theoretisch effizienteAlgorithmen angestrebt.

Das "Kompendium Theoretische Informatik - eine Ideensammlung" erganzt das Lehrbuch "Theoretische Informatik - eine algorithmenorientierte Einfuhrung" vom gleichen Autor. An Stelle von formalen Beweisen werden die wesentlichen Ideen herausgearbeitet und vorgestellt. Die Vertiefung und Auffrischung von Kenntnissen in Theoretischer Informatik wird unterstutzt. Die Ideensammlung wird erganzt durch Ubungsaufgaben mit Losungen und Losungsmethoden sowie Testfragen mit knappen Antworten.

Der erfolgreiche Einsatz von Rechnern bei der Lösung von Problemen in fast allen Lebensbereichen beruht u.a. auf der technologischen Entwicklung, die zu schnelle­ ren Rechnern mit größerem Speicher führte, auf der größeren Benutzerfreundlich­ keit der Rechner und auf effizienteren Algorithmen zur Lösung der betrachteten Probleme. Dieses Buch befaßt sich mit dem Entwurf effizienter Algorithmen für grundlegende Probleme, die häufig als Teilprobleme in komplexeren Problemen auftreten. Während auf der unteren Ebene der Hardware von Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon immer mit einem hohen Grad an Parallelität gearbeitet wurde, konnte auf höherer Ebene lange Zeit nur sequentiell gerechnet werden. Dies ändert sich nun durch die Entwicklung von Rechnern mit immer mehr Prozessoren. Das Buch legt daher einen Schwerpunkt auf Algorithmen, die gleich­ zeitig bezüglich paralleler Rechenzeit und Hardwaregröße (bei Hardwarelösungen) bzw. bezüglich paralleler Rechenzeit, Zahl der benutzten Prozessoren und Spei­ cherplatz (bei Softwarelösungen) effizient sind. Es werden effiziente Algorithmen für den Entwurf optimaler P LA's diskutiert. Danach werden die grundlegenden arithmetischen Funktionen Addition, Subtrak­ tion, Multiplikation und Division, die symmetrischen Funktionen, die auch als Zählfunktionen bezeichnet werden können, und Speicherzugriffsfunktionen behan­ delt. In diesem Teil des Buches werden vor allem Hardwarelösungen präsentiert. Für das Rechnen mit Matrizen, einfache Probleme auf Graphen, Sortierprobleme und Probleme der Elementaren Zahlentheorie werden effiziente Softwarelösungen vorgestellt. Das Buch enthält außerdem allgemeine Methoden der automatischen Parallelisierung sequentieller Algorithmen,Reduktionskonzepte zum Vergleich der Komplexität der behandelten Probleme und effiziente Simulationen zwischen den benutzten Rechenmodellen.

Die Starthilfen erleichtern den Übergang vom Abitur ins Studium. Für die Informatik stellt sich dabei die Frage: Wie hilft man beim Einstieg in dieses Fach, über das - etwa im Gegensatz zu Mathematik und Physik - vor allem bei Schülern und Schülerinnen oftmals falsche Vorstellungen herrschen? Die Autoren der "Starthilfe Informatik" wählen den Weg, dem Leser zunächst die zentralen Begriffe "Algorithmus" und "Datenstrukturen" bzgl. Darstellungsformen, Effizienz und Programmiermethodik näherzubringen. Eine Einführung in die objektorientierte Softwareentwicklung und ein Überblick über Kerngebiete der Praktischen Informatik runden den Band ab. Mit diesem Wissen sollte der inhaltliche Einstieg ins Informatikstudium problemlos gelingen. Das Buch steht im Rahmen des Projektes http://InterDoc.OFFIS.Uni-Oldenburg.de>InterDoc online zur Verfügung.

Die Komplexitätstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nützliche Ergebnisse sind schwer vermittelbar, da der Weg zu Ergebnissen für konkrete Probleme lang und beschwerlich ist. Während die NP-Vollständigkeitstheorie die gesamte Informatik beeinflußt hat, werden die neueren Ergebnisse in der Ausbildung an den Rand gedrängt. Dieses Lehrbuch trifft eine Auswahl unter den Ergebnissen, so dass die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt rückt.

Complexity theory is the theory of determining the necessary resources for the solution of algorithmic problems and, therefore, the limits of what is possible with the available resources. An understanding of these limits prevents the search for non-existing efficient algorithms. This textbook considers randomization as a key concept and emphasizes the interplay between theory and practice:New branches of complexity theory continue to arise in response to new algorithmic concepts, and its results - such as the theory of NP-completeness - have influenced the development of all areas of computer science.The topics selected have implications for concrete applications, and the significance of complexity theory for today's computer science is stressed throughout.

The two-volume set LNCS 4051 and LNCS 4052 constitutes the refereed proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, held in Venice, Italy, July 2006. In all, these volumes present more 100 papers and lectures. Volume I (4051) presents 61 revised full papers together with 1 invited lecture, focusing on algorithms, automata, complexity and games, on topics including graph theory, quantum computing, and more.

The two-volume set LNCS 4051 and LNCS 4052 constitutes the refereed proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, held in Venice, Italy, July 2006. In all, these volumes present more 100 papers and lectures. Volume II (4052) presents 2 invited papers and 2 additional conference tracks with 24 papers each, focusing on algorithms, automata, complexity and games as well as on security and cryptography foundation.

The 30 coherently written chapters by leading researchers presented in this anthology are devoted to basic results achieved in computational intelligence since 1997. The book provides complete coverage of the core issues in the field, especially in fuzzy logic and control as well as for evolutionary optimization algorithms including genetic programming, in a comprehensive and systematic way. Theoretical and methodological investigations are complemented by prototypic applications for design and management tasks in electrical engineering, mechanical engineering, and chemical engineering.This book will become a valuable source of reference for researchers active in computational intelligence. Advanced students and professionals interested in learning about and applying advanced techniques of computational intelligence will appreciate the book as a useful guide enhanced by numerous examples and applications in a variety of fields.

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!

Complexity theory is the theory of determining the necessary resources for the solution of algorithmic problems and, therefore, the limits of what is possible with the available resources. An understanding of these limits prevents the search for non-existing efficient algorithms. This textbook considers randomization as a key concept and emphasizes the interplay between theory and practice:New branches of complexity theory continue to arise in response to new algorithmic concepts, and its results - such as the theory of NP-completeness - have influenced the development of all areas of computer science.The topics selected have implications for concrete applications, and the significance of complexity theory for today's computer science is stressed throughout.

The 30 coherently written chapters by leading researchers presented in this anthology are devoted to basic results achieved in computational intelligence since 1997. The book provides complete coverage of the core issues in the field, especially in fuzzy logic and control as well as for evolutionary optimization algorithms including genetic programming, in a comprehensive and systematic way. Theoretical and methodological investigations are complemented by prototypic applications for design and management tasks in electrical engineering, mechanical engineering, and chemical engineering.This book will become a valuable source of reference for researchers active in computational intelligence. Advanced students and professionals interested in learning about and applying advanced techniques of computational intelligence will appreciate the book as a useful guide enhanced by numerous examples and applications in a variety of fields.

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!