[Brucker (2007)], новая книга Блажевича с соавторами [Blazewicz, Ecker, Pesch, Schmidt and Weglarz (2007)], посвящённая как теоретическим вопросам, так и приложениям теории расписаний книга Даванде и др.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Российск
ая

академи
я

наук


Учреждение Российской академии наук
Институт математики им. С.Л.
Соболева Сибирского отделения РАН


(ИМ СО РАН)


УДК
519.7

№ госрегистрации
01201064560

Инв. №


УТВЕРЖДАЮ

Директор
Учреждени
я

Российской
академии наук Институт мате
матики им.
С.Л. Соболева Сибирского отделения РАН

академик РАН

_________________________
Ершов Ю.Л.

___»____________________ 20
1
0 г.


Государственный

контракт

от 20» сентября 2010 г.



14.740.11.0
36
2

Шифр

заявки
: 
2010
-
1.1
-
113
-
130
-
032
»


ОТЧЕТ

О НАУЧНО
-
ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ


в рамках федеральной целевой программы
Научные и научно
-
педагогические кадры
инновационной России» на 2009
-
2013


по теме:


СОВРЕМЕННЫЕ ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ КИБЕРНЕТИКИ
»


(промежуточный
, этап № 1
)


Наименование этапа: Постановк
а и анализ задач»




Руководитель темы

член
-
корреспондент

РАН

________________ Мазуров В.Д.



Новосибирск 20
1
0




2

СПИСОК ИСПОЛНИТЕЛЕЙ

Рук. темы,
за
в
.

отделом ИМ С
О
РАН,
член
-
корр. РАН


_________________


В.
Д
.
Мазуров

(результаты)

Отв. исполнитель темы, исп.
директор НОЦ, д.
т.н.


_________________

С.М. Лавлинский

(
Реферат,
Введение,
Заключение,
Приложения А
-
В
, результаты,
подготовка
)

проф. НГУ
, д.ф.
-
м.н.


_________________

Береснев

В.Л.
(1.
9
, результаты)

п
роф. НГУ
, д.ф.
-
м.н.


_________________

Гимади Э.Х.
(1.1, результаты)

зав. кафедрой

НГУ,
д.ф.
-
м.н.

_________________

Ерзин А.И.

(1.
1
,
1.
8
,

результаты
,
подготовка
)

гл.н.с. ИМ СО РАН
,
д.ф.
-
м.н.

_________________

Кельманов А.В.

(1.
1
,

1.3,

результаты
, подгото
вка
)

в.н.с. ИМ СО РАН
,
д.ф.
-
м.н.

_________________

Севастьянов С.В.

(
1.
1
,

1.2

результаты)

в.н.с. ИМ СО РАН
, д.ф.
-
м.н.

_________________

Соловьева Ф.И.

(1.
6,

результаты
)

зав. лабораторией ИМ СО РАН
,
к.
ф.
-
м.н.

_________________

Августинович

С.В.

(1.
1
,
1.5,

результаты)

асс
. НГУ,
к.ф.
-
м.н.

_________________

Токарева Н
.
Н
.

(1.
7
, результаты)

ас
п
. НГУ

_________________

Могильных И
.Ю.

(1.
5
,
результаты)

доц. НГУ,

к.ф.
-
м.н.

_________________

Кротов Д
.
С
.

(1.
6
,1.5,

результаты
,
подготовка
)

ас
п
. НГУ

________________
_

Салимов П
.
В
.

(
1.5, результаты
)

н.с. ИМ СО РАН, к.ф.
-
м.н.

_________________

Алексеева Е.В.

(1.
9
.
2
, результаты,
подготовка)

м.
н.с. ИМ СО РАН, к.ф.
-
м.н.

_________________

Руднев А.С. (1.
9
, результаты)

н.с. ИМ СО РАН, к.ф.
-
м.н.

_________________

Орозбеков

Н.А.

(1.
9
, результаты)

асс. НГУ,
к.ф.
-
м.н.

_________________

Пузынина С
.А.

(
1.1, результаты)

асс. НГУ,
к.ф.
-
м.н.

_________________

Рыков И
.
А
. (1.1, результаты)

асс. НГУ,
к.ф.
-
м.н.

_________________

Тахонов И
.
И
. (1.1, результаты)

асс. НГУ

____________
_____

Алдын
-
оол Т.А.

(1.9, результаты)

аспирант НГУ

_________________

Горкунов Е
.
В
. (1.7, результаты)


3

аспирант НГУ

_________________

Лисицына М
.
А
. (1.7, результаты )

аспирант НГУ

_________________

Воробьев К
.
В
.

(1.
5
, результаты)

аспирант
ИМ СО РАН


___
______________

Козлов

А.С.

(1.2
,

результаты)

аспирант
ИМ СО РАН

_________________

Павлов С.В.
(1.
2
, результаты)

аспирант
ИМ СО РАН

_________________

Сухорослов

А.А.
(
1.2,
результаты
)

аспирант
НГУ


_________________

Долгушев А.В.
(
1.3, результаты
)

аспи
рант
ИМ СО РАН

_________________

Плотников Р.В.
(1.
8
, результаты)

аспирант
ИМ СО РАН

_________________

Курочкин А.А.
(1.
8
, результаты)

аспирант
ИМ СО РАН

_________________

Истомин А.М.
(1.
1
,

результаты)

студент НГУ

_________________

Романченко С.М.


(1
.
3
,
результаты)

студент НГУ

_________________

Мельников А.А.

(1.
9
.
2
,
результаты, подготовка
)

студент НГУ

_________________

Корпич Д.В.

(1.
3
, результаты
,
подготовка
)

студент

Н
ГУ

_________________

Панин А.А.

(1.
1
, результаты)


Норм
о
контролер

___________
______

Кравченко С.В.





4

Реферат


Отчет
6
5

с.,
1 ч.,
139

источник
ов
,
3

прил.

Тема:
СОВРЕМЕННЫЕ ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ КИБЕРНЕТИКИ


Ключевые слова:

теори
я

расписаний
;

кластерный анализ;

дискретный анализ;

совершенны
е

2
-
раскраск
и

гипер
куба
;

бент
-
функция;

методы глобальной маршрутизации;

игра Штакельберга;

модели конкурентного размещения предприятий
.

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

Выполнение НИР
в целом
направлено на провед
ение фундаментальных исследований
в области теоретической кибернетики по следующим направлениям:

-

задачи размещения и маршрутизации;

-

проблемы теории расписаний;

-

дискретный анализ и теория графов в задачах хранения, обработки, передачи и
защиты информа
ции;

-

актуальные проблемы анализа данных и распознавания образов.

В процессе
выполнения
1 этапа
НИР

пров
едены

следующие работы
.

1.
Проведен о
бзор литературы и определен
ы

приоритетны
е

направлени
я

фундаментальных
исследований в различных областях современн
ой кибернетики


2.
Проа
нализ
ированы

актуальны
е

проблем
ы

теории расписаний

и намечен соновной фронт
работ этого направления в НИР.

3.
Проведен о
бзор проблем в области поиска подмножеств похожих» векторов и
кластерного анализа
. Очерчен
широкий класс неизуче
нных и слабо изученных
оптимизационных задач, связанных с поиском подмножеств векторов и кластерным
анализом в евклидовом пространстве.
В качестве актульной задачи выделена проблема
с
ложностно
го

статус
а

оптимизационных задач, к которым сводятся некоторые п
роблемы
анализа данных, связанные с поиском подмножеств векторов
.


4.

В о
бзор
е

проблем дискретного анализа и теории графов в задачах хранения, обработки,
передачи и защиты информации

сделана
попытка проследить основные направления
развития теории кодирован
ия дискретных источников от задачи оптимального кодирования
известного источника к задаче оптимального универсального кодирования семейства
источников и задаче построения модели источника по сообщению
. Р
ассмотрены

5

самосихронизирующиеся и омофонные коды, а

также способы

кодирования двух часто
встречающихся на практике видов источников: текстов на естественных языках и
источников с низкой энтропией


5.
Приведен
краткий обзор
методов улучшения оценок числа совершенных 2
-
раскрасок
гиперкуба
. Выделены

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

6.
Проведен а
нализ критериев восстановимости кода (с точностью до эквивалентности) по
полной или частичной информации о метрических соотношениях между кодовыми
вершинами
. С новых позиций расс
мотрена
проблема жёсткости кодов
.

7.
Проанализированы

новы
е

конструкци
и

бент
-
функций, используемых для построения
кодов постоянной амплитуды в системах CDMA (Сod Division Mutip Accss)
. Приведен
обзор и
сследован
ий

по
нижни
м

оценк
ам

числа бент
-
функций,

которые могут быть получены
с помощью итеративных конструкций
.

8.

Проведен о
бзор проблем маршрутизации в современных беспроводных сенсорных сетях
.

Про
анализ
ированы

существующи
е

метод
ы

глобальной маршрутизации при проектировании
СБИС
.
Задача г
лобальн
ой

тра
ссировк
и

рассмотрена в контексте

важнейш
его
этап
а

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

9. Разработаны новые
п
остановк
и

математических моделей конкурентного размещения
предприятий с различными целевыми функциями в виде задач двухуровневого
целочисленного программирования
.

В
результате исследований
проведен обзор литературы
,

поставлены
и
проанализированы
основные
задачи НИР. По ряду направлений
получены новые
фундаментальные
результаты мирового уровня
, которые доложены на различных научных
форумах

и
опубликованы в монографиях и статьях
.













6

Обозначения и сокращения


ИМ СО РАН
-

Институт математики Сибирско
го отделения Россимйской академии наук.

НГУ


Новосибирский государственный университет.

НОЦ


научно
-
образовательный центр.

СБИС



сверхбольшие интегральные схемы.

7

Содержание


Введение

8

1

Постановка и анализ задач



9

1
.1

Обзор литературы и определени
е приоритетных направлений
фундаментальных исследований в различных областях современной
кибернетики

9

1.2

Анализ актуальных проблем теории расписаний

20

1.
3

Обзор проблем в области поиска подмножеств похожих» векторов и
кластерного анализа

28

1.
4

Обзо
р проблем дискретного анализа и теории графов в задачах хранения,
обработки, передачи и защиты информации

29

1.
5

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

30

1
.
6

Анализ критериев восстановимости кода (с точностью до эквивале
нтности) по
полной или частичной информации о метрических соотношениях между
кодовыми вершинами

30

1.
7

Анализ новых конструкций бент
-
функций, используемых для построения
кодов постоянной амплитуды в системах CDMA (Сod Division Mutip
Access)

31

1.
8

Об
зор проблем маршрутизации в современных беспроводных сенсорных сетях
и анализ существующих методов глобальной маршрутизации при
проектировании СБИС

32

1.
9

Постановка математических моделей конкурентного размещения предприятий
с различными целевыми функция
ми в виде задач двухуровневого
целочисленного программирования

38

1.9.1

Задача Лидера в игре Штакельберга

38

1.9.2.

Математические модели конкурентного размещения предприятий

41

2

Показатели

46

3

Заключение

47

4

Список использованных источников

49


Приложение
А

Список публикаций исполнителей

58


Приложение
Б

Список сделанных исполнителями докладов

61


Приложение В
Список представленных диссертаций

65



8


Введение

Выполнение НИР в целом направлено на проведение фундаментальных исследований
в области

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

I. Задачи размещения и маршрутизации;

II. Проблемы тео
рии расписаний;

III. Дискретный анализ и теория графов в задачах хранения, обработки, передачи и
защиты информации;

IV. Актуальные проблемы анализа данных и распознавания образов.

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



За
планированные
исследования 1 этапа являются заделом для всей НИР.
В ходе
работ предполагается
провести о
бзор литературы

и

определ
ить

приоритетны
е

направлени
я

фундаментальных исследований в различных областях современной кибернетики
.

Важная
роль в работах
1 этапа отведена
обхору

актуальных проблем теории расписаний
, кластерного
анализа,

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

направления
м

развития

теории кодирования
, разработки
методов улучшения оценок числа
совершенных 2
-
раскрасок гиперкуба
,
а
нализ
а

критериев восстановимости кода
, поиска
новы
х

конструкци
й

бент
-
функций
.

Совместно с

о
бзор
ом

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

и новыми п
остановк
ами

математических
моделей конкурентного размещения предприятий с различными целевыми функциями в виде
задач двухуровневого целочисленного программирования
,

эти исследования определяют

фронт работ

1 этапа

и
позвол
яю
т в максималь
ной степени конкретно
поставить основные
задачи, решаемые в рамках НИР.



9


1
.

Постановка и анализ задач



В рамках
работ первого этапа
НИР
проведен о
бзор литературы, относящейся к
тематике проекта
,

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

д
искретный анализ и теория графов в задачах хранения,
обработки, передачи и защиты информации
,

анализа данных и распознавания образов.

В о
тчете приведено описание работ по пунктам календарного плана
в соответствии с
техническ
им

задани
ем
.


1.1.

Обзор литературы и определение приоритетных направлений
фундаментальных исследований в различных областях современной
кибернетики


Можно выделить следующие

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

Задачам размещения

посвящено большое количество публикаций, среди которых
стоит отметить монографию [Береснев В.Л.

(
1978
)
]. Позже появились работы как
отечественн
ых, так и иностранных учёных, в которых рассматривались обобщения
простейшей задачи размещения. Некоторые способы решения таких задач представлены в
монографии [Береснев В.Л.

(
2005
)
]. В прак
тических приложениях достаточно важной
является метрическая задача

размещения, когда расстояния между объектами (пунктами
производства и потребления) удовлетворяют неравенству треугольника. Известно, что
метрическая задача размещения на сети является NP
-
трудной даже в случае неограниченных
объемов производства.
В

работе
[
Агеев А.А. (
2009
)
]
рассмотрен подкласс метрических задач
CFLP, в котором пункты производства и потребления расположены в вершинах путевого
графа, а мощности предприятий одинаковы. До недавнего времени единственным
полиномиальным точным алгоритмом для этог
о подкласса задач был алгоритм с временной
сложностью
O
(
m
5
n
2

+

m
3
n
3
), где
m

и
n



число предприятий и число пунктов спроса,
соответственно. В представленном ныне результате для решения задачи размещения на
путевом графе с одинаковыми производственными мощн
остями приводится обоснование
модифицированного полиномиального точного алгоритма с временной сложностью
O
(
m
4
n
2
).
Это на порядок улучшает ранее достигнутый результат как относительно числа предприятий

m
, так и относительно числа пунктов спроса
n

[
Агеев А.А
.

(
2009
)
].


10

Рассмотрена задача CFLP с одинаковыми объемами производства при некоторых
специальных ограничениях на объемы спроса клиентов и число открываемых предприятий.
Предполагается, что элементы матрицы транспортных расходов


независимые случайные
вел
ичины с равномерной функцией распределения на целочисленном сегменте [1,
r
].
Построен приближенный алгоритм решения задачи и проведен вероятностный анализ его
работы. Представлены условия, при которых алгоритм за время
O
(
n

ln
m
) (
n



число
потребителей,
m



число возможных пунктов производства) находит асимптотически
точное решение. Кроме того, в результате анализа построен быстрый алгоритм отыскания
совершенного паросочетания с минимальной суммой весов ребер в случайном графе и
обоснованы условия на параметр

r
, когда этот алгоритм асимптотически точен [
Гимади Э.Х.

(
2010
)
].

Для решения задачи размещения в так называемой
p
-
медианной форме с
расстояниями между вершинами


случайными независимыми переменными с одинаковой
функцией равномерного распределения


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

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

Типовой задачей маршрутизации

является задача коммивояжера. Она
NP
-
трудна в
сильном смысле, как на минимум, так и на максимум длины гамильтонова цикла. Это
стимулировало усилия по ра
зработке приближенных методов ее решения. Кристофидесом и
Сердюковым для приближенного решения метрической задачи коммивояжера для
n

вершин
был разработан приближенный алгоритм трудоемкостью O(
n
3
) с точностью 3/2. Этот,
пожалуй, наиболее цитируемый резуль
тат в дискретной оптимизации основан на
преобразовании кратчайшего остовного дерева в гамильтонов цикл. Естественными
модификациями классической задачи коммивояжера являются задачи, в которых требуется
найти два или несколько (вершинно или реберно) неперес
екающихся маршрутов
минимального или максимального суммарного веса. Одной из первых задач этого типа,
привлекших внимание исследователей, является задача
m
-
PSP (Krarup

(
1975)
)

о
m

коммивояжерах


m
-
pripattic sasman probm, которая также NP
-
трудна в с
ильном
смысле при
m



