Informatik für Mathematiker und Physiker (251-0847-00) HS07

Ankündigung

Der provisorische Termin für die Repetitionsprüfung im Winter ist der 26.1.2009.

Skript

Das Skript (auf Englisch) wird nur hier auf der Webseite veröffentlicht. Wer es ausdrucken möchte, kann das an einer der ETH Druckstationen tun. Dazu eignet sich die Version mit zwei Textseiten auf einer A4 Seite (2/1 Seiten), denn es gibt eine Seitenzahlbeschränkung für die öffentlichen Druckstationen. Jeweils zu Beginn der Volesung werden lediglich die Übungsaufgaben, die auch ein Teil des Skriptes sind, als Drucksache an die Studenten verteilt.

Die Lösungen zu allen Aufgaben im Skript werden veröffentlicht; nicht nur zu denen Aufgaben, die Sie während des Semesters lösen müssen. Dies soll ihnen als Möglichkeit dienen, zum Beispiel zur Prüfungsvorbereitung, noch weitere Aufgaben anzuschauen. Zudem können Sie unter diesem Link die Quelldateien der Programme in den Lösungen herunterladen und alles auf ihrem Rechner ausprobieren; ohne mühsames Abtippen. Unter Material tragen wir nur allfällige weitere Dokumente ein, und die Programme, die Sie während der Vorlesung sehen.

Ausgabedatum	Teil	Seiten	1/1 Seiten	2/1 Seiten	Lösungen 1/1	Lösungen 2/1
============================================================================================
2. Oktober	Introduction	5-16	[PDF][PS]	[PDF][PS]	keine	keine
2. Oktober	First C++ program	17-36	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
5. Oktober	Integers	37-58	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
5. Oktober	Booleans	59-70	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
12. Oktober	Control Statements	71-98	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
19. Oktober	Floating Point Numbers	99-122	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
26. Oktober	Arrays and Pointers	123-162	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
16. November	First Function	163-196	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
27. November	Recursion	197-224	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
29. November	Compound Types	225-256	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
7. Dezember	Classes	257-280	[PDF][PS]	[PDF][PS]	[PDF][PS]	[PDF][PS]
============================================================================================
Inhaltsverzeichnis:		1-4	[PDF][PS]	[PDF][PS]
Appendix A (Operatoren):		281-282	[PDF][PS]	[PDF][PS]
Index:		284-296	[PDF][PS]	[PDF][PS]

Material

Datum	Themen	Folien / Handout	Übungsaufgaben	Lösung	Programme
#1 (25.09.2007)	Algorithmus, Programm, Registermaschine	Kapitel 2 [PDF] (Sieben Wunder der Informatik)	Serie 1 [PDF][PS]	Lösung 1 [PDF][PS]	[HelloWorld.C]
#2 (02.10.2007)	C++: Identifiers, Ausdrücke, Variablen, Literale, Operatoren, Erstes Programm	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 2 [PDF][PS]	-	[power8.C]
#3 (09.10.2007)	Integers, Booleans, Auswertungsreihenfolge	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 3 [PDF][PS]	-	[fahrenheit.C] [limits.C]
#4 (16.10.2007)	Kontrollanweisungen	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 4 [PDF][PS]	Lösung 4 [PDF][PS]	[collatz.C] [prime.C] [scope.C] [sum_n.C]
#5 (23.10.2007)	Fliesskommazahlen	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 5 [PDF][PS]	-	[diff.C] [draw_circle.C] [euler.C] [harmonic.C]
#6 (30.10.2007)	Felder und Zeiger (I)	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 6 [PDF][PS]	-	[read_array.C] [eratosthenes.C] [eratosthenes2.C]
#7 (06.11.2007)	Unendlichkeit, Berechenbarkeit	Kapitel 3 [PDF], Kapitel 4 [PDF] (Sieben Wunder der Informatik)	Serie 7 [PDF][PS]	Lösung 7 [PDF][PS] Anhang Kapitel 3 (7 Wunder...) [PDF]	-
#8 (13.11.2007)	Felder und Zeiger (II)	Slides 1/1 [PDF][PS], Slides 6/1 [PDF][PS]	Serie 8 [PDF][PS]	Lösung 8 [PDF][PS]	[threedim_array_init.C] [string_matching.C] [string_matching2.C] [shortest_path.C] Input data
#9 (20.11.2007)	Funktionen	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 9 [PDF][PS]	-	[sort_array2_template.C] Input data
#10 (27.11.2007)	Rekursion (I)	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 10 [PDF][PS]	Lösung 10 [PDF][PS]	[fibonacci.C] [fibonacci2.C] [ackermann.C] [sort_array3.C]
#11 (04.12.2007)	Rekursion (II) Structs Referenztypen	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS]	Serie 11 [PDF][PS]	-	[lindenmayer.C] [dragon.C] [snowflake.C] [rational.C] [userational2.C] [tribool_truthtables.C]
#12 (11.12.2007)	Referenzen (const), Klassen (I), Zufallszahlen	Slides 1/1 [PDF], Real Programmers Don't Use Pascal	Serie 12 [PDF][PS]	-	[clock.C]
#13 (18.12.2007)	Klassen (II)	Slides 1/1 [PDF][PS], Slides 4/1 [PDF][PS], Algorithmus der Woche	Serie 13 [PDF][PS]	Lösung 13 [PDF][PS]	[array.C], [eratosthenes4.C]
Merkblatt zur Vorlesung [PDF] [PS]
Wichtige Unix Kommandos [PDF] [PS]

