Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

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

Prüfungeinsicht

Die Prüfung vom 12. 8. 2016 kann ohne Voranmeldung zur folgenden Zeit im Raum CAB G15.2 eingesehen werden: Ausserdem sind die Aufgabenstellung und die Musterlösung auch online einsehbar:

Die Prüfung vom 27. 1. 2016 kann ohne Voranmeldung zur folgenden Zeit im Raum CAB G15.2 eingesehen werden: Ausserdem sind die Aufgabenstellung und die Musterlösung auch online einsehbar:

Prüfungsrelevantes

Da viele Studenten froh um eine detaillierte Auflistung mit Prüfungsrelevantem und nicht Prüfungsrelevantem wären, stellen wir Ihnen hier eine solche Auflistung zur Verfügung: Prüfungsrelevantes

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

Folgen Sie dazu den Anweisungen zur Installation von Linux mit VirtualBox.

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

Folgen Sie dazu den Anweisungen zur Installation auf Linux.

Testen der Installation

Um Ihre Installation zu testen, können Sie versuchen gemäss der Anleitung Kompilieren eigener Programme ihr erstes Programm zu kompilieren und auszuführen.

Übungsserien und Vorlesungsfolien

Damit Sie die Programme auch ausprobieren können, sammeln wir die .cpp Dateien in diesem Ordner. Damit Sie Ihre eigenen Programme vor der Abgabe selbst testen können, drucken wir Ihnen entweder Beispielsaufrufe auf den Serien ab, oder stellen im Ordner [Input Data] (zu passender Serie) einige Beispiele (Eingabe/Ausgabe) zur Verfügung.

Nachdem Sie Ihre Programme fertig geschrieben und getestet haben, können Sie sie auf den IFMP-Judge submitten. Hierzu finden Sie auf den Serien bei den Programmieraufgaben einen Link. Sie müssen ausserdem einmalig einen Enrolment-Key eingeben. Dieser lautet
cplusplus
Falls Sie meinen, dass der IFMP-Judge nicht richtig funktioniert, finden Sie hier eine Seite mit bekannten Problemen, und in welchem Zeitraum sie aufgetreten sind.

Wir stellen Ihnen ausserdem Auflistungen der C++ Befehle der jeweiligen Woche zur Verfügung. Diese Auflistungen erheben keinen Anspruch auf Vollständigkeit. Falls Sie Fehler darin finden, oder andere Rückmeldungen oder Anmerkungen dazu haben, wenden Sie sich an Christian Zingg, zinggch@student.ethz.ch.
Datum Themen Folien / Handout C++ Übersicht Übungsaufgaben Lösung Programme Material
Vorlesung 1 (16.09.2014) Informatik: Definition und Geschichte, Algorithmen, Turing-Maschine, Höhere Programmiersprachen, Werkzeuge der Programmierung, das erste C++ Programm und seine syntaktischen und semantischen Bestandteile Handout zu den Abschnitten 1.1 bis 2.1 im Skript [PDF] [Aufzeichnung]
Organisatorische Hinweise [PDF]

