Taschenbuch der Informatik

Dritte neuhearheitete Auflage

des Taschenbuches der Nachrichtenverarbeitung In drei Bänden

Unter Mitwirkung zahlreiCher Fachleute

herausgegeben von

K. Stein buch W. Weber Redaktion T. Heinemann

Bandll

Struktur und Progranunierung

von EDV-Systelllen

Springer-Verlag Berlin Heidelberg New York 1974

Dr.-Ing. Karl Steinbuch o. Professor an der Universität

Karlsruhe

Dr.-Ing. Wolfgang Weber o. Professor an der Ruhr-Universität

Bochum

Dipl.-Ing. Traute Heinemann Fachhochschule Rheinland-Pfalz, Abteilung Trier

Fachrirhtung Elektrotechnik Trier

Mit 362 Abbildungen

ISBN -13: 978-3-642-65587-6 e-ISBN -13: 978-3-642-65586-9

DOI: 10.1007/978-3-642-65586-9

Das Werk ist urheberrechtlieh geschützt. Die dadurch begründeten Rechte, insbesondere die der Übersetzung, des Nachdrucks, der Entnahme von Abbildungen, der Funksendung, der Wiedergabe auf photomechanischem oder ähnlichem Wege und der Speicherung in Datenverarbeitungsanlagen bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Bei Vervielfältigungen für gewerbliche Zwecke ist gemäß § 54 UrhG eine Vergütung an den Verlag zu zahlen, deren Höhe mit dem Verlag

zu vereinbaren ist. © by Springer-Verlag, Berlin . Heidelberg 1967, 1971, 1974.

Library of Congress Catalog Card Number 73-80607 Softcover reprint ofthe hardcover 3rd edition '974

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Buche berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, daß solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von

jedermann benutzt werden dürften.

Gesamtherstellung: Universitätsdruckerei H. Stürtz AG, Würzburg

Vorwort

