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

Informatik für Mathematiker und Physiker (252-0847-00) HS12

Prüfungseinsicht

Die Prüfungen der Sommersession 2013 können ab sofort eingesehen werden. Mögliche Zeiten sind Mo, Di, Do, Fr 10-12 Uhr sowie 13-15 Uhr im Sekretariat von Frau Salow (CAB G19.1). Bitte vereinbaren Sie vorher per email einen Termin mit Frau Salow.

Vorlesung Herbst 2013

Folgen sie diesem Link für Informationen zur aktuellen Vorlesung: Herbstsemester 2013.

Probeklausuren

Hier finden Sie die Klausur vom Januar 2013 mit Lösung sowie die Klausur vom August 2012 mit Lösung. Die Prüfung im August 2013 wird im Aufbau und Aufgabenstil ähnlich sein. Wir empfehlen Ihnen, die Klausuren zunächst ohne Ansicht der Lösung zu bearbeiten und erst danach eine Selbstkontrolle mit Hilfe der Lösungen vozunehmen.

Grundlegende Informationen zur Vorlesung

Informationsblatt

Skript

Die Vorlesungsunterlagen für den C++ Teil bestehen aus Skript, Vorlesungsfolien und Übungsunterlagen. Das Skript ist auf Englisch verfasst und wird in einer freien elektronischen Form zur Verfügung gestellt. Die Vorlesungsfolien sind auf Deutsch verfasst und stellen zusammen mit den Übungsblättern den Prüfungsstoff dar. Das heisst, das Skript enthält viele zusätzliche Erklärungen und Übungen.

Arbeitsumgebung

In der Vorlesung arbeiten wir für die Programmieraufgaben mit einem Linux-System. Wir stellen Ihnen dafür eine Arbeitsumgebung zur Verfügung, die bereits alles enthält, was Sie brauchen.

Benutzung der Arbeitsumgebung auf einem privaten Computer

Installieren Sie den Virtual Box Client, laden Sie die von uns vorbereitete virtuelle Maschine herunter (XubuntuIFMP12.ova) und importieren Sie diese in den Virtual Box Client. Folgen Sie dazu den Anweisungen auf der ersten Übungsserie.

Benutzung der Arbeitsumgebung in einem öffentlichen Computerraum, oder für Linux-Experten

Laden Sie den von uns vorbereiteten Linux-Tarball herunter ( IFMP_12_Linux.tgz), entpacken und installieren Sie ihn. Folgen Sie auch hier den Anweisungen auf der ersten Übungsserie.
Aktualisiertes Makefile, zur Benuztung sowohl mit der Virtual Box als auch dem Tarball (nicht notwendig für Virtual Box und Tarball, die ab dem 20. September 12.00 Uhr heruntergeladen wurden).

Übungsserien und Vorlesungsfolien

Die Lösungen zu den Programmieraufgaben sind in schriftlicher Form in den Lösungsabschnitten zu den Vorlesungsunterlagen enthalten. Damit Sie die Programme auch ausprobieren können, sammeln wir die .cpp Dateien in diesem Ordner.

Datum Themen Folien / Handout Übungsaufgaben Lösung Programme

Vorlesung 1 (18.09.2012) Grundlagen: Computer, Editor, Betriebssystem, Compiler, Plattform; C++: erstes Programm, Literale, Variablen, Konstanten Folien zu den Abschnitten 1.1 bis 2.1 im Skript [pdf zum Drucken] [pdf zum Ansehen]
[pdf zum ersten Programm]

Ein Artikel aus der Anfangszeit der höheren Programmiersprachen
Serie 1 [PDF] Lösung 1[PDF] [power8.cpp], [power8_exact.cpp]

Vorlesung 2 (25.09.2012) Grundlagen: Ausdrücke, Operatoren, Anweisungen; Ganze Zahlen: Die Typen int, unsigned int, arithemtische Operatoren, Auswertungsreihenfolge Folien zum Abschnitt 2.2 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 2 [PDF] Lösung 2[PDF] [fahrenheit.cpp], [limits.cpp]

Vorlesung 3 (02.10.2012) Wahrheitswerte; Boolesche Funktionen; der Typ bool; Kontrollanweisungen: if, if-else, for; Blöcke und Sichtbarkeit Folien zum Abschnitt 2.3 im Skript [pdf zum Drucken] [pdf zum Ansehen]; Folien zum Abschnitt 2.4 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 3 [PDF] Lösung 3[PDF] [sum_n.cpp], [prime.cpp]

