Grundkurs Informatik: Grundlagen und Konzepte für die erfolgreiche IT-Praxis - Eine umfassende Einführung

Vorwort
Webseite, Hinweise, Errata
Inhaltsverzeichnis
Kapitel 1 Einführung
1.1 Was ist eigentlich Informatik?
1.2 Zur Geschichte der Informatik
1.2.1 Frühe Zähl- und Rechensysteme
1.2.2 Die Entwicklung von Rechenmaschinen
1.2.3 Die Computer-Generationen
1.3 Prinzipieller Aufbau von Computern
1.3.1 Zentraleinheit und Busstruktur
1.3.2 Systemkomponenten
1.4 Zahlensysteme und binäre Arithmetik
1.4.1 Darstellung von Zahlen
1.4.2 Umwandlung von Zahlen in verschiedene Darstellungssysteme
1.4.3 Binäre Arithmetik
1.4.4 Gleitkommazahlen
Literatur
Kapitel 2 Nachricht und Information
2.1 Abgrenzung der Begriffe Nachricht und Information
2.2 Biologische Aspekte
2.2.1 Sinnesorgane
2.2.2 Datenverarbeitung im Gehirn
2.2.3 Der genetische Code
2.3 Diskretisierung von Nachrichten
2.3.1 Abtastung
2.3.2 Quantisierung
2.4 Wahrscheinlichkeit und Kombinatorik
2.4.1 Die relative Häufigkeit
2.4.2 Die mathematische Wahrscheinlichkeit
2.4.3 Totale Wahrscheinlichkeit und Bayes-Formel
2.4.4 Statistische Kenngrößen
2.4.5 Fakultät und Binomialkoeffizienten
2.4.6 Kombinatorik
2.5 Information und Wahrscheinlichkeit
2.5.1 Der Informationsgehalt einer Nachricht
2.5.2 Die Entropie einer Nachricht
2.5.3 Zusammenhang mit der physikalischen Entropie
Literatur
Kapitel 3 Codierung
3.1 Grundbegriffe
3.1.1 Mittlere Wortlänge und Code-Redundanz
3.1.2 Beispiele für Codes
3.2 Quellencodierung und Datenkompression
3.2.1 Codebäume
3.2.2 Der Huffman-Algorithmus
3.2.3 Der Fano-Algorithmus
3.2.4 Arithmetische Codierung
3.2.5 Lauflängen-Codierung
3.2.6 Differenz-Codierung
3.2.7 Der LZW-Algorithmus
3.2.8 Datenreduktion durch unitäre Transformationen (JPEG)
3.3 Codesicherung und Kanalcodierung
3.3.1 Hamming-Distanz
3.3.2 m-aus-n-Codes
3.3.3 Codes mit Paritätsbits
3.3.4 Fehlertolerante Gray-Codes
3.3.5 Definition linearer Codes
3.3.6 Lineare Hamming-Codes
3.3.7 Zyklische Codes und Code-Polynome
3.3.8 CRC-Codes
3.3.9 Sicherung nicht-binärer Codes
3.3.10 Reed-Solomon Codes
Literatur
Kapitel 4 Verschlüsselung
4.1 Klassische Verfahren
4.1.1 Der Cäsar-Code
4.1.2 Vigenère-Codes
4.1.3 Affine Substitutions-Chiffren und Enigma
4.2 Moderne symmetrische Verfahren
4.2.1 Der Data Encryption Standard (DES)
4.2.2 Der Advanced Encryption Standard (AES)
4.2.3 One-Time-Pads und Stromchiffren
4.3 Moderne asymmetrische Verfahren
4.3.1 Diffie-Hellman Schlüsselaustausch
4.3.2 Der RSA-Algorithmus
4.3.3 Digitale Unterschrift
4.3.4 Elliptische-Kurven-Kryptographie
4.4 Kryptographische Hashfunktionen
4.5 Sicherheitsniveau und Empfehlungen
4.6 Quantencomputer und Kryptographie
4.6.1 Was ist ein Quantencomputer?
4.6.2 Auswirkungen auf kryptographische Verfahren
Literatur
Kapitel 5 Computerhardware und Maschinensprache
5.1 Digitale Grundschaltungen
5.1.1 Stromkreise
5.1.2 Dioden, Transistoren und integrierte Schaltkreise
5.1.3 Logische Gatter
5.2 Boolesche Algebra und Schaltfunktionen
5.2.1 Aussagenlogik
5.2.2 Der boolesche Verband
5.2.3 Das boolesche Normalform-Theorem
5.2.4 Vereinfachen boolescher Ausdrücke
5.3 Schaltnetze und Schaltwerke
5.3.1 Schaltnetze
5.3.2 Spezielle Schaltnetze
5.3.3 Schaltwerke
5.4 Die Funktion einer CPU am Beispiel des M68000
5.4.1 Die Anschlüsse der CPU M68000
5.4.2 Der innere Aufbau der CPU M68000
5.4.3 Befehlsformate und Befehlsausführung
5.4.4 Adressierungsarten
5.5 Maschinensprache und Assembler
5.5.1 Einführung
5.5.2 Der Befehlssatz des M68000
5.5.3 Programmbeispiele
Literatur
Kapitel 6 Rechnerarchitektur
6.1 Überblick
6.2 Was ist eine Rechnerarchitektur?
6.2.1 Physikalische Umsetzung – Silizium und Wafer
6.2.2 Digitale Schaltungen – Transistoren
6.2.3 Gatter, Schaltnetze und Schaltwerke – Boolesche Logik
6.2.4 Mikroarchitektur und Mikroprogramme
6.2.5 Befehlssatz-Architektur
6.2.6 Hardware-Struktur außerhalb der CPU
6.2.7 Exkurs: Quantencomputer
6.3 Die von-Neumann-Architektur
6.3.1 Komponenten eines von-Neumann-Rechners
6.3.2 Operationsprinzip
6.4 Die Harvard-Architektur
6.5 Der typische Desktop-PC und Laptop
6.6 Befehlssatz
6.6.1 Mikroprogramme und CISC
6.6.2 Reduced Instruction Set Computer: RISC
6.6.3 Abwärtskompatibilität
6.7 Klassifikation nach Flynn
6.8 Parallelität innerhalb einer Befehlssequenz
6.8.1 Fließbandverarbeitung – Optimierte Befehlsausführung
6.8.2 Superskalare Mikroprozessoren
6.8.3 VLIW – Very Long Instruction Word
6.9 Parallelität in Daten nutzen: Vektorprozessoren
6.10 Parallele Ausführung mehrerer Befehlssequenzen
6.10.1 Simultanes Multi-Threading innerhalb einer CPU
6.10.2 Multi-Core-CPU
6.10.3 Multiprozessor-Systeme
6.10.4 Multicomputer-Systeme
6.11 Speicherhierarchie
6.11.1 Speichertechnologien: Register, Cache und Hauptspeicher
6.11.2 Caching
6.11.3 Memory Management Unit und virtueller Speicher
6.11.4 Festplatten
6.11.5 Flash-Speicher und Solid State Disks
6.12 Ein- und Ausgabe: Interrupts und DMA
6.13 Verbindungsstrukturen
6.13.1 Gemeinsamer Bus
6.13.2 Zugriffsprotokolle für Busse und gemeinsame Speicher
6.13.3 Punkt-Zu-Punkt Verbindungen: PCI-Express und SATA
6.13.4 Weitere Verbindungsstrukturen
6.13.5 Allgemeine topologische Verbindungsstrukturen
6.14 Mikrocontroller und Spezialprozessoren
Literatur
Kapitel 7 Rechnernetze
7.1 Was ist ein Rechnernetz?
7.2 Das OSI-Schichtenmodell der Datenkommunikation
7.3 Bitübertragungsschicht
7.3.1 Kupfer, Glasfaser und der freie Raum
7.3.2 Leitungscodierung
7.3.3 Modulation, Multiplexing und Multiple Access
7.3.4 Netztopologien
7.4 Technologien der Sicherungsschicht
7.4.1 Netze im Nahbereich: PAN und WPAN
7.4.2 Lokale Netze: LAN und WLAN
7.4.3 Vorgriff: Leitungs- und Paketvermittlung
7.4.4 Zugang zum Internet: DSL, Kabel, FTTH und 5G
7.4.5 Die Behandlung von Übertragungsfehlern
7.5 Netzwerk- und Transportschicht: TCP/IP und das Internet
7.5.1 Überblick über das Internet
7.5.2 IP: Internet Protocol
7.5.3 IPv6
7.5.4 ICMP: Internet Control Message Protocol
7.5.5 TCP: Transmission Control Protocol
7.5.6 TLS und SSL: Transport Level Security
7.5.7 UDP: User Datagram Protocol
7.6 Anwendungsschicht: Von DNS bis HTTP und URIs
7.6.1 DNS: Domain Name System
7.6.2 E-Mail
7.6.3 FTP: File Transfer Protocol
7.6.4 SSH: secure shell und TELNET: teletype network
7.6.5 HTTP und HTTPS: Hypertext Transfer Protocol
7.6.6 URI: Uniform Resource Identifier
Literatur
Kapitel 8 Betriebssysteme
8.1 Überblick
8.1.1 Aufgaben
8.1.2 Betriebsarten
8.2 Betriebssystem-Architekturen
8.3 Aufgaben eines Betriebssystems im Detail
8.3.1 Prozessverwaltung
8.3.2 Synchronisation
8.3.3 Interprozess-Kommunikation
8.3.4 Speicherverwaltung und virtueller Speicher
8.3.5 Geräteverwaltung und -treiber
8.3.6 Dateiverwaltung
8.4 Benutzerschnittstelle: Shell, GUI und NUI
8.4.1 Kommandozeilen-Interpreter am Beispiel UNIX
8.4.2 Besonderheiten am Beispiel der UNIX-Shell
8.4.3 Grafische Benutzerschnittstelle
8.4.4 Natürliche Benutzerschnittstelle (NUI)
8.5 Beispiele für Betriebssysteme
8.5.1 Microsoft-Windows
8.5.2 UNIX, LINUX und Android
8.6 Betriebssystem-Virtualisierung
8.6.1 Anwendungsbereiche
8.6.2 Hypervisoren
8.6.3 Virtuelle Maschinen
8.6.4 Grundlegende Aktivitäten der Virtualisierung
8.7 Container am Beispiel Docker
8.7.1 Images und Container
8.7.2 Betriebsmittel: Netzwerk und Verzeichnisse
8.7.3 Eigene Images erzeugen
8.7.4 Docker auf Windows und Linux
Literatur
Kapitel 9 Höhere Programmiersprachen und C
9.1 Zur Struktur höherer Programmiersprachen
9.1.1 Ebenen des Informationsbegriffs in Programmiersprachen
9.1.2 Systeme und Strukturen
9.2 Methoden der Syntaxbeschreibung
9.2.1 Die Backus-Naur Form
9.2.2 Syntaxgraphen
9.2.3 Eine einfache Sprache als Beispiel: C- -
9.3 Einführung in die Programmiersprache C
9.3.1 Der Aufbau von C-Programmen
9.3.2 Einfache Datentypen
9.3.3 Strukturierte Standard-Datentypen
9.3.4 Operatoren und Ausdrücke
9.3.5 Anweisungen
9.3.6 Funktionen
9.3.7 Ein- und Ausgabefunktionen
9.3.8 Verarbeitung von Zeichenketten
9.3.9 Das Zeigerkonzept in C
Literatur
Kapitel 10 Objektorientierte Programmiersprachen und Java
10.1 Entstehung objektorientierter Sprachen
10.2 Einführung in die Programmiersprache Java
10.2.1 Grundlegender Aufbau eines Java-Programms
10.2.2 Syntax ähnlich wie in C
10.2.3 Datentypen und Variablen: Statische Typisierung
10.3 Klassen und Objekte
10.3.1 Attribute und Methoden
10.3.2 Statische Attribute und Methoden
10.3.3 Pakete (Packages)
10.3.4 Kapselung und Geheimnisprinzip
10.3.5 Vererbung und Polymorphie
10.4 Fortgeschrittene Java-Themen
10.4.1 Generische Klassen, Behälter und Algorithmen
10.4.2 Ausnahmen und Fehlerbehandlung
10.4.3 Annotationen und Reflection
10.4.4 Testgetriebene Entwicklung mit Java
10.4.5 Threads, Streams und parallele Verarbeitung
10.4.6 Lambda-Ausdrücke und funktionale Programmierung
10.4.7 Das Java-Ökosystem
Literatur
Kapitel 11 Automatentheorie und formale Sprachen
11.1 Grundbegriffe der Automatentheorie
11.1.1 Endliche Automaten
11.1.2 Darstellung von Automaten
11.1.3 Die akzeptierte Sprache von Automaten
11.1.4 Kellerautomaten
11.1.5 Turing-Maschinen
11.2 Einführung in die Theorie der formalen Sprachen
11.2.1 Definition von formalen Sprachen
11.2.2 Die Chomsky-Hierarchie
11.2.3 Reguläre Ausdrücke
11.2.4 Das Pumping-Lemma
11.2.5 Die Analyse von Wörtern
11.2.6 Compiler
Literatur
Kapitel 12 Algorithmen – Berechenbarkeit und Komplexität
12.1 Berechenbarkeit
12.1.1 Entscheidungsproblem und Church-Turing These
12.1.2 Das Halteproblem
12.1.3 Satz von Rice und weitere unentscheidbare Probleme
12.1.4 LOOP-, WHILE- und GOTO-Berechenbarkeit
12.1.5 Primitiv rekursive und μ-rekursive Funktionen
12.2 Komplexität
12.2.1 Die Ordnung der Komplexität: O-Notation
12.2.2 Analyse von Algorithmen
12.2.3 Die Komplexitätsklassen P und NP
12.2.4 NP-vollständige Probleme
12.2.5 Weitere Komplexitätsklassen
12.2.6 Quantencomputer: Probabilistische Komplexitätsklassen
12.3 Probabilistische Algorithmen
12.3.1 Pseudo-Zufallszahlen
12.3.2 Monte-Carlo-Methoden
12.3.3 Probabilistischer Primzahltest
12.4 Rekursion
12.4.1 Definition und einführende Beispiele
12.4.2 Rekursive Programmierung und Iteration
12.4.3 Backtracking
Literatur
Kapitel 13 Suchen und Sortieren
13.1 Einfache Suchverfahren
13.1.1 Sequentielle Suche
13.1.2 Binäre Suche
13.1.3 Interpolationssuche
13.1.4 Radix-Suche
13.2 Suchen von Mustern in Zeichenketten
13.2.1 Musterabgleich durch sequentielles Vergleichen
13.2.2 Musterabgleich durch Automaten
13.2.3 Die Verfahren von Boyer-Moore und Knuth-Morris-Pratt
13.2.4 Ähnlichkeit von Mustern und Levenshtein-Distanz
13.3 Gestreute Speicherung (Hashing)
13.3.1 Hashfunktionen
13.3.2 Kollisionsbehandlung
13.3.3 Komplexitätsberechnung
13.4 Direkte Sortierverfahren
13.4.1 Vorbemerkungen
13.4.2 Sortieren durch direktes Einfügen (Insertion Sort)
13.4.3 Sortieren durch direktes Auswählen (Selection Sort)
13.4.4 Sortieren durch direktes Austauschen (Bubblesort)
13.5 Höhere Sortierverfahren
13.5.1 Shellsort
13.5.2 Quicksort
13.5.3 Vergleich der Sortierverfahren
13.6 Sortieren externer Dateien
13.6.1 Grundprinzipien des sequentiellen Datenzugriffs
13.6.2 Sequentielle Speicherorganisation
13.6.3 Direktes Mischen (Direct Merge, Mergesort)
13.6.4 Natürliches Mischen (Natural Merge)
13.6.5 n-Band-Mischen
Literatur
Kapitel 14 Datenstrukturen, Bäume und Graphen
14.1 Sequentielle Datenstrukturen
14.1.1 Lineare Listen
14.1.2 Stapel, Schlangen und Ringpuffer
14.2 Binärbäume
14.2.1 Speichern und Durchsuchen von Binärbäumen
14.2.2 Binäre Suchbäume
14.2.3 Ausgleichen von Bäumen und AVL-Bäume
14.2.4 Heaps und Heapsort
14.3 Vielwegbäume
14.3.1 Rückführung auf Binärbäume
14.3.2 Definition von (a,b)-Bäumen und B-Bäumen
14.3.3 Operationen auf B-Bäumen
14.4 Graphen
14.4.1 Definitionen und einführende Beispiele
14.4.2 Speicherung von Graphen
14.4.3 Suchen, Einfügen und Löschen von Knoten und Kanten
14.4.4 Durchsuchen von Graphen
14.4.5 Halbordnung und topologisches Sortieren
14.4.6 Minimal spannende Bäume
14.4.7 Union-Find Algorithmen
Literatur
Kapitel 15 Software-Engineering
15.1 Überblick
15.1.1 Was ist Software?
15.1.2 Was bedeutet Engineering?
15.1.3 Warum ist Software-Engineering schwierig?
15.2 Tätigkeiten im Software-Lebenszyklus
15.2.1 Anforderungsanalyse und Spezifikation
15.2.2 Architekturentwurf
15.2.3 Implementierung
15.2.4 Test und Integration
15.2.5 Inbetriebnahme
15.2.6 Wartung und Weiterentwicklung
15.3 Querschnittsdisziplinen
15.3.1 Projektmanagement
15.3.2 Qualitätsmanagement
15.3.3 Konfigurationsmanagement
15.4 Vorgehensmodelle
15.4.1 Basismodelle
15.4.2 V-Modell XT als plangetriebenes Vorgehensmodell
15.4.3 Scrum als agiles Produktmanagement-Framework
15.4.4 Praktiken der moderenen Software-Entwicklung und DevOps
15.5 Modelle im Software-Engineering
15.5.1 Vom Problem zur Lösung
15.5.2 Die Unified Modeling Language
15.5.3 Ausgewählte Diagramme der UML im Detail
15.6 Hilfsmittel für den Entwurf von Algorithmen
15.6.1 Pseudocode
15.6.2 Flussdiagramme
15.6.3 Struktogramme nach Nassi-Shneiderman
15.6.4 Entscheidungstabellen
Literatur
Kapitel 16 Datenbanken
16.1 Einführung und Definition
16.2 Daten und ihre Modellierung
16.3 Zugriffsmuster auf gespeicherte Daten
16.4 Datenbanktechnologien Geschichte und Überblick
16.5 Relationale Datenbankmanagement-Systeme
16.5.1 Relationen
16.5.2 Schlüssel
16.5.3 Beziehungen (Relationships)
16.6 Relationale Algebra
16.7 Die Datenbanksprache SQL
16.7.1 SQL als deklarative Sprache
16.7.2 Definition des Datenbankschemas
16.7.3 Einfügen, Ändern und Löschen von Daten
16.7.4 Suchen mit SELECT
16.7.5 Programmiersprachen und SQL
16.8 Transaktionen, OLTP und ACID
16.9 OLAP, Data Warehousing und Data-Mining
16.10 Semi-Strukturierte Daten mit XML
16.10.1 Der Aufbau von XML-Dokumenten
16.10.2 Wohlgeformtheit und Validität
16.10.3 XML-Schema
16.10.4 XPath
16.10.5 XSL: Extended Style Sheet Language
Literatur
Kapitel 17 Anwendungsprogrammierung im Internet
17.1 Client-Server-Systeme
17.2 Grundlegende Technologien
17.2.1 HTML
17.2.2 DOM: Document Object Model
17.2.3 CSS: Cascading Style Sheets
17.3 Webanwendungen
17.3.1 HTML Formulare
17.3.2 Auswertung von Formularen
17.4 JavaScript
17.4.1 Grundlegende Eigenschaften
17.4.2 Funktionen
17.4.3 Objekte und Prototypen
17.4.4 Klassen seit ES6
17.4.5 JSON: JavaScript Object Notation
17.4.6 JavaScript und DOM
17.4.7 Ereignisgesteuerte Programmierung mit JavaScript
17.4.8 AJAX: Asynchronous JavaScript And XML
Literatur
Kapitel 18 Maschinelles Lernen: Deep Learning mit neuronalen Netzen
18.1 Klassifikation und Regression
18.2 Neuronale Netze
18.2.1 Das Perzeptron-Neuronenmodell
18.2.2 Aktivierungsfunktionen
18.2.3 Mehrschichtperzeptron
18.3 Bilderkennung: Neuronale Faltungsnetze (CNN)
18.4 Verarbeitung natürlicher Sprache – Vorverarbeitung: Vom Text zum Vektor
18.4.1 Tokenisierung
18.4.2 Word2vec
18.5 Verarbeitung natürlicher Sprache: Transformer
18.5.1 Überblick
18.5.2 Positionscodierung
18.5.3 Decodierer-Ausgabe: Lineare Schicht & Softmax
18.5.4 Aufmerksamkeitsmechanismen
18.5.5 Addition, Normierung, Abkürzungen
18.5.6 GPT & Co.
18.6 Normalisierung und Regularisierung
18.7 Bewertung von Klassifikatoren
18.8 Ausblick
Literatur
Index
Die Autoren