Ein Artikel aus der Anfangszeit der höheren Programmiersprachen 		Befehle 1 Serie 1 [PDF] [power8.cpp],
[power8_exact.cpp]		 power8-Animation und Handout zum ersten Programm
Vorlesung 2 (22.09.2015) Auswertung arithmetischer Ausdrücke, Assoziativität und Präzedenz, arithmetische Operatoren, Wertebereich der Typen int, unsigned int Handout zum Abschnitt 2.2 im Skript [PDF] [Aufzeichnung] Befehle 2 Serie 2 [PDF] [fahrenheit.cpp],
[limits.cpp]
Vorlesung 3 (29.09.2015) Boolesche Funktionen; der Typ bool; logische und relationale Operatoren; Kurzschlussauswertung; Sicheres Programmieren (Assertions und Konstanten); Auswahlanweisungen, Iterationsanweisungen, Terminierung, Handout zu den Abschnitten 2.3 und des ersten Teils von 2.4 im Skript [PDF] [Aufzeichnung] Befehle 3 Serie 3 [PDF] [assertion.cpp],
[assertion2.cpp],
[divmod.cpp],
[prime.cpp], [sum_n.cpp]		 Addierer-Animation
Vorlesung 4 (06.10.2015) Sichtbarkeit, lokale Variablen, While-, Do- und Sprunganweisung, die Typen float und double, Gemischte Ausdrücke und Konversion, Löcher im Wertebereich Handout zum zweiten Teil von Abschnitt 2.4 und zum ersten Teils von 2.5 im Skript [PDF] [Aufzeichnung] Befehle 4 Serie 4 [PDF] [collatz.cpp],
[euler.cpp],
[diff.cpp],
Vorlesung 5 (13.10.2015) Fliesskommazahlensysteme; IEEE Standard; Grenzen der Fliesskommaarithmetik; Fliesskomma-Richtlinien; Harmonische Zahlen; Funktionsdefinitionen- und Aufrufe; der Typ void; Vor- und Nachbedingungen Handout zum zweiten Teil von Abschnitt 2.5 und zum ersten Teils von 2.6 im Skript [PDF] [Aufzeichnung] Befehle 5 Serie 5 [PDF]
[dec2float_skeleton.cpp]		 [harmonic.cpp],
[callpow.cpp]
Vorlesung 6 (20.10.2015) Stepwise Refinement, Gültigkeitsbereich, Bibliotheken, Standardfunktionen, Vorschau Referenztypen Handout zum zweiten Teil von 2.6 und zum ersten Teil von 2.7 im Skript [PDF] [Aufzeichnung] Befehle 6 Serie 6 [PDF] [pow.cpp],
[callpow2.cpp],
[prime2.cpp]
Vorlesung 7 (27.10.2015) Referenztypen: Definition und Initialisierung, Call By Value , Call by Reference, Temporäre Objekte, Feldtypen, Sieb des Eratosthenes, Speicherlayout, Iteration, Vektoren, Zeichen, Texte, ASCII, UTF-8, Caesar-Code Handout zum zweiten Teil von 2.7 und zum ersten Teil von 2.8 im Skript [PDF] [Aufzeichnung] Befehle 7 Serie 7 [PDF] [eratosthenes.cpp],
[eratosthenes2.cpp],
[caesar_encrypt.cpp],
[caesar_decrypt.cpp]
Vorlesung 8 (03.11.2015) Strings, Lindenmayer-Systeme, Mehrdimensionale Felder, Vektoren von Vektoren, Kürzeste Wege, Zeiger Handout zum zweiten Teil von 2.8 und zum ersten Teil von 2.9 im Skript [PDF] [Aufzeichnung] Befehle 8 Serie 8 [PDF], [iteration_template_a.cpp], [iteration_template_b.cpp], [iteration_template_c.cpp] [Turtle-Befehle] [turtle.cpp],
[bitmap.cpp],
[lindenmayer.cpp],
[dragon.cpp],
[snowflake.cpp],
[bush.cpp],
[shortest_path.cpp],
[Eingabedaten]
Vorlesung 9 (10.11.2015) Iteration mit Zeigern, Felder: Indizes vs.\ Zeiger, Felder und Funktionen, Zeiger und const, Algorithmen, Container und Traversierung, Vektor-Iteratoren, Typedef, Mengen, das Iterator-Konzept, Mathematische Rekursion, Terminierung, der Aufrufstapel, Beispiele, Rekursion vs. Iteration Handout zum Kapitel 2.9 und zum ersten Teil von Kapitel 2.10 im Skript [PDF] [Aufzeichnung] Befehle 9 Serie 9 [PDF], [ex1a_template.cpp], [ex1b_template.cpp], [ex1c_template.cpp], [ex1d_template.cpp], [partitions_template.cpp] [fibonacci.cpp]
[fibonacci2.cpp]
Vorlesung 10 (17.11.2015) Bau eines Taschenrechners, Ströme, BNF, Parsen Handout zum Kapitel 2.10 im Skript [PDF] [Aufzeichnung] Befehle 10 Serie 10 [PDF] [calculator_l.cpp],
[calculator_r.cpp],
[calculator_r.in],
[simple_calculator_r.cpp],
[simple_calculator_l.cpp]
Vorlesung 11 (24.11.2015) Rationale Zahlen, Struct-Definition, Operator-Überladung, Const-Referenzen, Datenkapselung, Klassen-Typen Handout zum Abschnitt 3.1 im Skript [PDF] [Aufzeichnung] Befehle 11 Serie 11 [PDF] [use_rational.cpp]
Vorlesung 12 (01.12.2015) Memberfunktionen, Konstruktoren, verkettete Liste, Stapel, dynamischer Speicher, Kopierkonstruktor, Zuweisungsoperator, Destruktor, Konzept Dynamischer Datentyp Handout zum Abschnitt 3.3 im Skript [PDF] [Aufzeichnung] Befehle 12 Serie 12 [PDF](*),
[vector_template.cpp]		 [stack.h],
[stack.cpp],
[stack_example.cpp],
[stack_test.cpp]
Vorlesung 13 (08.12.2015) Ausdrucksbäume, Vererbung, Code-Wiederverwendung, virtuelle Funktionen, Polymorphie, Konzepte des objektorientierten Programmierens Handout zum nicht existierenden Abschnitt im Skript [PDF](**) [Aufzeichnung] Befehle 13 Serie 13 [PDF],
[extended_stack_template.cpp] [queue_template.cpp] [vector_template.cpp]		 [texpression.cpp],
[texpression_calculator_l.cpp],
[texpression_test.cpp],
[xexpression.cpp],
[xexpression_test.cpp]
Vorlesung 14 (15.12.2015) Treaps (Randomisierte Suchbäme) Handout zum nicht existierenden Abschnitt im Skript [PDF](**) [Aufzeichnung] Serie 14 [PDF],
[house_template.cpp] [statements_template.cpp]
(*) Das Abgabedatum der ifmp::vector Aufgabe wurde um eine Woche verlängert.
(**) Beachten Sie die Hinweise zu den prüfungsrelevanten Themen: Prüfungsrelevantes

Termine

Vorlesung: Dienstag 13:15-15:00, ML D 28 und ML E 12 (Videoübertragung).
Bernd Gärtner CAB G 31.1, Tel: 044 632 70 26, gaertner@inf.ethz.ch.
Übung: Dienstag 15:15-17:00
Chefassistent: Christian Zingg, zinggch@student.ethz.ch.

Die Einteilung in die Übungsgruppen wird in der ersten Vorlesung vorgenommen. Wenn Sie in dieser Stunde nicht anwesend sein können, wenden Sie sich per Email an Christian Zingg (zinggch@student.ethz.ch) zwecks nachträglicher Einteilung.

Gruppe Raum AssistentIn Email
A CAB G 59 Jerri Nummenpalo (E/D) jerri.nummenpalo@inf.ethz.ch
B IFW C 31 Yeara Kozlov (E/D) yeara.kozlov@inf.ethz.ch
C IFW A 34 Virág Varga (E) virag.varga@inf.ethz.ch
D ML H 41.1 Arshavir Ter-Gabrielyan (E) ter-gabrielyan@inf.ethz.ch
E CHN E 42 Dimitar Dimitrov (E) dimitar.dimitrov@inf.ethz.ch
F CHN G 22 Hemant Tyagi (E) htyagi@inf.ethz.ch
G CHN D 44 Marco Eilers marco.eilers@inf.ethz.ch
H CHN D 48 Cyrill Gössi cgoessi@student.ethz.ch
I ML J 37.1 Daniele Spampinato (I) daniele.spampinato@inf.ethz.ch
J ML H 34.3 Nathalie Ziehl ziehln@student.ethz.ch
K ML J 34.1 Jérôme Holbein jeromeh@student.ethz.ch
L HG F 26.5 Sezer Güler sezer.gueler@googlemail.com
M HG E 33.5 Christoph Müller (M) muellch@student.ethz.ch
N HG F 26.3 Matthias Untergassmair untergam@student.ethz.ch
O HG D 1.2 Roman Cattaneo romanc@student.ethz.ch
P HG D 3.3 Aaron Müller amm@student.ethz.ch
Q HG D 5.1 Maximilian Holst holstm@ethz.ch
R HG D 5.3 Felix Gast fgdorian@gmail.com
S ETF B 105 Michael Bühler buehlmic@student.ethz.ch
T LFW E 13 Jan Kleffmann klejan@ethz.ch
U NO C 60 Kaan Yücer kaan.yucer@disneyresearch.com

Die Gruppen A-F werden auf Englisch gehalten. Die beiden Gruppen A und B richten sich speziell an Studierende, die selber noch nicht fliessend in Englisch sind, aber dennoch eine Gruppe auf Englisch besuchen möchten. Die Gruppe I wird auf Italienisch gehalten. Die Gruppe M ist die Master-Class (siehe unten).

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 reichen Sie bis zu diesem Termin auf den IFMP-Judge ein. Hierzu finden Sie bei den entsprechenden Aufgaben auf den Serien Links. Die auf den normalen Übungsserien angegebenen Punkte dienen lediglich dazu, Ihnen auf einen Blick zu sagen, wie gut Sie eine Aufgabe gelöst haben. Die Punkte auf den normalen Übungsserien zählen nicht für Ihre Note in der Prüfung.

Freiwillige Programmierübung

Wir offerieren im Semester eine freiwillige Programmierübung, welche korrigiert und bewertet wird. Die dabei erzielten Punkte werden in die spätere Prüfungsklausur als Bonus mitgenommen. Maximal erreichbarer Bonus entspricht 1/8 Note. Dieser Bonus kann nicht in spätere Repetitionsklausuren mitgenommen werden.

