Programmierung, Algorithmen und Datenstrukturen

Heinz-Peter Gumm, Manfred Sommer

• Verlag: De Gruyter Oldenbourg
• Jahr: 2016
• ISBN:
  9783110442311
• Auflage: 1
• Thema: Computer Science
• Thema: Computer Science General

Dieser erste Band der Informatik erklärt die grundlegenden Konzepte: Programmierung, Algorithmen und Datenstrukturen. Nach einer Einführung zum Aufbau von Rechnersystemen und zur Darstellung von Informationen folgt ein Einstieg in die Programmierung mit der Sprache Python. Dabei werden grundsätzliche Prinzipien von Programmiersprachen erläutert, darunter Schleifen, Rekursion, imperative, funktionale und objektorientierte Programmierkonzepte. Einige konkrete Projekte werden in Python realisiert, so etwa zur Datenbeschaffung im Internet und deren Aufbereitung oder zum Umgang mit diversen Sensoren und zur Steuerung externer Geräte mit dem Raspberry-Pi. Dem Objektorientierten Programmieren und insbesondere der Programmiersprache Java ist ein eigenes Kapitel gewidmet. Diese Sprache und ihre Infrastruktur unterstützen besonders die professionelle Entwicklung großer Projekte. Auch die neuesten Konzepte von Java (Lambdas, Ströme und Funktionale) werden anschaulich erläutert. Das letzte Kapitel behandelt klassische Algorithmen und Datenstrukturen: Such- und Sortieralgorithmen, Listen, Bäume, Graphen, Maps, und diverse andere Datentypen zum effi zienten Speichern, Wiederauffi nden und Transformieren von Daten. Diese werden mit ihren Vor- und Nachteilen und anhand von Java-Programmen dargestellt.

Der zweite Band ist technischen Themen gewidmet – insbesondere der Rechnerarchitektur, Betriebssystemen, Rechnernetzen und speziell dem Internet. Der dritte und letzte Band der Buchreihe Informatik ist der Theoretischen Informatik gewidmet.

Das Buch richtet sich an alle Einsteiger, die sich ernsthaft mit Informatik beschäftigen wollen, sei es zum Selbststudium oder zur Begleitung von Vorlesungen. In den folgenden Bänden dieses Buches werden die Themen, Rechnerarchitektur, Betriebssysteme, Rechnernetze, Internet, Compilerbau und Theoretische Informatik vertieft.

Prof. Dr. Heinz-Peter Gumm

ist Professor für Theoretische Informatik in Marburg. Nach dem Studium in Darmstadt und Winnipeg (Kanada) von 1970 bis 1975 und der Habilitation 1981 folgten Professuren in Hawaii, Kalifornien und New York. Seine Forschungsgebiete sind Formale Methoden, Allgemeine Algebren und Coalgebren.

Prof. Dr. Manfred Sommer

ist emeritierter Professor für Praktische Informatik in Marburg. Nach dem Studium in Göttingen und München von 1964 bis 1969, war er Assistent am ersten Informatik-Institut in Deutschland an der TU München. Es folgten zehn Jahre bei Siemens in München und von 1984 bis 2014 war er Informatik-Professor in Marburg.

Kapitel 1

Grundlagen

In diesem Kapitel werden wir wichtige Themen der Informatik in einer ersten Übersicht darstellen. Zunächst beschäftigen wir uns mit dem Begriff Informatik, dann mit fundamentalen Grundbegriffen wie z.B. Bits und Bytes. Danach behandeln wir die Frage, wie Texte, logische Werte und Zahlen in Computern gespeichert werden. Wir erklären den Aufbau eines PCs und das Zusammenwirken von Hardware, Controllern, Treibern und Betriebssystem bis zur benutzerfreundlichen Anwendungssoftware. Viele der hier eingeführten Begriffe werden in den späteren Kapiteln noch eingehender behandelt. Daher dient dieses Kapitel als erster Überblick und als Grundsteinlegung für die folgenden.

1.1Was ist „Informatik“?

