Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.

Издательство: Академия Естествознания

Год издания: 2007

ISBN: 978-5-91327-013-9

Работа посвящена математическому моделированию задач дискретной оптимизации, исходные данные которых имеют неопределенный характер. Неопределенность данных представляет собой задание их в виде временных рядов, интервалов или нечетких множеств. В качестве инструментария для структурирования таких неопределенностей выбраны методы нелинейной динамики: фазовые портреты временных рядов, фрактальный анализ и клеточные автоматы. В процессе моделирования указанного класса задач возникает двухуровневый подход: нижний уровень – моделирование исходных данных, верхний уровень – решение оптимизационной задачи. На верхнем уровне рассматриваются теоретико-графовые задачи, для которых предлагаются алгоритмы их решения.

Для специалистов в области моделирования и управления сложными эволюционными процессами и системами, а также для преподавателей, студентов и аспирантов специальностей прикладной математики и теоретических основ информатики.



    Введение

    Глава 1. Необходимый минимум понятий в комбинаторике и вычислениях

        1.1. Исторический экскурс в комбинаторику

        1.2. Элементарные комбинаторные задачи

        1.3. Понятие сложности вычисления и порождения. Время и емкость

        1.4. Вычислимые функции и породимые множества. Перечислимые множества и разрешимые множества

        1.5. Шкала оценки сложности комбинаторных задач

    Глава 2. Основные понятия, примеры задач и методов дискретной оптимизации

        2.1. Введение

        2.2. Верхняя, нижняя и точная оценки оптимума Функция Шеннона

        2.3. О некоторых элементарных задачах дискретной оптимизации

            2.3.1. Вложение дискретной задачи в непрерывную и использование методов математического анализа

            2.3.2. Симметрия и оптимизация

            2.3.3. Изопериметрические соотношения

            2.3.4. Оптимизация при диофантовых соотношениях

        2.4. Методы типа покоординатного спуска для дискретных экстремальных задач.

    Глава 3. Экстремальные задачи на графах

        3.1. Введение к главе

        3.2. Алгоритмы нахождения кратчайшего пути (цепи) между вершинами графа

        3.3. Некоторые обобщения задачи о кратчайшем пути

        3.4. Задача о кратчайшем остовном дереве и ее приложения

        3.5. Классификация задач об остовном дереве по признаку вычислительной сложности

            3.5.1. Многообразие целевых функций

            3.5.2. Вычислительная сложность 1-критериальных задач

            3.5.3. Вычислительная сложность многокритериальных задач

        3.6. Эйлеровы обходы (маршруты) в графах.

        3.7. Проблема выделения гамильтонова контура (цикла). Задача коммивояжера

            3.7.1. К вопросу о критерии распознавания гамильтонова графа

            3.7.2. Решение задачи коммивояжера методом динамического программирования

            3.7.3. Методы без использования принципа оптимальности Беллмана

    Глава 4. Концепция двухуровневого подхода к дискретной оптимизации и моделированию в условиях неопределенности данных

        4.1. Обзор известных методов исследования и решения задач дискретной оптимизации в условиях неопределенности

            4.1.1. Проблема неопределенности в реальном математическом моделировании

            4.1.2. Нечеткие данные, возникающие в процессе математического моделирования

            4.1.3. Дискретные задачи с интервальными данными

        4.2. Прогнозирование эволюционных процессов и систем с памятью

            4.2.1. Прогнозирование временных рядов на базе инструментария фазового анализа

            4.2.2. Клеточно-автоматное прогнозирование

            4.2.3. Гибридные модели прогнозирования

        4.3. Концепция двухуровневого подхода к реальному моделированию эволюционных процессов и систем

    Глава 5 Задачи оптимизации на графах с интервальными параметрами

        5.1. Задачи на графах с интервальными параметрами.

        5.2. Сведение интервальной задачи дискретной оптимизации к дискретной многокритериальной задаче.

        5.3. Оценки вычислительной сложности

        5.4. Полиномиально разрешимые подклассы интервальных задач на графах

        5.5. Статистически эффективные алгоритмы

        5.6. Асимптотически точный алгоритм

    Список литературы


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.252