Die Kapitel 1-9 zusammen PDF

Preview

Summary

Download Die Kapitel 1-9 zusammen PDF

Description

Thomas Worsch und Simon Wacker unter Mitarbeit von P. Berdesinski, L. Buchholz, P. Fetzer

Grundbegriffe der Informatik Vorlesung im Wintersemester 2020/2021 (Fassung vom 9. Dezember 2020)

KIT-Fakultät für Informatik Karlsruher Institut für Technologie

I N H A LT S V E R Z E I C H N I S ( K U R Z ) Inhaltsverzeichnis (kurz)

i

Inhaltsverzeichnis (lang)

iii

1

Prolog

2

Signale, Nachrichten, Informationen, Daten 5

3

Mengen, Alphabete, Abbildungen 9

4

Wörter 23

5

Aussagenlogik 33

6

Induktives Vorgehen 49

7

Formale Sprachen 55

8

Übersetzungen und Codierungen 59

9

Speicher 79

1

10 Prozessor 85 11 Dokumente

97

12 Kontextfreie Grammatiken 103 13 Prädikatenlogik 115 14 Der Begriff des Algorithmus

131

15 Graphen 145 16 Erste Algorithmen in Graphen 157 17 Quantitative Aspekte von Algorithmen 175 18 Endliche Automaten 193 19 Reguläre Ausdrücke und rechtslineare Grammatiken 207

i

20 Turingmaschinen 217 21 Relationen 237 22 Mima-x

251

Literatur 263 Colophon 265

I N H A LT S V E R Z E I C H N I S ( L A N G ) Inhaltsverzeichnis (kurz)

i

Inhaltsverzeichnis (lang)

iii

1

Prolog 1 1.1 Aufbau der Vorlesung und Ziele 1 1.2 Quellen 2 Literatur 3

2

Signale, Nachrichten, Informationen, Daten 5 2.1 Signal 5 2.2 Übertragung und Speicherung 6 2.3 Nachricht 6 2.4 Information 7 2.5 Datum 8 2.6 Zusammenfassung 8

3

Mengen, Alphabete, Abbildungen 9 3.1 Mengen 10 3.2 Alphabete 15 3.2.1 Beispiel ASCII 15 3.2.2 Beispiel Unicode 16 3.3 Relationen und Abbildungen 17 3.3.1 Paare, Tupel und kartesische Produkte 17 3.3.2 Allquantor und Existenzquantor 18 3.3.3 Relationen und Abbildungen 18 3.4 Mehr zu Mengen 21

4

Wörter 23 4.1 Wörter 23 4.2 Das leere Wort 24 4.3 Mehr zu Wörtern 25 4.4 Konkatenation von Wörtern 25 4.4.1 Konkatenation mit dem leeren Wort 27 4.4.2 Eigenschaften der Konkatenation 28 4.4.3 Beispiel: Aufbau von E-Mails 28 4.4.4 Iterierte Konkatenation 30

iii

4.5 4.6

Formale Sprachen 30 Binäre Operationen 31

5

Aussagenlogik 33 5.1 Informelle Grundlagen 33 5.2 Syntax aussagenlogischer Formeln 34 5.3 Boolesche Funktionen 37 5.4 Semantik aussagenlogischer Formeln 38 5.5 Beweisbarkeit 43 Literatur 47

6

Induktives Vorgehen 49 6.1 Vollständige Induktion 49 6.2 Varianten vollständiger Induktion 6.3 Induktive Definitionen 53

51

7

Formale Sprachen 55 7.1 Operationen auf formalen Sprachen 55 7.1.1 Produkt oder Konkatenation formaler Sprachen 55 7.1.2 Konkatenationsabschluss einer formalen Sprache 57 7.2 Zusammenfassung 58

8

