Informatik- Handbuch

Informatik-Handbuch 2., aktualisierte und erweiterte Auflage

Herausgegeben von

Peter Rechenberg Gustav Pomberger

Endredaktion

Doris Martin

Drucktechnische Gestaltung

Klaus Pirklbauer

Carl Hanser Verlag München Wien

Inhalt 11

Inhalt

A Theoretische Informatik

1 L o g i k - A. Jung 33

1.1 Grundbegriffe der Logik 34

1.2 Aussagenlogik 36

Semantik der Aussagenlogik - Natürliches Schließen - Resolution

1.3 Von der Aussagenlogik zur Prädikatenlogik 44

1.4 Strukturen 45

Kongruenzrelationen - Tenne und Termalgebren

1.5 Gleichungslogik 50

1.6 Prädikatenlogik 52 Sprache der Prädikatenlogik - Semantik der Prädikatenlogik -Substitution - Natürliches Schließen mit Quantoren - Normalformen und Skolemisierung - Prädikatenlogische Resolution - Unentscheidbarkeit -Axiomatisierbarkeit - Prädikatenlogik zweiter Stufe

1.7 Modallogik 64

Sprache der Modallogik - Semantik der Modallogik - Modallogische Beweise - Spezielle modale Logiken - Multimodale Logik - Temporale Logik

Symbolverzeichnis 70

Allgemeine Literatur 71

Spezielle Literatur 72

2 Berechnungsmodelle - A. Jung 73

2.1 Speicherorientierte Modelle 74

Turingmaschinen - Registermaschinen

2.2 Funktionale Modelle 77

Algebraische Kombinationen - Primitive Rekursion - ^-Rekursion -Lambda- Kalkül

2.3 Kommunikation und verteilte Systeme 85

EA-Turingmaschinen - Verteilte Systeme



3 Formale Sprachen und Automaten - P. Rechenberg 89

3.1 Grundbegriffe 90

Zeichenketten und Sprachen - Grammatiken - Kanonische Ableitungen

und Mehrdeutigkeit

3.2 Die Chomsky-Hierarchie 93

3.3 Reguläre Sprachen und endliche Automaten 94

Charakterisierung - Reguläre Mengen und reguläre Ausdrücke - Endliche Automaten - Sonstiges

3.4 Kontextfreie Sprachen und Kellerautomaten 98

Charakterisierung - Grammatiktransformationen und Normalformen -Kellerautomaten - Kontextfreie Grammatiken und Kellerautomaten -Erkennungsverfahren

3.5 Deterministische Grammatiken 102

LL(ft)-Grammatiken und absteigende Syntaxanalyse - LR(k)-Grammatiken und aufsteigende Syntaxanalyse

3.6 Turingmaschinensprachen 104

3.7 Kontextsensitive und unbeschränkte Sprachen 106

Nachbildung von Turingmaschinen - Entscheidbarkeit kontextsensitiver Sprachen - Der linear beschränkte Automat - Unbeschränkte Sprachen

3.8 Weitere Sprachklassen 108

3.9 Eine Hierarchie von Sprachen 108




Grenzen der Berechenbarkeit - 1 . Wegener 111 4.1 Rechnermodelle und die Churchsche These 111

Rechnermodelle - Universelle Rechner - Simulationen - Churchsche These

4.2 Gibt es nichtberechenbare Funktionen? 113

Die Existenz nichtberechenbarer Funktionen - Das Halteproblem

4.3 Weitere unentscheidbare Probleme 115

Reduktionen - Softwareverifikation - Formale Sprachen -Prädikatenlogik


K o m p l e x i t ä t - 1 . Wegener 119

5.1 Größenordnungen und die O-Notation 120

5.2 Die NP-Vollständigkeitstheorie 121

Die Klasse P - Die Robustheit der Klasse P - Berechenbare Probleme, die nicht in P liegen - Die Klasse NP - NP-Vollständigkeit - NP-vollständige Probleme

5.3 Erweiterungen der NP-Vollständigkeitstheorie 126

Pseudopolynomielle Algorithmen und starke NP-Vollständigkeit -Approximationsalgorithmen und die PCP-Theorie

5.4 Komplexitätsklassen für probabilistische und parallele Rechner 130

Komplexitätsklassen für probabilistische Rechner - Eine Komplexitätsklasse für Parallelrechner

5.5 Die polynomielle Hierarchie 132

Die Komplexitätsklassen der polynomiellen Hierarchie -Komplexitätsklassen innerhalb von NP

5.6 Speicherkomplexität 133

Determinismus und Nichtdeterminismus - Vollständigkeit

Inhalt 13

5.7 Nichtuniforme Komplexitätsklassen 134

Schaltkreise mit beschränktem Fan-in - Tiefenbeschränkte Schaltkreise -Die NC-AC-Hierarchie - Branchingprogramme und OBDDs

5.8 Kommunikationskomplexität 138

Das Kommunikationsspiel - Untere Schranken - Anwendungen



6 Formale Semantik und Programmverifikation -E.-R. Olderog, B. Steffen 143

6.1 Sequentielle Programme 144

