Bücher der Reihe Xleitfaden Der Informatik

Das Ziel dieses Buches ist es, den Leser an den Grundlagen der Informatik zu begeistern. Um dies zu erreichen, bieten wir auer der ublichen rigorosen und detaillierten Prasentation eine leicht verstandliche und anschauliche Darstellung der Grundkonzepte und Ideen und erweitern die klassischen Themen wie Berechenbarkeit und Komplexitat um die faszinierenden Errungenschaften neuer Gebiete wie Randomisierung, Kryptographie und Kommunikation in Netzen.

Klar und fundiert fuhrt dieses Buch in die Grundlagen der Didaktik der Informatik ein. Neben dem theoretischen Rustzeug bietet es praxiserprobte Materialien fur die Lehrerausbildung. Zahlreiche Ubungsaufgaben mit Losungen helfen den Stoff zu vertiefen und bereiten auf die praktische Lehrtatigkeit vor.

Das Buch enthalt eine Einfuhrung in graphentheoretische Grundbegriffe und Basissatze. Graphen werden als Modellierungswerkzeuge fur verschiedene Anwendungen aus dem Bereich der Standortplanung, Logistik, Verkehrsplanung, des Scheduling und der Planung von Kommunikationsnetzen vorgestellt. Fur die entstehenden graphentheoretischen Probleme werden effiziente Verfahren vorgestellt und rigoros analysiert. Fur komplexitatstheoretisch "e;schwierige"e; Probleme enthalt das Buch effiziente Naherungsverfahren, die schnell Losungen mit beweisbarer Gute liefern.

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.

Heutzutage ist es fast schon eine Selbstverständlichkeit, daß in immer kürzeren Ab­ ständen neuartige Rechnertypen auf dem Markt erscheinen. Insbesondere die Mi­ kroprozessoren haben in den letzten Jahren eine stürmische Entwicklung erfahren und viele der Architekturkonzepte, die zunächst den Großrechnern vorbehalten wa­ ren, haben in die Architekturen der Mikroprozessoren Eingang gefunden. In anderen Worten, viele der grundlegenden Ideen, welche die Architektur von Rechnern be­ treffen, existieren schon seit langer Zeit. Sie haben sich trotz all der Fortschritte im Detail und in der Rechnertechnologie in erstaunenswerter Weise als außerordentlich tragfähig erwiesen. Noch heute spiegeln die meisten Rechnerarchitekturen die Grundzüge des sogenannten von Neumannschen Architekturkonzepts wider. Es ist ein Anliegen dieses Buchs, gerade diese grundlegenden Ideen herauszustellen, und nicht so sehr, auf die detaillierte Beschreibung heute verbreiteter Rechnertypen ein­ zugehen. Deshalb wurde auch auf die Beschreibung einzelner Mikroprozessoren weitgehend verzichtet. Darüber gibt es eine umfangreiche Literatur. Dennoch wer­ den alle wichtigen Architekturaspekte moderner Mikroprozessoren behandelt. Das Buch beginnt mit der Erläuterung des Begriffs Architektur. Anschließend wer­ den die wichtigsten Aspekte der Architekturbewertung angesprochen (Kapitel 1). Die Klassifizierung der gängigsten Rechnerarchitekturen ist Inhalt von Kapitel 2. Parallelrechner bilden dabei einen Schwerpunkt. Die ersten beiden Kapitel sollen zum einen eine Übersicht über die Architekturlandschaft vermitteln und zum ande­ ren dem Leser das Einordnen von Architekturkonzepten, wie sie in den folgenden Kapiteln behandelt werden, erleichtern. Danach wird zunächst der Aufbau derZentraleinheit eines Rechners behandelt (Kapitel 3).