Informatik I

In dieser Vorlesung soll in die Methoden und einfache theoretische Grundlagen der Informatik eingeführt werden.

Aus dem Inhalt:

Repräsentation von Daten
von-Neumann-Architektur und Assembler-Programmierung
Einführung in objekt-orientiertes Programmieren mit Python
Rekursion
Typsysteme
Einfache höhere Datenstrukturen
Abstrakte Datentypen
Such-Algorithmen
Komplexitätsanalyse

Übersicht

Folgende Übersicht zeigt die geplanten Themen und eine ungefähre Zeittafel. Je nach Bedarf können sich Verschiebungen ergeben.

Datum	Thema	Folien, 6up	Folien, 4up	Folien, 2up	Übungs- aufgaben	Literatur
26.10.	Begrüßung, Wissenswertes zum Studium	PDF	PDF	PDF
28.10.	Repräsentation von Daten (Bits, Bytes, Boole's)	PDF	PDF	PDF	PDF	KW 2.5,
2.11.	Repräsentation von Daten (Zeichen & Zahlen)	PDF	PDF	PDF
4.11.	Repräsentation von Daten (fixed-point, floating-point)	PDF	PDF	PDF	PDF
9.11.	Architektur eines Computers, Assembler-Progr, (Speicher, CPUs, Bus, TOY-Maschine)	PDF	PDF	PDF		KW 2.2
11.11.	Abstrakte Maschinenmodelle (Turing-Maschine)	PDF	PDF	PDF	PDF
16.11.	Vom Problem zum Programm (Spezifikation, Algorithmus)	PDF	PDF	PDF		KW 3.2
18.11.	Intro to Python & Vergleich mit C++ (Basics)	PDF	PDF	PDF	PDF	PT 1-3; PR 1.1, 2, 3.5, 4.1, 4.6-4.8;
23.11.	Operatoren, IO, Kontrollstrukturen	PDF	PDF	PDF		PT 7, 4; PR 9, 5;
25.11.	Kontrollstrukturen (Rest)	PDF	PDF	PDF	PDF
30.11.	Fehlerarten, Debugging in Python, Höhere Datenstrukturen in Python	PDF1 PDF2	PDF1 PDF2	PDF1 PDF2		IDLE; Debugger-Intro; PT 5; PR 3.5
2.12.	Funktionen (Call-by-Reference, Scope, Keyword-Value-Param.), Module, Unit-Tests	PDF	PDF	PDF	PDF	PT 4.6, 4.7, 6.1; PR 6.1-6.4, 8.1, 8.2;
7.12.	Klassen (Konstrukor, Overloading, Funktor)	PDF	PDF	PDF		PT 9.1-9.4; PR 7.1, 7.2, 7.6, 7.7
9.12.	Klassen Rest, Introspektion, Doku, doxygen, interaktives Beispiel	PDF	PDF	PDF	PDF	PR 2.5
14.12.	Typsysteme (static/dynamic typing, strong/weak typing)	PDF	PDF	PDF		LO 6.1, 6.6,
16.12.	Rekursion (Beipsiele, Rekursionsbaum, Divide-and-Conquer)	PDF	PDF	PDF	PDF	KW 6.9.5; RS 5.1, 5.2;'
21.12.	Rekursion Rest (Effizienz, Vergleich Iteration/Rekursion, Anwendungen, R.arten, primitiv-rekursive Funktionen, Wachstumshierarchie)	PDF	PDF	PDF	PDF	PF 2
11.1.	Einfache höhere Datenstrukturen (Listen, Multi-Listen, dünn besetzte Matrizen)	PDF	PDF	PDF		RS 3; KW 7.5-7.7;
13.1.	Einfache höhere Datenstrukturen 2 (Stack, Impl. mit Array & Liste, repeated doubling Strategie, UPN, Klammerausdrücke, Funktionsaufruf als Stack-Frame)	PDF	PDF	PDF	PDF	RS 4; KW 7.8
18.1.	Einfache höhere Datenstrukturen 3 (Queue), Abstrakte Datentypen (Intro, algebraische Methode)	PDF1 PDF2	PDF1 PDF2	PDF1 PDF2		RS 4; KW 7.9; PF 4, IS 10
20.1.	Abstrakte Datentypen Rest (Vollståndigkeit, modellbasierte und zusicherungenbasierte Methode, weitere Bsp.e)	PDF	PDF	PDF	PDF
25.1.	Such-Algorithmen (binäre S., exponentielle S., Interpolationss.) Laufzeit im average-case	PDF	PDF	PDF		KW 11; RS 12.1-12.4
27.1.	Komplexitätsanalyse (Kostenmaße, Rechenmodell, Funktionsklassen, Groß-O)	PDF	PDF	PDF	PDF	RS 2.1-2.3; KW 10.4
1.2.	Komplexitätsanalyse 2 (Groß-O-Kalkül, einfache Beziehungen, Kompl.analyse mittels Groß-O)	PDF	PDF	PDF		RS 2.4-2.7; KW 11.2.2, 11.3.1
3.2.	Komplexitätsanalyse 3 (Average-case Analyse, Maxsummen-Problem)	PDF	PDF	PDF	PDF
8.2.	Rückblick / Fragen & Antworten
10.2.	entfällt da Hörsaal belegt

Zusatzfolie (interaktiv in der Vorlesung am 11.11. entwickelt): Selbstkopierendes Programm.
In der Vorlesung am 25.11. wurde interaktiv ein einfaches Programm entwickelt zur Erzeugung von Lissajous-Figuren. Dieser Source-Code ist eine etwas weiter entwickelte Variante davon.

Kürzel der Literaturhinweise:
KW = Wolfgang Küchlin, Andreas Weber: Einführung in die Informatik; Springer, 3. Auflage.
PT = Guido van Rossum: Python Tutorial; Release 2.4.2, 28 September 2005; Link siehe unten.
PR = David M. Beazley: Python Referenz; Link siehe unten.
IDLE = Doku zur "Haus-IDE" in Python, IDLE; Link siehe unten.
Debugger-Intro = Stephen Ferg: Introduction to Debugger Terms and Concepts; 2005-09-02; Link siehe unten.
LO = Kenneth C. Louden: Programming Languages, Principles and Practice; PWS Publishing Company, Boston, 1993.
RS = Robert Sedgewick: Algorithms in C++, Parts 1-4; 3rd Edition, Addison Wesley. Auch die Titel Algorithms in C oder Algorithms in Java tun's genauso gut.
PF = Peter Forbrig: Introduction to Programming by Abstract Data Types; Fachbuchverlag Leipzig.
IS = Ian Sommerville: Software Engineering: 7th edition, Addison-Wesley.

Falls Sie sich diese Bücher anschaffen möchten, sollten Sie vielleicht überlegen, gebrauchte Exemplare zu erwerben -- oft gibt es diese zu einem Bruchteil des Neupreises. Zwei gute Internetadressen sind Abebooks und BookButler.

Hinweis: Die Folien sind kein Skript! Die Folien alleine reichen zum Nacharbeiten der Vorlesung nicht aus!

Unter Linux können Sie die PDF-Files mit acroread, xpdf oder gv lesen.

Vorschau

Die folgende Tabelle enthält einige Foliensätze als Vorschau. Sie sind kapitelweise organisiert, und nicht stundenweise. Ich behalte mir "last-minute"-Änderungen vor. Die definitiven Folien sind in der obigen Tabelle zu finden.

Kapitel	Thema	Folien, 6up	Folien, 4up	Folien, 2up
3	Aufbau und Modelle eines Computers (Hardware, Toy-Computer, Turing)	PDF	PDF	PDF
4	Vom Problem zum Programm (was ist ein Algo?)	PDF	PDF	PDF
5	Python Basics	PDF	PDF	PDF
5.1	Python Debugging	PDF	PDF	PDF
5.2	Python Not-So-Basic	PDF	PDF	PDF
6	Typsysteme	PDF	PDF	PDF
7	Rekursion	PDF	PDF	PDF
8	Datenstrukturen	PDF	PDF	PDF
9	ADTs	PDF	PDF	PDF

Scheinerwerb

Einen Schein erwirbt man durch erfolgreiche Teilnahme an den Übungen. Das heißt, Sie müssen auf jedem (außer einem) Übungszettel mindestens 30% und insgesamt mindestens 50% der maximal erhältlichen Punkte erreichen.

Eine "Schein"-Klausur findet nicht statt.

Klausur

NB: Auch Wiederholer müssen an den Übungen erfolgreich teilgenommen haben, d.h., mindestens 30% der Punkte in jedem Übungsblatt erreichen.

Übungsbetrieb

Anmeldung zu den Übungen

Die Anmeldung zu den Übungen erfolgt online über das eVE-System des Instituts für Informatik (www.in.tu-clausthal.de/~eve/). Nach einer kurzen Anmeldung kann man dort ganz einfach seine Wunschübungsgruppe (W1101-U-1 bis W1101-U-5) auswählen. Die Listen werden allerdings erst nach der ersten Vorlesung freigeschaltet.

Kandidatinnen und Kandidaten mit einem existierenden eVE-Account werden gebeten darauf zu achten, daß Ihre persönlichen Angaben aktuell sind!

Übungsblätter

Die Übungsblätter werden jeweils am Freitag im Lauf des Tages auf der Homepage der VL (also hier) ins Netz gestellt.

Abgabe der Lösungen ist jeweils in der darauffolgenden Woche direkt beim Tutor. Theoretische Aufgaben werden schriftlich abgeliefert, die Abgabe von praktischen Aufgaben klären Sie bitte mit Ihrem Tutor (Mail, CD, live, etc.).

Die Tutoren

Übungsgruppe Name Email Zeit Ort

W1101-U-1 Jessica Brinkmann jessica.brinkmann(at)tu-clausthal.de Mo 13-15 T1

W1101-U-2 Annika Lüdecke annika.luedecke(at)web.de Di 17-19 T4

W1101-U-3 Yike Hu yike.hu(at)tu-clausthal.de Di 17-19 T1

W1101-U-4 Anneli Moeller anneli.moeller(at)tu-clausthal.de Mi 17-19 T1

W1101-U-5 Claus Lohrberg claus.lohrberg(at)tu-clausthal.de Di 15-17 T1

Übungsgruppe	Name	Email	Zeit	Ort
W1101-U-1	Jessica Brinkmann	`jessica.brinkmann(at)tu-clausthal.de`	Mo 13-15	T1
W1101-U-2	Annika Lüdecke	`annika.luedecke(at)web.de`	Di 17-19	T4
W1101-U-3	Yike Hu	`yike.hu(at)tu-clausthal.de`	Di 17-19	T1
W1101-U-4	Anneli Moeller	`anneli.moeller(at)tu-clausthal.de`	Mi 17-19	T1
W1101-U-5	Claus Lohrberg	`claus.lohrberg(at)tu-clausthal.de`	Di 15-17	T1

Die Räume T1 und T4 befinden sich im Hörsaalgebäude auf der Tannenhöhe (gelbes Haus).

Aktive Teilnahme an den Übungen

Durch Vorrechnen von Übungsaufgaben an der Tafel ist es möglich, zusätzliche Punkte zu erhalten. Davon sollten Sie insbesondere dann Gebrauch machen, wenn Sie auf einem Übungszettel nicht die erforderlichen 30% der Punktzahl erreicht haben oder Ihnen noch Punkte für die 50%-Gesamtpunktemarke fehlen.

Auch bei der Scheinvergabe wirkt sich eine aktive Teilnahme an den Übungen in Grenzfällen positiv aus.

Punktestände

Ihren aktuellen Punktestand können Sie hier einsehen.

Hinweise und Downloads zur Bearbeitung der Übungsblätter

Übungsblatt Nr. 3:

Zur Bearbeitung des 3. Übungsblatts benötigen Sie die in Princeton entwickelte Toy-Machine. Klicken Sie dazu einfach auf den unten angegebenen Link und speichern Sie das Programm auf Ihrem Rechner.

Download Toy-Machine (ca 1.6 MByte)

Starten Sie das Programm durch Eingabe von "java -jar toy_1.4.jar" in der Kommandozeile (Bei einigen Systemen reicht auch ein einfacher Doppelklick).

Zum Starten benötigen Sie ausserdem Java ab Version 1.4. Ob Java bei Ihnen bereits installiert ist, können Sie unter www.java.com überprüfen und gegebenenfalls die benötigte Software direkt dort herunterladen.

Übungsblatt Nr. 5:

Python-Template für Aufgabe 4: farn.py

Zur Bearbeitung der Aufgabe benötigen Sie zusätzlich noch die Python Imaging Library.

Übungsblatt Nr. 6:

Textdatei zum Testen des Index-Programms aus Aufgabe 1: kant.txt

Python Library Reference

Mehr zum Thema "perfektes Mischen" und über die Mandelbrotmenge.

Achtung: Fehler in Aufgabe 3: statt |zi|<2 muss es heissen: |zi|>2.

In Aufgabe 2 ist ebenfalls ein Fehler: Im Tip zu Aufgabenteil c) sind Perfect-In- und Perfect-Out-Shuffle vertauscht. Korrekt muss es heißen: Betrachten sie die Binärdarstellung von N (von links nach rechts). Wenn ein Bit den Wert 0 hat, führen Sie ein "Perfect-Out-Shuffle" durch, wenn ein Bit den Wert 1 hat, ein "Perfect-In-Shuffle". Die PDF-Version zum Downloaden wurde entsprechend korrigiert.

