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) HS08
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

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

Ankündigung

Die Prüfung vom 12.2.2010 kann nun eingesehen werden. Melden Sie sich dazu bei Yves Brise an, um einen Termin auszumachen. Ohne Terminvereinbarung wird die Einsicht nicht gewährt! Kommen sie zur vereinbarten Zeit in das Büro von Frau Salow, CAB G19.1. Bitte denken sie auch daran, dass Sie Ihre Legi mitbringen. Die Musterlösung zur Prüfung können Sie hier herunter laden.
Die Challenge 107 bestand darin, ein Programm zu schreiben, mit welchem ein möglichst ansprechendes Lindenmayer Bild erzeugt wird. Wir haben dazu einige schöne Abgaben bekommen und möchten diese der Allgemeinheit nicht vorenthalten. Hier finden Sie die Resultate dieser Arbeit.

Skript

Das Skript (auf Englisch) kann hier ([PDF] [PS]) herunter geladen werden. 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 ([PDF] [PS]). Dennoch wird die zulässige Maximalseitenzahl für den kostenlosen Druck überschritten. Sie können das Skript also Tranchenweise oder bei einer kostenpflichtigen Stelle ausdrucken.

Wenn sie an einer gedruckten Version der Vorlesungsunterlagen (Teil Gärtner) interessiert sind, dann melden Sie sich bitte bei Yves Brise. Es handelt sich dabei um einen Ausdruck der elektronischen Version des Skriptes (nicht der Folien!), die sie auch weiter oben erhalten können. Die Unterlagen werden zum Selbstkostenpreis von 20.- CHF abgegeben.

Die wöchentlichen Übungen sind (von wenigen Ausnahmen abgesehen) im Skript integriert und werden nicht separat verteilt. Die Lösungen zu allen Aufgaben im Skript werden schrittweise veröffentlicht; nicht nur zu den 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.

