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

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

Prüfung mit Musterlösung

Klausur Winter 2017 (zweisprachig) und die Lösung dazu.

Prüfungsvorbereitung

Wir stellen Ihnen einen Rückblick mit Beispielen und eine Kurzzusammenfassung der Vorlesung zur Verfügung. In diesem Dokument finden Sie auch die Lernziele, die in der Prüfung kontrolliert werden. In der Liste unten sind diese Lernziele noch einmal aufgeführt, jeweils mit Links zu Aufgaben (aus den Serien und Selbsteinschätzungen), die diese Lernziele kontrollieren. Wichtig: In der Prüfung wird eine Teilmenge der angegebenen Lernziele kontrolliert, allerdings mit möglicherweise anderen Aufgabentypen. Das Studium alter Prüfungsaufgaben (ganz unten auf dieser Seite) wird deshalb auch empfohlen.

Goals: Students should be able to...


Musterlösung der Bonus-Serie

Wir stellen Ihnen hier eine Musterlösung für die Bonusserie zur Verfügung:

Musterlösung

Bonus-Serie

Die Bonusserie ist jetzt online! Wir werden diese Sektion der Webseite stets aktuell halten, und hier Neuigkeiten publizieren. Ausserdem werden wir Sie hier über technische Probleme aufklären, falls es zu solchen kommen sollte. Weitere organisatorische Details entnehmen Sie der Bonusserie. Der letztmögliche Abgabetermin ist der Dienstag, 6. Dezember 2016, um 23:59 Uhr.

Anmerkung: In der Bonusserie darf auch Funktionalität aus der Standarbibliothek benutzt werden, die in der Vorlesung bisher nicht behandelt worden ist (soweit von Codeboard unterstützt), zum Beispiel std::stack<int>.

Anmerkung 2: Es kann vorkommen, dass Codeboard Ihnen Testsets als falsch wertet, sofern Ihr Programm für diese länger als eine festgelegte Maximalzeit benötigt. Gründe für die Zeitüberschreitung können Ihrerseits entweder Programmierfehler oder ein sehr ineffizientes Programm sein. Wir werden allerdings die eingereichten Programme unabhängig von ihrer Laufzeit bewerten, weshalb es wichtig ist, dass Sie das Programm dennoch submitten. Eine Zeitüberschreitung aufgrund von Programmierfehlern (zum Beispiel uninitialisierte Variablen) sollten Sie aber auf jeden Fall selbst beheben, da sich diese Fehler bei uns auch ohne Zeitbegrenzung zeigen werden.

Änderungsprotokoll
Berechnung des Notenbonus
Musterlösung



Self-Assessment IV

Wir möchten Sie darauf hinweisen, dass wir Ihnen in Woche 13 (am 13.12.2016) das Self-Assessment IV anbieten. Die Hauptthemen werden sein: Sollte sich aus irgendwelchen Gründen bis dahin etwas verändern, werden wir Ihnen dies an dieser Stelle mitteilen.

Self-Assessment III

Wir möchten Sie darauf hinweisen, dass wir Ihnen in Woche 10 (am 22.11.2016) das Self-Assessment III anbieten. Die Hauptthemen werden sein: Sollte sich aus irgendwelchen Gründen bis dahin etwas verändern, werden wir Ihnen dies an dieser Stelle mitteilen.

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 (Version 2015) 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 dieser Vorlesung arbeiten wir mit Codeboard, einer Online-Entwicklungsumgebung. Codeboard unterstützt Sie beim Programmieren, beim Testen, als auch beim Abgeben Ihrer Programme an Ihren Übungsleiter. Auf der ersten Serie finden Sie eine kurze Anleitung zur Verwendung von Codeboard.
Anmerkung: Wir behalten uns vor, jeweils zwischen 8 und 9 Uhr morgens Wartungsarbeiten an unserem Setup vorzunehmen. Es kann deshalb sein, dass Sie dann nicht submitten können. Falls Sie davon betroffen sind, versuchen Sie es einfach später nochmal.

Ausserdem stellen wir Ihnen ein Tutorial zur Verfügung, in dem Sie die ersten Schritte im Programmieren in C++ lernen. Es hilft beispielsweise den Studierenden, die über keine Vorkenntnisse im Programmieren verfügen. Der Inhalt des Tutorials ist keine Voraussetzung, um der Vorlesung folgen zu können; alle im Tutorial angesprochenen Konzepte werden in der Vorlesung im Detail behandelt. Wenn Sie das Tutorial bearbeitet haben, wird Ihnen das Verständnis dieser Konzepte allerdings leichter fallen. Zum Tutorial bieten wir Ihnen an folgenden Daten Sprechstunden an, in welche Sie ohne Voranmeldung gehen können:

Zeit Datum Raum
17-19 Mi, 21. September CAB H 86.3
17-19 Do, 22. September CAB G 31.1
15-17 Fr, 23. September CAB G 31.1

Übungsserien und Vorlesungsfolien

Nachdem Sie Ihre Programme fertig geschrieben und getestet haben, können Sie sie submitten. Hierzu drücken Sie einfach in Codeboard auf den entsprechenden Button.

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 (20.09.2016) 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]