Übungsblatt Nr. 7:

In Aufgabe 2b) hat sich ein Fehler eingeschlichen: Statt j/128 muss es i/128 heissen. Die PDF-Version zum Downloaden wurde entsprechend korrigiert.

Bilddatei zum Testen der Bildeffekte aus Aufgabe 2: nikolaus.jpg (Hinweis: Die Ergebnisse mit den Parametern aus Aufgabe 2 können etwas anders aussehen als die Beispielbilder auf dem Übungszettel)

Übungsblatt Nr. 8:

Extrablatt mit ein paar zusätzliche Hinweisen zu Aufgabe 3: Aufgabe3Hinweise.pdf.

Weltkarte zum Testen von Aufgabe 3: welt.jpg

Dieses Bild zeigt die Einteilung der Karte in Längen und Breitengrade: projektion.gif.

Den Aufbau der Datei zum Testen von Aufgabe 3 finden Sie hier: http://de.wikipedia.org/wiki/Wikipedia:GEOnet_Names_Server

Die Datei mit den Geodaten zum Testen von Aufgabe 3 können sie unter folgender Adresse herunterladen: http://earth-info.nga.mil/gns/html/cntyfile/rs.zip

Wegen ihrer Größe (ca 12 MByte) wurde die Datei im zip-Format komprimiert. Vor dem Testen muss die Datei daher entpackt werden. Viele gängige Betriebssysteme enthalten bereits Programme zum dekomprimieren. Falls Sie auf Ihrem Computer noch kein solches Programm haben sollten, suchen Sie sich hier ein für Sie passendes Programm aus oder benutzen Sie die Rechner im Pool.

