In dieser Vorlesung soll in die Methoden und einfache theoretische Grundlagen der Informatik eingeführt werden.
Aus dem Inhalt:
Datum | Thema | Folien, 6up | Folien, 4up | Folien, 2up | Übungs- aufgaben |
Literatur |
---|---|---|---|---|---|---|
26.10. | Begrüßung, Wissenswertes zum Studium | |||||
28.10. | Repräsentation von Daten (Bits, Bytes, Boole's) | KW 2.5, | ||||
2.11. | Repräsentation von Daten (Zeichen & Zahlen) | |||||
4.11. | Repräsentation von Daten (fixed-point, floating-point) | |||||
9.11. | Architektur eines Computers, Assembler-Progr, (Speicher, CPUs, Bus, TOY-Maschine) | KW 2.2 | ||||
11.11. | Abstrakte Maschinenmodelle (Turing-Maschine) | |||||
16.11. | Vom Problem zum Programm (Spezifikation, Algorithmus) | KW 3.2 | ||||
18.11. | Intro to Python & Vergleich mit C++ (Basics) | PT 1-3; PR 1.1, 2, 3.5, 4.1, 4.6-4.8; | ||||
23.11. | Operatoren, IO, Kontrollstrukturen | PT 7, 4; PR 9, 5; | ||||
25.11. | Kontrollstrukturen (Rest) | |||||
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 | PT 4.6, 4.7, 6.1; PR 6.1-6.4, 8.1, 8.2; | ||||
7.12. | Klassen (Konstrukor, Overloading, Funktor) | PT 9.1-9.4; PR 7.1, 7.2, 7.6, 7.7 | ||||
9.12. | Klassen Rest, Introspektion, Doku, doxygen, interaktives Beispiel | PR 2.5 | ||||
14.12. | Typsysteme (static/dynamic typing, strong/weak typing) | LO 6.1, 6.6, | ||||
16.12. | Rekursion (Beipsiele, Rekursionsbaum, Divide-and-Conquer) | KW 6.9.5; RS 5.1, 5.2;' | ||||
21.12. | Rekursion Rest (Effizienz, Vergleich Iteration/Rekursion, Anwendungen, R.arten, primitiv-rekursive Funktionen, Wachstumshierarchie) | PF 2 | ||||
11.1. | Einfache höhere Datenstrukturen (Listen, Multi-Listen, dünn besetzte Matrizen) | 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) | 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) | |||||
25.1. | Such-Algorithmen (binäre S., exponentielle S., Interpolationss.) Laufzeit im average-case | KW 11; RS 12.1-12.4 | ||||
27.1. | Komplexitätsanalyse (Kostenmaße, Rechenmodell, Funktionsklassen, Groß-O) | RS 2.1-2.3; KW 10.4 | ||||
1.2. | Komplexitätsanalyse 2 (Groß-O-Kalkül, einfache Beziehungen, Kompl.analyse mittels Groß-O) | RS 2.4-2.7; KW 11.2.2, 11.3.1 | ||||
3.2. | Komplexitätsanalyse 3 (Average-case Analyse, Maxsummen-Problem) | |||||
8.2. | Rückblick / Fragen & Antworten | |||||
10.2. | entfällt da Hörsaal belegt |
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.
Kapitel | Thema | Folien, 6up | Folien, 4up | Folien, 2up | |
---|---|---|---|---|---|
3 | Aufbau und Modelle eines Computers (Hardware, Toy-Computer, Turing) | ||||
4 | Vom Problem zum Programm (was ist ein Algo?) | ||||
5 | Python Basics | ||||
5.1 | Python Debugging | ||||
5.2 | Python Not-So-Basic | ||||
6 | Typsysteme | ||||
7 | Rekursion | ||||
8 | Datenstrukturen | ||||
9 | ADTs |
Eine "Schein"-Klausur findet nicht statt.
Kandidatinnen und Kandidaten mit einem existierenden eVE-Account werden gebeten darauf zu achten, daß Ihre persönlichen Angaben aktuell sind!
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.).
Übungsgruppe | Name | 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).
Auch bei der Scheinvergabe wirkt sich eine aktive Teilnahme an den Übungen in Grenzfällen positiv aus.
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.
Zur Bearbeitung der Aufgabe benötigen Sie zusätzlich noch die Python Imaging Library.
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.
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)
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.
Online Literatur zu Python
Literatur zu Themen der Vorlesung
Interessante Literatur
Software
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.
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.