Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Informatik (D-MATH,D-PHYS) WS06/07
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Informatik für Mathematiker und Physiker (251-0847-00) WS06/07

Prüfungseinsicht:

Ab 1.10.2007 bei Frau Andrea Salow (CAB G19.1).

Hauptpruefung am 31. August 2007:

WICHTIG!

Selbst wenn Sie in den Zwischenprüfungen eine ausreichende Zwischennote erreicht haben, müssen Sie lt. Rektorat aus formalen Gründen zur Hauptprüfung erscheinen. Falls Sie unentschuldigt fehlen, haben Sie laut Reglement (das nichts von der Zwischennote "weiss") die Prüfung nicht bestanden.

Sie können im Fall einer ausreichenden Zwischennnote jedoch ein leeres Blatt abgeben, woraufhin Ihre Zwischennnote zum Tragen kommt. Ich möchte Ihnen aber ans Herz legen, die Hauptprüfung als Anreiz zu sehen, Ihre erreichte Zwischennote noch zu verbessern.

Die formale Anwesenheitspflicht ist für Sie im Fall einer ausreichenden Zwischennote natürlich lästig, sie ist aber unumgänglich, damit wir dem Reglement genügen und mögliche Rekurse vermeiden können.

Ergebnisse der Vorlesungsevaluation:

Zum Verständnis: Fragen R1, R2, R3, S8, S9, S10 beziehen sich auf den Dozenten Gärtner, D1-D6 sind die entsprechenden Fragen für den Dozenten Hromkovic. Die Fragen D7-D9 waren wie folgt (Antwort 1: überhaupt nicht; Antwort 5: in höchstem Masse) Kommentare der Dozenten folgen!

Zwischenklausuren:

Noten beider Zwischenklausuren und die resultierenden Zwischennoten

Die 2. Zwischenklausur kann ab dem 8.2.07 bei Frau Hefti (CAB G19.1) eingesehen werden. Mittwochs ist das Sekretariat normalerweise nicht besetzt.

Die zweite Zwischenklausur ist wesentlich schlechter ausgefallen als die erste, so dass insgesamt ungefähr 120 von 270 Studierenden keine ausreichende Zwischennote erzielt haben. Warum?

Der Schwierigkeitsgrad der zweiten Zwischenklausur war vergleichbar mit dem der ersten, relativ zu den Übungsaufgaben: wie bei der ersten Zwischenklausur haben wir uns bei der Auswahl der Aufgaben am Schwierigkeitsgrad der relevanten Übungsserien orientiert. Klar ist andererseits, dass die Übungsserien im zweiten Teil der Vorlesung schwieriger waren, weil der Vorlesungsstoff komplexer wurde. Trotzdem gilt: wer die relevanten Übungsserien selbständig bearbeitet (oder die Lösungen zumindest nachvollzogen) hatte, war auch für die zweite Zwischenklausur gut vorbereitet.

Unser Eindruck von der Korrektur ist, dass viele Studierende (möglicherweise unter dem Eindruck einer guten Note in der ersten Zwischenklausur) viel zu wenig in die Vorbereitung auf die zweite Zwischenklausur investiert haben. Alle Aufgaben waren gut durch die Übungen und das Material vorbereitet, und eine seriöse Beschäftigung mit den entsprechenden Unterlagen hätte problemlos zu einer ausreichenden Note geführt.

Aufgabe 1 (Nachbedingungen von drei Funktionen finden, zwei davon rekursiv) war sicher die schwierigste Aufgabe, obwohl der Aufgabentyp selbst von Exercise 56 (Serie 10) bekannt war.

Aufgabe 2 (Programm, Algorithmus, Entscheidbarkeit) war fast völlig vorhersehbar, da in der Vorlesung eine Aufgabe zu diesen Themen - ohne Transferleistung - angekündigt worden war. Die fünfseitige Zusammenfassung dazu (Serie 7) enthät explizit die Lösungen für die Aufgabenteile e), f) und g); Seiten 1-3 des Buchkapitels zu Serie 2 enthalten explizit die Lösungen für die Aufgabenteile a), b) und c).

Aufgabe 3 (Structs und Funktionalität implementieren) war eine Transferaufgabe, die mit Exercises 63, 66, 72 (Serie 10) sehr gut vorbereitet war.