Materialien der Übungsgruppen

Jede Woche finden Übungsgruppen statt, in denen die Themen aus den Vorlesungen geübt werden (siehe oben). Wir stellen den Übungsleitern jeweils einige Materialien (Präsentationen, Programme, etc.) zur Verfügung, mit denen sie ihren Unterricht gestalten können. Wir stellen Ihnen diese Materialien auf einer speziellen Website zur Verfügung, damit Sie diese nach den Übungsstunden erneut ansehen können, wenn Sie dies wollen. Zu beachten ist aber, dass diese Materialien der Übungsgruppen nicht prüfungsrelevant sind. Ausserdem kann es sein, dass Ihre Übungsleiterin/Ihr Übungsleiter, diese Materialien nicht (oder nur teilweise) in ihre/seine Übungsstunden integriert. Falls Ihre Übungsleiterin/Ihr Übungsleiter, eigene Materialien verwendet, fragen Sie am besten dort direkt, ob sie/er Ihnen ihre/seine Materialien zur Verfügung stellt.

Hier finden Sie die Materialien: Materialien

Master-Class

Die Master-Class richtet sich an diejenigen Studierenden, die bereits Erfahrung im Programmieren haben. Selbstverständlich ist die Master-Class nicht prüfungsrelevant, ausserdem wird dort nicht explizit auf die Prüfung vorbereitet. Allfällige Fragen zum Vorlesungsstoff beantwortet Christoph Müller aber trotzdem gerne während der Pause oder auch per Mail. Ausserdem können ihm die wöchentlichen Übungsserien regulär zur Korrektur abgegeben werden (schriftliche Aufgaben auf Papier und Programmieraufgaben via IFMP-Judge). Während der ersten Master-Class wird ein Test zur Selbsteinschätzung offeriert.

Inhalt:

Prüfung

Die Hauptprüfung findet im Sommer 2016 statt.

Die Referenz für den Prüfungsstoff ist alles, was in der Vorlesung besprochen wurde (laut Handout), die Übungsaufgaben und der Inhalt der Probeprüfung. Insbesondere bedeutet das, dass zusätzliche Informationen aus dem Skript nicht an der Prüfung verlangt werden, es sei denn, es wird im Prüfungsstoff explizit darauf verwiesen. Wie bereits unter Freiwillige Programmierübung erwähnt, können Sie sich unter dem Semester mit einer freiwilligen Programmierübung Ihre Note aufbessern.

Repetitionsprüfung

In der Repetitionsprüfung wird der Stoff der zuletzt gelesenen Vorlesung geprüft. Für die Repetitionsprüfung im Januar/Februar 2016 ist also der Stoff von diesem Semester (HS15) massgebend.

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. Wir empfehlen Ihnen, die Klausuren zunächst ohne Ansicht der Lösung zu bearbeiten und erst danach eine Selbstkontrolle mit Hilfe der Lösungen vorzunehmen.
  1. Klausur Frühjahr 2016 (zweisprachig) und die Lösung dazu.
  2. Klausur Herbst 2015 (zweisprachig) und die Lösung dazu.
  3. Klausur Frühjahr 2015 (zweisprachig) und die Lösung dazu.
  4. Klausur Frühjahr 2014 (English) und die Lösung dazu.
  5. Probeklausur A Dezember 2013 (English) und die Lösung dazu.
    Probeklausur B Dezember 2013 (English) und die Lösung dazu.
  6. Klausur Herbst 2013 (English) und die Lösung dazu.
  7. Klausur Frühjahr 2013 und die Lösung dazu.
  8. Klausur Herbst 2012 und die Lösung dazu.
  9. Klausur Frühjahr 2012 und die Lösung dazu.
  10. Klausur Herbst 2011 und die Lösung dazu.
  11. Klausur Frühjahr 2011 und die Lösung dazu.
  12. Klausur Herbst 2010 und die Lösung dazu.
  13. Klausur Frühjahr 2010 und die Lösung dazu.
  14. Klausur Herbst 2009 und die Lösung dazu.
  15. Klausur Frühjahr 2009 und die Lösung dazu.
  16. Klausur Herbst 2008 und die Lösung dazu.
  17. Klausur Frühjahr 2008 und die Lösung dazu.
  18. Klausur Herbst 2007 und die Lösung dazu.
  19. Klausur Herbst 2006 und die Lösung dazu.
  20. Klausur Frühjahr 2006 und die Lösung dazu.
  21. Klausur Herbst 2005 und die Lösung dazu.

Literatur und Links


Last modified: , by Bernd Gärtner. Valid HTML 4.0! Valid CSS!