Колмогоров теория алгоритмов кратко

Обновлено: 07.07.2024

Определение.Теория алгоритмов – раздел математики, который изучает общие свойства алгоритмов. Проблема теории – построение алгоритма, обладающего заданными свойствами. Такую проблему называют алгоритмической.

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

Среди других определений рассматривают определение Колмогорова.

Определение.Алгоритм – всякая система вычислений по определенным данным, которые после числа шагов приводят к решению задачи.

По Маркову: Алгоритм – точное предписание, определенный вычислительный процесс, варьирует исходные данные к результату.

Определения не являются математически строгими и характеризуют набор свойств алгоритма.

Дискретность информации. Каждый алгоритм имеет дело с входными, промежуточными, выходными данными, которые представлены в виде конечных слов в некотором формате.
Дискретность работы алгоритма. Алгоритм выполняется по шагам. На каждом шаге выполняется только одна операция.
Выполнимость операций. В алгоритме не должно быть невыполнимых операций.
Конечность алгоритма. Описание алгоритма должно быть конечным.
Детерминированность алгоритма. Каждый шаг алгоритма строго определен. После каждого шага указывается какой шаг сделать следующим или указывается, что алгоритм должен закончить работу.
Массовость алгоритма. Алгоритм должен решать задачи из данного класса задач. Если найдется задача, для которой алгоритм не применим, то последовательность нельзя назвать алгоритмом.

С развитием науки появились задачи, для которых не были найдены методы решений. Отсутствие алгоритма: недостаточность знаний или решения для алгоритма не существует. Для решения этой проблемы введена вычислительная функция. Пусть есть алгоритм α. Областью применимости α называют те объекты, которым он принадлежит. Говорят, что α вычисляет функцию f, если его область совпадает с D(f) и алгоритм α переработал элемент х их своей области применимости в область f(х).

Функция f(х) называется вычислимой, если существует вычисляемый ее алгоритм. Данное определение не является строгим. Математики Клини и Черч строго определили математические функции, названные примитивно-рекурсивными. Черч высказал гипотезу, что множество рекурсивных совпадает со множеством вычислительных функций. Это получило название тезиса Чеча. Математики Пост и Тьюринг ввели понятие математической машины- абстрактная машина, которая механически вычисляет. Тезис Тьюринга: Для всякой вычислительной функции может быть построена машина Тьюринга. Для всякой рекурсивной функции может быть построена машина Тьюринга. Практический опыт показывает, что тесты являются верными, нет ни одного опровержения.

Цели и задачи теории алгоритмов

Обобщение результатов позволяет выделить цели и соотнесенные задачи:

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

Критерием качества называют признак, позволяющий оценивать качество разработанного алгоритма. Таким критерием является сложность. Чтобы оценка сложности была объективной, необходимо, чтобы оценка была количественной.

Теоретики, оценивая сложность алгоритма, строят математическую модель машины Тьюринга. Тогда количество шагов для машины Тьюринга определяет его сложность.

Среди других определений рассматривают определение Колмогорова.

Определения не являются математически строгими и характеризуют набор свойств алгоритма.

Дискретность информации. Каждый алгоритм имеет дело с входными, промежуточными, выходными данными, которые представлены в виде конечных слов в некотором формате.
Дискретность работы алгоритма. Алгоритм выполняется по шагам. На каждом шаге выполняется только одна операция.
Выполнимость операций. В алгоритме не должно быть невыполнимых операций.
Конечность алгоритма. Описание алгоритма должно быть конечным.
Детерминированность алгоритма. Каждый шаг алгоритма строго определен. После каждого шага указывается какой шаг сделать следующим или указывается, что алгоритм должен закончить работу.
Массовость алгоритма. Алгоритм должен решать задачи из данного класса задач. Если найдется задача, для которой алгоритм не применим, то последовательность нельзя назвать алгоритмом.

Цели и задачи теории алгоритмов

Обобщение результатов позволяет выделить цели и соотнесенные задачи:

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

Создание и применение электронных цифровых вычислительных машин базировалось на мощном фундаменте разработок отечественных математических школ, сделавших значительный вклад в мировую науку. Стремительный старт ядерной и космической программ, выполнение которых обеспечило СССР стратегический паритет в 50-60-х годах XX в., стал возможен благодаря важнейшим результатам, полученным математиками в течение предвоенного десятилетия.

