Bücher der Reihe Leitfaden Der Informatik

Die theoretische Informatik ist älter als die praktische, angewandte oder technische 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 ten­ dieren 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, dass 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, dass es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, muss 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. Exis­ tenzaussagen 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 (1995)). Stets wurde bei positiven Resultaten eine Umsetzung in praktisch und theoretisch effizienteAlgorithmen angestrebt.

Der Begriff der formalen Sprache ist grundlegend für viele Bereiche der angewandten und theoretischen Informatik, sei es im Bereich der Programmiersprachen, im Compilerbau oder auch in Datenmanipulations- und Abfragesprachen oder Datenbanktechnologie. Ausgehend von motivierenden Beispielen werden die klassischen analysierenden und erzeugenden Systeme formaler Sprachen untersucht: Der Hierarchie der Automaten, von endlichen Automaten über Kellerautomaten bis hin zu Turing-Maschinen, wird die Hierarchie der Chomsky-Grammatiken gegenübergestellt, wobei die einzelnen Sprachklassen diskutiert und klar gegeneinander abgegrenzt werden. Schließlich erfolgt die Darstellung grundlegender Begriffe wie "Algorithmus", "Berechenbarkeit", Entscheidbarkeit", etc. Die Bedeutung dieser Begriffe für die Informatik im allgemeinen und für die Theorie formaler Sprachen im speziellen wird herausgearbeitet. Ziel des Bandes ist es, auf leicht verständliche und dennoch präzise Weise eine Einführung in diese wichtigen Gebiete der Informatik zu geben. Insbesondere soll beim Leser ein Verständnis für viele methodischen Grundlagen - etwa für die Konzepte von Programmiersprachen - entwickelt werden. Das Buch ist im Rahmen des http://medoc.informatik.tu-muenchen.de/deutsch/medoc.html>MeDoc-Projektes in die elektronische Informatik-Bibliothek aufgenommen worden und steht über das Projekt http://InterDoc.OFFIS.Uni-Oldenburg.de>InterDoc weiterhin zur Verfügung.

Als vor fast 40 Jahren ein Entwicklungsteam seiner hohen Direktion das Konzept und Teile einer neuen Rechenanlage vorstellte, machte das Wort vom "Elefanten" die Runde. Dessen ungeachtet machten sich einige Entwick­ ler bereits Gedanken dariiber, wie man ein "Team" von etwa vier solchen Elefanten" zusammenbringen konnte, urn die damals anstehende Aufgabe " einer automatisierten Flugsicherung bewaJtigen zu konnen. Eine Elefantenherde? Mitnichten - schon damals gab es "Konzeptionisten", welche den "Elefanten" der auBeren Dimension nach sehrumpfen sahen. AI­ lerdings gab erst die Technik integrierter Bauteile die Moglichkeit, den Ele­ fanten bzw. Monoprozessor auf einem Chip zu realisieren und ihn damit auf die ihm gemaB Grosse zu reduzieren: Ein Chip als Ausgangspunkt bzw. als Einzeller einer neuen Generation von Automaten-Wesen, die sich aus Tausenden von solchen Einheiten zusammensetzt. Der Vergleieh mit der Darwin'schen Evolution liegt nahe. Die Natur benotigte einige Milliarden von Jahren fUr eine entsprechende Entwieklung vom Einzeller zu hoheren Organismen.

