Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | preliminary term schedule | history
predoc-courses | schools | block-courses | workshops

Block Course

  Block Course on 
  within the
  Research Training Group (Graduiertenkolleg)
        Methods for Discrete Structures
  Institute for Computer Science, Free University of Berlin
  25.03.2008 - 04.04.2008
    Helmut Alt and Christian Knauer,
	 possibly guest speakers 
    Lecture in the morning, 9 - 12
    Problem solving in small groups in the afternoon
    discussion of the solutions: 17-18
  - basics of computational geometry and complexity theory
  - "easily solvable" geometric problems
  - NP-hard geometric problems (e.g., packing and covering problems,
    Euclidean shortest paths in 3 dimensions, minimum weight triangulation,
    FrÈchet distance of surfaces)
  - approximation algorithms, fixed parameter tractability, realistic inputs
  - PSPACE-hard geometric problems (e.g., robot motion planning, linkage

- PSPACE - decidability of the 1st order theory of the reals with applications - undecidable geometric problems The language of the course is English. Organizers: The course is offered by the Research Training Group (Graduiertenkolleg) "Methods for Discrete Structures" of the Free University, the Humboldt University and the Technical University in Berlin, and is organized by Helmut Alt, Christian Knauer, and Tamara Knoll at the Free University of Berlin. Location: The course will be hosted by the Computer Science Department of the Free University of Berlin. Audience: This is a two week block course for graduate students (on the PhD and the master level) working in Discrete Mathematics or in Computer Science (in a broad sense). Participants are expected to have basic knowledge in geometry, discrete mathematics, and algorithms and complexity. The course is free of charge. Registration: Participants are asked to register via email with Christian Knauer