Der Begriff Informatik leitet sich von dem Begriff Information her. Er entstand in den 60er Jahren. Informatik ist die Wissenschaft von der maschinellen Informationsverarbeitung. Die englische Bezeichnung für Informatik ist Computer Science, also die Wissenschaft, die sich mit Rechnern beschäftigt. Wenn auch die beiden Begriffe verschiedene Blickrichtungen andeuten, bezeichnen sie dennoch das Gleiche. Die Spannweite der Disziplin Informatik ist sehr breit, und demzufolge ist das Gebiet in mehrere Teilgebiete untergliedert.

1.1.1Technische Informatik

Die Technische Informatik beschäftigt sich vorwiegend mit der Konstruktion von Rechnern, Speicherchips, schnellen Prozessoren oder Parallelprozessoren, aber auch mit dem Aufbau von Peripheriegeräten wie Festplatten, Druckern und Bildschirmen. Die Grenzen zwischen der Technischen Informatik und der Elektrotechnik sind fließend. An einigen Universitäten gibt es den Studiengang Datentechnik, der gerade diesen Grenzbereich zwischen Elektrotechnik und Informatik zum Gegenstand hat.

Man kann vereinfachend sagen, dass die Technische Informatik für die Bereitstellung der Gerätschaften, der so genannten Hardware, zuständig ist, welche die Grundlage jeder maschinellen Informationsverarbeitung darstellt. Naturgemäß muss die Technische Informatik aber auch die beabsichtigten Anwendungsgebiete der Hardware im Auge haben. Insbesondere muss sie die Anforderungen der Programme berücksichtigen, die durch diese Hardware ausgeführt werden sollen. Es ist ein Unterschied, ob ein Rechner extrem viele Daten in begrenzter Zeit verarbeiten soll, wie etwa bei der Wettervorhersage oder bei der Steuerung einer Raumfähre, oder ob er im kommerziellen oder im häuslichen Bereich eingesetzt wird, wo es mehr auf die Unterstützung intuitiver Benutzerführung, die Präsentation von Grafiken, Text oder Sound ankommt.

1.1.2Praktische Informatik

Die Praktische Informatik beschäftigt sich im weitesten Sinne mit den Programmen, die einen Rechner steuern. Im Gegensatz zur Hardware sind solche Programme leicht veränderbar, man spricht daher auch von Software. Es ist ein weiter Schritt von den recht primitiven Operationen, die die Hardware eines Rechners ausführen kann, bis zu den Anwendungsprogrammen, wie etwa Textverarbeitungssystemen, Spielen und Grafiksystemen, mit denen ein Anwender umgeht. Die Brücke zwischen der Hardware und der Anwendungssoftware zu schlagen, ist die Aufgabe der Praktischen Informatik.

Ein klassisches Gebiet der Praktischen Informatik ist der Compilerbau. Ein Compiler übersetzt Programme, die in einer technisch-intuitiven Notation, einer so genannten Programmiersprache, formuliert sind, in die stark von den technischen Besonderheiten der Maschine geprägte Notation der Maschinensprache. Es gibt viele populäre Programmiersprachen, darunter BASIC, Cobol, Fortran, Pascal, C, C++, C#, Java, Scala, JavaScript, PHP, Python, Perl, LISP, ML und PROLOG. Programme, die in solchen Hochsprachen formuliert sind, können nach der Übersetzung durch einen Compiler auf den verschiedensten Maschinen ausgeführt werden oder, wie es im Informatik-Slang heißt, laufen. Ein Programm in Maschinensprache läuft dagegen immer nur auf dem Maschinentyp, für den es geschrieben wurde.

1.1.3Theoretische Informatik

