Paul Levi, Ulrich Rembold
Einführung in die Informatik für Naturwissenschaftler und Ingenieure
Vorwort
6
Inhalt
8
Übersicht über den Inhalt des Buches
18
1 Einführung
28
1.1 Bedeutung der Informatik
28
1.2 Geschichte der Informatik
32
1.2.1 Entstehung der Zahlensysteme
32
1.2.2 Mechanisierung des Rechnens
34
1.2.3 Rein mechanische Rechenmaschinen
36
1.2.4 Datenspeicherung und Programmsteuerung
38
1.2.5 Elektromechanische Rechenmaschinen
41
1.3 Rechnergenerationen: Entwicklung elektronischer Rechenmaschinen
43
1.4 Technologische Entwicklung moderner Mikrorechner
52
1.5 Architekturen von Einzel- und Netzwerkrechnern
58
1.5.1 Architektur eines Einzelrechners
58
1.5.2 Architektur eines Netzwerkrechners
61
2 Grundlagen der Informatik
66
2.1 Information und Kodierung
66
2.1.1 Darstellungen, Zeichen, Worte und Sprachen
66
2.1.2 Binäre Kodierung
70
2.1.3 Dualzahlen und ihre rechnerinternen Darstellungen
76
2.1.4 Informationstheorie
93
2.1.5 Semantik: Effekt der Information
100
2.2 Algorithmen, Berechenbarkeit und Komplexität
102
2.2.1 Algorithmen, Berechenbarkeit und Entscheidbarkeit
103
2.2.2 Datentypen
105
2.2.3 Komplexität und NP-Vollständigkeit
108
2.2.4 Parallelität und Algorithmen
112
2.3 Mathematische Logik
113
2.3.1 Syntax und Semantik der Aussagenlogik
114
2.3.2 Syntax und Semantik der Prädikatenlogik
120
2.4 Boolesche Funktionen, Terme und Schaltwerke
125
2.4.1 Boolesche Funktionen und Ausdrücke
125
2.4.2 Boolesche Algebra
129
2.4.3 Normalformen
130
2.4.4 Schaltnetze und Schaltwerke
135
2.5 Grundbegriffe der Automatentheorie
139
2.5.1 Deterministische endliche Automaten
140
2.5.2 Erkennende und übersetzende endliche Automaten
147
2.5.3 Akzeptierte Sprachen
150
2.5.4 Zelluläre Automaten
152
2.6 Grammatiken und formale Sprachen
154
2.6.1 Grammatik
155
2.6.2 Formale Sprache
159
2.6.3 Chomsky-Grammatiken
160
2.6.4 Sprachklassen und Automaten
161
2.7 Graphen und Bäume
163
2.7.1 Graphen
163
2.7.2 Bäume
168
2.7.3 Ähnlichkeiten von Graphen
172
2.8 Petri-Netze und nebenläu. ge Prozesse
175
2.8.1 Petri-Netze
176
2.8.2 Prozesse und Nebenläu. gkeit
181
3 Datenstrukturen
186
3.1 Konstruktion zusammengesetzter Datenstrukturen: Feld und Verbund
187
3.2 Statische Stapel und Schlangen
189
3.3 Einfache dynamische Datenstruktur: Lineare Liste
190
3.4 Adjazenzlisten für Graphen
193
3.5 Nichtlineare Listen für Bäume und Graphen
195
3.5.1 Rekursive De.nition von Bäumen und Graphen
195
3.5.2 Suchbäume
197
3.6 Relationale Dateien und B-Bäume
198
3.6.1 Relationale Dateien
198
3.6.2 B-Bäume
204
4 Algorithmen und Prozesse
210
4.1 Algorithmen, Programme und Prozesse
210
4.2 Prozessdeklaration und Synchronisation nebenläu . ger Prozesse
213
4.3 Rekursive Programme
215
4.4 Sortieralgorithmen für lineare Felder
216
4.4.1 Sortieren durch Austausch
217
4.4.2 Sortieren durch Einfügen
219
4.4.3 Sortieren durch Verschmelzen
220
4.5 Suchalgorithmen für lineare Felder
221
4.5.1 Sequentielles Suchen
221
4.5.2 Binäres Suchen
221
4.6 Binäre Suchbäume
223
4.7 Operationen auf relationalen Datenbanken
224
4.7.1 Relationenalgebra
224
4.7.2 Assoziative Anfragen
227
4.8 Genetische Algorithmen
229
4.8.1 Grundbegriffe und Operatoren genetischer Algorithmen
231
4.8.2 Ablauf und Anwendung genetischer Algorithmen
233
4.8.3 Konvergenz genetischer Algorithmen: Schemata
235
4.9 Parallelität in Programmen
236
4.9.1 Vektorisierung einer Zählschleife
238
4.9.2 Parallelisierung einer Zählschleife
240
5 Programmiersprachen und -systeme
242
5.1 Einleitung
242
5.2 Maschinennahe Programmiersprachen
243
5.2.1 Aufbau einer Zentraleinheit
244
5.2.2 Maschinensprache
249
5.2.3 Assemblersprache
257
5.3 Höhere Programmiersprachen
282
5.3.1 Imperative Programmiersprachen
285
5.3.2 Logische Programmiersprachen
306
5.3.3 Funktionale Programmiersprachen
309
5.3.4 Objektorientierte Programmiersprachen
312
5.4 Struktur eines Assemblers
316
5.4.1 Aufgaben eines Assemblers
316
5.4.2 Struktur eines Assemblers
321
5.5 Compiler
324
5.5.1 Ablauf der Compilation
324
5.5.2 Lexikalische Analyse
325
5.5.3 Syntaktische Analyse und Aufbau des Syntaxbaumes
327
5.5.4 Semantische Analyse
328
5.5.5 Codegenerierung
329
5.5.6 Codeoptimierung
333
5.6 Interpreter
335
6 Softwareengineering
338
6.1 Einleitung
338
6.1.1 Was ist Softwareengineering?
339
6.1.2 Notwendigkeit einer systemtechnischen Softwarekonstruktion
340
6.2 Softwarephasenmodell
347
6.2.1 Konventionelles Phasenmodell
347
6.2.2 Re-Engineering
349
6.2.3 Das Spiralmodell
350
6.3 Modellierung für die Softwareerstellung
351
6.3.1 Das Modell
351
6.3.2 Datenmodellierung
352
6.3.3 Modellierung von Prozessen
354
6.3.4 Modellierung der Benutzerschnittstelle
355
6.4 Qualitätsanforderungen an eine systematische Softwarekonstruktion
356
6.5 Softwarewerkzeuge
361
6.5.1 Allgemeine Betrachtungen
361
6.5.2 SADT
364
6.5.3 SARS, ein Werkzeug zur Anforderungsspezi. kation
367
6.5.4 EPOS
370
6.5.5 Objektorientiertes Design
372
6.5.6 Modell-basierte Spezi. kation
375
6.6 Ein Softwarelebenszyklus
381
6.6.1 Phasen der Softwarekonstruktion
381
6.6.2 Analyse des Ist- und Sollzustandes
381
6.6.3 De.nition der Anforderungen
382
6.6.4 Grobentwurf
384
6.6.5 Feinentwurf
385
6.6.6 Codierung
385
6.6.7 Integrationstest
386
6.6.8 Wartung und Betrieb
386
6.7 Software-Qualitätssicherung
387
6.7.1 Allgemeine Betrachtungen
387
6.7.2 Lösungsmöglichkeiten zur Qualitätssicherung
388
6.8 Organisation von Softwareprojekten
389
6.8.1 Begriffe
390
6.8.2 Formen des Projektmanagements
390
6.8.3 Hilfsmittel für das Projektmanagement
393
6.8.4 Dokumentation
397
7 Rechnerarchitekturen und digitale Speichermedien
400
7.1 Rechnerstrukturen
401
7.2 Operationsprinzip eines Rechners
407
7.3 Von-Neumann-Rechnerarchitektur
409
7.3.1 Von-Neumann-Operationsprinzip
409
7.3.2 Strukturen eines Von-Neumann-Rechners
413
7.4 Mikroprogrammierung
445
7.5 CISC-, RISC-Prozessoren und deren Nachfolger
452
7.5.1 CISC- und RISC-Prozessoren
452
7.5.2 Kombination von CISC- und RISC-Architekturen
455
7.6 Allgemeine Speichermerkmale und Speicherorganisation
456
7.6.1 Allgemeine Speichermerkmale
456
7.6.2 Speicherorganisation
460
7.7 Halbleiterspeicher
465
7.7.1 ROM-Speicher
467
7.7.2 RAM-Speicher
468
7.8 Optische Plattenspeicher
470
7.9 Magneto-optische Plattenspeicher
474
8 Architektur verteilter Systeme
476
8.1 Verteilte Systeme und verteilte Anwendungen
477
8.2 Verteilte Systeme und Anwendungen
483
8.2.1 Internet
483
8.2.2 Intranet
485
8.2.3 World Wide Web
485
8.2.4 Mobiles und allgegenwärtiges Rechnen
488
8.3 Entwurfskriterien und Bewertung verteilter Systeme
489
8.3.1 Entwurfskriterien für verteilte Systeme
490
8.3.2 Vor- und Nachteile verteilter Systeme
492
8.4 Architekturen verteilter Systeme
493
8.4.1 Operationsprinzipien verteilter Systeme
493
8.5 Strukturen verteilter Systeme
503
8.5.1 Hardware-Strukturen und Hardware-Komponenten verteilter Systeme
504
8.5.2 Software-Struktur verteilter Systeme
515
9 Spezielle Netzwerkdienste und Middleware- Unterstützungen für verteilte Anwendungen
532
9.1 Namendienste
533
9.1.1 Namenraum
533
9.1.2 Namenresolution
536
9.2 Zeitdienste
537
9.2.1 Zeit in verteilten Systemen
538
9.2.2 NTP: Zeitdienst zur externen Uhrensynchronisation im Internet
540
9.3 Sicherheitsdienste
545
9.3.1 Sicherheitskriterien, Bedrohungen und Attacken
546
9.3.2 Sicherheitslücken und Sicherheitsmechanismen
548
9.3.3 Kryptogra. sche Algorithmen
551
9.3.4 Authenti.zierung und Zerti. zierung
560
9.4 Java: verteilte objektorientierte Programmiersprache
567
9.4.1 Netzwerkkonzepte von Java
568
9.4.2 Java-Struktur
578
9.5 CORBA: Architektur für Middleware
580
9.5.1 Netzwerkkonzepte, Merkmale und Terminologie
581
9.5.2 CORBA-Struktur
586
9.6 Exemplarische Anwendungen von Netzwerkdiensten und ihre Auswirkungen
588
9.6 Exemplarische Anwendungen von Netzwerkdiensten
588
9.6.1 Anwendungsfelder und Perspektiven
589
9.6.2 Auswirkungen von Netzwerkdiensten
595
10 Betriebssysteme
600
10.1 Funktionen eines Betriebssystems
601
10.1.1 Betriebsmittel und Betriebsarten
601
10.1.2 Verwaltung und Betrieb
604
10.1.3 Zentrale Betriebssysteme und Betriebssysteme für verteilte Systeme
607
10.2 Operationsprinzip der impliziten, asynchronen Parallelität
610
10.2.1 Funktionseinheiten und ihre Interaktionsmechanismen
610
10.2.2 Synchronisation der Informationsinteraktionen
612
10.2.3 Interaktionsmodell und Interaktionsmuster
613
10.2.4 Kontrollmodell und Parallelität
615
10.2.5 Implizite, asynchrone Parallelität
618
10.3 Grundstrukturen von Betriebssystemen
621
10.3.1 Funktionseinheitenbereich
621
10.3.2 Infrastrukturbereich
625
10.4 Prozesse: Verwaltung und Betrieb
633
10.4.1 Prozesszustände
634
10.4.2 Schwer- und Leichtgewichtprozesse
636
10.4.3 Prozess-Scheduling
640
10.5 Prozessinteraktionen (Interaktionsverwaltung)
647
10.5.1 Synchronisation konkurrierender Prozesse in zentralen und verteilten Systemen
649
10.5.2 Kooperation und synchronisierte Kommunikation in zentralen und verteilten Systemen
656
10.6 Speicherverwaltung
665
10.6.1 Adressräume und Mehrprogrammbetrieb
666
10.6.2 Virtuelle Speicherverwaltung und Seitenadressierung
672
10.6.3 Strategien der Speicherverwaltung
675
10.6.4 Cache-Verwaltung
678
10.6.5 Speicherschutz
682
10.7 Dateisysteme
683
10.7.1 Aufgaben und Grundstruktur eines Dateisystems
684
10.7.2 Logische Organisationsformen von Dateien
689
10.7.3 Reale indexsequentielle Dateiorganisation
692
10.7.4 Datenstrukturen der Dateiverwaltung
693
10.7.5 Verteilte Dateisysteme
696
Literatur
708
Online-Zitate
718
Namen- und Stichwortverzeichnis
720
© 2009-2024 ciando GmbH