Das Config-File für Doxygen können Sie hier herunterladen: GeoInfoSystem.cfg. Falls Ihre Datei nicht GeoInfoSystem.py heißt, müssen Sie die Zeile "INPUT = GeoInfoSystem.py" abändern.

Übungsblatt Nr. 9:

Eine Turtlegrafikklasse für die Python-Image-Library (Wird für die Aufgaben 2 und 3 benötigt): Turtle.py.

Übungsblatt Nr. 12:

Benchmark-Programm für die Such-Algorithmen SearchBenchmark.py (Wird für die Aufgaben 2 benötigt).

Lösungsvorschläge

Die folgenden Beispiellösungen zu den Programmieraufgaben wurden von Michael Knop und Philipp Kraus erstellt:

Blatt 5

Aufgabe 1a, Aufgabe 1b, Aufgabe 2, Aufgabe 3, Aufgabe 4

Blatt 6

Aufgabe 1, Aufgabe 2, Aufgabe 3

Blatt 7

Aufgabe 1a, Aufgabe 1b, Aufgabe 2

Blatt 8

Aufgabe 1a, Aufgabe 1b

Blatt 9

Aufgabe 1, Aufgabe 2, Aufgabe 3, Turtle-Klasse

Blatt 10

Aufgabe 1a, Aufgabe 1b, Aufgabe 2, Stack-Klasse

