Research
- Algorithms, data structures, and applications
- Information Technology and Education
- Heuristics, Exhaustive Search and Games
Algorithms, data structures, and applications[ Picture: Searching for near-optimal placement and modulation of beams in radiotherapy ] The technical focus of our research on algorithms and data structures clusters around the areas of geometry, combinatorics and search [N00, NW99]. We look for compute-intensive applications where these techniques can be brought to bear, and seek cooperation with application experts. Examples of technical results are the program library ZRAM, which automatically parallelizes search algorithms [BAFN99], and combinatorial-geometric algorithms designed to use it [NDM99, AN01]. Recent and current applications of geometric search algorithms include finding dense packings of polymers [MNSS, SSMN01] and finding radiotherapy treatment plans that irradiate a given target with a desired dose while damaging surrounding healthy tissue as little as possible (B. Haas, doctoral research in progress jointly with the University Hospital Bern). Ph.D theses:
Currently in progress: Benjamin Haas: Automatic field setup for external beam radiotherapy. |  Searching for near-optimal placement and modulation of beams in radiotherapy |
Information Technology and EducationThe impact of information and communication technology (ICT) on education is only just beginning to be felt. The technology forces that affect the future of education are of two kinds. First and foremost, there is a strong demand for information and communication technology to become a part of general education [N99]: to be learned, in appropriate dosage, by practically anybody, at all stages of the educational life line, from elementary school to life long learning. Second, there is the use of this technology as a delivery tool to present information anytime, anywhere via portable interactive multi-media devices, and to enhance the learning process thanks to a quality of interaction unequaled by any previous educational technology. The Ph.D project of Raimond Reichert addresses the design, use and evaluation of educational programming environments based on the simple concept of finite state machines, such as the toy robot Kara [RNH00, HNR01]. Vincent Tscherter is developing interactive learning components that automatically generate exercises in the theory of computation and provide step-by-step feedback. Werner Hartmann, Director of Teacher Education, leads the team that created EducETH, the collection of web-based educational materials that is widely used in schools at various levels. |  LegoKara - A toy robot programmed as a finite state machine. |
Heuristics, Exhaustive Search and GamesPuzzles and games provide challenging benchmarks for the effectiveness of heuristic and exhaustive search techniques. Ralph Gasser showed that the game of Merrils (Mühle) is a draw. Adrian Bruengger solved Sam Loyd's "15-puzzle" (order 15 sliding tiles inside a 4 by 4 matrix) by showing that the hardest initial configuration is 80 moves away from the target. Thomas Lincke's program was the Awari champion at the Fifth Computer Olympiad, London 2000. [WJ99, TM00, L01, M01] Ph.D theses:
|