Seit der letzten Auflage des von J(.Steinbuch herausgegebenen Taschenbuchs der Nachrichtenverarbeitung im Jahre 1967 war eine Überarbeitung dieses Werkes wiederum dringend notwendig geworden, um die dynamische Entwicklung dieses Gebietes in einem "Zeitschnitt" einzufangen.

Autoren, Herausgeber und Verlage solcher Werke leiden wie diese selbst natürlich unter dem Zwang, ein in Bewegung befindliches Gebiet immer nur in gewissen Zeitabständen darstellen zu können, zumal bei der Drucklegung manche Beiträge schon wieder ergänzungsbedürftig sind, aus verlegerischen und organisa­torischen Gründen jedoch die Festlegung eines rechtzeitigen Abgabetermines erforderlich ist, gerade bei einem derart umfangreichen Unternehmen mit dieser großen Anzahl von Einzelautoren.

Nach wie vor war das Ziel bei der Gestaltung dieses Nachfolgers des Taschen­buchs der Nachrichtenverarbeitung, ein Nachschlagewerk für die Grundlagen und die Technik der Nachrichtenverarbeitung zu schaffen, das dem Ingenieur, System­analytiker, Organisationsfachmann, Informatiker, Mathematiker und Physiker eine rasche Übersicht schafft, die wichtigsten Tatsachen unmittelbar darstellt und für spezielle Fragen Quellenhinweise gibt.

In dieser Hinsicht ist der Charakter des ursprünglichen Werkes gewahrt ge­blieben. Gänzlich neu ist jedoch die begriffliche Gliederung des Gesamtstoffes und die Aufnahme neuer Themenkomplexe und damit die Beteiligung zusätzlicher Autoren für Einzelbeiträge, wobei eine Reihe früherer Beiträge aus Gründen der Beschränkung auf einen vernünftigen Umfang fortgelassen oder gekürzt werden mußten.

Neu hinzugekommen sind insbesondere größere Abschnitte über die Program­mierung und über die Anwendung von EDV-Systemen.

Die Herausgeber sind dabei von dem Wunsch ausgegangen, durch eine hierarchi­sche Stoffeinteilung eine möglichst große Übersichtlichkeit für den Benutzer zu erreichen, wie sie bei dieser Stoffülle durch ein einfaches NebeneinandersteIlen des nur grob vorsortierten Stoffes nicht zu erreichen gewesen wäre. So ergibt sich eine erste Information über die inhaltliche Gliederung der drei Bände des Taschenbuchs der Informatik aus der auf S. XVI abgedruckten Übersicht.

Die in der zweiten Auflage des Taschenbuchs der Nachrichtenverarbeitung erschienenen Beiträge wurden, soweit sie vom Themenkomplex her hier wieder mit gleichen oder ähnlichen Titeln aufgenommen werden konnten, von den Verfassern fast generell wesentlich ergänzt oder neu geschrieben.

Ihnen und in gleicher Weise auch den neu hinzugetretenen Autoren sei hier herzlich gedankt für die für alle Beteiligten diffizile und Geduld erfordernde Ge­meinschaftsarbeit, die dann gelohnt hat, wenn dieses \Nerk allen unseren Fach­kollegen, Studenten, Ingenieuren und WIssenschaftlern eine nützliche Hilfe für ihre Arbeit ist.

VI Vorwort zu Band II

An den Schluß unseres Vorwortes möchten wir den Dank an unsere Redakteurin und an Verlag und Druckerei stellen. Die redaktionelle Arbeit wurde von Frau Dipl.-Ing. T. Heinemann in mehrfachem Durchgang mit Sorgfalt und termin­licher Promptheit bewältigt. Dem Springer-Verlag sei für die saubere und einwand­freie Herstellung der Bücher besonders gedankt.

K. Steinbuch W. Weber

Vorwort zu Band 11

War der Band I des "Taschenbuch der Informatik" der Behandlung grund­legender Basisdisziplinen und den Bauelementen und Baugruppen von EDV­Anlagen gewidmet, bildet der hier vorliegende Band II den Kern des dreibändigen Werks.

Den Auftakt bildet Kapitel 5 mit theoretischen Grundlagen der Schaltalgebra, Automatentheorie, Nachrichtentheorie und Codierung.

Es folgt das zentrale Kapitel "Organisation und Wirkungsweise von EDV­Anlagen". Die Leit-, Rechen- und Ein-Ausgabe-Werke und die Peripheriegeräte von EDV-Anlagen werden in den Folgekapiteln behandelt.

Band II wird abgeschlossen durch Abschnitte über die Programmierung digi­taler, analoger und hybrider Rechnersysteme.

Karlsruhe und Bochum, im Frühjahr 1974

K. Steinbuch W. Weber

Mitar beiterverzeichnis

Berger-Damiani, Erich R., Prof. Dr.-Ing., Technische Universität Berlin, Institut für Fernmeldetechnik

ehroust, Gerhard, Dipl.-Ing., IBM Laboratorium Wien

Gerstmann, Hans, Assessor des Lehramtes, Böblingen

Glombitza, Günter, Ing. (grad.), i. H. IBM Roece Inc., Vienna Branch, Wien

Haake, Dieter, Dipl.-Ing., Telefunken Computer GmbH, Konstanz

Händler, Wolfgang, Prof. Dr. rer.nat., Institut für Mathematische Maschinen und Datenverarbeitung der Universität Erlangen-Nürnberg

Härtenberger, Ludolf, Ing. (grad.), i.H. Siemens AG, München

Hartenstein, Reiner, Dr.-Ing., Institut für· Informatik IV der Universität, Karlsruhe

Hartwig, Rüdiger, Dr.-Ing., i. H. IBM Deutschland GmbH, Sindelfingen

Hoffmann, Hans-Jürgen, Prof. Dr.-Ing., Technische Hochschule Darmstadt, Fachbe-reich Informatik (Der Beitrag wurde abgefaßt während der Tätigkeit beim IBM Forschungslaboratorium, Rüschlikon)

Jess, Jochen, Prof. Dr.-Ing., Technische Hogeschool Eindhoven, Afdeling der Elektrotechniek, Eindhoven

Kley, Adolf, Dr.-Ing., AEG-Telefunken, Forschungsinstitut, Ulm

von Knorre, Karl-Friedrich, Ing. (grad.), Telefunken Computer GmbH, Konstanz

Kohler, Siegfried, Ing.(grad.), LH. Siemens AG, München

Kürner, Hans, Dipl.-Ing., i.H. Siemens AG, Karlsruhe

Mehlhose, Gerhard, Ing. (grad.), Böblingen

Meyer-Brätz, Günter, Prof. Dr.- Ing., AE G-Telefunken, Forschungsinstitut, Ulm

Nowotny, Ernst, Dr., IBM Laboratorium Wien

Paulus, Erwin, Dr.-Ing., München

Peschke, Peter, Dipl.-Ing., Telefunken Computer GmbH, Konstanz

Preisinger, Max, Ing. (grad.), Wittibreut

Rohde, Helmut, Dipl.-Ing., i.H. AEG-Telefunken, Informationstechnik, Konstanz

Spies, Peter Paul, Prof.-Dr., Institut für angewandte Mathematik und Informatik der Universität Bonn, Abt. für Informatik II

Walter, Wolfgang, Dr.-Ing., i. H. IBM Deutschland GmbH, Stuttgart

Zemanek, Heinz, Prof. Dr. techn., Direktor des IBM Laboratoriums Wien

Inhaltsverzeichnis

5. Grundlagen

5.1 Logische Algebra und Theorie der Schaltnetzwerke. VonH.Zemanek, Wien, in Zusammenarbeit mit G. Chroust und E. Nowotny

5.1.1 Die Funktion in der logischen Algebra . 3 5.1.2 Rechenregeln der logischen Algebra 12 5.1.3 Schaltnetzwerke: Analyse und Synthese 19 5.1.4 Bündel von Funktionen 29 5.1.5 Basisfunktionen ..... 32 5.1.6 Die Zeit in der Schaltalgebra 36 5.1. 7 Asynchrone Betriebsweise 45 5.1.8 Entstörung und Prüfung von Bauelementen 48 5.1.9 Informationstheoretische Betrachtungen 52 5.1.10 Verallgemeinerungen der Schaltalgebra . 55

Literatur 59

5.2 Automatentheorie. Von W. Händler, Erlangen 63

5.2.1 Nomenklatur und einige elementare mathematische Hilfsmittel 63 5.2.2 Allgemeine endliche Automaten ........ 69 5.2.3 Äquivalenz und Homomorphismus ............ 71 5.2.4 Reduktion von vollständigen endlichen Automaten .... . 72 5.2.5 Anmerkungen zu unvollständigen, nichtdeterministischen und stocha-

stischen Automaten . . . . . . . . . . . . . . . . . 74 5.2.6 Halbgruppen von endlichen Automaten und Experimente 75 5.2.7 Automat und Sprache . . . . . . . . . . . . . . . 78 5.2.8 Kellerautomaten und kontextfreie Sprachen als Beispiel 82 5.2.9 Zellulare Logik und iterative Automaten-Netze . 86

Literatur 87

5.3 Nachrichtentheorie, Zahlensysteme und Codierung. Von E. R. Berger-Damiani, Berlin . . . . . . . . . . . . . . . . 88

5.3.1 Informationstheoretische Grundlagen. . . . . . 88 5.3.1.1 Die Nachricht als Auswahl: der Informationsgehalt 88 5.3.1.2 Bedingter Informationsgehalt, Synentropie. . . . 90 5.3.1.3 Die fortgesetzte Auswahl; Informationsbelag und Informationsfluß 91 5.3.1.4 Der Übertragungskanal . . . . . . . . . . . . . 92 5.3.1.5 Die Kanalkapazität . . . . . . . . . . . . . . . 93

5.3.2 Die Prinzipien der Codierung; die Darstellung von Codes 94 5.3.3 Die Darstellung numerischer Information. 97 5.3.4 Die Codierung von Alpha-Text 100 5.3.5 Codes mit Nebenbedingungen 103

5.3.5.1 Einschrittige Codes . . . . 103 5.3.5.2 Ketten-Codes . . . . . . 103 5.3.5.3 Einschrittige Ketten-Codes. 103 5.3.5.4 Redundanzsparende ("optimale") Codes 104 5.3.5.5 Redundanz-Einsparung durch Codes-Umsetzung 105 5.3.5.6 Lexikographische Codes . . . . . . . . . . . 106

Inhaltsverzeichnis

5.3.5.7 Die Eindeutigkeit der Textzerlegung 5.3.5.8 Kennzeichnung der Phasenlage ...

5.3.6 Sicherung gegen Störungen . . . . . . 5.3.6.1 Kennzeichnung der binären Störungen 5.3.6.2 Das Grundprinzip der Sicherung . . . 5.3.6.3 Gruppencodes . . . . . . . . . . . 5.3.6.4 Zeichensicherung, Blocksicherung, gleitende Sicherung. 5.3.6.5 Zeichensicherung 5.3.6.6 Blocksicherung .

Literatur

6. Organisation und Wirkungsweise von EDV -Anlagen 6.1 Universelle Digital-Rechenanlagen. Von W. Händler, Erlangen, und P. P.

IX

106 106 107 107 109 110 111 112 113 116

Spies, Bonn . . . . . . . . . . . . . . . . . . . 118

6.1.1 Der klassische Universalrechner . . . . . . . . . 118 6.1.1.1 Funktionsbedingte Struktur einer Rechenanlage 118 6.1.1.2 Grundlagen der Realisierung 119 6.1.1.3 Parallel-Rechner . . . 126 6.1.1.4 Serien-Rechner. . . . 138

6.1.2 Kenngrößen des Entwurfs. 142 6.1.2.1 Informationsdarstellung 142 6.1.2.2 Befehlsvorrat 156

6.1.3 Struktur der Rechner-Werke 163 6.1.3.1 Speicherwerk . 163 6.1.3.2 Rechenwerk . . . . . 166 6.1.3.3 Leitwerk . . . . . . 174

6.1.4 Moderne Universalrechner . 182 6.1.4.1 Einfluß von Apparatur und Programmatur auf die Entwicklung 182 6.1.4.2 Simultanarbeit im Rechnerkern 187 6.1.4.3 Simultane Ausführung von Programmen. 195 6.1.4.4 Bewertung von Rechenanlagen 218

6.1.5 Ausblick 231

Literatur 238

6.2 Analoge und hybride Rechnersysteme

6.2.1 Analoge und hybride Rechnersysteme. Von A. Kley, Ulm, und G. Meyer­Brötz, U1m . . . . . . . . . . . . . . . . . . . . . . . . . . 242

6.2.1.1 Das "Spektrum" elektronischer Rechenanlagen ......... 242 6.2.1.2 Zur Planung und Konstruktion von Gleichspannungs-Analogrech-

6.2.1.3 6.2.1.4 6.2.1.5 6.2.1.6

Literatur

nern ........... . Steuerung, Anwahl und Prüfung Stromversorgung . . . . . Der hybride Analogrechner Das hybride Rechnersystem

6.2.2 Programmierung von Analog- und Hybridsystemen. Von J. Jess, Eindhoven .....

6.2.2.1 Einleitende Bemerkungen . 6.2.2.2 Ablauf des Programmiervorganges 6.2.2.3 Programmierung einzelner Phasen am Analogteil 6.2.2.4 Verläßlichkeit von Analogrechenmodellen 6.2.2.5 Nichtelementare Programmabläufe

Literatur

245 249 256 258 263

264

265

265 267 268 280 282

289

x Inhaltsverzeichnis

7. Leit-, Rechen- und Ein/Ausgabe-Werke 7.1 Leitwerke. Von H. Rohde, Konstanz ...... .

7.1.1 Aufgaben und Arbeitsweise der einzelnen Werke 7.1.1.1 Zentrales Leitwerk . 7.1.1.2 Operationensteuerung . . . . . . . . . 7.1.1.3 Adressenrechenwerk . . . . . . . . . . 7.1.1.4 Programmunterbrechungswerk (Interrupt) 7.1.1.5 Das Vorrangwerk (Speicherzugriffskoordinator) .

7.1.2 Entwurf und Ausführung der Werke 7.1.2.1 Allgemeine Grundlagen .. . 7.1.2.2 Mikroprogrammierung ... . 7.1.2.3 Das Zeitverhalten der Werke.

Literatur

290

291 291 292 294 299 301 302 302 307 312 313

7.2 Rechenwerke. Von K.-F. von Knorre, Konstanz. 314

7.2.1 ZahlendarsteIlung von Operanden zur Verarbeitung im Rechenwerk . 314 7.2.1.1 Zeichendarstellung . . 314 7.2.1.2 Festpunktdarstellung . . . . . . . . . . . 314 7.2.1.3 Gleitpunktdarstellung . . . . . . . . . . . 315 7.2.1.4 Darstellung negativer Zahlen und Vorzeichen. 315

7.2.2 Operationen des Rechenwerks . 316 7.2.2.1 Arithmetische Operationen. . 317 7.2.2.2 Boolesche Operationen 317 7.2.2.3 Organisatorische Operationen 317

7.2.3 Aufbau von Rechenwerken 318 7.2.3.1 Serienverarbeitung . . . . . 318 7.2.3.2 Parallelverarbeitung 319 7.2.3.3 Aufbau eines herkömmlichen Rechenwerks . 320 7.2.3.4 Aufbau eines Rechenwerks mit mehreren Operationswerken 325 7.2.3.5 Aufbau eines Stack-Rechenwerks. . . . . . . . . 325

Literatur (s. S. 313)

7.3 EinjAusgabewerke. Von D. Haake, Konstanz, und P. Peschke, Konstanz 327

7.3.1 Einleitung . . . . . . . . . . . . . . . . . 327 7.3.2 Das EA-Werk ist ein Teil des Zentral-Prozessors. . 328

7.3.2.1 EinjAusgabe im ungeladenen Zustand. . . . . 328 7.3.2.2 Programmierte EinjAusgabe (Rechnerkernkanal) 328

7.3.3 EinjAusgabewerk als selbständige Funktionseinheit. 335 7.3.3.1 EA-Auftrag zur Durchführung einer EA-Operation 335 7.3.3.2 Auftragsübermittlung an das EA-Werk . . . 336 7.3.3.3 Aufgabe und Funktion des EA-Leitwerks . . 337 7.3.3.4 Aufgabe und Funktion eines EA-Kanalwerks . 339

8. Peripheriegeräte 8.1 AnalogjDigital- und DigitaljAnalog-Umsetzer. Von H. Kürner, Karlsruhe 341

8.1.1 AnalogjDigital-Umsetzer für elektrische Größen 8.1.1.1 ADU zur Augenblickswllrtmessung ... . 8.1.1.2 ADU zur Mittelwertmessung ...... .

8.1.2 DigitaljAnalog-Umsetzer für elektrische Größen 8.1.2.1 Parallelarbeitende DAU mit Gleichspannungsausgang 8.1.2.2 Parallelarbeitende DAU mit Wechselspannungsausgang 8.1.2.3 Seriell arbeitende DAU . . . . . . . . . . . . . 8.1.2.4 DAU mit Zwischengröße ............ .

8.1.3 ADU für geometrische Größen (Drehwinkel und Länge) . 8.1.3.1 ADU nach dem Parallelverfahren (Absolut-Messung) 8.1.3.2 ADU nach dem Serienverfahren (Inkrement-Messung)

341 345 351 354 355 358 359 359 360 360 361

Inhaltsverzeichnis

8.1.4 DAU für geometrische Größen (Drehwinkel und Längen) 8.1.4.1 DAU mit Schrittmotoren ... 8.1.4.2 DAU mit digitaler Wegmessung 8.1.4.3 DAU mit analoger Wegmessung

Literatur

8.2 Digitale Anzeigevorrichtungen. Von W. Walter, Stuttgart

8.2.1 Einführung . . . . . . . 8.2.2 Abbildende Ziffernanzeigen 8.2.3 Zusammengesetzte Ziffern 8.2.4 Ausblick

Literatur

8.3 Elektrische Schreibmaschinen. Von G. Glombitza, Wien.

8.3.1 Korrespondenz-Schreibmaschine. . . . 8.3.2 Eingabe- und Ausgabe-Schreibmaschinen

Literatur

8.4 Fernschreib- und Lochstreifengeräte. Von L. Härtenberger, München, und S. Kohler, München . . . . . . . . . . . . . . . . . . . . . .

8.4.1 Handelsübliche Fernschreibgeräte mit Serien-Ein- und -Ausgang 8.4.1.1 Allgemeines. . . . . 8.4.1.2 Senderprinzipien . . . . . . . . . . . . 8.4.1.3 Empfängerprinzipien . . . . . . . . . . 8.4.1.4 Merkmale handelsüblicher Fernschreibgeräte 8.4.1.5 Fernschreibgeräte in Sonderausführung . .

8.4.2 Lochstreifengeräte mit parallelem Ein- und Ausgang 8.4.2.1 Langsame Lochstreifengeräte . 8.4.2.2 Schnelle Lochstreifenleser 8.4.2.3 Schnelle Locher 8.4.2.4 Lochstreifenwickler

Literatur

8.5 Lochkartenmaschinen. Von G. Mehlhose, Böblingen .....

8.5.1 Lochkarten und Codes ..... 8.5.2 Kartenlochen und Kartenprüfen . 8.5.3 Eingabe-Einheiten. . . . . . . 8.5.4 Sortieren und Mischen ..... 8.5.5 Äußere und innere Programmeinrichtung 8.5.6 Doppler und Lochschriftübersetzer ... 8.5.7 Lochkartenmaschinen als Peripherie-Geräte

Literatur

8.6 Mechanische Schnelldrucker. Von R. Hartwig, Sindelfingen

8.6.1 AufgabensteIlung im Datenverarbeitungssystem 8.6.2 Kennzeichnung, Aufbau und Arbeitsweise 8.6.3 MSD-Entwicklung der letzten Jahre

Literatur

8.7 Nichtmechanische Schnelldrucker. Von M. Preisinger, Wittibreut

8.7.1 Der NMSD in der Datenverarbeitung 8.7.2 Nichtmechanische Druckverfahren ....... .

8.7.2.1 Elektrostatische Druckverfahren . . . . . . . 8.7.2.2 Photoelektrische Verfahren (Photronic Printing) 8.7.2.3 Elektromagnetische Druckverfahren. 8.7.2.4 Elektrochemische Druckverfahren . . . . . .

XI

361 361 362 362

363

365

365 366 369 371

372

372

372 381

387

387

387 387 392 396 399 403 404 405 410 414 417

418

418

418 422 425 426 429 431 432

436

436

436 437 443

444

HG

447 447 447 452 453 454

XII Inhal tsverzeichnis

8.7.2.5 Elektrothermische Druckverfahren . . . . . ... 8.7.2.6 Photographische Druckverfahren; das COM-System .

8.7.3 Logische Schaltungen in NMSD ...... . Literatur . . . . . . .

8.8 Optische Ein- und Ausgabe, Bildschirmgerä te. Karlsruhe ........ .

8.8.1 Photo-elektrische Abtaster 8.8.2 Bildschirm-Konsolgeräte . 8.8.3 Bildschirm-Ausgabe . . .

8.8.3.1 Reproduzierende Bildausgabe 8.8.3.2 Punktschreibende graphische Ausgabe. 8.8.3.3 Linienschreibende graphische Ausgabe. 8.8.3.4 Alphanumerische Ausgabe

8.8.4 Bildschirm-Eingabe 8.8.4.1 Alphanumerische Eingabe 8.8.4.2 Graphische Eingabe. . . 8.8.4.3 Selektion durch Markierung

8.8.5 Systemkonfigurationen mit Bildschirmgeräten

Von R. Hartenstein,

8.8.6 Film-Recorder, Projektoren und Elektrolumineszenz-Displays Literatur . . . . . . . . . . . . . . . . . . . . . . .

8.9 Akustische Eingabe und Ausgabe. Von E. Paulus, München 8.9.1 Einführung ..... 8.9.2 Sprachausgabesysteme 8.9.3 Spracheingabe Literatur

9. Programmierung digitaler Datenverarbeitungssysteme Von H. Gerstmann, Böblingen, und H.-]. Hoffmann, Darmstadt

