Skip to main content
main-content

Über dieses Buch

Dieses Buch ist aus dem Vorkurs Informatik entstanden, der von den Autoren seit 2001 an der Universitat Dortmund etwa einen Monat vor Beginn der Vorlesungszeit des Wintersemesters ver­ anstaltet wird. Die Idee zur Einfiihrung eines Vorkurses Informatik kam durch Erfahrungen in der Vorlesung ,,Einfiihrung in die Programmierung" im WS 2000/2001 auf. Diese Vorlesung, an der bedingt durch den IT-Boomjener Zeit mehr als 1000 Studierende teilnahmen, machte besonders deutlich, dass die Studienanfangerinnen und -anfanger eine sehr unterschiedliche Grundausbil­ dung in Informatik aus der Schule mitbringen. Dies macht die Durchfiihrung einer Einfiihrungs­ vorlesung, welche fiir die Mehrzahl der Teilnehmerinnen und Teilnehmer angemessen ist, recht schwer. Das Ziel des Vorkurses ist, einen einheitlichen Kenntnisstand zu erreichen. Der Vorkurs Informatik an der Universitat Dortmund wird sehr gut nachgefragt. Etwas mehr als die Halfte der spateren Studienanfangerinnen und und Anfanger des Faches Informatik nehmen teil. Hinzu kommen angehende Studierende aus anderen Fachern (Mathematik, Wirtschaftsinge­ nieurwesen, Betriebswirtschaftslehre, Informationstechnik), deren Teilnahme sich jedoch oft auf den ersten Teil, eine Einfiihrung in die Programmierung, beschrankt. Zu erwahnen ist, dass sich das bisher verfugbare Folienskript auch bei Studierenden der ersten Semester gro8er Beliebtheit erfreut, wie Download-Zahlen zeigen. Anonyme fragebogenbasierte Nachfragen zu Beginn des dritten Semesters zeigen, dass der Vorkurs trotz der bis dahin nicht nur positiven Priifungserfah­ rungen der Studierenden von 40% als nutzlich und von 51 % etwas nutzlich eingestuft wird. All dies hat uns bewogen, dieses Buch zu schreiben.

Inhaltsverzeichnis

Frontmatter

Einleitung

Einleitung

Zusammenfassung
Das Ziel dieses Buches ist es, eine Grundbildung in Informatik zu vermitteln, die den Einstieg in das Studium der Informatik und benachbarter Fächer erleichtern soll. Es wendet sich vor allem an Leserinnen und Leser, die keinen durchgängigen Informatikunterricht an der Schule haben oder hatten. Aber auch für diejenigen, die schon gute Kenntnisse der Informatik haben, sind Kapitel enthalten, die fortgeschrittenere Themen aufgreifen.
Heinrich Müller, Frank Weichert

Was ist Informatik?

Frontmatter

1. Informatik

Zusammenfassung
Eine Möglichkeit, sich dem Begriff Informatik zu nähern, sind typische Ausdrücke, die mit Informatik zu tun haben: Information, Informationssysteme, Computer, EDV, Rechner, Programmierung, Software, Hardware, Internet, Textverarbeitung, Computerspiele. Betrachtet man diese Begriffe, so stellt man fest, dass „Information“ und „Computer“ eine wesentliche Rolle spielen.
Heinrich Müller, Frank Weichert

Programmierung

Frontmatter

2. Vom Problem über den Algorithmus zum Programm

Zusammenfassung
Computer sind heute praktisch überall zu finden. Entsprechend groß ist die Vielzahl der Problemstellungen, mit denen man bei der Entwicklung von Programmen und Software-Systemen konfrontiert ist. Viele Problemstellungen erscheinen auf den ersten Blick recht weit von dem entfernt, was von Rechnern zu bewältigen ist, oder scheinen von sehr unterschiedlicher Natur zu sein. Um mit diesen Schwierigkeiten zurecht zu kommen, bietet die Informatik Problemlösungsstrategien an, die sich bewährt haben. In Abschnitt 2.1 dieses Kapitels stellen wir eine Vorgehensweise vor, in deren Zentrum das Konzept des „Algorithmus“ steht. Der Begriff des Algorithmus wird in Abschnitt 2.2 behandelt. Abschnitt 2.3 präsentiert ein Beispiel zur Verdeutlichung der Vorgehensweise.
Heinrich Müller, Frank Weichert

3. Algorithmenentwurf