Termine Vorlesung: Dienstag 13:15-15:00, HG F1 Bernd Gärtner, CAB G32.2, Tel: 044 632 70 26, . Juraj Hromkovic, CAB F16, Tel: 044 632 44 08 . Übung: Yves Brise, CAB G36.2, Tel: 044 44 632 77 96, . Gruppe A, Dienstag 15:15-17:00, CAB G56, Beat Gfeller. Gruppe B, Dienstag 15:15-17:00, HG D5.3, Stefan Wanger. Gruppe C, Dienstag 15:15-17:00, HG E1.2, Jürgen Doser. Gruppe D, Dienstag 15:15-17:00, CLA E4, Stephan Classen. Gruppe E, Dienstag 15:15-17:00, HG F26.3, Matus Harvan. Gruppe F, Dienstag 15:15-17:00, HG F26.5, Anna Zych (class held in English). Gruppe G, Dienstag 15:15-17:00, IFW A34, Christoph Lins. Gruppe H, Dienstag 15:15-17:00, LFW E13, Andreas Streich. Gruppe I, Dienstag 15:15-17:00, CHN E42, Mitra Purandare (class held in English). Gruppe J, Dienstag 15:15-17:00, ML J37.1, Matthias Indermühle. Gruppe K, Dienstag 15:15-17:00, CAB H57, Holger Flier.

Inhalt der Vorlesung Der Hauptteil der Vorlesung ist eine algorithmisch orientierte Einführung ins Programmieren anhand der Sprache C++. Dieser Teil gliedert sich in die drei Bereiche "Grundlagen", "Funktionen" und "Klassen". Besonderes Augenmerk liegt auf dem Rechnen mit arithmetischen Typen. Desweiteren geben wir einen Einblick in die Geschichte der Informatik und einige ihrer wichtigen theoretischen Grundlagen.

Diskussionsforum Ein online Forum steht für sie bereit, in dem alle Fragen rund um die Vorlesung diskutiert werden können. Im Forum können Sie (anonym, wenn Sie wollen) Fragen stellen, mit anderen kommunizieren, Vorlesungsinhalte kommentieren, Fehler/Unklarheiten im Skript melden, aber auch (das ist sehr erwünscht) Fragen anderer beantworten. Sie können jederzeit ein neues Thema Ihrer Wahl eröffnen (mit einem möglichst aussagekräftigen Titel), oder Beiträge zu bestehenden Themen einstellen. Fragen und Diskussionen zu Übungsaufgaben sind ausdrücklich erlaubt, nicht erlaubt ist lediglich das Veröffentlichen ausgearbeiteter Lösungen (z.B. komplette Programme). Wir ermuntern sie ausdrücklich dazu das Forum zu besuchen und zu gestalten. Das Forum wird von den Vorlesungsbetreuern moderiert; das heisst, dass sie dort auch Antworten von "offizieller" Seite erhalten können.

