Заведующий сектором – д.ф.-м.н., проф. Любецкий Василий Александрович

Тел. (095) 299-83-54, (095) 413-46-43; E-mail: lyubetsk@iitp.ru

Ведущие ученые сектора:

• построение приемлемой сложности (квадратичных и т.п.) алгоритмов для описания характерных процессов вычислительной генетики (выделение регуляторных сигналов в геномной последовательности, оптимизация дерева видов на основе деревьев генов и т.п.); разработка методов выделения регуляторных сигналов в ДНК и РНК бактерий на основе сравнения нескольких геномов;
• исследование алгоритмического, теоретико-модельного и семантического подходов к понятиям информации, информационного взаимодействия; к описанию понятий, сцен; к описанию информационных процессов достижения цели; исследование психологии восприятия предикатов и отношений;
• исследование концепции эффективного описания объектов (структур, отношений, понятий) на основе следующих теорий: модельной полноты, редукции интуиционистских и модальных систем к классическим, колмогоровской сложности.

Исследован алгоритм менее чем квадратичной сложности, который осуществляет вложение многих данных деревьев генов в исходное дерево видов, оценивает качество этого совместного вложения и на этой основе итеративно преобразует дерево видов так, чтобы монотонно увеличивалось качество совместного вложения.

Получен алгоритм квадратичной сложности, который по данному набору геномных последовательностей выделяет в них общий “сигнал” – систему подобных слов фиксированной длины, удовлетворяющих определенным соотношениям.

Разработан метод выделения регуляторных сигналов в ДНК бактерий на основе сравнения нескольких геномов. Описаны бактериальные регулоны (пуриновый, ароматических аминокислот, аргининовый, рибофлавиновый, СОС-ответа и ряд других) и архебактериальные регулоны (пуриновый, триптофановый, теплового шока, утилизации азота). Разработан метод предсказания специфичности транспортеров (с неизвестной функцией) по регуляции кодирующего их гена, и впервые описаны семейства транспортеров пуринов и рибофлавина. На основании сравнительного анализа с Escherichia coli найдены регуляторные сигналы трансляции рибосомальных белков Haemophilus influenzae в следующих оперонах: spc, S10, L11, a и S15; постороены аттенюаторы транскрипции ароматических биосинтетических оперонов trpEDCBA, pheA и pheST у следующих гамма-пурпурных бактерий: Salmonella tiphi, Yersinia pestis, Erwinia herbicola, Vibrio cholerae, Haemophilus influenzae, Actinobacillus actinomyce-temcomitans, Xanthomonas campestris, а также у хламидии.

Разработан метод предсказания генов человека в геномных последовательностях, содержащих ошибки. Начата работа над созданием алгоритма предсказания генов на основе сравнения таких последовательностей.

Получено теоретико-модельное описание ряда конкретных классов преобразователей информации (далее ПИ) и аксиоматическое описание произвольного класса ПИ. Развит байесовский подход к задачам принятия решений и доказан байесовский принцип в классах линейных, многозначных, нечетких ПИ и в аксиоматически заданном классе ПИ.

Исследованы принципы построения категорий динамических ПИ. Построена категория линейных недетерминированных динамических ПИ с дискретным временем. Исследована задача оптимального синтеза систем формирования изображений с непрерывным полем зрения. Показано, что она сводится к интегральному уравнению Фредгольма второго рода. Проведено численное моделирование полученного алгоритма решения этой задачи.

Доказан вариант теоремы Шеннона – Макмиллана – Бреймана для индивидуальных случайных последовательностей. Получены сложностные оценки применимости закона о длине максимальной серии успехов. Изучена зависимость функций правдоподобия от сложности распределения вероятностей. Доказана эквивалентность двух определений бернуллиевской последовательности (по Колмогорову и на основе перестановочных мер).

Получен статистически достоверный экспериментальный вывод о существовании систематических искажений при оценке линейных свойств пространства. Экспериментально показано, что схема “сначала деление отрезка на n частей, затем удлинение одной части в n раз” при чётном n приводит к систематической ошибке преуменьшения восстанавливаемого отрезка по сравнению с первоначальным, а при нечётном n – наоборот, к систематической ошибке преувеличения восстанавливаемого отрезка. Выяснено, что при небольшой длине l исходного отрезка (не более 10 см) относительная ошибка существенно меньше, чем при l > 10 см. Проведён эксперимент по оценке точности известной зрительной иллюзии “веера”. Проведен эксперимент, показавший, что словосочетания (в русском языке) со смыслом обобщённых кванторов приводят к систематическому смещению соответствующего значения в сторону завышения. Предложены предварительные модели, объясняющие эти эксперименты. (Работы проводились совместно с Лабораторией № 12 ИППИ РАН).

Получен эффективно заданный широкий класс описаний (теорий), относительно которых всякое суждение эквивалентным образом приводится к бескванторному (или другому простому) виду.

Получен линейной сложности перевод формальных доказательств в классической теории в доказательства соответствующей интуиционистской теории; в частности, это позволяет по классическому доказательству существования зависимой величины эффективно получить алгоритм, реализующий эту величину.

Найден общий способ построения существенно более простых, чем было известно, алгоритмов вычисления булевых функций (а именно, булевских разрешающих деревьев высоты 2M log N). Понятия можно определять как булевы функции, у которых i-й аргумент соответствует наличию/отсутствию i-го признака у рассматриваемого объекта. Простые алгоритмы вычисления булевых функций дают более адекватное представление соответствующих понятий.

Доказано, что для любых слов x и y существуют преобразователи p (слова x в слово y) и q (слова y в слово x), оба минимально возможной длины и “независимые” (т.е. с общей информацией порядка log от сложностей x и y). Если “независимость” понимать как log от условных сложностей x/y и y/x, то такие p и q могут не существовать.

Доказано, что если слово x просто относительно любого достаточно сложного слова y, то существует простой алгоритм, переводящий почти все y в данное x.

Вычислена сложность ряда важных задач, формулируемых в терминах конъюнкции, дизъюнкции и импликации двух множеств слов. Найдена такая пропозициональная формула (не выводимая в интуиционистском исчислении высказываний), что сложность соответствующей задачи мала (порядка логарифма от сложностей аргументов).

Доказано, что существуют такие слова A,B,C, что сложность формулы “A или B влечет C” близка к сумме колмогоровских условных сложностей K(C|A)+K(C|B).

Получены верхние оценки (древесной) ширины графов, не содержащих в качестве миноров плоских решеток данного размера r. Оценки таковы: для произвольных графов exp(p(r)), где р – фиксированный полином, а для плоских графов – линейная относительно r функция. Отсюда получены такие же оценки минимального размера графовой КС-грамматики, порождающей все графы, которые имеют ограниченную степень и не содержат в качестве миноров решеток данного размера. Предложено используемое в алгоритмах генетики понятие n-делимого графа и доказано существование полиномиального алгоритма, который по графу G и числу n выясняет, является ли G n-делимым (и строит процесс его деления).

Доказано, что всякая обобщенно полная по Посту табличная модальная логика, являющаяся расширением K4, обладает интерполяционным свойством (важная связь понятий “информационной насыщенности” логики).

Доказано, что существует модальная логика с бесконечным множеством полных по Посту расширений, но все такие ее расширения табличны.

Получен алгоритм разрешения модальных предикатных логик K, K4, T, S4, S5 относительно классической логики предикатов.

1. Любецкий В.А. Логика устной речи в сравнении с логикой письменной речи. Труды Второго Российского философского конгресса, Екатеринбург, Издательство Уральского университета, часть 1, 1999, с. 222.
2. Горемыкина Г.И., Любецкий В.А. О преобразовании классических выводов в интуиционистские. Труды второй международной конференции "Смирновские чтения", Москва, ИФРАН, 1999, с. 38-41.
3. Любецкий В.А., Чернавский А.В. Об основах интеллектуальных процессов. Труды Второго Российского философского конгресса, Екатеринбург, Издательство Уральского университета, часть 1, 1999, с. 223-224.
4. Любецкий В.А. Логические модели процессов информационного взаимодействия. Труды Международной конференции РАН "Проблемы управления и моделирования в сложных системах", Самара, 20-26 июля 1999 г., с. 133-145.
5. Кузнецов Н.А., Любецкий В.А. Компьютерная логика в информационных процессах. Проблемы передачи информации, том 35, вып. 2, 1999, с. 107-111.
6. Lyubetsky V.A. Topics in Classical and Intuitionistic Model Theory. Patras University press and Simon Inc., Patras (Greece) and Stockholm (Sweden), 1999, 520 p.
7. Vereshchagin N.K. Relativizability in Complexity Theory. In: L. Beklemishev, M. Pentus, N. Vereshchagin. Provability, Complexity, Grammars, AMS Translations 2, vol. 192, 1999, p. 87-176.
8. Muchnik An.A., Romashchenko A.E., Shen A., Vereshchagin N.K. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". Proceedings of IEEE conference on Computational Complexity, Atlanta (USA), IEEE Publishing House, 1999, p. 62-73.
9. Raz R., Tardos G., Verbitsky O., Vereshchagin N. Arthur-Merlin Games in Boolean Decision Trees. Journal of Computer and Systems Sciences, vol. 59, 1999, p. 534-560.
10. Razborov A., Vereshchagin N. One Property of Cross-Intersecting Families. Electronical Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc), TR99-014, 1999, 3 p.
11. Durand B., Shen A., Vereshchagin N. Descriptive complexity of computable sequences. Lecture Notes in Computer Sciences, vol. 563, 1999, p. 153-162.
12. Верещагин Н.К., Шень А. Начала теории множеств. М.: Московский центр непрерывного математического образования, 1999, 127 с.
13. Горбунов К.Ю. Структурные свойства контекстно-свободных грамматик. Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. М.: МГУ, 1999, 11 с.
14. Diestel К, Jensen T.R., Gorbunov K.Yu., Thomassen C. Highly Connected Sets and the Excluded Grid Theorem. Journal of Combinatorial Theory, Series B, vol. 75, 1999, p. 61-73.
15. Чагров А.В., Чагрова А.А. Бесконечные множества несводимых модальностей в нормальных модальных логиках. Логические исследования. Выпуск 5. М., Наука, 1999, с. 150-159.
16. Чагров А.В. Строго импликативные формулы в модальных логиках, близких к интуиционисткой. Логические исследования. Выпуск 6. М.: Российская политическая энциклопедия (РОССПЭН), 1999, с. 69-75.
17. Чагров А.В. К вопросу об обратной математике модальной логики. Смирновские чтения, вторая международная конференция. М.: ИФРАН , 1999, с. 72-75.
18. Чагров А.В. Конструктивная логика. В кн.: Философская энциклопедия. М.: ИФРАН (в печати).
19. Chagrov A.V. A First-Order Effect and Modal Propositional Formulas. In: Logic and Foundation of Mathematics. Selected Contributed Papers of the Tenth International Congress of Logic, Methodology and Philosophy of Science. A.Cantini, E.Casari, P.Minary (Eds.) Florence, August 1995. Kluwer Academic Publishers, 1999, p. 209-218.
20. Zakharyaschev A.V., Wolter F., Chagrov A. Advanced Modal Logic. In: New Handbook of Philosophical Logic. D. Gabbay (Еd.), North-Holland, 1999, p. 20-205.
21. Чагров А.В. Логика, не являющаяся ни конечно-значной, ни бесконечно-значной. Труды научно-исследовательского логического семинара ИФРАН. М.: Наука, 1999, 8 с. (в печати).
22. V'yugin V.V. Algorithmic complexity and stochastic properties of finite binary sequences. The Computer Journal, vol. 42, no. 4, 1999, p. 294-317.
23. Голубцов П.В. Преобразователи информации и проблема сравнения информативности. Труды второго российского философского конгресса, Екатеринбург, Издательство Уральского университета, часть 1, 1999, с. 209.
24. Голубцов П.В. Алгебраический подход к определению информативности. Труды международной конференции РАН "Проблемы управления и моделирования в сложных системах", Самара, 20-26 июля 1999 г., с. 106-111.
25. Голубцов П.В. Aксиоматическое описание категорий преобразователей информации. Проблемы передачи информации, т. 35, № 3, 1999, с. 109-127.
26. Zhang Y., Golubtsov P., Carpio R., Wagner L. Wafer Mapping for Stepper Effects Characterization. SPIE '99 in Santa Clara, Santa Clara, March 16, 1999, с. 27-30.
27. Витрещак А.Г., Гельфанд М.С. Аттенюация транскрипции оперонов биосинтеза ароматических аминокислот гамма пурпурных бактерий. Научный совет по молекулярной биологии и генетике РАН. Школа молодых ученых "Молекулярная биология и биомедицина", Черноголовка, 12-16 апреля 1999 г. (в печати).
28. Гельфанд М.С., Витрещак А.Г., Миронов А.А. Информационное взаимодействие и регуляторные образцы в бактериальных геномах. Труды международной конференции "Проблемы управления и моделирования в сложных системах", Самара, 20-26 июля 1999 г., с. 101-105.
29. Витрещак А.Г., Бансал А.К., Титов И.И., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Инициация трансляции оперонов рибосомальных белков. Биофизика, том 44, вып. 4, 1999, с. 601-610.
30. Gelfand M.S., Mironov A.A., Jomantas J., Kozlov Y.I., Perumov D.A. A conserved RNA structure element involved in the regulation of bacterial riboflavin synthesis genes. Trends in Genetics, vol 15, no. 11, 1999, p. 439-442.
31. Mironov A.A., Koonin E.V., Roytberg M.A., Gelfand M.S. Computer analysis of transcription regulatory patterns in completely sequenced bacterial genomes. Nucleic Acids Research, vol. 27, no. 14, 1999, p. 2981-2989.
32. Frishman D, Mironov A, Gelfand M. Starts of bacterial genes: estimating the reliability of computer predictions. Gene, vol. 234, no. 2, 1999, p. 257-265.
33. Gelfand M.S., Dubchak I., Dralyuk I., Zorn M. ASDB: database of alternatively spliced genes. Nucleic Acids Research, vol. 27, no. 1, 1999, p. 301-302.
34. Миронов А.А., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Участки связывания PurR. Молекулярная биология, т. 33, № 1, 1999, с. 127-132.
35. Миронов А.А., Фришман Д., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Участки связывания рибосом. Молекулярная биология, т. 33, № 1, 1999, с. 133-140.
36. Кривенцева Е.В., Макеев В.Ю., Гельфанд М.С. Статистический анализ экзон-интронной структуры генов высших эукариот. Биофизика, т. 44, № 4, 1999, с. 595-600.
37. Боровина Т.А., Назипова Н.Н., Овербик Р., Гельфанд М.С. Статистический анализ и предсказание бактериальных сайтов связывания рибосом. Биофизика, т. 44, № 4, 1999, с. 611-619.
38. Миронов А.А., Гельфанд М.С. Компьютерный анализ регуляторных сигналов в полных бактериальных геномах. Участки связывания LexA и DinR. Молекулярная биология, т. 33, № 5, 1999, с. 772-778.
39. Миронов А.А., Гельфанд М.С. Вычислительная биология на рубеже десятилетий. Молекулярная биология, т. 33, № 6 1999, с. 969-984.
40. Kriventseva V., Gelfand M.S. Statistical analysis of the exon-intron structure of higher and lower eukaryote genes. Journal of Biomolecular Structure and Dynamics, vol. 17, no. 2, 1999, p 281-288.
41. Дружинин Ю.Г., Чернавский А.В. Задачи оценки геометрических структур воспринимаемого пространства в геометрической психофизике. Труды международной конференции РАН "Проблемы управления и моделирования в сложных системах", Самара, 20-26 июля 1999 г., с. 112 -116.