Blatt 11

Aufgabe 1, Aufgabe 2, Stack-Klasse

Blatt 12

Aufgabe 2

Literatur

Goos: Vorlesungen über Informatik, Springer, Band 1 & 2.
Robert Sedgewick: Algorithms in C (oder ... in C++), Parts 1-4, Addison-Wesley (bzw. Pearson).
Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentce Hall.
Küchlin, Weber: Einführung in die Informatik, Springer.
Helmut Herold, Bruno Lurz, Jürgen Wohlrab: Grundlagen der Informatik, Pearson Studium, 2006.

Vorsicht vor deutschen Übersetzungen: sie enthalten oft eine gräßliche Terminologie! Tip: Kaufen Sie nicht gleich alle Bücher, sondern schauen Sie sich erst einmal in der Uni-Bibliothek an.

Online Literatur zu Python

Die Homepage von Python enthält alles, was man braucht: Downloads, Tutorials, Software, Links, etc.
Learning to Program (Quelle). Sehr gut für absolute Programmier-Anfänger. Bitte ignorieren Sie die Einsprengsel zu JavaScript und VBScript!
Non-Programmers Tutorial For Python (Quelle1, Quelle2, Alternative, ). Auch gut für absolute Programmier-Anfänger.
Python Referenz. Recht ausführlich, in deutsch, auch für Anfänger.
Das Python Tutorial (Quelle). Vom Erfinder von Python persönlich, sehr ausführlich, gut geeignet für Beinahe-Anfänger.
Instant Python (Quelle). Für erfahrene Programmierer zum schnellen Einstieg.
Python Quick Reference: als HTML, als PDF on screen und als PDF zum Drucken (Quelle); eignet sich, wie der Name schon sagt, hauptsächlich zum Nachschlagen.
Falls Sie noch andere Tutorials zu Python suchen, finden Sie es bestimmt auf dieser Liste von über 200 Python Tutorials, sortiert nach Topics (Anfänger, Threads-, GUI-Programmierung, etc.)
Die Online-Doku zu IDLE ist recht gut, und enthält auch eine Anleitung zum Debugging in Python.
Für Programmier-Anfänger hier eine kleine Einführung in die Begriffe und Konzepte eines Debuggers (Quelle)

