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

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


Prüfung mit Musterlösung, Prüfungseinsicht

Klausur Sommer 2018 (zweisprachig) und die Lösung dazu. Die Prüfungseinsicht findet statt am Freitag, 21. September 2018, 15-17 Uhr, CAB G15.2, ohne Voranmeldung. Bitte Legi mitbringen!

Termine

Vorlesung: Dienstag 13:15-15:00, ML D 28 und ML E 12 (Videoübertragung).

Dozent: Bernd Gärtner CAB G 31.1, Tel: 044 632 70 26, gaertner@inf.ethz.ch.

Übung: Dienstag 15:15-17:00; Übungsgruppen auf Deutsch, Englisch und Italienisch. Die Online-Einschreibung in die parallelen Übungsgruppen ist ab Dienstag, 19. September, 15.15 Uhr über diesen Link möglich.

Inhalt und Lernziele

Die Vorlesung gibt eine Einführung in das Programmieren anhand der Sprache C++. Wir behandeln fundamentale Typen, Kontrollanweisungen, Funktionen, Felder und Klassen. Die Konzepte werden dabei jeweils durch Algorithmen und Anwendungen motiviert und illustriert. Die Vorlesungsunterlagen für den C++ Teil bestehen aus Skript, Vorlesungshandouts und Übungsunterlagen. Das Skript ist auf Englisch verfasst und wird in einer freien elektronischen Form zur Verfügung gestellt. Die Vorlesungshandouts sind auf Deutsch und Englisch verfasst und stellen zusammen mit den Übungsserien den Prüfungsstoff dar. Das Skript enthält viele zusätzliche Erklärungen und Übungen. Konkrete Lernziele sind die folgenden (auf Englisch):

Goals: Students should be able to...

Tutorial

Zum erleichterten Einstieg in die Vorlesung, insbesondere für Anfänger im Programmieren, stellen wir dieses Jahr wieder ein Einstiegstutorial zur Verfügung, welches im Selbststudium durchlaufen werden kann. Wir empfehlen die frühzeitige Bearbeitung. Das Tutorial ist in deutscher und englischer Sprache verfügbar. Sie können innerhalb des Tutorials jederzeit die Sprache wechseln.

Prüfung und Notenbonus

Die Prüfung zur Vorlesung 2017 findet je nach Ihrer Wahl im Winter 2018 (empfohlen) oder im Sommer 2018 statt.

Die Referenz für den Prüfungsstoff sind die publizierten Handouts, die Übungsaufgaben und deren Lösungen. Zusätzliche Informationen aus dem Skript sind nicht prüfungsrelevant. Wir werden nur die oben angegebenen Lernziele prüfen. Durch Bearbeitung der wöchentlichen Übungsserien können Sie sich einen Bonus von maximal 0.25 Notenpunkten erarbeiten, den Sie an die Prüfung mitnehmen. Der Bonus ist proportional zur erreichten Punktzahl über alle Serien, wobei volle Punktzahl einem Bonus von 0.25 entspricht. Beispiel: Sie erreichen 60% aller Punkte auf den Übungsserien. Das ergibt einen Notenbonus von 0.15. In der Prüfung selbst erreichen Sie eine Punktzahl, die (vor Rundung) einer Note von 5.05 entspricht. Ihre Gesamtnote (vor Rundung) ist damit 5.20.

Bonuspunktregeln

  1. Abschreiben nicht erlaubt! Wir ermutigen Sie dazu, Aufgaben miteinander zu diskutieren; jede Abgabe muss allerdings die Arbeit eines einzelnen Studierenden sein. Falls wir feststellen, dass zwei oder mehr Studierende die gleiche Lösung (oder Lösungen des Vorjahres) abgegeben haben, geht der Bonus für alle Beteiligten vollständig verloren.
  2. Regeln einhalten! Einige Aufgaben haben besondere Regeln. Aufgabe 1.2 zum Beispiel erlaubt keine Multiplikationen. Abgegebene Lösungen, die diese Regeln verletzen, erhalten keine Punkte. Das automatisch erzielte Ergebnis wird in diesem Fall von Ihrem Assistenten manuell auf Null gesetzt. Eine Regel, die immer gilt, ist, dass nur Sprachkonstrukte erlaubt sind, die in der Vorlesung oder den Übungen besprochen worden sind.
  3. Keine hartcodierten Lösungen! Lösungen, die nicht die gegebene Aufgabe lösen, sondern nur die gegebenen Testfälle, zählen als falsch. Ihr Assistent wird Ihnen die Punktzahl für solche "hartcodierten" Lösungen entsprechend reduzieren.

Arbeitsumgebung

In dieser Vorlesung arbeiten wir mit Code Expert, einer Online-Entwicklungsumgebung. Code Expert unterstützt Sie beim Programmieren, Testen und Abgeben Ihrer Programme an Ihren Übungsleiter. Auf dem Infoblatt zu den Übungen finden Sie eine kurze Anleitung zur Verwendung von Code Expert, und in der ersten Übungsstunde erfolgt eine Einführung durch Ihren Übungsleiter.

Material zur Vorlesung


Datum Themen Folien / Handout C++ Übersicht Übungsserie Lösung Programme Material

Vorlesung 1 (19.09.2017) Informatik: Definition und Geschichte, Algorithmen, Turing-Maschine, Höhere Programmiersprachen, Werkzeuge der Programmierung, das erste C++ Programm und seine syntaktischen und semantischen Bestandteile Infoblatt zu den Übungen
Organisatorisches (Handout, English)
Vorlesung 1 (Handout ,English)
Video-Aufzeichnung
Befehle 1 Serie 1 [html] Lösung 1 [html] [power8.cpp] power8-Animation und Handout zum ersten Programm

Vorlesung 2 (26.09.2016) Auswertung arithmetischer Ausdrücke, Assoziativität und Präzedenz, arithmetische Operatoren, Wertebereich der Typen int, unsigned int Vorlesung 2 (Handout, English)
Video-Aufzeichnung
Befehle 2 Serie 2 [html] Lösung 2 [html] [fahrenheit.cpp]
[limits.cpp]
Zaubertrick
[Flashcard Auswertungsreihenfolgen]
[Flashcard Ausdruckswert]
Selfassessment 1
Lösung
Bewertungsschema
Notenskala

Vorlesung 3 (03.10.2017) Boolesche Funktionen; der Typ bool; logische und relationale Operatoren; Assertions; Auswahlanweisungen, Iterationsanweisungen, Terminierung, Blöcke Vorlesung 3 (Handout, English)
Video-Aufzeichnung
Befehle 3 Serie 3 [html] Lösung 3 [html] [divmod.cpp]
[prime.cpp]
[sum_n.cpp]
Addierer-Animation
[Flashcard XOR]

Vorlesung 4 (10.10.2017) Sichtbarkeit, lokale Variablen, While-, Do- und Sprunganweisung, die Typen float und double, Gemischte Ausdrücke und Konversion, Löcher im Wertebereich Vorlesung 4 (Handout, English)
Video-Aufzeichnung
Befehle 4 Serie 4 [html] Lösung 4 [html] [collatz.cpp],
[euler.cpp],
[diff.cpp]
[Flashcard ForLoop]
[Halteproblem]

Vorlesung 5 (17.10.2017) Fliesskommazahlensysteme; IEEE Standard; Grenzen der Fliesskommaarithmetik; Fliesskomma-Richtlinien; Harmonische Zahlen; Funktionsdefinitionen- und Aufrufe; der Typ void; Vor- und Nachbedingungen Vorlesung 5 (Handout, English)
Video-Aufzeichnung
Befehle 5 Serie 5 [html] Lösung 5 [html] [harmonic.cpp],
[callpow.cpp]
[Flashcard Overhang]