Arbeitsumgebung Für die Programmieraufgaben stehen die Rechner im HG D13 (13 Linux-PCs), HG E26.1 (32 Linux-PCs) sowie HG E27 (21 Linux-PCs) zur Verfügung. Wo vorhanden, können natürlich auch eigene Rechner benutzt werden. Wer mit dem Gedanken spielt, sich ein eigenes Notebook anzuschaffen, der sollte einen Blick auf die Neptun Angebote werfen. Wir arbeiten mit einer Unix Umgebung. Unter MS Windows kann man eine solche Umgebung sehr einfach mittels cygwin emulieren. Weiter unten findet man eine Kurzanleitung zur Installation von cygwin. Bei Zugansproblemen aller Art, die Sie nicht mir ihrem Übungsleiter zusammen lösen kösen, kontaktieren Sie bitte eine der Personen vom Nethz support.

Hinweise zur Übung Auf jeder Übungsserie gibt es mehrere Aufgaben, die schriftlich zu bearbeiten und zum angegebenen Termin - meist in der Woche darauf - zu Beginn der Übungsstunde abzugeben sind. Programmieraufgaben senden sie bis zu diesem Termin per E-Mail an den Übungsleiter. Gruppenabgaben wie auch das Einreichen identischer Lösungen sind nicht zulässig. Alle Aufgaben aus dem Skript werden mit jeweils vier Punkten bewertet. Bei jeder Übungsserie haben Sie die Möglichkeit, zwei reguläre Aufgaben Ihrer Wahl durch eine sogenannte "Herausforderung" zu ersetzen, die mit 8 Punkten bewertet wird. Herausforderungen sind anspruchsvollere Übungsaufgaben fuer Studierende, die den entsprechenden Stoff bereits kennen oder als zu leicht empfinden. Es wird sowohl theoretische als auch praktische Herausforderungen geben.

Testatbedingungen Die Serie 11 ist die letzte Serie, welche für die 50%-Regelung des Testates zählt. Serie 12 wird eine Bonusserie sein, mit der man noch einmal zusätzliche Punkte holen kann, falls man knapp steht. In Woche 13 werden keine weiteren Übungen ausgeteilt. Das Testat erhält, wer insgesamt mindestens 50% (86) der möglichen Punkte (172) aus den gestellten Übungsaufgaben erzielt, sowie mindestens zwei der Schnellübungen sinnvoll bearbeitet hat.

Prüfung Die Prüfung besteht aus einer zweistündigen Klausur. Es sind keine Hilfsmittel erlaubt. Bedingung für die Zulassung zur Prüfung ist das Übungstestat. Der provisorische Termin für die Prüfung im Winter ist der 26. Januar 2009. Bitte beachten Sie, dass dies lediglich eine Vorankündigung ist, bindend ist nur das offizielle Aufgebot der ETH. Der Prüfungsstoff umfasst alles was in der Vorlesung gezeigt wurde. Insbesondere also auch das Kapitel Felder und Zeiger. Beachten Sie, dass die Vorlesungsunterlagen zum Teil ausführlicher sind als die Präsentationen. Die weiterführenden Teile der Unterlagen sind nicht direkt prüfungsrelevant, aber natürlich manchmal für ein genaueres Verständnis hilfreich.

Schnellübungen Auf einigen Übungsserien wird die erste Aufgabe aus einer Schnellübung bestehen. Diese Aufgaben sind in den ersten x (typischerweise x = 20) Minuten der Übungsstunde zu bearbeiten und werden dann vom Übungsleiter eingesammelt. Es versteht sich, dass hierfür die Anwesenheit in der Übungsstunde erforderlich ist, eine nachträgliche Abgabe ist nicht möglich.

Alte Prüfungen Als Vorbereitung auf die Prüfung stellen wir Ihnen hier eine Liste alter Prüfungen und Musterlösungen zu dieser Vorlesung zur Verfügung. Angaben in den Lösungen ohne Gewähr. Klausur Herbst 2008 und die Lösung dazu. Klausur Frühling 2008 und die Lösung dazu. Klausur Herbst 2007 und die Lösung dazu. Klausur Herbst 2006 und die Lösung dazu. Klausur Frühling 2006 und die Lösung dazu. Klausur Herbst 2005 und die Lösung dazu.

Literatur Juraj Hromkovic: Sieben Wunder der Informatik, Teubner, 2006 Andrew Koenig and Barbara E. Moo: Accelerated C++, Addison-Wesley, 2000. Stanley B. Lippman: C++ Primer, 3. Auflage, Addison-Wesley, 1998. Bjarne Stroustrup: The C++ Programming Language, 3. Auflage, Addison-Wesley, 1997. Doina Logofatu: Algorithmen und Problemlösungen mit C++, Vieweg, 2006.