9.1 Einleitung . . 9.1.1 Daten . . 9.1.2 Programme 9.1.3 Systeme . 9.1.4 Programmiersysteme .

9.2 Datenstrukturen . . . . 9.2.1 Lineare Listen

9.2.1.1 Typen linearer Listen 9.2.1.2 Speicherdarstellung linearer Listen

9.2.2 Felder . . . . . 9.2.3 Listenstrukturen 9.2.4 Bäume . . . . . 9.2.5 Dateien

9.2.5.1 Dateischemata 9.2.5.2 Dateiorganisation .

9.3 Grundoperationen 9.3.1 Anweisungen . . . .

9.3.1.1 Funktionen . . . 9.3.1.2 Wertzuweisungen . 9.3.1.3 Funktionsprozeduren

9.3.2 Universelle Programmiersprachen 9.3.2.1 Modell einer universellen Programmiersprache 9.3.2.2 Schleifenprogramme . . . . . .

9.3.3 Operationen in Programmiersprachen 9.3.3.1 Arithmetische Operationen. 9.3.3.2 Zeichenfolge-Operationen

457 458 459 464

465 465 467 467 468 469 469 472 474 474 474 476 477 478 479 481 481 482 491 495

497 497 498 500 501

502 504 504 505 506 507 507 509 509 510

