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

Informatik für Mathematiker und Physiker (251-0847-00) WS04/05

Termine

Vorlesung: Dienstag 13:15-15:00, HG F1.
Bernd Gärtner, IFW B45.1, Tel: 01-632 70 26, .
Übung:
Michael Hoffmann, IFW B47.2, Tel: 01-632 73 90, .
Gruppe A,Dienstag 15:15-17:00,LFW E13,Jörg Derungs.
Gruppe B,Dienstag 15:15-17:00,HG D5.3,Leo Ruest.
Gruppe C,Dienstag 15:15-17:00,HG E1.2,Gábor Szabó, (in English).
Gruppe D,Dienstag 15:15-17:00,HG F26.1,Michael Gatto.
Gruppe E,Dienstag 15:15-17:00,HG F26.3,Uche Mennel.
Gruppe F,Dienstag 15:15-17:00,HG F26.5,Thomas Bruderer.
Gruppe G,Dienstag 15:15-17:00,LEC C14,Sarah Gugl.
Gruppe H,Dienstag 15:15-17:00,ML D13,Matthias Schrag.
Gruppe I,Donnerstag 15:15-17:00,ETZ J91,Reto Ghioldi.
Gruppe J,Freitag 15:15-17:00,HG D3.1,Alexander Hall.
Gruppe K,Freitag 15:15-17:00,ML J37.1,Markus Deluigi.

Inhalt

Das Ziel der Vorlesung ist eine algorithmisch orientierte Einführung ins Programmieren. Anhand der Sprache C++ werden zunächst die Elemente des prozeduralen Programmierens eingeführt, also Variable, Zuweisung, bedingte Anweisung, Schleife, Prozedur, Feld, Verbund und Zeiger. Dynamische Datenstrukturen werden an den Beispielen lineare Listen und Bäume studiert. Einige wichtige Algorithmen zum Suchen und Sortieren werden erklärt und bezüglich Korrektheit und Laufzeit- und Speicher-Effizienz analysiert. In einem zweiten Teil werden dann die weiteren Möglichkeiten von C++ ausgelotet, was auf die Konzepte des objektorientierten und des generischen Programmierens führt.

Arbeitsumgebung

Für die Programmieraufgaben stehen die Rechner im HG D13 (13 Linux-Workstations), HG E19 (34 Sun-Workstations) sowie HG E26.1 (36 Sun-Workstations) zur Verfügung. Wo vorhanden, können natürlich auch eigene Rechner benutzt werden. Wer mit dem Gedanken spielt, sich ein eigenes Notebook anzuschaffen, der sollte einen Blick auf die Neptun Angebote werfen. Wir arbeiten mit einer Unix Umgebung. Unter MS Windows kann man eine solche Umgebung sehr einfach mittels cygwin emulieren. Weiter unten findet man eine Kurzanleitung zur Installation von cygwin.

Hinweise zur Übung

Auf jeder Übungsserie gibt es mehrere Aufgaben, die schriftlich zu bearbeiten und zum angegebenen Termin - meist in der Woche darauf - abzugeben sind. Gruppenabgabe wie auch das Einreichen identischer Lösungen sind nicht zulässig.

Testatbedingungen

Am Ende der Übungen wird ein Testat vergeben. Das Testat erhält, wer
  1. sowohl auf den ersten sechs als auch auf den folgenden - wahrscheinlich ebenfalls sechs - Übungsserien jeweils mindestens 60% der möglichen Punkte erreicht, sowie
  2. mindestens die Hälfte der Schnellübungen sinnvoll bearbeitet.

Prüfung

Die Prüfung besteht aus einer zweistündigen Klausur. Bedingung für die Zulassung zur Prüfung ist das Übungstestat. Es sind folgende Hilfsmittel erlaubt: maximal zwei handgeschriebene DIN A4 Blätter (beidseitig beschrieben, also max. vier A4 Seiten). Als Anhaltspunkt dafür, wie die schriftliche Prüfung ungefähr aussehen könnte: die Klausur, welche die Repetenten im März geschrieben haben.

NEU!

Die Musterlösung für obige Testklausur.

Schnellübungen

Auf einigen Übungsserien wird die erste Aufgabe aus einer Schnellübung bestehen. Diese Aufgaben sind in den ersten x (typischerweise x = 20) Minuten der Übungsstunde zu bearbeiten und werden dann vom Übungsleiter eingesammelt. Es versteht sich, dass hierfür die Anwesenheit in der Übungsstunde erforderlich ist, eine nachträgliche Abgabe ist nicht möglich. Schnellübungen werden in der Regel eine Woche vorher angekündigt.

