Sie sind hier
E-Book

Einführung in die Informatik für Naturwissenschaftler und Ingenieure

AutorPaul Levi, Ulrich Rembold
VerlagCarl Hanser Fachbuchverlag
Erscheinungsjahr2003
Seitenanzahl737 Seiten
ISBN9783446223950
FormatPDF
KopierschutzWasserzeichen/DRM
GerätePC/MAC/eReader/Tablet
Preis23,99 EUR

Grundlagenwissen im Bereich Informatik
Es gibt kaum ein technisches oder naturwissenschaftliches Problem, das nicht von der Informatik beeinflusst wird. Deshalb gehören die Grundlagen der Informatik längst zu den Studieninhalten von Natur- und Ingenieurwissenschaften.
Dieses bewährte Lehrbuch bietet eine umfassende Einführung in die Informatik, die den Erfordernissen dieser Studiengänge entspricht und auf die Anforderungen in der Praxis ausgerichtet ist.
Die Autoren erläutern die grundlegenden Konzepte, um den Studenten ein Grundverständnis zu vermitteln, das sie auf sich ständig erneuernde Technologien übertragen können. Durch die modulare Struktur der Kapitel kann sich der Leser je nach Vorkenntnissen den gewünschten Stoff selbst zusammenstellen und auch zum Selbststudium nutzen.   

Kaufen Sie hier:

Horizontale Tabs

Kapitelübersicht
  1. Vorwort und Übersicht über den Inhalt des Buches
  2. 1 Einführung
  3. 2 Grundlagen der Informatik
  4. 3 Datenstrukturen
  5. 4 Algorithmen und Prozesse
  6. 5 Programmiersprachen und -systeme
  7. 6 Softwareengineering
  8. 7 Rechnerarchitekturen und digitale Speichermedien
  9. 8 Architektur verteilter Systeme
  10. 9 Spezielle Netzwerkdienste und Middleware-Unterstützungen für verteilte Anwendungen
  11. 10 Betriebssysteme
  12. Literatur und Online-Zitate
  13. Namen- und Stichwortverzeichnis
Leseprobe

3 Datenstrukturen (S. 169-170)

Algorithmen, sei es in Form von Programmen oder Prozessen, arbeiten stets mit Daten [Mehlhorn 86]. Diese Daten können einfach und wenig strukturiert oder komplex und stark strukturiert sein. Daten, denen eine de.nierende Struktur aufgeprägt wurde, heißen Datenstrukturen. Einfache Datenstrukturen sind Stapel und Schlangen (Abschn. 3.2) und lineare Listen (Abschn. 3.3). Bäume, Graphen und relationale Dateien stellen komplexe Datenstrukturen (Abschn. 3.5 und 3.6) dar. Diese werden wiederum durch einfachere Datenstrukturen implementiert. So werden beispielsweise Graphen üblicherweise durch Adjazenzlisten repräsentiert (Abschn. 3.4).

Die einfachen Datenstrukturen Stapel und Schlangen werden mit Hilfe zusammengesetzter Datenstrukturen aufgebaut. Felder (engl. arrays) und Verbunde (engl. records) sind typische Vertreter solcher zusammengesetzten Datenstrukturen (Abschn. 3.1, Abschn. 5.3.1.5). Die Elemente zusammengesetzter Datenstrukturen sind jedoch nicht von einem beliebigen Datentyp, der den erlaubten Wertebereich vorgibt, sondern sie gehören Grundtypen wie z. B. integer oder real an (Abschn. 5.3.1.4).

Naturgemäß besteht ein enger Zusammenhang zwischen dem verwendeten Algorithmus und der dafür am geeignetsten Datenstruktur. Wegen dieser engen Kopplung wurden Datentypen (Abschn. 2.2.2) eingeführt. Es besteht jedoch ein deutlicher Unterschied zwischen einer Datenstruktur und einem darauf arbeitenden Datentyp, obwohl häufig beide Begriffe gleichbedeutend verwendet werden. Ein Datentyp enthält nicht nur eine Datenstruktur, sondern er umfasst gleichzeitig die Menge der dazugehörenden Operationen.

Aus Sicht der objektorientierten Programmierung ist eine Datenstruktur noch kein Objekt, denn es muss die folgenden Bedingungen erfüllen (Abschn. 5.3.4): Ein solches Objekt vereinigt in sich nicht nur eine Datenstruktur und die dazugehörenden Operationen, sondern es wechselwirkt mit anderen Objekten durch Nachrichtenaustausch und es kann seine Variablen und Operationen vererben.