512 512 513 514 514 515 515 516 517 518 520

Inhaltsverzeichnis

9.3.3.3 Listenoperationen . . 9.3.3.4 Logische Operationen 9.3.3.5 Systemoperationen .

9.4 Einsatz digitaler Datenverarbeitungssysteme 9.4.1 Reichweite der algorithmischen Beschreibung 9.4.2 Systemstruktur . . . . .

9.4.2.1 Programmieraufwand ..... 9.4.2.2 Mathematische Modelle . . . . 9.4.2.3 Systematisches Programmieren.

9.4.3 Numerische Anwendungen 9.4.3.1 Rundungsfehler 9.4.3.2 Intervallarithmetik . . . 9.4.3.3 Numerische Algorithmen

9.4.4 Nichtnumerische Anwendungen 9.4.4.1 Simulationsmodelle . . . . 9.4.4.2 Nichtdeterministische Algorithmen

9.4.5 Ausprüfen von Programmen 9.4.5.1 Testverfahren . . 9.4.5.2 Beweisverfahren . . . .

9.4.6 Grenzen des Einsatzes . . .

XIII

520 521 522

522 522 523 523 525 525 527 528 530 531 531 532 533 534 534 535 536

9.5 Diagrammatische Hilfsmittel der Programmierung 536 9.5.1 Vorbereitende Arbeiten zur Programmierung 536 9.5.2 Datenflußplan 537 9.5.3 Programmablaufplan 537 9.5.4 Entscheidungstabellen 543 9.5.5 Programmdokumentation 544