Literatur

  • Skript (Draft) zur Vorlesung. [PDF][PS]
  • NEU! Neue Skriptversion (einige Fehler beseitigt, 1.Juli 2005). [PDF][PS]
  • Errata zur neuen Skriptversion
  • Andrew Koenig and Barbara E. Moo: Accelerated C++, Addison-Wesley, 2000.
  • Stanley B. Lippman: C++ Primer, 3. Auflage, Addison-Wesley, 1998.
  • Bjarne Stroustrup: The C++ Programming Language, 3. Auflage, Addison-Wesley, 1997.

Material


Datum Themen Folien Übungsserie Programme

#1 (19.10.2004) Grundlagen, elementare arithmetische Operationen [PDF][PS] [PDF][PS] prime.C, prog1.C, prog2.C, prog3.C, summe.C, absurd.C.

#2 (26.10.2004) Schleife, bedingte Anweisung, Priorität und Assoziativität arithmetischer Operationen - [PDF][PS] fahrenheit.C, binaer.C, random.C.

#3 (2.11.2004) Fliesskommazahlen: Darstellung und Konversionen - [PDF][PS] muenzwurf.C, harakiri.C, subtract.C.

#4 (9.11.2004) Rechnen mit Fliesskommazahlen, Zusammenfassung Kontrollstrukturen, Blöcke und Sichtbarkeit, boolesche Ausdrücke - [PDF][PS] convert.C, harmonic.C, bigsmall.C, one.C.

#5 (16.11.2004) Prozedurale Abstraktion (Funktionen) - [PDF][PS] math.h, math.C, prime.C, libifm-1.17.tar.gz.

#6 (23.11.2004) Rekursion, Strings - [PDF][PS] math.C, fib.h, ggt.h, ackermann.h, login.h, code.C.

#7 (30.11.2004) Call by reference, reguläre Ausdrücke - [PDF][PS] mac2unix.C, mac2unix-index.C, mac2unix-iterator.C, linecount.C, freude.txt.

#8 (7.12.2004) Iteratoren, Kontextfreie Grammatiken - [PDF][PS] brackets.C, calc-simple.C.

#9 (14.12.2004) Vektoren - [PDF][PS] eratosthenes.C, eratosthenes-it.C, minsort.C.

#10 (21.12.2004) Sortieren: Bubblesort und Quicksort - [PDF][PS] quicksort.C, bubblesort.h.

#11 (11.01.2005) Name lookup, Überladen von Funktionen, Abstrakte Datentypen (Einführung) - [PDF][PS] rational.C.

#12 (18.01.2005) Klassen - [PDF][PS] rational.h.

#13 (25.01.2005) Dynamische Speicherverwaltung, Listen - [PDF][PS] list.h (erste Version).

#14 (01.02.2005) Iteratoren für Listen - - - list.h.

Dokumentation der libifm [HTML] [PS] [PDF]
(Postscript-Ausgabe für libturtle: Ersetze src/turtle.C durch turtle_ps.C.)

Merkblatt zur Vorlesung [PS] [PDF]

Wichtige Unix Kommandos [PS] [PDF]

Cygwin

Cygwin ist eine Unix-artige Umgebung für MS Windows. Eine kurze Installationsanleitung findet man hier.

Eine cygwin shell öffnet man durch Doppelclick auf das schwarz-grüne cygwin icon. In dieser shell kann man mittels des Kommandos startx einen X-server und ein zugehöriges Terminal starten. So ein Terminal ist unsere bevorzugte Arbeitsumgebung, von wo aus man z.B. den emacs, den compiler g++ und die erstellten ausführbaren Programme aufruft.

Emacs

Den file .emacs solltet Ihr in Euer Heimatverzeichnis kopieren. (Diese neue Version vom 25.10.2004 behebt die Probleme mit dem Compiler auf den Solaris Maschinen.)

Unter Cygwin ist das Heimatverzeichnis im Verzeichnisbaum unterhalb des bei der Installation angegebenen cygwin Wurzelverzeichnisses zu finden, z.B. als c:\cygwin\home\myname.

Wem die Schriftgrösse zu klein ist: Shift-Taste drücken und mit der linken Maustaste in das Emacs Fenster klicken. Es erscheint ein Menu zu Schriftart und -grösse.

OS-X

Mac OS 10 Benutzer sollten die Developer CD installieren, insbesondere auch das Paket X11. Eine grosse Auswahl von open source software packages wie z.B. emacs kann sehr bequem via fink installiert werden. Marcus Deluigi (Übungsleiter der Gruppe K) ist im Falle von Fragen oder Problemen auf dieser Plattform der geeignete Ansprechpartner.

Last modified: $Date: 2005/10/10 14:45:09 $ by Michael Hoffmann. Valid HTML 4.0! Valid CSS!