2. Для задачи отыскания приближенного решения задачи 2
-
PSP на максимум
на полном
n
-
вершинном графе с симметричной матрицей расстояний построен алгоритм с

11

временной сложностью O(
n
3
) и гарантированной оценкой точности 3/4
(
Агеев, Гимади
,
Бабурин
)
. В основе алгоритма лежит общая идея, впервые реализованная А. Сердюковым
при построении приближенного алгоритма для нахождения одного гамильтонова цикла
максимального веса в полном неориентированном взвешенном графе с теми же оценками
временной

сложности и точности. Прямое применение его схемы построения частичных
туров к задаче 2
-
PSP не приводит к успеху, поскольку конструируемые частичные туры
могут содержать одинаковые ребра. Поэтому предлагается алгоритм, в котором в качестве
исходного подгр
афа, подвергающегося разбиению на два реберно
-
непересекающихся
частичных тура, используется либо кубический подграф (при четном
n
), либо почти
кубический» подграф (при нечетном
n
) максимального веса. Найденные реберно
-
непересекающиеся частичные туры в дал
ьнейшем удается дополнить до реберно
непересекающихся маршрутов, что далеко не всегда возможно в случае произвольных
реберно
-
непересекающихся частичных туров.

В области
анализа данных и распознавания образов

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

Как

известно [
Jain

A
.
K
.

(1988)
],

[
Kaufman

L
.

(2005)
]
,

[
P
.
Arabie

(1996)]
,

[Richard O.
(2001)]
конструктивная модель какой
-
либо содержательной проблемы анализа данных и
распознавания образов формул
ируется в форме задачи оптимизации подходящего критерия
или функционала (максимума правдоподобия, минимума суммы квадратов уклонений,
максимума апостериорной вероятности и т.п.), адекватно отражающего эту проблему.
Оптимизация этого критерия в комбинации с

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


12

Широко распространенным (в Российской Федерации и за рубежом) и наиболее часто
используемым подходом к решению задач анализа данных и распознавания образов является
подход, сущность которого состоит в разбиении задачи на небол
ьшое число подзадач
(этапов), которые решаются либо известными оптимизационными малотрудоемкими
алгоритмами, либо быстрыми» эвристическими процедурами. При этом задача в целом, как
оптимизационная проблема, как правило, не формулируется, какие
-
либо доказу
емые оценки
точности ее решения не устанавливаются, а класс допустимых входов не описываются
формально (математически). Подтверждение работоспособности алгоритмов и
компьютерных технологий получают в численных экспериментах и на примерах решения
конкретных

прикладных задач, т.е. для узкого класса реально имеющихся (под рукой)
входных данных. Этот подход отчетливо просматривается на множестве российских и
международных конференций, в тысячах отечественных и зарубежных публикаций
(библиографический список зай
мет не один десяток страниц) и реализован в
многочисленных существующих информационных технологиях, системах анализа данных и
распознавания образов (см., например, [
Jain

A
.
K
.
(2010)
] и цитированные там работ
ы).


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

последние 15
-
20 лет
сложилась устойчивая мировая тенденция, направленная, во
-
первых, на изучение
комбинаторной сложности специфических (как правило, труднорешаемых) экстремальных
задач, к которым сводятся типовые проблемы анализа данных и распознавания об
разов, а во
-
вторых, на построение эффективных алгоритмов с гарантированными оценками точности
для решения этих задач. Это направление исследований в последние годы оформилось в виде
области, которую можно определить как экстремальные задачи анализа данных

и
распознавания образов».

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


13

Одной из наиболее общих проблем
теории кодирования и дискретной математики

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

Первая бесконечная серия совершенных блоковых кодов

была построена Р.
Хэммингом в 1950 году. Спустя более чем 20 лет В.А. Зиновьев и В. К. Леонтьев
[
Зиновьев
В. А.,

(
1972
)
,

(1973)]

и

независимо

Э
.
Титвайнен

в

[
Tietavainen

A
.

(1973)]

доказали что кодов
с параметрами, отличными от параметров кода Хэмминга, з
а исключением двоичного и
троичного кодов Голея, над полями Галуа не существует. Ф
.
Дельсарт

в

[
Delsarte

P
.
(
1973
)]

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

кодов в n
-
кубе содержит
равномерно упакованные в узком смысле коды, введенные Н. В. Семаковым, В. А.
Зиновьевым и Г. В. Зайцевым в
[
Семаков Н.В.

(1971)]
. Этот класс включает совершенные и
укороченные совершенные коды, выколотые коды Препараты, некоторые к
лассы кодов БЧХ
и выколотых кодов Рида
-
Маллера. Полное описание всех равномерно упакованных кодов
было сделано Х. К. А. ван Тилборгом в
[
Van Tilborg H. C. A.
(
1975)
]
.

Проблема существования совершенных кодов в схеме Джонсона оказалась сложнее,
чем аналоги
чная проблема в схеме Хэмминга. В

работе

[
Delsarte

P
.
(
1973
)]

Дельсарт
выдвинул гипотезу, что нетривиальных совершенных кодов в графе Джонсона не
существует. Усилия целого ряда авторов так и не привели ни к ее доказательству, ни к ее
опровержению. Один из
лучших на сегодняшний день результатов был получен Д.Гордоном
в 2006 году в работе
[
Gordon M.D.
(
2006
)]
. Используя компьютер, он доказал, что не
существует 1
-
совершенных кодов в графах Джонсона J(n,w) при n< 2^250.

Как отмечалось ранее, совершенные 2
-
раскр
аски являются обобщением

1
-
совершенных кодов. Заметим, что гипотеза Дельсарта не может быть обобщена на
совершенные 2
-
раскраски графов Джонсона. У
.
Мартин

в

работе

[
Martin

W
.
J
.
(
1998
)]

заметил, что нетривиальную совершенную 2
-
раскраску графа J(n,w) можно
получить,
покрасив блоки произвольной k
-
кратной (w
-
1)
-
схемы (при этом подразумевается что все

14

блоки схемы различны) в один цвет, а оставшиеся вершины J(n,w) в другой цвет. Проблема
существования таких схем при
w
3 была решена М. Дегоном в 1983 в работе
[
De
hon

M
.
(
1983
)]
; при w4 для однократного случая (системы четверок Штейнера) Х. Ханани в работе
[
Hanani H.
(
1960
)]
, для двукратного случая А. Хартманом и К. Т. Фелпсом в
[
Hartman A.,
(
1990
)]
, для трехкратного случая К. Т. Фелпсом, Д. Р. Стинсоном и С. А. Ва
нстоуном в
работе
[
Phelps K.T.

(
1989
)]
. Проблема существования таких схем для параметров, отличных
от

вышеперечисленных, за исключением нескольких спорадических случаев, является
открытой.

Каково положение дел сегодня в

т
еори
и

расписаний
?

Для того, чтобы

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

Общая классификация направлений исследований в дискретной оптимизации
.

Поскольку
теори
я

расписаний

является частью такой обширной области науки как
исследование операций, то одн
им

из значимых
напр
авлений

исследований
(и первым шагом
в исследовании задачи)
является
построение адекватных математических моделей

для
реальных исследуемых процессов

или объектов
. Таким образом, целью первой части
всякого
исследовани
я

(отправляющегося от реальной прикладно
й задачи)
является
выявление общематематических проблем в реальн
ой

задач
е
, определение критериев
оптимальности выбора решения, форм
улировка оптимизационных (либо
распознавательных) задач.

Распознавательной

задачей мы называем такую задачу, в которой ставит
ся
некоторый вопрос о свойствах заданного на входе объекта, а нашей задачей является
угадывание» правильного ответа из двух возможных вариантов: ДА» или НЕТ».
(Таковыми являются все задачи из класса
NP
.)
В
оптимизационных

задачах требуется
найти, как пр
авило, одно (оптимальное по заданному критерию) решение из множества
допустимых решений. В других постановках целью решателя задачи» является отыскание
множества
всех

оптимальных решений. В третьих постановках ставится вопрос об
отыскании полного множеств
а неулучшаемых» (по заданному набору критериев) решений
многокритериальной задачи (построение так называемого
Парето
-
оптимального
множества

решений), либо


полного множества представителей
Парето
-
оптимального
множества
. В четвёртых постановках имеется уп
орядоченный набор критериев, и требуется

15

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

Следующим шагом
(и направлением) в теоретическом исследовании задачи
является
анализ сложности

полученной оптимизационной (либо распознавательной) задачи
. Под
этим

шагом
»

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

Нередко возникает ситуация, когда построенная математическая модель, хотя и
достаточно адекватно отражает исходну
ю прикладную задачу, но оказывается слишком
сложной в вычислительном плане (причём, не только в смысле точного её решения, но и
приближённого). В этом случае возникает необходимость вернуться к первому шагу
исследований прикладной задачи (построение модели
) и попытаться построить другую
модель, более удобную для решения. Таким образом, процесс исследования исходной
задачи является итеративным, где на каждой итерации повторяются шаги 1 и 2
(моделирования и анализа сложности полученной модели).

Упомянутый выш
е анализ сложности задачи» имеет абсолютный характер,
безотносительный к какому
-
либо конкретному алгоритму. Хотя доказательство
полиномиальной (псевдо
-
полиномиальной) разрешимости задачи, как правило, опирается
на описание конкретного алгоритма, этот резу
льтат также является абсолютным, поскольку
доказывает
существование

алгоритма решения с трудоёмкостью не выше заданной
функции от длины входа задачи (или от других параметров этого входа). Отрицательные же
результаты, говорящие о несуществовании тех или ин
ых алгоритмов, носят априорно
абсолютный характер, безотносительный к каким
-
либо алгоритмам.

Ортогональным» к данному направлению исследований (отправляющемуся от
конкретной
модели

или класса моделей) являются исследования, направленные на
разработку унив
ерсальных
методов
,
способных находить приемлемые решения для
широкого спектра оптимизационных задач и их примеров. Хорошо известными примерами
таких универсальных методов являются линейное и динамическое программирование,
метод ветвей и границ, алгоритмы л
окального поиска и др. Универсальность таких методов,
однако, не исключает необходимости учёта специфики конкретной задачи, решаемой

16

данным методом (т.е. требует разработки конкретного
алгоритма
), поэтому процесс
исследования того или иного универсального
метода потенциально бесконечен и направлен
на всё более широкое его применение по отношению к новым, ранее не исследованным
задачам и моделям.

Получаемые результаты исследований алгоритмов могут иметь как абсолютный
характер (когда они доказаны теоретическ
и и справедливы для всех без исключения
примеров задачи из рассматриваемого класса


такие алгоритмы называются
алгоритмами с
гарантированными оценками качества
), так и характер некоего правдоподобного»
утверждения, в пользу которого свидетельствуют мног
очисленные факты» либо
наблюдения. Речь идёт о так называемой эспериментальной компьютерной проверке»
эффективности исследуемого алгоритма на некотором конечном семействе конкретных
входных примеров задачи. (Под эффективностью» алгоритма здесь зачастую
п
одразумевается абсолютная оценка времени счёта конкретных примеров, а также
апостериорная оценка близости получаемых решений конкретных примеров к оптимуму.)
Несмотря на массовость и широкую распространённость такого направления исследований,
подобные резу
льтаты всегда оставляют открытые вопросы как в теоретическом, так и в
практическом плане: достаточно ли представительна данная конечная выборка примеров,
чтобы из неё можно было сделать теоретические выводы о поведении алгоритма на всём
(бесконечном) семей
стве примеров исходной задачи? Отражает ли представленная конечная
совокупность примеров реальное вероятностное распределение примеров конкретной
прикладной задачи? Часто авторы подобных исследований не задаются подобными
вопросами, что значительно снижает

их практическую ценность (не говоря о
теоретической).

Классификация направлений исследований в теории расписаний.

Говоря о
первой (модельно
-
ориентированной») группе направлений исследований в теории
расписаний, следует отметить такие группы моделей и зад
ач, которые за прошедшие
десятилетия своего развития смогли оформиться в самостоятельные дисциплины


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


17

M
achine

scheduling

(где обязательными понятиями моделей являются машины» и
работы»); прародителями» этой дисциплины являются такие прикладные области как
цеховое планирование, многопроцессорные вычислительные машины и др.

P
roject

scheduling

(
ил
и управление проектами»; по
-
видимому, этому английскому
названию соответствует русскоязычное календарное планирование», хотя в нём и нет
упоминания о каких
-
либо проектах»); базовыми понятиями в этой дисциплине являются
ресурсы» и задания»; типичными о
граничениями в задаче из этой области являются
ресурсные ограничения и ограничения предшествования на множестве заданий
.

T
ime

tabling

(
или построение временных таблиц»); спецификой этой области
является построение расписания на фиксированном временном инт
ервале (например,
построение учебного расписания в школе или вузе на недельной или двухнедельной
основе); здесь оперируют такими понятиями как группы», преподаватели», аудитории»,
учебный план»; распределение преподавателей» по дисциплинам и группам с
читается,
как правило, заданным, а оптимальное распределение занятий по аудиториям и временной
сетке требуется отыскать
.

N
urse

rostering
; для этого названия пока нет русско
-
язычного аналога, поскольку
данная дисциплина развивается исключительно за рубежом,

в развитых странах; речь идёт о
задачах распределения нагрузки медперсонала в лечебном заведении (с учётом их
квалификации, предпочтений, а также предпочтений клиентов); в отличие от задач
классической теории расписаний (
machine

scheduling
)
, где, как прав
ило, рассматриваются
регулярные (реже


нерегулярные) целевые функции от моментов завершения работ,

задачи
в данной области характеризуются, во
-
первых, наличием нежёстких» ограничений (т.е.,
пожеланий», которые необязательно соблюдать), а во
-
вторых, в ка
честве критерия
оптимальности рассматривается минимум количества невыполненных пожеланий
.

P
acket

routing

(
маршрутизация пакетов в сетях связи); данная область начала активно
развиваться в связи с возникновением и быстрым развитием Всемирной Паутины»;
возн
икающие здесь задачи объединяют в себе сложность потоковых задач и задач на
составление расписаний выполнения работ
.

Robotic

cells

(роботизированные производства)


дисциплина, характеризующаяся
наличием элемента доставки» изделия до машин, причём доставк
а осуществляется одним
либо несколькими роботами». Данная область теории расписаний отличается от
machine

scheduling

более изощрёнными моделями с реализацией нетривиальных технологических
моментов, а также бόльшим приближением этих задач к практике.

T
ran
sportation

scheduling
, объединяющее всевозможные задачи на составление
расписаний воздушного, морского, железнодорожного, общественного и пр. транспорта.

18

Эти задачи характеризуются повышенной вычислительной сложностью, поскольку
постановки задач вынуждены
учитывать множество разнотипных ограничений как весьма
жёсткого, так и мягкого» характера. О жёсткости некоторых ограничений (и
неукоснительности их соблюдения на практике) говорит следующий пример. Когда через
неделю после известных событий 11 сентября в

США при посадке в аэропорту им. Джона
Кеннеди по неизвестным причинам разбился пассажирский самолёт, то первой же версией
были происки Аль
-
Каиды». Однако более тщательное расследование дало неожиданный
результат. Выяснилось, что приземляющийся самолёт по
пал в турбулентные воздушные
потоки, оставленные от взлёта другого пассажирского самолёта с той же полосы. Диспетчер
дал разрешение на посадку, не выждав положенного по технологии двухминутного
интервала ожидания. Ценой несоблюдения технологического ограни
чения стали полторы
сотни человеческих жизней.

Cyclic

scheduling

(
построении циклических расписаний для одной либо нескольких
групп идентичных работ)


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

Online

scheduling

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

scheduling

(
когда часть информации о входном примере
известна, а часть


нет).

Constraint
-
based

scheduling



область задач на построение расписаний с целевыми
функциями минимизации числа мягких» ограничений на допустимые расписания.

Из второй (методо
-
ориентированной») группы направлений исследований можно
выделить направления дальнейшего развития т
аких классических методов как:

--

метод ветвей и границ (и его многочисленные модификации);

--

метод динамического программирования;

--

метод линейного программирования и полиэдральный анализ;

--

методы локального поиска (поиск с запретами, имитация обжиг
а»,
генетические» алгоритмы, муравьиные колонии», и др.);


19

--

геометрические методы (основанные на анализе свойств векторных семейств в
конечномерных нормированных пространствах);

--

графско
-
ориентированные методы, опирающиеся на сведение расписательных
з
адач к задачам раскраски графов и мультиграфов и на анализ свойств этих графов.

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

