«Наука в Сибири»
№ 47 (2682)
4 декабря 2008 г.
МАТЕМАТИКИ ИЗМЕРЯЮТ СЛОЖНОСТЬ
В Институте математики имени С. Л. Соболева СО РАН на базе лаборатории дискретного анализа в последних числах октября проводилась Международная школа-семинар «Синтез и сложность управляющих систем». Прошедшая школа — уже семнадцатая по счету и первая имени академика Олега Борисовича Лупанова, который был инициатором их проведения и, фактически, руководителем этого направления в России.
Галина Шпак, «НВС»
Организаторами школы выступили Московский государственный университет, Институт прикладной математики им. М. В. Келдыша (Москва) и Институт математики (Новосибирск).
Синтез и сложность управляющих систем — область исследования математической кибернетики. В этом отношении прошедшая школа знаменательна тем, что ровно 50 лет назад начали выходить сборники «Проблемы кибернетики».
— В 1958 году, — уточняет заведующий лабораторией дискретного анализа, профессор Александр Андреевич Евдокимов, — в первом выпуске была опубликована статья Алексея Андреевича Ляпунова «О некоторых общих вопросах кибернетики», а во втором — статья Сергея Всеволодовича Яблонского «Основные понятия кибернетики». В этих работах впервые появился термин «управляющая система», и была проанализирована общность этого понятия по отношению к основным задачам исследования кибернетических систем. В статьях А. А. Ляпунова «О логических схемах программ» и А. П. Ершова «Операторные алгорифмы» были заложены основы теоретического программирования.
— Именно — алгорифмы?
— Вы даже в курсе этих разночтений? Сейчас говорят — алгоритмы, а раньше различные научные школы пользовались разной терминологией. Не знаю, почему.
Так вот, в первых выпусках «Проблем кибернетики» были опубликованы и работы Олега Борисовича Лупанова по синтезу и сложности управляющих систем, заложившие основы развития этого направления на многие годы вперёд. Ученик О. Б. Лупанова профессор О. М. Касим-заде возглавляет теперь кафедру дискретной математики Московского университета. Он — председатель оргкомитета школы. Много участников, особенно молодых аспирантов, было и с кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ. У нас давние контакты с обеими этими кафедрами, вместе проводим и молодежные школы по дискретной математике и её приложениям, в том числе, и в Новосибирске. Вот и прошедшая школа является фактически мини-конференцией по дискретной математике с более широкой тематикой, чем название школы.
— Наверное, нужно прояснить математический смысл обычных, привычных слов «синтез» и «сложность».
— Сложность — категория трудно определимая, да и на бытовом уровне использование понятия сложности многообразно. Но в точных математических науках стремятся давать чёткие определения, достигая той или иной степени общности, и так, чтобы это отвечало потребностям исследуемых задач. Так и в математической теории синтеза управляющих систем. Сложность — это функция параметров системы, отражающая ресурсы на её описание или реализацию в определённом классе заданных средств. Ученый секретарь нашей школы-семинара Елизавета Антоновна Окольнишникова недавно защитила докторскую диссертацию именно по тематике синтеза и сложности.
Ноль и единица
или прямые и обратные задачи
Чтобы я не запуталась в «математических цепях», мне предложили автореферат диссертации, в котором дается и общая характеристика предмета нашего разговора. Елизавета Антоновна тактично поправила меня:
— Мы не занимаемся системами уравнений, «математическими цепями», как выразились вы. Мы доказываем теоремы.
Докторскую диссертацию по специальности «дискретная математика и математическая кибернетика» Е. Окольнишникова защитила в прошлом году. Сущность работы отражена в ее названии: «Методы получения нижних оценок сложности ветвящихся программ, вычисляющих булевы функции». Воспользуюсь некоторыми цитатами, общей характеристикой работы.
«Теория сложности вычислений является важным разделом математической кибернетики. Целью теории является оценивание величины ресурсов, необходимых для решения тех или иных вычислительных задач. Рассматриваются различные модели вычисления, такие, например, как машины Тьюринга, автоматы, нормальные алгоритмы, схемы из функциональных элементов, формулы в различных базисах и т.д. В качестве оцениваемых ресурсов рассматриваются время вычисления, объем используемой памяти, длина программы и др. Под сложностью вычисления понимается величина этого ресурса. Основным объектом теории является получение верхних и нижних оценок сложности. При этом получение нижних оценок сложности в большинстве рассматриваемых моделей вычислений представляет наибольшую трудность. Это объясняется тем, что при установлении нижних оценок сложности надо в той или иной мере просмотреть все возможные способы вычисления рассматриваемого объекта и показать, что вычислить этот объект с меньшими затратами невозможно. При получении нижних оценок сложности возникают, решаются и используются важные и интересные задачи из различных областей дискретной математики».
Самое главное, можно догадаться, что с помощью функции математически выражаются многообразные количественные закономерности в природе. И всё-таки без простых аналогий не обойтись. К тому же, происходит подмена понятий. Нематематики, говоря о предмете дискретной математики, подразумевают информатику, а тут еще математическая кибернетика.
— Сейчас термин «математическая кибернетика» употребляется всё реже, — сказал А. Евдокимов, — а информатика у всех на слуху. Хотя мне представляется, что известные дискуссии на тему «кибернетика — информатика» в основном бесплодны. Замечу, что предмет, задачи и методы информатики представляются гораздо более расплывчатыми, чем это было сделано в пионерских работах по кибернетике, о которых я говорил ранее. В наше время нередко информатикой считают просто использование мощных вычислительных возможностей компьютеров или вычислительных сетей для алгоритмического или вычислительного решения задач в какой-либо определённой области исследования.
Теперь о простых аналогиях. Когда я читаю лекции по дискретной математике студентам кафедры биоинформатики НГУ, то популярно объясняю смысл задач синтеза и сложности таким примером. Пусть вам нужно составить некоторый текст телеграммы. Можно выразить свое послание длинно или кратко. Вы стремитесь к краткости, но не в ущерб содержанию. Нужную информацию передать необходимо. Составив (синтезировав) текст, вы определяете верхнюю оценку сложности минимально возможной длины записи вашего послания. Но как доказать, что длина любой вашей телеграммы не может быть слишком короткой? Или, что понадобится не менее 5 минут на передачу? Или, что любые из средств связи не в состоянии передать содержание вашего послания? Постановка подобных вопросов и приводит к доказательствам нижних оценок сложности в задачах синтеза.
В автореферате Елизаветы Антоновны я вычитала, что в данной работе рассматриваются вопросы сложности ветвящихся программ, иначе — математических моделей вычислений, вычисляющих булевы функции, а также операции над булевыми функциями, которые позволяют из просто вычислимых функций получать функции большей сложности.
Комментируя содержательность задач синтеза, профессор А. Евдокимов выделил два типа задач.
— Разработка алгоритмов решения задач — основа многих численных методов решения, особенно в наш век мощных компьютеров. Каждый алгоритм — это верхняя оценка сложности задачи. Доказательства невозможности решения задачи с требуемой трудоёмкостью в определённом классе средств — это нижние оценки. Задача состоит в том, чтобы сблизить эти оценки, пытаясь точнее вычислить «истинную» сложность.
Но задачи синтеза и сложности касаются не только алгоритмических или вычислительных задач, но и схемно-конструкторских построений, и задач упрощения моделей, которые осуществляют заданное функционирование и т.п. Модели вычисления булевых функций — одни из самых простых. Каждая переменная и сама функция принимает только два значения — ноль или единица. В этом «алфавите» работают и «большие» вычислительные системы.
— До сих пор в двоичной системе?
— До сих пор. Но, правда, существуют специализированные устройства, которые работают в многозначной логике. А для математических исследований теоретических вопросов достаточно, как правило, двузначного случая.
Задачами анализа, синтеза и сложности различных моделей занимается много сотрудников лаборатории, не только Елизавета Антоновна.
Отважусь здесь дополнить профессора А. Евдокимова цитатой из реферата: «Удобным объектом для изучения сложности являются характеристические функции двоичных кодов (о которых А. Евдокимов говорил. — Прим. Г.Ш.). Эти функции детально изучаются в дискретной математике, в частности, в теории кодов, исправляющих ошибки. Интерес к этим функциям вызван как их структурными свойствами (одним из таких свойств является «достаточно равномерная распределенность множества единиц значений характеристических функций этих кодов по n-мерному булеву кубу), так и широким практическим применением». Надо понимать, что результаты теоретической работы д.ф.-м.н. Е. Окольнишниковой могут быть использованы при исследовании различных вопросов сложности булевых функций.
— Александр Андреевич, вы упомянули, что подобными задачами занимаются почти все сотрудники лаборатории. Большая у вас лаборатория?
— Сейчас у нас тринадцать человек. Для Института математики это значительный коллектив. Из нашей лаборатории недавно выделилась группа исследователей, которые тоже выступали на прошедшей школе. Группа называется ВТК «Совершенные структуры»
— Интересное название.
— Название из теории совершенных кодов. В данном случае речь идёт о задачах существования, построения и упаковки специального типа регулярных структур в дискретных пространствах. Можно провести аналогию с правильными решёточными структурами в кристаллографии или химии. Совершенный код — это плотная упаковка шаров, своего рода «алмаз», вложенный в структуру булева n-мерного куба. Геометрически красивое образование.
— Получается, что вы и логики, и геометры, и чистые математики...
— Это хорошая мысль! Действительно, для решения задач в нашей области исследования нередко приходится привлекать понятия и методы различных разделов математики: комбинаторики, дискретной геометрии, алгебры, теории вероятности. И, конечно, математический анализ, ведь дискретный анализ и есть фактически функциональный анализ в области дискретных функций. Поэтому для успешной работы мы должны быть достаточно универсальными математиками.
Восхищает сама «ветвящаяся» математика и ее органичное единство. Любопытен многоговорящий исторический факт. Английский математик Джордж Буль в своей книге «Законы мысли» (в другом переводе «Исследование законов мышления», 1854 г.) показал, что законы формальной логики, кодифицированные Аристотелем и в течение столетий изучавшиеся в университетах, сами могут быть предметом исчисления.
Защита
Принято считать, что математика — наука для молодых, а точнее, наука молодых. И на самом деле так. Доказательств из истории науки больше, чем достаточно.
— Это часто подчеркивал Сергей Львович Соболев, — подтвердил в нашем разговоре заведующий лабораторией А. Евдокимов. — Он сам был избран действительным членом Академии наук в очень молодом возрасте. Конечно, научный состав в те годы, когда он возглавлял Институт математики, был моложе.
— Как у вас обстоят дела с защитами диссертаций?
— По-разному, но мне кажется, что в математике лучше, чем в Сибирском отделении в целом, хотя в определенный период много молодых математиков уехало из страны, главным образом, выпускники Новосибирского университета. В последние годы ситуация меняется к лучшему. Это отмечают многие. И о научной молодежи стали заботиться лучше, но с главным — жильём — в целом плохо.
 |
| Защищает диссертацию Н. Н. Токарева. |
У нас 12 ноября состоялось замечательное событие — выпускница НГУ Наталья Николаевна Токарева задолго до окончания аспирантуры защитила диссертацию по направлению «Дискретная математика и математическая кибернетика». Ее руководитель к.ф.-м.н. Юрий Леонидович Васильев — известный специалист по теории кодирования. Наташе 25 лет. Представленная к защите работа «Сильно нелинейные булевы функции: бент-функции и их обобщения» вызвала большой интерес и имеет хорошую перспективу. Оппонентом выступала Елизавета Антоновна.
— Название загадочное.
— Работа из области криптографии, науки о шифрах, — пояснила Е. Окольнишникова.
— Значит, Наталья может открыть любой «сейф»?
— Пока до этого не дошло, — отшутилась Елизавета Антоновна. — Скорее, это ближе к хакерству.
В частности, прикладные задачи криптографии обеспечивают секретность передачи информации по линиям связи и компьютерную защиту. И в банковском деле применяют разнообразное шифрование. В работе Н. Токаревой предложены новые классы функций, которые можно использовать для создания шифров.
 |
| Выступает оппонент д.ф.-м.н. Е. А. Окольнишникова. |
— Елизавета Антоновна, как вы оцениваете работу аспирантки?
— Прекрасная работа! Очень активная, трудолюбивая девушка. Она получила аспирантский грант на конкретное исследование и, можно сказать, досрочно решила сложную задачу. Диссертационный совет Института математики принял решение о присвоении ей ученой степени кандидата физико-математических наук единогласно.
— Елизавета Антоновна, а у вас как было?
— После окончания физматшколы и Новосибирского университета у меня получилось не очень просто. Кандидатскую диссертацию защитила в 1982 г., а докторскую — в 2007. У нас вообще в теоретической кибернетике не так много докторов наук. Кстати, недавно защитила докторскую еще одна претендентка — сотрудник ВТК «Совершенные структуры».
— Удивительно, мне показалось, что женщины-математики опережают мужчин. К чему бы это?
— Нельзя так сказать. Сейчас многие одаренные студенты-математики уходят в программирование. К слову, после защиты кандидатской я в течение восьми лет была единственной «остепененной» в отделении теоретической кибернетики. Но, в принципе, в отделении кибернетики достаточно много женщин-математиков защищают диссертации.
— За что же вам присудили докторскую? — еще раз уточним...
— За разработку метода получения нижних оценок сложности ветвящихся программ. В теории нижних оценок сложности есть особая, парадоксальная ситуация. Во многих моделях вычисления почти все функции вычисляются слишком сложно, а методов получения нетривиальных оценок для конкретных функций очень немного. Мною предложен один из таких методов.
Я могу только добавить, читая автореферат диссертации, что все основные результаты теоретика Е. Окольнишниковой — новые, а метод, о котором идет речь, — первый и пока единственный.
Генетические связи
Ветвящиеся программы — это математическая модель вычислений, хорошо моделирующая работу компьютерных программ, состоящих из условных операторов. Так утверждают математики. С безусловными тоже хорошо работают?
Иными словами — хорошо ли «ветвятся» программы развития собственно дискретной математики и насколько математическая кибернетика связана, допустим, с науками о жизни? Кроме того, в Российской академии, в Сибирском отделении существуют междисциплинарные и другие исследовательские проекты. Насколько активно участвует в них лаборатория дискретного анализа?
— Об этом есть, что сказать, — заведующий лабораторией А. Евдокимов сразу представил активы, начиная с грантов. — Лаборатория с 1993 года получает гранты РФФИ. В общих чертах темы исследований можно обозначить объединённым названием «Дискретный анализ и его приложения». Почти все сотрудники лаборатории заняты в этих грантах. Грант в области синтеза и сложности реализации булевых функций ветвящимися программами — у Елизаветы Антоновны Окольнишниковой.
Наши исследования поддерживаются и программой фундаментальных исследований Отделения математических наук РАН «Алгебраические и комбинаторные методы математической кибернетики» (проект «Новые методы дискретного анализа и комбинаторной оптимизации»).
Теперь, что касается связей с науками о жизни. Это очень широко поставленный вопрос. Я позволю себе сказать только об одной стороне, непосредственно касающейся нас. Несколько лет назад мы заявзали научные контакты с Институтом цитологии и генетики, с лабораторией теоретической генетики академика Николая Александровича Колчанова. Участвовали в двух междисциплинарных интеграционных проектах Сибирского отделения. Первый назывался «Моделирование фундаментальных генетических систем и процессов». Мы занимались математическими задачами алгоритмической обработки и анализа генетических текстов. Более интересным для нас оказалось участие во втором интеграционном проекте — «Генные сети: теоретический анализ, компьютерное моделирование и экспериментальное конструирование». Кстати, работа по этому проекту была для нас близка тематике прошедшей школы, на которой был представлен мой и магистрантки НГУ Елены Олеговны Лиховидовой доклад «Дискретная модель регуляторного контура генной сети с пороговыми функциями».
Я люблю работать со студентами. Читаю лекции на ММФ и курс дискретной математики на ФЕН для биологов-генетиков кафедры биоинформатики. Они тоже меня кое-чему учат в этой области. К этим лекциям меня привлёк Вадим Александрович Ратнер — известный специалист в области молекулярной биологии, который, наряду с Ляпуновым, является одним из пионеров применения кибернетического подхода к изучению моделей в биологии.
— Биологи могут увеличить свой предмет исследования, могут сделать компьютерную картинку и увидеть модель на экране. А вы как действуете?
— Биологи работают с живым материалом. Они его препарируют, «расшифровывают», исследуют структуру, формируют модель, прежде чем «построить картинку», которая, как мне представляется, служит скорее лишь иллюстрацией, а не инструментом исследования. Но об этом лучше спросить самих биологов. А мы работаем уже с моделью, уточняем её математическую основу, и хотя модель абстрактна, но она позволяет изучать нужные свойства её функционирования с помощью математики. Если отвлечься от моделирования, то далее и возникают задачи анализа, сложности и даже синтеза этих моделей биологических систем управления и взаимосвязи их структуры и функционирования. Обнаружение связей структуры и функции и есть одно из фундаментальных направлений настоящих и будущих исследований и в математической кибернетике, и в молекулярной генетике.
Фото В. Новикова
стр. 6-7