Syntax - Operationelle Semantik - Verifikation - Beweisskizzen

6.2 Parallele Programme 153

Gemeinsame Variablen - Syntax - Operationelle Semantik -Verifikation: Partielle Korrektheit - Verifikation: Totale Korrektheit -Fallstudie: Finde positives Element

6.3 Ausblick 160




Daten

1 Zeichen- und Zahlendarstellungen - W. F. Bohn, T. Flik 167 1.1 Zeichendarstellung 168

1.2 Zifferncodes 168

1.3 Codierung alphanumerischer Daten 169

6-Bit-Codes - 7-Bit-Codes - 8-Bit-Code nach ISO/IEC - 8-Bit-Codenach EBCDIC - 8-Bit-Code des PC unter DOS (PC-ASCII) - 16-Bit-Code (Unicode) - 32-Bit-Code (UCS) - Bezeichnungsweisen

1.4 Ganze Zahlen 177

Vorzeichenlose Dualzahlen - Vorzeichenbehaftete Dualzahlen -Computerarithmetik mit Dualzahlen - Oktale und sedezimale Codierung - Dualcodierte Dezimalziffern (BCD-Zahlen)

1.5 Gleitpunktzahlen 183

Zahlendarstellung - Computerariffimetik mit Gleitpunktzahlen

Fachwörter und Kurzbezeichnungen 189



2 Informations- und Codierungstheorie - H. Rohling, T. May 191 2.1 Geschichte und Anwendungsbereiche 191

2.2 Informationstheorie 193

14 Inhalt

Nachricht und Information - Entropie - Binärcodierung für eine diskrete Quelle - Kanalkapazität

2.3 Codierungstheorie - Blockcodes 199

Hamming-Verfahren - Algebraische Grundbegriffe - Binäre Gruppencodes - Zyklische Codes - Weitere Codierungstechniken -Spezielle Codierverfahren

2.4 Codierungstheorie - Faltungscodes 211




3 Kryptologie und Datensicherheit - W. Fumy, V. Kessler 217 3.1 Einführung 217

Zur Bedeutung und Geschichte - Kryptoanalytische Angriffe - Perfekte Verschlüsselungssysteme

3.2 Symmetrische Kryptographie 221

Entwurfskriterien - Stromchiffren - Symmetrische Blockchiffren -Betriebsarten - Authentifizierungs-Codes

3.3 Schlüssellose kryptographische Mechanismen 227

Einwegfunktionen - Kryptographische Hashfunktionen

3.4 Asymmetrische Kryptographie 229

Öffentliche und private Schlüssel - RSA - Diskreter Logarithmus in endlichen Gruppen

3.5 Authentifizierung 234

3.6 Schlüsselmanagement 235

Public-key-Infrastruktur - Schlüsselverteilung - Schlüsselhinterlegung/-offenlegung



Normen 237

4 D a t e n k o m p r e s s i o n - M. Durst, M. MUhlhäuser 239

4.1 Grundlagen 239

Übersicht - Modellierung

4.2 Verlustfreie Kompression 242

Huffman-Codierung - Arithmetische Codierung - Lempel-Ziv-Codierungen

4.3 Verlustbehaftete Kompression 247

Zusammenhang mit verlustfreier Kompression - Audiokompression -Festbildkompression - Videokompression



Inhalt 15

Technische Informatik

1 Schaltkreise und digitale Logikschaltungen - R. Hagelauer 257

1.1 Schaltkreise 258

Grundgatter - Grundfunktionen mit NAND- und NOR-Gattera -Logikfamilien - Kenndaten von Logikfamilien

1.2 Schaltnetze 265

Codierschaltungen - Multiplexer/Demultiplexer -Arithmetikschaltungen - Vereinfachung von Schaltfunktionen -Dynamisches Verhalten

1.3 Schaltwerke 271

Endliche Automaten - Realisierung endlicher Automaten -Pegelgesteuerte Flipflops - Flankengesteuerte Flipflops - Beispiele von Schaltwerken

1.4 Programmierbare Logikschaltungen 281

Programmierbare Logikbausteine (PLDs) - Anwenderprogrammierbare Gate-Arrays (FPGAs)

1.5 VLSI-Entwurf 285

Entwurfsablauf - Klassifikation von ASICs (ASIC-Architekturen)




2 Prozessoren - A. Bode 293 2.1 Der Prozessor und seine Teilwerke 293

2.2 Die v. Neumann-Prinzipien der Rechnerorganisation 297

2.3 Technologie 298

2.4 CISC, RISC und Nachfolger 300

CISC - RISC - Kombination von CISC und RISC

2.5 Beispiel eines superskalaren Mikroprozessors 310

2.6 Zukünftige Entwicklungen 312 VLIW - Vielfädigkeit - Multiprozessoren

2.7 Sonderformen von Mikroprozessoren 314

Monolithischer Mikrorechner - Bitslice-Mikroprozessor

2.8 Mikroprogrammierung 314

Mikroprogrammierte Implementierung des Maschinenbefehlszyklus -Mikrobefehlszyklus - Mikroprogrammtechniken - Hilfsmittel für die Entwicklung von Mikroprogrammen