A
.
Разработка эффективных г
еометрически
х

методов

нахождения

приближённ
ых

решени
й

цеховых задач
, основанны
х

на алгоритмах компактного и нестрогого
суммирования векторов в заданных областях (или семействах областей) конечномер
ного
нормированного пространства.
Э
тот подход к приближённому решению цеховых задач на
построение кратчайших расписаний
,

р
одившийся одновременно (в 1974 году) в
Новосибирске и Харькове, в дальнейшем получил широкое развитие в работах С.В.
Севастьянова. Сил
а метода была продемонстрирована на широком круге задач (подробный
обзор результатов представлен в статье
[
S.V. Sevast'janov
(
1994)
]
.

В дальнейшем этот
подход активно использовался зарубежными авторами (см. серию статей американских
профессоров Christos K
oulamas
и

Gorg J. Kyparisis, а также работы
K
.
Jansen

и
S
.
Sviridenko
, посвящённые построению полиномиальных аппроксимационных схем для
задачи
job

shop
). Однако очевидно, что потенциал этого метода далеко не исчерпан.
Авторами проекта предполагается как
использование этого подхода к другим задачам
теории расписаний, так и дальнейшее развитие самого метода.

B
.
Многопараметрический анализ сложности задач.

До сих пор в работах
зарубежных авторов преобладают результаты по одномерному» (в лучшем случае


пло
скому») анализу сложности задачи в зависимости от одного либо двух каких
-
то
выбранных параметров. В то же время, исследуемые задачи зависят, как правило, от гораздо
большего числа параметров, и для получения более полной картины» сложности задачи от
всей
совокупности параметров желательно рассматривать все комбинации ограничений на
рассматриваемые параметры.
Новый

подход

к исследованию сложности задач
, хотя и
требует более тонкого и скрупулёзного анализа, является более перспективным в плане
достижения луч
шего понимания задачи и понимания природы её сложности. Данный
подход, являющийся детищем участников проекта (и описанный подробно в работе
[
S.

Sevastianov
(
2005
)
],

уже

показал свою перспективность
на ряде задач дискретной
оптимизации
(см., например,
[
А.В.

Кононов (2000)
]
, а также
[
Каширских К.Н. (2000)
])
.


20

C
.
Направление исследования задач с ресурсными ограничениями, основанное на
у
нифицированн
ом

подход
е

к
трактовке

ресурсных ограничений различных типов.

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

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

E
.
Область задач с прерываниями операций является наименее изученной областью
теории расписаний
. Даже для сравнительно простых задач (таких как классическая задача
job

shop
) свойства оптимальных расписаний изучены настолько слабо, что э
то не позволяет
строить даже простейши
е

алгоритм
ы

точного решения переборного типа. Вопросы
существования оптимальных расписаний со свойством целочисленности всех прерываний
решены лишь фрагментарно для некоторых конкретных типов целевой функции. А такие
ф
ундаментальные теоретические вопросы как гарантированное существование
оптимального решения (при условии, что множество допустимых решений не

пусто), и
принадлежность задачи распознавания классу
NP

(т.е. возможность полиномиального
решения задачи на недете
рминированной машине Тьюринга) практически вовсе не
затрагиваются в работах по теории расписаний. Тем не менее, у участников проекта есть
определённые наработки к решению данных проблем для достаточно общих задач теории
расписаний и календарного планирован
ия.


1.2.

Анализ актуальных проблем теории расписаний

Глобальной проблемой теории расписаний (как и дискретной оптимизации в целом)
является проблема установления сложности той или иной задачи. (Достаточно пояснить,
что проблема построения эффективных алгоритмо
в
точного либо приближённого
решения

21

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

примера рассмотрим классические цеховые задачи
job

shop

и
open

shop
. В качестве параметров, влияющих на сложность
задачи, можно рассматривать
такие параметры как: число работ, число машин, верхняя граница на число

операций
каждой работы, то же
-

для каждой машины, ограничение на число
различных

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

полученной задачи
. Например, при некоторых
значениях параметров задачи
open

shop

и
job

shop

могут быть по отдельности
по
линомиально разрешимыми, но их смешение приводит к возникновению существенно
более сложной (
NP
-
трудной в сильном смысле) задачи. Таким образом, само смешение»
задач различных типов также является неким параметром задачи. В качестве другого
примера рассмот
рим два типа задач: с прерываниями и без прерываний операций. В задачах
первого типа разрешается любое число прерываний любой из операций. В задачах второго
типа не разрешаются никакие прерывания вообще. Обычно, классическая теория
расписаний рассматривает

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

Другой глобальной проблемой является решение вопросов о существовании
оптимальных расписаний с определёнными свойствами. Так например, в задачах с
прерываниями операций интересной проблемой является определение мини
мальной
верхней границы (Г1) на число прерываний, не влияющей на длину оптимального
расписания. В тех случаях, когда задача с разрешением прерываний является
полиномиально разрешимой, а соответствующая задача без прерываний


NP
-
трудной,
возникает естестве
нный вопрос: при какой минимальной границе (Г2) на число прерываний,
возникающих в системе, задача остаётся гарантированно полиномиально разрешимой?
Интересно также установить соотношение между величинами Г1 и Г2. Другим примером
проблемы
установления свой
ств оптимальных решений
является определение
минимального числа миграций, не влияющего на длину оптимального
расписания в задаче

с
параллельными машинами и миграционными задержками. Наконец, в качестве третьего
примера подобной проблемы приведём проблему о
ценки числа внутренних простоев

22

(дыр») на машинах в системе
open

shop

в оптимальном расписании. Определение этой
величины важно как с теоретической, так и прикладной точек зрения, поскольку влияет на
эффективность алгоритмов
приближённого
решения данной з
адачи.

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

Остаются слабо изученными (с точки зрения анализа
их
сложности и построения
точных и приближённых алгоритмов решения) такие теоретические проблемы, имеющие
серьёзную прикладную значимость, как:



о
дномашинная задача с оборотными ресурсами при неодновременном
поступлении работ;



задача
open

shop

с маршрутизацией машин;



задача с параллельными поточными цехами (на минимум длины расписания
)
.


В
рамках проекта

планируется выполнить:



Анализ сложности и

разработку алгоритмов решения задачи с оборотными
ресурсами и неодновременным поступлением работ на минимум длины
расписания (а также


с другими целевыми функциями) в зависимости от
различных параметров и для различных вариантов машинной среды (в
частнос
ти, в зависимости от параметра число различных моментов
поступления работ»);



Анализ свойств оптимальных расписаний в задачах с прерываниями
операций;



Анализ сложности построения коротких» расписаний для цеховых задач;



Разработку эффективных алгоритмов ре
шения цеховых задач с
маршрутизацией;



Разработку эффективных алгоритмов решения задачи с

параллельными
поточными цехами;



Разработку
эффективных алгоритмов

отыскания множества всех оптимальных
расписаний для классической задачи Джонсона.


23


Обзор литературы п
о приоритетным направлениям теории расписаний
.
С
овременное состояние исследований в области
теории расписаний

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


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

cells
),
медицинское обслуживание
(
nurse

rostering
),
управление пакетами в сетях связи (
packet

routing
),
построени
е расписаний
для транспорта
(
transportation

scheduling
)
и др.

Из работ, посвящённых анализу сложности задач, преобладают те, которые содержат
лишь самый начальный уровень анализа


анализ точного решения задачи в общей
постановке. (Обычно речь не заходит о

построении полной карты сложности» задачи от
заданного набора параметров задачи


что мы ставим одним из приоритетов нашего
проекта.) Из алгоритмических подходов львиная доля публикаций содержит так
называемые метаэвристики» и экспериментальный анализ»

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

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

в Москве,
Ленинграде и других городах), практически перестали существовать, другие (такие как
Минская и Киевская школы)


оказались за рубежом». В этих условиях, по сути,
единственным активным научным центром по теории расписаний в России остаётся
Новос
ибирская школа по теории расписаний (основанная в 60
-
е годы прошлого века на базе
Института математики СО АН СССР такими её представителями как Н.И. Глебов, В.А.
Перепелица, Э.Х. Гимади, В.Э. Хенкин), а также её Омский филиал с активно работающим
В.В. Серв
ахом и его многочисленными учениками.
Некоторое оживление в последние годы

24

наблюдалось в этой области в Казани,


до тех пор, однако, пока А.А. Лазарев и его
ученики не перебрались в Москву и за рубеж.
Однако, несмотря на сравнительную
малочисленность» ро
ссийской группы исследователей по теории расписаний, научный
уровень их исследований явно превосходит среднемировой. В том числе, работы
участников данного проекта активно публикуются в международных журналах по
дискретной математике и исследованию операци
й, а сами участники проекта ежегодно
представляют свои новые результаты на международных конференциях по теории
расписаний и комбинаторной оптимизации.

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


немало теоретически значимых работ, не теряющих
своей актуальности, находится в публикациях прошлых лет, в то время как в потоке
современных публикаций немало число конъюнктурных работ, не имеющих теоретической
либо практической ценности.

Видимо, од
ними из первых работ по теории расписаний являются работы Беллмана и
Гросса
[
Bellman

and

Gross

(
1954
)
]

и Джонсона
[
Johnson

(
1954
)]
, а первое упоминание о
теории расписаний» как о самостоятельной дисциплине встречается уже в статье Беллмана

1956 года
[
Bell
man

(
1956
)
]
. Одной из первых монографий по теории расписаний является
сборник статей под редакцией Мута и Томпсона
[
Muth

and

Thompson

(
1963)
]
, в основном
сконцентрированных на вычислительных аспектах алгоритмов. Более известной является
монограф
ия Конвея,
Максвелла и Миллера
[
Conway
,
Maxwell

and

Miller

(
1967)
]
, которая,
несмотря на некоторую несовременность», остаётся до сих пор интересной во многих
аспектах. Помимо детерминированных моделей, книга затрагивает стохастические аспекты
и вопросы из теории оче
редей. В то же время, книга Бэйкера
[
Baker

(
1974)
]

является
прекрасным обзором по детерминированным моделям. Она не затрагивает вопросов
вычислительной сложности, поскольку вышла непосредственно перед появлением
основополагающих работ Кука и Карпа. Вышедша
я в следующем году на русском языке
монография Танаева и Шкурбы
[
Танаев, Шкурба
(
1975)
]

описывает широкий спектр
результатов по применению метода ветвей и границ, а также методов линейного,
целочисленного и динамического программирования к теории расписани
й. Описываются
эффективные комбинаторные методы точного решения и многочисленные эвристики. Что
любопытно (и удивительно для книги, вышедшей в 1975 году), в ней описываются
локальные методы», использующие понятие окрестности» допустимого решения. В

25

целом

обозревается более четырёх сотен статей, из которых 215


на русском языке и 213


на английском и прочих языках (что свидетельствует об интенсивности ведения
исследований по теории расписаний в бывшем Советском Союзе).

Вышедшая уже в следующем году книга

Кофмана
[
Coffman

(
1976)
]
, являющаяся
собранием статей по детерминированной теории расписаний, уже затрагивает вопросы
вычислительной сложности задач. Учебник Френча
[
French

(
1982)
]

знак
омит

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

под
редакцией Демпстера, Ленстры и Ринноой Канна
[
Dempster
,
Lenstra

and

Rinnoo
y

Kan

(
1982)
]
.

Следующим, довольно интенсивным шагом в развитии теории расписаний оказался
выпуск на русском языке двухтомника Танаева с учениками. В первый том
[
Танаев, Гордон,
Шафранский

(
1984)
]

вошли результаты по одностадийным системам, а во второй
[
Т
анаев,
Сотсков, Струсевич
(
1989)
]



по многостадийным. В них, помимо методов точного
решения, уже встречаются описания некоторых результатов по приближённому решению
задач с гарантированными оценками качества. Также довольно продвинутой в
теоретическом пла
не является монография Блажевича и др.
[
Blazewicz
,
Cellary
,
Slowinski

and

Weglarz

(
1986)
]
, в которой рассматриваются задачи с ресурсными ограничениями, а
также многокритериальные задачи. Следующая кн
ига Блажевича и др.
[
Blazewicz
,
Ecker
,
Schmidt

and

Weglar
z

(
1993)
]

уже в значительной степени затрагивает вычислительные
аспекты в детерминированных моделях теории расписаний, а также вопросы практических
приложений этих задач на производстве. Более прикладной характер носит монография
Мортона и Пентико
[
Morton

and

Pentico

(
1993)
]
, в которой описывается большое число
эвристик, могущих оказаться полезными при решении практических задач. В 1994 году
издательство Клувер переводит на английский язык двухтомник Танаева
[
Tanaev

(
1994
)]
.
Вышедшая в том же году монографи
я Дузере
-
Пере и Ласерре
[
Dauz
`
ere
-
Per
`
es

and

Lasserre

(
1994)
]

концентрируется в основном на задачах типа
job

shop
, а сборник статей под
редакцией Цвебена и Фокса
[
Zweben

and

Fox

(
1994)
]

описывает ряд существующих систем
по составлению расписаний и их приме
нение. В следующем году выходит аналогичный
сборник под редакцией Брауна и Шерера
[
Brown

and

Scherer

(
1995)
]
. Множество
интересных статей по детерминированной ТР содержится в сборнике трудов конференции
под редакцией Кретьена, Кофмана, Ленстры и Лю
[
Chreti
enne
,
Coffman
,
Lenstra

and

Liu

(
1995)
]
. Учебник Бэйкера
[
Baker

(
1995)
]

является неплохим введением в область задач на
упорядочение и построение расписаний. Брукер
[
Brucker

(
1995)
]

в первой редакции своей

26

книги представляет достаточно подробный анализ слож
ности многих задач
детерминированной ТР. Паркер
[
Parker

(
1995)
]

даёт аналогичный обзор, но при этом в
значительной мере концентрируется на задачах с ограничениями предшествования и других
графско
-
теоретических моментах. Книга Сьюла
[
Sule

(
1996)
]

представл
яет из себя текст
более прикладного характера, где обсуждаются интересные реальные прикладные задачи.
Книга Блажевича и др.
[
Blazewicz
,
Ecker
,
Pesch
,
Schmidt

and

Weglarz

(
1996)
]

является
расширенной редакцией предыдущей книги примерно тех же авторов
[
Blaze
wicz
,
Ecker
,
Schmidt

and

Weglarz

(
1993)
]
. Монография

Овацика

и

Узсоя

[
Ovacik

and

Uzsoy

(
1997)
]

всецело посвящена методам декомпозиции сложных моделей
job

shop
.
В том же году
выходит два сборника под редакцией Ли и Лая
[
Lee

and

Lei

(
1997)
]
, содержащих как м
ного
интересных теоретических, так и прикладных статей. В 1998 году выходит ещё одна
монография Танаева с учениками
[
Танаев
(
1998)
]
, посвящённая так называемым
групповым» задачам теории расписаний. Книга Пинедо и Чао
[
Pinedo

and

Chao

(
1999)
]

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

В новом столетии поток монографий по теории расписаний открывается книгой
Баптиста и др.
[
Baptiste
,
LePa
pe

and

Nuijten

(
2001)
]
, покрывающей область применения
техники
constraint

programming

к задачам типа
job

shop
, и сборником статей под ред.
Нарейека
[
Nareyek

(
2001)
]
, посвящённых применению методов локального поиска к той же
задаче. Книги Ткиндта и Бело
[
T

kindt

and

Billaut

(
2002
)
,
(
2006)
]

содержат отличные обзоры
по многокритериальной теории расписаний. В 2004 году под редакцией Льюнга появляется
очень солидное издание 
The

Handbook

of

Scheduling
»
[
Leung

(
2004)
]
, насчитывающее
более тысячи страниц и содержа
щее множество интересных обзорных статей по всем
аспектам современной теории расписаний. Книга Пинедо
[
Pinedo

(
2005)
]

является
расширенной и дополненной редакцией более ранней книги
[
Pinedo

and

Chao

(
1999)
]
. В том
же году выходит книга Швиндта
[
Schwindt

(
2
005)
]
, посвящённая задачам
project

scheduling

с
ресурсными ограничениями.

Книга под редакцией Херрмана
[
Herrmann

(
2006)
]

рассказывает о реальных системах составления расписаний для промышленных
предприятий. С самого начала в ней не только подчёркивается её

прикладной характер, но и
делается как бы противопоставление этих работ теоретическим исследованиям, ведущимся
в теории расписаний и не приносящим никакой пользы для нужд реальных производств».
Также в предисловии к книге подчёркивается, что книга никоим

образом не затрагивает
таких (также прикладных) областей применения теории расписаний как
transportation

scheduling
,
nurse

rostering
,
time

tabling

и

project

scheduling

(куда можно было бы добавить

27

также
packet

routing

и некоторые другие, не упомянутые авт
ором области). В том же году
выходит небольшая теоретическая монография Лазарева и Гафарова
[
Лазарев
(
2006)
]

на
русском языке, посвящённая одной специальной проблеме из
machine

scheduling
, а также
книга Брукера и Кнуст
[
Brucker
,
Knust

(
2006)
]
, в которой ра
ссматриваются различные
усложнённые (по сравнению с классическими) модели и задачи теории расписаний. Для
решения последних предлагаются как всевозможные эвристики, так и точные алгоритмы.

2007 год выдался весьма урожайным» на монографии по теории расписа
ний и её
приложениям. Было опубликовано 7 книг! Во
-
первых, выходит значительно дополненное
пятое издание книги Брукера
[
Brucker

(
200
7
)
]
, новая книга Блажевича с соавторами
[
Blazewicz
,

Ecker
,
Pesch
,
Schmidt

and

Weglarz

(
2007)
]
,
посвящённая как теоретическим

вопросам, так и приложениям теории расписаний; книга Даванде и др.
[
Dawande
,
Geismar
,
Sethi

and

Sriskandarajah

(
2007)
]
,
посвящённая задачам на построение расписаний для
роботизированных производств
,

а также


книга под редакцией Левнера
[
Levner

(
2007)
]
,
в

которой рассматриваются теоретические и прикладные проблемы многостадийных систем.

Ещё одна русскоязычная монография Лазарева и Гафарова
[
Лазарев
(
2007)
]

рассматривает
задачи с ограничениями предшествования и ресурсными ограничениями. Наконец, в
монографи
и Йозефовской
[
Jozefowska

(
2007)
]

рассматриваются модели и алгоритмы для
компьютерных и производственных систем с нетрадиционными (нерегулярными) целевыми
функциями от моментов завершения работ.

В 2008 году выходит третье издание книги Пинедо
[
Pinedo

(
2008
)
]
, а также
английский перевод книги под редакцией Билло и др.
[
Billaut
,
Moukrim

and

Sanlaville

(
2008)
]
, первоначально (в 2005 году) опубликованной на французском языке. Книга
посвящена вопросам устойчивости и гибкости расписаний.

Наконец, в 2009 году выхо
дит
книга Бэйкера и Трища
[
Baker

and

Trietsch

(
2009)
]
,
являющаяся значительно дополненным
переизданием более ранней монографии Бэйкера
[
Baker

(
1995)
]
.

Помимо упомянутых выше четырёх десятков монографий результаты по теории
расписаний освещались в необозрим
ом количестве обзорных статей. Ясно, что в данном
отчёте нет возможности перечислить их все. Тем не менее, мы не можем не упомянуть
наиболее значимых работ (так называемых 
milestones
»

на пути развития теории
расписаний). Одной из таких значимых работ оказ
алась 80
-
страничная обзорная статья Лолэ
и др.
[
Lawler
,
Lenstra
,
Rinnooy

Kan

and

Shmoys

(
1993
)
]
, в которой приведена трёхпольная
классификация задач из такой обширной области теории расписаний как
machine

scheduling
.
(
Следует отметить, что
,

несмотря на зам
етные недостатки этой системы, ей до сих пор
пользуется большинство расписальщиков», работающих в данной области.) Другим
верстовым столбом», наиболее полно зафиксировавшим текущие достижения теории

28

расписаний (на момент написания статьи), была статья Че
на, Поттса и Вёгингера
[
Chen
,
Potts

and

Woeginger

(
1998)
]
.

Из

последних

обзоров

следует

упомянуть

статью Вонга и др.
[
Wang
,
Zhang
,
Gao

and

Li

(
2008)
]
, посвящённую многокритериальной оптимизации, и статью Левнера

и

др
.
[
Levner
,
Kats
,
L
ó
pez

de

Pablo
,
Cheng

(
2010)
]
,
описывающую текущее состояние в такой
нетрадиционной области исследований как
cyclic

scheduling

(специфика рассматриваемых
здесь задач состоит в том, что множество работ бесконечно).


1.3. Обзор проблем в области поиска подмножеств похожих» векто
ров и
кластерного анализа

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

В первой части этих работ


[
Бабурин

А
.Е.

(2007)
]
, [
Гимади

Э.Х. (2006)
],
[

Кельманов

А.В

(2008), (2009)
]
-

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

Во второй части упомянутых работ
-

[
Долгушев А.В
. (2010)
], [
Aloise

D
.

(2008)
],
[
Dasgupta

S
.
(2007)
], [
Mahajan

M
.

(2009)
]
-

рассматривалась модель
структурированных
данных, в которой заданное множество векторов содержит непересекающиеся подмножества
-

кластеры, включающие близкие» (по критерию минимума суммы квадратов расстояний)
между собой векторы. Проблема анализа данных состояла в разбиении зада
нного множества
на подмножества по указанному критерию. Оптимизационная задача, к которой сводится эта
проблема анализа данных, широко известна под названием MSSC (Minimum
-
Sum
-
of
-
Squares
Custring). В некоторых публикациях эта же задача фигурирует под наз
ванием k
-
mans. В
работах [
Долгушев А.В.

(2010)
], [
Mahajan

M
. (2009)
] показано, что задача MSSC в форме
верификации свойств NP
-
полна.


29

К числу неизученных относится следующая задача. Дано: конечное множество
векторов евклидова пространства. Найти: подмножес
тво векторов заданной мощности такое,
что сумма квадратов расстояний между всевозможными парами векторов из этого
подмножества минимальна. К этой задаче сводится типичные для многих приложений,
проблемы. Однако до настоящего времени она не изучена, несмотр
я на содержательное
сходство с задачами
,

исследованными в
вышеупомянутых работах
.


1.4.
Обзор проблем дискретного анализа и теории графов в задачах хранения,
обработки, передачи и защиты информации

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

и
преобразование Барроуза
--
Уилера. Описаны наиболее известные методы сжатия данных:
блочное,
равномерное по выходу и арифметическое кодирование, схема кодирования
Лемпела
--
Зива и методы интервального кодирования. Приведены оценки избыточности и
трудоемкости перечисленных методов. Даны схемы доказательства для некоторых наиболее
важных утвержден
ий. Кроме того, рассмотрены задачи рандомизации сообщений и
кодирования с синхронизацией, а также способы кодирования текстов на естественных
языках и источников с низкой энтропией. Теория кодирования дискретных источников
исследует задачу сжатия сообщен
ий без потери информации. Под сообщением
подразумевается конечное или бесконечное слово в некотором алфавите,

порожденное
стационарным источником. Источником называется последовательность одинаково
распределенных случайных величин, множество значений кот
орых
-

алфавит источника.
Кодированием называется инъективное отображение множества слов алфавита источника в
множество двоичных слов, а стоимостью кодирования
-

отношение средней длины кода
сообщения к длине сообщения.

В

статье

[
Shannon

C
.
E
.
(
1948
)],

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

разность
между стоимостью и энтропией
-

является осно
вным критерием качества кодирования.
Другими важными характеристиками кодирования являются объем памяти, который
требуется при программной реализации метода, и среднее время кодирования и
декодирования, измеряемое в операциях над битами. Основной область
ю применения
алгоритмов кодирования являются компьютерные программы сжатия данных (архиваторы).
Методы кодирования могут быть использованы также в криптографии (см.
[
Рябко Б.Я.


30

(
1997
)]
), задачах прогнозирования (см.
[
Рябко Б.Я.

(1003)]
) и поиска информации

[
Кричевский Р.Е.
(
1989)
]
.

Сделана попытка проследить основные направления развития теории кодирования
дискретных источников от задачи оптимального кодирования известного источника к задаче
оптимального универсального кодирования семейства источников и зад
аче построения
модели источника по сообщению; а также от побуквенного кодирования к арифметическому
кодированию и схеме кодирования Лемпела
--
Зива.

Кроме того, рассмотрены самосихронизирующиеся и омофонные коды, а также
способы

кодирования двух часто встр
ечающихся на практике видов источников: текстов на
естественных языках и источников с низкой энтропией.


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

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

нижние оценки дает свитчинговый метод, все верхние оценки на сегодняшний
день мало отличаются от тривиальных.

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

затронут вопрос
существования совершенных раскрасок при заданных параметрах: найдено новое свойство
совершенных раскрасок, достигающих границы корреляционной иммунности.


1.6. Анализ критериев восстановимости кода (с точностью до эквивалентности)
по полной или частичной информации о метрических соотношениях между
кодовыми вершинами

Доказано, что для восстановления произвольного двоичного кода с точностью до
эквивалентности
достаточно знать размерности всех его подкодов чётной мощности.


31

Показано, что теорема носит неулучшаемый характер.

Пусть два произвольных двоичных кода C1 и C2 имеют одинаковую мощность и
длину n. Биекция кодов C1 и C2 называется сильной изометрией, если
для каждого
подмножества кода C1 его размерность совпадает с размерностью образа. Здесь под
размерностью кода подразумевается размерность минимальной грани двоичного куба,
содержащей этот код. Соответственно, биекция называется полусильной изометрией, ес
ли
равенство размерностей имеет место для всех подкодов чётной мощности. Заметим, что и
сильные, и полусильные изометрии являются изометриями в традиционном смысле.

Обычно проблема жёсткости кодов формулируется, как проблема продолжения
изометрии пары код
ов до эквивалентности
[
Августинович С.В.,
(2003)], [
Solov
'
eva

F
.
I
.

(
1998
)]
. Мы рассматриваем несколько иную постановку. Код называется метрически
жёстким, если он однозначно (как вариант
-

с точностью до эквивалентности)
восстанавливается по некоторому н
абору своих метрических инвариантов. В качестве
инвариантов могут выступать следующие: набор попарных расстояний между кодовыми
вершинами
[
Августинович

С.В.
(1994)]
; граф минимальных расстояний кода (
[
Августинович

С.В.
(1998)]
,
[
Могильных И.Ю.
(
2009
)], [
M
ogilnykh

I
.
Yu
.

(
2009
)]
; граф фиксированных
расстояний гиперкуба
[
Красин В.Ю.
(
2006
)
; наборы троек вершин кода, попарные
расстояния между которыми фиксированы.

Наиболее сильным инвариантом оказался полный набор размерностей подкодов кода.
[
Августинович С.В.

(
2000
)]
. Наши исследования показывают, что этот инвариант избыточен.
Именно, для однозначного восстановления двоичного кода достаточно знать размерности
только подкодов чётной мощности. Доказано также, что этот набор инвариантов минимален.

Рассмотрим па
ру двоичных кодов одинаковой мощности и длины. В работе
[
Августинович С.В.
(
2000
)]

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

следствие:
полусильно изометричные двоичные коды эквивалентны.


1.7.
Анализ новых конструкций бент
-
функций, используемых для построения
кодов постоянной амплитуды в системах CDMA (Сod Division Mutip Accss)

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

32

булевы функции называются бент
-
функциями. Актуальность исследования бент
-
функций
подтверждается их многочисленными теоретическим
и и практическими приложениями.

Бент
-
функции активно применяются в технологиях цифровой сотовой связи, а именно
в технологии CDMA, использующейся большинством поставщиков беспроводного
оборудования во всем мире согласно стандартам IMT
-
2000 мобильной связи

третьего
поколения (в России


стандарты IMT
-
MC 450 или CDMA
-
450).

Исследованы нижние оценки числа бент
-
функций, которые могут быть получены с
помощью итеративных конструкций, а именно с помощью конструкции A.Cantaut and
P.Charpin (2003). Показано, что
задача оценки числа итеративных бент
-
функций тесно
связана с проблемой декомпозиции булевых функций в сумму двух бент
-
функций.
Приведена нижняя оценка числа итеративных бент
-
функций, которая предполагается
асимптотически точной. С использованием метода Мон
те
-
Карло подсчитано число
итеративных бент
-
функций от малого числа переменных. Основываясь на проведенных
численных экспериментах, сформулированы гипотезы об асимптотическом значении числа
всех бент
-
функций.


1.8.

Обзор проблем маршрутизации в современных
беспроводных сенсорных
сетях и анализ существующих методов глобальной маршрутизации при
проектировании СБИС

Рассмотрим задачу построения коммуникационной сети (без ограничения общности
можно считать её деревом), связывающей множество сенсоров. Предполагает
ся, что
расположение сенсоров известно, и для связи они используют беспроводной интерфейс.
Энергия сенсора ограничена ёмкостью аккумуляторной батареи, а энергетические затраты на
связь пропорциональны дальности передачи. Если известно дерево, связывающее с
енсоры,
то дальность передачи сенсора определяется расстоянием до самого дальнего соседнего (в
дереве) сенсора.

Вопросу построения коммуникационной сети, однозначно определяемой дальностью
передачи её элементов, посвящён целый ряд публикаций, среди которы
х выделим
следующие.

В

работе

[
L
.
M
.
Kirousis

(
2000
)
]
рассматривается

проблема

потери

энергии

при

передаче

пакетов

данных

с

использованием

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

33

R
3

(Ранее в [A.
E.F. Clementi

(
2000
)
]
была

показана

NP
-
трудность

задачи

в

R
2
).
Для этого
случая предложен 2
-
приближенный алгоритм с квадратичной трудоёмкостью (от числа
вершин).

В статье [P. Carmi

(
2007
)
] рассмотрен случай, когда каждый передатчик способен
передавать на
два расстояния: близко» и далеко». Показано, что задача остаётся NP
-
трудной и в этом случае. Предложен такой приближённый полиномиальный алгоритм, что
число передатчиков на дальнее расстояние не более 11/6 от числа таких передатчиков в
оптимальном решени
и. Также предложен экспоненциальный 9/5
-
приближённый алгоритм.

В работе [E. Athaus

(
2006
)
] рассматриваемую задачу в евклидовом пространстве
полиномиально свели к задаче Штейнера на специально построенном графе. Это позволило
получить 5/3

+



вполне полин
омиальную аппроксимационную схему (FPTAS), а также 11/6

приближенный полиномиальный алгоритм.

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

(см., например,
[J. Wu (
2005)
]
)

рассматривается

минимальное

остовное

дерево
.
Очевидно, что минимальный остов не всегда является оптимальным
коммуникационным деревом.

В [Ерзин А.И.

(
2010
)
] исполнителями проекта рассмотрена общая задача построения
комму
никационного дерева в произвольном взвешенном графе с неотрицательными весами
рёбер. Показано, что такая задача также является NP
-
трудной в сильном смысле, а
минимальный остов является 2
-
приближённым решением. Найдены частные случаи
полиномиальной разрешим
ости задачи. Определены пределы аппроксимируемости задачи.
Предложен эвристический алгоритм.

Задача выбора древовидной коммуникационной сети, а также оптимальных
соединений в этой сети с заданными ограничениями на времена получения сигналов
вершинами
-
терми
налами
,

является NP
-
трудной как с аддитивной функцией задержки (время
прохождения сигнала по пути равно сумме временных задержек входящих в путь ребер), так
и в модели Эльмора [
Elmore W.C.
(
1948
)
]. Например, в сигнальном дереве (cock tr),
которое отвеч
ает за синхронизацию вычислительных систем, время прихода сигналов в
терминалы ограничено как сверху (что естественно), так и снизу (что продиктовано
необходимостью минимизации, так называемого, временного перекоса


cock skw). Если
коммуникационная сеть

является частью интегральной схемы, то время распространения

34

сигнала обычно оценивается формулами Эльмора, что делает задачу ещё сложнее, но при
этом и более важной, т.к. время передачи данных в интегральных схемах составляет до 60%
временных затрат. При
несвоевременном получении сигналов терминалами понижается
производительность всей сист
емы [Erzin A.I. (
2000
)
].

Глобальная трассировка является одним из важнейших этапов проектирования СБИС,
на котором для ка
ж
дой цепи определяется множество используемых об
ластей
маршрутизации в усл
о
виях ограничений на трассировочные ресурсы и время прохождения
сигнала. В лит
е
ратуре встречается несколько формулировок задачи глобальной трассировки
(ЗГТ) с различными критериями и о
г
раничениями, подробный обзор которых приведен

в
работе [Kastnr R.

(
2002
)
]. Основной целью глобальной трассировки является
маршрутизация всех цепей СБИС без нарушения ограничений. При этом даже простейшая
постановка, в которой требуется осуществить трассировку двухтерминальных цепей в
условиях огран
и
ченности трассировочных ресурсов, является NP
-
трудной задачей. Для
решения ЗГТ исследователями предложены различные подходы, в которых трассировка, как
правило, осуществляется лишь на двух слоях. В основе этих подходов лежат алгоритмы
последовательной марш
рутизация, алг
о
ритмы трассировки с разрывом связей и поиском
новых соединений, алгоритмы, основанные на решении задач о мног
о
продуктовом потоке,
иерархические методы, а также различные метаэвр
и
стики. При проектировании
современных СБИС на этапе глобальной
маршрутизации, наряду с учетом трассировочных
ресурсов, все большее внимание уделяется времени прохо
ж
дения сигнала. При этом
плотность соединений и временная задержка являются, как правило, конкурирующими
критериями, и в литературе практически отсутствуют
публикации, в которых эти критерии
рассматриваются совместно.

Основные подходы к решению задач глобальной маршрутизации изложены в
монографиях [S.

M.

Sait

(
1995
)
], [
M
.

Sarrafzadeh

(
1996
)
], [
N
.

A
.

Sherwani

(
1999
)
].

Книга

[
A
.

B
.

Kahng

(
1995
)
]
и

обзорная

статья

[
J
.

Cong

(
1996
)
]
целиком

посвящены

задачам

маршрутизации
,
но

основное

внимание

там

уделяется

задаче

построения

единственной

сети
.

Задача глобальной маршрутизации входит в число теоретически трудных проблем
(является NP
-
трудной), поэтому для ее реше
ния разрабатываются, в основном,
приближенные алгоритмы. Одна из возможных классификаций выделяет три класса таких
алгоритмов: последовательные алгоритмы, параллельные алгоритмы и метаэвристики.

Последовательная маршрутизация.

Наиболее популярным подходом

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

35

упорядочиваются в соответствии с некоторым критерием их важности, а затем производится
их поочередная маршрутизация.

Алгоритм поиска в лабиринте
, предназначенный д
ля

нахождения кратчайшего пути в
глобальном графе был впервые предложен в работе [C.

Y.

Lee

(
1961
)
] и основан на методе
поиска в ширину. Причиной популярности этого метода является простота реализации (даже
при наличии препятствий) и гарантия нахождения оп
тимального решения в случае его
существования. Некоторые способы ускорения алгоритма поиска в лабиринте представлены
в статьях [
F.

Hadlock

(
1975
)
]
и

[
J
.

Soukup

(
1978
)
].

Основным недостатком алгоритма поиска в лабиринте и его многочисленных
вариаций являетс
я необходимость хранения значительного объема информации для каждой
вершины. Для сокращения числа ячеек памяти был разработан
алгоритм пробных связей
,
изложенный в статьях [
D.

W.

Hightower

(
1969
)
], [
K
.

Mikami

(
1968
)
]. Этот алгоритм,
основанный на методе по
иска в двух направлениях существенно экономичнее алгоритма
поиска в лабиринте, но он не гарантирует нахождения кратчайшего пути между двумя
точками.


Описанные алгоритмы не применимы для многотерминальных сетей. В

книге

[
C
.

Schen

(
1986
)
] такие сети разбив
аются на несколько двухтерминальных сетей, которые
затем трассируются поочередно.

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

статье

[
C
.

Chiang

(
1990
)
]
задача

глобальной

маршрутизации

решается

последовательным

построением

минимаксного

дерева

Штейнера

для

каждой

сети
.
Вес ребер сети вы
числяется по оценкам плотности. Доказано, что
построенное дерево является оптимальным минимаксным деревом Штейнера. Веса ребер
динамически корректируются после маршрутизации каждой сети, отражая изменения
плотности.

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

статье

[
C
.

Chiang

(
1994
)
]
предложен алгоритм одновременной минимизации двух указанных кри
териев, основанный
на последовательной маршрутизации сетей с использованием приближенного алгоритма
построения прямоугольного дерева Штейнера минимального веса, отличающегося от
оптимального не более чем в два раза.


36

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

Параллельная

маршрутизация.
Одним из способов преодоления недостатков
последовательного подхода является использование алгоритмов одновременной
маршрутизации всей совокупности сетей, основанных на решении
задачи целочисленного
линейного программирования
(
ЦЛП
).

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

Один из первых известных
иерархических методов маршрутизации

был предложен в
работе [M.

Burstein

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

Общей проблемой иерархических методов является то, что маршрутизация,
выполненная на определенном уровне иерархии, может оказатьс
я не оптимальной на
следующем уровне. Для преодоления этого недостатка в статье [M.

Hayashi

(
1995
)
]
предложен комбинированный метод решения многоуровневой задачи глобальной
маршрутизации.

Задача глобальной маршрутизации может быть сформулирована как
задача

о
многопродуктовом потоке в сети
. В

статье

[
E
.

Shragowitz

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

В

статье

[
F
.

Shahrokhi

(
1990
)
] предложен приближенный алгоритм для быстрого
решения двухтерминальной дробной задачи о многопродуктовом потоке. В контексте задачи

37

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

Метаэвристики.
Основная идея этих алгоритмов заключается в дополнении
традиционных алгоритмов наискорейшего спуска определенными механизмами,
позвол
яющими не ограничиваться нахождением локального минимума. Одним из наиболее
известных методов такого типа является алгоритм имитации отжига, представленный в
работе [S. Kirkpatrick

(
1983
)
].
В

статье

[
M
.

P
.

Vecchi

(
1983
)
] на основе алгоритма имитации
отжиг
а предложен алгоритм решения задачи глобальной маршрутизации для случая
двухтерминальных сетей, в которых разрешенное число поворотов не превышает 2.

Известен пакет прикладных программ Timbr
-
Wof, в котором метод имитации отжига
используется для решения
задач размещения и глобальной маршрутизации. Для каждой сети
строится множество деревьев
-
кандидатов, и одно из этих деревьев выбирается случайным
образом в качестве начального решения. Каждая итерация алгоритма состоит в замене
одного дерева другим для нек
оторой сети. Критерием качества решения является суммарное
переполнение пропускных способностей ребер. Сеть, для которой производится замена
дерева, выбирается случайным образом из множества сетей, пересекающих ребра, на
которых имеется переполнение.

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

A.

Chen

(
1989
)
] (
эволюционный

алгоритм
), [
H
.

Esbensen

(
1994
)
] (
генетический

алгоритм
)
и

[
H
.

Youssef

(
1999
)
] (
поиск

с

запретами
).

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

работе

[
D
.
Wang

(
1996
)
]
начальное решение строится алгоритмом поиска дерева Штейнера, учитывающим
временные ограничения. Далее для улучшения решения используется следующий подход. На
каждой итерации разрываются сети, проходя
щие через ребра с наибольшей плотностью.
Задача повторной маршрутизации формулируется как задача о многопродуктовом потоке и
решается с помощью иерархического алгоритма. Равномерность распределения проводников
достигается максимизацией равномерности глобал
ьного потока и минимизацией
максимальной плотности.


38

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

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

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


1.9.
Постановка математических моделей конкурентного размещения
предприятий с различным
и целевыми функциями в виде задач двухуровневого
целочисленного программирования

Исследую
тся
задачи, являющиеся обобщением хорошо известной задачи размещения
предприятий (средств обслуживания) на максимум
[
Береснев В.Л.

(
2005
)
].
В этих задачах в
отличие от

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

1.
9
.1. Задача Лидера в игре Штакельберга

Задач
и конкурентного размещения предприятий

будем формулировать на базе
и
з
вестной модели конкуренц
ии на рынке [
Stackelberg

H
.
Von

(
1952
)
], называемой игрой
Штакельберга. В этой модели имеются две соперничающие стороны: Лидер и
Посл
е
дователь, которые последовательно принимают решения, стремясь достичь свои,
вообще г
о
воря, различные цели. Сначала Лидер
принимает решения, зная цель, которую
стремиться достичь Последователь. Затем Послед
о
ватель, зная решение Лидера, принимает
свое решение, оптимизирующее его целевую фун
к
цию.

Задача Лидера в игре Штакельберга состоит в выборе такого решения, которое
ма
к
сими
зирует его целевую функцию, значение которой зависит и от опт
и
мального
решения, принятого последователем.


39

Пусть множество
A

задает множество возможных решений Лидера, а множество
B
(
x
)



множество возможных решений Последователя, при усл
о
вии, что Лидер при
нял решение
x

A
. Обозначим через
f
(
x
,
z
) целевую фун
к
цию Лидера, которая может выражать, например,
величину прибыли, получаемую Лидером, если он принял решение
x
, а Последователь


решение
z
. Аналоги
ч
но, через
g
(
x
,

z
) обозначим целевую функцию Последовател
я, равную,
например, прибыли, которую, получит Последователь, если Лидер выбрал решение
x
, а
П
о
следователь


реш
е
ние
z
.

Тогда задача Лидера в игре Штакельберга записывается как следующая задача
дву
х
уровневого математического программирования:


x

A
;



оптимальное решение задачи:


z

B
(
x
).

Эта задача
, как и всякая задача двухуровневого математического программирования
[
Dempe

S
.
,
2
002
]

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

A

задачи верхнего уровня. Аналогично, в задаче вер
хнего уровня в
качестве п
а
раметра присутствует оптимальное решение

задачи нижнего уро
в
ня.

Допустимым решением задачи Лидера будем называть пару
, где
x

A
, а



оптимальное решение задачи

нижнего уровня с параметром
x
.

Отметим, что рассматриваемая задача Лидера является корректной, если при любом
x

A

для любых допустимых решений

и

выпо
л
няется равенство
. Это условие спр
аведливо, в частности, когда при любом
x

A

задача
ни
ж
него уровня имеет единственное оптимал
ь
ное решение.

Если данное условие выполняется, то определение оптимального решения задачи
Л
и
дера не вызывает трудностей. Допустимое решение

я
в
ляется
оптимальным
, если

для любого допустимого реш
е
ния
.


40

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

Рас
смотрим два правила поведения Последователя при выборе им своего решения:
кооперативное
и

некооперативное.

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

В первом случае искомым решением задачи Лидера, которое будем называть
опт
и
мальным кооперативным

решением задачи, будет допустим
ое р
е
шение

такое,
что


Другими словами, допустимое решение

задачи Лидера является оптимал
ь
ным
кооперативным решением, если

для любого допустимого реш
е
ния
.

При некооперативном поведении Последователя наилучшим решением задачи Лид
е
ра
будем считать допустимое решение
, для которого


и называть его
оптимальным некооперативным
решением задачи Лидера
. Допуст
и
мое
решение

задачи Лидера будем называть допустимым некооперативным решен
и
ем,
если

для любого допустимого решения
. Тогда оптимальное
некооп
е
ративное решение


это такое решени
е, что

для любого
допустимого н
е
кооперативного решения
.

Таким образом, будем рассматривать две постановки задачи Лидера в игре
Штакел
ь
берга. В первой необходимо найти оптимальное кооперативное решение, а во

второй


о
п
тимальное некооперативное решение.

В некоторых случаях рассматриваемая задача Лидера, представленная как задача
двухуровневого математического программирования, может быть записана как

обычная



41

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

Предположим, что целевая функция Лидера
f
(
x
,

z
)
имеет вид

f
(
x
,

z
)

=
h
(
x
) +


g
(
x
,

z
),

где
h
(
x
)



произвольная функция, а




число любого знака.

Легко видеть, что в этом случае для любых допустимых решений

и

з
а
дачи Лидера выполняется равенство
. Поэтому для оптимального
значения целевой функции задачи Лидера справедливы равенства


Отсюда, если




0
, получаем


И, если



0
, то


Таким образом, если


� 0
, то задача Лидера записывается как

обычная


задача
м
а
тематического программирования вида


x

A
;

z

B
(
x
),

а если


0
, то как следующая максиминная задача


x

A
;

z

B
(
x
)
.


1.
9
.2. Математические модели конкурентного размещения предприятий

Сформулируем задачу конкурентного размещения предприятий как задачу Лидера в
игре Штакельберга. При этом, следуя терминологии игры Штакельберга, стороны,


42

откр
ы
вающие предприятия, будем называть соответственно Лидером и Последователем.
Введем необход
и
мые обозначения.

Обозначим через
I

 {1,…,
m
} множество предприятий (возможных мест ра
з
мещения
предприятий), а через

J

 {1,…,
n
}


множество потреб
и
телей. Сч
итаем, что для всякого
i

I

заданы величины
f
i

и
g
i

равные фиксированным затратам на открытие предприятия
i

с
о
ответственно
Л
идером и
П
оследователем. Для
i

I

и
j

J


через
p
ij

обозначим величину
дох
о
да, п
о
лучаемого предприятием
i

при обслуживании потребителя
j
.

Считаем, что для всякого
j

J

на множестве
I

задано отношение порядка

j
,
показ
ы
вающее предпочтения потребителя
j

при выборе им предприятия. Отношение
i


j

j

для
i
,
k

I

означает, что из двух открытых предприятий
i

и
k

потребитель
j

выберет
предприятие
i
. Считаем также, что отнош
е
ние
i


j

k

для
i
,
k

I

означает, что либо
i


j

k
, либо
i

=
k
.

Для формальной записи задачи используем следующие переменные:

x
i



переменная, показывающая открывает или нет
Л
идер предприятие
i

I
;

x
i

 1, если открывает и
x
i

= 0
, если нет;

x
i
j



переменная, показывающая является ли предприятие
i

I

на
илучшим

для
потр
е
бителя
j

J

среди всех предприятий, открытых
Л
идером.

z
i



переменная, показывающая открывает или нет
П
оследователь предприятие
i

I
;
z
i

 1, если открывает и
z
i

= 0,

если нет;

z
i
j



переменная, показывающая является ли предприятие
i

I
, открытое
П
оследов
а
телем, наилучшим для потребителя
j

J

среди всех предприятий, открытых
Л
идером и
П
о
следователем.

С использованием указанных переменных и введенных обозначений задача
ко
нк
у
ре
н
т
ного

размещения предприятий записывается следующим обр
а
зом:


(1.9.
2.1)


(1.9.
2.2)


(1.9.

43

2.3)


(1.9.
2.4)




оптимальное решение зад
ачи:

(1.9.
2.5)


(1.9.
2.6)


(1.9.
2.7)


(1.9.
2.8)


(1.9.
2.9)

Целевая функция (
1.
9.2.
1) сформулированной задачи выражает величину прибыли,
пол
у
чаемой
Л
идером с уч
етом потери части потребителей, захваченных»
П
оследователем.
Н
е
равенство (
1.
9.2.
2) реализует правило выбора потребителем наиболее предпочтительного
пре
д
приятия среди всех предприятий, открытых
Л
идером. Это же неравенство гарант
и
рует,
что каждый потребител
ь может выбрать для своего обслуживания не более одного о
т
крыт
ого
предприятия. Ограничение (
1.
9.2.
3) означает, что потребитель для своего обслуживания
может выбрать только открытое предприятие. Аналогичный смысл имеют целевая функция и
огр
а
ничения за
дачи (
1.
9.2.6)

(
1.
9.2.9). Целевая функция (
1.
9.2.
6) выражает суммарную
прибыль, получа
е
мую
П
оследователем, а неравенс
тво (
1.
9.2.
7) обеспечивает выполнение
правила выбора потр
е
бителем наиболее предпочтительного для него предприятия среди всех
предприятий, откр
ы
ты
х как
Л
идером, так и
П
оследователем. Помимо этого ограни
чение
(
1.
9.2.
7) показывает, что если предприятие открыто
Л
идером, то оно не может быть о
т
крыто
П
оследователем.

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

она включает задачу первого уровня (
1.
9.2.
1)

(
1.
9.2.
4), кот
о
рую будем называть
задачей Лидера

и обозначать
L
, и задачу второго уровня
(
1.
9.2.
6)

(
1.
9.2.
9), к
о
торую будем называть
задачей Последователя

и обозначать через
F
. Для
зада
чи (
1.
9.2.
1)

(
1.
9.2.
9) будем использовать об
о
значение (
L
,
F
).


44

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

В этом случае задача нижнего уров
ня в задаче конкурентного размещения
предпр
и
ятий записывается следующим образом:






Эту задачу будем обозначать через
F


, а задачу конкур
ентного размещения
предпр
и
ятий с такой задачей нижн
е
го уровня


через (
L
,
F


).

Обозначим через
X

= ((
x
i
), (
x
ij
))
допустимое решение задачи
L
, а через
Z

= ((
z
i
), (
z
ij
))
и

соответственно допустимое и оптимальное решение задач
F

и
F


.

Пару

назовем
допустимым решением

задачи (
L
,
F
) (задачи (
L
,
F


)), если
X



допустимое решение задачи
L
,
а


оптимальное решение задачи
F

(задачи

F


).

Обозначим через
L
(
X
,
Z
)
целевую функцию задач (
L
,
F
) и (
L
,
F


).

Допустимое решение

задачи (
L
,
F
) (задачи (
L
,
F


)) назовем
допустимым
н
е
кооперативным

решением задачи (
L
,
F
) (задачи (
L
,
F


)), если для всякого оптимального
р
е
шения
задачи

F

(задачи
F


) выполняется
неравенство
.

Допустимое некооперативное решение

задачи (
L
,
F
) (задачи (
L
,
F


)) назовем
оптимальным некооперативным

решением задачи (
L
,
F
) (задачи (
L
,
F


)), если для любого
допустимого некооперативного решен
ия

задачи (
L
,
F
) (задачи (
L
,
F


)) выполняется

45

неравенство
. При этом величину

будем называть
оптимал
ь
ным значением целевой функции задачи (
L
,
F
) (задачи (
L
,
F


)).

Далее основное вним
ание будет сосредоточено на проблеме вычисления
оптимальн
о
го значения целевой функции задач (
L
,
F
) и (
L
,
F


) и поиску оптимальных
некооперативных решений этих задач.































46




2

Показатели


2.1. Защиты диссертаций

Исполнителями НИР п
редставлен
ы

3


кандидатск
их

диссертаци
и

(см. Приложение
В
).


2
.
2
. Список студентов, аспирантов, докторантов и молодых исследователей,
закрепленных в сфере науки

и

образования
.

Зачислены в аспирантуру

ИМ СО РАН
:



Курочкин А
.
А
.
;



Плотников Р.В.
;



Истомин А.М.

П
ринят в штат ИМ СО РАН
:

Руднев А.С.

Принята в штат НГУ:

Алдын
-
оол Т.А.

2
.
3
. Количество подготовленных и опубликованных статей:

Опубликовано
17
, принято к печати
2
,
сдано в печать

1
5

ста
т
ей

(см. Приложение
А
).


2
.
4
.
Количество

сделанных докладов
:


Сделано
1
7

доклад
ов

на отечественных и
17

доклад
ов

на международных научных
форумах.

(см. Приложение
Б
).



47

3

Заключение


В процессе выполнения 1 этапа НИР пров
едены

следующие работы
.

1. Проведен о
бзор литературы и определен
ы

приоритетны
е

направлени
я

фундаментальны
х
исследований в различных областях современной кибернетики
.

2. Проа
нализ
ированы

актуальны
е

проблем
ы

теории расписаний
.

3. Проведен о
бзор проблем в области поиска подмножеств похожих» векторов и
кластерного анализа
. Очерчен
широкий класс неизученных и сл
або изученных
оптимизационных задач, связанных с поиском подмножеств векторов и кластерным
анализом в евклидовом пространстве.

4.

В о
бзор
е

проблем дискретного анализа и теории графов в задачах хранения, обработки,
передачи и защиты информации

сделана
попы
тка проследить основные направления
развития теории кодирования дискретных источников от задачи оптимального кодирования
известного источника к задаче оптимального универсального кодирования семейства
источников и задаче построения модели источника по сооб
щению
.

5. Приведен
краткий обзор
методов улучшения оценок числа совершенных 2
-
раскрасок
гиперкуба
.

6. Проведен а
нализ критериев восстановимости кода (с точностью до эквивалентности) по
полной или частичной информации о метрических соотношениях между код
овыми
вершинами
. С новых позиций рассмотрена
проблема жёсткости кодов
.

7. Проанализированы

новы
е

конструкци
и

бент
-
функций, используемых для построения
кодов постоянной амплитуды в системах CDMA (Сod Division Mutip Accss)
. Приведен
обзор и
сследован
ий

по
нижни
м

оценк
ам

числа бент
-
функций, которые могут быть получены
с помощью итеративных конструкций
.

8.

Проведен о
бзор проблем маршрутизации в современных беспроводных сенсорных сетях
.

Про
анализ
ированы

существующи
е

метод
ы

глобальной маршрутизации при проек
тировании
СБИС
.

9. Разработаны новые п
остановк
и

математических моделей конкурентного размещения
предприятий с различными целевыми функциями в виде задач двухуровневого
целочисленного программирования
.

В результате исследований
проведен обзор литературы
, п
роанализированы

и
поставлены основные задачи НИР. По ряду направлений
получены новые фундаментальные
результаты мирового уровня, которые доложены на различных научных форумах

и
опубликованы в монографиях и статьях
.




48

Приведены списки опубликованных работ,

выступлений на научных форумах, а также
другие показатели успешной работы в рамках данного проекта.

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

По результатам
1 этапа
НИР напрашивает
ся вывод о целесообразности продолжения
работ.































49

4.
Список использованных источников


1.

Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи
стандартизации

-


Новосибирск
:

Изд
-
во Наука
,

1978



323 с.

2.

Агеев А.А., Гимади Э
.Х., Курочкин А.А. Полиномиальный алгоритм решения
задачи размещения на цепи с одинаковыми производственными мощностями
предприятий // Дискретный анализ и исследование операций. Новосибирск: Изд
-
во ИМ СО РАН, 2009
.
-


Т. 16, № 5.
-

С. 3
-
17
.

3.

Гимади Э.Х.,
Курочкин А.А. Одна задача размещения с одинаковыми объемами
производства на случайных входных данных
//

Вестник НГУ. Математика. 2010, в
печати.

4.

Jain A.K.
,
Dubes R.C.

Algorithms for clustering data. Prentice Hall, New Jersey:
Englewood Cliffs, 1988.


320 P.

5.

Kaufman L., Rousseeuw P. Finding Groups in Data: An Introduction to Cluster
Analysis.
New York: John Wiley and Sons, 2005.
-

368 P.

6.

P. Arabie, L. J.

Hubert.
An overview of combinatorial data analysis. In P. Arabie, L. J.
Hubrt, and G. D Sot, ditors, Cassication and Custring, p. 5
-
63. New York:
World Publishing, 1996.

7.

Richard O. Duda
,
Peter E. Hart
,
David G.
Stork
.
Pattern Classification, 2nd Edition.
New York:John Wiley & Sons, 2001.


680 P.

8.


Edwards A. W. F., Cavalli
-
Sforza L. L. A Method for Cluster Analysis // Biometrics.
-

1965.
-

Vol. 21.
-

P. 362
-
375.

9.


Jain A.K. Data Clustering: 50 Years Beyond K
-
Mea
ns // Pattern Recognition Letters.
2010. Vol. 31, No. 8. P. 651
-
666.

10.

Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM'04).
2004.

11.

Интеллектуализация обработки информации: 8
-
я

международная

конференция
.
Республика

Кипр
,
г
.
Пафос
,
17

24
октября

2010
г
.:
Сборник

докладов
.


М
.:
МАКС

Пресс
, 2010.

12.

Hamming R. W. Error detecting and errorcorrecting codes // Bell Syst.Tech.J. 1950.
V.
29. P. 147
-
160.

13.

Зиновьев В. А., Леонтьев В.К. О совершенных кодах // (Препринт/ИППИ АН
СССР). 1972. Вып.

1. С. 26
-
35.

14.

Зиновьев В. А., Леонтьев В.К. Несуществование совершенных кодов над полями
Галуа // Проблемы управления и теории информации.
1973.
Вып
. 2.
С
. 123
-
132.


50

15.

Tietavainen

A
.
On

the

nonexistence

of

perfect

codes

over

the

finite

fields

//
SIAM

J
.
Appl
.

Math
. 1973.
V. 24. P. 88
-
96.

16.

Delsarte

P. An Algebraic Approach to the Association Schemes of Coding Theory //
Philips Res.
Rep. Suppl. 1973. V. 10. P.1
-
97.

17.

Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Равномерно упакованные коды // Пробл.
передачи информ. 197
1. Т. 7. N. 1. С. 38
--
50.

18.

Van Tilborg H. C. A. Uniformly packed codes // Ph. D. Thesis, Eindhoven University of
Technology, the Netherlands, 1975
.

19.

Delsarte P. An Algebraic Approach to the Association Schemes of Coding Theory //
Philips Res.
Rep. Suppl. 197
3. V. 10. P.1
-
97.

20.

Gordon M.D. Perfect Single Error
-
Correcting Codes in the Johnson Scheme // IEEE
Trans.
Inform. Theory. 2006. V. 52. N. 10. P. 4670
-
4672.

21.

Martin W. J. Completely

Regular Designs // J. Combin.
Designs. 1998. V. 6. N. 4. P.
261
--
273

22.

Dehon M
. On the existence of 2
-
designs $S_{
\
lambda}(2,3,v)$ without repeated blocks
// Discrete Math. 1983.
V. 43. P. 155
-
171.

23.

Hanani H. On quadruple systems // Canad.
J. Math. 1960. V. 15. P. 145
-
157

24.

Hartman A., Phelps K.T. Tetrahedral quadruple systems // Utili
tas Math. 1990.
V. 37. P.
181
-
189.

25.

Sevast'janov

S.V.

Discrete Appl. Math.
1994
.
V.
55
.

P. 59
-
82
.

26.

Sevastianov

S.

An introduction to multi
-
problems// Europea
n Journal of Operational Research, 2005, V. 165(2) P. 387
-
397
.

27.

Кононов

А.В.
, Севастьянов

С.В.

О сложности нахождения связной предписанной
раскраски вершин графа// Дискретный анализ и исследование операций.
2000
.

Сер.
1. Т. 7, N 2. С. 21
-
46
.

28.

Каширских К.Н.,

Севастьянов

С.В., Черных И.Д. Четырехпараметрический анализ
сложности задачи opn shop

// Дискретный анализ и исследование операций.
2000
.
Сер. 1. Т. 7 , N 4. С. 59
-
77
.

29.

Baker K.R. Introduction to Sequencing and Scheduling, John Wiley, NY
.
1974
.

30.

Baker K.R.
Elements of Sequencing and Scheduling, K. Baker, Amos Tuck School of
Business Administration, Dartmouth College, Hanover, NH 03755.

1995
.

31.

John Wiley &
Sons, Inc.

2009
.


51

32.

Baptiste P., Le Pape

C. and Nuijten W. Constraint
-
Based Scheduling, Kluwer Academic
Publishers, Boston.

2001
.

33.

Bellman R. Mathematical aspects of scheduling theory, J. Soc.
Industr. and Appl. Math.
2,
1956
, № 3, 168
-
205.

34.

Bellman R., Gross O. Some combinatorial problems arising

in the theory of multistage
processes, J. Soc.
Industr. and Appl. Math. 2,
1954
,
№ 3, 175
-
183.

35.

Billaut J.C., Moukrim A. and Sanlaville E. (eds.)
Flexibility and Robustness in
Scheduling, London: ISTE Ltd, Hoboken (USA): John Wiley & Sons, Inc.

2008
.

36.

J. Bla
zewicz, W. Cellary, R. Slowinski and J. Weglarz Scheduling under Resource
Constraints
-

Deterministic Models, Annals of Operations Research, Vol. 7, Baltzer,
Basel.

1986
.

37.

J. Blazewicz, K. Ecker, E. Pesch, G. Schmidt and J. Weglarz Scheduling Computer and
Manufacturing Processes, Springer Verlag, Berlin.

1996
.

38.

Blazewicz J., Ecker K., Pesch E., Schmidt G. and Weglarz J. Handbook on Scheduling.
From Theory to Applications, Berlin/New York: Springer, 2007.

39.

J. Blazewicz, K. Ecker, G. Schmidt and J. Weglarz Sche
duling in Computer and
Manufacturing Systems, Springer Verlag, Berlin.

1993
.

40.

D.E. Brown and W.T. Scherer (eds.)
Intelligent Scheduling Systems, Kluwer Academic
Publishers, Boston.

1995
.

41.

P. Brucker Scheduling Algorithms (First Edition), Springer Verlag, Ber
lin.

1995
.

42.

P. Brucker Scheduling Algorithms (Fifth Edition), Springer Verlag, Berlin.

2007
.

43.

Brucker P., Knust S. Complex Scheduling. Springer, 2006.

44.

B. Chn, C.N. Potts and G.J. Wogingr “A Rviw of Machin Schduing:
Complexity, Algorithms, and Approxi
mabiity”, in Handbookof Combinatoria
Optimization, D.
-
Z. Du and P. Pardalos (eds.), pp. 21

169, Kluwer Academic Press,
Boston.

1998
.

45.

P. Chretienne, E.G. Coffman, Jr., J.K. Lenstra, and Z. Liu (eds.) Scheduling Theory and
Applications, John Wiley, New Yor
k.
1995
.

46.

E.G. Coffman, Jr.
(ed.) Computer and Job Shop Scheduling Theory, John Wiley, New
York.

1976
.

47.

R.W. Conway,W.L.Maxwell, L.W. Miller Theory of Scheduling, Addison
-
Wesley,
Reading, MA.

1967
.

48.

S. Dauz`ere
-
P
ґ
er`es and J.
-
B. Lasserre An Integrated Approac
h in Production Planning
and Scheduling, Lecture Notes in Economics and Mathematical Systems, No. 411,
Springer Verlag, Berlin.

1994
.


52

49.

M.W. Dawande, H.N. Geismar, S.P. Sethi, and C. Sriskandarajah Throughput
Optimization in Robotic Cells, International Seri
es in Operations Research and
Management Science, Springer.

2007
.

50.

M.A.H. Dempster, J.K. Lenstra and A.H.G. Rinnooy Kan (eds.)
Deterministic and
Stochastic Scheduling, Reidel, Dordrecht.

1982
.

51.

S. French Sequencing and Scheduling: an Introduction to the Mat
hematics of the Job
Shop, Horwood, Chichester, England.

1982
.

52.

S.M. Johnson Optimal two
-
and
-
three stage production schedules with set
-
up times
incudd, Nav. Rs. Log. Quart. 1, № 1
,
1954, 61
-
68.

53.

J. Jozefowska Just
-
in
-
Time Scheduling: Models and Algorithms
for Computer and
Manufacturing Systems.
Springer.

2007
.

54.

J.W. Herrmann (ed.)
Handbook of production scheduling. New York: Springer
Science+Business Media.

2006
.

55.

E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys Sequencing and
Scheduling: Algorithm
s and Complexity, in Handbooks in Operations Research and
Management Science, Vol. 4: Logistics of Production and Inventory, S.S. Graves,
A.H.G. Rinnooy Kan and P. Zipkin, (eds.),
1993
,

pp. 445

522, North
-
Holland, New
York.

56.

C.
-
Y. Lee and L. Lei (eds.)
“Sch
duing: Thory and Appications”, Annas of
Operations Research, Vol. 70, Baltzer, Basel.

1997
.

57.

J.Y.
-
T. Leung (ed.)
Handbook of Scheduling, Chapman and Hall/CRC, Boca Raton,
Florida.

2004
.

58.

E. Levner (ed.)
Multiprocessor Scheduling: Theory and Applications
, Vienna: I
-
Tech
Education and Publishing.

2007
.

59.

E. Lvnr, V. Kats, D.A. Lópz d Pabo and T.C.E. Chng Compxity of Cycic
Scheduling Problems: A State
-
of
-
the
-
Art Survey, Computers & Industrial Engineering,
2010
,

59(2),
P.
352
-
361.

60.

T.E. Morton and D. P
entico Heuristic Scheduling Systems, John Wiley, NY.

1993
.

61.

J.F. Muth and G.L. Thompson (eds.) Industrial Scheduling, Prentice
-
Hall, NJ.

1963
.

62.

A. Nareyek (ed.)
Local Search for Planning and Scheduling, Revised Papers of ECAI
2000Workshop in Berlin, Germany,

Lecture Notes in Computer Science, No. 2148,
Springer Verlag, Berlin.

2001
.

63.

I.M. Ovacik and R. Uzsoy Decomposition Methods for Complex Factory Scheduling
Problems, Kluwer Academic Publishers, Boston.

1997
.

64.

R.G. Parker Deterministic Scheduling Theory, Cha
pman & Hall, London.

1995
.


53

65.

M. Pinedo Planning and Scheduling in Manufacturing and Services, Springer Series in
Operations Research, Springer, New York.

2005
.

66.

M.L. Pinedo Scheduling. Theory, Algorithms, and Systems.
Third Edition, Springer
Science+Business
Media.

2008
.

67.

M. Pinedo and X. Chao Operations Scheduling with Applications in Manufacturing and
Services, Irwin/McGraw
-
Hill, Burr Ridge, IL.

1999
.

68.

C. Schwindt Resource Allocation in Project Management, Berlin/Heidelberg: Springer
-
Verlag.

2005
.

69.

D.R. Sule In
dustrial Scheduling, PWS Publishing Company, Boston.

1996
.

70.

V.S. Tanaev, V.S. Gordon, Y.M. Shafransky Scheduling theory. Single
-
stage systems.


Dordrecht/Boston/London: Kluwer Academic Publishers.

1994
.

71.

V.S. Tanaev, Yu.N. Sotskov, V.A. Strusevich Schedulin
g theory. Multi
-
stage systems.


Dordrecht/Boston/London: Kluwer Academic Publishers.

1994
.

72.

V. T‱kindt and J.
-
C. Billaut Multicriteria Scheduling
-

Theory, Models, and Algorithms
(First Edition), Springer, Berlin.

2002
.

73.

V. T‱kindt and J.
-
C. Billaut Multicr
iteria Scheduling
-

Theory, Models, and Algorithms
(Second Edition), Springer, Berlin.

2006
.

74.

Xiao
-
Juan Wang, Chao
-
Yong Zhang , Liang Gao and Pei
-
Gen Li A survey and future
trend of study on multi
-
objective scheduling, Fourth International Conference on Nat
ural
Computation (ICNC '08). Proceedings.

2008
.

75.

M. Zweben and M. Fox (eds.)
Intelligent Scheduling, Morgan Kaufmann Publishers,
San Francisco, California.

1994
.

76.

А.А. Лазарев, Е.Р. Гафаров Теория расписаний. Минимизация суммарного
запаздывания для одного пр
ибора
.
2006
.


М.: Вычислительный центр им. А.А.
Дородницына РАН.

77.

А.А. Лазарев, Е.Р. Гафаров Теория расписаний. Исследование задач с
отношениями предшествования и ресурсными ограничениями
.
2007
.


М.:
Вычислительный центр им. А.А. Дородницына РАН.

78.

В.С. Танае
в, В.С. Гордон, Я.Н. Шафранский Теория ра
списаний. Одностадийные
системы
, М.: Наука.


79.

В.С. Танаев,

М.Я.

Ковалёв, Я.Н. Шафранский Теория расписаний. Групповые
технологии. Минск:
Институт технической кибернетики НАН Белоруссии
.

1998
.

80.

В.С. Танаев, Ю.Н. Сотс
ков, В.А. Струсевич Теория расписаний. Многостадийные
системы, М.: Наука.

1989
.

81.

В.С. Танаев, В.В. Шкурба Введение в теорию расписаний, М.: Наука.

1975
.


54

82.


Бабурин

А.Е., Гимади

Э.Х., Глебов

Н.И., Пяткин

А.В. Задача отыскания
подмножества векторов с максимальн
ым суммарным весом // Дискретный анализ
и исследование операций. Сер. 2. 2007. Т.14, №1. С. 32
-
42.

83.


Гимади

Э.Х., Кельманов

А.В., Кельманова

М.А., Хамидуллин

С.А.
Апостериорное обнаружение в числовой последовательности
квазипериодического фрагмента при зад
анном числе повторов // Сиб. журн.
индустр. математики. 2006. Т. 9, № 1(25). С. 55
-
74.

84.

Долгушев А.В., Кельманов А.В. К вопросу об алгоритмической сложности одной
задачи кластерного анализа // Дискретный анализ и исследование операций. 2010.
Т. 17, №2. С.
39
-
45.

85.


Кельманов

А.В., Пяткин

А.В. О сложности одного из вариантов задачи выбора
подмножества похожих» векторов // Доклады РАН. 2008. Т.421, №5. С. 590
-
592.

86.


Кельманов

А.В., Пяткин

А.В. Об одном варианте задачи выбора подмножества
векторов // Дискретный

анализ и исследование операций. 2008. Т.15, №5. С. 25
-
40.

87.

Кельманов А.В., Пяткин А.В. О сложности некоторых задач поиска подмножеств
векторов и кластерного анализа // Журн. вычисл. математики и мат. физики. 2009,
Т.49, №11. С. 2059
-
2067.

88.

Aloise D., Deshp
ande A., Hansen P., Popat P. NP
-
Hardness of Euclidean Sum
-
of
-
Squares Clustering // Les Cahiers du GERAD, G
-
2008
-
33.
2008. 4 p.

89.

Dasgupta S. The Hardness of k
-
means Clustering // Technical Report CS
-
2007
-
0890.
University of California, 2007.


6 p.

90.

MacQueen

J.B. Some Methods for Classification and Analysis of Multivariate
Observations // Proc. 5
-
th Berkeley Symp.
Of Mathematical Statistics and Probability.
1967. Vol. 1. P. 281
-
297.

91.

Mahajan M., Nimbhorkar P., Varadarajan K. The Planar k
-
means Problem is NP
-
H
ard //
Lecture Notes in Computer Science. 2009. Vol. 5431. P. 284
-
285.

92.

Phelps K.T., Stinson D.R., Vanstone S.A. The existence of simple $S_{3}(3,4,v)$ //
Discrete Math. 1989.
V. 77. P. 255
-
258.

93.

Shannon C.E. A mathematical theory of communication// Bell Sy
stem. Tech. J. 1948.
V.27, pt. I,. P.379
-
423; pt.II, P.623
-
656. Русский перевод: Шеннон К. Работы по
теории информации и кибернетике. М.: Изд
-
во иностр. лит
-
ры, 1963.

94.

Рябко Б.Я., Фионов А.Н. Быстрый метод рандомизации сообщений// Проблемы
передачи информа
ции. 1997. Т.33, Вып.3. С.3
-
14.

95.

Рябко Б.Я. Алгоритмический подход к задаче прогнозирования // Проблемы
передачи информации. 1993. Т.29, Вып.2. С.96
-
103.


55

96.

Кричевский Р.Е. Сжатие и поиск информации. М.: Радио и связь. 1989.

97.

Августинович С.В., Соловьёва Ф.И.

К метрической жесткости двоичных кодов//
Пробл. передачи информ.
-

2003.
-

Т.39, №2., С.23
-
28.

98.

Solov'evaF.I., Avgustinovich

S.V., Honold T., Heise W.
On the extendability


of code isometries// J.Geom.
-

1998.
-

V
.61.
-

P
.3
-
16
.

99.

Августинович

С.В. Об из
ометричности плотно упакованных бинарных кодов//
Дискретный анализ
-

Новосибирск: Ин
-
т математики, 1994.
-

С.3
-
5
.

100.

Августинович

С.В. К строению графов минимальных расстояний совершенных
бинарных (n,3)
-
кодов // Дискрет. анализ и исслед. операций. Сер.1.
-

1998.
-

Т.3,
№5.
-

С.3
-
5.

101.

Могильных И.Ю. О слабых изометриях кодов Препараты // Пробл. передачи
информ.
-

2009.
-

Т.45, №2., С.78
-
83
.

102.

Mogilnykh I.Yu., Ostergard P.R.J., Pottonen O., Solov'eva F.I. Reconstructing
extended perfect binary one
-
error
-
correcting

codes from their minimum distance graphs
// IEEE Trans. Inform. The
ory
-

2009. V.55., P.2622
-
2625.

103.

Красин В.Ю. О слабых изометриях булева куба // Дискрет. анализ и исслед.
операций. Сер.1.
-

2006.
-

Т.13, №4. С.26
-
32
.

104.

Августинович С.В. О сильной изометрии

бинарных кодов // Дискрет. анализ и
исслед. операций. Сер.1.
-

2000.
-

Т.7, №3.
-

С.3
-
5.

105.

L.M.
Kirousis
, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet
Theoretical Computer Science
, 2000, 243,
P.
289

305
.

106.

A.E.F. Clementi,

P. Penna, and R. Silvestri.
On the power assignment problem in
Electronic Colloquium on Computational Complexity
, 2000, 054
.

107.

P. Carmi, M.J. Katz. Power Assignment in Radio Networks with Two Power Levels
// Algorithmica, 2007, 47,
P.
183
-
2
01
.

108.

E. Althaus, G. Calinescu, I.I. Mandoiu, S. Prasad, N. Tchervenski, A. Zelikovsky.
Wireless Networks // Wireless Networks, 2006, 12(3), 287
-
299
.

109.

J. Wu, S. Yang.
Energy
-
Efficien
t Node Scheduling Models in Sensor Networks with
Adjustable Ranges // Int. J. of Foundations of Computer Science, 2005, v. 16, No. 1, p.
3
-
17
.

110.

Ерзин А.И., Шамардин Ю.В. Одна задача синтеза оптимального остовного
дерева // Труды Межд. кон
ф
. Интеллектуализа
ция обработки информации»
(ИОИ
-
8), Кипр, Пафос, 2010, 251
-
254
.


56

111.

Elmore W.C. The transient response of damped linear networks with particular
regards to wide
-
band amplifies // J. Appl.
Phys. 1948. V. 19. P. 55

63
.

112.

Erzin A.I.,
Cho

J.D. A deep
-
submicron Steine
r tree // Mathematical and Computer
Modelling.
№ 31. 2000. P. 215
-
226
.

113.

Kastner R., Bozorgzadeh E., Sarrafzadeh M. Pattern routing: use and theory for
increasing predic
t
ability and avoiding coupling // IEEE Trans. on CAD. 2002.
V. 21. P.
777
-
791.

114.

S.

M.

Sait

and H.

Youssef.
VLSI physical design automation

: theory and practice.
1995
.

115.

M
.

Sarrafzadeh

and

C
.

K
.

Wong
.
An introduction to VLSI physical design.

1996
.

116.

N
.

A
.

Sherwani
. Algorithms

for VLSI Physical Design Automation.

1999
.

117.

A.

B.

Kahng and G.

Robins.
On
optimal interconnections for VLSI.

1995
.

118.

J.

Cong, L.

He, C.
-
K.

Koh, and P.

H.

Madden. Performance optimization of VLSI
interconnect layout.
Integration

:
the

VLSI

Journal
,
vol
.

21, 1996
,

pp
.

1
-
94
.


119.

C.

Y.

Lee.
An algorithm for path connection and its applic
ation.
IRE Trans. on
Electronic Computers
, vol.
EC
-
10, 1961,

pp. 346
-
365
.

120.

F.

Hadlock.
Finding a maximum cut of a planar graph in polynomial time.
SIAM J.
on Computing
, vol.

11, 1975
,

pp.

885
-
892
.

121.

J
.

Soukup
.
Fast maze router.
Proc. of 15th DAC
, 1978, pp.

10
0
-
102.

122.

D.

W.

Hightower.
A solution to the line routing problem on a continuous plane.
Proc. 6th Design Automation Workshop
, 1969,

pp.

1
-
24
.

123.

K
.

Mikami

and

K
.

Tabuchi
.
A computer program for optimal routing of printed
circuit connectors.
Proc. IFIPS Conf.
, 1
968,

pp.

1475
-
1478
.

124.

C.

Schen.
VLSI placement and routing using simulated annealing.

1986
.

125.

C.

Chiang, M.

Sarrafzadeh, and C.

K.

Wong. Global routing based on Steiner Min
-
Max trees.
IEEE Trans. on CAD
, vol.

9, pp. 1318
-
1325, 1990
.

126.

C.

Chiang, C.

K.

Wong, and

M.

Sarrafzadeh. A weighted Steiner tree
-
based global
router with simultaneous length and density minimization.
IEEE Trans. on CAD
, vol.

13,
1994,

pp. 1461
-
1469
.

127.

M.

Burstein and R.

Pelavin.
Hierarchical wire routing.
IEEE Trans. on CAD
,
vol.

CAD
-
2, 1983,

p
p. 223
-
234
.

128.

M.

Hayashi and S.

Tsukiyama.
A hybrid hierarchical approach for multi
-
layer global
routing.
Proc.
European Desing and Test Conference
, 1995,

pp.

492
-
496
.

129.

E.

Shragowitz and S.

Kell. A global router based on a multicommodity flow model.
Integrati
on, the VLSI Journal
, vol. 5, 1987,

pp. 3
-
16
.


57

130.

F.

Shahrokhi and D.

W.

Matula. The maximum concurrent flow problem.
Journal of
the ACM
, vol. 37, 1990,

pp. 318
-
334
.

131.

S. Kirkpatrick, C.

D.

Gelatt, and M.

P.

Vecchi.
Optimization by simulated annealing.
Science
, vol. 220, 1983,

pp. 671
-
680
.

132.

M.

P.

Vecchi and S.

Kirkpatrick Global wiring by simulated annealing.
IEEE Trans.
on CAD
, vol. CAD
-
2, 1983,

pp. 215
-
222
.

133.

Y.

A.

Chen, Y.

L.

Liu, and Y.

C.

Hsu.
A new global router for ASIC design based on
simulated evolution.

Proc. Int. Symp. on VLSI Technology, Systems and Applications
,
1989,

pp. 261
-
265
.

134.

H
.

Esbensen
.
A macro
-
cell global router based on two genetic algorithms.
Proc.
EDAC
, ,1994

pp. 428
-
433
.

135.

H
.

Youssef

and

S
.

M
.

Sait
.
Timing
-
driven global routing for standard
-
cell VLSI
design.
Computer systems: Science and Engineering
, vol. 14, 1999,

pp. 175
-
185
.

136.

D. Wang and E. S. Kuh. Performance
-
driven interconnect global routing.
Proc.
Great Lake Symp. VLSI
, 1996,

pp. 132
-
136
.

137.

Береснев В.Л.

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

-


Н
о
восибирск
:

Изд
-
во Института математики
,

2005

-

408 с.

138.

Dempe S. Foundations of bilevel programming.
-

Dordrecht: Kluwer Ac. Pub., 2002.
-

332 p.

139.

Stackelberg H. von.
The theory of the market economy.
-

Oxford: Oxford Univ.

Press, 1952.
-

289 p.
















58

Приложение
А
.

Список публикаций

исполнителей


Опубликованные статьи:

1.

Alekseeva

E
.
V
.,
Kochetova

N
.
A
.,
Kochetov

Yu
.
A
.,
Plyasunov

A
.
V
.

A

heuristic

and

exact


for

the

dicrete

$(r|p)$
-
centroid

problem

//
L
ecture
N
otes
C
omputer
S
cience, Berlin: Springer, 2010.
-

V. 6022,
-

P.
11
--
22.

2.

Лавлинский С.М.

Государственно
-
частное партнерство на сырьевой территории
-

экологич
е
ские проблемы, модели и перспективы // Проблемы прогнозирования
.
-


2010
.

-

№ 1
.
-

С
. 99
-
111.

3.

Ерзин

А.И., Шамардин Ю.В. Одна задача синтеза оптимального остовного дерева //
Труды Межд. кон. Интеллектуализация обработки информации» (ИОИ
-
8), Кипр,
Пафос, 2010,
с.
251
-
254
.

4.

Бабурин А.Е.,
Гимади Э.Х.

Об асимптотической точности эффективного

алгоритм
а

решения

задачи
m
-
PSP на максимум в многомерном
евклидовом пространстве //
Труды ИММ УрО РАН, 20
1
0
,
Т. 1
5
. №
4
.
С. 21
-
32
.

5.

Гимади Э.Х.

О вероятностном анализе алгоритма решения

задачи о
p
-
медиане

//
Дискретный анализ и исследование операций. Новосибирск: Изд
-
во ИМ

СО РАН,
20
1
0. Т. 1
7
.



3
. С
.

11
-
19
.

6.

Кельманов А.В.

О сложности некоторых задач анализа данных // Журнал
вычислительной математики и математической физики. 2010, Т.50, №11. С. 2045
-
2051.

7.

Кельманов А.В.
, Пяткин А.В. NP
-
полнота некоторых задач выбора подм
ножества
векторов // Дискретный анализ и исследование операций. 2010. Т.15, №5. С. 31
-
45.

8.

K‱manov A.V.,

Khamidullin S.A. An Algorithm for Recognition of a Vector Alphabet
Generating a Sequence with a Quasi
-
Periodic Structure // Pattern Recognition and I
mage
Analysis.
2010. Vol. 20, No.4, pp. 451
-
458.

9.

A.V. K‱manov
. On the Complexity of Some Data Analysis Problems // Computational
Mathematics and Mathematical Physics, 2010, Vol. 50, No. 11, pp. 1941
-
1947.

10.

Кельманов А. В.

NP
-
полнота некоторых задач поис
ка подмножеств векторов // Труды
Института математики и механики УрО РАН. 2010. Т. 16, № 3. С. 121
-
129.

11.

Кротов Д.С.

О свитчинговой разделимости графа и его подграфов // Дискретный
анализ и исследование операций, 2010, , т. 17, №2, С. 46
-
56.

12.

Токарева Н.Н.

Обобщения бент
-
функций. Обзор работ // Дискретный анализ


и исследование операций, 2010, , т. 17, №1, С. 33
-
62.

13.

Августинович С.В., Могильных И.Ю.

Совершенные раскраски графов Джонсона


59


J(8,3) и J(8,4) в два цвета // Дискретный анализ и исследо
вание операций, 2010,



т. 17, №2, С. 3
-
19.

14.

Горкунов Е.В. Мономиальные автоморфизмы линейной и простой компонент кода


Хэмминга // Дискретный анализ и исследование операций, 2010, т. 17, №1, С. 11

33.

15.

Воробьёв К.В.
, Фон
-
Дер
-
Флаасс Д.Г. О сов
ершенных 2
-
раскрасках гиперкуба,


Сибирские Электронные Математические Известия , (2010), том 7,

С
. 65
-
75.

16.

Горкунов Е.В., Августинович С.В.

О восстановлении двоичных кодов по
размерностям их подкодов // Дискретный анализ и исследование операций,

2010,

т. 17,
№5, С. 15
-
21.

17.

Севастьянов С.В., Ситтерс Р.А., Фишкин

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

//

Автоматика и телемеханика.
N

10, 2010.

C
. 90
-
99.



Статьи
,

принятые к печати:

1.

Береснев В.Л., Мельников А.А.

Приближенные алгоритмы для задачи

конкурентного размещения пре
д
приятий // Дискретный анализ и исследование
операций.
-
2010
.
-

Т.

17,


№ 6.

2.

Алдын
-
оол Т.А., Ерзин А.И.,

Залюбовский В.В. Покрытие плоской обл
асти случайно
распределёнными сенсорами // Вестник НГУ. С
е
рия: математика, механика,
информ
а
тика, № 4, 2010
.


Статьи, сданные в печать:

1.

Береснев В.Л.,
Гончаров

Е.Н.,
Мельников А.А..

Локальный поиск по обобщенной
окрестности

//
Дискретный анализ и исследова
ние операций.

2.

V. Zalyubovskiy,
T. Aldyn
-
ool, A. Erzin
, H. Choo
. Energy
-
Efficient Coverage
-
Guaranteed
Node Scheduling Models in Sensor Networks with Random Deployed Sensors //
Proceedings, 2nd Int. Conf. on Internet (ICONI) 2010,
Philippines
.

3.

Гимади Э.Х.
,
Дементьев В.Т. Децентрализованная обобщенная задача о назначениях
// Сибирские электронные математические известия
, 2010.

4.

Гимади Э.Х., Курочкин А.А.

Одна задача размещения с одинаковыми объемами
производства на случайных входных данных // Вестник НГУ.
Мате
матика. 2010
.

5.

Э. Х. Гимади,

Е. Н. Гончаров, В. В. Залюбовский, Н. И. Пляскина, В. Н. Харитонова.
О программно
-
математическом обеспечении решения задачи ресурсно
-
календарного

60

планирования на примере освоения нефтегазовых ресурсов Восточной Сибири //
Вестни
к НГУ.
Математика. 2010.

6.

Кельманов А.В., Романченко С.М.

Приближённый алгоритм для решения одной
задачи поиска подмножества векторов // Дискретный анализ и исследование
операций. 2011.

7.

Пузынина С.А.

О периодичности совершенных раскрасок бесконечной
гексаго
нальной и треугольной решеток
//

Сиб. мат. ж
урнал

8.

Горкунов Е.В.

Группа автоморфизмов q
-
ичного кода Хэмминга //

Дискретн. анализ
и исслед. опер
аций
.

9.

P. Sole and
Natalia Tokareva

Connections between quaternary and Boolean bent functions
// Designs, codes a
nd Cryptography, 2010.

10.

Токарева Н.Н. Группа автоморфизмов множества бент
-
функций // Дискретная
математика, 2010.

11.

J. Karhum¨aki, S. Puzynina Turt graphics and ocay catnativ squncs // Thortica
Informatics and Applications.

12.

S. Avgustinovich, J.

Karhum¨aki, S. Puzynina On abian vrsions of Critica factorization
theorem // Theoretical Informatics and Applications.

13.

С.В.Августинович, М.А.Лисицына Совершенные 2
-
раскраски транзитивных
кубических графов // Дискретн. анализ и исслед. опер.

14.

N. Tokarev
a On the number of bent functions from iterative constructions: bounds and
hypotheses // Advances in Mathematics of Communications, 2010.

15.

N. Tokareva Duality between bent functions and affine functions // Discrete Mathematics,
2010.














61


Приложен
ие
Б
.


Список сделанных
исполнителями
докладов


На всероссийских конференциях и семинарах:

1.

Береснев

В.Л., Гончаров

Е.Н.. Алгоритм локального спуска по расширенной
окрестн
о
сти для задачи размещения предприятий // Российская конференция
Дискретная оптимиза
ция и исследование операций»
,
А
л
тай, 27 июня


3 июля 2010

(секционный).

2.

Береснев

В.Л., Мельников

А.А. Алгоритмы локального поиска по обобщенной
окр
е
стности для задачи конкурентного размещ
е
ния предприятий

// Российская
конференция Дискретная оптимизация
и исследование операций»
,
А
л
тай, 27 июня


3 июля 2010

(секционный).

3.

Алексеева Е.В., Кочетова Н.А. Модифицированный точный метод для задачи о
(
r
|
p
)
-
центроиде
,
секционный доклад

// Российская конференция Дискретная оптимизация
и исследование операций»
,
А
л
т
ай, 27 июня


3 июля 2010

(секционный).

4.

Алдын
-
оол Т.А., Ерзин А.И., Залюбовский В.В. Покрытие плоской области случайно
распределенными сенсорами //

Росс. конф. Дискретная оптимизация и исследование
операций»
27

июня



03

июля

2010 г., Республика Алтай (се
кционный)

5.

Астраков С.Н., Ерзин А.И. Покрытие ограниченных плоских областей кругами //

Росс.
конф. Дискретная оптимизация и исследование операций»
27

июня



03

июля

2010
г., Республика Алтай (секционный)

6.

Ерзин А.И., Плотников Р.В. Максимизация времени жизн
и сенсорной сети в случае
заданного множества покрытий //

Росс. конф. Дискретная оптимизация и
исследование операций»
27

июня



03

июля

2010 г., Республика Алтай (секционный)

7.

Ерзин

А
.
И
.,
Шамардин

Ю
.
В
.
Одна

задача

синтеза

оптимального

остовного

дерева

//
М
ежд
.
кон
.

Интеллектуализация

обработки

информации
»,
Кипр
,
Пафос
, 17
-
24
октября

2010
г
. (
секционный
)
.

8.

А.Е.Бабурин,

Э.Х
.
Гимади
.

Об асимптотической точности эффективного алгоритма
решения задачи
m
-
PSP

на максимум в многомерном евклидовом пространстве

//

Рос
сийская конференция Дискретная оптимизация и исследование операций»: Изд
-
во Ин
-
та математики, 2010.
С. 151
-
151
(
секционный
)
.

9.

Гимади Э.Х
., Дементьев В.Т. Децентрализованная обобщенная задача о назначениях
//

Российская конференция Дискретная оптимизация и

исследование операций»: Изд
-
во Ин
-
та математики, 2010.
С
. 101
-
101
(
секционный
)
.


62

10.

Гимади Э.Х., Курочкин А.А. Полиномиальные алгоритмы для некоторых классов
задачи размещения
//

Российская конференция Дискретная оптимизация и
исследование операций»: Изд
-
во Ин
-
та математики, 2010.
С. 158
-
158
(
секционный
)
.

11.

Гимади Э.Х
., Рыков И.А. Приближенный рандомизированный алгоритм отыскания
подмножества векторов с максимальной нормой суммы в многомерном евклидовом
пространстве
//

Российская конференция Дискретная оптимизац
ия и исследование
операций»: Изд
-
во Ин
-
та математики, 2010.
С. 102
-
102
(
секционный
)
.

12.

Долгушев А.В., Кельманов А.В. К вопросу о сложности задачи MSSC // Материалы
Российской конференции Дискретная оптимизация и исследование операций»,
DOOR
-
2010, Алтай, 27 и
юня
-

3 июля 2010

(
секц
ионный)
.

13.

Кельманов А.В. О сложности некоторых задачах анализа данных и распознавания
образов // Российск
ая

конференци
я

Дискретная оптимизация и исследование
операций», DOOR
-
2010, Алтай, 27 июня
-

3 июля 2010

г. (
секц
ионный)
.

14.

Кельм
анов А.В., Михайлова Л.В., Хамидуллин С.А. Об одной задаче поиска и
идентификации наборов фрагментов в числовой последовательности // Российск
ая

конференци
я

Дискретная оптимизация и исследование операций», DOOR
-
2010,
Алтай, 27 июня
-

3 июля 2010

г. (
секц
и
онный)
.

15.

Кельманов А.В., Пяткин А.В. NP
-
полнота некоторых задач поиска подмножества
векторов // Российск
ая

конференци
я

Дискретная оптимизация и исследование
операций», DOOR
-
2010, Алтай, 27 июня
-

3 июля 2010

г. (
секц
ионный)
.

16.

Севастьянов С
.
В
.,
Б
.
М
.
Т
.
Лин
,

Хуанг

Ш
.
Л
.
Задача

с

оборотными

ресурсами
:
анализ

сложности

и

алгоритмы
//

Российская

конференция


Дискретная

оптимизация

и

исследование

операций
” (
DOOR
-
2010),
Республика

Алтай
, 27
июня


3

июля

2010

(
секц
ионный)
.


17.


Козлов

А.С. К гипотезе существования дл
я задачи на
m

параллельных машинах
оптимального расписания с не более чем
m
-
1
миграцией
//

Российская

конференция


Дискретная

оптимизация

и

исследование

операций
” (
DOOR
-
2010),
Материалы

конференции. Республика

Алтай
, 27
июня

3

июля 2010 (
секц
ионный)
.


Н
а
международных конференциях и семинарах
:

1.

Береснев

В.Л. Алгоритм локального поиска для задачи конкурентного

размещения пре
д
приятий

//

8 Международн
ая

конференция Интеллектуализация
обработки информации», 17


24 октября, 2010, г. Пафос, Кипр

(секционный).


63

2.


Beresnev

V..
Approximation Algorithm for the Co
m
petitive Facility Location Problems //
24
-
th European Conference on Operational Research, Lisbon, Portugal, 2010
(
секционный
).

3.

-
centroid problem /
/ 24
-
th
Europan Confrnc on Oprationa Rsarch, Lisbon, Portuga, 2010 (секционный).

4.

V.
Zalyubovskiy
, T. Aldyn
-
ool, A. Erzin, H. Choo
.
Energy
-
Efficient Coverage
-
Guaranteed
Node Scheduling Models in Sensor Networks with Random Deployed Sensors // The 2
nd
International Conference on Internet (ICONI) 2010, 16
-
20 Dec. 2010,
Philippines

(
секционный
).

5.

Edward

GIMADI
,
Aleksei

GLEBOV
,
Anastasia

GORDEEVA
,
Eugenia

IVONINA
,
and

Dolgor

ZAMBALAEVA
.
Some

polynomial

algorithms

with performance guarantees for
the 2
-
PS
P in complete graph

// Abstracts of Intrnationa Confrnc “Oprations Rsarch
2010”, 1

3 Sept. 2010, Munich, Germany. P.121


(
секц
ионный)
.


6.

Alexander KUROCHKIN.
Effective algorithm for the two
-
stage FLP on the tree network

//
Abstracts of International

Confrnc “
ALGORITHMS


(ODSA 2010)
, 13

15 Sept. 2010. Rostock
,
Germany
.


P. 29
-
29

(
секц
ионный)
.

7.

Edward GIMADI
.

Approximation algorithms with performance guarantees for some

discrete routing problems

// Abstracts of Interna
tiona Confrnc “
STRUCTURES AND ALGORITHMS


(ODSA 2010)
, 13

15 Sept. 2010. Rostock
,
Germany
.


P
.

8
-
8

(
секц
ионный)
.

8.

Гимади Э.Х. Алгоритмы с оценками качества решения некоторых задач выбора
подмножества векторов в евклидовом пространстве /
/

Международная конференция
Интеллектуализация обработки информации» (ИОИ
-
8), Кипр, г. Лимассол, 10

16
октября 2010 г., С. 240
-
243

(
секц
ионный)
.

9.

Долгушев

А
.
В
.,
Кельманов

А
.
В
.
О

сложности

одной

задачи

кластерного

анализа

//
Интеллектуализация обработки и
нформации: 8
-
я

международная

конференция
.
Республика

Кипр
,
г
.
Пафос
, 17

24
октября

2010
г
.

(
секц
ионный).

10.

Кельманов

А
.
В
.,
Пяткин

А
.
В
. NP
-
полнота

некоторых

задач

выбора

подмножества

векторов

// Интеллектуализация обработки информации: 8
-
я

международная

кон
ференция
.
Республика

Кипр
,
г
.
Пафос
, 17

24
октября

2010
г
. (
секц
ионный).

11.

Кельманов

А
.
В
.,
Михайлова

Л
.
В
.,
Хамидуллин

С
.
А
.
Об

одной

задаче

обнаружения

и

идентификации

векторных

наборов

в

последовательности

/// Интеллектуализация
обработки информации: 8
-
я

м
еждународная

конференция
.
Республика

Кипр
,
г
.
Пафос
,
17

24
октября

2010
г
. (
секц
ионный).


64

12.

Кельманов

А
.

В
. NP
-
полнота

некоторых

задач

анализа

данных

// Интеллектуализация
обработки информации: 8
-
я

международная

конференция
.
Республика

Кипр
,
г
.
Пафос
,
17

24
о
ктября

2010
г
.
(пленарный).

13.

S. Avgustinovich, J. Karhum¨aki, S. Puzynina On abian vrsions of Critica factorization
theorem.International, selected contribution, Mons Theoretical Computer Scienc
e Days,
September, 2010, France

(
пленарный
).

14.

Gorkunov E.V.

Symmetries of a q
-
ary Hamming code
.

Workshop on Algebraic and
Combinatorial Coding Theory
,
Novosibirsk, Russia
,

Sept.5

11
, 2010 (
секционный
)
.

15.


Avgustinovich S.V., Gorkunov E.V. On redundancy of strong isometries of binary codes
.

IEEE Int. Conf. on Compu
tational Technologies in Electrical and Electronics Engineering
,

Irkutsk, Russia.
July11
-
15, 2010,
(
секционный
)
.

16.

Heden O., Solov'eva F.I., Mogilnykh I.Yu. Intersections of perfect binary codes

-

2010
International Conference on Computatuional Technologies
in Electrical and Electronics
Engineering (SIBIRCON
-
2010), Irkutsk, Russia, July 11
-
15, 2010

(
секционный
)
.

17.

Avgustinovich S.V., Mogilnykh I.Yu. On completely regular codes in Johnson

graphs J(2w+1,w) with covering radius 1
-


Twelfth International workshop
on Algebraic
Combinatorial Coding Theory (ACCT
-
2010), September 5
-
11, 2010, Akademgorodok,
Novosibirsk, Russia

(
секционный
)
.



















65

Приложение
В
.

Список представленных диссертаций




Ф.И.О.

Искомая
степень

Дата

П
редставле
-
ния

Шифр

спец
-
ти, сове
т

Тема

1

Могильных
Иван Юрьевич

к
.ф.
-
м.н.

16
.0
6
.20
1
0

01.01.09

Д 003.015.01

С
овершенные 2
-
раскраски
графов
Д
жонсона

2

Салимов Павел
Вадимович


к
.ф.
-
м.н.

2
2
.09.20
10

01.01.09

Д 003.015.01

Р
екуррентность и
равномерная рекуррентность
бесконечных слов

и их про
изведений

3

Горкунов
Евгений
Владимирович

к.ф.
-
м.н.

22
.0
9
.20
1
0

01.01.0
9

Д 003.015.03

Группы автоморфизмов
кодов Х
эмминга и их
компонент







Приложенные файлы

  • pdf 7773860
    Размер файла: 783 kB Загрузок: 0

Добавить комментарий