Juraj Hromkoviˇc

Lehrbuch Informatik

Juraj Hromkoviˇc

Lehrbuch

Informatik

Vorkurs Programmieren, Geschichte und Begriffsbildung, Automatenentwurf

STUDIUM

Bibliografische Information der Deutschen Nationalbibliothek

Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der

Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über <http://dnb.d-nb.de> abrufbar.

Prof. Dr. Juraj Hromkoviˇc

Geboren 1958 in Bratislava, Slowakei. Studium der Mathematischen Informatik an der Komensk´y Universität, Bratislava. Promotion (1986) und Habilitation (1989) in Informatik an der Komensk´y Universität. 1990 – 1994 Gastprofessor an der Universität Paderborn, 1994 – 1997 Professor für Parallelität an der CAU Kiel. 1997 – 2003 Professor für Algorithmen und Komplexität an der RWTH Aachen. Seit 2001 Mitglied der Slowakischen Gesellschaft. Seit Januar 2004 Professor für Informatik an der ETH Zürich.

1. Auflage 2008

Alle Rechte vorbehalten

© Vieweg +Teubner | GWV Fachverlage GmbH, Wiesbaden 2008

Lektorat: Ulrich Sandten | Kerstin Hoffmann

Vieweg+Teubner ist Teil der Fachverlagsgruppe Springer Science+Business Media. www.viewegteubner.de

Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen.

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichenund Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften.

Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg

Druck und buchbinderische Verarbeitung: Strauss Offsetdruck, Mörlenbach Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier.

Printed in Germany

ISBN 978-3-8348-0620-8

Vorwort

Dieses Lehrbuch ist der erste Schritt in unseren Bemühungen die große Lücke in den Unterrichtsmaterialien für Informatik an Gymnasien und für das Lehramtsstudium zu schließen. Somit ist dieses Buch das erste in einer geplanten Serie von Lehrbüchern. Unser Ziel ist nicht der Versuch, den Inhalt des Informatikunterrichts festzulegen, sondern ein viel größeres Angebot an Themen zu unterbreiten, als man tatsächlich aus Zeitgründen im Unterricht umsetzen kann. Dies entspricht auch der dynamischen Entwicklung der Informatik. Mit Ausnahme von unbestreitbaren fundamentalen Konzepten hat es keinen Sinn heute darüber zu streiten, welche Fachgebiete in Zukunft tragbarer als andere sein werden. Deswegen bieten wir den Lehrpersonen die Wahl, sich geeignete Themen und die Stufe ihrer Vertiefung abhängig von eigenen Kenntnissen, Interessen und Schwerpunkten auszusuchen. Darum strukturieren wir unsere Unterrichtsunterlagen in Form von Modulen. Jedes Modul ist einem Thema gewidmet und entspricht im Umfang 16 bis 32 Unterrichtsstunden. Die Module bestehen jeweils aus mehreren Lektionen unterschiedlicher Schwierigkeitsgrade, die die Wahl eines angestrebten Vertiefungsgrads oder einen differenzierten Unterricht ermöglichen. Die Module selbst sind so weit wie möglich von der Kenntnis anderer Module unabhängig.

Dieses erste Lehrbuch beinhaltet die folgenden drei Module: „Vorkurs Programmieren in LOGO“, „Geschichte und Begriffsbildung“ und „Entwurf von endlichen Automaten“. Das erste Modul bietet eine Einführung in das Programmieren. Mit seinen ersten sechs Lektionen ermöglicht es sogar einen Einstieg ab dem vierten Schuljahr und mit seinen letzten Lektionen ist es mit dem Mathematikunterricht in den letzten Gymnasialklassen verzahnt. Dabei geht es nicht darum, eine höhere Programmiersprache zu erlernen, sondern vielmehr darum, die fundamentalen Konzepte des systematischen Programmierens und ein tieferes Verständnis zu erwerben. Die notwendige Programmierumgebung ist kostenlos verfügbar.

In der tiefen Wurzel jeder Wissenschaftsdiziplin befindet sich die Begriffsbildung, die maßgebend für die Entwicklung einer Disziplin ist. Das Modul „Geschichte und Begriffsbildung“ verfolgt diese Idee, indem es die Geschichte der Informatik anhand der Entwicklung der Grundbegriffe und Grundkonzepte erklärt. Neben einer Erklärung für die fundamentalsten Fachbegriffe wie Algorithmus, Programm und Berechnungskomplexität werden hier auch die Grundlagen des korrekten logischen Denkens und korrekten Argumentierens, sowie das Modell der Registermaschine anhand einer einfachen Assemblersprache vermittelt.