Übersetzungen und Codierungen 59 8.1 Von Wörtern zu Zahlen und zurück 59 8.1.1 Dezimaldarstellung von Zahlen 59 8.1.2 Andere unbeschränkte Zahldarstellungen 60 8.1.3 Ganzzahlige Division mit Rest 62 8.1.4 Von Zahlen zu ihren Darstellungen 63 8.1.5 Beschränkte Zahlbereiche und Zahldarstellungen 64 8.2 Komposition von Funktionen 65 8.3 Von einem Alphabet zum anderen 66 8.3.1 Ein Beispiel: Übersetzung von Zahldarstellungen 66 8.3.2 Homomorphismen 68 8.3.3 Beispiel Unicode: UTF-8 Codierung 71 8.4 Huffman-Codierung 72 8.4.1 Algorithmus zur Berechnung von Huffman-Codes 73 8.4.2 Weiteres zu Huffman-Codes 77 8.5 Ausblick 78

9

Speicher 79

9.1 9.2 9.3 9.4

Bit und Byte 79 Binäre und dezimale Größenpräfixe 80 Speicher als Tabellen und Abbildungen 81 9.3.1 Hauptspeicher 81 Ausblick 84

10 Prozessor 85 10.1 Einfache „Hardware“-„Bausteine“ 85 10.2 Grobstruktur der Mima 88 10.3 Maschinenbefehle der Mima 90 10.3.1 Befehle zum Datentransport 91 10.3.2 Arithmetische/logische Befehle 91 10.3.3 Sprungbefehle 92 10.4 Mikroprogrammsteuerung der Mima 93 10.4.1 Befehlsholphase 94 10.4.2 Befehlsdecodierungsphase 95 10.4.3 Befehlsausführungsphase 95 10.5 Ein Beispielprogramm 95 11 Dokumente 97 11.1 Dokumente 97 11.2 Struktur von Dokumenten 98 11.2.1 LATEX 98 11.2.2 HTML und XHTML 100 11.2.3 Eine Grenze unserer bisherigen Vorgehensweise 101 11.3 Zusammenfassung 102 12 Kontextfreie Grammatiken 103 12.1 Rekursive Definition syntaktischer Strukturen 12.2 Kontextfreie Grammatiken 108 12.3 Relationen (Teil 2) 112 12.4 Ausblick 113

103

13 Prädikatenlogik 115 13.1 Syntax prädikatenlogischer Formeln 115 13.2 Semantik prädikatenenlogischer Formeln 118 13.3 Freie und gebundene Variablenvorkommen und Substitutionen 13.4 Beweisbarkeit 126 14 Der Begriff des Algorithmus

131

121

14.1 14.2 14.3 14.4

Lösen einer Sorte quadratischer Gleichungen 132 Zum informellen Algorithmusbegriff 133 Informelle Einführung des Hoare-Kalküls 134 Ein Algorithmus zur Multiplikation nichtnegativer ganzer Zahlen

15 Graphen 145 15.1 Gerichtete Graphen 145 15.1.1 Graphen und Teilgraphen 145 15.1.2 Pfade und Erreichbarkeit 147 15.1.3 Isomorphie von Graphen 149 15.1.4 Ein Blick zurück auf Relationen 150 15.2 Ungerichtete Graphen 151 15.2.1 Anmerkung zu Relationen 154 15.3 Graphen mit Knoten- oder Kantenmarkierungen 15.3.1 Gewichtete Graphen 155

140

154

16 Erste Algorithmen in Graphen 157 16.1 Repräsentation von Graphen im Rechner 157 16.2 Berechnung der 2-Erreichbarkeitsrelation und Rechnen mit Matrizen 161 16.2.1 Matrizenmultiplikation 163 16.2.2 Matrizenaddition 164 16.3 Berechnung der Erreichbarkeitsrelation 165 16.3.1 Potenzen der Adjazenzmatrix 166 16.3.2 Erste Möglichkeit für die Berechnung der Wegematrix 167 16.3.3 Zählen durchzuführender arithmetischer Operationen 168 16.3.4 Weitere Möglichkeiten für die Berechnung der Wegematrix 170 16.4 Algorithmus von Warshall 171 16.5 Ausblick 174 Literatur 174 17 Quantitative Aspekte von Algorithmen 175 17.1 Ressourcenverbrauch bei Berechnungen 175 17.2 Groß-O-Notation 176 17.2.1 Ignorieren konstanter Faktoren 177 17.2.2 Notation für obere und untere Schranken des Wachstums 17.2.3 Die furchtbare Schreibweise 182 17.2.4 Rechnen im O-Kalkül 183 17.3 Matrizenmultiplikation 185

