2020-01-14
129
Одновременно с решением тех или иных вычислительных задач теория алгоритмов накапливает и систематизирует фундаментальные идеи и техники эффективных вычислений. Ниже перечислим список основных исследовательских направлений такого рода.
Прежде всего, необходимо ответить, как измерять эффективность алгоритмов? Первым ответом было число шагов выполняемых соответствующей машиной Тьюринга. После понимания неадекватности этой меры была предложена новая модель (RAM) дающая гораздо более точное приближение вычислительной сложности на практике. Кроме времени работы, полезно изучать и другие ресурсы, используемые при вычислениях. Это объем используемой компьютерной памяти и (это стало особенно важным в последнее время) количество раундов и объем передаваемых сообщений в распределенных вычислениях. Также, мы получим разное понимание трудоемкости алгоритмов, рассматривая сложность в среднем или сложность в худшем случае.
Первой фундаментальной идей теории вычислений стало наблюдение, что почти каждому алгоритму соответствует специально подобранная структура данных, которая позволяет работать с данными максимально эффективно. Таким образом, удалось выделить и изучить отдельно базовые задачи (сортировка, удаление, вставка, поиск), а затем использовать эти конструкции как составные части более сложных алгоритмов.
Следующей идеей большого значения является рекурсия. Многие алгоритмы наиболее естественно описываются при помощи самих себя. Конечно, это сразу порождает огромные сложности. Как известно, никакая проверка корректности алгоритмов (даже установления факта окончания работы) в общем случае не может быть решена. Тем не менее, рекурсия является одним из наиболее часто используемых приемов при разработке новых алгоритмов.
Теория сложности выделила класс задач, которые имеют переборное решение, но до сих пор не решенные эффективно (класс NP). В последнее время был найден целый ряд идей и техник (локальный поиск, рандомизация, модифицированная рекурсия), которые позволили в ряде случаев существенно ускорить экспоненциальный перебор (например, с 2^n до 1.331^n для задачи 3-SAT). Таким образом, атака задач, являющихся труднорешаемыми с точки зрения теории сложности может привести к новым нетривиальным идеям теории алгоритмов.
Как сформулировать задачу, которую невозможно сформулировать? Например, как объяснить компьютеру отличие всевозможных способов рукописного написания цифры «1» от столь же разнообразных способов написания «2»? С помощью примеров! Теория машинного обучения выработала следующую схему работы с задачами искусственного интеллекта.
1. Собрать коллекцию начальных данных с известными ответами
2. Разделить эту коллекцию на две группы: учебную и тестовую
3. Выбрать общий вид решающего правила
4. Подобрать коэффициенты и характеристики решающего правила на учебной коллекции, дающие максимальное совпадение с правильными ответами
5. Проверить качество работы полученного алгоритма на тестовой коллекции
6. В случае неудовлетворительных результатов вернуться к шагу 3.
Факторы определения «важности» задач и результатов.
По этим признакам можно определить текущие популярные темы:
§ Тематика работ, за которые присуждаются научные премии
§ Тематика монографий, публикуемых в крупнейших издательствах
§ Тематики, наиболее широко представленные на конференциях общего профиля
§ Темы специализированных конференций и школ
На выбор направлений научной деятельности влияют следующие факторы:
§ Возможность найти государственное финансирование
§ Наличие крупных компаний, заинтересованных в данном направлении
§ Принадлежность темы к наиболее популярным на данный момент
§ Возраст темы. Объем уже проведенных исследований
§ Масштаб текущих исследований: количество ученых, лабораторий, конференций, журналов, вовлеченных в данное направление
§ Связи данного направления с другими темами и науками
§ «Цена входа»: необходимый объем предварительных знаний для начала оригинальных исследований
При выборе исследовательской задачи обычно учитывают:
§ Собственный внутренний интерес к задаче
§ Интерес исследовательского сообщества к задаче
§ Прикладной интерес к решению задачи
§ Предысторию исследований по задаче
§ Автора задачи. Участников предыдущих исследований
§ Связи данной задачи с другими задачами и направлениями
§ Масштаб задачи. Оцениваемая сложность задачи.
§ Вхождение задачи в рамки более широкого исследовательского вопроса
§ Возможность расширения и обобщения решения данной задачи
§ Принадлежность задачи сразу к нескольким научным направлениям
§ Возможность изложить суть задачи (и особенно результата) на макимально простом и доступном языке
Механизмы, используемые для распространения задач в научной среде:
§ Обзорные научные статьи
§ Бюллетени научных ассоциаций (например, EATCS)
§ Открытые вопросы в монографиях
§ «Чтение по диагонали» трудов крупнейших конференций и важнейших журналов
§ Работа в соавторстве
§ Рабочие школы-семинары (workshops, например семинары в Дагштуле).
§ Разделы «направления для дальнейшей работы» в научных статьях
§ (Редко) публикация отдельных списков открытых проблем