Material
Datum Themen Folien / Handout Übungsaufgaben Lösung Programme
#1 (23.09.2008) Algorithmus, Programm, Registermaschine Kapitel 2 [PDF], (Sieben Wunder der Informatik), Zusammenfassung Registermaschine [PDF] Serie 1 [PDF][PS] Lösung 1 [PDF][PS] [HelloWorld.C]
#2 (30.09.2008) Unendlichkeit,
Berechenbarkeit		 Kapitel 3 [PDF], Kapitel 4 [PDF] (Sieben Wunder der Informatik) Serie 2 [PDF][PS] Lösung 2 [PDF][PS], Aufgabe 3.10 aus "7 Wunder" [PDF]
#3 (7.10.2008) C++: Identifiers, Ausdrücke,
Variablen, Literale,
Operatoren, erstes Programm		 Slides [PDF] Aufgaben: 1, 2, 7, 8 (je 4 Pkt.),
Challenge (optional): 9, 10 (je 8 Pkt.),
(Abschnitt 2.1.18 im Skript),
Abgabetermin: 14.10.2008		 Lösungen zu Abschnitt 2.1 [PDF] [power8.C], [power8_exact.C], [integer.h], [garbled.C]
#4 (14.10.2008) Integers, Booleans, Auswertungsreihenfolge Slides [PDF] Aufgaben: 11, 19, 26, 30 (je 4 Pkt.),
Challenge (opt.): 21, 22, 32 (je 8 Pkt.),
Abgabetermin: 21.10.2008		 Lösungen zu Abschnitt 2.2 [PDF],
Lösungen zu Abschnitt 2.3 [PDF]		 [fahrenheit.C] [limits.C]
#5 (21.10.2008) Kontrollanweisungen Slides [PDF] Aufgaben: 36, 37, 44, 45 (je 4 Pkt.),
Challenge (opt.): 48, 49 (je 8 Pkt.),
Abgabetermin: 28.10.2008		 Lösungen zu Abschnitt 2.4 [PDF] [collatz.C] [prime.C] [scope.C] [sum_n.C]
#6 (28.10.2008) Fliesskommazahlen Slides [PDF] Aufgaben: 52 a c d, 57, 59, 60 (je 4 Pkt.),
Challenge (opt.): 63, 64 (je 8 Pkt.),
Abgabetermin: 4.11.2008		 Lösungen zu Abschnitt 2.5 [PDF] [euler.C] [diff.C] [harmonic.C]
#7 (4.11.2008) Felder und Zeiger (I) Slides [PDF] Aufgaben: 65 b, 66, 67, 70 (je 4 Pkt.),
Challenge (opt.): 75, 77 (je 8 Pkt.),
Abgabetermin: 11.11.2008		 Lösungen zu Abschnitt 2.6 [PDF] [read_array.C] [eratosthenes.C] [eratosthenes2.C]
#8 (11.11.2008) Felder und Zeiger (II) Slides [PDF] 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 (18.11.2008) Funktionen Slides [PDF] Aufgaben: 81, 87 (je 4 Pkt.), 89 (8 Pkt.),
Challenge (opt.): 93, 94 (je 8 Pkt.),
Abgabetermin: 25.11.2008		 Lösungen zu Abschnitt 3.1 [PDF] [callpow.C] [swap_template.C] [sort_array_template.C]
Input data
#10 (25.11.2008) Rekursion (I) Slides [PDF] Aufgaben: 95, 99, 102, 105 (je 4 Pkt.),
Challenge (opt.): 106 (8 Pkt.),
Abgabetermin: 2.12.2008		 Lösungen zu Abschnitt 3.2 [PDF] [fibonacci.C] [fibonacci2.C] [ackermann.C] [sort_array3.C]
#11 (2.12.2008) Rekursion (II)
Structs
Referenztypen
Operator-Überladung		 Slides [PDF] Aufgaben: 104, 108, 111, 118 (je 4 Pkt.),
Challenge (opt.): 107, 114 (je 8 Pkt.),
Abgabetermin: 9.12.2008		 Lösungen zu Abschnitt 4.1 [PDF]
Lösungen zu Abschnitt 4.2 [PDF]		 [bush.C] [dragon.C] [lindenmayer.C] [rational.C] [snowflake.C] [userational2.C]
#12 (9.12.2008) Referenzen (const),
Klassen (I),
Zufallszahlen		 Slides [PDF] Aufgaben: 120, 124, 126, 127 (je 4 Pkt.),
Challenge (opt.): 121, 128 (je 8 Pkt.),
Abgabetermin: 16.12.2008		 Lösungen zu Abschnitt 4.3 [PDF] [BibliothekBauen.pdf] [Makefile] [clock.C] [random.h] [random.C] [random_pi.C] [loaded_dice.h] [loaded_dice.C] [choosing_numbers.C]
#13 (16.12.2008) Klassen (II) Slides [PDF] Serie 13 [PDF] Lösung 13 [PDF][PS]
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: Dienstag 15:15-17:00
Yves Brise, CAB G36.2, Tel: 044 44 632 77 96, .
Gruppe A,Dienstag 15:15-17:00,CAB G56,Matthias Geel.
Gruppe B,Dienstag 15:15-17:00,CAB G57,Anna Zych (english).
Gruppe C,Dienstag 15:15-17:00,CHN D48,Jo Helmuth.
Gruppe D,Dienstag 15:15-17:00,CHN E42,Janick Cardinale.
Gruppe E,Dienstag 15:15-17:00,CHN G22,Martin Jaggi.
Gruppe F,Dienstag 15:15-17:00,CHN G46,Andres Bühlmann.
Gruppe G,Dienstag 15:15-17:00,CLA E4,Lukas Beyeler.
Gruppe H,Dienstag 15:15-17:00,HG D5.3,Anna Hanulova.
Gruppe I,Dienstag 15:15-17:00,HG E1.2,Davide Bilo (italiano).
Gruppe J,Dienstag 15:15-17:00,HG F26.3,Rajesh Ramaswamy (english).
Gruppe K,Dienstag 15:15-17:00,HG F26.5,Florian Negele.
Gruppe L,Dienstag 15:15-17:00,IFW A34,Christoph Lins.
Gruppe M,Dienstag 15:15-17:00,LFV E41,Marcel Schöngens.
Gruppe N,Dienstag 15:15-17:00,LFW E13,Ulrike Glavitsch.
Gruppe O,Dienstag 15:15-17:00,ML J37.1,Roozbeh Derakhshan (english).

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. Die Anmeldung erfolgt mit Ihrem ETH login.

Im Forum können Sie 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 etliche Rechner in verschiedenen Räumen zur Verfügung. Eine komplette Liste gibt es hier. Die meisten der PCs sind dualboot Windows/Linux. Informationen dazu gibt es hier. Wenn 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.

Testatbedingungen

Bitte lesen Sie sich die folgenden Absätze genau durch. Es handelt sich dabei um wichtige Informationen bezüglich der Leistungskontrollen.

Was ist das Testat, und wie bekomme ich es?

Das Testat bescheinigt Ihnen eine erfolgreiche Teilnahme am Übungsbetrieb. Jede der wöchentlich ausgegebenen Übungsserien enthält 4 reguläre Übungsaufgaben, für deren korrekte Lösung jeweils 4 Punkte vergeben werden. Zusätzlich enthalten die meisten Serien "Challenge"-Aufgaben, aus denen jeweils 8 Punkte erzielt werden können. Insgesamt wird es 13 Übungsserien geben.

Um das Testat zu erhalten, müssen Sie 96 Punkte aus allen ausgegebenen Übungsserien erreichen; das sind 50 Prozent der regulären Punkte aus 12 Übungsserien. Es spielt dabei keine Rolle, ob Sie die Punkte aus regulären Aufgaben oder aus "Challenge"-Aufgaben erzielen.

Der Sinn dieser Anforderung besteht darin, Sie in Ihrem eigenen Interesse zu regelmässiger Beschäftigung mit dem Vorlesungsstoff zu motivieren. Die Erfahrung zeigt, dass viele Studierend beim Fehlen solcher Anforderungen die Vorlesung schleifen lassen und bei der späteren Vorbereitung auf die Prüfung dann hoffnungslos überfordert sind.

Studierende, die sich durch den Vorlesungsstoff eher unterfordert fühlen und das regelmässige Bearbeiten "langweiliger" Aufgaben als Zumutung empfinden, sind eingeladen, jeweils die "Challenge"-Aufgaben zu bearbeiten. Dies sind meist schwierigere Aufgaben, für die auch entsprechend mehr Punkte vergeben werden.

Warum brauche ich das Testat?

In der Regel nach dem ersten Studienjahr findet für die Bachelor-Studierenden die schriftliche Basisprüfung (bestehend aus vier Einzelprüfungen) über alle obligatorischen Fächer des Basisjahres statt. Der Erhalt des Testats ist eine unabdingbare Zulassungsvoraussetzung für die Basisprüfung.

Was passiert, wenn ich das Testat nicht erhalte?

Selbst wenn Sie die Testate in allen anderen obligatorischen Fächern erhalten haben, werden Sie bei Fehlen eines Testats nicht zur Basisprüfung zugelassen und sind damit gezwungen, das Testat im darauffolgenden Studienjahr nachzuholen und somit alle Einzelprüfungen (auch die über die anderen obligatorischen Fächer, in denen Sie die Testate erhalten haben) um mindestens ein halbes Jahr zu verschieben.

Kann ich das Testat auch nachträglich noch erhalten?