Zusammenfassung
Dieses Kapitel führt in Grundkonzepte zur Formulierung von Algorithmen ein. Abschnitt 3.1 präsentiert einen Algorithmus für das Problem der Suche nach dem kleinsten Wert in einer endlichen Menge von Zahlen, der solche Grundkonzepte exemplarisch verwendet. Seine Funktionsweise wird an einem Beispiel verdeutlicht. Abschnitt 3.2 stellt dann diese Grundkonzepte im Einzelnen vor, beispielsweise die Verwendung von Variablen, bedingten Anweisungen und Schleifen. Er schließt mit einer grafischen Alternative zur sprachlichen Formulierung von Algorithmen, der Darstellung durch Ablaufdiagramme, die am Beispiel des Algorithmus für die Minimumsuche demonstriert wird.
Heinrich Müller, Frank Weichert

4. Grundkonzepte der Programmierung

Zusammenfassung
Nach der Einführung in den Algorithmenentwurf des vorigen Kapitels befassen wir uns nun mit der Überführung von Algorithmen in Programme, die auf Computern ausführbar sind. Zur Formulierung von Programmen verwenden wir Elemente der Programmiersprache Java.
Heinrich Müller, Frank Weichert

5. Funktionen

Zusammenfassung
Dieses Kapitel erweitert die uns bisher bekannten Möglichkeiten des Algorithmenentwurfs und der Programmierung um ein weiteres Konzept: die Funktionen. Wir demonstrieren zunächst die Nützlichkeit von Funktionen an Algorithmen zum Sortieren einer endlichen Menge von Zahlen. Bei den Algorithmen handelt es sich um Varianten der Idee des Sortierens durch Minimumsuche, die in den Abschnitten 5.1, 5.1.1 und 5.1.2 vorgestellt werden. Abschnitt 5.2 beschreibt das Konzept der statischen Methoden von Java, die in dieser Programmiersprache die Rolle von Funktionen übernehmen. Die Deklaration von Funktionen, die auch als Unterprogramme verstanden werden können, wirft die Frage nach der Abhängigkeit des Ortes der Verwendbarkeit von Elementen eines Programms auf. Beispielsweise ist in diesem Zusammenhang der Ort einer Variablendeklaration von Interesse. Dies führt zum Begriff des Gültigkeitsbereichs von Deklarationen, der Gegenstand von Abschnitt 5.3 ist.
Heinrich Müller, Frank Weichert

6. Rekursion

Zusammenfassung
Rekursion ermöglicht es, Algorithmen für viele Probleme besonders kurz und elegant zu formu lieren, indem der Algorithmus, angewendet auf reduzierte Problemversionen, sich wieder selbst verwendet. Abschnitt 6.1 führt das Prinzip der Rekursion anhand eines weiteren Algorithmus zum Sortieren einer Folge von Zahlen, dem Sortieren durch Mischen, ein. Abschnitt 6.1.2 zeigt, wie dieser Algorithmus als Java-Programm unter Verwendung von Funktionen realisiert werden kann. Dem Sortieren durch Mischen liegt das allgemeine Prinzip des „Divide and Conquei“ zu grunde, das in Abschnitt 6.2 vorgestellt wird. Algorithmen, die diesem Prinzip folgen, lassen sich häufig in natürlicher Weise rekursiv formulieren.
Heinrich Müller, Frank Weichert

7. Klassen und Objekte

Zusammenfassung
Wie wir bereits wissen, bezeichnet ein Datentyp eine Menge von Daten gleicher Art. Beispiele sind die ganzen Zahlen, reelle Zahlen, Wahrheitswerte oder Zeichenketten. Diese Datentypen sind für den Einsatz eines Computers als „Rechenmaschine“ ausreichend. Es fällt jedoch schwer, damit in intuitiver Weise nichtnumerische Daten zu handhaben. Daher bieten höhere Programmiersprachen die Möglichkeit zur Deklaration eigener, komplexerer Datentypen, die es erlauben, Datensätze oder Objekte anzulegen, die sich aus anderen Daten zusammensetzen.
Heinrich Müller, Frank Weichert

8. Objektorientierte Programmierung

Zusammenfassung
Im vorangehenden Kapitel haben wir die Bedeutung des Konzeptes der Klassen und Objekte im Wesentlichen dadurch begründet, dass es durch sie möglich wird, zusammengesetzte Datentypen und Datenstrukturen zu deklarieren und zu verwenden. Diese Datentypen erlauben es, Daten in intuitiverer Weise zu speichern und zu handhaben, als es die primitiven Datentypen vermögen. Klassen und Objekte sind aber auch die Basis eines Ansatzes zur Lösung von Problemen, der sich von dem algorithmischen Grundgedanken unterscheidet, den wir bis jetzt praktiziert haben: dem Ansatz der objektorientierten Modellierung und Programmierung.
Heinrich Müller, Frank Weichert

9. Klassenbibliotheken

Zusammenfassung
Die Effizienz von Programmiersprachen zur Lösung von Problemen ist insbesondere durch die Verfügbarkeit von Programmstücken zur Lösung immer wieder auftretender Aufgaben bestimmt. Zur Verwaltung und Verwendung existierender Programmstücke bieten manche Programmiersprachen Mechanismen zur Organisation von Programmpaketen an. Abschnitt 9.1 führt in das Konzept der „Packages“ von Java ein, die diesem Zweck dienen. Es folgen verschiedene Beispiele der Nutzung: Applets (Abschnitt 9.2), Systemzeit (Abschnitt 9.3) und Streams (Abschnitt 9.4).
Heinrich Müller, Frank Weichert

10. Grafikprogrammierung mit Swing

Zusammenfassung
Für die Nutzung von Computern hat die Verwendung von Grafik hohe Bedeutung erlangt. Es existieren Programmpakete, die eine effiziente Realisierung von grafischen Benutzungsschnittstellen von Programmen ermöglichen. Dieses Kapitel demonstriert Möglichkeiten solcher Programmpakete anhand des Java-Pakets Swing. Nach einer allgemeinen Einführung in die Grafikprogrammierung mit Java in Abschnitt 10.1 gibt Abschnitt 10.2 Grundlagen zur Implementierung einer einfachen Benutzungsschnittstelle. Die Konzepte werden im Abschnitt 10.3 genutzt, um zwei Beispiele zur Grafikprogrammierung zu realisieren. Den Abschluss des Kapitels bildet ein ausführlicheres Beispielprogramm in Form einer praktischen Aufgabe.
Heinrich Müller, Frank Weichert

11. Andere Programmierstile

Zusammenfassung
In den vorangegangenen Kapiteln haben wir im Wesentlichen zwei Ansätze zur Lösung von Problemen beschrieben: den algorithmischen Ansatz und den objektorientierten Ansatz. Daneben haben zwei weitere Vorgehensweisen Bedeutung erlangt: der funktionale Ansatz und der logikbasierte Ansatz. In diesem Kapitel geben wir eine kurze Übersicht über diese Vorgehensweisen und entsprechende Programmiersprachen, die es erlauben, die entwickelten Lösungen auf effektive und effiziente Weise in Programme umzusetzen. Es gliedert sich in Abschnitte zur imperativen Programmierung 11.2, funktionalen Programmierung 11.3 und logischen Programmierung 11.4.
Heinrich Müller, Frank Weichert

Algorithmen und Datenstrukturen

Frontmatter

12. Asymptotische Aufwandsanalyse

Zusammenfassung
Wir haben uns bisher auf die Problemlösung konzentriert, d.h. zu einem gestellten Problem überhaupt ein Programm zu finden. In vielen Anwendungen ist es jedoch wichtig, dass das resultierende Programm beziehungsweise der zugrunde liegende Algorithmus effizient ist. Zur Beurteilung der Effizienz gibt es verschiedene Kriterien, wie zum Beispiel die Ausführungszeit des Programms oder der Bedarf an Speicher. Das Bestreben der Aufwandsanalyse ist es, die Effizienz schon auf algorithmischer Ebene beurteilen zu können, um unnötigen Programmieraufwand oder aufwändige experimentelle Analysen durch Ausführung auf einem Computer zu vermeiden. Die Abschnitte 12.1 und 12.2 führen in die Analyse des Zeit- beziehungsweise Speicherbedarfs von Algorithmen ein.
Heinrich Müller, Frank Weichert

13. Sortieren