С другой стороны, развитие самой математики после появления и начала применения компьютеров для решения вычислительных и невычислительных задач получило новые стимулы.

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

Андрей Николаевич Колмогоров родился 12 (25) апреля 1903 г. в г. Тамбове. В 1925 г. он окончил Московский университет. А.Н. Колмогоров принадлежал к московской математической школе, возглавлявшейся академиком Н.Н. Лузиным. Первые студенческие работы Андрея Николаевича были опубликованы в 1923-1925 гг. в журнале Fundamenta mathematicae, что говорило об их высоком научном уровне.

В звании профессора А.Н. Колмогоров был утвержден в 1930 г., а ученую степень доктора физико-математических наук получил в 1935 г. В январе 1939 г. А.Н. Колмогоров был избран действительным членом АН СССР по Отделению математических и естественных наук (математика).

В теории множеств, продолжая работы Н.Н. Лузина, А.Н. Колмогоров заложил основы построения систем операций над множествами, опубликованные им в Математическом сборнике еще в 1928 г.

В теории функций студенческая работа 1923 г., устанавливающая существование почти всюду расходящегося ряда Фурье, сделала А.Н. Колмогорова известным всему миру.

В топологии А. Н. Колмогоров (параллельно с американским ученым Дж. У. Александером) предложил фундаментальные основы теории когомологий.

Вклад А. Н. Колмогорова в общую теорию динамических систем и классическую механику был охарактеризован на Международном математическом конгрессе в 1954 г. в Амстердаме как важная историческая веха в развитии науки. В области теории динамических систем А.Н. Колмогоров открыл новый метод, позволяющий описывать возмущения условно-периодических движений, который считается одним из крупнейших достижений математики ХХ века. Метод Колмогорова-Арнольда-Мозера (КАМ) играет важную роль в нелинейной механике.

В теории алгоритмов А.Н. Колмогорову принадлежат определение общего понятия алгоритма и создание теории сложности конструктивных объектов. Результаты, связанные с дискретными автоматами и конечными алгоритмами, были доложены А.Н. Колмогоровым на Четвертом Всесоюзном математическом съезде в 1963 г. и во многом определили дальнейшее развитие в этой области. Он продолжил исследование марковской теории нормальных алгоритмов, а именно тех алгоритмов, которые подлежат реализации с помощью цифровых вычислительных машин.

В математической логике А.Н. Колмогоров одним из первых изучал интуиционистскую логику как предмет математического исследования. А.Н. Колмогоров оказал огромное влияние на развитие российских школ математической логики.

При исследовании знаменитой тринадцатой проблемы Гильберта о суперпозициях Андрей Николаевич установил в 1956 г. возможность представления любой непрерывной функции (от сколь угодно большого числа переменных) в виде суперпозиции непрерывных функций трех переменных. Одновременно он выдвинул идеи, позволившие его ученику В.И. Арнольду (тогда студенту-третьекурснику) понизить в этом результате число переменных с трех до двух и тем самым окончательно решить 13-ю проблему Гильберта. При этом ответ оказался противоположным тому, который ожидался Д. Гильбертом в 1900 г. при постановке проблемы. Как известно, Д. Гильберт предложил доказать, что конкретная непрерывная, даже алгебраическая функция, не представима в виде суперпозиции непрерывных же функций двух переменных. В 1957 г. А.Н. Колмогоров усилил результат В.И. Арнольда, показав, что любую непрерывную функцию от произвольного числа переменных можно представить в виде суперпозиции непрерывных функций одного переменного и единственной функции двух переменных — функции сложения.

А.Н. Колмогоров принимал непосредственное участие в решении ряда практических задач. Так, Институт физики атмосферы РАН вырос из небольшой лаборатории турбулентности, созданной в 1946 г. по инициативе А.Н. Колмогорова в составе Института теоретической геофизики АН СССР и до 1949 г. им возглавляемой. Директором Института океанологии АН СССР был ученик А.Н. Колмогорова член-корреспондент АН СССР А.С. Модин.

Еще в 1936 г. по инициативе А. Н. Колмогорова его ученик А.А. Ляпунов занялся статической обработкой опытных данных по расщеплению гибридов. Это на долгие годы определило применение математических методов для решения задач генетики, как во времена гонений на генетику в 40-х годах, так и позже, во время действительно серьезных событий в науке, связанных с открытием генетического кода.