9.6 Ausdrucksmittel problemorientierter Programmiersprachen. 545 9.6.1 Einleitung . . . . . . . . . . . . . . . . . . . . 545 9.6.2 Sprachliche Ausdrucksmittel und zugeordnete Bedeutung - Syntax,

Semantik. . . . . . . . . . . . . . . . . 546 9.6.3 Formalisierte Syntax ........... 548 9.6.4 Festes bzw. freies Format, Formularbenutzung 551 9.6.5 Implizite und algorithmische Programmierung 552 9.6.6 Äußere und innere Syntax, gemeinsame Züge der Semantik 554 9.6.7 Programmobjekte problemorientierter, algorithmischer Programmie-

rung, Vereinbarungen 556 9.6.8 Unterprogrammtechnik . . . . . 558 9.6.9 Parameterversorgung . . . . . . 559 9.6.10 Datenfelder, Programmschleifen 561 9.6.11 Verzweigungen im Programmablauf 561 9.6.12 Wertzuweisung . . . . 564 9.6.13 Notprogramme . . . . 565 9.6.14 Datenein- und -ausgabe 565 9.6.15 Parallele Prozesse. . . 566 9.6.16 Kompilierer . . . . . 567 9.6.17 Programmbibliotheken, Programmbindung, Programmladen, modu-