Arbeitsspeicher- und Bussysteme - H. Hellwagner 323 3.1 Speicher- und Bushierarchien 323

3.2 Caches 325

Funktion von Caches - Cache-Typen und Anordnung im Rechensystem -Adressierung von Caches - Organisationsformen -Aktualisierungsstrategie - Ersetzungsstrategie - Leistungsbetrachtungen

3.3 Hauptspeicher 330

Speicherbausteine - Grundlegender Speicheraufbau -Speicherverschränkung - Weitere Maßnahmen zur Leistungssteigerung des Speichers

3.4 Bussysteme 334

Grundlagen von Bussen - Merkmale von Bussen - Busfunktionen -Realisierung von Bussen - Maßnahmen zur Leistungssteigerung von Bussen - Gebräuchliche Bussysteme



Externe Speicher und Peripheriegeräte - W. Proebster, D. Schwarzstein 341

4.1 Magnetische Speicher 342

Grundlagen - Magnetische Plattenspeicher - Magnetische Bandspeicher

4.2 Optische und magnetooptische Speicher 346

CD-ROM und CD-R - Magnetooptische Aufzeichnung und Phasenwechselverfahren

4.3 Eingabegeräte 347

Tastaturen - Maus, Joystick, Rollkugel, Rändelräder - Grafische Tabletts, Digitalisierer - Abtaster - Lichtgriffel, berührungsempfindliche Bildschirme - 6D-Eingabegeräte - Datenhandschuh und Datenanzug

4.4 Anzeigegeräte , 350

Aktive Anzeigen - Passive Anzeigen - Dreidimensionale Anzeigen

4.5 Drucker und Plotter 353

Matrix- und Vollzeichendrucker - Laserdrucker - Tintenstrahldrucker -Thermodrucker - Plotter

4.6 Chipkarten 358


Parallelrechner - J. Volkert 363 5.1 Definition und Klassifikation von Rechnerarchitekturen 363

5.2 Motivation und Einsatzgebiete für Parallelrechner 364

5.3 Verbindungsnetzwerke für Parallelrechner 365

Aufgaben und Merkmale von Verbindungsnetzwerken - Beispiele für dynamische Verbindungsnetzwerke

5.4 SIMD-Maschinen 368

Vektorrechner - Feldrechner

5.5 Multiprozessoren 372

Inhalt 17

Die zwei wesentlichen Klassen von Multiprozessoren -Speichergekoppelte Systeme - Das Cache-Kohärenz-Problem bei Ein-Bus-Systemen - NUMA-Systeme mit verteiltem gemeinsamen Speicher -Hilfsmittel zur Synchronisation in speichergekoppelten Maschinen -Nachrichtengekoppelte Multiprozessoren



6 R e c h n e r n e t z e - B. Plattner, P. Schulthess 381

6.1 Begriffsbestimmung 382

6.2 Weitverkehrsnetze und öffentliche Netze 385

6.3 Übertragungsmedien 386

6.4 Die Bitübertragungsschicht 386

Schnittstellen-Standards - Codierungen - Trägermodulation -Anwendungsfälle

6.5 Die Sicherungsschicht 390

Grundlegende Protokollmechanismen - Medienzuteilung als Teilschicht der Sicherungsebene (MAC-Sublayer) - Anwendungsfälle

6.6 Medienzuteilung auf gemeinsam genutzten Übertragungskanälen 392

Statisches Multiplexverfahren - Tokenvergabe - CSMA-Techniken -Leistungsverhalten lokaler Netze - Anwendungsfälle

6.7 Die Vermittlungsschicht 396

Der Dienst der Vermittlungsschicht - Leitweglenkung - Behandlung von Überlastsituationen - Die Protokollfamilie TCP/IP - OSI-Protokolle der Vermittlungsschicht

6.8 Die Transportschicht 404

Transportprotokolle in TCP/IP - OSI-Transportprotokolle

Abkürzungsverzeichnis 405



7 Leistungsbewertung und Fehlertoleranz - A. Bode, H. Hellwagner . . . 409

7.1 Leistungsbewertung 409

Bedeutung einer quantitativen Betrachtung von Rechnern - Aspekte der Leistungsbewertung - Leistungsmaßzahlen - Methoden der Leistungsbewertung und Lastmodelle

7.2 Fehlertoleranz 416

Übersicht - Grundlagen - Beispiele fehlertoleranter Architekturen



Inhalt

Praktische Informatik

1 Algorithmen und Datenstrukturen - J. Nievergelt 425 1.1 Komplementäre Sichten - Was und Wie 425

Die Sicht des Benutzers: Daten und Operationen - Programmieren als Brücke vom Postulierten zum Gegebenen - Die Sicht des Programmierers: Datenstrukturen und Algorithmen - Verständnis für Grundbegriffe und algorithmisches Denken

1.2 Die Vielfalt möglicher Datenstrukturen 430

1.3 Einfache Datenstrukturen und Zugriffsalgorithmen 432