2

Im dritten Modul „Entwurf von endlichen Automaten“ geht es nicht nur darum, ein paar Methoden zum Entwurf von Steuerungsmechanismen zu unterrichten. Im Vordergrund stehen hier die modulare Technik zum systematischen Entwurf von komplexen Systemen sowie die Grundlagen der Modellierung von Rechnern und Berechnungen. Die beiden letzten Module werden durch E-Learning-Systeme zur Programmierung im Assembler und zum Automatenentwurf unterstützt.

Weitere Module, die wir als Fortsetzung planen, sind: „Programmieren in Pascal/Delphi/Oberon“, „Informationssysteme“, „Datenstrukturen und effiziente Implementierung von Algorithmen“, „Kryptologie“, „Wahrscheinlichkeit und zufallsgesteuerte Systeme“, „Schaltkreisentwurf und parallele Algorithmen“, „Geometrische Algorithmen“, „Logik und korrekte Argumentation“, „Methoden zum Algorithmenentwurf“, „Kommunikation und Suche im Internet“, und „Grenzen der Automatisierung“.

Das didaktische Konzept basiert auf dem Ausführlichkeitsgrad von Leitprogrammen. Alles wird sorgfältig erklärt und sofort durch Übungsaufgaben (teilweise mit vorgeschlagenen Lösungen) gefestigt und überprüft. Durch das detaillierte und anschauliche Vorgehen eignet sich das Lehrbuch auch zum Selbststudium im Gymnasialalter. Die Erklärungen sind mit Hinweisen für die Lehrperson begleitet. Diese Hinweise gehen zum einen auf mögliche Schwierigkeiten bei der Vermittlung des Stoffes ein, sprechen zum anderen Empfehlungen für die Verwendung von geeigneten didaktischen Methoden aus und vermitteln Unterrichtserfahrung. Damit ist dieses Lehrbuch auch für das Lehramtsstudium bestimmt, sowie für alle Informatikanfänger oder diejenigen, die Informatik im Nebenfach studieren.

Hilfreiche Unterstützung anderer hat zur Entstehung dieses Lehrbuches wesentlich beigetragen. Besonderer Dank gilt Karin Freiermuth, Roman Gächter, Stephan Gerhard, Lucia Keller, Jela Sherlak, Ute Sprock, Andreas Sprock und Björn Steffen für sorgfältiges Korrekturlesen, zahlreiche Verbesserungsvorschläge und umfangreiche Hilfe bei der Umsetzung des Skriptes in Latex. Für die Sprachkorrekturen bedanke ich mich herzlich bei Frau Regina Lauterschläger. Ich möchte mich sehr bei Karin Freiermuth, Barbara Keller und Björn Steffen dafür bedanken, dass sie mich mit viel Enthusiasmus beim Testen der Unterrichtsunterlagen in der schulischen Praxis begleitet haben oder einige Lektionen selbstständig unterrichtet haben.

Genauso herzlich danke ich den Lehrpersonen Pater Paul (Hermann-Josef-Kolleg, Steinfeld), Uwe Bettscheider (INDA Gymnasium Aachen), Hansruedi Müller (Schweizerische Alpine Mittelschule Davos), Yves Gärtner, Ueli Marty (Kantonsschule Reussbühl), Meike

3

Akveld, Stefan Meier und Pietro Gilardi (Mathematisch-naturwissenschaftliches Gymnasium Rämibühl, Zürich), Harald Pierhöfer (Kantonsschule Limattal, Urdorf) und Michael Weiss (Gymnasium Münchenstein), die es uns ermöglicht haben, in einigen Klassen kürzere oder längere Unterrichtssequenzen zu testen oder sie sogar selbst getestet haben und uns ihre Erfahrungen mitgeteilt haben. Ein besonderer Dank geht auch an die Schulleitungen der Schulen, die uns für das Testen unserer Module die Türen geöffnet haben. Für die hervorragende Zusammenarbeit und die Geduld mit einem immer eigensinniger werdenden Professor bedanke ich mich herzlich bei Frau Kerstin Hoffmann und Herr Ulrich Sandten vom Teubner Verlag.

Ich wünsche allen Leserinnen und Lesern beim Lernen mit diesem Buch so viel Vergnügen, wie wir selbst beim Unterrichten der vorliegenden Lektionen empfunden haben.

Zürich, im September2008

Juraj Hromkovicˇ

Inhaltsverzeichnis

6 Inhaltsverzeichnis

Modul I

Vorkurs Programmieren in LOGO