In diesem Kapitel konzentrieren wir uns auf die am häu.gsten gebrauchten Datenstrukturen. Die zugehörigen Algorithmen werden im nächsten Kapitel vorgestellt. Neben der Klassi.kation der Datenstrukturen nach ihrer Komplexität, d.h. ihrer internen Struktur, benutzen wir noch die Begriffe der statischen und dynamischen Datenstrukturen, um dieses Kapitel einzuteilen.

Wir sprechen von einer statischen Datenstruktur, wenn sie während ihrer gesamten Lebensdauer ihre Struktur oder Beziehung zu anderen Datenstruktur-Elementen und Größe beibehält. Die in den ersten beiden Abschnitten besprochenen Datenstrukturen sind statisch. In den restlichen Abschnitten werden dynamische Datenstrukturen behandelt.

Eine Datenstruktur heißt dynamisch, wenn sie sich während der Programmausführung verändert. Diese Veränderungen können sich dabei nur auf ihre Struktur und Größe beziehen, aber auch ihre Erzeugung bzw. Vernichtung beinhalten. Typisch für dynamische Datenstrukturen ist, dass sie während ihrer Lebenszeit wachsen und schrumpfen. Beispiele für solche Datenstrukturen sind lineare Listen, Bäume und Graphen. Sie alle werden durch Elemente, die durch Zeiger verkettet sind, implementiert.

3.1 Konstruktion zusammengesetzter Datenstrukturen: Feld und Verbund
Zusammengesetzte Datenstrukturen werden üblicherweise konstruktiv aufgebaut [Nievergelt, Hinrichs 93], [Ottmann, Widmayer 96]. Die meisten höheren Programmiersprachen bieten dafür Konstruktoren als Schlüsselworte, wie z.B. array, an. Bei der Aufzählung solcher Konstruktoren orientieren wir uns, auch in der Notation, an OBERON, der Nachfolgesprache von PASCAL [Reiser, Wirth 94]. Es werden die beiden elementaren Datenstrukturen Feld und Verbund beschrieben.

Feld. Die Datenstruktur Feld entsteht durch das Aneinanderreihen gleichartiger Elemente, wobei die Reihenfolge dieser Elemente wichtig ist. Diese statische Datenstruktur wird in einem Programm in einer Vereinbarung, auch Deklaration genannt, mit Hilfe des Konstruktes array de.niert. Dabei wird üblicherweise ein Feld von einem ganz bestimmten Typ mit einem Bezeichner explizit vereinbart.