Vorlesung 6 (24.10.2017) Stepwise Refinement, Gültigkeitsbereich, Bibliotheken, Standardfunktionen, Vorschau Referenztypen Vorlesung 6 (Handout, English)
Video-Aufzeichnung
Befehle 6 Serie 6 [html] Lösung 6 [html] [callpow2.cpp],
[prime2.cpp]
[Flashcard Intervallschnitt]
Selfassessment 2
Lösung
Bewertungsschema
Notenskala

Vorlesung 7 (31.10.2017) 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 Vorlesung 7 (Handout, English)
Video-Aufzeichnung
Befehle 7 Serie 7 [html] Lösung 7 [html] [eratosthenes.cpp],
[eratosthenes2.cpp],
[caesar_encrypt.cpp],
[caesar_decrypt.cpp]
[Flashcard Referenzen]

Vorlesung 8 (7.11.2017) Strings, Lindenmayer-Systeme, Mehrdimensionale Felder, Vektoren von Vektoren, Kürzeste Wege, Zeiger Vorlesung 8 (Handout, English)
Video-Aufzeichnung
Befehle 8 Serie 8 [html] Lösung 8 [html] [lindenmayer.cpp],
[bush.cpp]
[snowflake.cpp]
[rainbowflake.cpp]
[dragon.cpp]
[shortest_path.cpp]
[Flashcard Kürzeste Wege]
Lindenmayer-Dateien für Offline-Gebrauch

Vorlesung 9 (14.11.2017) 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 Vorlesung 9 (Handout, English)
Video-Aufzeichnung
Befehle 9 Serie 9 [html] Lösung 8 [html] [fibonacci.cpp],
[fibonacci2.cpp]
[Flashcard Zeiger]

Vorlesung 10 (21.11.2017) Bau eines Taschenrechners, Ströme, BNF, EBNF, Parsen Vorlesung 10 (Handout, English)
Video-Aufzeichnung
Befehle 10 Serie 10 [html] Lösung 10 [html] [checksum.cpp],
[calculator.cpp],
[simple_calculator_l.cpp],
[simple_calculator_r.cpp],
[calculator_r.cpp],
[calculator_l.cpp]
[Flashcard Rekursion]

Vorlesung 11 (28.11.2017) Rationale Zahlen, Struct-Definition, Operator-Überladung, Const-Referenzen, Datenkapselung, Klassen-Typen Vorlesung 11 (Handout, English)
Video-Aufzeichnung
Befehle 11 Serie 11 [html] [rational_init.cpp],
[rational_with_operators.cpp]
[Flashcard Eisenbahn] Selfassessment 3
Lösung mit Bewertungsschema
Notenskala

Vorlesung 12 (5.12.2017) Memberfunktionen, Konstruktoren, verkettete Liste, Stapel, dynamischer Speicher, Kopierkonstruktor, Zuweisungsoperator, Destruktor, Konzept Dynamischer Datentyp Vorlesung 12 (Handout, English)
Video-Aufzeichnung
Befehle 12 Serie 12 [html] [rationals_with_classes.cpp],
[stack_test.cpp],
[stack_example.cpp]
[Flashcard Konstruktoren]

Vorlesung 13 (12.12.2017) Ausdrucksbäume, Vererbung, Code-Wiederverwendung, virtuelle Funktionen, Polymorphie, Konzepte des objektorientierten Programmierens Vorlesung 13 (Handout, English)
Video-Aufzeichnung
Befehle 13 Serie 13 [html] (nicht bonus- und prüfungsrelevant, keine manuelle Korrektur) [texpression_test.cpp],
[texpression_calculator.cpp],
[double_calculator.cpp],
[xexpression_test.cpp]
[Flashcard Konstruktoren II]

Vorlesung 14 (19.12.2017) Inhaltlicher Rückblick mit Beispielprogrammen Vorlesung 14
Video-Aufzeichnung
[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] Selfassessment 4
und Lösung mit Bewertungsschema
Notenskala
Zusatzaufgaben und Lösung


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

Literatur und Links