Triple Inaugural lectures

Department of Computer Science hereby invites everyone interested to three inaugural lectures on the occasion of the appointment of Peter Bro Miltersen, Michael Schwartzbach and Morten Kyng to the position of professors - each in his own special field of research.

Abstract Morgen Kyng

Making it pervasive: computing, healthcare and user innovation 

Computing is undergoing fundamental changes as computation literally moves out of the box and begins to pervade our environment. Visions of (almost) almighty, intelligent agents taking care of our needs even before we know we have them are abundant. But current reality is somewhat different and just figuring out how to print or synchronize data on a mobile phone is often a problem. We will look at some of the challenges in developing useful applications, services and systems based on pervasive computing and illustrate these with examples from the healthcare area. What about physical/digital integration? What happens with interaction styles? What happens when systems cross organizational borders and integrate work and daily life? How may we organize innovative development processes? Answers are only beginning to emerge, but they point to a future where computing pervade our environment in useful, learnable and enjoyable ways.

Abstract Michael Schwartzbach

Deciding the Undecidable

A fundamental intellectual achievement in Computer Science, dating back to the 1930s, is the observation that that there is a universal notion of computability and that some problems are actually uncomputable. This is not merely a philosophical curiosity, but a concrete problem for the design and implementation of programming languages, since it turns out that every interesting question about the behavior of programs is undecidable in the sense of its answers being uncomputable. This includes questions about the correctness of programs, their running times, their resource consumptions, and the applicability of most optimizations. Fortunately, for practical purposes it is often sufficient to obtain conservative and approximate answers to these questions. The efficient computation of useful answers is the challenge that has given rise to the research area of static program analysis, which has an established mathematical basis but also a strong engineering flavor for real-life languages and questions. We present the foundations of static analysis and give examples of recent projects that use these techniques to combat undecidability.

Abstract Peter Bro Miltersen

Names In Boxes and Dante in Purgatory

We investigate two puzzles with a "recreational mathematics" flavour.

The first one ("Names In Boxes") originates in joint work with Anna Gal from 2003. The second one ("Dante in Purgatory") originates in very recent joint work with Kristoffer Arnsfelt Hansen and Michal Koucky. We solve the puzzles and explain their connection to deep unresolved problems of mathematical computer science.

Names in Boxes:
The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. The prisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it.

Dante in Purgatory:
There are seven terraces in Purgatory, indexed one to seven. Dante enters Purgatory at terrace one.

Each day, if Dante finds himself at some terrace i, he must play a game of matching pennies against Lucifer:

Lucifer hides a penny, and Dante must try to guess if it is heads up or tails up. If Dante guesses correctly, he proceeds to terrace i + 1 the next morning - if i + 1 is eight, he enters Paradise and the game ends. If, on the other hand, Dante guesses incorrectly, there are two cases. If he incorrectly guesses “heads”, he goes back to terrace one the next morning. If he incorrectly guesses “tails” the game ends and Dante forever loses the opportunity of visiting Paradise.

How can Dante ensure ending up in Paradise with probability at least 75 percent? How long should he expect to stay in Purgatory before the game ends in order to achieve this?