Einführung in die Informatik

von: Manfred Sommer, Heinz-Peter Gumm

De Gruyter Oldenbourg, 2006

ISBN: 9783486581157

Sprache: Deutsch

896 Seiten, Download: 65854 KB

Format: PDF, auch als Online-Lesen

geeignet für:

eBook anfordern

▸

Mehr zum Inhalt

Einführung in die Informatik

	Vorwort zur siebten Auflage	6
	Inhalt	8
	1 Einführung	26
	1.1 Was ist „Informatik“?	26
	1.1.1 Technische Informatik	26
	1.1.2 Praktische Informatik	27
	1.1.3 Theoretische Informatik	27
	1.1.4 Angewandte Informatik	28
	1.2 Information und Daten	29
	1.2.1 Bits	30
	1.2.2 Bitfolgen	31
	1.2.3 Hexziffern	32
	1.2.4 Bytes und Worte	33
	1.2.5 Dateien	33
	1.2.6 Datei- und Speichergrößen	34
	1.2.7 Längen- und Zeiteinheiten	35
	1.3 Informationsdarstellung	35
	1.3.1 Text	36
	1.3.2 ASCII-Code	36
	1.3.3 ASCII-Erweiterungen	37
	1.3.4 Unicode, UCS und UTF-8	38
	1.3.5 Zeichenketten	40
	1.3.6 Logische Werte und logische Verknüpfungen	40
	1.3.7 Programme	41
	1.3.8 Bilder und Musikstücke	41
	1.4 Zahlendarstellungen	42
	1.4.1 Binärdarstellung	42
	1.4.2 Das Oktalsystem und das Hexadezimalsystem	43
	1.4.3 Umwandlung in das Binär-, Oktal- oder	44
	Hexadezimalsystem	44
	1.4.5 Darstellung ganzer Zahlen	47
	1.4.6 Die Zweierkomplementdarstellung	48
	1.5 Standardformate für ganze Zahlen	50
	1.5.1 Gleitpunktzahlen: Reelle Zahlen	51
	1.5.2 Real-Zahlenbereiche in Programmiersprachen	54
	1.5.3 Daten – Informationen	55
	1.5.4 Informationsverarbeitung – Datenverarbeitung	56
	1.6 Hardware	56
	1.6.1 PCs, Workstations, Mainframes, Super-Computer	56
	1.6.6 Die Aufgabe der CPU	66
	1.6.7 Die Organisation des Hauptspeichers	68
	1.6.8 Speichermedien	71
	1.6.9 Magnetplatten	72
	1.6.10 Disketten	73
	1.6.11 Festplattenlaufwerk	74
	e	74
	1.6.12 Optische Laufwerke	76
	1.6.15 Text- und Grafikmodus	79
	1.7 Von der Hardware zum Betriebssystem	80
	1.7.1 Schnittstellen und Treiber	82
	1.7.2 BIOS	83
	1.7.3 Die Aufgaben des Betriebssystems	84
	1.7.4 Prozess- und Speicherverwaltung	85
	1.7.5 Dateiverwaltung	85
	1.7.6 DOS, Windows und Linux	88
	1.7.7 Bediensysteme	89
	1.8 Anwendungsprogramme	91
	1.8.1 Textverarbeitung	91
	1.8.2 Zeichen und Schriftarten	92
	1.8.3 Formatierung	93
	1.8.4 Desktop Publishing	94
	1.8.5 Textbeschreibungssprachen	95
	1.8.6 Tabellenkalkulation: spread sheets	99
	1.8.7 Der Rechner als Fenster zur Welt	101
	1.8.8 Wie geht es weiter?	103
	2 Grundlagen der Programmierung	104
	2.1 Programmiersprachen	105
	2.1.1 Vom Programm zur Maschin	105
	e	105
	2.1.2 Virtuelle Maschinen	106
	2.1.3 Interpreter	108
	2.1.4 Programmieren und Testen	108
	2.1.5 Programmierumgebungen	109
	2.1.6 BASIC	110
	2.1.7 Pascal	111
	2.1.8 Java	112
	2.1.9 Prolog	112
	2.2 Spezifikationen, Algorithmen, Programme	114
	2.2.1 Spezifikationen	114
	2.2.2 Algorithmen	116
	2.2.3 Algorithmen als Lösung von Spezifikationen	121
	2.2.4 Terminierung	121
	2.2.5 Elementare Aktionen	122
	2.2.6 Zuweisungen	123
	2.2.7 Vom Algorithmus zum Programm	124
	2.2.8 Ressourcen	126
	2.3 Daten und Datenstrukturen	127
	2.3.1 Der Begriff der Datenstruktur	127
	2.3.2 Boolesche Werte	128
	2.3.3 Zahlen	131
	2.3.4 Natürliche Zahlen	131
	2.3.5 Der Datentyp Integer	133
	2.3.6 Rationale Zahlen	135
	2.3.7 Reelle Zahlen	135
	2.3.8 Mehrsortige Datenstrukturen	136
	2.3.9 Zeichen	138
	2.3.11 Benutzerdefinierte Datenstrukturen	141
	2.3.12 Informationsverarbeitung und Datenverarbeitung	142
	2.4 Speicher, Variablen und Ausdrücke	144
	2.4.1 Deklarationen	145
	2.4.2 Initialisierung	146
	2.4.3 Kontext	146
	e	146
	2.4.4 Ausdrücke, Terme	147
	2.4.5 Auswertung von Ausdrücken	149
	2.4.6 Funktionsdefinitionen	150
	2.4.7 Typfehler	152
	2.4.8 Seiteneffekte	153
	2.5 Der Kern imperativer Sprachen	154
	2.5.1 Zuweisungen	154
	2.5.2 Kontrollstrukturen	156
	2.5.3 Drei Kontrollstrukturen genügen	156
	2.5.4 Die sequentielle Komposition	156
	2.5.5 Die Alternativanweisung	158
	2.5.6 Die while-Schleife	159
	2.5.7 Unterprogramme	160
	2.5.8 Lauffähige Programme	161
	2.6 Formale Beschreibung von Programmiersprachen	162
	2.6.1 Lexikalische Regeln	162
	2.6.2 Syntaktische Regeln	164
	2.6.3 Semantische Regeln	166
	2.7 Erweiterung der Kernsprache	167
	2.7.1 Bedingte Anweisung	167
	2.7.2 Fallunterscheidung	169
	2.7.4 Allgemeinere Schleifenkonstrukte	171
	2.7.5 Die for-Schleife	172
	2.7.6 Arrays – indizierte Variablen	173
	2.8 Rekursive Funktionen und Prozeduren	175
	2.8.1 Rekursive Programme	177
	2.8.2 Die Türme von Hanoi	177
	2.8.3 Spielstrategien als rekursive Prädikate – Backtracking	179
	2.8.4 Wechselseitige Rekursion	180
	2.8.5 Induktion – Rekursion	181
	2.8.6 Allgemeine Rekursion	181
	2.8.7 Endrekursion	183
	2.8.8 Lineare Rekursion	184
	2.8.9 Eine Programmtransformation	186
	2.9 Typen, Module, Klassen und Objekte	187
	2.9.1 Strukturiertes Programmieren	189
	2.9.2 Blockstrukturierung	189
	2.9.3 Strukturierung der Daten	190
	2.9.4 Objektorientierte Konstruktion neuer Datentypen	195
	2.9.5 Modulares Programmieren	197
	2.9.6 Schnittstellen – Interfaces	198
	2.9.7 Objektorientiertes Programmieren	201
	2.9.8 Vererbung	203
	2.9.9 Summentypen in objektorientierten Sprachen	205
	2.10.1 Vermeidung von Fehlern	209
	2.10.2 Zwischenbehauptungen	210
	2.10.3 Partielle Korrektheit	211
	2.10.4 Zerlegung durch Zwischenbehauptungen	212
	2.10.5 Zuweisungsregel	213
	2.10.6 Rückwärtsbeweis	215
	2.10.7 if-else-Regel	217
	2.10.8 Abschwächungsregel und einarmige Alternative	217
	2.10.9 Invarianten und whil	218
	-Regel	218
	2.10.11 Programm-Verifizierer	223
	2.10.12 do-Schleife	225
	2.10.13 Terminierung	226
	2.10.14 Beweis eines Programmschemas	226
	2.11 Zusammenfassung	227
	3 Die Programmiersprache Java	228
	3.1 Geschichte von Java	230
	3.2 Die lexikalischen Elemente von Java	230
	3.2.1 Kommentare	231
	3.2.2 Bezeichner	232
	3.2.3 Schlüsselwörter	232
	3.2.4 Literale	232
	3.3 Datentypen und Methoden	234
	3.3.1 Variablen	234
	3.3.2 Referenz-Datentypen	235
	3.3.3 Arrays	236
	3.3.4 Methoden	237
	3.3.6 Objekte und Referenzen	241
	3.3.7 Objekt- und Klassenkomponenten	242
	3.3.8 Attribute	243
	3.3.9 Überladung	244
	3.3.10 Konstruktoren	245
	3.3.11 Aufzählungstypen	246
	3.4 Ausführbare Java-Programme	247
	3.4.2 Programme	250
	3.4.3 Packages	251
	3.4.4 Standard-Packages	252
	3.5 Ausdrücke und Anweisungen	253
	3.5.1 Arithmetische Operationen	254
	3.5.2 Vergleichsoperationen	254
	3.5.3 Boolesche Operationen	255
	3.5.4 Bitweise Operationen	255
	3.5.5 Zuweisungsausdrücke	256
	3.5.6 Anweisungsausdrück	257
	e	257
	3.5.7 Sonstige Operationen	257
	3.5.8 Präzedenz der Operatoren	258
	3.5.9 Einfache Anweisungen	259
	3.5.10 Blöcke	260
	3.5.11 Alternativ-Anweisungen	261
	3.5.12 switch-Anweisung	261
	3.5.13 Schleifen	263
	3.5.14 Die for-Anweisung	263
	3.5.15 break- und continue-Anweisungen	265
	3.6 Klassen und Objekte	266
	3.6.1 Vererbung	268
	3.6.2 Späte Bindung (Late Binding)	273
	3.6.3 Finale Komponenten	273
	3.6.4 Zugriffsrechte von Feldern und Methoden	274
	3.6.5 Attribute von Klassen	274
	3.6.6 Abstrakte Klassen	275
	3.6.7 Rekursiv definierte Klassen	276
	3.6.8 Schnittstellen (Interfaces)	278
	3.6.9 Generische Datentypen	281
	3.6.10 Ausnahmen - Exceptions	282
	3.6.11 Zusicherungen – Assertions	286
	3.6.12 Threads	290
	3.6.13 Producer-Consumer mit Threads	294
	3.7 Grafische Benutzeroberflächen mit Java (AWT)	296
	3.7.1 Ein erstes Fenster	297
	3.7.2 Ereignisse	298
	3.7.3 Beispiel für eine Ereignisbehandlung	299
	3.7.4 Buttons	301
	3.7.5 Grafikausgabe in Fenstern	302
	3.7.6 Maus-Ereignisse	303
	3.7.7 Paint	306
	3.7.8 Weitere Bedienelemente von Programmen und Fenstern	309
	3.8 Dateien: Ein- und Ausgabe	309
	3.8.1 Dateidialog	309
	3.8.2 Schreiben einer Datei	310
	3.8.3 Lesen einer Datei	311
	3.8.4 Testen von Dateieigenschaften	312
	3.9 Wurzeln und Weiterentwicklung von Java	312
	4 Algorithmen und Datenstrukturen	314
	4.1 Suchalgorithmen	316
	4.1.1 Lineare Suche	317
	4.1.2 Binäre Suche	319
	4.1.3 Lineare Suche vs. binäre Suche	320
	4.1.4 Komplexität von Algorithmen	321
	4.2 Einfache Sortierverfahren	323
	4.2.1 Datensätze und Schlüssel	323
	4.2.2 Invarianten und Assertions	326
	4.2.3 BubbleSort	328
	4.2.4 SelectionSort	330
	4.2.5 InsertionSort	332
	4.2.6 Laufzeitvergleiche der einfachen Sortieralgorithmen	334
	4.2.7 ShellSort und CombSort	335
	4.3 Schnelle Sortieralgorithmen	336
	4.3.1 Divide and Conquer – teile und herrsche	336
	4.3.2 QuickSort	337
	4.3.3 Die Partitionierung	338
	4.3.4 Korrektheit von QuickSort	340
	4.3.5 Komplexität von QuickSort	340
	4.3.6 MergeSort	341
	4.3.7 DistributionSort (RadixSort)	343
	4.3.8 Wieso und wie gut funktioniert DistributionSort?	345
	4.3.9 Einsatz und Implementierung von DistributionSort	345
	4.3.10 Laufzeit der schnellen Sortieralgorithmen	347
	4.3.11 Externes Sortieren	349
	4.4 Abstrakte Datenstrukturen	350
	4.4.1 Datenstruktur = Menge + Operationen	350
	4.4.2 Die axiomatische Methode	350
	4.5 Stacks	351
	4.5.1 Stackoperationen	352
	4.5.2 Implementierung durch ein Array	354
	4.5.3 Implementierung durch eine Liste	355
	4.5.4 Auswertung von Postfix-Ausdrücken	356
	4.5.5 Entrekursivierung	357
	4.5.6 Stackpaare	358
	4.6 Queues, Puffer, Warteschlangen	359
	4.6.1 Implementierung durch ein „zirkuläres“ Array	360
	4.6.2 Implementierung durch eine zirkuläre Liste	362
	4.6.3 Anwendung von Puffern	362
	4.7 Listen	363
	4.7.1 Einfach verkettete Listen	364
	4.7.2 Der Listeniterator forEach	367
	4.7.3 Listen als Verallgemeinerung von Stacks und Queues	368
	4.7.4 Doppelt verkettete Listen	368
	4.7.5 Geordnete Listen und Skip-Listen	369
	4.7.6 Adaptive Listen	370
	4.7.7 Generische Listen	370
	4.7.8 Behälter (Collections)	371
	4.8 Bäume	373
	4.8.1 Beispiele von Bäumen	374
	4.8.2 Binärbäume	375
	4.8.3 Implementierung von Binärbäumen	376
	4.8.4 Traversierungen	377
	4.8.5 Kenngrößen von Binärbäumen	381
	4.8.6 Binäre Suchbäume	382
	4.8.7 Implementierung von binären Suchbäumen	383
	4.8.8 Balancierte Bäume	389
	4.8.9 AVL-Bäume	390
	4.8.10 2-3-4-Bäume	392
	4.8.11 B-Bäume	394
	4.8.12 Vollständige Bäume	395
	4.8.13 Heaps	396
	4.8.14 HeapSort	399
	4.8.15 Priority-Queues	400
	4.8.16 Bäume mit variabler Anzahl von Teilbäumen	400
	4.9 Graphen	401
	4.9.1 Wege und Zusammenhang	402
	4.9.2 Repräsentationen von Graphen	403
	4.9.3 Traversierungen	405
	4.9.4 Tiefensuche und Backtracking	406
	4.9.5 Breitensuche	407
	4.9.6 Transitive Hülle	408
	4.9.7 Kürzeste Wege	409
	4.9.8 Schwere Probleme für Handlungsreisende	412
	4.9.9 Eine Implementierung des TSP	413
	4.10 Zeichenketten	417
	4.10.1 Array-Implementierung	417
	4.10.2 Nullterminierte Strings	417
	4.10.3 Stringoperationen	418
	4.10.4 Suchen in Zeichenketten	419
	4.10.5 Der Boyer-Moore-Algorithmus	419
	5 Rechnerarchitektur	422
	5.1 Vom Transistor zum Chip	422
	5.1.1 Chips	423
	5.1.2 Chipherstellung	424
	5.1.3 Kleinste Chip-Strukturen	425
	5.1.4 Chipfläche und Anzahl der Transistoren	426
	5.1.5 Weitere Chip-Parameter	426
	5.1.6 Speicherbausteine	427
	5.1.7 Logikbausteine	428
	5.1.8 Schaltungsentwurf	428
	5.2 Boolesche Algebra	429
	5.2.1 Serien-parallele Schaltungen	429
	5.2.2 Serien-parallele Schaltglieder	431
	5.2.3 Boolesche Terme	432
	5.2.4 Schaltfunktionen	433
	5.2.5 Gleichungen	433
	5.2.6 SP-Schaltungen sind monoton	434
	5.2.7 Negation	435
	5.2.8 Boolesche Terme	436
	5.2.9 Dualität	437
	5.2.10 Realisierung von Schaltfunktionen	438
	5.2.11 Konjunktive Normalform	439
	5.2.12 Umwandlung in DNF oder KNF	440
	5.2.13 Aussagenlogik	441
	5.2.14 Mengenalgebra	441
	5.3 Digitale Logik	442
	5.3.1 Gatter mit mehreren Ausgängen	445
	5.3.2 Logik-Gitter	447
	5.3.3 Programmierbare Gitterbausteine	449
	5.3.4 Rückgekoppelte Schaltungen	449
	5.3.5 Anwendungen von Flip-Flops	452
	5.3.6 Technische Schwierigkeiten	453
	5.3.7 Die Konstruktion der Hardwarekomponenten	454
	5.3.8 Schalter, Codierer, Decodierer	454
	5.3.9 Speicherzellen	455
	5.3.10 Register	455
	5.3.11 Die Arithmetisch-Logische Einheit	458
	5.4 Von den Schaltgliedern zur CPU	461
	5.4.1 Busse	462
	5.4.2 Mikrocodegesteuerte Operationen	463
	5.4.3 Der Zugang zum Hauptspeicher	466
	5.4.4 Der Mikrobefehlsspeicher – das ROM	468
	5.4.5 Sprünge	468
	5.4.6 Berechnete Sprünge	469
	5.4.7 Der Adressrechner	471
	5.4.8 Ein Mikroprogramm	472
	5.4.9 Maschinenbefehle	473
	5.4.10 Der Maschinenspracheinterpretierer	475
	5.4.11 Argumente	476
	5.5 Assemblerprogrammierung	477
	5.5.1 Maschinensprache und Assembler	477
	5.5.2 Register der 80x86-Familie	478
	5.5.3 Allzweckregister und Spezialregister	480
	5.5.4 Flag-Register	480
	5.5.5 Arithmetische Flags	481
	5.5.6 Größenvergleiche	483
	5.5.7 Logische Operationen	484
	5.5.8 Sprünge	485
	5.5.9 Struktur eines vollständigen Assemblerprogrammes	487
	5.5.10 Ein Beispielprogramm	488
	5.5.11 Testen von Assemblerprogrammen	490
	5.5.12 Speicheradressierung	491
	5.5.13 Operationen auf Speicherblöcken	492
	5.5.14 Multiplikation und Division	493
	5.5.15 Shift-Operationen	494
	5.5.16 LOOP-Befehle	495
	5.5.17 Der Stack	496
	5.5.18 Einfache Unterprogramme	497
	5.5.19 Parameterübergabe und Stack	498
	5.5.20 Prozeduren und Funktionen	500
	5.5.21 Makros	500
	5.5.22 Assembler unter DOS	501
	5.5.23 Assembler unter Windows	503
	5.6 RISC-Architekturen	504
	5.6.1 CISC	504
	5.6.2 Von CISC zu RISC	505
	5.6.3 RISC-Prozessoren	506
	5.6.4 Pipelining	508
	5.6.5 Superskalare Architekturen	509
	5.6.6 Cache-Speicher	509
	5.6.7 Leistungsvergleich	509
	5.6.8 Konkrete RISC-Architekturen	510
	5.7 Architektur der Intel-PC-Mikroprozessorfamilie	513
	5.7.1 Adressierung	518
	5.7.2 Die Segmentierungseinheit	518
	5.7.3 Adressübersetzung	520
	5.7.4 Datenstrukturen und Befehle des Pentium	520
	5.7.5 MMX-Befehle	521
	5.7.6 Betriebsarten des Pentium	521
	5.7.7 Ausblick	522
	6 Betriebssysteme	524
	6.1 Basis-Software	525
	6.2 Betriebsarten	527
	6.2.1 Teilhaberbetrieb	527
	6.2.2 Client-Server-Systeme	527
	6.3 Verwaltung der Ressourcen	529
	6.3.1 Dateisystem	529
	6.3.2 Dateioperationen	530
	6.3.3 Prozesse	531
	6.3.4 Bestandteile eines Prozesses	532
	6.3.5 Threads	532
	6.3.6 Prozessverwaltung	533
	6.3.7 Prozesskommunikation	534
	6.3.8 Kritische Abschnitte – wechselseitiger Ausschluss	535
	6.3.9 Semaphore und Monitore	537
	6.3.10 Deadlocks	539
	6.3.11 Speicherverwaltung	540
	6.4 Das Betriebssystem UNIX	544
	6.4.1 Linux	544
	6.4.2 Das UNIX-Dateisystem	545
	6.4.3 Dateinamen	546
	6.4.4 Dateirechte	546
	6.4.5 Pfade	547
	6.4.6 Special files	548
	6.4.7 Externe Dateisysteme	548
	6.4.8 UNIX-Shells	549
	6.4.9 UNIX-Kommandos	549
	6.4.10 Optionen	550
	6.4.11 Datei-Muster	552
	6.4.12 Standard-Input/Standard-Output	552
	6.4.13 Dateibearbeitung	553
	6.4.14 Reguläre Ausdrücke	554
	6.5 UNIX-Prozesse	555
	6.5.1 Pipes	556
	6.5.2 Sind Pipes notwendig?	557
	6.5.3 Prozess-Steuerung	558
	6.5.4 Multitasking	560
	6.5.5 UNIX-Shell-Programmierung	562
	6.5.6 Die C-Shell	562
	6.5.7 Kommando-Verknüpfungen	563
	6.5.8 Variablen	563
	6.5.9 Shell-Scripts	565
	6.5.10 Ausführung von Shell-Scripts	565
	6.5.11 UNIX-Kommandos und Shell-Kommandos	565
	6.5.12 UNIX als Mehrbenutzersystem	567
	6.5.13 Verbindung zu anderen Rechnern	568
	6.5.14 Weltweiter Rechnerzugang	568
	6.5.15 UNIX-Tools	569
	6.5.16 Editoren	569
	6.5.17 C und C++	571
	6.5.18 Scanner- und Parsergeneratoren	572
	6.5.19 Projektbearbeitung	573
	6.6 X Window System	574
	6.6.1 Window-Manager und Terminal Emulator	575
	6.6.2 Grafische Oberflächen	576
	6.7 MS-DOS und MS-Windows	576
	6.7.1 Dynamic Link Libraries	578
	6.7.2 Object Linking and Embedding	578
	6.7.3 Windows NT, Windows 2000 und Windows XP	579
	6.7.4 Windows XP	580
	6.8 Alternative PC-Betriebssysteme	581
	7 Rechnernetze	584
	7.1 Rechner-Verbindungen	585
	7.1.1 Signalübertragung	585
	7.1.2 Physikalische Verbindung	587
	7.1.3 Synchronisation	589
	7.1.4 Bitcodierungen	590
	7.2 Datenübertragung mit Telefonleitungen	591
	7.2.1 ISDN	592
	7.2.2 DSL, ADSL und T-DSL	593
	7.2.3 ADSL2+	595
	7.3 Protokolle und Netze	595
	7.3.1 Das OSI-Modell	596
	7.3.2 Netze	598
	7.3.3 Netztopologien	599
	7.3.4 Netze von Netzen	601
	7.3.5 Zugriffsverfahren	604
	7.3.6 Wettkampfverfahren: CSMA-CD	604
	7.4 Netztechnologien	606
	7.4.1 Ethernet	606
	7.4.2 FDDI	607
	7.4.3 ATM	607
	7.4.4 SONET/SDH	609
	7.5 Drahtlose Netze	611
	7.5.1 Bluetooth	612
	7.5.2 WLAN	613
	8 Das Internet	620
	8.0.1 Bildung von Standards im Internet	621
	8.1 Die TCP/IP Protokolle	623
	8.1.1 Die Protokolle TCP und UDP	624
	8.1.2 Das IP Protokoll	626
	8.2 IP-Adressen	628
	8.2.1 Adressklassen	629
	8.2.2 Adressübersetzung	631
	8.3 Das System der Domain-Namen	634
	8.3.1 DNS-lookup in Java	637
	8.3.2 Programmierung einer TCP-Verbindung	639
	8.4 Intranets, Firewalls und virtuelle private Netzwerke	643
	8.5 Die Dienste im Internet	645
	8.5.1 E-Mail	646
	8.5.2 News	651
	8.5.3 FTP	651
	8.5.4 Telnet	652
	8.5.5 Gopher	653
	8.6 Das World Wide Web	653
	8.6.1 HTTP	655
	8.6.2 HTML	656
	8.6.3 Die Struktur eines HTML-Dokumentes	659
	8.6.4 Querverweise: Links	660
	8.6.5 Tabellen und Frames	661
	8.6.6 Formulare	663
	8.6.7 Style Sheets	664
	8.6.8 Weitere Möglichkeiten von HTML	665
	8.7 Web-Programmierung	665
	8.7.1 JavaScript	665
	8.7.2 Applets	668
	8.7.3 Die Struktur eines Applets	669
	8.7.4 Der Lebenszyklus eines Applet	670
	8.7.5 Interaktionen	670
	8.7.6 PHP	673
	8.7.7 XML	675
	8.7.8 DOM, Ajax und Web 2.0	684
	9 Theoretische Informatik und Compilerbau	686
	9.1 Analyse von Programmtexten	686
	9.1.1 Lexikalische Analyse	687
	9.1.2 Syntaxanalyse	688
	9.2 Reguläre Sprachen	689
	9.2.1 Reguläre Ausdrücke	690
	9.2.2 Automaten und ihre Sprachen	692
	9.2.3 Implementierung endlicher Automaten	694
	9.2.5 Automaten für reguläre Sprachen	695
	9.2.6 Von nichtdeterministischen zu deterministischen Automaten	696
	9.2.7 Anwendung: flex	697
	9.3 Kontextfreie Sprachen	698
	9.3.1 Kontextfreie Grammatiken	699
	9.3.2 Ableitungen	700
	9.3.3 Stackautomaten (Kellerautomaten)	701
	9.3.4 Stackautomaten für beliebige kontextfreie Sprachen	703
	9.3.5 Nichtdeterministische Algorithmen und Backtracking	703
	9.3.6 Inhärent nichtdeterministische Sprachen	706
	9.3.7 Ableitungsbaum, Syntaxbaum	706
	9.3.8 Abstrakte Syntaxbäume	707
	9.4 Grundlagen des Compilerbaus	708
	9.4.1 Parsen durch rekursiven Abstieg (recursive descent)	709
	9.4.2 LL(1)-Grammatiken	710
	9.4.3 Äquivalente Grammatiken	712
	9.4.4 Top-down und bottom-up	713
	9.4.5 Shift-Reduce Parser	715
	9.4.6 Die Arbeitsweise von Shift-Reduce-Parsern	716
	9.4.7 Bottom-up Parsing	717
	9.4.8 Konflikte	718
	9.4.9 Ein nichtdeterministischer Automat mit Stack	718
	9.4.10 Übergang zum deterministischen Automaten	721
	9.4.11 Präzedenz	723
	9.4.12 LR(1) und LALR(1)	724
	9.4.13 Parsergeneratoren	725
	9.4.14 lex/flex & yacc/bison	726
	9.4.15 Grammatische Aktionen	728
	9.4.16 Fehlererkennung	730
	9.4.17 Synthetisierte Werte	730
	9.4.18 Symboltabellen	731
	9.4.19 Codeoptimierung	731
	9.5 Berechenbarkeit	732
	9.5.1 Berechenbare Funktionen	733
	9.5.2 Beispiele berechenbarer Funktionen	734
	9.5.3 Diagonalisierung	736
	9.5.4 Nicht berechenbare Funktionen	737
	9.5.5 Algorithmenbegriff und Churchsche These	737
	9.5.6 Turingmaschinen	738
	9.5.7 Turing-Post Programme	740
	9.5.8 Turing-berechenbare Funktionen	741
	9.5.9 Registermaschinen	742
	9.5.10 GOTO-Programme	743
	9.5.11 While-Programme	744
	9.5.12 For -Programme ( Loop -Programme)	746
	9.5.13 Effiziente Algorithmen als For-Programme	746
	9.5.14 Elementare (primitive) Rekursion	747
	9.5.15 Allgemeine Rekursion (µ-Rekursion)	749
	9.5.16 Die Ackermannfunktion	750
	9.5.17 Berechenbare Funktionen – Churchsche These	751
	9.5.18 Gödelisierung	751
	9.5.19 Aufzählbarkeit und Entscheidbarkeit	753
	9.5.20 Unlösbare Aufgaben	753
	9.5.21 Semantische Probleme sind unentscheidbar	754
	9.6 Komplexitätstheorie	756
	9.6.1 Rückführung auf ja/nein-Probleme	757
	9.6.2 Entscheidungsprobleme und Sprachen	757
	9.6.3 Maschinenmodelle und Komplexitätsmaße	758
	9.6.4 Sprachen und ihre Komplexität	759
	9.6.5 Effiziente parallele Lösungen	759
	9.6.6 Nichtdeterminismus	761
	9.6.7 Die Klasse NP	762
	9.6.8 Reduzierbarkeit	763
	9.6.9 Der Satz von Cook	765
	9.6.10 NP-Vollständigkeit	767
	9.6.11 CLIQUE ist NP-vollständig	767
	9.6.12 Praktische Anwendung von SAT-Problemen	768
	9.6.13 P = NP ?	771
	10 Datenbanksysteme	772
	10.1 Datenbanken und Datenbanksysteme	772
	10.2 Datenmodelle	774
	10.2.1 Entity/Relationship-Modell	774
	10.2.2 Das Relationale Datenbankmodell	776
	10.2.3 Relationen	777
	10.2.4 Die relationale Algebra	778
	10.2.5 Erweiterungen des relationalen Datenmodells	779
	10.2.6 Abbildung eines E/R-Datenmodells in ein relationales Modell	779
	10.3 Die Anfragesprache SQL	780
	10.3.1 Datendefinition	780
	10.3.2 Einfache Anfragen	782
	10.3.3 Gruppierung und Aggregate	783
	10.3.4 Verknüpfung verschiedener Relationen	784
	10.3.5 Einfügen, Ändern und Löschen von Datensätzen	784
	10.3.6 Mehrbenutzerbetrieb	785
	10.4 Anwendungsprogrammierung in Java	787
	10.4.1 Das SQL-Paket in Java	788
	10.4.2 Aufbau einer Verbindung	789
	10.4.3 Anfragen	789
	10.5 Zusammenfassung	791
	11 Grafikprogrammierung	792
	11.1 Hardware	792
	11.1.1 Auflösungen	793
	11.1.2 Farben	793
	11.2 Grafikroutinen für Rastergrafik	794
	11.2.1 Bresenham Algorithmus	796
	11.3 Einfache Programmierbeispiele	797
	11.3.1 Mandelbrot- und Julia-Mengen	799
	11.3.2 Turtle-Grafik	803
	11.3.3 L-Systeme	807
	11.3.4 Ausblick	810
	11.4 3-D-Grafikprogrammierung	810
	11.4.1 Sichtbarkeit	811
	11.4.2 Beleuchtungsmodelle	812
	11.4.3 Ray-Tracing	815
	11.4.4 Die Radiosity Methode	816
	11.4.5 Ausblick	817
	12 Software-Entwicklung	818
	12.1 Methoden und Werkzeuge für Projekte	819
	12.2 Vorgehensmodelle	821
	12.2.1 Code and fix-Verfahren	821
	12.2.2 Wasserfall-Modelle	822
	12.2.3 Transformations-Modelle	825
	12.2.4 Nichtsequentielle Vorgehensmodelle	825
	12.2.5 Prototyping und Spiralmodelle	826
	12.2.6 Modelle zur inkrementellen Systementwicklung	827
	12.2.7 Evolutionäre Entwicklungsmodelle	827
	12.2.8 Modelle zur objektorientierten Systementwicklung	828
	12.3 Traditionelle Methoden zur Programmentwicklung	830
	12.3.1 Strukturierte Programmierung	830
	12.3.2 Schrittweise Verfeinerung und Top-down-Entwurf	830
	12.3.3 Geheimnisprinzip, Daten-Abstraktion und Modularisierung	831
	12.3.4 Strukturierte Analyse- und Entwurfstechniken	832
	12.3.5 Entity/Relationship-Modellierung	833
	12.3.6 Systematische Test-, Review- und Inspektionsverfahren	834
	12.4 Objektorientierte Software- Entwicklungsmethoden	834
	12.4.1 Prinzipien der Objektorientierung	834
	12.4.2 Objektorientierter Entwurf	835
	12.5 Objektorientierte Analyse und Modellierung	836
	12.5.1 Standardisierung der objektorientierten Modellierung	837
	12.5.2 Die Modellierungssprache UML	837
	12.5.3 Software-Architektur	841
	12.5.4 Entwurfsmuster und Frameworks	842
	12.5.5 Aspekt-orientierte Entwicklung	842
	12.5.6 Modell-getriebene Architektur	843
	12.6 Projekt-Management	844
	12.6.1 Projektinitialisierung und -planung	844
	12.6.2 Projektsteuerung und -koordination	845
	12.6.3 Projektabschluss und -bericht	846
	12.7 Software-Qualitätssicherung	846
	12.7.1 Qualitätsnormen und Zertifizierung	848
	12.8 Werkzeuge und Programmierumgebungen	850
	12.8.1 Klassifizierung von Werkzeugen	850
	12.8.2 Werkzeuge zur Analyse und Modellierung	851
	12.8.3 Werkzeuge für Spezifikation und Entwurf	851
	12.8.4 Programmier-Werkzeuge	852
	12.8.5 Test- und Fehlerbehebungs-Werkzeuge	852
	12.8.6 Tätigkeitsübergreifende Werkzeuge	854
	12.8.7 Entwicklungs-Umgebungen	855
	A Literatur	858
	A.1 Einführende Bücher	858
	A.2 Lehrbücher der Informatik	859
	A.3 Programmieren in Pascal	860
	A.4 Programmieren in Java	860
	A.5 Algorithmen und Datenstrukturen	861
	A.6 Rechnerarchitektur	862
	A.7 Betriebssysteme	863
	A.8 Rechnernetze	863
	A.9 Internet	864
	A.10 Theoretische Informatik und Compilerbau	865
	A.11 Datenbanken	866
	A.12 Grafikprogrammierung	867
	A.13 Software-Entwicklung	868
	A.14 Mathematischer Hintergrund	871
	A.15 Sonstiges	871
	Stichwortverzeichnis	872
	Mehr eBooks bei www.ciando.com	0

Einführung in die Informatik

von: Manfred Sommer, Heinz-Peter Gumm

Einführung in die Informatik

Kategorien

eBooks