Errata zu den Musterlösungen
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Informatik für Mathematiker und Physiker (251-0847-00) WS05/06

Skript:

10.2. 2006: Das vollständige und überarbeitete Skript liegt jetzt vor.
Version zum Ausdrucken (Kleinformat; wie in der Vorlesung ausgegeben, 109 Seiten) [PS] [PDF]
Version zum Ansehen (Grossformat, 217 Seiten) [PS] [PDF]
Wir haben die bekannten Fehler (siehe alte Errata) beseitigt sowie ein Inhaltsverzeichnis und einen Index hinzugefügt. Bitte melden Sie uns ab sofort nur noch Fehler, die Sie in der neuen Version finden.
Errata zur Skriptversion vom 10. Februar 2006

Prüfung:

Hier ist die Hauptprüfung für die Studierenden des WS 05/06 vom Herbst 2006 und die dazugehöhrige Musterlösung.
Sowohl die Wiederholungsprüfung im März 2006 als auch die Hauptprüfung im Herbst findet nach dem Modus für diese Vorlesung statt. Das heisst:
  • zweistündige Klausur
  • keine Hilfsmittel
Damit Sie eine Idee bekommen, wie die Prüfungen aussehen könnten, finden Sie hier die Wiederholungsprüfung für die Studierenden des WS 03/04, die Hauptprüfung für die Studierenden des WS 04/05 sowie die Wiederholungsprüfung für die Studierenden des WS 04/05.

Hier ist die Musterlösung zur Hauptprüfung fürs WS 04/05 und die Musterlösung zur Wiederholungsprüfung fürs WS 04/05. Die Lösung zur Wiederholungsprüfung fürs WS 03/04 finden Sie auf der Webseite des letzten Jahres.

ACHTUNG: Der Stoff aus den WS 03/04 und WS 04/05 ist nicht identisch mit dem Stoff dieses Jahres!

Termine

Vorlesung: Dienstag 13:15-15:00, HG F1
Bernd Gärtner, CAB G32.2, Tel: 01-632 70 26, .
Übung:
Michael Hoffmann, CAB G33.1, Tel: 01-632 73 90, .
Gruppe A,Dienstag 15:15-17:00,CAB G56,Boris Köpf.
Gruppe B,Dienstag 15:15-17:00,HG D5.3,Florian Walpen.
Gruppe C,Dienstag 15:15-17:00,HG E1.2,Dorian Kind.
Gruppe D,Dienstag 15:15-17:00,HG F26.1,Burkhart Wolff.
Gruppe E,Dienstag 15:15-17:00,HG F26.3,Uche Mennel.
Gruppe F,Dienstag 15:15-17:00,HG F26.5,Thomas Bruderer.
Gruppe G,Dienstag 15:15-17:00,LEC C14,Stephan Classen.
Gruppe H,Dienstag 15:15-17:00,LFW E13,Elias Vicari.
Gruppe I,Dienstag 15:15-17:00,ML F40,Diana Senn.
Gruppe J,Dienstag 15:15-17:00,CAB G52,Kaspar Fischer.
Gruppe K,Dienstag 15:15-17:00,ML J37.1,Samuel Riedmann.

Inhalt

Das Ziel der Vorlesung ist eine algorithmisch orientierte Einführung ins Programmieren anhand der Sprache C++. Die Vorlesung gliedert sich in die vier Teile "Grundlagen", "Funktionen", "Klassen" und "Generisches Programmieren". Besonderes Augenmerk liegt auf dem Rechnen mit arithmetischen Typen.

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.

Hinweise zur Übung

Auf jeder Übungsserie gibt es mehrere Aufgaben, die schriftlich zu bearbeiten und zum angegebenen Termin - meist in der Woche darauf - abzugeben sind. Gruppenabgabe wie auch das Einreichen identischer Lösungen sind nicht zulässig.

Alle Aufgaben aus dem Skript werden mit jeweils vier Punkten bewertet.

Programmieraufgaben sind immer bis zum darauffolgenden Montag, 16:00 Uhr, per email abzugeben. Schriftliche Aufgaben sind immer in der Pause der darauffolgenden Vorlesung abzugeben.

Testatbedingungen

Am Ende der Übungen wird ein Testat vergeben. Das Testat erhält, wer
  1. sowohl auf den ersten sechs als auch auf den folgenden - wahrscheinlich ebenfalls sechs - Übungsserien jeweils mindestens 60% der möglichen Punkte erreicht, sowie
  2. mindestens die Hälfte der Schnellübungen sinnvoll bearbeitet.

Prüfung

Die Prüfung besteht aus einer zweistündigen Klausur. Bedingung für die Zulassung zur Prüfung ist das Übungstestat. Es sind keine Hilfsmittel erlaubt.

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. Schnellübungen werden in der Regel eine Woche vorher angekündigt.

Literatur

  • 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.

Material


Datum Themen Skript bis Übungsaufgaben Programme

#1 (25.10.2005) Grundlagen 2.1.3 [PDF] [PS] [power8.C]

#2 (01.11.2005) Syntax und Semantik 2.1.12 Exercises 1, 3, 4 und 6 aus dem Skript -

#3 (08.11.2005) Integrale Zahlentypen 2.2 Exercises 7e-l, 8e-l, 12 und 13 aus dem Skript [fahrenheit.C] [limits.C]

#4 (15.11.2005) Booleans 2.3 Exercises 17b,c,e,f, 18, 20c,d und 23 aus dem Skript -

#5 (22.11.2005) Kontrollstrukturen I 2.4.3 Exercises 26, 27 und 34 aus dem Skript [sum_n.C] [prime.C]

#6 (29.11.2005) Kontrollstrukturen II 2.4 Exercises 25, 29, 31 und 35 aus dem Skript [collatz.C]

#7 (06.12.2005) Gleitkommazahlen 2.5.6 Exercises 36, 38, 45 und 46 aus dem Skript [euler.C] [diff.C]

#8 (13.12.2005) Gleitkommazahlen / Funktionen 3.1.7 (exkl. 3.1.6) Exercises 43, 47, 50 und 52 aus dem Skript [harmonic.C] [callpow.C] [prime2.C]

#9 (20.12.2005) Rekursion 3.2 Exercises 57, 58 a), c), 59, 62 aus dem Skript. Das Soll sind 3 Aufgaben die 4. gibt Bonuspunkte. [fibonacci.C] [ackermann.C] [lindenmayer.C] [snowflake.C] [dragon.C]

#10 (10.01.2006) Klassen 4.1.10 Exercises 64, 65, 66 b), 67 aus dem Skript. [gcd.h] [rational_.h] [userational_.C] [random.h]

#11 (17.01.2006) Call-by-reference und dynamische Datenstrukturen 4.2.1 Exercises 63 (Theorieaufgabe), 69, 70 aus dem Skript. [rational.h] [userational.C]

#12 (24.01.2006) Dynamische Datenstrukturen 4.2.7 Exercises 71-74 aus dem Skript. Das Soll sind 2 Aufgaben, die 3. und 4. geben Bonuspunkte. [exptree.h] [exptree.C] [SLIDES-PDF]

#13 (31.01.2006) Dynamische Datenstrukturen / Template Funktionen 5.1 Keine Sollübungen; Exercises 77-78 geben Bonuspunkte.

#14 (07.02.2006) Template Klassen, std::vector<> Nicht im Skript, kein Prüfungsstoff -

Merkblatt zur Vorlesung [PS] [PDF]

Wichtige Unix Kommandos [PS] [PDF]

Skriptteil vom 1. November 2005 [PS][PDF] (Wurde am 1. November in der Vorlesung ausgegeben.)

Skriptteil vom 15. November 2005 [PS][PDF] (Wurde am 15. November in der Vorlesung ausgegeben.)

Skriptteil vom 29. November 2005 [PS][PDF] (Wurde am 29. November in der Vorlesung ausgegeben.)

Skriptteil vom 13. Dezember 2005 [PS][PDF] (Wurde am 13. Dezember in der Vorlesung ausgegeben.)

Skriptteil vom 20. Dezember 2005 [PS][PDF] (Wurde am 20. Dezember in der Vorlesung ausgegeben.)

Skriptteil vom 10. Januar 2006 [PS][PDF] (Wurde am 10. Januar in der Vorlesung ausgegeben. Neu: Mit Exercise 69.)

Skriptteil vom 24. Januar 2006 [PS][PDF] (Wurde am 24. Januar in der Vorlesung ausgegeben und enthält auch den Teil vom 17.01.2006.)

Skriptteil vom 31. Januar 2006 [PS][PDF] (Wird am 31. Januar in der Vorlesung ausgegeben)

Errata zum Skript [text]

Libwindow

(Neue Version 1.19 vom 20.12.2005; behebt Probleme mit Warnungen auf einigen Plattformen.)

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.19.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.19.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.19 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.19 hineinkopieren.

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.

Emacs

Den file .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: $Date: 2006/10/03 10:07:00 $ by Michael Hoffmann. Valid HTML 4.0! Valid CSS!