Organisatorische Hinweise [PDF]

Ein Artikel aus der Anfangszeit der höheren Programmiersprachen

[Aufzeichnung]
Befehle 1 Serie 1 [PDF] Lösung 1 [PDF] [power8.cpp] power8-Animation und Handout zum ersten Programm

Vorlesung 2 (27.09.2016) 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]

Self-Assessment [PDF]
Lösung 2 [PDF]

Lösung SA [PDF]
[fahrenheit.cpp]
[limits.cpp]
Zaubertrick
[Flashcard 1]

Vorlesung 3 (04.10.2016) Boolesche Funktionen; der Typ bool; logische und relationale Operatoren; Assertions; Auswahlanweisungen, Iterationsanweisungen, Terminierung, Blöcke Handout zu den Abschnitten 2.3 und des ersten Teils von 2.4 im Skript [PDF]
[Aufzeichnung]
Befehle 3 Serie 3 [PDF] Lösung 3 [PDF] [divmod.cpp]
[prime.cpp]
[sum_n.cpp]
Addierer-Animation
[Flashcard 2]

Vorlesung 4 (11.10.2016) 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] Lösung 4 [PDF] [collatz.cpp],
[euler.cpp],
[diff.cpp]
[Flashcard 3]

Vorlesung 5 (18.10.2016) 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] Lösung 5 [PDF] [harmonic.cpp],
[callpow.cpp]
[Flashcard 4]

Vorlesung 6 (25.10.2016) 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](*)

Self-Assessment II [PDF]
Lösung 6 [PDF]

Lösung SA II [PDF]
[callpow2.cpp],
[prime2.cpp]
[Flashcard 5]

Vorlesung 7 (01.11.2016) Referenztypen: Definition und Initialisierung, Call By Value , Call by Reference, Temporäre Objekte, Konstanten, Const-Referenzen, 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] Lösung 7 [PDF] [eratosthenes.cpp],
[eratosthenes2.cpp],
[caesar_encrypt.cpp],
[caesar_decrypt.cpp]
[Flashcard 6]

Vorlesung 8 (08.11.2016) 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]
[Turtle-Befehle]
Lösung 8 [PDF] [lindenmayer.cpp],
[bush.cpp]
[snowflake.cpp]
[rainbowflake.cpp]
[dragon.cpp]
[shortest_path.cpp]
[Flashcard 7]

Vorlesung 9 (15.11.2016) 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] Lösung 9 [PDF] [fibonacci.cpp],
[fibonacci2.cpp]
[Flashcard 8]

Vorlesung 10 (22.11.2016) Bau eines Taschenrechners, Ströme, BNF, EBNF, Parsen Handout zum Kapitel 2.10 im Skript [PDF]
[Aufzeichnung]
Befehle 10 Serie 10 [PDF](**)

Self-Assessment III [PDF]
Lösung 10 [PDF]

Lösung SA III [PDF]
[calculator.cpp],
[simple_calculator_l.cpp],
[simple_calculator_r.cpp],
[calculator_r.cpp],
[calculator_l.cpp]
[Flashcard 9]

Vorlesung 11 (29.11.2016) Rationale Zahlen, Struct-Definition, Operator-Überladung, Const-Referenzen, Datenkapselung, Klassen-Typen Handout zum Abschnitt 3.1 im Skript [PDF]
[Aufzeichnung]
Befehle 11 Diese Woche keine neue Serie [use_rational.cpp],
[rationals_with_operators.cpp]

Vorlesung 12 (06.12.2016) 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] Lösung 12 [PDF] [rationals_with_classes.cpp],
[stack_test.cpp],
[stack_example.cpp]
[Flashcard 10]
[Flashcard 11]

Vorlesung 13 (13.12.2016) 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]
Self-Assessment IV [PDF]
Lösung 13 [PDF]
Lösung SA IV [PDF]
[texpression_test.cpp],
[texpression_calculator.cpp],
[double_calculator.cpp],
[xexpression_test.cpp]
[Flashcard 12]

Vorlesung 14 (20.12.2016) Inhaltlicher Rückblick mit Beispielprogrammen Folien [PDF] [lecture2.cpp] [lecture3a.cpp] [lecture3b.cpp] [lecture4a.cpp] [lecture4b.cpp] [lecture5.cpp] [lecture6.cpp] [lecture7a.cpp] [lecture7b.cpp] [lecture8.cpp] [lecture9a.cpp] [lecture9b.cpp] [lecture10.cpp] [lecture11.cpp] [lecture12a.cpp] [lecture12b.cpp]

(*) Anmerkung: in der Aufgabenstellung bei Aufgabe 2.b hatte es einen Fehler. In der jetzt veröffentlichten Version ist dieser korrigiert.
(**) Anmerkung: bei der Aufgabe 3.b wurde ein Hinweis ergänzt, dass gewisse Bestandteile des Programms aus Platzgründen nicht abgedruckt sind, aber im Programm dennoch vorhanden sind.

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 Bhargav Bhatt (E) bbhatt [at] ethz.ch
B LFW C 1 Der-Yeuan Yu (E) dyu [at] inf.ethz.ch
C ML H 34.3 Alen Stojanov (E) astojanov [at] inf.ethz.ch
D ML H 41.1 Reza Sefidgar (E) srsefidgar+ifmp [at] gmail.com
E CHN D 48 Sinisa Matetic (E) sinisa.matetic [at] inf.ethz.ch
F CHN D 44 David Sommer david.sommer [at] inf.ethz.ch
G CHN E 42 Benjamin Rothenberger rothenbb [at] student.ethz.ch
H ML J 34.1 Dejan Mircic mircicd [at] student.ethz.ch
I ML J 37.1 Daniele Spampinato (I) daniele.spampinato [at] inf.ethz.ch
J HG D 1.2 Roman Cattaneo romanc [at] student.ethz.ch
K HG D 3.3 Jan Kleffmann klejan [at] ethz.ch
L HG D 5.1 Sven Heberle heberles [at] student.ethz.ch
M HG D 5.3 Max Biegert mbiegert [at] student.ethz.ch
N HG E 33.5 Sezer Güler sezer.gueler [at] googlemail.com
O HG F 26.3 Aaron Müller aam [at] student.ethz.ch
P HG F 26.5 Raphael Appenzeller apraphae [at] student.ethz.ch
Q IFW A 34 Tobias Sägesser tobiass [at] student.ethz.ch
R IFW C 31 Pascal Iselin iselinp [at] student.ethz.ch
S IFW D 42 Felix Richter richterf [at] student.ethz.ch
T NO C 6 Jérôme Holbein jeromeh [at] student.ethz.ch

Die Gruppen A-E werden auf Englisch gehalten. Die Gruppe I 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 reichen Sie bis zu diesem Termin auf Codeboard via Submit-Button ein. Auf den Serien gibt es Links, welche Sie direkt zur entsprechenden Aufgabe auf Codeboard weiterleiten. Auf den normalen Übungsserien finden Sie ausserdem Punkte zu jeder Aufgabe. Diese 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 Ihr Übungsleiter diese Materialien nicht (oder nur teilweise) in seine Übungsstunden integriert. Falls Ihr Übungsleiter, eigene Materialien verwendet, fragen Sie am besten dort direkt, ob er Ihnen seine Materialien zur Verfügung stellt.

Hier finden Sie die Materialien: Materialien

Prüfung

Die Prüfung zur Vorlesung 2016 findet je nach Ihrer Wahl im Winter 2017 oder im Sommer 2017 statt.

Die Referenz für den Prüfungsstoff ist alles, was in der Vorlesung besprochen wurde (laut Handout), die Übungsaufgaben und deren Lösungen, und der Inhalt der Bonusserie und deren Lösung. 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. Wir werden vorlesungsbegleitend konkrete Lernziele veröffentlichen und nur diese prüfen. Wie bereits unter Freiwillige Programmierübung erwähnt, können Sie sich unter dem Semester mit einer freiwilligen Programmierübung Bonuspunkte holen, die an die Prüfung mitgenommen werden.

Repetitionsprüfung

Es handelt sich bei der Repetitionsprüfung um die normale Prüfung der entsprechenden Prüfungssession. Das bedeutet, dass der Stoff der zuletzt gelesenen Vorlesung geprüft wird.

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 Herbst 2016 (zweisprachig) und die Lösung dazu.
  2. Klausur Frühjahr 2016 (zweisprachig) und die Lösung dazu.
  3. Klausur Herbst 2015 (zweisprachig) und die Lösung dazu.
  4. Klausur Frühjahr 2015 (zweisprachig) und die Lösung dazu.
  5. Klausur Frühjahr 2014 (English) und die Lösung dazu.
  6. Probeklausur A Dezember 2013 (English) und die Lösung dazu.
    Probeklausur B Dezember 2013 (English) und die Lösung dazu.
  7. Klausur Herbst 2013 (English) und die Lösung dazu.
  8. Klausur Frühjahr 2013 und die Lösung dazu.
  9. Klausur Herbst 2012 und die Lösung dazu.
  10. Klausur Frühjahr 2012 und die Lösung dazu.
  11. Klausur Herbst 2011 und die Lösung dazu.
  12. Klausur Frühjahr 2011 und die Lösung dazu.
  13. Klausur Herbst 2010 und die Lösung dazu.
  14. Klausur Frühjahr 2010 und die Lösung dazu.
  15. Klausur Herbst 2009 und die Lösung dazu.
  16. Klausur Frühjahr 2009 und die Lösung dazu.
  17. Klausur Herbst 2008 und die Lösung dazu.
  18. Klausur Frühjahr 2008 und die Lösung dazu.
  19. Klausur Herbst 2007 und die Lösung dazu.
  20. Klausur Herbst 2006 und die Lösung dazu.
  21. Klausur Frühjahr 2006 und die Lösung dazu.
  22. Klausur Herbst 2005 und die Lösung dazu.

Literatur und Links



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