RUS ENG

Ковалев М. Я. Теория алгоритмов: Курс лекций

Ковалев М. Я. Теория алгоритмов: Курс лекций. В 2 ч. Ч. 2: Приближенные алгоритмы / М. Я. Ковалев, В. М. Котов, В. В. Лепин. - Мн.: БГУ, 2003. - 147 с.

ISBN 985-485-105-2 (ч. 2)

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

Предназначено для студентов, аспирантов и специалистов в области исследования операций, автоматизации управления и календарного планирования производства.


Оглавление

Введение

5

Глава 1. Основы теории полиномиальной сводимости задач

8

Глава 2 . Локальный поиск

21

2.1. Локальный поиск для задачи о максимальном разрезе

26

2.2. Сложность локального поиска

29

2.3. Окрестности, основанные на структурной близости решений

33

2.4. Локальный поиск фиксированной глубины

35

2.4.1 Локальный поиск для задачи о разбиении гра ф а

42

2.5. Локальный поиск переменной глубины

44

2.6. Эвристики, основанные на локальном поиске

47

2.6.1. Алгоритм имитации отжига

47

2.6.2. Поиск с запретами

49

2.6.3. Генетические алгоритмы

51

Глава 3 . Приближенные алгоритмы с гарантиро ванными оценками точности

55

3.1. Задача k-разбиения

64

3.2. Нижняя оценка оптимального решения

64

3.3. Приближенные методы для задачи k-разбиения

71

3.3.1. Алгоритмы свертки

71

3.3.2. Алгоритмы "в минимапьно загруженный"

73

3.3.3. Обменный алгоритм

74

3.3.4. Прямо-двойственный подход

78

3.4. Задача 3-разбиения

90

3.4.1. Описание алгоритма

92

3.4.2. Приложения в теории расписаний

98

3.5. Задача теории расписаний с задержками

101

3.6. Задача о разбиении

105

3.7. Градиентный алгоритм

106

3.8. Semi on-line версия задачи разбиения

118

3.8.1. Наличие буфера для хранения данных

119

3.8.2. Два парanлельных процессора

124

3.8.3. Известная обпщая сумма

128

3.9. On-line алгоритмы для задачи k-упаковки

130

3.10. Построение вполне полиномиальных –приближенных алгоритмов

134

Другие сайты факультетаСтруктураОбразованиеМагистратураНаукаМеждународное сотрудничествоСтудентуНИРСАСовет молодых ученыхОлимпиадыАбитуриентуШкольникуЦентр
Компетенций
по ИТ
Microsoft
Imagine Premium
ИсторияИздания факультетаПрофбюро ФПМИПерсональные страницыФотогалереи Газета ФПМыНаши партнеры