Функциональный анализ. Оказывается, что и непрерывная математика необходима в разработке алгоритмов. Это случается, в основном, при компьютерной обработке явлений, имеющих непрерывную природу. Это, конечно же, цифровая обработка аудио и видео записей. Такие широко используемые стандарты, как MPEG и JPG содержат идеи, взятые из свойств преобразования Фурье и активно используют дискретный аналог операции свертки.
3.2. Наиболее значимые применения алгоритмов
Первым прикладным направлением, по существу выделившим теорию вычислений в отдельное направление стали численное решение уравнений из физики, расчеты в атомной сфере и управление космическими кораблями и спутниками.
Следующим источником множества вычислительных задач стали вопросы оптимизации задачи в экономике. К основным достижениям стоит отнести формулировку задачи линейного программирования (Канторовича), симплекс-метод, алгоритмы Кармаркара и алгоритм Хачияна.
Успехи математической статистики и развитие измерительных приборов и рентгенов породили необходимость в алгоритмах автоматической диагностики и обработки данных томографии. Сейчас с огромной скоростью проводится внедрение компьютерной техники в самых разных направлениях медицины.
С ростом объемов информации возникла необходимость в эффективных механизмах ее хранения и использования. алгоритмы обработки запросов в базах данных относятся к числу наиболее широко применимых.
Как известно наибольший объем информации человек воспринимает зрением. Поэтому неудивителен большой интерес к алгоритмам обработки изображений, моделированию пейзажей и движения по воображаемой местности (виртуальная реальность). Огромные усилия тратятся на разработку все новых алгоритмов сжатия растровых изображений, аудио и видео потоков (MPEG4, JPEG).
Главным направлением развития информационных технологий последних двух десятилетий стал Интернет и распределенные вычисления. Теория алгоритмов здесь находит свое применение в задачах маршрутизации пакетов (TCP/IP и DNS) и поисковых системах. Небывалый успех системы Google стал, пожалуй, самым запоминающимся случаем, когда простая математическая идея (алгоритм PageRank) привела к феноменальному коммерческому успеху.
Особое значение играет решение задач, успех в которых нельзя строго сформулировать – так называемые задачи искусственного интеллекта. Перечислим лишь некоторые: автоматическое распознавание речи, отпечатков пальцев, лиц людей, системы распознавания свой - чужой, автоматическая классификация, автоматический контроль качества.
В конце концов, теория алгоритмов пришла к тому, что объектами обработки стали сами алгоритмы. Основными задачами являются автоматическая верификация и оптимизация программ и системы по распараллеливанию выполнения программ на многопроцессорных вычислительных системах.
Следующим направлением являются лингвистические алгоритмы: проверка орфографии, автоматический перевод, «разговаривающие» программы. Следующим шагом стала работа с грамматикой.
Наконец, компьютерам стали доверять все более и более важные задачи. Методы машинного обучения используются в разработке роботов (особенно заманчивой звучит создание футбольной команды роботов, способной выиграть у чемпионов мира 2050 года). Естественно ожидать, что время распространения устройств, оснащенных датчиками и способных самостоятельно принимать оптимальное решение, наступит очень скоро.
Наиболее популярным прикладным направление в самое последнее время стали исследования в биоинформатике: вычисление (восстановление) геномов и построение наиболее вероятной цепочки мутаций, которая переводит один генотип в другой.
3.3. Идеи и техники в теории алгоритмов
Одновременно с решением тех или иных вычислительных задач теория алгоритмов накапливает и систематизирует фундаментальные идеи и техники эффективных вычислений. Ниже перечислим список основных исследовательских направлений такого рода.
Прежде всего, необходимо ответить, как измерять эффективность алгоритмов? Первым ответом было число шагов выполняемых соответствующей машиной Тьюринга. После понимания неадекватности этой меры была предложена новая модель (RAM) дающая гораздо более точное приближение вычислительной сложности на практике. Кроме времени работы, полезно изучать и другие ресурсы, используемые при вычислениях. Это объем используемой компьютерной памяти и (это стало особенно важным в последнее время) количество раундов и объем передаваемых сообщений в распределенных вычислениях. Также, мы получим разное понимание трудоемкости алгоритмов, рассматривая сложность в среднем или сложность в худшем случае.
Первой фундаментальной идей теории вычислений стало наблюдение, что почти каждому алгоритму соответствует специально подобранная структура данных, которая позволяет работать с данными максимально эффективно. Таким образом, удалось выделить и изучить отдельно базовые задачи (сортировка, удаление, вставка, поиск), а затем использовать эти конструкции как составные части более сложных алгоритмов.
Следующей идеей большого значения является рекурсия. Многие алгоритмы наиболее естественно описываются при помощи самих себя. Конечно, это сразу порождает огромные сложности. Как известно, никакая проверка корректности алгоритмов (даже установления факта окончания работы) в общем случае не может быть решена. Тем не менее, рекурсия является одним из наиболее часто используемых приемов при разработке новых алгоритмов.
Теория сложности выделила класс задач, которые имеют переборное решение, но до сих пор не решенные эффективно (класс NP). В последнее время был найден целый ряд идей и техник (локальный поиск, рандомизация, модифицированная рекурсия), которые позволили в ряде случаев существенно ускорить экспоненциальный перебор (например, с 2^n до 1.331^n для задачи 3-SAT). Таким образом, атака задач, являющихся труднорешаемыми с точки зрения теории сложности может привести к новым нетривиальным идеям теории алгоритмов.
Как сформулировать задачу, которую невозможно сформулировать? Например, как объяснить компьютеру отличие всевозможных способов рукописного написания цифры «1» от столь же разнообразных способов написания «2»? С помощью примеров! Теория машинного обучения выработала следующую схему работы с задачами искусственного интеллекта.
1. Собрать коллекцию начальных данных с известными ответами
2. Разделить эту коллекцию на две группы: учебную и тестовую
3. Выбрать общий вид решающего правила
4. Подобрать коэффициенты и характеристики решающего правила на учебной коллекции, дающие максимальное совпадение с правильными ответами
5. Проверить качество работы полученного алгоритма на тестовой коллекции
6. В случае неудовлетворительных результатов вернуться к шагу 3.
4. Факторы определения «важности» задач и результатов.
По этим признакам можно определить текущие популярные темы:
- Тематика работ, за которые присуждаются научные премии
- Тематика монографий, публикуемых в крупнейших издательствах
- Тематики, наиболее широко представленные на конференциях общего профиля
- Темы специализированных конференций и школ
На выбор направлений научной деятельности влияют следующие факторы:
- Возможность найти государственное финансирование
- Наличие крупных компаний, заинтересованных в данном направлении
- Принадлежность темы к наиболее популярным на данный момент
- Возраст темы. Объем уже проведенных исследований
- Масштаб текущих исследований: количество ученых, лабораторий, конференций, журналов, вовлеченных в данное направление
- Связи данного направления с другими темами и науками
- «Цена входа»: необходимый объем предварительных знаний для начала оригинальных исследований
При выборе исследовательской задачи обычно учитывают:
- Собственный внутренний интерес к задаче
- Интерес исследовательского сообщества к задаче
- Прикладной интерес к решению задачи
- Предысторию исследований по задаче
- Автора задачи. Участников предыдущих исследований
- Связи данной задачи с другими задачами и направлениями
- Масштаб задачи. Оцениваемая сложность задачи.
- Вхождение задачи в рамки более широкого исследовательского вопроса
- Возможность расширения и обобщения решения данной задачи
- Принадлежность задачи сразу к нескольким научным направлениям
- Возможность изложить суть задачи (и особенно результата) на макимально простом и доступном языке
Механизмы, используемые для распространения задач в научной среде:
- Обзорные научные статьи
- Бюллетени научных ассоциаций (например, EATCS)
- Открытые вопросы в монографиях
- «Чтение по диагонали» трудов крупнейших конференций и важнейших журналов
- Работа в соавторстве
- Рабочие школы-семинары (workshops, например семинары в Дагштуле).
- Разделы «направления для дальнейшей работы» в научных статьях
- (Редко) публикация отдельных списков открытых проблем
6. Стили проведения научных исследований.
Пожалуй, нет единого максимально эффективного метода по выбору исследовательских задач и направлений. Напротив, можно выделить несколько стилей.
Решатель задач. В этом методе исследования заключаются в выборе строго-сформулированной задачи с известной ценностью и технической атаке на задачу. После определенного периода времени (скажем две недели) либо результат достигнут, либо усилия прекращаются и идет поиск новой задачи. Для такого подхода следующие факторы влияют на успех:
- Хорошо налаженный механизм нахождения задач
- Выбор задач с относительно невысокой «ценой входа»
- Мощная техника доказательств
Разработчик теории. Здесь основной целью является накопить, систематизировать и обобщить максимальное число фактов объединенных общим понятием или исследовательским вопросом. Факторами успеха здесь будут: