Combinatorial Search Algorithms for Function Evaluation

Relatore:  Ferdinando Cicalese - Università degli Studi di Salerno
  giovedì 6 ottobre 2011 alle ore 16.45 16:45 rinfresco; ore 17:00 inizio seminario

In a typical combinatorial search problem one is required to develop a testing procedure to determine which one of a finite number of possible objects or conditions is present. Such problems arise in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, and many other fields.

More precisely, we define an identification problem as follows:

a) a finite set of objects, O1,..., On, from which an initially unknown object has to be identified;
b) a finite set of m tests (or questions) Q1, ..., Qm, which can be used  to acquire information about the unknown object to be identified;
c) a set of m costs, C1, ..., Cm, where Ci is the cost we incur when we apply test Qi.

In some variants, one also allows erroneous outcomes of the tests and/or makes additional probabilistic assumptions on the identity of the object to be identified.

A solution to the above problem is a deterministic algorithm (decision tree) for choosing which questions to ask such that: (i) the unknown object will always be identified; (ii) as little cost as possible will be incurred.

In this talk, we focus on one particular instance of the above problem: function evaluation with priced information. This problem has applications in automatic diagnosis, strategic decision making, computer games, database query optimization.


Luogo
Ca' Vignal - Piramide, Piano 0, Sala Verde

Referente
Maria Paola Bonacina

Referente esterno
Data pubblicazione
27 settembre 2011

Offerta formativa

Condividi