Zusammenfassung
Das Sortieren großer Datenbestände ist eine wichtige Aufgabe kommerziell eingesetzter Rechensysteme. Daher hat das Auffinden effizienter Lösungen des Sortierproblems in der Informatik großes Interesse gefunden. In diesem Kapitel wollen wir uns mit der Aufwandsanalyse von Algorithmen zum Sortieren von Zahlen befassen, um die Anwendung der Konzepte des vorigen Kapitels zu demonstrieren. Gegenstand unseres Interesses ist die Analyse des Zeitaufwandes der uns schon bekannten Verfahren des Sortierens durch Minimumsuche (Abschnitt 13.1) und des Sortierens durch Mischen (Abschnitte 13.2 und 13.4). Wir werden dabei von einem wesentlichen Beweisprinzip der Mathematik, der vollständigen Induktion, Gebrauch machen, das auch in der Informatik von hoher Bedeutung ist und im Abschnitt 13.3 detailiert behandelt wird.
Heinrich Müller, Frank Weichert

14. Mengen

Zusammenfassung
Ein weiteres wichtiges Einsatzgebiet von Computern ist das Verwalten von Datenmengen. Dieses Kapitel stellt verschiedene Lösungsansätze für diese Aufgabe vor. Sie unterscheiden sich in der Art der Datenstrukturen, die der Realisierung der drei Operationen „Einfügen eines Elements”, „Suchen nach einem Element” und „Entfernen eines Elements” zugrunde liegen.
Heinrich Müller, Frank Weichert

Vom Programm zum Rechner

Frontmatter

15. Hardware und Programmierung

Zusammenfassung
Eine Möglichkeit zur Beherrschung der Komplexität von Systemen wie der Software und der Hardware eines Computers ist, Stufen unterschiedlichen Details einzuführen und dann für die Komponenten eine Stufe anzugeben, wie sie in der nächst feineren Stufe realisiert werden. Abbildung 15.1 zeigt eine solche Vorgehens weise. Es gibt dort sechs Ebenen. Die unteren drei Ebenen beziehen sich auf die Hardware, die oberen drei Ebenen auf die Programm- oder Software-Seite.
Heinrich Müller, Frank Weichert

16. Rechnerarchitektur und Maschinensprache

Zusammenfassung
Die Architektur eines Rechners beschreibt, analog zur Architektur eines Hauses, den Aufbau aus Komponenten. Abschnitt 16.1 stellt die heute meist gebräuchliche Rechnerarchitektur vor, die unter dem Namen von-Neumann-Architektur bekannt ist. Ihre zentralen Komponenten sind ein Prozessor und Speicher. Der Speicher, auf den in Abschnitt 16.2 eingegangen wird, enthält die Daten, aber auch das Programm. Der Prozessor führt Programme aus, die sich aus Befehlen zusammensetzen, die vom Prozessor der Reihe nach ausgeführt werden. Das Aufbauprinzip von Prozessoren und Befehlen ist Gegenstand von Abschnitt 16.3.
Heinrich Müller, Frank Weichert

17. Schaltungen

Zusammenfassung
Schaltungen verknüpfen Daten. In heutigen Rechnern handelt es sich dabei weitgehend um Information, die durch aneinandergereihte Dateneinheiten repräsentiert wird. Jede Dateneinheit kann hierbei jeweils zwei unterschiedliche Werte annehmen. Abschnitt 17.1 führt in die zweiwertige Informationsdarstellung ein. Es folgt eine Darstellung der zweiwertigen Informationsverarbeitung anhand von Booleschen Funktionen (Abschnitt 17.2) und deren Realisierung durch Boolesche Schaltungen (Abschnitt 17.3). Das Kapitel schließt mit zwei Schaltungsbeispielen unterschiedlicher Art: einem 1-Bit-Addierer (Abschnitt 17.3.1), der Eingangswerte zu einem Ergebniswert verknüpft, und einem RS-Flipflop (Abschnitt 17.3.2), das die Fähigkeit zur Informa-tionsspeicherung hat.
Heinrich Müller, Frank Weichert

18. Formale Sprachen und Compiler

Zusammenfassung
Rechner werden heutzutage meist in einer höheren Programmiersprache, wie zum Beispiel Java, programmiert. Auf der anderen Seite haben Prozessoren nach wie vor eine erheblich einfacher strukturierte Maschinensprache. Damit ein Programm, das in einer höheren Programmiersprache geschrieben ist, auf einem Rechner ausführbar wird, muss es in Maschinenbefehle überführt werden. Diese Überführung wird in der Regel von Compilern geleistet. Ein Beispiel ist der Java-Compiler, in dessen Verwendung im Teil 1.2 Programmierung” eingeführt wurde. In diesem Kapitel soll ein erster Eindruck von der inneren Arbeitsweise von Compilern gegeben werden.
Heinrich Müller, Frank Weichert

Backmatter

Weitere Informationen