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

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

Prüfungseinsicht

Die Prüfungen der Sommersession 2012 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.

Ankündigung

Die Bilder zur Lindenmayer Challenge sind da. Es gibt auch ein kleines Video dazu.
Am SOI Tag (Swiss Olympiad in Informatics) am 14. Januar 2012 hält Prof. Dr. Donald Knuth, einer der berühmtesten Informatiker unserer Zeit, einen Vortrag mit dem Titel "All Questions Answered", in dem er auf Fragen aus dem Publikum eingehen wird. Wir können ihnen diese Veranstaltung nur wärmstens empfehlen.
Um die Funktion to_double von IFM/integer zu verwenden brauchen Sie ein neues Makefile. Weitere Infos auf der Virtual Box Seite und in der Übungsstunde.

Vorlesungsunterlagen

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.

Die drei Vorlesungen, die Hromkovic hält, behandeln einige theoretischen Aspekte der Informatik. Beachten Sie, dass es hier keine Vorlesungsfolien geben wird, jedoch ebenfalls vorausgesetzt wird, dass alles was in der Vorlesung besprochen wurde, an der Prüfung behandelt werden kann. Es wird auch für diesen Teil einige Texte geben, die den Inhalt der Vorlesung vertiefen.

Material

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

#1 (20.09.2010) Algorithmus, Programm, Registermaschine Kapitel 2 [PDF] (Sieben Wunder der Informatik), Zusammenfassung Registermaschine [PDF]

#2 (27.09.2010) Unendlichkeit,
Berechenbarkeit
Kapitel 3 [PDF] (Sieben Wunder der Informatik) Serie 1 [PDF] Lösung 1 [PDF]

#3 (4.10.2010) C++: Identifiers, Ausdrücke,
Variablen, Literale,
Operatoren, erstes Programm
Folien zu den Abschnitten 1.1 bis 2.1 im Skript [pdf zum Drucken] [pdf zum Ansehen] [pptx],
Ein Artikel aus der Anfangszeit der höheren Programmiersprachen
Serie 2 [PDF] Lösung 2 [PDF] [hello_world.cpp], [power8.cpp], [power8_exact.cpp]

#4 (11.10.2010) Integers, Booleans, Auswertungsreihenfolge Folien zu den Abschnitten 2.2 bis 2.3 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 3 [PDF] Lösungen zu Abschnitt 2.1 [PDF],
Lösungen zu Abschnitt 2.2 [PDF]
Lösungen zu Abschnitt 2.3 [PDF]
[fahrenheit.cpp] [limits.cpp]

#5 (18.10.2010) Reduktionen, Randomisierte Algorithmen Kapitel 4 [PDF] (Sieben Wunder der Informatik) Serie 4 [PDF] Lösung 4 [PDF]

#6 (25.10.2010) Kontrollanweisungen Folien zum Abschnitt 2.4 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 5 [PDF] Lösungen zu Abschnitt 2.4 [PDF] [collatz.cpp] [prime.cpp] [scope.cpp] [sum_n.cpp]

#7 (1.11.2010) Fliesskommazahlen Folien zum Abschnitt 2.5 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 6 [PDF] Lösungen zu Abschnitt 2.5 [PDF] [euler.cpp] [diff.cpp] [harmonic.cpp] [onepixel.cpp]

#8 (8.11.2010) Felder und Zeiger (I) Folien zum Abschnitt 2.6 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 7 [PDF] [read_array.cpp] [eratosthenes.cpp] [eratosthenes2.cpp]

#9 (15.11.2010) Felder und Zeiger (II) Folien zum Abschnitt 2.6 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 8 [PDF] Challenge Sprachenerkennung [PDF] [PPT] Lösung 8 [PDF], Lösungen zu Abschnitt 2.6 [PDF],
Video Pfadfinder Aufgabe
[string_matching.cpp] [string_matching2.cpp] [shortest_path.cpp]
Input data

#10 (22.11.2010) Funktionen Folien zum Abschnitt 3.1 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 9 [PDF] Lösungen zu Abschnitt 3.1 [PDF] [callpow.cpp] [prime2.cpp]

#11 (29.11.2010) Rekursion (I) Folien zum Abschnitt 3.2 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 10 [PDF] [fak-1.cpp] [fibonacci.cpp] [fibonacci2.cpp] [ackermann.cpp] [merge_sort.cpp] [minimum_sort.cpp]

#12 (6.12.2010) Rekursion (II)
Structs
Referenztypen
Operator-Überladung
Folien zum Abschnitt 3.2, 4.1 und 4.2 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 11 [PDF] Lösungen zu Abschnitt 3.2 [PDF], Lösungen zu Abschnitt 4.1 [PDF] [dragon.cpp] [lindenmayer.cpp] [snowflake.cpp] [bush.cpp] [rational.cpp] [userational.cpp] [userational2.cpp]

#13 (13.12.2010) Referenzen (const),
Klassen (I),
Zufallszahlen
Folien zum Abschnitt 4.2 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Serie 12 [PDF] Lösungen zu Abschnitt 4.2 [PDF] [clock.cpp] [random.h] [random.cpp] [random_pi.cpp] [loaded_dice.h] [loaded_dice.cpp] [choosing_numbers.cpp]

