Informatik

Eine praktische Einführung mit Bash und Python

Tobias Häberlein

• Publisher: De Gruyter Oldenbourg
• Year: 2016
• eBook ISBN: 9783110495690
• Edition: 2
• Topic: Computer Science
• Subtopic: Computer Science General
• Index: Computer Science

Die praktische Informatik lebt vom Ausprobieren verschiedener Lösungswege, dem Experimentieren mit Programmkonstrukten und Algorithmen, und allgemein vom "Selbermachen". Darauf baut das didaktische Konzept des Buchs auf: Anhand einer Vielzahl an Aufgaben kann der Student die präsentierten Konzepte selbst erfahren, mit Ihnen arbeiten und so die eigentlichen Probleme der Informatik wirklich verstehen.

1Was ist Informatik?

Der Begriff „Informatik“ wurde bereits Ende der 50er Jahre von dem deutschen Professor Dr. Karl Steinbuch geprägt. Den Begriff „Informatik“ kann man sich entweder zusammengesetzt aus den Wörtern „Information“ und „Automatik“ denken – will man die Tatsache betonen, dass es in der Informatik um die automatische Verarbeitung von Informationen geht. Will man dagegen die Ähnlichkeit der Informatik und der Mathematik betonen, so kann man sich den Begriff „Informatik“ zusammengesetzt aus den Wörtern „Information“ und „Mathematik“ denken.

Während man die Mathematik als eine Wissenschaft des „formal1 Denkbaren“ auffassen kann, beschäftigt sich die Informatik mit dem „formal Realisierbaren“, also mit Berechnungen, die maschinell ausgeführt werden können. Ihre Fragestellungen, etwa zur Berechenbarkeit oder zur künstlichen Intelligenz, reichen bis in die Philosophie hinein. Kleines Beispiel: Ist die folgende Funktion (mit Hilfe einer automatischen Rechenmaschine, also einem Computer) berechenbar?

Aufgabe 1.1

Überlegen Sie sich, wie ein Computer-Programm – unabhängig von einer bestimmten Programmiersprache – aussehen könnte, das diese Funktion f versucht zu berechnen. Was spricht dagegen, die Funktion f als „berechenbar“ zu bezeichnen?

Ausgewählte Pioniere der Informatik

Die folgende Liste der „Pioniere der Informatik“ ist subjektiv und könnte, von einer anderen Person erstellt, anders aussehen. Diese Liste enthält wichtige Persönlichkeiten aus den Bereichen der Theoretischen (Gödel, Turing, Chomsky, Knuth, Cook) und Praktischen Informatik (Richie, Thompson, Torvalds, Stallman, Peyton-Jones).

Vieles von dem, was auf den folgenden Seiten beschrieben wird, ist für den Informatik-Anfänger nicht einfach zu verstehen, und es wird auch nicht erwartet, dass Sie alles Beschriebene im Detail genau verstehen – es ist eher dafür gedacht, ihr Interesse für die Informatik und die theoretischen Grundlagen der Informatik zu wecken, und auch um Sie in die Lage zu versetzen, zumindest von den „großen“ Problemen der Informatik „schon einmal gehört“ zu haben.

Kurt Gödel

1906 – 1978

Gödel beschäftigte sich unter anderem mit maschinell (d. h. durch eine automatische Rechenmaschine wie ein Computer) ableitbaren Aussagen. Von ihm stammt der „Gödelsche Unvollständigkeitssatz“. Mit ihm beweist Gödel, dass es sogar in dem einfachsten Teilbereich der Mathematik, der Zahlentheorie (also der Theorie ganzer Zahlen), wahre Aussagen geben muss, die man nicht automatisiert ableiten bzw. beweisen kann. Dies versetzte der Mathematik der damaligen Zeit, den 30er Jahren des 20. Jahrhunderts, einen herben Schlag. Bis dahin war man fest davon überzeugt, die Mathematik widerspruchsfrei formalisieren zu können, d. h. in eine Form zu bringen, die auch eine Maschine „verstehen“ könnte und mit der eine Maschine so umgehen könnte, dass sie aus den formalisierten Grundvoraussetzungen (oft auch Axiome genannt) alle wahren Aussagen der Mathematik automatisch ableiten könnte.

Alan Turing

1912 – 1954

Der junge Turing interessierte sich für das sogenannte „Entscheidungsproblem“ (auch im englischsprachigen Raum so genannt), eines der “Hilbertschen Probleme”2. Das Entscheidungsproblem lässt sich folgendermaßen formulieren: Gibt es, zumindest prinzipiell, eine mechanisch anwendbare Methode, die entscheiden kann, ob eine gegebene mathematische Behauptung beweisbar ist?

Um dieses Problem zu lösen, versuchte/hom Turing zunächst formal zu definieren, was unter einer „mechanisch anwendbaren Methode“ zu verstehen sei. Er drückte seine Definition in Form einer theoretischen Maschine aus, die bestimmte, wohl definierte Operationen auf einem Streifen Papier durchführen konnte. Diese „Maschine“, mit der Turing definierte, was unter „berechenbar“ zu verstehen sei, nennt man die Turingmaschine. Mit Hilfe dieses formalen Konzeptes einer Rechenmaschine konnte Turing beweisen, dass das Entscheidungsproblem unlösbar ist.

Es stellte sich im Weiteren heraus, dass die Turingmaschine tatsächlich exakt die Fähigkeiten jedes Computers beschreibt: Eine Turingmaschine ist prinzipiell nicht mehr oder weniger leistungsfähig als jeder heutige Computer (ausgenommen: Quantencomputer). Mit Hilfe des einfachen mathematischen Modells der Turingmaschine lassen sich viele grundsätzliche Dinge über Berechenbarkeit zeigen.

Außerdem war Turing maßgeblich am Entschlüsseln geheimer Nachrichten der Nazis beteiligt.

Noam Chomsky

*1928

Noam Chomsky formalisiert die Darstellung und den Aufbau natürlicher Sprachen mit formalen „Grammatiken“. Diese Grammatiken definierten rekursiv den Aufbau und das Verhältnis der einzelnen Sprachelemente zueinander. Er entwickelte die sog. Chomsky-Hierarchie, in der er Klassen von Sprachen nach ihrer Komplexität „sortierte“: Typ-3-Sprachen sind die einfachsten; Typ-0-Sprachen die komplexesten. Um eine Typ-0-Sprache zu bauen bzw. zu erkennen, benötigt man den vollen Funktionsumfang einer Turing-Maschine. Um Typ-1-Sprachen zu erkennen genügen einfachere „Maschinen“, usw.

Besonders im Compilerbau und in vielen Bereichen der Theoretischen Informatik sind Chomskys Arbeiten auch heute noch sehr wichtig.

Donald E. Knuth

*1938

Donald E. Knuth ist Autor der mehrbändigen Buchreihe „The Art of Computer Programming“ und der Begründer der formalen Analyse und Laufzeitanalyse von Algorithmen. Er war der erste, der die Groß-Oh-Notation systematisch zur Beschreibung des Laufzeitverhaltens von Algorithmen verwendete. Unter anderem hat er den „Knuth-Morris-Pratt“-Algorithmus entwickelt, der im Vergleich zu älteren Ansätzen eine deutlich schnellere String-Matching3-Methode bereitstellte (d. h. eine Methode, um alle Vorkommen eines bestimmten Strings in einem Text zu suchen).

Außerdem hat Knuth das Textsatzsystem TEX entwickelt (mit dem auch dieses Buch geschrieben wurde) inklusive der zugehörigen Zeichendefinitionssprache Metafont.

Stephen A. Cook

*1939

Stephen A. Cook formulierte und erforschte das für die Theoretische Informatik grundlegende und bis heute ungelöste P/NP-Problem. Es gilt als eines der wichtigsten ungelösten Probleme der Mathematik und Informatik. In der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik, geht es darum, „Probleme“4 anhand des Zeitaufwands zu klassifizieren, der benötigt wird, um sie zu lösen. Die Anzahl der zur Lösung maximal benötigten Berechnungsschritte wird auch als Zeitkomplexität bezeichnet.

Die Komplexitätsklasse P bezeichnet die Menge von Problemen, deren Laufzeit auf einer Turingmaschine sich im Verhältnis zur Größe n der Eingabe durch ein Polynom nk beschreiben lässt: Das Sortierproblem, beispielsweise, liegt in P, da man Algorithmen angeben kann, die eine Liste mit n Elementen (die Größ...

Table of contents

• Cover
• Titelseite
• Impressum
• Vorwort
• Inhalt
• 1 Was ist Informatik?
• 2 Unix/Linux und Shell-Programmierung
• 3 Python-Programmierung
• 4 Programmierung mit regulären Ausdrücken
• 5 Datenbanken und Datenbankprogrammierung
• 6 Internet und Internetprogrammierung
• 7 Nebenläufige und Parallele Programmierung
• Literatur
• Stichwortverzeichnis
• Fußnoten