А. Н. Колмогоров был примером редкого сочетания математика и естествоиспытателя, теоретика и практика. Одновременно он был философом науки (философии математики) и ее популяризатором.

На механико-математическом факультете МГУ А.Н. Колмогоров заведовал кафедрами теории вероятностей (с 1935 г.), математической статистики (с 1976 г.), математической логики (с 1980 г.). В 1954-1958 гг. А.Н. Колмогоров был деканом механико-математического факультета МГУ.

Основной тезис А.Н. Колмогорова состоял в том, что кибернетика — это не наука, а научное направление. В составе этого направления он рассматривал математическую лингвистику, указывая, что возможны два понимания этой области математики. Первая — это теория абстрактного формирования языка, близкая к математической логике и теории алгоритмов. Вторая — применение математических методов в обычной (традиционной) лингвистике. Вклад А.Н. Колмогорова в развитие семиотики, как одной из составляющих кибернетического направления, а в настоящее время — информатики, обогатил оба указанных выше подхода.

В мировой науке, чтобы отметить достижения в тех областях, которые не охватываются Нобелевскими премиями, были учреждены Бальцановские премии. В 1963 г. состоялось первое присуждение Бальцановской премии по математике, и ее лауреатом стал А.Н. Колмогоров. Это была высшая оценка вклада А.Н. Колмогорова в мировую науку.

Андрей Николаевич Колмогоров умер 20 октября 1987 г. в Москве.

О жизни и деятельности А. Н. Колмогорова имеются воспоминания его учеников и коллег:

Была ли встреча с самым дорогим вам человеком случайной, или виной тому была какая-то скрытая причина? А что насчёт странного вчерашнего сна – это были только случайные метания синапсов мозга, или он раскрыл что-то глубокое по поводу вашего подсознания? Возможно, сон пытался рассказать вам что-то о вашем будущем. Возможно, что и нет. Имеет ли тот факт, что ваш близкий родственник заболел опасной разновидностью рака, какой-то глубокий смысл, или же это просто последствия случайных мутаций ДНК?

В нашей жизни мы часто задумываемся над закономерностями происходящих вокруг нас событий. Мы задаёмся вопросом, случайны ли наши жизни, или у них есть какой-то смысл, уникально истинный и глубокий. Я, как математик, часто обращаюсь к числам и теоремам за идеями по поводу подобных вопросов. И так получилось, что я кое-что узнал о поиске смысла в закономерностях жизни благодаря одной из самых глубоких теорем математической логики. Эта теорема, проще говоря, демонстрирует, что в принципе невозможно узнать, является ли объяснение закономерности наиболее глубоким или интересным из всех объяснений. Точно так же, как в жизни, поиск смысла в математике ничем не ограничен.

Небольшая прелюдия. Рассмотрим следующие три строки символов.

2. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

В начале 1960-х американский подросток Грегори Хайтин, всемирно известный русский [и советский] математик Андрей Николаевич Колмогоров, и пионер информатики Рэй Соломонов независимо друг от друга сформулировали способ измерения сложности последовательностей символов. Их идеи стали называть теорией сложности Колмогорова или алгоритмической теорией информации. Они постулируют, что сложность строки определяется длиной наикратчайшей компьютерной программы, способной её выдать. То есть, возьмём строчку, и поищем самую короткую компьютерную программу, которая её выдаёт. Программа – один из видов описания строки. Если кратчайшая из таких программ окажется очень короткой, тогда в строке есть простая закономерность, и она не очень сложная. Мы говорим, что в такой строке мало алгоритмическое содержание. И наоборот, если для выдачи строки требуется длинная программа, тогда строка сложная, и её алгоритмическое содержание больше. Для любой строки необходимо искать кратчайшую программу, выдающую такую строку. Длина такой программы называется Колмогоровской сложностью строки.

Давайте вернёмся к трём первым строчкам. Первые две строки можно описать при помощи относительно коротких компьютерных программ:

1. Вывести “100” 30 раз.

2. Вывести первые 25 простых чисел.

Колмогоровская сложность первой строки меньше Колмогоровской сложности второй строки, поскольку первая программа короче второй. Что насчёт третьей? У этой строчки нет очевидных закономерностей. Тем не менее, можно написать дурацкую программу, выводящую эту последовательность:

3. Вывести “38386274868783254735796801834682918987459817087106701409581980418”