Libwindow

(Version 1.21 vom 22.10.2007)

Für die graphische Ausgabe verwenden wir die Bibliotheken libwindow und libturtle. Um mit diesen Bibliotheken arbeiten zu können, müssen Sie sie zunächst installieren. Hierzu speichern Sie die Datei libwindow-1.21.tgz in Ihr Heimatverzeichnis. Öffnen Sie ein shell-terminal, wechseln Sie dort in Ihr Heimatverzeichnis, und entpacken Sie die Datei mittels des Kommandos

tar xvzf libwindow-1.21.tgz

(Sollte Ihr browser die Datei schon eigenmächtig beim download entpackt haben, schlägt dieses Kommando vielleicht fehl. Probieren Sie in diesem Fall tar xvf ..., d.h. obiges Kommando ohne die Option "z".)

Die Bibliothek wird in ein Unterverzeichnis namens libwindow-1.21 entpackt. Wechseln Sie in dieses Verzeichnis. Das weitere Vorgehen ist in einer Datei namens README beschrieben, die sich dort befindet. Übersetzen und starten Sie nach der Installation die Demo-Programme, um sicherzustellen, dass alles korrekt funktioniert.

Achtung!

Wann immer Sie die graphische Ausgabe in einem Ihrer Programme benutzen wollen, müssen Sie in das Verzeichnis, in dem sich Ihr Programm befindet, die Datei Makefile aus dem Verzeichnis libwindow-1.21 hineinkopieren.

Achtung!

Wenn Sie unter Cygwin arbeiten und sich Ihr Heimatverzeichnis in einem Ordner befindet, dessen Name Leerzeichen enthält (wie z.B. "Documents and Settings"), so wird das vorgegebene Makefile nicht funktionieren, da Cygwin nicht mit Leerzeichen in Dateinamen umgehen kann. Setzen Sie in diesem Fall bitte explizit die Variable INFO1HOME im Makefile auf das (neue) Verzeichnis, in dem die Bibliothek installiert werden soll, z.B. so:

# directory where you install this library
INFO1HOME = /cygdrive/c/Documents\ and\ Settings/yourhome/libwindow

Cygwin

Cygwin ist eine Unix-artige Umgebung für MS Windows. Eine kurze Installationsanleitung findet man hier.

Eine cygwin shell öffnet man durch Doppelclick auf das schwarz-grüne cygwin icon. In dieser shell kann man mittels des Kommandos startx einen X-server und ein zugehöriges Terminal starten. So ein Terminal ist unsere bevorzugte Arbeitsumgebung, von wo aus man z.B. den emacs, den compiler g++ und die erstellten ausführbaren Programme aufruft. Alternativ können sie die entsprechende Umgebung auch direkt mit der Datei C:\cygwin\usr\X11R6\bin\startxwin.bat starten.

Das Tastaturlayout von cygwin ist standardmässig auf die amerikanische Tastatur abgestimmt. Wenn sie das auf das Schweizer Layout ändern möchten, dann öffnen sie die Datei C:\cygwin\usr\X11R6\bin\startxwin.bat in einem Texteditor.
Sie müssen nun die Zeile

%RUN% XWin -multiwindow -clipboard -silent-dup-error

durch die Zeile

%RUN% XWin -xkblayout ch -multiwindow -clipboard -silent-dup-error

ersetzen.

Emacs

Neu: behebt Problem mit Leerzeichen im Verzeichnisnamen.
Die Datei .emacs solltet Ihr in Euer Heimatverzeichnis kopieren. (Achtung: Als text-file speichern, nicht etwa im HTML-Format.)

Unter Cygwin ist das Heimatverzeichnis im Verzeichnisbaum unterhalb des bei der Installation angegebenen cygwin Wurzelverzeichnisses zu finden, z.B. als c:\cygwin\home\myname.

Wem die Schriftgrösse zu klein ist: Shift-Taste drücken und mit der linken Maustaste in das Emacs Fenster klicken. Es erscheint ein Menu zu Schriftart und -grösse.

OS-X

Mac OS 10 Benutzer sollten die Developer CD installieren, insbesondere auch das Paket X11. Eine grosse Auswahl von open source software packages wie z.B. emacs kann sehr bequem via fink installiert werden.

Dorian Kind hat eine ausführliche Anleitung dazu geschrieben.

---

Last modified: , by Yves Brise.