181

17.3.1 Rückblick auf die Schulmethode 186 17.3.2 Algorithmus von Strassen 187 17.4 Asymptotisches Verhalten „implizit“ definierter Funktionen 17.5 Unterschiedliches Wachstum einiger Funktionen 189 17.6 Ausblick 190 Literatur 191

188

18 Endliche Automaten 193 18.1 Erstes Beispiel: ein Getränkeautomat 193 18.2 Mealy-Automaten 196 18.3 Moore-Automaten 198 18.4 Endliche Akzeptoren 200 18.4.1 Beispiele formaler Sprachen, die von endlichen Akzeptoren akzeptiert werden können 201 18.4.2 Eine formale Sprache, die von keinem endlichen Akzeptoren akzeptiert werden kann 203 18.5 Ausblick 204 19 Reguläre Ausdrücke und rechtslineare Grammatiken 207 19.1 Reguläre Ausdrücke 207 19.2 Rechtslineare Grammatiken 211 19.3 Kantorowitsch-Bäume und strukturelle Induktion 212 19.4 Ausblick 215 Literatur 216 20 Turingmaschinen 217 20.1 Alan Mathison Turing 217 20.2 Turingmaschinen 217 20.2.1 Berechnungen 220 20.2.2 Eingaben für Turingmaschinen 222 20.2.3 Ergebnisse von Turingmaschinen 223 20.3 Berechnungskomplexität 224 20.3.1 Komplexitätsmaße 226 20.3.2 Komplexitätsklassen 227 20.4 Unentscheidbare Probleme 228 20.4.1 Codierungen von Turingmaschinen 229 20.4.2 Das Halteproblem 230 20.4.3 Die Busy-Beaver-Funktion 232 20.5 Ausblick 234

Literatur 235 21 Relationen 237 21.1 Äquivalenzrelationen 237 21.1.1 Definition 237 21.1.2 Äquivalenzklassen und Faktormengen 238 21.2 Kongruenzrelationen 238 21.2.1 Verträglichkeit von Relationen mit Operationen 238 21.2.2 Wohldefiniertheit von Operationen mit Äquivalenzklassen 239 21.3 Halbordnungen 239 21.3.1 Grundlegende Definitionen 239 21.3.2 „Extreme“ Elemente 242 21.3.3 Vollständige Halbordnungen 243 21.3.4 Stetige Abbildungen auf vollständigen Halbordnungen 244 21.4 Ordnungen 247 21.5 Ausblick 249 22 Mima-x 251 22.1 Stapel / Stack / Keller 251 22.1.1 Der Stapel 251 22.1.2 Operationen auf einem Stapel 251 22.1.3 Implementierung eines Stapels 253 22.1.4 Die Ackermann-Funktion 253 22.2 MiMa-X 255 22.2.1 Architektur 255 22.2.2 Stapelimplementierung 255 22.2.3 „Flache“ Funktionsaufrufe 256 22.2.4 „Richtige“ Funktionsaufrufe mit einem Stapel Literatur 263 Colophon 265

257

1 PROLOG Mark Twain wird der Ausspruch zugeschrieben: „Vorhersagen sind schwierig, besonders wenn sie die Zukunft betreffen.“ Wie recht er hatte, kann man auch an den folgenden Zitaten sehen: 1943: „I think there is a world market for maybe five computers.“ (Thomas Watson, IBM) 1949: „Computers in the future may weigh no more than 1.5 tons.“ (Popular Mechanics) 1977: „There is no reason for any individual to have a computer in their home.“ (Ken Olson, DEC) 1981: „640K ought to be enough for anybody.“ (Bill Gates, Microsoft, bestreitet den Ausspruch) 2000: Es wurden mehr PCs als Fernseher verkauft. 2012: In Deutschland gab es Ende des Jahres etwa 30 Millionen Smartphones. Das lässt sofort die Frage aufkommen: Was wird am Ende Ihres Studiums der Fall sein? Sie können ja mal versuchen, auf einem Zettel aufzuschreiben, was in fünf Jahren am Ende Ihres Masterstudiums, das Sie hoffentlich an Ihr Bachelorstudium anschließen, wohl anders sein wird als heute, den Zettel gut aufheben und in fünf Jahren lesen. Am Anfang Ihres Studiums steht jedenfalls die Veranstaltung „Grundbegriffe der Informatik“, die unter anderem verpflichtend für das erste Semester der Bachelorstudiengänge Informatik und Informationswirtschaft am Karlsruher Institut für Technologie vorgesehen ist. Der vorliegende Text ist ein Vorlesungsskript zu dieser Veranstaltung.

