OLYMPIADS IN INFORMATICS, 2012, Vol. 6, 110-114
© Institute of Mathematics and Informatics,

ISSN 1822-7732

Tasks of a Priori Unbounded Complexity

Pavel S. PANKOV, Kirill A. BARYSHNIKOV

International University of Kyrgyzstan OJSC ``Finance Credit Bank'', Bishkek, Kyrgyzstan E-mail: pps50@rambler.ru, baryshnikov.kirill@gmail.com

Abstract

We consider the following types of tasks: (*) Is there an element meeting some conditions in an infinite set? (**) If such element a priori exists, find any element or the first of such elements. By the condition, the number of operations (steps) to solve the task is unbounded, and the first aim is to guess any upper estimation for this number and further to improve this estimation. In general, tasks (*) are non-resolvable because they are reduced to the well-known problem of words identity in Markov algorithmical language; tasks (**) are resolvable because an infinite discrete set is countable. We hope that some classes of such tasks may be of interest for using in informatics olympiads of various levels. A survey of such tasks in various branches of informatics and some ideas to create and to solve them are presented.

Keywords:

informatics olympiads, tasks, unboundedness


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2012