Vorlesung 4 (09.10.2012) do-Anweisung, Sprung-Anweisungen, Auswahl der richtigen Iterationsanweisung; Fliesskommazahlen: die Typen float und double, Fliesskommazahlensysteme, Löcher im Wertebereich, IEEE Standard, Fliesskomma-Richtlinien Folien zum Abschnitt 2.5 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 4 [PDF] Lösung 4[PDF] [euler.cpp], [diff.cpp] [harmonic.cpp]

Vorlesung 5 (16.10.2012) Felder, Sieb des Eratosthenes, Zeiger, Zeigerarithmetik, dynamischer Speicher Folien zu den Abschnitt 2.6.1 bis 2.6.10 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 5 [PDF] Lösung 5[PDF] Challenge-Lösung von Nick Sauerwein [mandelbrotend.cpp] [eratosthenes.cpp] [eratosthenes2.cpp], [onepixel.cpp]

Vorlesung 6 (23.10.2012) Zeichen, Caesar-Code, String-Matching, Mehrdimensionale Felder, Kürzeste Wege [Video] Folien zu den Abschnitt 2.6.11 bis 2.6.12 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 6 [PDF] Zusatz-Challenge [PDF] Lösung 6[PDF] [caesar_encrypt.cpp] [caesar_decrypt.cpp] [string_matching.cpp] [string_matching2.cpp] [shortest_path.cpp] [Input data]

Vorlesung 7 (30.10.2012) Funktionsdefinitionen und -aufrufe; Gültigkeitsbereich; Felder als Funktionsargumente; Bibliotheken; Standardfunktionen Folien zum Abschnitt 3.1 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 7 [PDF] Lösung 7[PDF] [callpow.cpp] [prime2.cpp] [Input data]

Vorlesung 8 (6.11.2012) Rekursive Funktionen; Korrektheit, Terminierung; Rekursion vs. Iteration; Sortieren Folien zum Abschnitt 3.2 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 8 [PDF] Lösung 8[PDF] [fak-1.cpp] [fibonacci.cpp] [fibonacci2.cpp] [ackermann.cpp] [minimum_sort.cpp] [merge_sort.cpp]

Vorlesung 9 (13.11.2012) Lindenmayer-Systeme; Structs, benutzerdefinierte Operatoren, Referenztypen, Call by value / reference Folien zu den Abschnitten 3.2.7 bis 4.2.5 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 9 [PDF] Lösung 9[PDF] [lindenmayer.cpp] [dragon.cpp] [snowflake.cpp] [bush.cpp]

Vorlesung 10 (20.11.2012) Const-Referenzen, Klassen, Zufallszahlen Folien zu den Abschnitten 4.2.6 bis 4.3.10 im Skript [pdf zum Drucken] [pdf zum Ansehen] Serie 10 [PDF] Lösung 10[PDF] [choosing_numbers.cpp] [TicTacToe data]

Vorlesung 11 (27.11.2012) Listen, Funktionalität, Copy-Konstruktor, Zuweisungsoperator, Destruktor, Dynamische Datentypen Folien zu keinen Abschnitten im Skript :-) [pdf zum Drucken] [pdf zum Ansehen] Serie 11 [PDF] Lösung 11[PDF] [MyNode.h][MyNode.cpp][MyList.h][MyList.cpp][myListTest.cpp] [Ordner]

Vorlesung 12 (04.12.2012) Binäre Suchbäe, Treaps (randomisierte binäre Suchbäume) Folien: [pdf zum Drucken] [pdf zum Ansehen] Serie 12 [PDF] Lösung 12[PDF] [TreapNode.h][TreapNode.cpp][TreapSkeleton.h][TreapSkeleton.cpp][treapSkeletonTest.cpp] [Ordner]

Vorlesung 13 (11.12.2012) Analyse Treaps (randomisierte binäre Suchbäume) Folien: [pdf zum Drucken] [pdf zum Ansehen] Serie 13 [PDF] Lösung 13[PDF] [findmin.cpp]

Vorlesung 14 (18.12.2012) Generisches programmieren: Template-Funktionen, Template-Klasen, generisches Sortieren, Fibonacci- und Ackermann-ZAhlen zur Kompilierungszeit Folien: [pdf zum Drucken] [pdf zum Ansehen] [swap.cpp] [generic_minimum_sort.cpp] [GenericTreapNode.h] [GenericTreap.h] [treapSort.cpp] [fibTemplate.cpp] [ackermannTemplate.cpp]

Termine