Мы могли бы попытаться использовать удивительные возможности современных компьютеров, чтобы найти закономерность и кратчайшую программу. Разве не было бы замечательно, если бы существовал компьютер, способный просто вычислить Колмогоровскую сложность любой строки? Такой компьютер принимал бы на вход строку, и выводил бы длину кратчайшей программы, способной выдать эту строку. Конечно же, со всеми этими новомодными штучками вроде ИИ, глубинного обучения, больших данных, квантовых вычислений, и т.п., должно быть легко создать такой компьютер.

Увы, такой компьютер создать невозможно! Пусть современные компьютеры и весьма мощны, эта задача невыполнима. Таково содержание одной из глубочайших теорем математической логики. Теорема, по сути, говорит, что Колмогоровскую сложность строки невозможно вычислить. Не существует механического устройства, определяющего размер наименьшей программы, выдающей заданную строку. Дело не в том, что наш текущий уровень компьютерных технологий не дотягивает до задачи, или что мы недостаточно умны для того, чтобы написать такой алгоритм. Было доказано, что сама идея описание и вычисления демонстрирует, что компьютер в принципе не в состоянии выполнить такую задачу для любой строки. И если компьютер, возможно, способен на поиски определённых закономерностей в строке, он не способен найти наилучшую закономерность. Мы, возможно, и найдём короткую программу, выводящую определённую последовательность, но всегда может существовать ещё более короткая. Мы никогда об этом не узнаем.

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

Парадокс интересных чисел связан с утверждением, что все натуральные числа интересные. 1 – это первое число, и это интересно. 2 – первое чётное число. 3 – первое нечётное простое число. 4 – интересное число, потому что 4 = 2 × 2 и 4 = 2+2. В таком роде можно продолжать дальше, и находить интересные свойства многих чисел. В какой-то момент мы можем встретить число без интересных свойств. И мы можем назвать это число первым неинтересным номером – но это само по себе уже интересное свойство. В итоге неинтересные числа тоже оказываются интересными!

Самое маленькое число, которое нельзя описать меньше, чем пятнадцатью словами [The smallest number that cannot be described in less than 15 words]

Для описания числа требуется 15, 16 или даже больше слов. Его нельзя описать 12, 13 или 14 словами. Однако, вот в чём проблема: приведённая выше фраза описывает это число при помощи 10 слов [по-английски – 12 слов / прим. перев.]. Наше описание числа противоречит описанию числа – вот вам и парадокс.

В парадоксе интересных чисел и в парадоксе Берри мы приходим к противоречиям, предполагая существование точного способа описания чего-либо. Точно так же, доказательство невычислимости Колмогоровской сложности вытекает из того, что если бы оно было вычислимым, мы пришли бы к противоречию.

То, что Колмогоровская сложность невычислима – это результат из чистой математики, и мы не должны путать этот идеальный мир с куда как более сложной и беспорядочной реальностью. Однако существуют некоторые общие моменты, связанные с Колмогоровской сложностью, которые мы можем привнести в реальный мир.

Много раз мы сталкивались с тем, что казалось нам совершенно хаотичным. Случайность нервирует нас, и мы ищем закономерности, частично устраняющие хаос. Если мы находим закономерность, остаётся неясным, является ли она лучшей закономерностью, объясняющей наши наблюдения. Мы можем задаться вопросом – существует ли более глубокая закономерность, дающая лучшее объяснение. Теория Колмогоровской сложности учит нас тому, что на базовом уровне не существует гарантированного способа определить наилучшую закономерность. Мы просто никогда не узнаем о том, является ли найденная нами закономерность наилучшей.

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

Реальный мир добавляет сложности. Если в мире строк и компьютерных программ ошибок нет, в реальном мире можно совершить ошибку. Мы легко узнаем, выводит ли какая-то определённая программа строку, или нет. И хотя мы, вероятно, не сможем определить оптимальную программу для вывода определённой строки, мы сможем определить, выводит ли она требуемую строку. А реальный мир, в отличие от этого, гораздо более сложный. Нам может показаться, что мы видим последовательность, когда её, на самом деле, нет.

Наше понимание наших поисков смысла начинает оформляться. Мы презираем случайности и обожаем закономерности. Мы биологически запрограммированы находить закономерности, объясняющие то, что мы видим. Но мы не можем быть уверены, что найденная нами закономерность будет правильной. Даже если бы мы каким-то образом могли гарантировать отсутствие ошибки, и достигли бы совершенства, подобного компьютерному, где-то всё равно всегда может находиться ещё более глубокая истина. Это напряжение подпитывает нашу любовь к литературе, театру и кино. Когда мы читаем роман или смотрим пьесу, автор или режиссёр представляет нам последовательность событий с общей темой, закономерностью или моралью. Литература, пьесы и кино предлагают нам великолепный способ убежать от обычно непонятного и бессмысленного хаоса, встречающегося нам в окружающем мире. Очень хорошая литература идёт дальше, и оставляет нам возможности многих интерпретаций. Мы лицом к лицу встречаемся с невычислимостью Колмогоровской сложности.

Это напряжение также определяет, как мы проживаем наши жизни. Путешествуя сквозь якобы случайные события, мы ищем закономерности и структуру. Жизнь полна взлётов и падений. Есть радость влюблённости, веселого времяпрепровождения с детьми, ощущения великих достижений по окончанию сложной работы. Есть боль разрушающихся отношений, агония неудачи после активных попыток выполнить задачу, трагедия смерти любимого. Мы пытаемся искать во всём этом смысл. Мы презираем чувство полной случайности и идею, что мы просто следуем хаотичным, незамысловатым законам физики. Мы хотим знать, нет ли в окружающем мире какого-то смысла, цели, значимости. Нам нужна волшебная история жизни, и мы рассказываем себе истории.

Иногда эти истории просто ложны. Иногда мы обманываем себя и окружающих. А иногда мы правильно определяем закономерности. Но даже когда история правдива, она не обязательно будет наилучшей. Мы никогда не будем уверены, что в глубине не лежит ещё более базовая и точная история. Старея и впадая в тоску, мы приобретаем определённые идеи по поводу Вселенной, недоступные нам раньше. Мы находим улучшенные закономерности. Возможно, мы начинаем видеть вещи яснее. Или нет. Мы никогда не узнаем. Но мы знаем, что поиски гарантированно не закончатся.

Нозон Яновски – доктор наук в математике, работает в Образовательном центре городского университета Нью-Йорка, профессор информатики в Бруклинском колледже того же университета.

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

Как говорили ученые, работавшие в этой же области,

система, введенная Колмогоровым, превратила теорию вероятностей в строгую математическую дисциплину.

Поставленные вопросы постепенно обрастали ответами, параллельно с которыми из-за отсутствия стройной системы случались различные парадоксы.

Математические методы современной теории вероятностей активно используются квантовой механикой и родственными ей науками. А квантовая теория — это основа понимания микромира, без нее большинство достижений науки последних десятилетий было бы невозможно

Ученый наделил теорию всеми необходимыми элементами, чтобы ее можно было назвать математической дисциплиной.

Ученый дал изучаемым объектам и их основным отношениям названия, а также заложил фундамент в виде аксиом, почти как в алгебре или геометрии. Аксиомы зафиксировали постулаты и правила, а выводы стали возможными исходя из установленных теорем.

С помощью развитых Колмогоровым методов появилась возможность решать самые разнообразные прикладные задачи. Исследования эти выполнялись в самых разных областях самим Андреем Николаевичем и его последователями. Одной из таких работ стало дополнительное подтверждение знаменитого генетического закона Менделя.

Краткая биография

Андрей Николаевич Колмогоров родился 12 (25) апреля 1903 года в Тамбове в семье агронома. Рано потерял родителей, воспитывался сестрой матери. Окончил частную гимназию, в 1920-м поступил на математическое отделение Московского университета. В 1930-м Колмогоров стал профессором этого университета, с 1933 по 1939 год был директором Института математики и механики, руководил кафедрой теории вероятностей механико-математического факультета и Межфакультетской лабораторией статистических методов. В 1935 году ему присвоили степень доктора физико-математических наук, в 1939-м он был избран действительным членом Академии наук СССР. В 1941 году за работы по теории вероятностей Колмогорову была присуждена Сталинская премия. В середине 1960-х годов под его руководством проходила модернизация системы среднего математического образования. Удостоен многочисленных премий, почетный член многих иностранных академий и научных обществ. Последние годы жизни заведовал кафедрой математической логики. Скончался 20 октября 1987 года в Москве.

Читайте также: