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

Das Buch bietet eine umfassende und praxisorientierte Einführung in die wesentlichen Grundlagen und Konzepte der Informatik. Es umfasst den Stoff, der typischerweise in den ersten Semestern eines Informatikstudiums vermittelt wird, vertieft Zusammenhänge, die darüber hinausgehen und macht sie verständlich. Die Themenauswahl orientiert sich an der langfristigen Relevanz für die praktische Anwendung. Praxisnah und aktuell werden die Inhalte für Studierende der Informatik und verwandter Studiengänge sowie für im Beruf stehende Praktiker vermittelt. Praxisnah und aktuell werden die Inhalte für Studierende der Informatik und verwandter Studiengänge sowie für im Beruf stehende Praktiker vermittelt. 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