Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
November 19 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
How to compute fast search strategies
- Speaker:
Tobias Jacobs (National Institute of Informatics)
- Abstract:
Consider the following search problem: Given a collection of entities
and a set of tests, one wants to identify a certain entity using tests
from the set. As an example, the entities might be diseases, and the
tests might be symptoms like body temperature, headache, etc. An
adaptive search strategy is a way to determine the next test to apply,
based on the outcomes of the previous tests. The goal is to apply as few
tests as possible.
This talk begins with an introduction to search problems and the
computation of adaptive search strategies. The need to compute efficient
search strategies arises in many different applications, e.g. machine
learning, data compression, and data bases. Depending on the problem
variant, the computational complexity ranges from cases solvable in
linear time to problems that are even hard to approximate. Subsequently,
current research results are going be discussed, and finally the talk
concludes by stating the most important open questions.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar