courses in Berlin
| Winter 2002/03 |
|
other semesters
courses in Berlin |
|
Pre-Doc Courses
RandAlgs Randomized Algorithms
ApproxAlgs Approximation: Theory and Algorithms
GeomMod Surface Representations and Geometric Modeling
The course topics presented will include:
PosGames Positional Games and Algorithms
The list of the subjects that we are going to cover is (1)
Tic-Tac-Toe-like games, Ramsey games, game-graph and game-tree,
pairing strategy, potential functions, (2) Game-theoretic first moment
method, (3) Game-theoretic second moment method, (4) Graph games and
random graphs, (5) Tic-Tac-Toe in higher dimensions, (6) Algorithmic
and game-theoretic Lovasz Local Lemma, complexity problems.
Prerequisites: Almost nothing -- it is a self-contained course, but
a knowledge of the simplest concepts of combinatorics,
and reasonable problem-solving skills are expected.
No textbook is available: I am going to give hand-outs
and problem-sheets.
CompVis Selected Topics in Computer Vision
Graph Theory
Algorithmen für Kommunikationsnetze (in German)
WEB Algorithms
We discuss recent advances in this new research area that highlights
links between different research topics such as Game Theory, Economy,
Web Research, and Theoretical Computer Science. One of the goals of this
course is to provide different perspectives for a problem. Towards this
end we will consider routing, networking, and graphs problems in
different settings. For instance:
Online algorithms capture the lack of performance due to uncertainty
about the future: e.g. we need to decide how to route a stream of
packets without knowledge of future routing requests.
Algorithms for selfish agents study how to design a protocol in the case
where agents that implement the protocol may follow their own interests,
and tune the parameters of the protocol for their own benefit: e.g. what
happens if a selfish Internet user increases her TCP window size to get
more throughput?
*Remark: In this announcement we use a generic term "Web" for all layers
of the Internet: From basic router protocols to applications such as the
World Wide Web.
Other semesters
Winter 2000/01
,
Summer 2001
,
Winter 2001/02
,
Summer 2002
E. Welzl, B. Gärtner, U. Wagner
(Mo&Tu, Oct 21 - Nov 22, 2002)
Randomized algorithms have by now emerged into many fields, and have
lead to several improvements and simplifications compared to
deterministic methods. We will discuss applications in several areas,
including optimization, approximate counting and solving of hard
problems (e.g. SAT). The emphasis will be on understanding of the
basic methods, so that they can be applied in several situations.
J. Blömer, M. Cochand, T. Erlebach, B. Gärtner, A. Steger, P. Widmayer
(Th&Fr, Oct 21 - Nov 22, 2002)
This course is concerned with approximation algorithms for NP-hard
optimization problems. The topics covered include: basic and advanced
approximation algorithms for selected problems; more general
techniques such as linear programming relaxation and derandomization;
inapproximability and the PCP concept.
M. Gross
(Mo&Tu, Jan 6 - Feb 7, 2003)
Recent advances in 3D digital geometry processing have created a
plenitude of novel concepts for the mathematical representation and
interactive manipulation of graphics models. This course covers some
of the latest developments in geometric modelling and surface
representations. The first part of the course will revisit traditional
methods, such as splines and NURBS, and will introduce the basic
notions of differential geometry. The second part of the course will
address more recent developments in geometry processing including
subdivision, smoothing, geometric filtering, and wavelets.
J. Beck (Rutgers University, USA)
(Th&Fr, Jan 6 - Feb 7, 2003)
In the last few years I keep writing a book entitled `positional
games', which would be the first book on the subject. `Positional
games' is completely different from both the traditional Neumann-type
``game theory" and the Berlekamp-Conway-Guy type ``Nim-like games"
(see the well-known 2-volumed `Winning Ways' of the three authors).
Positional games' is about `Tic-Tac-Toe-like' board games, and is
closely related to Ramsey theory, Matching theory and the
Erdös-type ``probabilistic method" (see the well-known book of
Alon-Spencer). The winning and drawing strategies are effective
potential function algorithms: this explains the word `algorithms' in
the title. This is a brand new subject which is full of exciting open
problems.
L. van Gool, B. Schiele, G. Székely
(Th&Fr, Jan 6 - Feb 7, 2003)
The class covers various fundamental as well as advanced techniques in
computer vision. A particular emphasis is on visual object recognition
using different approaches. Two alternative schools are described and
compared: appearance vs. model based. These are complemented with
novel, hybrid solutions, built upon invariance theory. A second
emphasis is on techniques to characterize object shape and binary
scenes. Basic concepts of topology and metrics on discrete image
rasters are investigated. Time permitting, several learning techniques
in the context of visual recognition are discussed.
Other Courses related to CGC
T. Szabó
(We 13-15, IFW B42 [Exercises: We 15-16, IFW B42])
This course is an introduction to the theory of graphs intended for
students in mathematics and computer science/engineering students with
an interest in theory. We start from basic definitions and examples,
but hope to move on quickly and cover a broad range of topics. Some
applications and relations to Computer Science will also be
discussed. Emphasis will be given to reading, understanding and
developing proofs. There is no prerequisite, other than basic
mathematics introduced in the Grundstudium. Possible topics include:
degrees, paths, trees, cycles, Eulerian circuits, bipartite graphs,
extremality, matchings, connectivity, network flows, vertex and edge
colorings, Hamiltonian cycles and planarity.
T. Erlebach
(Mo 10-12, ETZ F91 [Exercises: We 15-17, ETZ F91])
Der Kurs stellt Techniken für den Entwurf und die Analyse von
Algorithmen vor, die insbesondere für Anwendungen in
Kommunikationsnetzen nützlich sind. Behandelt werden
Grundlagen zu Algorithmen und Graphen (Spannbäume, kürzeste
Pfade, Flussprobleme), effiziente Algorithmen für optimal
lösbare Probleme (Multicast in WDM-Netzen, Min-Cut-Berechnung,
Ausfallsicherung von Netzen), effiziente Datenstrukturen (IP
Prefix Lookup), Approximationsalgorithmen für
Netzwerkoptimierungsprobleme (Spanner, Lastbalancierung in Ringen,
Wellenlängenzuteilung in WDM-Netzen) und Online-Algorithmen,
die trotz fehlenden Wissens über die Zukunft beweisbar gute
Entscheidungen treffen (Zugangskontrolle in QoS-Netzen).
P.Penna, K. Schlude, R. Wattenhofer, P. Widmayer
(We 13-15, IFW A32 [Exercises: We 15-16, IFW A34])
The goal of the course is to understand the main algorithmic issues and
techniques related to the Web*. Traditionally an "algorithm" is a
computational procedure that takes an input and produces an output. A
"Web algorithm" is different because the Web is distributed and
dynamically changing. More importantly, not all entities in the Web
cooperate; some act selfishly and spontaneously. How much performance is
lost because of this? And what can we do about it? To answer these
questions, we need a theoretical model for the Web that describes how
the participating entities interact and react to a changing situation.
| Last modified on 2003-04-25 18:13:23 by Falk Tschirschnitz <tschirsc@inf.ethz.ch> |
Copyright © 2000-2001 
|