Die Theoretische Informatik beschäftigt sich mit den abstrakten mathematischen und logischen Grundlagen aller Teilgebiete der Informatik. Theorie und Praxis sind in der Informatik enger verwoben, als in vielen anderen Disziplinen, theoretische Erkenntnisse sind schneller und direkter einsetzbar. Durch die theoretischen Arbeiten auf dem Gebiet der formalen Sprachen und der Automatentheorie zum Beispiel hat man das Gebiet des Compilerbaus heute sehr gut im Griff. In Anlehnung an die theoretischen Erkenntnisse sind praktische Werkzeuge entstanden. Diese sind selbst wieder Programme, mit denen ein großer Teil des Compilerbaus automatisiert werden kann. Bevor eine solche Theorie existierte, musste man mit einem Aufwand von ca. 25 Bearbeiter-Jahren (Anzahl der Bearbeiter * Arbeitszeit = 25) für die Konstruktion eines einfachen Compilers rechnen, heute erledigen Studenten eine vergleichbare Aufgabe im Rahmen eines Praktikums.

Neben den Beiträgen, die die Theoretische Informatik zur Entwicklung des Gebietes leistet, ist die Kenntnis der theoretischen Strukturen eine wichtige Schulung für jeden, der komplexe Systeme entwirft. Gut durchdachte, theoretisch abgesicherte Entwürfe erweisen sich auch für hochkomplexe Software als sicher und erweiterbar. Software-Systeme, die im Hauruck-Verfahren entstehen, stoßen immer bald an die Grenze, ab der sie nicht mehr weiterentwickelt werden können. Die Entwicklung von Software sollte sich an der Ökonomie der Theoriebildung in der Mathematik orientieren – möglichst wenige Annahmen, möglichst keine Ausnahmen. Ein wichtiger Grund etwa, warum die Konstruktion von Fortran-Compilern so kompliziert ist, liegt darin, dass dieses Prinzip bei der Definition der Programmiersprache nicht angewendet wurde. Jeder Sonder- oder Ausnahmefall, jede zusätzliche Regel macht nicht nur dem Konstrukteur des Compilers das Leben schwer, sondern auch den vielen Fortran-Programmierern.

1.1.4Angewandte Informatik

Die Angewandte Informatik beschäftigt sich mit dem Einsatz von Rechnern in den verschiedensten Bereichen unseres Lebens. Da in den letzten Jahren die Hardware eines Rechners für jeden erschwinglich geworden ist, gibt es auch keinen Bereich mehr, der der Computeranwendung verschlossen ist. Einerseits gilt es, spezialisierte Programme für bestimmte Aufgaben zu erstellen, andererseits müssen Programme und Konzepte entworfen werden, die in vielfältigen Umgebungen einsetzbar sein sollen. Beispiele für solche universell einsetzbaren Systeme sind etwa Textverarbeitungssysteme oder Tabellenkalkulationssysteme (engl. spreadsheet). Angewandte Informatik nutzt heute jeder, der im Internet die aktuelle Tageszeitung liest, seine E-Mail erledigt, Bankgeschäfte tätigt, chattet, sich in sozialen Netzwerken tummelt, Musik herunterlädt, oder nur Filme anschaut.

Auch die Angewandte Informatik ist nicht isoliert von den anderen Gebieten denkbar. Es gilt schließlich, sowohl neue Möglichkeiten der Hardware als auch im Zusammenspiel von Theoretischer und Praktischer Informatik entstandene Werkzeuge einer sinnvollen Anwendung zuzuführen. Als Beispiel mögen die Smartphones, Organizer und Tablet-PCs dienen, die im Wesentlichen aus einem Flüssigkristall-Bildschirm bestehen, den man mit einem Griffel oder einfach mit Fingergesten bedienen kann. Die Angewandte Informatik muss die Einsatzmöglichkeiten solcher Geräte, etwa in der mobilen Lagerhaltung, auf der Baustelle oder als vielseitiger, „intelligenter“ Terminkalender entwickeln. Die Hardware wurde von der Technischen Informatik konstruiert, die Softwaregrundlagen, etwa zur Handschrifterkennung, von der Praktischen Informatik aufgrund der Ergebnisse der Theoretischen Informatik gewonnen.

Wenn man im deutschsprachigen Raum auch diese Einteilung der Informatik vornimmt, so ist es klar, dass die einzelnen...