Next week (September 24- September 28, 2012), at the Faculty of Mathematics, Natural Sciences and Information Technologies in Koper, dr. Ferdinando Cicalese from the University of Salerno, Italy will be giving three lectures. The lectures will take place in the "Seminar room" at Galeb (Kettejeva 1, Koper).
The lectures will be held on:
- Monday (September 24, 2012) 10:00-11:00
- Wednesday (September 26, 2012) 10:00-11:00
- Friday (September 28, 2012) 10:00-11:00
All welcome!
Title: Models and Methodologies in Combinatorial Search
Abstract:
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 properties is present in a given sample.
The structure of a typical search problem appears more often than one would expect, in surprisingly diverse scenarios. A search problem can be the task of: (i) identifying objects within a set via a series of tests (identification); (ii) learning the structure of a given function via sampling (learning); (iii) determining the most concise way of representing a given piece of information so that recovery is uniquely achievable (encoding); (iv) distinguishing patterns on the basis of exact or approximate examples (classification).
Typical applications are found in medical diagnosis, database theory, networking, laboratory analysis, computer decision making, bioinformatics data analysis and inference, just to mention a few.
We shall analyze three different scenarios where instances of the above models are found and give a glimpse of the tools and techniques used in the field.
In the first talk, we shall discuss a model of approximate string matching. Given a pattern p, and a string s, we are interested in finding any or all jumbled occurrences of the pattern p in the given string. By a jumbled occurrence of p in s we mean the existence of a substring of s which has exactly the same multiplicity of characters of the pattern p, i.e., it coincides with p or with any permutation of p.
In the second talk, we shall focus on non-adaptive group testing procedures: in a finite set U we want to identify an initially unknown subset P. We can test any subset Q of U for the presence of elements of P, we also assume some knowledge on the cardinality of the target set P.
We shall look at non-adaptive procedures for group testing, we shall show the connections between this problem and error correcting codes. We shall also survey recent results in this area and discuss known and novel applications.
In the third talk, we shall look at a very general model of identification problem, where the reservoir of tests available is restricted. We are given: (i) a finite set of objects, O1,..., On, from which an initially unknown object has to be identified; (ii) a finite set of m tests (or questions) Q1, ..., Qm, which can be used to acquire information about the unknown object to be identified; (iii) a set of m costs, C1, ..., Cm, where Ci is the cost we incur when we apply test Qi.
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. Since this problem is in general hard, we shall concentrate on approximation algorithms. We shall analyze a greedy approach that achieves the best known approximation ratios simultaneously for many different variations of this identification problem.