Nein. Wenn Sie während des Semesters nicht auf 96 Punkte kommen, wird Ihnen das Testat nicht erteilt, und es gibt keine Möglichkeit, es nachträglich noch zu bekommen. Sonderregelungen gelten nur bei nachgewiesener Krankheit, Absenzen wegen Militärdienst, oder bei später in den Studiengang eintretenden Studierenden.

Ich studiere nicht im Bachelor-Programm D-MATH / D-PHYS. Was gilt für mich?

Das hängt von Ihrem Studiengang ab und kann nicht pauschal beantwortet werden. Wenn Sie zu irgendeinem Zeitpunkt eine Prüfung über diese Vorlesung ablegen wollen, erkundigen Sie sich bitte bei den Verantwortlichen für Ihren Studiengang über die Zulassungsvoraussetzungen und Bedingungen. Falls Sie nicht an einen Prüfungsblock gebunden sind, können Sie die Prüfung bereits im Winter (zusammen mit den Repetierenden des letzten Studienjahres) ablegen.

Was ist, wenn ich das Testat in einem früheren Semster schon erhalten habe?

Einmal erhalten, bleibt das Testat für immer gültig. Sie sind gerne dazu eingeladen, die Übungen trotzdem abzugeben, müssen dies aber nicht tun.

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 Prüfungsstoff umfasst den theoretischen Teil (Hromkovic) und den C++ Teil (Gärtner). Für den C++ Teil gilt: Alles was auf den Folien erschienen ist und in der Vorlesung diskutiert wurde, gehört dazu. Für den theoretischen Teil gilt folgendes: Sie sollten die grundlegenden Begriffe der Informatik (Algorithmus, Programm, Entscheidungsproblem, Registermaschine,...) definieren resp. beschreiben können, Sie sollten einfache Registermaschinen-Programme verstehen und schreiben können, Sie sollten den Diagonalisierungsbeweis und seine Anwendungsbeispiele kennen und Sie sollten mit den ersten beiden Übungen vertraut sein. Zusammenfassend kann man sagen, dass die Kapitel 2, 3 und der erste Teil von 4 des Buches "Seven Wonders" den Stoff umreissen. Nicht zum Stoff gehören Reduktionen zwischen Entscheidungsproblemen (Abschnitt 4.4 in "Seven Wonders") und deren Anwendungen, z.b. das Halteproblem.

Aufgrund der zeitlichen Gewichtung der beiden Teile ist es klar, dass in der Prüfung der Fokus vor allem auf C++ Aufgaben liegen wird. Die letzten drei Prüfungen sind ein guter Anhaltspunkt, um sich die Aufteilung vorzustellen.

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.
  1. Klausur Winter 2009 und die Lösung dazu.
  2. Klausur Herbst 2008 und die Lösung dazu.
  3. Klausur Frühling 2008 und die Lösung dazu.
  4. Klausur Herbst 2007 und die Lösung dazu.
  5. Klausur Herbst 2006 und die Lösung dazu.
  6. Klausur Frühling 2006 und die Lösung dazu.
  7. Klausur Herbst 2005 und die Lösung dazu.

und Links

Libwindow

(Version 1.23 vom 8.10.2008)

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.23.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.23.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.23 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.23 hineinkopieren. Sie können dann Ihr Programm mit emacs oder dem Befehl make meinprogramm kompilieren.

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 und FAQs findet man hier.

Die Kommandozeilen Umgebung starten Sie mit C:\cygwin\usr\X11R6\bin\startxwin.bat (Tipp: Icon auf dem Desktop anlegen). 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

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 X 10.5 (Leopard) Benutzer sollten die Developer CD installieren. Emacs ist schon installiert, muss aber als graphisches Programm eingerichtet werden. Hier ist eine ausführliche Anleitung dazu. Falls jemand eine ältere Version von OS X verwendet (Tiger, Panther), dann empfehlen wir die entsprechende Anleitung auf der letztjährigen Kurshomepage.
Last modified: , by Yves Brise. Valid HTML 4.0! Valid CSS!