lare Programmierung . . . . . . . . . . . . . . . . . 568 9.6.18 Emulatoren, Simulatoren, Sprachumwandlungsprogramme . . 569 9.6.19 Makrosubstitution . . . . . . . . . . . . . . . . . . . 570 9.6.20 Automatische Erstellung von Kompilierern, Metakompilierer . 570 9.6.21 Abriß der geschichtlichen Entwicklung 570

9.7 Die wichtigsten Programmiersprachen 571 9.7.1 ALGOL 60 571 9.7.2 ALGOL 68 578 9.7.3 FORTRAN 579 9.7,4 BASIC. . 582

XIV Inhaltsverzeichnis

9.7.5 COBOL . . . . . . . . . . . . . . . . . . . 583 9.7.6 PLjI . . . . . • . . . . . . . . . . . . . . . 583 9.7.7 Listen- und Symbolverarbeitung: LlSP, SNOBOL . 585 9.7.8 Matrizenverarbeitung: APL. . . . . . . . . . . 586 9.7.9 Berichtsschreibung: RPG. . . . . . . . . . . . 587 9.7.10 ModelIierung und Simulation: GPSS, SIMSCRIPT, SIMULA 587 9.7.11 Betriebs- und Kommandosprachen. . . . . 588 9.7.12 Sonstiges . . . . . . . . . . . . . . . . 589