Motivationen fUr da.., Verfassen von Blichern gibt es zweifellos viele. Wodurch aber wird die Wahl eines Thenlas bestimmt? Kenntnisse und Vorlieben spielen sicher­ lich eine Rolle, aber es muB doch noch die lJberzeugung hinzukommen, daB das behandelte Gebiet nicht nur fUr die Autoren von Bedeutung sei. U nd so geht es lIns mit "Parallelverarbeitung". Einzelne Grlinde dafUr sind im Buch aufgefUhrt, kurz gesagt glauben wir, daB sich eine Begegnung mit ihr nicht vermeiden laBt lind daB darliberhinaus zumindest einige ihrer Prinzipien genligend Interesse beanspruchen dlirfen. Daher haben wir eine EinfUhrung verfaBt, die zu einem Einstieg in dieses Gebiet verhelfen soli. Unter dem Aspekt des Erkennens gewisser (einfacher) Musterklassen werden im ersten Teil verschiedene Modelle von Automaten, die unterschiedliche Modi der Parallelverarbeitung reprasentieren, eingefUhrt, lind sie werden mit dem "Referenzmodell" der (sequentiellen) Turingmaschine sowie teilweise untereinan­ der verglichen. 1m zweiten Teil wird dargestellt, welche Bezlige diese Modelle zu Rechnerarchitekturen besitzen. Da es uns darauf ankam, die Konzepte herauszuarbeiten, werden ein Teil des Stoffes informell vorgestellt und "technisch aufwendige" Beweise oft nur skizziert. Perso­ nen mit Grundkenntnissen aus den Bereichen Formale Sprachen, Komplexitats­ theorie und Rechnerarchitektur, wie sie liblicherweise zum Ende des Infonnatik­ Grundstudiums zu erwarten sind, sollte die Lektlire keine Schwierigkeiten bereiten.

tungssystem Access aus dem verbreiteten Standardpaket MS-Of£ice ein benutzerfreundliches Werkzeug fur Ausbildung und Anwen­ dung zur Verfugung.

Methodisch modern und studentenfreundlich wird das Grundwissen der Elektrotechnik vermittelt.Der Leser erhält zahlreiche Hilfen, die den Lernprozess erleichtern. Lernziele, Zusammenfassungen, Beispiele und Übungen mit Lösungen erlauben eine optimale und selbstständige Übungs- und Prüfungsvorbereitung. Darüber hinaus werden die modernen Computerprogramme MATLAB und Multisim systematisch einbezogen.

Erlernen Sie die Grundlagen der Bioinformatik theoretisch fundiert und zugleich anschaulich mit vielen Beispielen.Die Bioinformatik hat in den vergangenen Jahren eine immer höhere Aufmerksamkeit erhalten. Dazu haben viele Großprojekten wie zum Beispiel das Human Genome Project beigetragen. Dieser Trend setzt sich durch immer neue und verfeinerte Ansätze zur Gewinnung und Analyse molekularbiologischer Daten fort.

Mustererkennung bildet die Grundlage für die Lösung verschiedenster Problembereiche in der Informatik. Spracherkennung, Schrifterkennung, Analyse biologischer Sequenzen: mit diesem Lehrbuch gelingt Ihnen der fundierte Einstieg in Theorie und Praxis.

Das Buch führt in die Grundlagen des Protocol Engineerings ein. Es stellt die Funktionsweise von Kommunikationsprotokollen, die Methoden und Techniken für ihre Beschreibung sowie die Phasen der Protokollentwicklung vor. Es werden sowohl praktische als auch theoretische Aspekte des Protocol Engineerings untersucht.

Grundlagen der Computergrafik und des Geometrischen Modellierens werden mit diesem Buch dargestellt. Es behandelt neuere rasterbasierte Techniken (z.B. Texturmapping und Anti-Aliasing), die in modernen Grafikbibliotheken und Grafikkarten von PCs üblich sind. Daneben werden Ray-Tracing und Radiosity Methoden und objektraum-definierte Modelliertechniken, sowie effiziente Algorithmen der Geometrie grundlegend besprochen. Zu den einzelnen Kapiteln sind Übungsaufgaben angeführt.

Nach einer detaillierten Beschreibung multimedialer Daten werden grundlegende Techniken im Bereich der Betriebssysteme und Datenbanken diskutiert, die für die besondere Aufgabe der Verwaltung benötigt werden.In der neuen Auflage werden auch die Aspekte berücksichtigt, die durch die rasante Verbreitung des Internet in Erscheinung getreten sind. Anhand von Übungsaufgaben kann der Leser das erlangte Wissen festigen und vertiefen.