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

Для широкого круга читателей.

Настоящий сборник работ имеет несколько особенностей. В нём впервые в достаточно популярной форме даётся обзор постановок задач, результатов и методов решения оптимизационных проблем дискретной математики. Развитие этой области математики в последние 15—20 лет тесно связано с внедрением ЭВМ в науку и производство, а в настоящее время и в другие сферы жизни и деятельности человека. Эта связь нашла отражение во всех работах сборника. Показано, как использование компьютера приводило к постановкам задач, как это было со многими задачами поиска, выбора в условиях неопределённости; как ЭВМ непосредственно использовалась для решения задач, например задачи о «четырёх красках», более столетия остававшейся нерешённой.

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

Статья Э. Н. Гордеева «Задачи выбора и их решение» посвящена обзору основных методов решения оптимизационных эадач выбора. В ней обсуждается влияние ЭВМ на постановку и решение задач. Освещена взаимосвязь известных методов решения, выделяются специфические черты задач, которые позволяют успешно применять тот или иной алгоритм. Кроме того, в этой работе приведены практически все основные понятия и определения, используемые в сборнике, что в значительной степени избавляет читателя от необходимости выяснения терминологии.

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

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

В работе Э. Н. Гордеева и В. К. Леонтьева «Задачи выбора в условиях неопределённости» описан ряд подходов к решению задач, числовые параметры которых заданы с погрешностью. Изложены основы теории устойчивости дискретных экстремальных задач, даны примеры алгоритмов исследования устойчивости, обсуждена их трудоёмкость. Приведены примеры непосредственного использования теории устойчивости для решения оптимизационных задач. Большинство приведённых результатов принадлежит авторам.

Задачам целочисленного линейного программирования посвящена статья Н. Н. Кузюрина «Задачи линейного булева программирования и некоторые комбинаторные проблемы». Здесь рассмотрен ряд классических комбинаторных проблем. Уделено внимание как алгоритмическому, так и метрическому аспекту. Дано качественное исследование приближённых алгоритмов.

Л. Г. Хачиян в своей статье изложил новые результаты, касающиеся построения в определённом смысле оптимальных алгоритмов в задачах сортировки и выпуклого программирования. Эти результаты приведены в рамках общего подхода, популярно изложены и богато иллюстрированы.

ПРЕДИСЛОВИЕ
Член-корреспондент АН СССР Ю. И. Журавлёв

Книги на ту же тему

1. Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
2. Комбинаторика, Виленкин Н. Я., 1969
3. Комбинаторные методы дискретной математики, Сачков В. Н., 1977
4. Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
5. Введение в прикладную комбинаторику, Кофман А., 1975
6. Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
7. Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
8. Задачи по теории множеств, математической логике и теории алгоритмов, Лавров И. А., Максимова Л. Л., 1975
9. Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
10. Информатика, Луенбергер Д. Д., 2008
11. Теория графов, Харари Ф., 1973
12. Булевы алгебры, Сикорский Р., 1969
13. Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
14. Параллельные алгоритмы целочисленной оптимизации, Хохлюк В. И., 1987
15. Элементы динамического программирования, Вентцель Е. С., 1964
16. Динамические задачи дискретной оптимизации, Рихтер К., 1985
17. Элементы теории оптимальных систем, Моисеев Н. Н., 1975
18. Математические методы оптимального управления. — 2-е изд., перераб. и доп., Болтянский В. Г., 1968
19. Численные методы оптимизации: Единый подход, Полак Э., 1974
20. Методы распознавания: Учебное пособие для вузов. — 3-е изд., перераб. и доп., Горелик А. Л., Скрипкин В. А., 1989
21. Дискретная математика для программистов, Хаггарти Р., 2004
22. Введение в дискретную математику, Яблонский С. В., 1979
23. Анализ алгоритмов. Вводный курс, Макконнелл Д., 2002
24. Регулярные выражения. 2-ое издание, Фридл Д., 2003