Vorlesung: Dienstag 13:15-15:00, ETA F5
Bernd Gärtner, CAB G31.1, Tel: 044 632 70 26, gaertner@inf.ethz.ch.
Übung: Dienstag 15:15-17:00
Chefassistent: Milos Novacek CAB F52.2, Tel: 044 44 633 92 62, milos.novacek@inf.ethz.ch
GruppeZeitRaumAssistentInemail
A Di 15:15 - 17:00 CAB G56 Maria Christakis maria.christakis@inf.ethz.ch
B Di 15:15 - 17:00 CAB G59 Malte Schwerhoff malte.schwerhoff@inf.ethz.ch
C Di 15:15 - 17:00 CHN D44 Benjamin Schindler bschindler@inf.ethz.ch
D Di 15:15 - 17:00 CHN D48 Lucas Brutschy lucas.brutschy@inf.ethz.ch
E Di 15:15 - 17:00 CHN E42 Nguyen Thanh Binh thannguy@inf.ethz.ch
F Di 15:15 - 17:00 CHN G22 Sebastian Stich sstich@inf.ethz.ch
G Di 15:15 - 17:00 HG D1.2 Christian Stücklberger stuecklc@student.ethz.ch
H Di 15:15 - 17:00 HG D3.1 Florian Andritsch fandritsch@student.ethz.ch
I Di 15:15 - 17:00 HG D3.3 Gian-Peder Fasser gfasser@student.ethz.ch
J Di 15:15 - 17:00 HG D5.1 Thomas Scholtes thoschol@student.ethz.ch
K Di 15:15 - 17:00 HG F26.3 David Glenck glenckda@student.ethz.ch
L Di 15:15 - 17:00 HG F26.5 Christoph Müller muellch@student.ethz.ch
M Di 15:15 - 17:00 IFW A34 Daniele Spampinato daniele.spampinato@inf.ethz.ch
N Di 15:15 - 17:00 LFW E11 Markus Roos mroos@student.ethz.ch
O Di 15:15 - 17:00 LFW E13 Joris Ticozzelli jorist@student.ethz.ch
P Di 15:15 - 17:00 ML J34.1 Georg Ofenbeck ofenbeck@inf.ethz.ch
Q Di 15:15 - 17:00 ML J34.3 Endri Dibra edibra@student.ethz.ch
R Di 15:15 - 17:00 ML J37.1 Andrea Arteaga arteagaa@student.ethz.ch
S Di 15:15 - 17:00 HG D5.3 Flavio Petrini petrinif@student.ethz.ch
Die Gruppen A, E, und M werden auf Englisch gehalten. Die Gruppe R wird auf Italienisch gehalten.

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.

Hinweise zur Übung

Auf jeder Übungsserie gibt es mehrere Aufgaben, die schriftlich zu bearbeiten und zum angegebenen Termin 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 3-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 50% der regulären Punkte aus allen Übungsserien erlangen. Bei 13 Übungsserien werden das 100 Punkte sein. Es spielt dabei jedoch keine Rolle, ob Sie die Punkte aus regulären Aufgaben oder aus Challenge-Aufgaben erzielen. Insbesondere können Sie sowohl die regulären als auch die Challenge-Aufgaben einer Serie lösen und somit mehr als 16 Punkte pro Serie 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 Studierende 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 darauf folgenden 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 100 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 Semester 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.

Die Referenz für den Prüfungsstoff ist alles, was in der Vorlesung besprochen wurde, und die Übungsaufgaben. Insbesondere bedeutet das, dass zusätzliche Informationen aus dem Skript nicht an der Prüfung verlangt werden.

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. Die Lösungen sind zum jetzigen Zeitpunkt noch nicht zugänglich und werden gegen Ende des Semesters freigeschaltet.
  1. Klausur Herbst 2011 und die Lösung dazu.
  2. Klausur Frühjahr 2011 und die Lösung dazu.
  3. Klausur Herbst 2010 und die Lösung dazu.
  4. Klausur Frühjahr 2010 und die Lösung dazu.
  5. Klausur Herbst 2009 und die Lösung dazu.
  6. Klausur Frühjahr 2009 und die Lösung dazu.
  7. Klausur Herbst 2008 und die Lösung dazu.
  8. Klausur Frühjahr 2008 und die Lösung dazu.
  9. Klausur Herbst 2007 und die Lösung dazu.
  10. Klausur Herbst 2006 und die Lösung dazu.
  11. Klausur Frühjahr 2006 und die Lösung dazu.
  12. Klausur Herbst 2005 und die Lösung dazu.

Literatur und Links


Last modified: 2018 Feb 28, 16:53:28, by Bernd Gärtner. Valid HTML 4.0! Valid CSS!