Inhaltsverzeichnis
Vorwort6
Inhalt8
Übersicht über den Inhalt des Buches18
1 Einführung28
1.1 Bedeutung der Informatik28
1.2 Geschichte der Informatik32
1.2.1 Entstehung der Zahlensysteme32
1.2.2 Mechanisierung des Rechnens34
1.2.3 Rein mechanische Rechenmaschinen36
1.2.4 Datenspeicherung und Programmsteuerung38
1.2.5 Elektromechanische Rechenmaschinen41
1.3 Rechnergenerationen: Entwicklung elektronischer Rechenmaschinen43
1.4 Technologische Entwicklung moderner Mikrorechner52
1.5 Architekturen von Einzel- und Netzwerkrechnern58
1.5.1 Architektur eines Einzelrechners58
1.5.2 Architektur eines Netzwerkrechners61
2 Grundlagen der Informatik66
2.1 Information und Kodierung66
2.1.1 Darstellungen, Zeichen, Worte und Sprachen66
2.1.2 Binäre Kodierung70
2.1.3 Dualzahlen und ihre rechnerinternen Darstellungen76
2.1.4 Informationstheorie93
2.1.5 Semantik: Effekt der Information100
2.2 Algorithmen, Berechenbarkeit und Komplexität102
2.2.1 Algorithmen, Berechenbarkeit und Entscheidbarkeit103
2.2.2 Datentypen105
2.2.3 Komplexität und NP-Vollständigkeit108
2.2.4 Parallelität und Algorithmen112
2.3 Mathematische Logik113
2.3.1 Syntax und Semantik der Aussagenlogik114
2.3.2 Syntax und Semantik der Prädikatenlogik120
2.4 Boolesche Funktionen, Terme und Schaltwerke125
2.4.1 Boolesche Funktionen und Ausdrücke125
2.4.2 Boolesche Algebra129
2.4.3 Normalformen130
2.4.4 Schaltnetze und Schaltwerke135
2.5 Grundbegriffe der Automatentheorie139
2.5.1 Deterministische endliche Automaten140
2.5.2 Erkennende und übersetzende endliche Automaten147
2.5.3 Akzeptierte Sprachen150
2.5.4 Zelluläre Automaten152
2.6 Grammatiken und formale Sprachen154
2.6.1 Grammatik155
2.6.2 Formale Sprache159
2.6.3 Chomsky-Grammatiken160
2.6.4 Sprachklassen und Automaten161
2.7 Graphen und Bäume163
2.7.1 Graphen163
2.7.2 Bäume168
2.7.3 Ähnlichkeiten von Graphen172
2.8 Petri-Netze und nebenläu. ge Prozesse175
2.8.1 Petri-Netze176
2.8.2 Prozesse und Nebenläu. gkeit181
3 Datenstrukturen186
3.1 Konstruktion zusammengesetzter Datenstrukturen: Feld und Verbund187
3.2 Statische Stapel und Schlangen189
3.3 Einfache dynamische Datenstruktur: Lineare Liste190
3.4 Adjazenzlisten für Graphen193
3.5 Nichtlineare Listen für Bäume und Graphen195
3.5.1 Rekursive De.nition von Bäumen und Graphen195
3.5.2 Suchbäume197
3.6 Relationale Dateien und B-Bäume198
3.6.1 Relationale Dateien198
3.6.2 B-Bäume204
4 Algorithmen und Prozesse210
4.1 Algorithmen, Programme und Prozesse210
4.2 Prozessdeklaration und Synchronisation nebenläu . ger Prozesse213
4.3 Rekursive Programme215
4.4 Sortieralgorithmen für lineare Felder216
4.4.1 Sortieren durch Austausch217
4.4.2 Sortieren durch Einfügen219
4.4.3 Sortieren durch Verschmelzen220
4.5 Suchalgorithmen für lineare Felder221
4.5.1 Sequentielles Suchen221
4.5.2 Binäres Suchen221
4.6 Binäre Suchbäume223
4.7 Operationen auf relationalen Datenbanken224
4.7.1 Relationenalgebra224
4.7.2 Assoziative Anfragen227
4.8 Genetische Algorithmen229
4.8.1 Grundbegriffe und Operatoren genetischer Algorithmen231
4.8.2 Ablauf und Anwendung genetischer Algorithmen233
4.8.3 Konvergenz genetischer Algorithmen: Schemata235
4.9 Parallelität in Programmen236
4.9.1 Vektorisierung einer Zählschleife238
4.9.2 Parallelisierung einer Zählschleife240
5 Programmiersprachen und -systeme242
5.1 Einleitung242
5.2 Maschinennahe Programmiersprachen243
5.2.1 Aufbau einer Zentraleinheit244
5.2.2 Maschinensprache249
5.2.3 Assemblersprache257
5.3 Höhere Programmiersprachen282
5.3.1 Imperative Programmiersprachen285
5.3.2 Logische Programmiersprachen306
5.3.3 Funktionale Programmiersprachen309
5.3.4 Objektorientierte Programmiersprachen312
5.4 Struktur eines Assemblers316
5.4.1 Aufgaben eines Assemblers316
5.4.2 Struktur eines Assemblers321
5.5 Compiler324
5.5.1 Ablauf der Compilation324
5.5.2 Lexikalische Analyse325
5.5.3 Syntaktische Analyse und Aufbau des Syntaxbaumes327
5.5.4 Semantische Analyse328
5.5.5 Codegenerierung329
5.5.6 Codeoptimierung333
5.6 Interpreter335
6 Softwareengineering338
6.1 Einleitung338
6.1.1 Was ist Softwareengineering?339
6.1.2 Notwendigkeit einer systemtechnischen Softwarekonstruktion340
6.2 Softwarephasenmodell347
6.2.1 Konventionelles Phasenmodell347
6.2.2 Re-Engineering349
6.2.3 Das Spiralmodell350
6.3 Modellierung für die Softwareerstellung351
6.3.1 Das Modell351
6.3.2 Datenmodellierung352
6.3.3 Modellierung von Prozessen354
6.3.4 Modellierung der Benutzerschnittstelle355
6.4 Qualitätsanforderungen an eine systematische Softwarekonstruktion356
6.5 Softwarewerkzeuge361
6.5.1 Allgemeine Betrachtungen361
6.5.2 SADT364
6.5.3 SARS, ein Werkzeug zur Anforderungsspezi. kation367
6.5.4 EPOS370
6.5.5 Objektorientiertes Design372
6.5.6 Modell-basierte Spezi. kation375
6.6 Ein Softwarelebenszyklus381
6.6.1 Phasen der Softwarekonstruktion381
6.6.2 Analyse des Ist- und Sollzustandes381
6.6.3 De.nition der Anforderungen382
6.6.4 Grobentwurf384
6.6.5 Feinentwurf385
6.6.6 Codierung385
6.6.7 Integrationstest386
6.6.8 Wartung und Betrieb386
6.7 Software-Qualitätssicherung387
6.7.1 Allgemeine Betrachtungen387
6.7.2 Lösungsmöglichkeiten zur Qualitätssicherung388
6.8 Organisation von Softwareprojekten389
6.8.1 Begriffe390
6.8.2 Formen des Projektmanagements390
6.8.3 Hilfsmittel für das Projektmanagement393
6.8.4 Dokumentation397
7 Rechnerarchitekturen und digitale Speichermedien400
7.1 Rechnerstrukturen401
7.2 Operationsprinzip eines Rechners407
7.3 Von-Neumann-Rechnerarchitektur409
7.3.1 Von-Neumann-Operationsprinzip409
7.3.2 Strukturen eines Von-Neumann-Rechners413
7.4 Mikroprogrammierung445
7.5 CISC-, RISC-Prozessoren und deren Nachfolger452
7.5.1 CISC- und RISC-Prozessoren452
7.5.2 Kombination von CISC- und RISC-Architekturen455
7.6 Allgemeine Speichermerkmale und Speicherorganisation456
7.6.1 Allgemeine Speichermerkmale456
7.6.2 Speicherorganisation460
7.7 Halbleiterspeicher465
7.7.1 ROM-Speicher467
7.7.2 RAM-Speicher468
7.8 Optische Plattenspeicher470
7.9 Magneto-optische Plattenspeicher474
8 Architektur verteilter Systeme476
8.1 Verteilte Systeme und verteilte Anwendungen477
8.2 Verteilte Systeme und Anwendungen483
8.2.1 Internet483
8.2.2 Intranet485
8.2.3 World Wide Web485
8.2.4 Mobiles und allgegenwärtiges Rechnen488
8.3 Entwurfskriterien und Bewertung verteilter Systeme489
8.3.1 Entwurfskriterien für verteilte Systeme490
8.3.2 Vor- und Nachteile verteilter Systeme492
8.4 Architekturen verteilter Systeme493
8.4.1 Operationsprinzipien verteilter Systeme493
8.5 Strukturen verteilter Systeme503
8.5.1 Hardware-Strukturen und Hardware-Komponenten verteilter Systeme504
8.5.2 Software-Struktur verteilter Systeme515
9 Spezielle Netzwerkdienste und Middleware- Unterstützungen für verteilte Anwendungen532
9.1 Namendienste533
9.1.1 Namenraum533
9.1.2 Namenresolution536
9.2 Zeitdienste537
9.2.1 Zeit in verteilten Systemen538
9.2.2 NTP: Zeitdienst zur externen Uhrensynchronisation im Internet540
9.3 Sicherheitsdienste545
9.3.1 Sicherheitskriterien, Bedrohungen und Attacken546
9.3.2 Sicherheitslücken und Sicherheitsmechanismen548
9.3.3 Kryptogra. sche Algorithmen551
9.3.4 Authenti.zierung und Zerti. zierung560
9.4 Java: verteilte objektorientierte Programmiersprache567
9.4.1 Netzwerkkonzepte von Java568
9.4.2 Java-Struktur578
9.5 CORBA: Architektur für Middleware580
9.5.1 Netzwerkkonzepte, Merkmale und Terminologie581
9.5.2 CORBA-Struktur586
9.6 Exemplarische Anwendungen von Netzwerkdiensten und ihre Auswirkungen588
9.6 Exemplarische Anwendungen von Netzwerkdiensten588
9.6.1 Anwendungsfelder und Perspektiven589
9.6.2 Auswirkungen von Netzwerkdiensten595
10 Betriebssysteme600
10.1 Funktionen eines Betriebssystems601
10.1.1 Betriebsmittel und Betriebsarten601
10.1.2 Verwaltung und Betrieb604
10.1.3 Zentrale Betriebssysteme und Betriebssysteme für verteilte Systeme607
10.2 Operationsprinzip der impliziten, asynchronen Parallelität610
10.2.1 Funktionseinheiten und ihre Interaktionsmechanismen610
10.2.2 Synchronisation der Informationsinteraktionen612
10.2.3 Interaktionsmodell und Interaktionsmuster613
10.2.4 Kontrollmodell und Parallelität615
10.2.5 Implizite, asynchrone Parallelität618
10.3 Grundstrukturen von Betriebssystemen621
10.3.1 Funktionseinheitenbereich621
10.3.2 Infrastrukturbereich625
10.4 Prozesse: Verwaltung und Betrieb633
10.4.1 Prozesszustände634
10.4.2 Schwer- und Leichtgewichtprozesse636
10.4.3 Prozess-Scheduling640
10.5 Prozessinteraktionen (Interaktionsverwaltung)647
10.5.1 Synchronisation konkurrierender Prozesse in zentralen und verteilten Systemen649
10.5.2 Kooperation und synchronisierte Kommunikation in zentralen und verteilten Systemen656
10.6 Speicherverwaltung665
10.6.1 Adressräume und Mehrprogrammbetrieb666
10.6.2 Virtuelle Speicherverwaltung und Seitenadressierung672
10.6.3 Strategien der Speicherverwaltung675
10.6.4 Cache-Verwaltung678
10.6.5 Speicherschutz682
10.7 Dateisysteme683
10.7.1 Aufgaben und Grundstruktur eines Dateisystems684
10.7.2 Logische Organisationsformen von Dateien689
10.7.3 Reale indexsequentielle Dateiorganisation692
10.7.4 Datenstrukturen der Dateiverwaltung693
10.7.5 Verteilte Dateisysteme696
Literatur708
Online-Zitate718
Namen- und Stichwortverzeichnis720

