GRUNDBEGRIFFE DER INFORMATIK thomas worsch 2008 2009 / INHALTSVERZEICHNIS 1 1 Prolog 11 1 . Aufbau der Vorlesung und Ziele 12 2 . Quellen 2 4 Signale, Nachrichten, Informationen, Daten 21 4 . Signal 22 5 . Übertragung und Speicherung 23 5 . Nachricht 24 6 . Information 25 6 . Datum 26 7 . Zusammenfassung 3 8 Alphabete 31 8 . Alphabete 32 11 . Relationen und Abbildungen 33 12 . Logisches 34 14 . Zusammenfassung und Ausblick 4 16 Wörter 41 16 . Wörter 42 17 . Das leere Wort 43 18 . Mehr zu Wörtern 44 19 . Konkatenation von Wörtern 45 24 . Binäre Operationen 46 24 . Zusammenfassung 5 25 Der Begriff des Algorithmus 51 26 . Lösen einer Sorte quadratischer Gleichungen 52 26 . Zum informellen Algorithmusbegriff 53 . ZurKorrektheitdesAlgorithmuszurLösungeinerSor- 27 te quadratischer Gleichungen 54 28 . Wie geht es weiter? 55 . EinAlgorithmuszurMultiplikationnichtnegativergan- 29 zer Zahlen 56 . DerAlgorithmuszurMultiplikationnichtnegativergan- 32 zer Zahlen mit einer Schleife 6 36 Formale Sprachen 61 36 . Formale Sprachen 62 36 . Operationen auf formalen Sprachen 63 39 . Zusammenfassung 7 40 Dokumente 71 40 . Dokumente 0 2008 2009 gbi:skript: ii © worsch / 72 41 . Struktur von Dokumenten 73 44 . Zusammenfassung 8 45 Kontextfreie Grammatiken 81 45 . Rekursive Definition syntaktischer Strukturen 82 49 . Kontextfreie Grammatiken 83 2 53 . Relationen (Teil ) 84 54 . Ein Nachtrag zu Wörtern 85 55 . Ausblick 9 56 Speicher 91 56 . Bit und Byte 92 57 . Speicher als Tabellen und Abbildungen 93 59 . Binäre und dezimale Größenpräfixe 94 60 . Ausblick 10 61 Übersetzungen und Codierungen 101 61 .Von Wörtern zu Zahlen und zurück 102 65 .Von einem Alphabet zum anderen 103 68 .Huffman-Codierung 104 73 .Ausblick 11 74 Graphen 111 74 .Gerichtete Graphen 112 79 .Ungerichtete Graphen 113 82 .Graphen mit Knoten- oder Kantenmarkierungen 12 84 Erste Algorithmen in Graphen 121 84 .Repräsentation von Graphen im Rechner 122 86 .Berechnung der Erreichbarkeitsrelation 123 92 .Algorithmus von Warshall 124 94 .Ausblick 13 96 Quantitative Aspekte von Algorithmen 131 96 .Ressourcenverbrauch bei Berechnungen 132 97 .Groß-O-Notation 133 103 .Matrixmultiplikation 134 .AbschätzungdesWachstumsrekursivdefinierterFunktionen 106 135 107 .Ausblick 14 108 Endliche Automaten 141 108 .Erstes Beispiel: ein Getränkeautomat 142 111 .Mealy-Automaten 143 113 .Moore-Automaten 144 114 .Endliche Akzeptoren 145 117 .Ausblick 0 2008 2009 gbi:skript: iii © worsch / 15 118 Reguläre Ausdrücke und rechtslineare Grammatiken 151 118 .Reguläre Ausdrücke 152 122 .Rechtslineare Grammatiken 153 123 .Ausblick 16 124 Turingmaschinen 161 124 .Alan Mathison Turing 162 124 .Turingmaschinen 163 130 .Berechnungskomplexität 164 134 .Schwere Probleme 165 135 .Unentscheidbare Probleme 166 140 .Ausblick 17 141 Relationen 171 141 .Äquivalenzrelationen 172 144 .Kongruenzrelationen 173 146 .Halbordnungen 174 152 .Ordnungen 175 154 .Ausblick 18 156 Logik 181 156 .Formeln in Prädikatenlogik erster Stufe 182 157 .Theorien und Beweisbarkeit 183 .InterpretationenundModellefürgeschlosseneFormeln 159 184 160 .Beispiele für Modelle für geschlossene Formeln 185 161 .Grenzen von Prädikatenlogik erster Stufe 186 162 .Ausblick 163 Index 172 Literatur 0 2008 2009 gbi:skript: iv © worsch / 1 PROLOG Mark Twain wird der Ausspruch zugeschrieben: „Vorhersagensindschwierig,besonderswennsiedie Zukunft betreffen.“ Wie recht er hatte kann man auch an den folgenden Zitaten se- hen: 1943 : „I think there is a world market for maybe five compu- ters.“ (Thomas Watson, IBM) 1949 15 : „Computers in the future may weigh no more than . tons.“ (Popular Mechanics) 1977 : „Thereisnoreasonforanyindividualtohaveacomputer in their home.“ (Ken Olson, DEC) 1981 640 : „ K ought to be enough for anybody.“ (Bill Gates, Mi- crosoft, bestreitet den Ausspruch) 2000 : Es wurden mehr PCs als Fernseher verkauft. 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 Master- studiums, 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 verpflich- tend für das erste Semester der Bachelorstudiengänge Informa- tikundInformationswirtschaftanderUniversitätKarlsruhevor- 2008 2009 gesehen ist, zu denen man sich zum Wintersemester / einschreiben konnte. Der vorliegende Text ist ein Vorlesungsskript zu dieser Veran- staltung, wie ich sie in jenem Semester (halten will bzw. inzwi- schen) gehalten habe. 11 aufbau der vorlesung und ziele . 15 90 FürdieseVorlesungstehen Terminezuje MinutenzurVer- fügung. Ich habe versucht, den Vorlesungsinhalt auf eine Rei- he überschaubarer inhaltlicher Einheiten aufzuteilen. Vermut- 15 30 lich wird ihre Zahl am Ende zwischen und liegen. Man 19 wird sehen ... am Ende waren es . Die Vorlesung hat vordergründig mehrere Ziele. Zum einen sollen,wiederNamederVorlesungsagt,eineganzeReihewich- tiger Begriffe und Konzepte gelernt werden, die im Laufe des Studiumsimmerundimmerwiederauftreten;typischeBeispiele sindGraphenundendlicheAutomaten.Zumzweitensollenpar- allel dazu einige Begriffe und Konzepte vermittelt werden, die 1 1 2008 2009 gbi:skript: © worsch / manvielleichteherderMathematikzuordnenwürde,abereben- fallsunverzichtbarsind.DrittenssollendieStudentenmitwichti- genVorgehensweisenbeiderDefinitionneuerBegriffeundbeim Beweis von Aussagen vertraut gemacht werden. Induktives Vor- gehen ist in diesem Zusammenhang wohl zu allererst zu nen- nen. Andere Dinge sind nicht explizit Thema der Vorlesung, wer- den 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 verständlich (!) und präzise zu formulieren, und • wie man ordentlich und ethisch einwandfrei andere Quel- len benutzt und zitiert. Ichhabeversucht,derVersuchungzuwiderstehen,prinzipiell wie in einem Nachschlagewerk ü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 bes- serzumachenistauchdemBuch„Lernen“vonManfredSpitzer 2002 ( ) geschuldet. Es sei allen als interessante Lektüre empfoh- len. 12 quellen . Bei der Vorbereitung der Vorlesung habe ich mich auf diverse Quellen gestützt: Druckerzeugnisse und andere Quellen im In- ternet, die gelesen werden wollen, sind in den Literaturverwei- sen aufgeführt. Explizit an dieser Stelle erwähnt seien die Bücher von Goos 2006 2005 ( ) und Abeck ( ), die Grundlage waren für die Vorle- sung „Informatik I“, den Vorgänger der diesjährigen Vorlesun- gen „Grundbegriffe der Informatik“ und „Programmieren“. Gespräche und Diskussionen mit Kollegen sind nirgends zi- tiert. Daher sei zumindest an dieser Stellen pauschal allen ge- dankt, die – zum Teil womöglich ohne es zu wissen – ihren Teil beigetragen haben. Für Hinweise auf Fehler und Verbesserungsmöglichkeiten bin ich allen Lesern dankbar. 2009 Thomas Worsch, im Februar . 1 2 2008 2009 gbi:skript: © worsch / literatur Abeck, Sebastian (2005). Kursbuch Informatik, Band 1. Universi- tätsverlag Karlsruhe. Goos, Gerhard (2006). VorlesungenüberInformatik:Band1:Grund- lagen und funktionales Programmieren. Springer-Verlag. Spitzer, Manfred (2002). Lernen: Gehirnforschung und Schule des Lebens. Spektrum Akademischer Verlag. 1 3 2008 2009 gbi:skript: © worsch / 2 SIGNALE, NACHRICHTEN, INFORMATIONEN, DATEN Das Wort Informatik ist ein Kunstwort, das aus einem Präfix des Wortes Information und einem Suffix des Wortes Mathematik zu- sammengesetzt ist. So wie es keine scharfe Grenzen zwischen z.B. Physik und Elektrotechnikgibt,sonderneinenfließendenÜbergang,soistes z.B. auch zwischen Informatik und Mathematik und zwischen InformatikundElektrotechnik.Wirwerdenhiernichtversuchen, das genauer zu beschreiben. Aber am Ende Ihres Studiums wer- den Sie vermutlich ein klareres Gefühl dafür entwickelt haben. Was wir in dieser ersten Einheit klären wollen, sind die of- fensichtlich wichtigen Begriffe Signal, Nachricht, Information und Datum. 21 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 21 diesen Text auf einer Braillezeile (siehe Abbildung . ) ertasten, dannklapptdas,weildurchKrafteinwirkungdieHautIhrerFin- ger leicht demformiert wird. In allen Fällen sind es also physi- Abbildung2.1:Eine Braillezeile, Quelle: http://commons.wikimedia. org/wiki/Image:Refreshable_Braille_display.jpg (10.10.2008) kalische Vorgänge, die ablaufen und im übertragenen oder gar wörtlichenSinneeinen„Eindruck“davonvermitteln,wasmitge- teilt werden soll. DenBegriffMitteilungwollenwirhierinformellbenutzenund darauf vertrauen, dass er von allen passend verstanden wird (was auch immer hier „passend“ bedeuten soll). Die Verände- rungeiner(odermehrerer)physikalischerGrößen(zumBeispiel Schalldruck) um etwas mitzuteilen nennt man ein Signal. Signal Unter Umständen werden bei der Übermittlung einer Mittei- lung verschiedene Signale benutzt: Lichtwellen dringen in die Augen des Vorlesers, was elektrische Signale erzeugt, die dazu 2 4 2008 2009 gbi:skript: © worsch / führen, dass Schallwellen erzeugt werden, die ins Ohr des Hö- rers dringen. Dort werden dann ...und so weiter. 22 übertragung und speicherung . Schallwellen, Lichtwellen, usw. bieten die Möglichkeit, eine Mit- teilung von einem Ort zu einem anderen zu übertragen. Damit verbundenist(jedenfallsimalltäglichenLeben)immerauchdas Vergehen von Zeit. EsgibteineweitereMöglichkeit,MitteilungenvoneinemZeit- punkt zu einem späteren zu „transportieren“: Die Speicherung alsInschrift.DieHerstellungvonInschriftenmitPapierundStift Inschrift 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 de- nenSieganzselbstverständlichsagenwürden,dass„dadieglei- chen Zeichen stehen“. Um sozusagen zum Kern dessen vorzustoßen „was da steht“, bedarfeseinesAktesinunserenKöpfen.DennenntmanAbstrak- tion. 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änd- nis 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 Vorlesun- gen 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,aufdenwiralsnächstesetwasgenauereingehenwollen: 23 nachricht . Offensichtlich kann man etwas (immer Gleiches) auf verschiede- ne Arten, d.h. mit Hilfe verschiedener Signale, übertragen, und auch auf verschiedene Weisen speichern. Das Wesentliche, das übrig bleibt, wenn man z.B. von ver- schiedenenMedienfürdieSignalübertragungoderSpeicherung absieht, nennt man eine Nachricht. Nachricht Das,wasmanspeichernundübertragenkann,sindalsoNach- richten. Und: Man kann Nachrichten verarbeiten. Das ist einer der zentralen Punkte in der Informatik. Mit Inschriften werden wir uns ein erstes Mal genauer in Ein- 3 9 heit genauerbeschäftigenundmitSpeicherunginEinheit .Be- schreibungen, wie Nachrichten in gewissen Situationen zu ver- arbeiten sind, sind Programme (jedenfalls die einer bestimmten Art). Dazu erfahren Sie unter anderem in der parallel stattfin- denden Vorlesung Programmieren mehr. 2 5 2008 2009 gbi:skript: © worsch / 24 information . Meist übertragt man Nachrichten nicht um ihrer selbst willen. Vielmehr ist man üblicherweise in der Lage, Nachrichten zu in- terpretieren und ihnen so eine Bedeutung zuzuordnen. Dies ist Interpretation die einer Nachricht zugeordnete sogenannte Information. Information Wie eine Nachricht interpretiert wird, ist aber nicht eindeu- tig festgelegt. Das hängt vielmehr davon ab, welches „Bezugs- system“ 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 Men- schen vor sich geht und welche Interpretationsvorschriften sie anwenden. Er verarbeitet also im obigen Sinne Nachrichten und keine Informationen. Dasheißtabernicht,dassRechnereinfachimmernursinnlose Aktionen ausführen. Vielmehr baut und programmiert man sie gerade so, dass zum Beispiel die Transformation von Eingabe- zu Ausgabenachrichten bei einer bestimmten festgelegten Inter- pretationzueinerbeabsichtigtenInformationsverarbeitungpasst: Programm- Rechner: 42 17 −−−−−−−→ 59 ausführung ↓ ↓ ↓ Interpretation Interpre tation Interpre tation Rechnen Mensch: zweiund- siebzehn −−−−−→ neunund- Addition vierzig fünfzig 25 datum . DieumgangssprachlichmeistanzutreffendeBedeutungdesWor- 2 tes „Datum“ ist die eines ganz bestimmten Tages, z.B. „ . De- 1958 zember “. Ursprünglich kommt das Wort aus dem Lateini- schen, wo „datum“ „das Gegebene“ heißt. In der Informatik ist mit einem Datum aber oft etwas anderes gemeint: Syntaktisch handelt es sich um die Singularform des vertrauten Wortes „Daten“. Unter einem Datum wollen wir ein Paar verstehen, das aus einer Nachricht und einer zugehörigen Information besteht. WennmansichaufbestimmtefesteInterpretationsmöglichkei- ten von Nachrichten und eine feste Repräsentation dieser Mög- lichkeiten als Nachrichten geeinigt hat, kann man auch ein Da- tum als Nachricht repräsentieren (i.e. speichern oder übertra- gen). 2 6 2008 2009 gbi:skript: © worsch /