Zusammenfassend müssen wir feststellen, dass die zweite Zwischenklausur von vielen Studierenden offenbar nicht ernst genommen wurde. Die entsprechenden negativen Ergebnisse sind natürlich nicht als "Strafe" zu verstehen, sondern als klarer Hinweis im Hinblick auf die Hauptprüfung im Herbst.

Skript:

Das Skript (auf Englisch) wird semesterbegleitend in der Vorlesung ausgegeben.

AusgabedatumTeilSeitenelektronische Version
=====================================================================================
24. Oktober Introduction 7-18 [pdf]
7. November A first C++ program 19-38 [pdf]
14. November Integers and Booleans 39-68 [pdf]
21. November Control Statements 69-96 [pdf]
28. November Floating point numbers 97-116 [pdf]
12. Dezember Functions 117-154 [pdf]
9. Januar Structs and Type Variants 155-186 [pdf]
23. Januar Classes 187-212 [pdf]
Inhaltsverzeichnis für alle bisherigen Teile: 1-6 [pdf]
Operatorliste und Index für alle bisherigen Teile: 213-225 [pdf]

Material


Datum Themen Skript bis Übungsaufgaben Programme

#1 (24.10.2006) Einführung/Grundlagen 1 (Folien: [PDF]) [PDF] [PS] [power8.C]

#2 (31.10.2006) Grundlagen der Berechenbarkeit [PDF] [PS] [PDF] [PS] -

#3 (07.11.2006) Grundlagen der Syntax und Semantik von C++ 2.1 (Folien: [PDF]) Exercises 1, 3, 4 und 6 aus dem Skript [power8.C]

#4 (14.11.2006) Integrale Zahlentypen, Wahrheitswerte 2.3 (Folien: [PDF] [PDF]) Exercises 7, 8, 12 und 20 aus dem Skript [fahrenheit.C]

#5 (21.11.2006) Kontrollanweisungen 2.4.5 (Folien: [PDF] [PDF]) Exercises 25, 26, 32, und 34 aus dem Skript [prime.C] [collatz.C]

#6 (28.11.2006) Kontrollanweisungen, Fliesskommazahlen 2.4.6. und 2.5 (Folien: [PDF]) Exercises 35cd, 37ac, 42, und 44 aus dem Skript [euler.C] [diff.C] [harmonic.C] [fpsys.C (Sol.Ex.45 - please try to compile)]

#7 (05.12.2006) Berechenbarkeit und Entscheidbarkeit [PDF] [PDF] [PS] -

#8 (12.12.2006) Funktionen 3.1 (Folien: [PDF][PDF]) Exercises 48, 49, 52, und 55 aus dem Skript [math.h] [math.C] [callpow4.C] [Makefile] [prime2.C]

#9 (19.12.2006) Rekursion 3.2 (Folien: [PDF]) Exercises 56, 57, 58, und 62 aus dem Skript [fibonacci.C] [fibonacci2.C] [lindenmayer.C] [snowflake.C] [dragon.C]

#10 (9.1.2007) Structs, Referenztypen, Const-Typen 4.2 (Folien: [PDF]; Real Programmer's don't use Pascal [PDF] ) Exercises 63, 66, 72, und 75 aus dem Skript [userational.C] [rational.h] [rational.C] [userational2.C]

#11 (16.1.2007) Reduktionen 7 Wunder, Kapitel 4 [PDF] [PS] -

#12 (23.1.2007) Klassen 4.2 (Folien: [PDF]; Algorithmus der Woche Exercises 78, 79, 80, und 81 aus dem Skript [random.h] [random.C] [random_pi.C] [loaded_dice.h] [loaded_dice.C] [choosing_numbers.C]

#13 (30.1.2007) Dynamische Datentypen 4.2 (Folien: [PDF] -- [array.h] [array.C] [eratosthenes.C] [eratosthenes2.C] [eratosthenes3.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: 01-632 70 26, .
Juraj Hromkovic, CAB F16, Tel: 01-632 44 08 .
Übung:
Michael Hoffmann, CAB G33.1, Tel: 01-632 73 90, .
Gruppe A,Dienstag 15:15-17:00,CAB G56,Robert Berke.
Gruppe B,Dienstag 15:15-17:00,HG D5.3,Olivier Girard.
Gruppe C,Dienstag 15:15-17:00,HG E1.2,Dorian Kind.
Gruppe D,Dienstag 15:15-17:00,CLA E4,David Graf.
Gruppe E,Dienstag 15:15-17:00,HG F26.3,Michael Gatto.
Gruppe F,Dienstag 15:15-17:00,HG F26.5,Andreas Hasler.
Gruppe G,Dienstag 15:15-17:00,IFW A34,Christoph Lins.
Gruppe H,Dienstag 15:15-17:00,LFW E13,Yves Brise.
Gruppe I,Dienstag 15:15-17:00,CHN E42,Paul Hankes Drielsma.
Gruppe J,Dienstag 15:15-17:00,ML J37.1,Thai Son Hoang (class held in English).
Gruppe K,Dienstag 15:15-17:00,CAB H57,Leo Rüst.

Inhalt

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.

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

Aufgaben sind immer bis zum darauffolgenden Dienstag (Beginn der Übungen) abzugeben. Programmieraufgaben bis zu diesem Termin per email an den Übungsleiter.

Testatbedingungen

Am Ende der Übungen wird ein Testat vergeben. Das Testat erhält, wer insgesamt mindestens 50% der möglichen Punkte aus den gestellten Übungsaufgaben erzielt.

Prüfung

Sowohl die Wiederholungsprüfung im März 2007 als auch die Hauptprüfung im Sommer 2007 finden nach dem Modus für diese Vorlesung statt.

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.

ACHTUNG: Der Stoff aus dem WS 05/06 ist nicht identisch mit dem Stoff dieses Jahres!

Zwischenklausuren

Bereits in diesem Semester werden zwei (freiwillige) schriftliche Zwischenklausuren (jeweils 45 Minuten) geschrieben, in den Übungsstunden und ebenfalls ohne Hilfsmittel. Für diese Klausuren ist keine Anmeldung erforderlich, Sie müssen lediglich Ihre Legi zu den enstprechenden Terminen mitbringen. Falls Sie aus wichtigen Gründen (z.B. Militär) bei einem oder beiden Terminen verhindert sind, melden Sie sich bitte rechtzeitig bei Herrn Gärtner. Bedingung für die Zulassung zu den Zwischenklausuren ist, dass Sie in den Übungsserien, die bis eine Woche vor den jeweiligen Terminen abzugeben sind, mindestens 50 % der erreichbaren Punkte erzielt haben. Falls Sie aus einem früheren Vorlesungsbesuch das Testat bereits besitzen, so gelten für Sie keine Zulassungsvoraussetzungen.

Falls Sie beide Zwischenklausuren bestehen (Note jeweils mindestens 4.0), so ist die Durschnittsnote beider Noten (auf eine Viertelnote aufgerundet) Ihre Zwischennnote und wird Ihnen für die Hauptprüfung angerechnet. Konkret heisst das, dass Sie sich in der Hauptprüfung gegenüber Ihrer erreichten Zwischennnote nur verbessern können.

Beispiel: Sie schliessen die beiden Zwischenklausuren mit den Noten 4.5 und 5.25 ab. Sie erreichen damit eine Zwischennnote von 5.0. Wenn Sie bei der Hauptprüfung eine Note von höchstens 5.0 erzielen (also auch, wenn Sie ein leeres Blatt abgeben), ist 5.0 Ihre Gesamtnote für die Vorlesung. Erzielen Sie bei der Hauptprüfung eine bessere Note als 5.0, so wird diese bessere Note zu Ihrer Gesamtnote.

Termine: Die beiden Zwischenklausuren finden in den ersten 45 Minuten der Übungen statt, und zwar an den folgenden beiden Terminen:

  1. Dienstag, 12. Dezember 2006 und
  2. Dienstag, 23. Januar 2007.
Ein Vor- oder Nachschreiben der Zwischenklausuren ist nicht möglich (ausser bei den oben erwähnten wichtigen Gründen).

Alte Prüfungen

Als Vorbereitung auf die Zwischenklausuren und die Hauptprü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.
  1. Klausur Herbst 2006 und die Lösung dazu.
  2. Klausur Frühling 2006 und die Lösung dazu.
  3. Klausur Herbst 2005 und die Lösung dazu.

Literatur

Libwindow

Neue Version!

(Version 1.20 vom 04.12.2006)

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

Emacs

Neu: behebt Problem mit Leerzeichen im Verzeichnisnamen.
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: 2007/10/02 09:55:00 $ by Michael Hoffmann. Valid HTML 4.0! Valid CSS!