STUDIUM Thorsten Schöler, Stefan Höltgen, Johannes Maibaum, Thomas Fischer MEDIENTECHNISCHES WISSEN BAND 2: INFORMATIK, PROGRAMMIEREN, KYBERNETIK Herausgegeben von Stefan Höltgen Thorsten Schöler, Stefan Höltgen, Johannes Maibaum, Thomas Fischer Medientechnisches Wissen 2 De Gruyter Studium Weitere empfehlenswerte Titel Medientechnisches Wissen, Band 1 S. Höltgen (Hrsg.), 2017 ISBN 978-3-11-047748-1, e-ISBN (PDF) 978-3-11-047750-4, e-ISBN (EPUB) 978-3-11-047762-7 Medientechnisches Wissen, Band 3 S. Höltgen, 2019 ISBN 978-3-11-049626-0, e-ISBN (PDF) 978-3-11-049627-7, e-ISBN (EPUB) 978-3-11-049359-7 Medientechnisches Wissen, Band 4 S. Höltgen (Hrsg.), 2020 ISBN 978-3-11-058179-9, e-ISBN (PDF) 978-3-11-058180-5, e-ISBN (EPUB) 978-3-11-058182-9 Mathematik B. Ulmann, 2015 ISBN 978-3-11-037511-4, e-ISBN (PDF) 978-3-11-037513-8, e-ISBN (EPUB) 978-3-11-039785-7 Thorsten Schöler, Stefan Höltgen, Johannes Maibaum, Thomas Fischer Medientechnisches Wissen Band 2: Informatik, Programmieren, Kybernetik Herausgegeben von Stefan Höltgen Herausgeber Dr. Stefan Höltgen Humboldt-Universität zu Berlin Inst. für Musikwissenschaft und Medienwissenschaft Georgenstr. 47 10117 Berlin stefan.hoeltgen@hu-berlin.de ISBN 978-3-11-049624-6, e-ISBN (PDF) 978-3-11-049625-3, e-ISBN (EPUB) 978-3-11-049358-0 Library of Congress Control Number: 2018959324 Bibliographic information published by the Deutsche Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der DeutschenNationalbibliografie; detaillierte bibliografische Daten sind im Internet über http://dnb.dnb.de abrufbar. © 2019 Walter de Gruyter GmbH, Berlin/Boston Redaktion: Maria Kuban Einbandabbildung: Martin Meier Druck und Bindung: CPI books GmbH, Leck www.degruyter.com Inhalt Vorwort | 1 Teil I: Informatik (Thorsten Schöler) 1 Einführung | 7 2 Einleitung | 8 3 3.1 3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 3.1.6 3.2 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 Theoretische Informatik | 10 Formale Sprachen | 10 Grammatik | 11 Reguläre Sprachen (Typ 3) | 13 Kontextfreie Sprachen (Typ 2) | 15 Kontextsensitive Sprachen (Typ 1) | 16 Rekursiv aufzählbare Sprachen (Typ 0) | 16 Zusammenfassung formaler Sprachen | 17 Automatentheorie | 18 Endliche Zustandsautomaten | 18 Kellerautomaten | 21 Turingmaschine | 24 Zusammenfassung Automatentheorie | 27 Registermaschine | 27 4 4.1 4.2 Technische Informatik | 29 Geschichtlicher Hintergrund | 29 Aktuelle Entwicklungen in der technischen Informatik | 37 5 5.1 5.1.1 5.1.2 5.1.3 5.1.4 5.2 5.2.1 5.2.2 5.3 5.3.1 Algorithmen und Datenstrukturen | 40 Algorithmen | 40 Eigenschaften von Algorithmen | 41 Textuelle Beschreibungsverfahren | 42 Laufzeitanalyse von Algorithmen | 47 Implementierung von Algorithmen | 51 Datenstrukturen | 54 Listen | 55 Stapel- oder Kellerspeicher | 56 Sortieralgorithmen | 57 Insertionsort | 58 VI | Inhalt 5.3.2 5.3.3 5.3.4 5.3.5 5.3.6 Selectionsort | 60 Bubblesort | 61 Quicksort | 63 Mergesort | 64 Heapsort | 66 6 6.1 6.2 6.3 6.4 6.5 Bäume | 69 Deőnitionen | 69 Knoten- und blattorientierte Bäume | 71 Binäre Suchbäume | 71 AVL-Bäume | 74 B-Bäume | 78 7 7.1 7.2 7.3 7.4 Gestreute Speicherung, Hashing | 82 Kollisionen | 84 Offenes Hashing, getrennte Verkettung | 85 Geschlossenes Hashing | 86 Weitere Anwendungen | 86 8 Präfixbäume | 88 9 9.1 9.2 9.2.1 9.2.2 9.3 9.3.1 9.3.2 9.4 Graphen | 90 Grundlegendes zu Graphen | 90 Breiten- und Tiefensuche | 92 Breitensuche | 92 Tiefensuche | 94 Minimale Spannbäume | 101 Algorithmus von Kruskal | 101 Algorithmus von Prim | 103 Kürzeste Wege | 103 10 Schwere Probleme und Heuristiken | 106 10.1 Problem des Handlungsreisenden | 107 10.1.1 Durch Ausprobieren (brute force) | 108 10.1.2 Nearest-Neighbour-Insertion | 109 10.1.3 Nearest-Insertion-Heuristik | 109 10.1.4 Farthest-Insertion-Heuristik | 110 10.1.5 Random-Insertion-Heuristik | 110 10.1.6 Minimaler-Spannbaum-Heuristik | 111 10.1.7 Tourverschmelzungsheuristik | 112 10.2 Rucksackproblem | 116 Inhalt 11 Zusammenfassung und Ausblick | 125 12 Lektüreempfehlungen | 127 | VII Literatur | 129 Teil II: Programmieren für Medienwissenschaftler (Stefan Höltgen & Johannes Maibaum) 1 Einleitung | 133 2 2.1 2.1.1 2.1.2 2.1.3 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 2.2.7 2.3 2.4 2.4.1 2.4.2 2.4.3 2.5 2.5.1 2.5.2 2.5.3 2.6 2.7 2.8 Assembler | 136 Einführung | 136 Assembler | 137 Hardwarenahe Programmierung | 139 Aufbau einer CPU | 139 Funktionen | 142 Die Busse | 142 Die Arithmetisch-Logische Einheit (ALU) | 143 Die Register | 143 Zahlensysteme: Dual, Dezimal, Hexadezimal | 144 Adressen und Speicher | 146 Memory-mapped I/O und ROM | 147 Adressierungsarten | 148 Der Befehlssatz der 6502 | 151 Der MOUSE-Computer | 154 Aufbau | 154 Speicherorganisation | 155 Besondere Adressen im ROM | 155 Programmierung | 157 Warteschleifen | 158 Selbstmodifizierender Code | 160 Interrupt Handling | 161 Assemblercode lesen | 164 Schluss | 167 Lektüreempfehlungen | 167 3 3.1 3.2 BASIC | 169 BBC BASIC | 170 Eigenschaften der Sprache | 172 VIII | Inhalt 3.2.1 3.2.2 3.2.3 3.2.4 3.3 3.3.1 3.3.2 3.3.3 3.4 3.5 Die Struktur von BASIC-Programmen | 173 Befehle | 174 Funktionen und Daten, Variablen und Konstanten | 174 BBC BASIC und Assembler | 175 Programmieren in BASIC | 176 Historische BASIC-Algorithmen | 177 Standard-Algorithmen in BASIC | 188 Computerarchäologie mit BASIC | 192 Schluss | 200 Lektüreempfehlungen | 201 4 C | 204 4.1 Zum Einstieg | 204 4.2 Die verwendete Plattform | 205 4.3 Erster Einstieg: Noch einmal Zahlenraten | 206 4.4 Zweiter Einstieg: źHallo, Welt“ in C | 209 4.5 Noch einmal Assembler | 212 4.6 Datentypen | 214 4.7 Variablen | 217 4.8 Funktionen | 219 4.9 Kontrollstrukturen | 223 4.10 Zeiger (Pointer) | 226 4.10.1 Einen Zeiger erstellen | 227 4.10.2 Zeiger erlauben Funktionen mit mehr als einem źRückgabewert“ | 227 4.10.3 Zeiger und Arrays | 229 4.11 Schluss | 234 4.12 Lektüreempfehlungen | 235 5 5.1 5.2 5.2.1 5.2.2 5.3 5.3.1 5.3.2 5.3.3 5.3.4 5.4 5.5 5.6 5.7 Python | 237 Ein interaktiver Einstieg | 238 Ein fast interaktiver Einstieg in die Objektorientierung | 241 Module | 247 Vererbung | 248 Zeichenketten, Sequenz- und Wörterbuchdatentypen | 250 Zeichenketten | 250 Listen | 253 Iterieren über Sequenzen | 255 źWörterbücher“ (assoziative Datenfelder) | 258 Beispielprogramm: Markow-Ketten | 260 Beispielprogramm: Schlagzeile vorlesen | 264 Schluss | 267 Lektüreempfehlungen | 268 Inhalt Teil III: Kybernetik (Thomas Fischer) Kybernetik | 274 1 1.1 1.2 1.3 1.4 1.5 1.6 Einführung | 275 Überblick | 275 Abgrenzung | 276 Technische Voraussetzungen und Hinweise | 277 Die medienwissenschaftliche Relevanz der Kybernetik | 278 Hintergrund | 280 Geschichte und Gesichter der Kybernetik | 285 2 2.1 2.2 2.3 2.4 2.5 Determinismus und Determinierbarkeit | 302 Widersprüchliche Grundannahmen | 302 Physikalische Umsetzung logischer Formalismen | 303 Klare Zustände: der Zweipunkt-Thermostat | 304 Programmierbare Abläufe: die Turingmaschine | 311 Deterministische Mechanismen: die Triviale Maschine | 316 3 3.1 3.2 3.3 3.4 3.5 Zirkuläre Kausalität | 321 A beeinŕusst B und B beeinŕusst A | 321 Logische Paradoxien | 322 Geburtsurkunde der Kybernetik | 324 Reŕexivität | 325 Widerstand gegenüber zirkulärer Kausalität | 327 4 4.1 4.2 4.3 4.4 Zwischen Wirk- und Zweckursachen | 330 Das Vorhalteproblem der Luftabwehr | 330 Vorhersage auf der Basis von Beobachtung | 334 Stabilität und Stabilisierung | 336 Dynamische Stabilität | 337 5 5.1 5.2 5.3 5.4 Ausgangspunkt Subjekt | 341 Eine kritische Annäherung an źInformation“ | 341 Konstruierende Wahrnehmung | 353 Radikaler Konstruktivismus | 360 Empirisch-wissenschaftliche Methodik | 364 6 6.1 6.2 6.3 Systeme, Systemgrenzen und Wiedereintritt | 369 Vom technischen zum ethischen Systembegriff | 369 Gedächtnis und Wiedereintritt | 373 Operative Geschlossenheit und Eigenform | 376 | IX X | Inhalt 6.4 Selbstorganisation und gesellschaftliches Handeln | 383 7 7.1 7.2 7.3 7.4 Von Determinierbarkeit zu Nicht-Determinierbarkeit | 391 Potenzielle, gegebene und erforderliche Varietät | 392 Reduktion von Varietät | 396 Nicht-determinierbare Maschinen | 401 Ampliőkation von Varietät | 408 8 Ausblick | 419 9 Lektüreempfehlungen | 420 Literatur | 424 Schlagwortverzeichnis | 434 Vorwort Dieser zweite Band der Reihe źMedientechnisches Wissen“ knüpft auf unterschiedliche Art und Weise an die Themen des ersten Bandes an und führt sie weiter. Ging es dort zentral um die medientechnisch-theoretischen Grundlagen (Logik und Informationstheorie), so widmen sich die Autoren dieses Buches nun in drei Teilbänden deren praktischen Anwendungsfällen in der Informatik und der Kybernetik, sowie in der Programmierung von Digitalcomputern. In einer Zeit, in der Digitalcomputer zur dominierenden Medientechnologie in nahezu allen Bereichen von Kultur, Technik und Wissenschaft geworden sind, ist das Wissen um deren Funktionsweisen von immanenter Wichtigkeit ś und das nicht nur für Vertreter¹ jener Fachdisziplinen, die solche Technologien entwickeln. Forderungen nach einem verbindlichen Informatik-Unterricht und der möglichst frühen Einführung in eine Programmiersprache in Schulen reagieren auf diese Entwicklung. źComputer literacy“ als ein didaktisches Konzept, das bereits in den 1980er Jahren dem anwachsenden źComputeranalphabetismus“ (Kittler 1996) entgegenzutreten hoffte, stellt sich heute nicht mehr bloß der Ohnmacht des Endanwenders entgegen, sondern wird auch für die (ehemals źtechnikfernen“) Geistes- und Kulturwissenschaften zum wichtigen Handwerkszeug. Die źDigital Humanities“ stellen diesen Disziplinen Technologien als Forschungswerkzeuge zur Verfügung, die zunächst in ihrer Funktionalität verstanden werden müssen. Nur so wird/bleibt erkennbar, wie sich deren ź[medien]technische Aprioris“ (Ernst 2007:28; Kittler 1986:180) in die Forschung einschreiben. Nietzsches źUnser Schreibzeug arbeitet mit an unserem Gedanken.“ (Nietzsche 2003:18) gilt mehr denn je, wenn künstliche Intelligenzen mithilfe neuronaler Netze Muster in Forschungsdaten suchen und őnden und damit źDenkprozesse“ übernehmen. Medienwissenschaft kann hier eine Vermittlerrolle zukommen, indem sie die speziőschen Methoden und Theorien von Geistes- und Kulturwissenschaften mit technomathematischem und informatischem Wissen zu Medien verbindet und auf diese Weise einen Kanal für die interdisziplinäre Kommunikation öffnet. Dazu ist allerdings Theorie-, Fakten- und Methodenwissen auf beiden Seiten nötig, dessen Grundlagen unsere Lehrbuchreihe stiften möchte. Dies passiert kleinschrittig und ohne speziősche Kenntnisse (jenseits des Abiturs) vorauszusetzen. Im ersten Teilband werden vom Informatiker Thorsten Schöler die grundlegenden Begriffe und Konzepte der Informatik vorgestellt. Über die innere Strukturierung des Fachgebietes in theoretische, technische, praktische, angewandte Informatik sowie dem Arbeitsfeld źInformatik und Gesellschaft“ lassen sich unterschiedlichste Verbindungen zu medientechnischen Anwendungsfällen aufzeigen. Am Anfang steht hier 1 Zur Lektüreerleichterung wird in diesem Buch das generische Maskulin verwendet, womit aber alle Geschlechter gemeint und angesprochen sein sollen. https://doi.org/10.1515/9783110496253-001 2 | Vorwort die Vermittlung des Wissens, dass es sich bei Digitalcomputern um źimplementierte Theorie“ handelt: Die Theorien von Automaten und ihren Sprachen, die zur universellen Rechenmaschine führen, stellen die epistemologische Grundlage für die Architekturen von Rechenmaschinen und Computern dar. Im Informatik-Teilband werden davon ausgehend, die technische Informatik und ihre Geschichte vorgestellt, dann Algorithmen und Datenstrukturen, Bäume und Graphen (als wichtige diagrammatische Beschreibungsmittel für Prozesse) und schließlich das Thema Komplexität, das die Probleme des Zeitverbrauchs von Berechnungsprozessen als ein wichtiges Grenzphänomen von Digitalcomputern vorstellt. Wo möglich, werden Codes (in der Programmiersprache Python) und Beispiele aus der Medientechnik zur Exempliőkation herangezogen. Der zweite Teilband stellt eine Programmierlehre für Medienwissenschaftler dar, in der in vier kurzen Einführungen vier Programmiersprachen vorgestellt werden. Diese berufen sich mehr noch als die anderen Teilbände auf den Einsatz assistierender Sekundärliteratur, denn in der Kürze der Darstellungen kann kaum systematisch in eine Programmiersprache eingeführt werden. Vielmehr soll es um die Kodiőzierung medienwissenschaftlicher Fragestellungen gehen, die sowohl Digitalcomputer selbst als auch andere Medientechnologien betreffen. Programmieren soll dadurch sowohl als Schlüsselkompetenz zum Verständnis von Computern dienen, als auch als medienwissenschaftliches Werkzeug zum źoperativen Argumentieren“ medientechnischer Sachverhalte. Hierzu wurden die vier Sprachen 6502-Assembler, BBC BASIC, C und Python ausgewählt, die von den Medienwissenschaftlern Stefan Höltgen und Johannes Maibaum in einzelnen Kapiteln vorgestellt werden. Der speziősche 8-Bit-Assembler des MOS 6502 hat bereits im Logikteilband (vgl. Band 1, Kap. I.7²) Einsatz gefunden und bezieht sich auf den in Band 4 (dort Kap. II) vorgestellten Selbstbaucomputer MOUSE, der hier vorerst als Emulation für Arduino eingesetzt wird. Das BASIC-Kapitel verfolgt neben den erwähnten Zwecken das Ziel, Programmieren zugleich in seiner Kulturgeschichte zu verorten und diese programmierend als źRe-Enactment“ aufzurufen. Mit der Programmiersprache C wird in das strukturierte Programmieren eingeführt und Aufgaben aus dem Bereich Steuerung und Regelung werden vorgeführt. Python schließlich dient der Möglichkeit, eine źLesekompetenz“ für moderne objektorientierte Sprachen zu vermitteln und die in den Informatik- und Kybernetik-Teilbänden vorgestellten Beispiele zu verstehen. Die Einfachheit und weite Verbreitung Pythons macht die Sprache überdies zu einem idealen Programmiertool für Medienwissenschaftler. Der dritte Teilband rückt die Kybernetik mit ihren medienwissenschaftlichen Implikationen ins Zentrum der Betrachtung. Thomas Fischer, Kybernetiker und Desi2 Die Querverweise zu Kapiteln im selben Band werden wie folgt angegeben: Eine römische Ziffer gibt den Teilband an (hier: I für Informatik, II für Programmierlehre, III für Kybernetik), die nachfolgenden lateinischen Ziffern die jeweiligen Kapitelnummern. Wird zu anderen Bänden der Reihe verwiesen, wird die Angabe źBand“ mit der betreffenden Bandnummer vorangestellt. Vorwort | 3 gnwissenschaftler, führt hier systematisch in diese Disziplin ein. Ausgehend von ihrer historischen Entwicklung (mit einem Blick auf die so genannte źKybernetik erster Ordnung“ ś auch in Hinblick auf die Deutsche Kybernetik), stellt er die Grundprinzipien kybernetischen Denkens vor und exempliőziert diese anhand technischer Apparaturen und in Experimenten. Mit dem Einsatz der źKybernetik zweiter Ordnung“ gerät der Beobachter von Prozessen in den Blick und wird als Element solcher Prozesses selbst mitgedacht. Insbesondere in human- und sozialwissenschaftlichen Fragen lässt sich so Mensch-Maschine-Kopplung alternativ auffassen und ermöglicht es beispielsweise, Simulationen von kulturellen und gesellschaftlichen Prozessen durch Computer als kybernetische Prozesse zu verstehen. Die zahlreichen Experimente im Teilband laden dazu ein, kybernetische Theorien zu źaktualisieren“ und als eine wichtige Strukturwissenschaft (vgl. Artmann 2000:63ff.) für medienwissenschaftliches Denken zugänglich zu machen. Der vorliegende Band kann sowohl als Lehrgrundlage für Einführungskurse als auch als autodidaktische Lektüre dienen³. Neben den Experimenten, die im Buch vorgeschlagen sind, beőnden sich hierfür auf der Webseite des DeGruyter-Verlages⁴ zusätzliche Informationen und Materialien. Um den Erfolg der Experimente zu gewährleisten, sollte die empfohlene Hardware und Software verwendet werden. (Die Autoren haben sich hier auf ein kostengünstiges Setup geeinigt: ein Arduino-Unound ein Raspberry-Pi-3-Computer.) Die Installation der Hardware- und SoftwareKomponenten wird in einem ebenfalls online vorliegenden Dokument beschrieben. Die Redaktion des zweiten Bandes der Reihe źMedientechnisches Wissen“ hat wieder Maria Priebe übernommen, wofür ihr großer Dank gilt. Unterstützt wurde der Entstehungsprozess vom Lehrstuhl für Medientheorien der Humboldt-Universität zu Berlin (namentlich Prof. Dr. Wolfgang Ernst). Technische Unterstützung haben die Autoren und der Herausgeber vom Redaktionsteam der Reihe sowie vom Lektorat des DeGruyter-Verlags erhalten. Auch hierfür sei expliziter Dank ausgedrückt. Berlin im Sommer 2018 Stefan Höltgen 3 Alle Abbildungen stammen, soweit nicht anders vermerkt, von den Autoren der Teilbände. 4 www.degruyter.com 4 | Vorwort Literatur Artmann, S. (2010): Historische Epistemologie der Strukturwissenschaften. München: Fink. Ernst, W. (2007): Das Gesetz des Gedächtnisses. Medien und Archive am Ende (des 20. Jahrhunderts). Berlin: Kadmos. Kittler, F. A. (1986): Grammophon – Film – Typewriter. Berlin: Brinkmann & Bose. Kittler, F. A. (1996): Computeranalphabetismus. In: Matejovski, Dirk /Kittler, Friedrich (Hgg.): Literatur im Informationszeitalter. Frankfurt am Main/New York: Campus, S. 237–251. Nietzsche, F. (2003): Brief an Heinrich Köselitz in Venedig Ende Februar 1882 (Nr. 202). In: Ders.: Schreibmaschinentexte. Vollständige Edition Faksimiles und kritischer Kommentar. Aus dem Nachlass herausgegeben von Stephan Günzel und Rüdiger Schmidt-Grépály. Weimar: Universitätsverlag. Der zweite Band der Lehrbuchreihe Medientechnisches Wissen stellt die Themen Informatik, Kybernetik sowie vier Programmiersprachen für Medienwissenschaftler vor. Damit soll Studenten ein Lehrwerk und Dozenten ein Kompendium an die Hand gegeben werden, in dem die technischen Grundlagen von Medien und der sie betreffenden Fachdisziplinen kleinschrittig vermittelt werden. Im ersten Kapitel wird in für digitale Medientechnik zentrale Aspekte der Informatik eingeführt. Die historischen und epistemologischen Hintergründe des Computers werden dabei ebenso verhandelt, wie Aspekte der theoretischen Informatik, welche die Grenzen dieses Mediums markieren. Das zweite Kapitel stellt die vier Programmiersprachen Assembler, BASIC, C und Python vor. Diese Sprachen sind sowohl als Gegenstände von besonderem medienwissenschaftlichen Interesse als auch als Tools, um digitale Medien programmierend zu erforschen. Mit der Kybernetik im drittem Kapitel wird eine immer noch aktuelle Disziplin in ihrer medienwissenschaftlichen Bedeutung behandelt. Der Akzent liegt hier auf der Kybernetik zweiter Ordnung, die vielfältige Verflechtungen mit der Medienwissenschaft aufweist. In Band 1 wurde in die Themengebiete Logik, Informations- und Speichertheorie eingeführt. Band 3 beschäftigt sich mit der Mathematik, Physik und Chemie der Medien. In Band 4 werden Elektronik, Messtechnik (am Beispiel eines selbstgebauten Computers) und die Facharchäologie für Medienwissenschaftler vorgestellt. Stefan Höltgen (Hrsg.) ist Medienwissenschaftler an der Humboldt-Universität zu Berlin. Er lehrt dort Theorien, Geschichte und Informatik der Medien und forscht zur Archäologie früher Mikrocomputer und ihrer Programmierung. Thorsten Schöler ist Professor für Informatik an der Fakultät für Informatik an der Hochschule für angewandte Wissenschaften Augsburg, Koordinator der Forschungsgruppe Verteilte Systeme und seit 2016 Honorary Doctor of Odessa National Polytechnic University. Johannes Maibaum ist Medieninformatiker und entwickelt eingebettete Multimediasysteme für tonwelt GmbH (Berlin). Er studierte Medienwissenschaft an der HU Berlin mit den Schwerpunkten Technikphilosophie und Computerarchäologie. Thomas Fischer ist Professor für Architektur an der Xi‘an Jiaotong-Liverpool Universität in Suzhou (China), Designforscher und Kybernetiker, Fellow der Design Research Society sowie ein Vize-Präsident und Träger des Warren McCulloch Award der American Society for Cybernetics. www.degruyter.com ISBN 978-3-11-049624-6