9.8 Maschinelle Übersetzung von Programmiersprachen 589 9.8.1 Allgemeines. . . . . . . . . . . . . . . . 589

9.8.1.1 Klammerstrukturen . . . . . . . . . . . 590 9.8.1.2 Das Erkennen syntaktisch zulässiger Zeichenfolgen 591

9.8.2 Richtungsweisende Verfahren 594 9.8.2.1 Syntaktische Funktionen . . . . . . . . . . . 594 9.8.2.2 Syntaktische Zustände . . . . . . . . . . . . 595

9.8.3 Einige Ergebnisse der Theorie kontextfreier Sprachen 597 9.8.3.1 Kontextfreie Sprachen . . . . . . . . . 597 9.8.3.2 Kellerautomaten und kontextfreie Sprachen . . . 598 9.8.3.3 Deterministische Sprachen. . . . . . . . . . . 599 9.8.3.4 Präzedenzgrammatik nach WirthjWeber (precedence grammar) 599 9.8.3.5 LR(k)-Grammatik nach Knuth [LR(k) grammar] . 601 9.8.3.6 Reduktionssprachen . . 601

9.8.4 Übersetzungstechniken . . 601 9.8.4.1 Semantische Aktionen. 601 9.8.4.2 Lexikale Analyse . . . 602 9.8.4.3 Codegenerierung . . . 603 9.8.4.4 Rekursive Programmierung 604 9.8.4.5 Optimierung. . . . . . . 605 9.8.4.6 Adreßzuweisung . . . . . 607