1.1

aufbau der vorlesung und ziele

Seit dem Wintersemester 2015/2016 ist die Vorlesung „Grundbegriffe der Informatik“ von vorher zwei auf drei Vorlesungsstunden pro Woche vergrößert. Der Vorlesungsinhalt ist auf eine Reihe überschaubarer Kapitel aufgeteilt. Die Vorlesung hat vordergründig mehrere Ziele. Zum einen sollen, wie der Name der Vorlesung sagt, eine ganze Reihe wichtiger Begriffe und Konzepte gelernt werden, die im Laufe des Studiums immer und immer wieder auftreten; typische Beispiele sind Graphen und endliche Automaten. Zum zweiten sollen parallel dazu einige Begriffe und Konzepte vermittelt werden, die man vielleicht eher der Mathematik zuordnen würde, aber ebenfalls unverzichtbar sind. Drittens sollen

1

die Studenten mit wichtigen Vorgehensweisen bei der Definition neuer Begriffe und beim Beweis von Aussagen vertraut gemacht werden. Induktives Vorgehen ist in diesem Zusammenhang wohl zu allererst zu nennen. Andere Dinge sind nicht explizit Thema der Vorlesung, werden aber (hoffentlich) doch vermittelt. So bemühe ich mich mit diesem Skript zum Beispiel auch, klar zu machen, • dass man präzise formulieren und argumentieren kann und muss, • dass Formalismen ein Hilfsmittel sind, um gleichzeitig verständlich (!) und präzise formulieren zu können, und • wie man ordentlich und ethisch einwandfrei andere Quellen benutzt und zitiert. Ich habe versucht, der Versuchung zu widerstehen, prinzipiell wie in einem Nachschlagewerk im Haupttext überall einfach nur lange Listen von Definitionen, Behauptungen und Beweisen aneinander zu reihen. Gelegentlich ist das sinnvoll, und dann habe ich es auch gemacht, sonst aber hoffentlich nur selten. Der Versuch, das ein oder andere anders und hoffentlich besser zu machen ist auch dem Buch „Lernen“ von Manfred Spitzer (2002) geschuldet. Es sei allen als interessante Lektüre empfohlen.

1.2

quellen

Bei der Vorbereitung der Vorlesung habe ich mich auf diverse Quellen gestützt: Druckerzeugnisse und andere Quellen im Internet, die gelesen werden wollen, sind in den Literaturverweisen aufgeführt. Explizit an dieser Stelle erwähnt seien zum einen die Bücher von Goos (2006) und Abeck (2005), die Grundlage waren für die Vorlesung „Informatik I“, den Vorgänger der Vorlesungen „Grundbegriffe der Informatik“ und „Programmieren“. Außerdem findet man im WWW diverse Versionen eines Buches zu „Mathematics for Computer Science“, das ursprünglich von Lehman und Leighton ausgearbeitet wurde. Die aktuelle Version stammt von Lehman, Leighton und Meyer (2013). Durch Ihre Mitarbeit an der Vorlesung und der zugehörigen großen Übung haben im Laufe der Jahre Matthias Schulz, Matthias Janke und Simon Janke Beiträge geleistet, die auch dieses Vorlesungsskript mit eingeflossen sind. Gespräche und Diskussionen mit ihnen und anderen Kollegen sind nirgends zitiert. Daher sei zumindest an dieser Stellen pauschal allen gedankt, die – zum Teil womöglich