#14 (20.12.2010) Klassen (II) Folien zum Abschnitt 4.3 im Skript [pdf zum Drucken] [pdf zum Ansehen] [ppt] Lösungen zu Abschnitt 4.3 [PDF]

Merkblatt zur Vorlesung [PDF]

Wichtige Unix Kommandos [PDF] [PS]

Termine

Vorlesung: Dienstag 13:15-15:00, HG F1
Bernd Gärtner, CAB G31.1, Tel: 044 632 70 26, .
Juraj Hromkovic, CAB F16, Tel: 044 632 44 08 .
Übung: Dienstag 15:15-17:00
Yves Brise, CAB G19.3, Tel: 044 44 632 77 96, .
Gruppe A,Dienstag 15:15-17:00,CAB G56,Martin Jaggi.
Gruppe B,Dienstag 15:15-17:00,CHN D44,Andrea Arteaga.
Gruppe C,Dienstag 15:15-17:00,CHN D48,Stefan Pauli.
Gruppe D,Dienstag 15:15-17:00,CHN E42,Dimitar Asenov.
Gruppe E,Dienstag 15:15-17:00,CHN G22,Maria Christakis (english).
Gruppe F,Dienstag 15:15-17:00,ETZ H91, Gian-Peder Fasser.
Gruppe G,Dienstag 15:15-17:00,ETZ K91,Daniel Tschudi.
Gruppe H,Dienstag 15:15-17:00,HG D1.2,Simone Frau (italiano).
Gruppe I,Dienstag 15:15-17:00,HG D3.1,Valentina de Rosa (english).
Gruppe J,Dienstag 15:15-17:00,HG D3.3,Benjamin Schindler.
Gruppe K,Dienstag 15:15-17:00,HG F26.3,Lukas Huthmacher.
Gruppe L,Dienstag 15:15-17:00,HG F26.5,Christian Müller.
Gruppe M,Dienstag 15:15-17:00,IFW A34,Florian Andritsch.
Gruppe N,Dienstag 15:15-17:00,IFW B42,Florian Negele.
Gruppe O,Dienstag 15:15-17:00,IFW D42,Markus Roos.
Gruppe P,Dienstag 15:15-17:00,LFW E11, Milos Novacek (english).
Gruppe Q,Dienstag 15:15-17:00,LFW E13,Endri Dibra.
Gruppe R,Dienstag 15:15-17:00,ML J37.1,Thomas Scholtes.
Gruppe S,Dienstag 15:15-17:00,NO E39,Malte Schwerhoff.

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. Des weiteren geben wir einen Einblick in die Geschichte der Informatik und einige ihrer wichtigen theoretischen Grundlagen.

Arbeitsumgebung

Einer der Assistenten, Andrea Arteaga, hat einen Emulator für Registermaschinen-Programme geschrieben, wie wir sie in der Vorlesung verwenden. Der Emulator sollte alle Befehle, die wir in der Vorlesung behandeln, verstehen, aber es handelt sich noch um eine beta Version. Das heisst, vor allem wenn ein ungültiges Programm eingegeben wird, sind die Resultate manchmal nicht absehbar. Wir ermutigen Sie, Ihre Programme darauf zu testen, möchten aber gleichzeitig erwähnen, dass wir keine Garantien für Korrektheit abgeben. Weitere Informationen finden sie auf der Seite unter Dokumentation. Für den Rest der Vorlesung arbeiten wir mit einem Unix System wie es in der Form von Linux in den ETH Computerräumen installiert ist. Es stehen etliche öffentliche Rechner in verschiedenen Räumen zur Verfügung. Eine komplette Liste gibt es hier. Bei Zugangsproblemen, die Sie nicht mir ihrem Übungsleiter zusammen lösen können, kontaktieren Sie bitte die Informatikdienste der ETH (Telefon intern 27777). Die meisten der PCs sind dualboot Windows/Linux. Das heisst Sie müssen zuerst Linux starten, falls Sie mit einem Windows Login Fenster begrüsst werden. Informationen dazu gibt es hier.

Wenn vorhanden, können natürlich auch private Rechner benutzt werden. Wer mit dem Gedanken spielt, sich ein eigenes Notebook anzuschaffen, der sollte einen Blick auf die Neptun Angebote werfen. Für die privaten Rechner verwenden wir in diesem Semester eine Linux openSUSE Installation, die auf allen gängigen Betriebssystemen über eine sogenannte VirtualBox von uns zur Verfügung gestellt wird.

Unabhängig davon, ob Sie auf einem öffentlichen oder privaten Rechner arbeiten, muss man den Rechner für den Einsatz in der Vorlesung konfigurieren. Einzig in der VirtualBox Distribution sind alle Einstellungen schon integriert. Lesen Sie dazu die Anleitung für Linux.

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.

Lindenmayer Challenge

Seht euch die Liste der eingereichten Abgaben an. Es gibt auch ein kleines Video dazu.

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 insgesamt 16 Punkte vergeben werden. Zusätzlich enthalten die meisten Serien Challenge-Aufgaben, aus denen jeweils 8 Punkte erzielt werden können. Insgesamt wird es 12 Übungsserien geben.

Um das Testat zu erhalten, müssen Sie 50% der regulären Punkte aus allen Übungsserien erlangen. Bei 12 Übungsserien werden das voraussichtlich 96 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 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 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: , by Yves Brise. Valid HTML 4.0! Valid CSS!