Der Stapel: Datentyp und Implementierung - Der Stapel als Hochseil für Algorithmenakrobatik - Die Warteschlange, als zirkulärer Puffer implementiert - Suchen im Wörterbuch

1.4 Rechenmodelle und Komplexität 438

Speicher mit Direktzugriff - Probleminstanzen, Problemklassen und Asymptotik - Untere Schranken - Problemreduktion

1.5 Typen von Datenstrukturen 444

Implizite Datenstrukturen, Adreßberechnung - Die Vorrangschlange, als Heap implementiert - Hashing - Verkettete Listen

1.6 Das Zusammenspiel von Algorithmus und Datenstruktur 454

Heapsort: Datenstruktur führt zum Algorithmus - Plane-sweep, Warteschlange, Wörterbuch

1.7 Algorithmik gemäß anderen Spielregeln 459

1.8 Kleines Lexikon der Algorithmik 461

1.9 Bemerkungen und Literaturhinweise 465



2 P r o g r a m m i e r s p r a c h e n - G. Goos, W. Zimmermann 469

2.1 Methodische Grundlagen 471

Abstrakte Datentypen - Grundlegende abstrakte Datentypen -Programmierparadigmen

2.2 Elemente von Programmiersprachen 480

Syntax, Semantik und Pragmatik - Syntaktische Eigenschaften -Semantische Eigenschaften

2.3 Bindungen 483

Lebensdauer und Bindungen - Statische Bindung und Blockstruktur

2.4 Datentypen und Ausdrücke 486

Grundtypen - Zusammengesetzte Typen - Variablen in imperativen Sprachen, Zeigertypen - Vereinigungstypen und polymorphe Typen -Typäquivalenz - Ausdrücke

2.5 Sequentielle Ablaufsteuerung 493

Zuweisungen, bedingte Anweisungen und Schleifen - Prozeduren und Funktionen - Ausnahmen

2.6 Modularität und Objektorientierung 500

Module - Klassen und Objekte - Vererbung - Generizität

Inhalt 19

2.7 Skriptsprachen 507

2.8 Parallelität 511

2.9 Historische Entwicklung von Programmiersprachen 511



3 Prozedurorientierte Programmierung - G. Pomberger 517 3.1 Grundlegende Begriffe 517

3.2 Entwurfs- und Zerlegungstechniken 518

3.3 Prozedurorientierte Zerlegung nach dem Prinzip

der schrittweisen Verfeinerung 520

3.4 Modulbildung - Strukturierung im Großen 523

3.5 Konstruktionen zur Ablaufsteuerung - Strukturierte Programmierung 525


4 Objektorientierte Programmierung - G. Blaschek 529 4.1 Eigenschaften 530

4.2 Begriffe der objektorientierten Programmierung 530

Objekte - Nachrichten - Klassen - Methoden

4.3 Vererbung 533

Ableitung von Klassen - Überschreiben von Methoden - Unterschiede zwischen Basis- und abgeleiteter Klasse - Ist-Beziehungen

4.4 Polymorphie 535

Definition und Zuweisungsregeln - Polymorphie in untypisierten Sprachen - Referenzsemantik - Objekterzeugung - Semantik von Referenzzuweisungen

4.5 Dynamische Bindung 538

Dynamische Bindung durch Methodensuche - Dynamische Bindung mit Methodentabellen - Zusammenspiel von Vererbung, Polymorphie und dynamischer Bindung

4.6 Abstrakte Klassen 540

Faktorisierung - Konkretisierung - Benutzung abstrakter Klassen

4.7 Klassenhierarchien 542

Hierarchie abstrakter Klassen - Wurzelklasse - Mehrfache Vererbung

4.8 Objektorientierte Programmiersprachen 544

4.9 Klassenbibliotheken 545

Bausteinbibliotheken - Strukturierung von Klassenbibliotheken -Rahmenprogramme

4.10 Objektorientierter Entwurf 547

4.11 Besonderheiten 548

Generizität - Prototypen - Kovarianz und Kontravarianz - Separate Schnittstellendefinitionen (Interfaces)

4.12 Vor- und Nachteile der objektorientierten Programmierung 551



Inhalt

5 Funktionale Programmierung - M. Odersky 553 5.1 Funktionale Programmiersprachen 554

5.2 Grundzüge des funktionalen Programmierens 555

Datentypen - Funktionen - Bezug zu abstrakten Datentypen -Polymorphie - Funktionen höherer Ordnung - Listen - Listenfunktionen höherer Ordnung

5.3 Funktionale Komposition 560

Monaden - Beispiele für Monaden

5.4 Implementierung funktionaler Sprachen 563




6 : Logische Programmierung - N. E. Fuchs 567

6.1 Grundlagen 568

Einführung - Definite logische Programme - Resolution - Negation -Prolog

6.2 Programmiertechniken 576

Listen - Metaprogrammierung - Alternative Beweisstrategien - Partielle Auswertung

6.3 Anwendungen 579

Deduktive Datenbanken - Regelbasiertes Programmieren -Computerlinguistik - Softwaretechnik - Logische Programmierung und das Internet