9.8.5 Abriß der Geschichte der Übersetzung von PPS 607

9.9 Betriebssysteme 9.9.1 Aufgaben eines Betriebssystems, Auf teilung der Aufgaben zwischen

Betriebsablaufverwaltung und Überwacher ......... . 9.9.2 Mehrprogrammbetrieb, Mehrprozessorsystem, Mehrrechnersystem 9.9.3 Stapelverarbeitung, Dialogverarbeitung, Verfahrenskontrolle . . 9.9.4 Dateien, Dateiorganisation und -zugriff, Überwachungssysteme für

Datenein- und -ausgabe. . . . . . . . 9.9.5 Arbeitsreihenfolge (Scheduling) . . . . 9.9.6 Belegungskontrolle (Resource allocation) 9.9.7 Systemgenerierung ...... . 9.9.8 Geschichtlicher Überblick

9.10 Programmierung einer Modellmaschine 9.10.1 Einleitung . . . . . 9.10.2 Die Modellmaschine . 9.10.3 Speichereinteilung 9.10.4 Adressierung. . . . 9.10.5 Befehlsstruktur . . . 9.10.6 Eine symbolische Schreibweise für Befehle und Daten 9.10.7 Die vollständige Befehlsliste der Modellmaschine . . 9.10.8 Arithmetische und logische Befehle, Vergleichsbefehle,

befehle . . . . . . . . . . . . . . . . . . . .. Bewegungs-

9.10.9 Unbedingte und bedingte Sprungbefehle . . . . . . . . . . . . . 9.10.10 Indizierung in Befehlen, Befehle zur günstigen Programmierung von

Programmschleifen .. . . . . . . . . . . . . . . . . . . . 9.10.11 Überwachungsbefehle, Überwachungs- und Problemstatus, Aus­

nahmebedingungen und Programmunterbrechungen . . . . . . .

608

608 609 611

612 613 615 617 618

619 619 620 621 624 626 628 629

633 634

634

636

Inhaltsverzeichnis xv

9.10.12 Datenein- und -ausgabe, Kanalprogramme 638

9.11 Ein Modell eines Überwachers . . . . . . . . 641 9.11.1 Einleitung, der Modellüberwacher . . . . . 641 9.11.2 Prozesse und Kommunikation zwischen Prozessen im Modellüber-

wacher . . . . . . . 645 9.11.3 Arbeitsreihenfolge 646 9.11.4 Arbeitsspeicherbelegung 646 9.11.5 Datenein- und -ausgabe 647

9.12 Ein Modell eines Übersetzers 649 9.12.1 Einleitung . . . . . . . 649 9.12.2 Prinzipieller Aufbau des Übersetzers 649 9.12.3 Behandlung besonderer Spracheigenschaften. Makroanweisungen 650 9.12.4 Codegenerierung . . . . . . . . . . 651

9.13 Ein Modell einer Betriebsablaufverwaltung 653 9.13.1 Einleitung, das Modell. 653 9.13.2 Auftragsbeschreibung . 654 9.13.3 Programmbeschreibung 655 9.13.4 Dateibeschreibung 656

Literatur . . . 656

Sachvuzeichnis 661

XVI

Band I : Grundlagen der technischen Informatik

2 Bauelemente

Allgemeine Grundlagen

3 Digitale Schaltungen

Bau gruppen und Wandler

4 Digitale Speicher

Band n: Struktur und Programmierung von EDV-Systemen

5 Grundlagen

7 Leit-,Rechen- und

Ein -Ausgabewerke

9

6 Organisation und Wirkungs­

weise von EOV-Anlagen

8 Peripheriegeräte

Programmierung digitaler

Da t e nve ra rb e i tun gs systeme

Band rn : Anwendungen und spezielle Systeme

10 11 12 Kommerzielle Technische wissenschaft- Prozen­

datenverarbeitung Datenverarbeitung liche Datenverarbeitung

13 Spezielle Aufgaben der

Nachrichtenverarbeitung

14 Nac hrichtenverarbeitu ng

im Menschen