### Ver Post

## Talk by Prof. Kurt Mehlhorn_Max Planck Institute for Informatics

6 Outubro 2017, 16:48 - Maria Lucília Gonçalves Abreu

**Title:** Certifying
Computations: Algorithmics meets Software Engineering

**Speaker: **Prof. Kurt
Mehlhorn_Max Planck Institute for Informatics

**Date:** October 23th
2017

**Time: **10:30a.m.

**Location: **Anfiteatro PA3_Pavilhão de Matemática_Campus
Alameda

**Abstract**

I am mostly interested in algorithms for difficult combinatorial and
geometric problems: What is the fastest tour from A to B? How to optimally assign jobs to machines?
How can a robot move from one location to another one? Algorithms solving such
problems are complex and their implementation is error-prone. How can we make
sure that our implementations of such algorithms are reliable? Certifying
algorithms are a viable approach towards the goal. The top part of the figure
above illustrates the I/O behavior of a conventional program for computing a
function f . The user feeds an input x to the program and the program returns
an output y. Why should the user believe that y is equal to f (x)? A certifying
algorithm for f computes y and a witness (proof) w; w proves that the algorithm
has not erred for this particular input. The certifying algorithms is
accompanied by a checker program C. It accepts the triple (x;y;w) if and only
if w is a valid witness for the equality y = f (x). Certifying algorithms are
the design principle for LEDA, the library of efficient data types and
algorithms ([MN99]). In the first part of the talk, we introduce the concept of
certifying algorithms and discuss its significance.. In the second part of the
talk, we survey certifying algorithms ([MMNS11]). In the third part of the
talk, we discuss the formal verification of certifying computations ([ABMR14,
NRM14]).

**Bio**

Kurt Mehlhorn heads the department “Algorithms and Complexity” at the
Max Planck Institute for Informatics in Saarbrücken. He is author or co-author
of approx. 300 research papers and has published six books. 80 of his former
students now hold professorships. Mehlhorn has been awarded a number of
prestigious research prizes. These include the Leibniz Prize of the German
Research Foundation in 1986 and the Konrad Zuse Medal in 1995. He was Vice
President of the Max Planck Society from 2002 to 2008. In 2014, he celebrated
his 30th anniversary as a university teacher. He is a member of the Leopoldina,
the National Academy of Sciences, of acatech, the National Academy of Science
and Engineering, the Academia Europaea, and the Indian National Academy of
Engineering. Last year, members of the US National Academy of Science appointed
him as a “Foreign Associate” in their ranks. He is the second European computer
scientist to be honored this way. In 1995 he co-founded the Algorithmic
Solution Software GmbH.

More information here.