6.4 Andere logische Programmiersprachen 582

Constraint-Programmierung - Induktive logische Programmierung -Logische und funktionale Programmierung - Parallele logische Programmierung



7 Parallele Programmierung - H. Burkhart 587

7.1 Grundkonzepte 588

Sequentialität - Nebenläufigkeit, Parallelismus - Synchronisation -Kommunikation - Fehlersituationen

7.2 Architekturspezifische Programmiermodelle 592

Adele-Erweiterungen für die parallele Programmierung - Übersetzung implizit paralleler Programme - Datenparallelismus - Programmierung mittels gemeinsamem Speicher - Programmierung mittels Nachrichtenaustausch

7.3 Parallele Algorithmen 598

PRAM-Modell - Algorithmen für Prozeßtopologien

7.4 Leistungsaspekte 605

Laufzeit, Rechenleistung, Kommunikationszeit, Bandbreite -Beschleunigung, Effizienz - Amdahl-Gesetz - Gustafson-Barsis-Gesetz - Skalierbarkeit, Isoeffizienz - Beschleunigungs-Anomalien -Leistungsverluste

Inhalt 21

7.5 Parallelprogrammierung in der Praxis 609

Bibliotheken für den Nachrichtenaustausch - Programmieren speichergekoppelter Multiprozessoren - Paralleles Programmieren mit Fortran - Paralleles Programmieren mit Java - Umsetzungen formaler Modelle - Programmierwerkzeuge

7.6 Zukünftige Entwicklungen des parallelen Rechnens 614

Architekturunabhängige Programmiermodelle - Softwaretechnik

paralleler Systeme - Standortunabhängiges Rechnen



8 Visuelle Programmierung - S. Schiffer 619 8.1 Entstehung und Einteilung 619

8.2 Begriffe 621

8.3 Konzepte für VP-Systeme 623

Steuerflußorientierte VP-Systeme - Funktionsorientierte VP-Systeme -Datenflußorientierte VP-Systeme - Objektorientierte VP-Systeme -Einschränkungsorientierte VP-Systeme - Regelorientierte VP-Systeme -Beispielorientierte VP-Systeme - Formularorientierte VP-Systeme -Multiparadigmenorientierte VP-Systeme - Zusammenfassung



9 Betriebssysteme - L. Borrmann 633 9.1 Aufgaben eines Betriebssystems 634

9.2 Prozesse 634

Prozeßverwaltung - Zustandsinformation - Leichtgewichtige Prozesse (threads) - Prozeßsynchronisation - Prozeßkommunikation

9.3 Ablaufplanung (Scheduling) 641

9.4 Speicherverwaltung 644

Virtueller Speicher - Adreßübersetzung in Systemen mit virtuellem

Speicher - Seitenverwaltung in Systemen mit virtuellem Speicher

9.5 Ein-/Ausgabe 652

9.6 Dateisystem 655 Logische Struktur von Dateisystemen - Physische Struktur von Dateisystemen - Entwurfskriterien

9.7 Schutzmechanismen 661

9.8 Bedienschnittstelle 663

Grafische Oberflächen - Kommando-Interpretierer (shell)

9.9 Echtzeitbetriebssysteme 665

9.10 Betriebssysteme für verteilte Rechensysteme 665

Verteilte Dateisysteme - Verteilte Benutzerverwaltung - Verteilter gemeinsamer Speicher

9.11 Betriebssysteme für parallele Rechensysteme 668

9.12 Architektur und Realisierung von Betriebssystemen 669

Verschiedene Arten von Betriebssystem-Architekturen -Betriebssystemaufrufe

Inhalt



10 Verteilte Systeme - M. Mühlhäuser 675 10.1 Grundbegriffe und Besonderheiten 676

10.2 Das OSI-Referenzmodell 677

Architektur - Dateneinheiten - Schichtungsvorschlag -Zusammenfassung, Kritik und weitere Normungsaktivitäten

10.3 Softwaretechnik für Kommunikationsprotokolle 681

10.4 Protokollmechanismen 683

10.5 Anwendungsorientierte Protokolle 686

Die Kommunikationssteuerungsschicht - Die Darstellungsschicht - Die Anwendungsschicht

10.6 Grundlagen der Entwicklung verteilter Anwendungen 695

Grundlegende Ansätze und Paradigmen - Interprozeßkommunikation -Prozedur-Fernaufruf - Verteilter objektorientierter Ansatz - Verwandte und alternative Ansätze

10.7 Plattformen für verteilte Anwendungen 702

DCE und Corba - ROSE und ODP / ANSAware

10.8 Zusammenfassung und Weiterführendes 706

Verzeichnis mehrfach verwendeter Abkürzungen 707



11 Echtzeitsysteme - H. Kopetz 709 11.1 Anforderungen an harte Echtzeitsysteme 710

Rechtzeitigkeit - Verläßlichkeit

11.2 Systemarchitektur 712

Hardwarestruktur - Planbarkeit - Fehlertoleranz

11.3 Echtzeitkommunikation 715