gbi:skript:1

2

© worsch&wacker 2008–2021

ohne es zu wissen – ihren Teil beigetragen haben.

Für Hinweise auf Fehler und Verbesserungsmöglichkeiten bin ich allen Lesern dankbar. Explizit danken möchte ich in diesem Zusammenhang den Studenten Felix Lübbe, Matthias Fritsche und Thomas Schwartz, die eine ganze Reihe von Korrekturen geliefert haben. Im Laufe des Jahres 2020 haben die ehemaligen Tutoren Philipp Berdesinski, Luca Buchholz und Patrick Fetzer die bisher noch fehlenden Kapitel 10 und 22 zum Aufbau eines einfachen Prozessors erarbeitet. Dafür danke ich Ihnen ganz herzlich.

Thomas Worsch, im November 2020.

literatur Abeck, Sebastian (2005). Kursbuch Informatik, Band 1. Universitätsverlag Karlsruhe (siehe S. 2). Goos, Gerhard (2006). Vorlesungen über Informatik: Band 1: Grundlagen und funktionales Programmieren. Springer-Verlag (siehe S. 2). Lehman, Eric, Tom Leighton und Albert R. Meyer (2013). Mathematics for Computer Science. url: http://courses.csail.mit.edu/6.042/fall13/class-material. shtml (siehe S. 2). Spitzer, Manfred (2002). Lernen: Gehirnforschung und Schule des Lebens. Spektrum Akademischer Verlag (siehe S. 2).

gbi:skript:1

3

© worsch&wacker 2008–2021

2 SIGNALE, NACHRICHTEN, I N F O R M AT I O N E N , D AT E N Das Wort Informatik ist ein Kunstwort, das aus einem Präfix des Wortes Information und einem Suffix des Wortes Mathematik zusammengesetzt ist. So wie es keine scharfe Grenze zwischen z. B. Physik und Elektrotechnik gibt, sondern einen fließenden Übergang, so ist es z. B. auch zwischen Informatik und Mathematik und zwischen Informatik und Elektrotechnik. Wir werden hier nicht versuchen, das genauer zu beschreiben. Aber am Ende Ihres Studiums werden Sie vermutlich ein klareres Gefühl dafür entwickelt haben. Was wir in diesem ersten Kapitel klären wollen, sind die wichtigen Begriffe Signal, Nachricht, Information und Datum.

2.1

signal

Wenn Sie diese Zeilen vorgelesen bekommen, dann klappt das, weil Schallwellen vom Vorleser zu Ihren Ohren gelangen. Wenn Sie diese Zeilen lesen, dann klappt das, weil Lichtwellen vom Papier oder dem Bildschirm in Ihr Auge gelangen. Wenn Sie diesen Text auf einer Braillezeile (siehe Abbildung 2.1) ertasten, dann klappt das, weil durch Krafteinwirkung die Haut Ihrer Finger leicht deformiert wird. In allen Fällen sind es also physikalische Vorgänge, die ablaufen und

Abbildung 2.1: Eine Braillezeile, Quelle: http://commons.wikimedia.org/wiki/ Image:Refreshable_Braille_display.jpg (17.10.2013) im übertragenen oder gar wörtlichen Sinne einen „Eindruck“ davon vermitteln, was mitgeteilt werden soll. Den Begriff Mitteilung wollen wir hier informell benutzen und darauf vertrauen, dass er von allen passend verstanden wird (was auch immer hier „passend“ be-

5

deuten soll). Die Veränderung einer (oder mehrerer) physikalischer Größen (zum Beispiel Schalldruck) um etwas mitzuteilen nennt man ein Signal. Unter Umständen werden bei der Übermittlung einer Mitteilung verschiedene Signale benutzt: Lichtwellen dringen in die Augen des Vorlesers, was elektrische Signale erzeugt, die dazu führen, dass Schallwellen erzeugt werden, die ins Ohr des Hörers dringen. Dort werden dann . . . und so weiter.

2.2

übertragung und speicherung