Weitere E-Books zum Thema: Studienliteratur MINT

Lexikon der Informatik

E-Book Lexikon der Informatik
Format: PDF

Für den sicheren und kompetenten Umgang mit den Begriffen der Informatik: Die Auswahl der über 6000 Kurzdefinitionen unter mehr als 5000 Stichworten ist repräsentativ und aktuell. Die Autoren…

Lexikon der Informatik

E-Book Lexikon der Informatik
Format: PDF

Für den sicheren und kompetenten Umgang mit den Begriffen der Informatik: Die Auswahl der über 6000 Kurzdefinitionen unter mehr als 5000 Stichworten ist repräsentativ und aktuell. Die Autoren…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Weitere Zeitschriften

BIELEFELD GEHT AUS

BIELEFELD GEHT AUS

Freizeit- und Gastronomieführer mit umfangreichem Serviceteil, mehr als 700 Tipps und Adressen für Tag- und Nachtschwärmer Bielefeld genießen Westfälisch und weltoffen – das zeichnet nicht ...

caritas

caritas

mitteilungen für die Erzdiözese FreiburgUm Kindern aus armen Familien gute Perspektiven für eine eigenständige Lebensführung zu ermöglichen, muss die Kinderarmut in Deutschland nachhaltig ...

Deutsche Hockey Zeitung

Deutsche Hockey Zeitung

Informiert über das internationale, nationale und internationale Hockey. Die Deutsche Hockeyzeitung ist Ihr kompetenter Partner für Ihr Wirken im Hockeymarkt. Sie ist die einzige ...

ea evangelische aspekte

ea evangelische aspekte

evangelische Beiträge zum Leben in Kirche und Gesellschaft Die Evangelische Akademikerschaft in Deutschland ist Herausgeberin der Zeitschrift evangelische aspekte Sie erscheint viermal im Jahr. In ...

Evangelische Theologie

Evangelische Theologie

 Über »Evangelische Theologie« In interdisziplinären Themenheften gibt die Evangelische Theologie entscheidende Impulse, die komplexe Einheit der Theologie wahrzunehmen. Neben den ...