Literatur zu Themen der Vorlesung

W. Kahan, Joseph D. Darcy: How JAVA's Floating-Point Hurts Everyone Everywhere; March 1998, ACM Workshop on Java for High-Performance Computing, Stanford. (Quelle)
B. P. Welford: Note on a Method for Calculating Corrected Sums of Squares and Products Technometrics, Vol. 4, No. 3 (Aug., 1962), pp. 419-420. (Quelle)
David Goldberg: What Every Computer Scientist Should Know About Floating-Point Arithmetic March, 1991, Computing Surveys. (Quelle1, Quelle2)

Interessante Literatur

How To Ask Questions The Smart Way: eine nette Anleitung zum Fragen-Stellen, vom wahrscheinlich berühmtesten Exponenten der Open-Source-Bewegung; ist zwar auf das Fragen in technischen Foren / Newsgroups gemünzt, trifft aber, bei ein wenig Abstraktion, genauso auf das Fragen an der Uni zu.
How To Become A Hacker von Eric Steven Raymond (einer Ikone der Open-Source-Software Bewegung): darin erklärt er unter anderem, welche Programmiersprachen man lernen sollte, und aus welchen Gründen.
Beating the Averages von Paul Graham. Darin beschreibt er unter anderem das "Blub Paradox", das wahrscheinlich so ähnlich für alle Bereiche der Erkenntnis gilt.

Software

Für die praktischen Übungen wird Python benötigt, welches für alle gängigen Betriebssysteme frei erhältlich ist. Bei vielen Linux-Distributionen wird es default-mäßig direkt mit installiert.
Wenn Sie die Programmieraufgaben zu Hause bearbeiten wollen, benötigen Sie neben Python noch die Python Imaging Library. Dabei handelt es sich um eine Bibliothek zur Erstellung und Bearbeitung von Bildern.
Zum Programmieren benötigt man grundsätzlich lediglich einen einfachen Text-Editor, wie ihn alle gängigen Betriebssysteme bereits integriert haben. Etwas komfortabler geht es mit einer integrierten Entwicklungsumgebung (kurz IDE). Python bringt mit IDLE eine solche IDE bereits mit.
Noch ein wenig komfortabler im Betrieb ist die Python-IDE SPE
Eine extrem mächtige IDE ist Eclipse; für diese gibt es ein Plugin PyDev, damit kann man dann auch Python-Code in dieser IDE editieren.
Noch ein (kommerzielles) IDE ist Wingware, von dem es auch eine kostenlose personal Edition gibt.
Zur Dokumentation Ihrer Programme empfiehlt sich das automatische Dokumentations-System Doxygen.

Change Monitoring:

If you enter your email adress in one of the boxes above and then press one of the "Monitor" buttons, then either ChangeDetection or ChangeDetect will send you an email whenever I make changes to this page.

Gabriel Zachmann
Last modified: Fri Apr 15 09:22:01 MDT 2011