РОССИЙСКАЯ АКАДЕМИЯ НАУК
С.-ПЕТЕРБУРГСКОЕ ОТДЕЛЕНИЕ
МАТЕМАТИЧЕСКОГО ИНСТИТУТА
ИМ. В.А.СТЕКЛОВА
Лаборатория математической логики
Принципы развития теории алгоритмов
Реферат по истории науки аспиранта
Лифшица Юрия Михайловича
Научный руководитель ………………../ Ю.В.Матиясевич
д.ф.-м.н., член-корр. РАН
Преподаватель ………………../ А.Н.Соколов
д.ф. н.,
Принципы развития теории алгоритмов
Юрий Лифшиц
Содержание
1. Введение
2. Хронология теории алгоритмов
3. Современное состояние теории алгоритмов
3.1. Использование других наук в алгоритмах
3.2. Наиболее значимые применения алгоритмов
3.3. Идеи и техники в теории алгоритмов
4. Формирование популярных направлений исследований
5. Стили проведения научных исследований
6. Заключение и выводы
7. Список источников
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).