РОССИЙСКАЯ АКАДЕМИЯ НАУК
С.-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ
МАТЕМАТИЧЕСКОГО ИНСТИТУТА
ИМ. В.А.СТЕКЛОВА
Лаборатория математической логики
Принципы развития теории алгоритмов
Реферат по истории науки аспиранта
Лифшица Юрия Михайловича
Научный руководитель ………………../ Ю.В.Матиясевич
д.ф.-м.н., член-корр. РАН
Преподаватель ………………../ А.Н.Соколов
д.ф. н.,
Принципы развития теории алгоритмов
Юрий Лифшиц
Содержание
Введение
Хронология теории алгоритмов
Современное состояние теории алгоритмов
Использование других наук в алгоритмах
Наиболее значимые применения алгоритмов
Идеи и техники в теории алгоритмовФормирование популярных направлений исследований
Стили проведения научных исследований
Заключение и выводы
Список источников
1. ВведениеВ этой работе мы хотим систематизировать факторы, влияющие на формирования плана активных исследований в теории алгоритмов. Как конкретные направления исследований становятся популярными, попадают в центр внимания, а потом постепенно утрачивают свою ведущую роль? Какими факторами определяется популярность исследовательских задач? На каких принципах основана оценка достижений ученых? Какие существуют стили работы для получения наиболее важных (в будущем) результатов. Для ответа на эти вопросы мы начнем со знакомства с хронологией основных достижений теоретической информатике. В следующем разделе мы опишем современное состояние исследований в теоретической информатике. Далее мы перечислим основные факторы, оказывающие влияние на оценку «важности» теорем и теорий. Следующий рассмотренный вопрос – стили проведения исследований. В заключении мы сформулируем темы, которые могут стать центральными в самом ближайшем будущем.
2. ХронологияIV-III века до н.э. Появление первых алгоритмов: Алгоритм Евклид для наибольшего общего делителя, решето Эратосфена.
1822 - Чарльз Беббидж приступил к созданию "разностной машины"
1926 – Борувка - первый алгоритм нахождения остовного дерева (далее Ярник, Прим и Крускал).
1936 - В Германии Конрад Зусе приходит к выводу, что программы, состоящие из битовых комбинаций, можно запоминать; он подает заявку на патентование метода автоматического выполнения вычислений с использованием "памяти комбинаций"
1936 – Алан Тьюринг, строгое понятие алгоритма (машина Тьюринга). Тезис Черча: любой алгоритм может быть представлен в виде машины Тьюринга.
1939 – Леонид Канторович – формулировка задачи линейного программирования, первый алгоритм для ее решения.
1945 - Джон фон Нейман (John von Neumann) в своем докладе по проектированию EDVAC (Electronic Discrete Variable Automatic Computer) ввел понятие запоминаемой программ
1947 – Георг Данциг создает симплекс метод
1948 – Альфред Тарский – алгоритм проверки истинности любого утверждения о вещественных числах в логике первого порядка.
1948 - Клод Шеннон опубликовал "Математическую теорию связи", заложив таким образом основу современного понимания коммуникационных процессов
1948 - Ричард Хемминг сформулировал способ обнаружения и корректировки ошибок в блоках данных
1952 – алгоритм архивирования Хаффмана
1954 – Сьюард - сортировка подсчетом (линейное время в среднем)
1959 - Джон Маккарти разработал LISP (list processing) - язык для использования в задачах искусственного интеллекта
1962 – Дэвис, Лоджеман, Лавлэнд – DLL алгоритм для SAT и других NP-полных задач.
1962 – Форд и Фалкерсон – полиномиальный алгоритм нахождения максимального потока.
1962 – Хоар – Quicksort (алгоритм быстрой сортировки)
1962 – Адельсон-Вельский и Ландис – AVL-деревья (балансированные деревья)
1964 – Дж.Вильямс – Heapsort (сортировка с помощью кучи)
1965 – Алан Робинсон – основание логического программирования.
1965 – Хартманис и Стернс: определение понятия «вычислительная сложность», зарождение теории сложности. Понятие массовой задачи?
1965 – Владимир Левенштейн - Введение редакторского расстояния
1969 – Штрассен – быстрый алгоритм перемножения матриц
1970 – Юрий Матиясевич – вычислительная неразрешимость решения диофантовых уравнений (решена 10ая проблема Гильберта).
1971 – Вапник и Червоненкис – метод опорных векторов (support vector machines и VC размерность).
1971-1972 - Кук, Левин, Карп – основание теории NP-полноты.
1975 – Джон Холланд – разработка генетических алгоритмов
1976 – Диффи и Хеллман – установление непосредственной связи между криптографией и теорией сложности.
1977 – Лемпель и Зив – алгоритм для архивирования текстов.
1976 – Кнут, Моррис и Пратт – линейный алгоритм поиска подстрок
1977 – Алгоритм Бойера-Мура поиска подстрок
1978 – Райвест, Шамир, Адлеман – разработка криптосистемы RSA.
1979 – Гэри и Джонсон – систематизация теории NP-полноты.
1979 – Леонид Хачиян – полиномиальный алгоритм решения задачи линейного программирования
1981 – Карл Померанц – метод квадратичного решета для разложения чисел на множители
1982 – Эндрю Яо – определение функции с секретом.
1982 – Тейво Кохонен – самоорганизующиеся карты (self-organizing maps)
1984 – Кармаркар – метод внутренней точки для задачи линейного программирования
1985 – Александр Разборов – Теорема Разборова (нижняя экспоненциальная оценка на сложность решения задачи о клике монотонными схемами).
1986 – Псевдослучайный генератор Блюма, Блюма и Шуба
1989 - Тим Бернерс-Ли предложил CERN (Европейскому совету ядерных исследований) проект World Wide Web
1989 – Голдвассер, Микали и Раков – определение доказательства с нулевым разглашением.
1991 – Корман, Лейзерсон и Райвест – «Введение в алгоритмы» - главная книга по алгоритмам во всем мире.
1992 – Ади Шамир - IP = PSPACE (важный результат в теории сложности, объясняющий, что два разных понимания сложности задачи на самом деле совпадают).
1992 – Арора, Сафра и Арора, Лунд, Мотвани, Судан, Шегеди – Теорема о вероятностно-проверяемых доказательствах (PCP-theorem).
1993 – МакМиллан – Символьный алгоритм верификации программ
1994 – Питер Шор - Квантовый алгоритм разложения чисел на множители.
1994 - В университете Южной Калифорнии Леонард Адлеман продемонстрировал, что ДНК может быть использована как вычислительное средство
1994 – Преобразование Берроуза-Вилера
1996 – Алгоритм Гровера для поиска на квантовом компьютере
2002 – Агравал, Кайал, Саксена, полиномиальный алгоритм проверки числа на простоту.
2004 – Алгоритм Вильямса – прорыв барьера 2^n для задачи о максимальном разрезе.
3. Современное состояние теории алгоритмов.3.1. Использование других наук в алгоритмах
Информатика и ее центральная область, теория алгоритмов, возникла недавно. И естественно, что она многое берет у старших наук-соседей.
Физика. Влияние физики в информатике проявилось только в последние годы и вызвало настоящий взрыв новых исследований. Центральным направлением, объединяющим эти науки, стало изучение нестандартных моделей вычислений. Как показал еще физик Ричард Фейнман, физические явления, такие как спин электрона, могут быть использованы для вычислений. Современные исследования показали, по-видимому, квантовые алгоритмы не сводятся к обычной (использующей биты) модели вычислений. Следовательно, пространство эффективно решаемых задач расширяется. Упомянем здесь также такие темы, как вычисления с вещественными числами (Real RAM), оптический компьютер и даже (!) бильярдные вычисления.
Теория вероятностей. Одна из наиболее применяемых математических теорий в информатике. Два ключевых направления: оценка времени работы алгоритма «в среднем», и вероятностные алгоритмы. Исследования в теории сложности показывают, что детерминированные алгоритмы не всегда дают наилучшие решение. Более того, на практике вероятностные алгоритмы могут работать заметно быстрее даже при наличии альтернативного детерминированного алгоритма (например, задача проверки на простоту).
Биология. Для решения самых трудных задач своей деятельности человек обращается за помощью к природе. Что делать, если мы хотим найти решение для таких трудных и неформализуемых задач, как классификация и распознавание образов? Посмотреть, как эта задача решается в природе – то есть человеческим мозгом! Так возникла идея симуляции и моделирования вычислительных способностей нейронов. Предложенная модель получила название нейронных сетей. Затем был сделан следующий шаг. Важно не только как человек решает конкретную задачу (младенцы довольно плохо приспособлены к жизни), важно с какой феноменальной скоростью человек обучается в течении своей жизни. Так возникла теория машинного обучения (machine learning).
Теория графов и комбинаторика. Современные компьютеры работают с дискретными данными. Наиболее простыми объектами такого рода являются натуральные числа, последовательности, конечные множества и графы. Поэтому их основные свойства, изученные в соответствующих разделах математики, используются в теории алгоритмов невероятно часто. Когда специалисты по алгоритмам дорастут до работы с более сложными объектами, наверное, следующие уровни математики найдут свое применение.
Математическая логика. Собственно, из нее и выросла теория алгоритмов. Мечтой математиков начала XX века было создание единого (вычислительного) метода решения математических проблем. К сожалению, как показал уже Тьюринг, существуют вычислительно неразрешимые задачи. Тем не менее, логика дала мощный аппарат выражения различных свойств математических объектов и формальные правила работы с этими свойствами. В современной теоретической информатике логика используется для разработки новых языков программирования, задач автоматической верификации программ и для изучения сложности вычислительных задач (proof complexity).
Функциональный анализ. Оказывается, что и непрерывная математика необходима в разработке алгоритмов. Это случается, в основном, при компьютерной обработке явлений, имеющих непрерывную природу. Это, конечно же, цифровая обработка аудио и видео записей. Такие широко используемые стандарты, как MPEG и JPG содержат идеи, взятые из свойств преобразования Фурье и активно используют дискретный аналог операции свертки.
3.2. Наиболее значимые применения алгоритмов
Первым прикладным направлением, по существу выделившим теорию вычислений в отдельное направление стали численное решение уравнений из физики, расчеты в атомной сфере и управление космическими кораблями и спутниками.
Следующим источником множества вычислительных задач стали вопросы оптимизации задачи в экономике. К основным достижениям стоит отнести формулировку задачи линейного программирования (Канторовича), симплекс-метод, алгоритмы Кармаркара и алгоритм Хачияна.
Успехи математической статистики и развитие измерительных приборов и рентгенов породили необходимость в алгоритмах автоматической диагностики и обработки данных томографии. Сейчас с огромной скоростью проводится внедрение компьютерной техники в самых разных направлениях медицины.
С ростом объемов информации возникла необходимость в эффективных механизмах ее хранения и использования. алгоритмы обработки запросов в базах данных относятся к числу наиболее широко применимых.
Как известно наибольший объем информации человек воспринимает зрением. Поэтому неудивителен большой интерес к алгоритмам обработки изображений, моделированию пейзажей и движения по воображаемой местности (виртуальная реальность). Огромные усилия тратятся на разработку все новых алгоритмов сжатия растровых изображений, аудио и видео потоков (MPEG4, JPEG).
Главным направлением развития информационных технологий последних двух десятилетий стал Интернет и распределенные вычисления. Теория алгоритмов здесь находит свое применение в задачах маршрутизации пакетов (TCP/IP и DNS) и поисковых системах. Небывалый успех системы Google стал, пожалуй, самым запоминающимся случаем, когда простая математическая идея (алгоритм PageRank) привела к феноменальному коммерческому успеху.
Особое значение играет решение задач, успех в которых нельзя строго сформулировать – так называемые задачи искусственного интеллекта. Перечислим лишь некоторые: автоматическое распознавание речи, отпечатков пальцев, лиц людей, системы распознавания свой - чужой, автоматическая классификация, автоматический контроль качества.
В конце концов, теория алгоритмов пришла к тому, что объектами обработки стали сами алгоритмы. Основными задачами являются автоматическая верификация и оптимизация программ и системы по распараллеливанию выполнения программ на многопроцессорных вычислительных системах.
Следующим направлением являются лингвистические алгоритмы: проверка орфографии, автоматический перевод, «разговаривающие» программы. Следующим шагом стала работа с грамматикой.
Наконец, компьютерам стали доверять все более и более важные задачи. Методы машинного обучения используются в разработке роботов (особенно заманчивой звучит создание футбольной команды роботов, способной выиграть у чемпионов мира 2050 года). Естественно ожидать, что время распространения устройств, оснащенных датчиками и способных самостоятельно принимать оптимальное решение, наступит очень скоро.
Наиболее популярным прикладным направление в самое последнее время стали исследования в биоинформатике: вычисление (восс
Одновременно с решением тех или иных вычислительных задач теория алгоритмов накапливает и систематизирует фундаментальные идеи и техники эффективных вычислений. Ниже перечислим список основных исследовательских направлений такого рода.
Прежде всего, необходимо ответить, как измерять эффективность алгоритмов? Первым ответом было число шагов выполняемых соответствующей машиной Тьюринга. После понимания неадекватности этой меры была предложена новая модель (RAM) дающая гораздо более точное приближение вычислительной сложности на практике. Кроме времени работы, полезно изучать и другие ресурсы, используемые при вычислениях. Это объем используемой компьютерной памяти и (это стало особенно важным в последнее время) количество раундов и объем передаваемых сообщений в распределенных вычислениях. Также, мы получим разное понимание трудоемкости алгоритмов, рассматривая сложность в среднем или сложность в худшем случае.
Первой фундаментальной идей теории вычислений стало наблюдение, что почти каждому алгоритму соответствует специально подобранная структура данных, которая позволяет работать с данными максимально эффективно. Таким образом, удалось выделить и изучить отдельно базовые задачи (сортировка, удаление, вставка, поиск), а затем использовать эти конструкции как составные части более сложных алгоритмов.
Следующей идеей большого значения является рекурсия. Многие алгоритмы наиболее естественно описываются при помощи самих себя. Конечно, это сразу порождает огромные сложности. Как известно, никакая проверка корректности алгоритмов (даже установления факта окончания работы) в общем случае не может быть решена. Тем не менее, рекурсия является одним из наиболее часто используемых приемов при разработке новых алгоритмов.
Теория сложности выделила класс задач, которые имеют переборное решение, но до сих пор не решенные эффективно (класс NP). В последнее время был найден целый ряд идей и техник (локальный поиск, рандомизация, модифицированная рекурсия), которые позволили в ряде случаев существенно ускорить экспоненциальный перебор (например, с 2^n до 1.331^n для задачи 3-SAT). Таким образом, атака задач, являющихся труднорешаемыми с точки зрения теории сложности может привести к новым нетривиальным идеям теории алгоритмов.
Как сформулировать задачу, которую невозможно сформулировать? Например, как объяснить компьютеру отличие всевозможных способов рукописного написания цифры «1» от столь же разнообразных способов написания «2»? С помощью примеров! Теория машинного обучения выработала следующую схему работы с задачами искусственного интеллекта.
Собрать коллекцию начальных данных с известными ответами
Разделить эту коллекцию на две группы: учебную и тестовую
Выбрать общий вид решающего правила
Подобрать коэффициенты и характеристики решающего правила на учебной коллекции, дающие максимальное совпадение с правильными ответами
Проверить качество работы полученного алгоритма на тестовой коллекции
В случае неудовлетворительных результатов вернуться к шагу 3.
4. Факторы определения «важности» задач и результатов.По этим признакам можно определить текущие популярные темы:
Тематика работ, за которые присуждаются научные премии
Тематика монографий, публикуемых в крупнейших издательствах
Тематики, наиболее широко представленные на конференциях общего профиля
Темы специализированных конференций и школ
На выбор направлений научной деятельности влияют следующие факторы:
Возможность найти государственное финансирование
Наличие крупных компаний, заинтересованных в данном направлении
Принадлежность темы к наиболее популярным на данный момент
Возраст темы. Объем уже проведенных исследований
Масштаб текущих исследований: количество ученых, лабораторий, конференций, журналов, вовлеченных в данное направление
Связи данного направления с другими темами и науками
«Цена входа»: необходимый объем предварительных знаний для начала оригинальных исследований
При выборе исследовательской задачи обычно учитывают:
Собственный внутренний интерес к задаче
Интерес исследовательского сообщества к задаче
Прикладной интерес к решению задачи
Предысторию исследований по задаче
Автора задачи. Участников предыдущих исследований
Связи данной задачи с другими задачами и направлениями
Масштаб задачи. Оцениваемая сложность задачи.
Вхождение задачи в рамки более широкого исследовательского вопроса
Возможность расширения и обобщения решения данной задачи
Принадлежность задачи сразу к нескольким научным направлениям
Возможность изложить суть задачи (и особенно результата) на макимально простом и доступном языке
Механизмы, используемые для распространения задач в научной среде:
Обзорные научные статьи
Бюллетени научных ассоциаций (например, EATCS)
Открытые вопросы в монографиях
«Чтение по диагонали» трудов крупнейших конференций и важнейших журналов
Работа в соавторстве
Рабочие школы-семинары (workshops, например семинары в Дагштуле).
Разделы «направления для дальнейшей работы» в научных статьях
(Редко) публикация отдельных списков открытых проблем
6. Стили проведения научных исследований.
Пожалуй, нет единого максимально эффективного метода по выбору исследовательских задач и направлений. Напротив, можно выделить несколько стилей.
Решатель задач. В этом методе исследования заключаются в выборе строго-сформулированной задачи с известной ценностью и технической атаке на задачу. После определенного периода времени (скажем две недели) либо результат достигнут, либо усилия прекращаются и идет поиск новой задачи. Для такого подхода следующие факторы влияют на успех:
Хорошо налаженный механизм нахождения задач
Выбор задач с относительно невысокой «ценой входа»
Мощная техника доказательств
Разработчик теории. Здесь основной целью является накопить, систематизировать и обобщить максимальное число фактов объединенных общим понятием или исследовательским вопросом. Факторами успеха здесь будут:
Выбор важной, значимой и признаваемой темы
Работа в направлении внешних целей: прикладных результатов или смежных тем
Эстетическая привлекательность (стройность) разрабатываемой теории
Естественность исследуемых вопросов
Создатель понятия. Пожалуй, наиболее редкий и трудный тип исследований. Исследуя неформализованные явления, информационные отношения и прикладные задачи, выделить абстрактную модель, которая отражает суть этих явлений, но при этом максимальна проста. Здесь речи не идет о решении научной задачи, это гораздо труднее – расширить язык науки. Факторы, позволяющие добиться успеха в этом направлении:
Выбор, научного направления, находящегося в хаосе и неопределенности
Практическая важность реальных явлений
Ясное понимание цели, для которой будет использоваться создаваемый научный язык
Глубокое знание разнообразных формальных описательных средств
Интуиция, позволяющая выделить главное и отбросить несущественное
Вера в свою модель и способность популяризировать новый подход
Строитель мостов. По целому ряду причин в научной среде особенно ценятся результаты, полученные на стыке разных областей или даже наук. Такие открытия часто приносят новое понимание явлений, которое было бы невозможно внутри отдельных направлений. Такого рода результаты невозможно получить, не имея:
Широкой эрудиции
Научных интересов и исследовательской работы в принципиально разных областях
Желания строить аналогии между разными тематиками
Генератор вопросов. Все научная индустрия нацелена на решение тех или иных задач. Но прежде чем начать их решать, необходимо сформулировать цели, что, как известно, составляет половину работы. Порождение по-настоящему важных вопросов представляет собой целое искусство. Тут важны:
Постоянное и неуемное любопытство
Видение глобальных целей
Развитое чувство вкуса
Авторитет в научной среде
Понимание нужд приложений и целей научного движения
7. ЗаключениеПопытаемся еще раз сформулировать отличительные признаки выдающихся результатов. Каждый из нижеперечисленных факторов способствует широкому признанию результата:
Решение строго сформулированной и долго остающейся нерешенной проблемы
Введение нового определения, которое оказалось удобным для описания многих явлений и понятий
Первый предложенный метод для какой-либо проблемы
Первая работа в определенном направлении
Систематизация накопленных фактов в единую теорию.
Упрощение доказательств важных теорем, нахождение альтернативных доказательств
Опровержение/доказательство гипотез
Изучив список самых значимых результатов теории алгоритмов, и посмотрев на время, когда были сделаны эти открытия, можно сделать интересный вывод. Почти в каждом случае эти понятия и алгоритмы были предложены до того, как соответствующий раздел теоретической информатики вышел на пик своей популярности. То есть, для проведения наиболее важных исследований стоит ориентироваться не на те области, которые сейчас вызывают наибольший интерес, а на те, которые еще только могут попасть в центр развития теории.
Поэтому так интересно попытаться сделать прогноз и угадать основополагающие темы исследований ближайшего будущего. Укажем здесь три направления, которые представляются очень перспективными.
Алгоритмы, которые обрабатывают объекты «второго уровня сложности». Для вычислительных задач, работающих с базовыми математическими объектами, такими как строки, элементы упорядоченных множеств, натуральные числа, (взвешенные) графы, конечные автоматы, матрицы, построено немало эффективных алгоритмов. Напротив, автоматическая обработка более сложных объектов, непредставимых напрямую этими элементарными понятиями, еще только становиться предметом изучения. Сейчас мы пытаемся подобрать эффективные алгоритмы обращения с такими понятиями, как программа (автоматическая оптимизация, распараллеливание и верификация), Интернет (поиск и сортировка сайтов по значимости), тексты на естественных языках (автоматический перевод и проверка грамотности) или геном человека.
Алгоритмы, использующие базы знаний. Технологии настоящего позволяют собрать уйму интереснейшей информации о человечестве: структуру взаимоотношений (социальные сети), полную статистику покупок, музыкальные, книжные и кино-предпочтения, список и динамику поисковых запросов каждого человека. Все эти огромные объемы данным пока остаются сравнительно бесполезными. Однако представляется, что в самое ближайшее время удастся наладить автоматическое извлечение из таких данных каких-то общих закономерностей и шаблонов, и использовать их для предсказания будущих событий в различных сферах.
Продвижение на пути к понимаю вопросов на естественном языке. Сейчас все программы способны обрабатывать входные данные лишь строго-определенного математического типа. В то время как абсолютным идеалом стала бы машина, способная ответить на любой человеческий вопрос. Первым шагом на этом пути должно стать выделение некого промежуточного языка запросов, который, если и не совпадает с естественным, то хотя бы существенно выразительней языка запросов, которым мы пользуемся в поисковых системах в Интернете.
Отметим, что для третьего направления большую роль может сыграть тесное сотрудничество со специалистами по лингвистике. Вполне возможно, что лингвистика станет следующим стратегическим партнером теории алгоритмов и уже сейчас стоит задуматься о самом тесном сотрудничестве с представителями этой науки.
В заключение скажем, что любой путь к выдающимся результатам невозможен без четкого понимания цели, внутреннего желания ее достичь, концентрации, получения удовольствия от проводимых исследований и постоянного общения с научной средой.
Список источников
Theory of Computation: Goals and Perspective
http://eccc.hpi-web.de/eccc/info/DISCUSSIONS/GoalsPerspectives.html
Papers in Computer Science [Wikipedia]
http://en.wikipedia.org/wiki/List_of_important_publications_in_computer_science
ACM/IEEE Computing Curricula 2001
http://se.math.spbu.ru/cc2001/
Most cited articles in Computer Sciencehttp://citeseer.ist.psu.edu/articles.html
Премия Неванлинны
http://www.mathunion.org/medals/Nevanlinna/Prizewinners.html
Ривест Р., Кормен Т., Лейзерсон Ч. “Алгоритмы: построение и анализ”Michael Nielsen: Principles of Effective Research
http://www.qinfo.org/people/nielsen/blog/archive/000120.html
А.Разборов. Theoretical Computer Science: взгляд математика.http://www.computerra.ru/offline/2001/379/6782/
Лэнс Фортноу. Мои любимые теоремы.
http://weblog.fortnow.com/2006/01/favorite-theorems-preview.html
Мультимедиа продукт "История Информатики"
http://cshistory.nsu.ru
Computer Sciences - основные вехи ("Timeline of Computing History", Computer, Vol. 29, No.10 Translated from the original English version and reprinted with permission (IEEE))
http://www.dvgu.ru/meteo/PC/ComputerHystor.htm
History of Algorithms
http://cs-exhibitions.uni-klu.ac.at/index.php?id=193
Timeline of algorithms
http://en.wikipedia.org/wiki/Timeline_of_algorithms