The problem of reconstruction of an unknown sequence using the minimum number of its subsequences is considered. A number N(n,t) was found that has the following properties: (i) there exist two binary sequences of length n which have the same set from N(n,t) distinct their subsequences of length n-t, (ii) any binary sequence of length n can be uniquely defined using any subset from N(n,t)+1 its subsequences of length n-t. A simple algorithm was also found which reconsruct an arbitrary sequence of length n using any set from N(n,t)+1 its subsequences of length n-t (if such a set exists). This algorithm is based on a combination of majority and threshold principles.

Back to Workshop Schedule