Verläßliche Nachrichtenübertragung - Uhrensynchronisation -Ereignisgesteuerte und zeitgesteuerte Protokolle - Beispiele von Echtzeitprotokollen

11.4 Echtzeitbetriebssystem 718

Organisation der Anwendersoftware - Statische Prozeßeinplanung -Dynamische Einplanung von E-Prozessen - Dynamische Einplanung von K-Prozessen

11.5 Schlußbemerkungen 721



12 Systemsoftware - H. Mössenböck 723 12.1 Editoren 723

Texteditoren - Grafikeditoren

Inhalt 23

12.2 Binder und Lader 727

12.3 Debugger 729

12.4 Browser 732

12.5 Profiler 732

12.6 Automatische Speicherbereinigung 733



Ü b e r s e t z e r - H. Mössenböck 737

13.1 Abgrenzung und Einteilung 737

13.2 Lexikalische Analyse 738

Lexikalische Symbole - Der lexikalische Analysator als endlicher Automat - Implementierung - Spezielle Probleme

13.3 Syntaxanalyse 741

Top-down-Analyse - Bottom-up-Analyse

13.4 Semantikverarbeitung 748

Symbolliste - Zwischensprachen - Attributierte Grammatiken

13.5 Optimierungen 752

13.6 Codeerzeugung 756

Einfache Codeerzeugung - Codeerzeugung mittels Mustervergleich



Softwaretechnik - C. Floyd, H. Züllighoven 763

14.1 Was ist Softwaretechnik? 764

Gegenstand der Softwaretechnik - Sichtweisen der Softwaretechnik -Aufbau dieses Kapitels

14.2 Software und Softwarequaiität 766

Eigenschaften von Software - Vielfalt von Anwendungssoftware -Softwarequalität

14.3 Konzepte für Programmierung und Spezifikation 769

Strukturierte Programmierung - Datenabstraktion - Programmierung im Großen - Formale Spezifikation und Verifikation von Programmen

14.4 Modellierungsmittel und Methoden 771

Modellierungsmittel - Methodenbegriff - Strukturierte Methoden -Objektorientierte Methoden

14.5 Projekte zur Softwareentwicklung 774

Charakteristika von Softwareprojekten - Tätigkeiten bei der Produktentwicklung - Vorgehensmodelle - Evolutionäre Systementwicklung und Prototyping

14.6 Der Softwareentwicklungsprozeß 780

Beteiligte bei der Softwareentwicklung - Leitbilder bei der Softwareentwicklung - Kooperation und Koordination - Produkt- und Konfigurationsverwaltung. - Qualitätssicherung - Sicherung der Prozeßqualität

24 Inhalt

14.7 Architektur von Softwaresystemen 784

Architekturprinzipien - Organisationsformen

14.8 Softwareentwicklungswerkzeuge 786

Allgemeine Literatur ; 788


15 Mensch-Maschine-Kommunikation - G. Blaschek 791 15.1 Begriff 791

15.2 Ergonomische Grundlagen 792

Wahrnehmungsleistung - Motorische Leistung - Sensorische und intuitive Typen von Benutzern - Nachrichtenmodell der Kommunikationspsychologie - Hamburger Verständlichkeitskonzept -Nationale und kulturelle Unterschiede

15.3 Das Schreibtischmodell 796

15.4 Zustände 797

Entstehung von Zuständen - Zustandsräume - Vermeidung von Zuständen - Befehle und Operanden

15.5 Entwurfstechniken 799

Brainstorming - Szenarien - Benutzertest

15.6 Style Guides 800

15.7 Ereignisgesteuerte Programmierung 801

Ereignisschleife - Ereignisbehandlung



Angewandte Informatik

1 Grafische Datenverarbeitung - w. Purgathofer, E. Greller 807

1.1 Begriffsbestimmung und Abgrenzung 808

1.2 Geräte der grafischen Datenverarbeitung 809

1.3 Arbeitsschritte der grafischen Datenverarbeitung 811

1.4 Geometrische Modellierung 812

Modellarten - Kurven und Flächen - Elementarobjekte - Transformation

von Elementarobjekten

1.5 Datenstrukturen 816

1.6 Transformationen, Projektionen, Clipping 820 Window-Viewport-Transformation - Geometrische Transformationen -Projektionen - Clipping

1.7 Objektdarstellung (Rendering) 823

Sichtbarkeitsverfahren - Beleuchtung und Schattierung - Ray-Tracing -Radiosity-Verfahren - Kombinierte Verfahren zur Berechnung der globalen Beleuchtung - Rendering in Echtzeit

Inhalt 25

1.8 Rastergraphik und Behandlung von Rasterbildern 835

Rastergrafik im Vergleich mit Vektorgrafik - Rasterkonversion -Flächenfüllen - Rastertransformation - a-Kanal - Anti-Aliasing -Dithering - Farbquantisierung - Texturen - Rasterbildkompression

1.9 Grafische Programmierung ._ 842

Allgemeines - X-Windows, OSF/Motif und MS Windows -RenderMan - OpenGL, Direct3D - Openlnventor, VRML, Java3D, Performer

1.10 Farbe in der grafischen Datenverarbeitung 845

Farbwahrnehmung - Farbsysteme

1.11 Computeranimation 847

1.12 Visualisierung 848

1.13 Virtuelle Realität 850




2 M u l t i m e d i a - M. Mühlhäuser 855

2.1 Charakteristika, Paradigmen 855

2.2 Grundlegende Konzepte 857

Synchronisation - Dienstgüte - Ströme - Zeitkapseln -Konfigurationsverwaltung

2.3 Handhabung von Multimediadaten 862

Interaktion - Codierung - Codierung von digitalem Video -Speicherung - Interpretation

2.4 Systemunterstützung 868

Netzwerke und Kommunikationsdienste - Betriebssysteme

2.5 Hypertext / Hypermedia 870

Grundbegriffe - Das Dexter-Modell - Weitergehende Aspekte - Das

World-Wide Web als Hypertextsystem



3 Datenbanksysteme - K. Dittrich 875

3.1 Anforderungen und Eigenschaften 876

3.2 Datenmodelle und Datendefinition 877

Konzepte - Das Relationenmodell - Weitere konventionelle Datenmodelle - Datenmodelle mit Objektkonzepten

3.3 Datenzugriff und -manipulation 887

Konzepte - Anfragesprachen - Sichten - Standards

3.4 Steuerung und Überwachung 894

Zugriffsschutz - Konsistenzsicherung - Transaktionen - Verteilung -Speicherverwaltung und Datentransport

26 Inhalt

3.5 Datenbankentwurf 904

3.6 DBMS als Komponenten von Informationssystemarchitekturen 905

3.7 Aktuelle und zukünftige Entwicklung 905



4 Dokumentsuche und Dokumenterschließung - R. Ferber 909 4.1 Problemstellung und Abgrenzung 909

4.2 Boolesche Suche 912

4.3 Erschließungsmethoden 914

Grundformreduktion - Klassifikationen - Thesauren

4.4 Das Vektorraummodell 919

Gewichtungsverfahren - Ähnlichkeitsmaße

4.5 Evaluierung von Suchsystemen 922

Qualitätsmaße Precision und Recall - Testkollektionen und TREC

4.6 Aktuelle Entwicklungen 924

4.7 Suche im World-Wide Web 925

4.8 Digitale Bibliotheken 927

4.9 Ausblick 928



5 Numerisches Rechnen - C. Überhuber 931

5.1 Daten der Numerik 932

5.2 Fehlerbegriffe der Numerik 935

5.3 Kondition mathematischer Probleme 936

5.4 Interpolation 937

5.5 Numerische Integration 941

5.6 Lineare Gleichungssysteme 943

Verfahren für Ausgleichsprobleme - LAPACK - Das fundamentale Softwarepaket für die Lineare Algebra

5.7 Nichtlineare Gleichungen 947

5.8 Numerische Software 951



6 Symbolisches Rechnen - B. Buchberger 955 6.1 Was ist symbolisches Rechnen? 955

Begriffsbestimmung - Abgrenzung

6.2 Mathematische Softwaresysteme aus der Sicht des Benutzers 959

Der Aufbau mathematischer Softwaresysteme - Der mathematische Inhalt symbolischer Softwaresysteme - Beispiele symbolischer Berechnungen -Die wichtigsten symbolischen Softwaresysteme

Inhalt 27

6.3 Die Mathematik hinter den symbolischen Softwaresystemen 964

Zur Algorithmisierung der Mathematik - Der Risch-Algorithmus für die symbolische Integration - Der Algorithmus zur Konstruktion von Gröbner-Basen - Vorzeicheninvariante Zerlegung des rc-dimensionalen reellen Raumes



7 Künstliche Intelligenz - J. Dorn, G. Gottlob 975 7.1 Begriff und Anwendungsgebiete 975

7.2 Wissensrepräsentation 977

Produktionsregeln - Einschränkungen - Unsicheres und vages Wissen -Nichtmonotones Schließen - Objektorientierte Wissensrepräsentation -Qualitatives Wissen - Ereignisorientierte Wissensrepräsentation

7.3 Wissensbasierte Suche 987

Heuristische Suche in Graphen - Heuristische Suche bei Zielkonflikten -Optimierung durch iterative Verbesserung von Lösungen

7.4 Lernen 991

Induktives Schließen - Fallbasiertes Schließen - Neuronale Netze

7.5 Entwicklung von wissensbasierten Systemen 995

7.6 Anwendungen der künstlichen Intelligenz 996



8 Internetdienste - S. Schiffer, J. Tempi 999 8.1 Einführung 999

8.2 Geschichte des Internets 1000

8.3 Internetdienste der Anwendungsschicht 1002

Domain Name System - Electronic Mail - Network News - Electronic Filetransfer - WWW - Weitere Internetdienste und -Protokolle

8.4 Java 1008

Die Programmiersprache Java - Die Java-Bibliothek - Die virtuelle Java-Maschine (JVM) - Sicherheitsmechanismen in Java - Der Netz-Computer (NC)

8.5 Sicherheitsaspekte 1012

Sicherheitslücken - Sicherheitskonzepte



Inhalt

Wirtschaftsinformatik

1 Grundlagen der Wirtschaftsinformatik - L. J. Heinrich 1019 1.1 Information und Kommunikation 1019

1.2 Informationsfunktion und Informationsnachfrage 1020

1.3 Informationssystem und Informationsinfrastruktur 1021

Arten von Informationssystemen - Ziele von Informationssystemen

1.4 Konzepte, Modelle und Modellieren 1025

1.5 Erhebungs- und Erfassungsmethoden 1026 Beobachtung - Befragung - Dokumentenauswertung

1.6 Analysemethoden 1029

Wirtschaftlichkeitsanalyse - Wertanalyse - Kommunikationsanalyse

1.7 Bewertungs- und Evaluierungsmethoden 1031

Nutzwertanalyse - Benchmarking - Checklisten



2 Architektur von Informationssystemen - E. J. Sinz 1035 2.1 Architekturbegriff 1035

2.2 Ein generischer Architekturrahmen zur Gestaltung von Informationssystem-Architekturen 1036

2.3 Ausgewählte Architekturkonzepte 1038

ARIS - Handels-H-Architektur - PROMET - SOM

2.4 Nutzung von Informationssystem-Architekturen 1042

2.5 Qualitätsmerkmale 1044

2.6 Verteilung in Informationssystem-Architekturen 1045


3 Konstruktion von Informationssystemen - E. J. Sinz 1049

3.1 Begriffsbestimmung und Abgrenzung 1049

Betriebliches Informationssystem als Teilsystem der Organisation -Problem der Konstruktion des Informationssystems - Struktur des Informationssystems

3.2 Aufgabenstruktur des Informationssystems 1053

Methoden zur Modellierung der Aufgabenstruktur - Vorgehen bei der Modellierung der Aufgabenstruktur - Werkzeugunterstützung

3.3 Aufbauorganisation 1057

Methoden zur Gestaltung der Aufbauorganisation - Vorgehen bei der Gestaltung der Aufbauorganisation - Werkzeugunterstützung

3.4 Anwendungssysteme 1060

Methoden zur Entwicklung von Anwendungssystemen - Vorgehen bei der Entwicklung und Einführung von Anwendungssystemen -Werkzeugunterstützung

Inhalt 29

3.5 Abstimmung der Komponenten 1063



4 Informationsmanagement - L. J. Heinrich 1065 4.1 Technologiemanagement 1066

Beobachten der Technologieentwicklung - Beeinflussen! der Technologieentwicklung - Planen des Technologiebedarfs - Decken des Technologiebedarfs - Verwalten des Technologiebestands - Bewerten des Technologieeinsatzes

4.2 Projektmanagement 1070

Projektdefinition - Projektorganisation - Vorgehensmodell -Projektplanung - Projektüberwachung - Projektsteuerung -Projektführung - Projektkontrolle

4.3 Produktions- und Problemmanagement 1073

Installation, Wartung und Reparatur der Betriebsmittel - Übernahme von Anwendungssystemen - Produktionsplanung und -Steuerung -Kapazitätsmanagement - Problemmanagement

4.4 Sicherheits- und Katastrophenmanagement 1076

Risikoanalyse - Maßnahmen des Sicherheitsmanagements - Maßnahmen des Katastrophenmanagements

Allgemeine Literatur . . 1080


Normen und Spezifikationen

1 Grundlagen - 1 . Wende 1083

1.1 Technischer Regelungsbedarf in der Informationstechnik 1083

1.2 Normung 1084

Grundsätze - Gremien und Strukturen - Arbeitsprinzipien, Werdegang einer Norm - Normenanwendung

1.3 Spezifikationsentwicklung außerhalb der Normung 1088

Konsortien - Workshops - Spezifikationsentwicklung in Branchen- und Berufsverbänden - Überführung von Spezifikationen in Internationale Normen



2 Normen und Spezifikationen der Informationstechnik ~ I. Wende 1093 2.1 Terminologie 1094

2.2 Zeichensätze und Codierung 1094

2.3 Programmiersprachen und Software-Entwicklung 1096

Programmiersprachen - Software-Entwicklung - Schnittstelle für die Portabilität von Anwendungsprogrammen

30 Inhalt

2.4 Kommunikation und verteilte Verarbeitung 1099

OSI-Referenzmodell - OSI-Grundnormen - Profil-Normen - Internet-Spezifikationen - Verteilte Verarbeitung offener Systeme (ODP-BRM)

2.5 Dokumentverarbeitung und Präsentation von Multimedia-Dokumenten . . . 1102

2.6 Sicherheitsverfahren 1104

2.7 Identifikationskarten 1106

2.8 Ergonomie 1107

2.9 Normen für Anwendungen der Informationstechnik 1108

Normen für den elektronischen Geschäftsverkehr - Normen für die rechnerunterstützte Konstruktion und Fertigung


Die Algorithmenbeschreibungssprache Adele 1111

Abkürzungsverzeichnis 1115

Namenverzeichnis 1121

Stichwortverzeichnis 1133

Documents

Informatik- Handbuch