Ябло́нский Сергей Всеволодович (6.12.1924-26.05.1998)
Кафедра математической кибернетики факультета ВМиК МГУ была основана в 1971 году выдающимся российским учёным, одним из основателей отечественной школы математической кибернетики и дискретной математики, Сергеем Всеволодовичем Ябло́нским.
С.В.Яблонский родился 6 декабря 1924 года в Москве в семье профессора механики. Его математическое дарование проявилось еще в школе, и в 1940 г. он стал победителем 6-й Московской математической олимпиады школьников. Окончив школу, он поступил в Московский университет на механико-математический факультет. Но это был 1941 год, и война надолго оторвала С.В.Яблонского от учебы. Осенью 1942 года после окончания первого курса он 18-летним юношей ушел на фронт и в составе 242-го танкового полка прошел трудный боевой путь по дорогам Великой Отечественной войны. О доблести и самоотверженности Сергея Всеволодовича говорят его боевые награды - два ордена Отечественной войны, два ордена Красной Звезды, орден Славы 3-й степени, боевые медали.
К занятиям любимой наукой Сергей Всеволодович смог вернуться лишь в победном 1945 году. Возвратившись в МГУ, он активно включился в учебу и в 1950 г. с отличием окончил механико-математический факультет МГУ. Научные исследования в студенческие годы он вел под руководством Нины Карловны Бари, и в 1950 г. опубликовал первую свою научную работу "О сходящихся последовательностях непрерывных функций" в "Вестнике Московского университета".
В 1950 г. Сергей Всеволодович поступил в аспирантуру механико-математического факультета МГУ, где его научным руководителем был Пётр Сергеевич Новиков, оказавший большое влияние на формирование научных интересов Сергея Всеволодовича. Тематикой исследований Сергея Всеволодовича стали вопросы выразимости в математической логике. Его исследования показали, что эти вопросы, порождённые математической логикой, находят более адекватное описание и решение в теории дискретных многозначных функций. Разработка этой теории и решение ряда конкретных задач в ней (в частности, окончательное решение проблемы полноты в 3-значной логике) составили основу кандидатской диссертации С.В. Яблонского "Вопросы функциональной полноты в k-значном исчислении", защищенной им в 1953 г.
С 1953 года Сергей Всеволодович начал работать в Отделении прикладной математики Математического института им. В.А.Стеклова, которое позднее было преобразовано в Институт прикладной математики. Он продолжил исследования в области дискретных многозначных функций и в 1958 г. в "Трудах Математического института им. В.А.Стеклова" (т. 51) опубликовал большую обзорную статью "Функциональные построения в k-значной логике", в которой удачно систематизировал накопленные к тому времени результаты в этой области. Эта статья сыграла огромную роль в становлении дискретной математики и математической кибернетики, и на протяжении многих лет была основным учебным пособием по теории дискретных функций для многих исследователей.
В это же время Сергей Всеволодович активно включился в исследование проблем, связанных с синтезом логических устройств. Среди работ этого периода важное место занимают его работы (совместно с И.А.Чегис) о тестировании электрических схем. Их работа "Логические способы контроля работы электрических схем", опубликованная в 1958 г. в том же 51-м томе "Трудов МИАН им. В.А.Стеклова", представляла новый взгляд на проблемы построения тестов и дала толчок развитию комбинаторно-логических методов как в теории надёжности схем, так и в распознавании образов.
Изучая логические вопросы в теории схем, Сергей Всеволодович непосредственно сталкивался и с новым математическим термином "кибернетика", вокруг которого шли философские и идеологические споры. Глубоко понимая важность математических проблем, связанных с кибернетикой, Сергей Всеволодович сразу же активно встал на ее защиту. Большое влияние в этом оказал на него Алексей Андреевич Ляпунов, вместе с которым они в 50-х и 60-х годах проводили знаменитый семинар по кибернетике. Сергей Всеволодович принял активное участие в организации периодического сборника "Проблемы кибернетики", издание которого началось в 1958 г. А.А. Ляпуновым. Сергей Всеволодович осознавал важность выделения в кибернетике чисто математических вопросов и отделение их от философии и идеологии. Итогом его анализа явилась опубликованная в 1959 г. в сборнике "Проблемы кибернетики" статья "Основные понятия кибернетики", в которой выделено и математически формализовано понятие управляющей системы, указаны проблемы и направления развития теории управляющих систем. Разъяснению и пропаганде идей кибернетики Сергей Всеволодович уделял большое внимание, о чем говорят его доклады, представленные на 3-м (в 1956 г. с соавторами) и 4-м Всесоюзных математических съездах, на Международном конгрессе по обработке информации ИФИП-68, на других конференциях, а также его публикации по теоретическим и прикладным проблемам кибернетики: статья в "Морском сборнике" (1960 г., с А.И. Бергом и А.А. Ляпуновым), ротапринт Института мировой экономики и международных отношений (1961 г., с А.А. Ляпуновым), статья в сборнике "Проблемы кибернетики" (1963 г., с А.А. Ляпуновым).
С 1958 г. Сергей Всеволодович возглавил отдел математической кибернетики в Институте прикладной математики, созданный им совместно с А.А. Ляпуновым. В этот период Сергей Всеволодович проводит исследования, связанные с проблемами сложности алгоритмов для минимизации схем. Полученные им в этом направлении важные результаты, объясняющие трудности в построении минимальных схем, вошли в его докторскую диссертацию "О некоторых математических вопросах теории управляющих систем", которую он успешно защитил в 1962 г. В 1966 г. С.В. Яблонский (совместно с Ю.И. Журавлёвым и О.Б. Лупановым) был удостоен Ленинской премии за цикл работ по теории управляющих систем. В 1968 г. он был избран членом-корреспондентом АН СССР по отделению математики, в работе которого он принял самое активное участие, ряд лет являясь заместителем академика-секретаря и членом бюро отделения математики. Он был одним из основателей и действительным членом Академии криптографии, в которой он также активно работал.
Сергей Всеволодович всегда понимал важность дискретных методов в теории управляющих систем и необходимость развития различных направлений дискретной математики как основы для построения и анализа дискретных моделей в различных приложениях.
Он внес огромный вклад в координацию и развитие научных исследований в области математической кибернетики и дискретной математики, глубоко понимая необходимость обмена информацией о новых научных результатах и поддержки исследований в данных направлениях. Большую роль в этом сыграл его "пятничный" семинар по математическим вопросам кибернетики, который регулярно работал в МГУ под руководством Сергея Всеволодовича более 30 лет и продолжал работу под руководством ученика Сергея Всеволодовича академика РАН О. Б. Лупанова. На этом семинаре обсуждались новые наиболее интересные результаты в области математической кибернетики и дискретной математики, с которыми выступали математики не только Москвы, но и других городов и даже других стран. Сам факт выступления на этом семинаре уже являлся высокой оценкой полученных результатов.
Сергей Всеволодович принимал активное участие в организации и проведении первых Всесоюзных конференций по проблемам теоретической кибернетики, а затем в течение многих лет был бессменным председателем оргкомитета этих конференций. Он активно способствовал становлению и росту научных коллективов в Нижнем Новгороде, Новосибирске, Казани, Саратове, Иркутске, других городах.
Большую роль в популяризации теории дискретных функций сыграла изданная С.В. Яблонским в 1966 г. совместно с его учениками Г.П. Гавриловым и В.Б. Кудрявцевым книга "Функции алгебры логики и классы Поста".
С 1974 г. Сергей Всеволодович стал главным редактором сборников "Проблемы кибернетики" (с 1989 г. они выходят под названием "Математические вопросы кибернетики"). Он принял активное участие в работе над "Математической энциклопедией", где разрабатывал и редактировал раздел, посвященный дискретной математике и математической кибернетике. Совместно с О.Б. Лупановым подготовил к изданию широко известный среди специалистов сборник статей "Дискретная математика и математические вопросы кибернетики".
Огромен вклад Сергея Всеволодовича в подготовку кадров в области математической кибернетики и дискретной математики. Параллельно с работой в ИПМ Сергей Всеволодович с 1954 г. вёл преподавание на механико-математическом факультете МГУ. Здесь он разрабатывал и оттачивал спецкурсы "Введение в дискретную математику" и "Основы кибернетики". С 1963 г. он - профессор МГУ. Сергей Всеволодович принял активное участие в организации в МГУ в 1970 году факультета вычислительной математики и кибернетики, где с 1971 года создал и возглавил кафедру теории автоматов и математической логики, которая вскоре была переименована в кафедру математической кибернетики. Эта кафедра, которой бессменно руководил С.В. Яблонский, подготовила несколько сотен специалистов в области математической кибернетики и дискретной математики. На факультете ВМиК Сергей Всеволодович начал чтение курсов "Введение в дискретную математику" и "Основы кибернетики" уже как обязательных курсов для студентов. Разработанная им программа этих курсов легла позднее в основу составленной им программы курса "Дискретная математика", принятой для университетов всей страны, что оказало огромное влияние на ознакомление с основами дискретной математики студентов-математиков всего Советского Союза. Сергей Всеволодович организовывал Всесоюзные методические совещания по проблемам преподавания дискретной математики. До сих пор основным учебником по дискретной математике в нашей стране и некоторых других странах является изданный в 1979 и 1986 годах учебник С.В. Яблонского "Введение в дискретную математику".
Активное участие принял Сергей Всеволодович в организации Международного математического центра им. С. Банаха. Он долгое время был членом совета этого центра и организовывал проведение в центре семестров по дискретной математике.
За большие заслуги в области научно-организационной деятельности Сергей Всеволодович был награждён орденом Трудового Красного знамени.
Сергей Всеволодович много работал со студентами и аспирантами, ставя перед ними задачи достаточно широкого спектра. Под его руководством выполнено и защищено более 25 кандидатских диссертаций, среди его учеников доктора наук, члены научных академий. Уже несколько поколений учеников и последователей Сергея Всеволодовича образуют созданную им мощную научную школу, объединяющую исследователей не только нашей страны, но и некоторых других стран.
В. Б. Алексеев
Сергей Всеволодович Яблонский
Огромную роль в становлении и развитии кибернетики сыграл Сергей Всеволодович Яблонский (1924-1998) – выдающийся русский ученый, один из основателей отечественной школы математической кибернетики и дискретной математики.
С. В. Яблонский родился 6 декабря 1924 г. в Москве, в семье профессора механики. Его математическое дарование проявилось еще в школе, в 1940 г. он стал победителем 6-й Московской математической олимпиады школьников. Окончив школу, он поступил в Московский университет на механико-математический факультет . Но это был 1941 год, и война надолго оторвала С. В. Яблонского от учебы. Осенью 1942 г., после окончания первого курса он 18-летним юношей ушел на фронт и в составе 242 танкового полка прошел трудный боевой путь по дорогам Великой Отечественной войны. О доблести и самоотверженности Сергея Всеволодовича говорят его боевые награды – два ордена Отечественной войны, два ордена Красной Звезды, орден Славы 3-й степени, боевые медали.
К занятиям любимой наукой С. В. Яблонский смог вернуться лишь в победном 1945 г. Возвратившись в МГУ , он активно включился в учебу и в 1950 г. с отличием окончил механико-математический факультет МГУ . Научные исследования в студенческие годы он вел под руководством Нины Карловны Бари. В 1950 г. он опубликовал в "Вестнике Московского университета" свою первую научную работу "О сходящихся последовательностях непрерывных функций".
В этом же году Сергей Всеволодович поступил в аспирантуру мехмата, где его научным руководителем был Петр Сергеевич Новиков, оказавший большое влияние на формирование научных интересов Яблонского . Тематикой исследований С. В. стали проблемы выразимости в математической логике. Его исследования показали, что эти вопросы, порожденные математической логикой, находят более адекватное описание и решение в теории дискретных многозначных функций. Разработка этой теории и решение ряда конкретных задач в ней (в частности, окончательное решение проблемы полноты в 3-значной логике) составили основу кандидатской диссертации С. В. Яблонского "Вопросы функциональной полноты в k-значном исчислении", защищенной им в 1953 г.
С 1953 г. Сергей Всеволодович начал работать в Отделении прикладной математики Математического института им. В. А. Стеклова, которое позднее было преобразовано в Институт прикладной математики . Он продолжил исследования в области дискретных многозначных функций и в 1958 г. опубликовал в "Трудах Математического института им. В. А. Стеклова" (т. 51) большую обзорную статью "Функциональные построения в k-значной логике", в которой удачно систематизировал накопленные к тому времени результаты в этой области. Эта статья сыграла огромную роль в становлении дискретной математики и математической кибернетики и на протяжении ряда лет была основным учебным пособием по теории дискретных функций для многих исследователей.
В это же время активно включился в исследование проблем, связанных с синтезом логических устройств. Среди результатов этого периода важное место занимают его работы (совместно с И. А. Чегис ) о тестировании электрических схем. Их работа "Логические способы контроля работы электрических схем", опубликованная в 1958 г. в том же 51 томе "Трудов МИАН", представляла новый взгляд на проблемы построения тестов и дала толчок развитию комбинаторно-логических методов как в теории надежности схем, так и в распознавании образов.
Изучая логические вопросы в теории схем, Сергей Всеволодович непосредственно сталкивался и с новым математическим термином "кибернетика", вокруг которого шли философские и идеологические споры. Глубоко понимая важность математических проблем, связанных с кибернетикой, Яблонский сразу же активно встал на ее защиту. Большое влияние в этом оказал на него , вместе с которым они в 50-х и 60-х годах проводили знаменитый семинар по кибернетике. С. В. принял активное участие в организации периодического сборника "Проблемы кибернетики", издание которого начал в 1958 г. А. А. Ляпунов.
Осознавал важность выделения в кибернетике чисто математических вопросов и отделение их от философии и идеологии. Итогом его анализа явилась опубликованная в 1959 г. в сборнике "Проблемы кибернетики" статья "Основные понятия кибернетики", в которой выделено и математически формализовано понятие управляющей системы, указаны проблемы и направления развития теории управляющих систем. Разъяснению и пропаганде идей кибернетики Сергей Всеволодович уделял большое внимание, о чем говорят его доклады, представленные на третьем (1956 г., с , и И. А. Полетаевым ) и четвертом Всесоюзных математических съездах, на Международном конгрессе по обработке информации ИФИП-68, на других конференциях, а также его публикации по теоретическим и прикладным проблемам кибернетики: статья в "Морском сборнике" (1960 г., с и ), ротапринт Института мировой экономики и международных отношений (1961 г., с ), статья в сборнике "Проблемы кибернетики" (1963 г., с ).
С 1958 г. возглавил отдел математической кибернетики Института прикладной математики , созданный им совместно с . В этот период С. В. проводит исследования, связанные с проблемами сложности алгоритмов для минимизации схем. Полученные им в этом направлении важные результаты, объясняющие трудности в построении минимальных схем, вошли в его докторскую диссертацию "О некоторых математических вопросах теории управляющих систем", которую он успешно защитил в 1962 г.
В 1966 г. С. В. Яблонский (вместе с Ю. И. Журавлевым и О. Б. Лупановым ) был удостоен Ленинской премии за цикл работ по теории управляющих систем. В 1968 г. он был избран членом-корреспондентом АН СССР по Отделению математики, в работе которого он принял самое активное участие, являясь в течение ряда лет заместителем академика-секретаря и членом бюро этого Отделения. Он был одним из основателей и действительным членом Академии криптографии, в которой также активно работал.
Сергей Всеволодович всегда понимал важность дискретных методов в теории управляющих систем и необходимость развития различных направлений дискретной математики как основы для построения и анализа дискретных моделей в различных приложениях.
Он внес решающий вклад в координацию и развитие научных исследований в области математической кибернетики и дискретной математики, глубоко понимая необходимость обмена информацией о новых научных результатах и поддержки исследований в данных направлениях. Большую роль в этом сыграл "пятничный" семинар по математическим вопросам кибернетики, который регулярно работал в МГУ под его руководством более 30 лет и продолжает работу и сейчас под руководством члена-корреспондента РАН О. Б. Лупанова – ученика С. В. Яблонского . На этом семинаре обсуждались новые наиболее интересные результаты в области математической кибернетики и дискретной математики, с которыми выступали математики не только Москвы, но и других городов, а также других стран. Сам факт выступления на этом семинаре уже являлся высокой оценкой полученных результатов.
С. В. Яблонский принимал активное участие в организации и проведении первых Всесоюзных конференций по проблемам теоретической кибернетики, а затем в течение многих лет был бессменным председателем Оргкомитета этих конференций. Он активно способствовал становлению и росту научных коллективов в Нижнем Новгороде, Новосибирске, Казани, Саратове, Иркутске и других городах.
Большую роль в популяризации теории дискретных функций сыграла изданная С. В. Яблонским в 1966 г., совместно с его учениками Г. П. Гавриловым и В. Б. Кудрявцевым , книга "Функции алгебры логики и классы Поста".
С 1974 г. – главный редактор сборников "Проблемы кибернетики" (с 1989 г. они выходят под названием "Математические вопросы кибернетики"). Он принял активное участие в работе над "Математической энциклопедией", где разрабатывал и редактировал раздел, посвященный дискретной математике и математической кибернетике. Совместно с О. Б. Лупановым , он подготовил к изданию широко известный среди специалистов сборник статей "Дискретная математика и математические вопросы кибернетики".
Научные работы С. В. в области дискретной математики и математической кибернетики получили всемирную известность, были переведены на многие языки и существенно определили облик современной математики.
Огромен вклад С. В. Яблонского в подготовку кадров в области математической кибернетики и дискретной математики. Параллельно с работой в Институте прикладной математики Сергей Всеволодович с 1954 г. вел преподавание на механико-математическом факультете МГУ . Здесь он разрабатывал и оттачивал спецкурсы "Введение в дискретную математику" и "Основы кибернетики". С 1963 г. он – профессор МГУ .
Сергей Всеволодович принял активное участие в организации в МГУ в 1970 г. факультета вычислительной математики и кибернетики (ВМиК ), где с 1971 г. создал и возглавил кафедру теории автоматов и математической логики, которая вскоре была переименована в кафедру математической кибернетики. Эта кафедра, которой бессменно руководил С. В. Яблонский, подготовила несколько сотен специалистов в области математической кибернетики и дискретной математики.
На факультете ВМиК Сергей Всеволодович начал чтение курсов "Введение в дискретную математику" и "Основы кибернетики" – уже как обязательных курсов для студентов. Разработанная им программа этих курсов легла позднее в основу курса "Дискретная математика", принятого для университетов всей страны, что оказало большое влияние на ознакомление с основами дискретной математики студентов-математиков всего Советского Союза.
Сергей Всеволодович организовывал Всесоюзные методические совещания по проблемам преподавания дискретной математики. До сих пор основным учебником по дискретной математике в нашей стране и некоторых других странах является изданный в 1979 и 1986 гг. учебник С. В. Яблонского "Введение в дискретную математику".
Много работал со студентами и аспирантами, ставя перед ними задачи достаточно широкого спектра. Под его руководством выполнено и защищено более 25 кандидатских диссертаций, среди его учеников – доктора наук, члены научных академий. Уже несколько поколений учеников и последователей Сергея Всеволодовича образуют созданную им мощную научную школу, объединяющую исследователей нашей страны и ряда других стран.
Активное участие принял в организации Международного математического центра им. С. Банаха . Он долгое время был членом совета этого Центра и организовывал проведение в Центре семестров по дискретной математике.
Много времени и сил посвятил С. В. Яблонский аттестации научных кадров, работая в специализированных советах по защите диссертаций и в ВАК СССР.
За большие заслуги в области научно-организационной деятельности Сергей Всеволодович был награжден орденом Трудового Красного Знамени.
Он работал в редколлегиях ряда научных журналов, до последних дней был членом редколлегии журнала "Дискретная математика".
С. В. Яблонского отличало предельно доброе и внимательное отношение к людям, острая восприимчивость и глубокое понимание новых идей, любовь к Родине, верность своему долгу ученого и гражданина России. В 1953 г. он вступил в ряды КПСС и до конца жизни остался верен своим убеждениям.
Сергей Всеволодович Яблонский (6 декабря 1924 - 26 мая 1998) - советский и российский математик, член-корреспондентом РАН (c 1968), один из основателей отечественной школы математической кибернетики. Автор ряда классических работ по проблемам синтеза, надёжности и контроля управляющих систем.
Биография
Родился 6 декабря 1924 года в семье студента-заочника физико-математического факультета 1-го Московского государственного университета Всеволода Яблонского (1901-1963) - будущего известного учёного, доктора технических наук, профессора, заслуженного деятеля науки и техники РСФСР.
Участник Великой Отечественной войны. Был призван в армию в 1942 году, с 1944 года - фронте, связист в танковой части.
Окончил механико-математический факультет (1950) и аспирантуру НИИ механики и математики (1953) МГУ, с 1963 года профессор МГУ. Специалист в области дискретной математики и математических вопросов кибернетики.
С 1953 года работал в Институте прикладной математики им. М. В. Келдыша РАН (ИПМ). Преподавал на кафедре высшей математики МФТИ.
В 1971 году создал при МГУ им. М. В. Ломоносова кафедру теории автоматов и математической логики (позднее переименованную в кафедру математической кибернетики ВМК МГУ), которую возглавлял до конца жизни. Член редколлегии «Математической энциклопедии».
Научная работа
Вся творческая жизнь С. В. Яблонского прошла в стенах ИПМ. В 1958 г. при активном содействии А. А. Ляпунова он создал в ИПМ отдел кибернетики и на протяжении 40 лет возглавлял его. С 1954 г. работал одновременно в Московском государственном университете им. М. В. Ломоносова, с 1970 г. возглавлял созданную им кафедру математической кибернетики на факультете вычислительной математики и кибернетики. Читавшиеся им в начале 1950-х годов на механико-математическом факультете МГУ курсы лекций и организованные им семинары по математическим вопросам кибернетики легли в основу современных университетских курсов по этой и смежным дисциплинам. В период становления кибернетики в нашей стране он был в первых рядах её пропагандистов. При его деятельном участии был начат в 1958 г. выпуск сборника «Проблемы кибернетики» - первого отечественного издания по кибернетике, продолжающегося и по сей день как сборник «Математические вопросы кибернетики». После отъезда А. А. Ляпунова в Новосибирск С. В. Яблонский становится руководителем общемосковского семинара по кибернетике в МГУ. До конца своих дней он являлся организатором всесоюзных и международных конференций по проблемам теоретической кибернетики. Продолжительное время деятельно работал на руководящих постах в Отделении математики АН СССР.
Основополагающее значение имеют работы С. В. Яблонского по алгоритмическим трудностям синтеза минимальных схем, по проблемам полноты функциональных систем, по надёжности и контролю управляющих систем.
Человек широких взглядов, он держал в поле зрения многие научные направления, старался поддержать всё перспективное, а в умении правильно оценить новое ему не было равных. Научная школа С. В. Яблонского, сложившаяся в Москве, вышла далеко за её пределы.
Перечень основных работ
Основные труды по теории управляющих систем, исследованию функциональных систем с операциями, вопросам контроля и надёжности управляющих систем, изучению алгоритмических трудностей синтеза управляющих систем.
- Яблонский С. В. О суперпозициях функций алгебры логики. - Матем. сб., 1952. - Т. 30 (72), № 2. - С. 270-360.
- Яблонский С. В. Функциональные построения в k-значной логике // Сборник статей по математической логике и её приложениям к некоторым вопросам кибернетики: Труды МИАН СССР. - М.: Изд-во АН СССР, 1958. - Т. 51. - С. 5-142.
- Яблонский С. В. Нижние мощностные оценки для сложности реализации функций из Pk схемами из функциональных элементов в произвольном базисе. Дискрет. матем., 6:4 (1994), с. 3-9
- Яблонский С. В. О построении тупиковых кратных экспериментов для автоматов. Тр. МИАН СССР, 133 (1973), с. 263-272
- Чегис И. А., Яблонский С. В. Логические способы контроля работы электрических схем. Тр. МИАН СССР, 51 (1958), с. 270-360
- Яблонский С. В. О классах функций алгебры логики, допускающих простую схемную реализацию.
УМН, 12:6(78) (1957), с. 189-196
- Яблонский С. В. О суперпозициях функций алгебры логики. Матем. сб., 30(72):2 (1952), с. 329-348
Монографии
- Функции алгебры логики и классы Поста. - М.: Наука, 1966.
- Предполные классы в многозначных логиках. - М.: МЭИ, 1997.
Учебники:
- Яблонский С. В. Введение в дискретную математику: Учебное пособие для вузов. - 6-е изд. - М.: Высшая школа, 2010. - 384 с. - ISBN 978-5-06-004681-6.
Награды и премии
Награждён орденом Трудового Красного Знамени (1974), двумя орденами Отечественной войны 2-й степени (1945), 2 орденами Красной Звезды (1944, 1945), орденом Славы 3-й степени (1944).
Лауреат Ленинской премии (1966)
В Советском Союзе исследования в области теории вычислений проводились в рамках теоретической кибернетики. Активное развитие этой области началось в 1950-х годах, когда электронные вычислительные машины были взяты на вооружение военными. Сергей Яблонский родился в 1924 году в Москве. Вернувшись с фронта после окончания Второй мировой войны, он продолжил изучать математику в Московском государственном университете. В 1953 году Яблонский защитил кандидатскую диссертацию под руководством Петра Сергеевича Новикова, который одним из первых в СССР начал заниматься проблемами вычислимости. Вместе с Алексеем Андреевичем Ляпуновым, также работавшим под руководством Новикова, Яблонский проводил в МГУ семинары по вопросам реализации булевых функций. Яблонский и Ляпунов организовывали и направляли всю исследовательскую деятельность в области теории вычислений.
Проблема выполнимости, упомянутая в четвертой главе, касается логических формул, т. е. формул, в которых основными операциями являются «И», «ИЛИ» и «НЕ». На самом деле любой вычислительный процесс можно представить в виде набора таких операций, или, другими словами, в виде схемы из элементов «И», «ИЛИ» и «НЕ». Одни задачи решаются схемами небольшого размера, для других необходимо огромное число элементов. Возникает понятие схемной сложности, и в начале пятидесятых Яблонский этим понятием заинтересовался.
Основатель теории информации – американский ученый Клод Шеннон – доказал, что некоторые логические функции имеют чрезвычайно высокую схемную сложность. Яблонский решил исследовать сложность построения таких функций. Хоть это и не очевидно, но если P и NP окажутся не равны, отсюда будет следовать, что некоторые легко формулируемые поисковые задачи нельзя решить при помощи маленьких схем.
Из результатов Шеннона вытекало, что сложность логических функций, заданных случайным образом, почти всегда близка к максимальной. Яблонский первым обратил внимание на этот факт и начал заниматься вопросом поиска сложных логических функций без использования случайных величин. Возникала ли при этом необходимость полного перебора всех функций? Ученый показал, что во время построения последовательности функций, имеющих сложную схемную реализацию, обязательно будут строиться и все остальные функции. Отсюда, в частности, следовало, что всякий метод построения некоторой сложной функции можно преобразовать таким образом, чтобы он строил любую другую функцию. Из того факта, что при построении сложных функций строятся также и все остальные, Яблонский сделал вывод о необходимости перебора. В 1959 году вышла его работа «О невозможности элиминации перебора всех функций из P 2 при решении некоторых задач теории схем».
Важность результатов Яблонского сложно переоценить; и все же интерпретировал он их не совсем верно. Ведь если при построении сложной функции можно получить и любую другую, то это еще не означает, что строить все остальные функции необходимо и другим способом сложную функцию никак не найти. На самом деле в работе Яблонского мало что говорилось о вычислительной сложности поиска самых сложных функций. Годом позже ученик Яблонского Юрий Иванович Журавлёв опубликовал статью с не менее впечатляющим названием – «О невозможности построения минимальных дизъюнктивных нормальных форм функций алгебры логики в одном классе алгоритмов», в которой тема вычислительной сложности также не затрагивалась. По сути ни та ни другая работа не касалась вопросов, связанных с проблемой равенства P и NP.
Советский Союз был социалистической страной с централизованной системой управления экономикой. В науке применялся аналогичный подход, и математические исследования находились под контролем различных комиссий, в которых Яблонский играл далеко не последнюю роль. Ученый полагал, что проблема перебора уже достаточно изучена в его собственной работе, и потому не приветствовал дальнейшие исследования в этом направлении, особенно если дело касалось вычислительной сложности и поиска алгоритмов. Далее мы увидим, что в результате такого подхода в шестидесятые годы в математическом сообществе случился раскол.
Андрей Николаевич Колмогоров
Андрей Колмогоров родился в 1903 году в Тамбове. В 1920 году он поступил в Московский университет, где поначалу интересовался не только математикой, но и пробовал свои силы и в истории, занимаясь изучением налогообложения на Руси в Средние века. Вопрос в его работе ставился такой: назначался ли налог сразу целому селению или же складывался из налогов, назначенных отдельных дворам? Проанализировав старинные налоговые записи, Колмогоров показал: расшифровать эти записи и объяснить правило, по которому они составлялись, будет гораздо проще в предположении, что налог назначался селению. На историческом отделении работу студента оценили очень высоко. Однако в ответ на вопрос, следует ли ему опубликовать полученные результаты, Колмогоров услышал: «У вашей гипотезы есть лишь одно обоснование. А для публикации требуется как минимум два», что в конечном итоге заставило его отвернуться от истории и посвятить себя науке, в которой одного доказательства было вполне достаточно. Колмогоров внес неоценимый вклад в самые разные области математики; это величайший математик XX века и один из крупнейших ученых в истории всей российской и мировой науки.
Существует забавная история – анекдот, по всей видимости, – о том, как Колмогоров спас теорию вероятностей от сталинского режима.
В тридцатых годах Сталин стремился укрепить свою власть. Все достижения науки и искусства, представлявшие потенциальную угрозу режиму, безжалостно уничтожались. Биологией заправляла группа псевдоученых, «приближенных к императору». В 1937 году очень многие генетики были арестованы как троцкисты и агенты фашистской разведки. В последующие десятилетия советская генетика – некогда предмет настоящей гордости – почти полностью прекратила свое существование.
Разобравшись с генетикой, «светочи науки» ополчились на теорию вероятностей за понятие независимых событий. Теория вероятностей занимается изучением шансов на тот или иной исход; к примеру, если одновременно бросить две игральные кости, то вероятность того, что в сумме выпадет пять очков, равняется одной девятой. Через понятие вероятности определяются и независимые события. Например, при подкидывании двух игральных костей число выпавших очков на одной никак не зависит от числа выпавших очков на другой. Все это плохо согласовывалось с марксистской философией, согласно которой все кругом взаимосвязано и взаимообусловлено.
Колмогорова вызвали наверх и упрекнули в том, что независимые события идут вразрез с идеями марксизма.
Ученый понимал, насколько важно подобрать верные слова: от того, что он скажет, зависит будущее советской математики. «Вы ошибаетесь», – начал он, и его собеседники тут же решили: «Попался!» Ведь критиковать линию партии – все равно что подрывать основы марксистского учения, и для Колмогорова это означало конец карьеры.
«Допустим, поп во время засухи молится о ниспослании дождя, – продолжал ученый. – На следующий день начинается дождь. Эти два события совершенно независимы». Что тут можно было возразить? Допустить даже самую отдаленную связь значило признать действенность религии, что было равносильно попытке дискредитировать учение Маркса. Так Колмогоров спас теорию вероятностей.
Рис. 5.3. Комикс про Дилберта. © Скотт Адамс, 2001. Публикуется с разрешения UNIVERSAL UCLICK. Все права защищены
Стремление проникнуть в суть вероятности и случайности привело Колмогорова к одной удивительно простой и в то же время гениальной идее. Рассмотрим три последовательности цифр:
999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999 999;
707 106 781 186 547 524 400 844 362 104 849 039 284 835 937 688 474;
982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097.
Выдавать одни девятки для генератора случайных чисел не очень-то естественно. Вторая последовательность, – как некоторые уже, наверно, догадались, – это начало дробной части квадратного корня из 1/2. А вот третья действительно была создана генератором.
Колмогоров придумал определять степень случайности последовательности в зависимости от длины ее самого короткого описания. Первая последовательность – это «51 девятка». Вторая – «1/√2». Описать третью можно, только повторив ее целиком: «982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097». Конечно, «описание» – понятие неформальное; Колмогоров формализовал его через понятие компьютерной программы.
Аналогичные идеи независимо друг от друга и от Колмогорова разработали также двое американских ученых: Рэй Соломонов (из Кливленда, а не из СССР, как можно было бы подумать по его фамилии) – чуть раньше Колмогорова, Грегори Хайтин – чуть позже. Однако Колмогоров и его последователи углубились в эту тему гораздо дальше, так что сложность, определяемую через длину описания, стали называть «колмогоровской».
Последовательность называется случайной, если самый короткий способ описать ее – это привести ее целиком, как в случае с нашим третьим примером.
Создать случайную последовательность нетрудно: просто выбирай каждое следующее число случайным образом – и все. Однако без случайных величин последовательность никогда не станет по-настоящему случайной. Алгоритм, не являющийся вероятностным, т. е. не использующий случайные числа, не способен строить случайные последовательности произвольной длины. Поэтому не стану утверждать, что последовательность
982 922 216 207 267 591 232 795 977 564 268 549 473 337 889 037 097
действительно является случайной: чтобы доказать это, мне пришлось бы проанализировать все возможные описания меньшей длины, а эта задача явно не из легких!
За понятием колмогоровской сложности стоит обширная и глубокая теория, которая находит применение в машинном обучении, анализе алгоритмов и в сложности вычислений. Именно колмогоровская сложность привела Леонида Левина – ученика Колмогорова – к проблеме равенства P и NP, хоть она и не связана с этой проблемой напрямую.