Schallwellen, Lichtwellen, usw. bieten die Möglichkeit, eine Mitteilung von einem Ort zu einem anderen zu übertragen. Damit verbunden ist (jedenfalls im alltäglichen Leben) immer auch das Vergehen von Zeit. Es gibt eine weitere Möglichkeit, Mitteilungen von einem Zeitpunkt zu einem späteren zu „transportieren“: Die Speicherung als Inschrift. Die Herstellung von Inschriften mit Papier und Stift ist uns allen geläufig. Als es das noch nicht gab, benutzte man z. B. Felswände und Pinsel. Und seit einigen Jahrzehnten kann man auch magnetisierbare Schichten „beschriften“. Aber was wird denn eigentlich gespeichert? Auf dem Papier stehen keine Schall- oder Lichtwellen oder andere Signale. Außerdem kann man verschiedene Inschriften herstellen, von denen Sie ganz selbstverständlich sagen würden, dass „da die gleichen Zeichen stehen“. Um sozusagen zum Kern dessen vorzustoßen „was da steht“, bedarf es eines Aktes in unseren Köpfen. Den nennt man Abstraktion. Jeder hat vermutlich eine gewisse Vorstellung davon, was das ist. Ich wette aber, dass Sie gerade als Informatik-Studenten zum Abschluss Ihres Studiums ein sehr viel besseres Verständnis davon haben werden, was es damit genau auf sich hat. So weit sich der Autor dieses Textes erinnern kann (ach ja . . . ), war die zunehmende Rolle, die Abstraktion in einigen Vorlesungen spielte, sein Hauptproblem in den ersten beiden Semestern. Aber auch das ist zu meistern. Im Fall der Signale und Inschriften führt Abstraktion zu dem Begriff, auf den wir als nächstes etwas genauer eingehen wollen:

2.3

Signal

nachricht

Offensichtlich kann man etwas (immer Gleiches) auf verschiedene Arten, d. h. mit Hilfe verschiedener Signale, übertragen, und auch auf verschiedene Weisen speichern.

gbi:skript:2

6

© worsch&wacker 2008–2021

Inschrift

Das Wesentliche, das übrig bleibt, wenn man z. B. von verschiedenen Medien für die Signalübertragung oder Speicherung absieht, nennt man eine Nachricht. Das, was man speichern und übertragen kann, sind also Nachrichten. Und: Man kann Nachrichten verarbeiten. Das ist einer der zentralen Punkte in der Informatik. Mit Inschriften werden wir uns ein erstes Mal in Kapitel 3 genauer beschäftigen und mit Speicherung in Kapitel 9. Beschreibungen, wie Nachrichten in gewissen Situationen zu verarbeiten sind, sind Programme (jedenfalls die einer bestimmten Art). Dazu erfahren Sie unter anderem in der parallel stattfindenden Vorlesung Programmieren mehr.

2.4

Nachricht

information

Meist übertragt man Nachrichten nicht um ihrer selbst willen. Vielmehr ist man üblicherweise in der Lage, Nachrichten zu interpretieren und ihnen so eine Bedeutung zuzuordnen. Dies ist die einer Nachricht zugeordnete sogenannte Information. Wie eine Nachricht interpretiert wird, ist aber nicht eindeutig festgelegt. Das hängt vielmehr davon ab, welches „Bezugssystem“ der Interpretierende benutzt. Der Buchhändler um die Ecke wird wohl den Text 1001 interpretieren als Zahl Tausendundeins, aber ein Informatiker wird vielleicht eher den Text 1001 interpretieren als Zahl Neun. Ein Rechner hat „keine Ahnung“, was in den Köpfen der Menschen vor sich geht und welche Interpretationsvorschriften sie anwenden. Er verarbeitet also im obigen Sinne Nachrichten und keine Informationen. Das heißt aber nicht, dass Rechner einfach immer nur sinnlose Aktionen ausführen. Vielmehr baut und programmiert man sie gerade so, dass zum Beispiel die Transformation von Eingabe- zu Ausgabenachrichten bei einer bestimmten festgelegten Interpretation zu einer beabsichtigten Informationsverarbeitung passt: Rechner:

Mensch:

42 Interpretation↓

zweiund-

17 Interpre↓...