Некоторые задачи дискретного разбиения и дефрагментации и методы их решения

• Автор: Якубов, Амучи Загирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Махачкала
• Количество страниц: 101 с. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. РАЗБИЕНИЯ В ЗАДАЧАХ ДЕФРАГМЕНТАЦИИ

§1.1. Формулировка задачи

§ 1.2. Вычислительная сложность задачи ДМ-

§ 1.3. Подходы к решению задачи дефрагментации

Пк,т,п

§1.4. Дефрагментация матриц класса У{,т-.,т}

ГЛАВА 2. РАЗБИЕНИЕ МНОЖЕСТВ

§2.1. Перечисление" ближайших" разбиений

§2.2. Разбиение множества на т подмножеств с ограничениями

§2.3. Множества со структурированными элементами
§2.4. Поиски "нетрадиционных" алгоритмов разбиения
ГЛАВА 3. ДЕФРАГМЕНТАЦИЯ СТРОК ТАБЛИЦЫ РАСПИСАНИЯ
Г к 7 п
§3.1. Дефрагментация матриц класса pLVJ
-(Zp, f ]
§3.2. Дефрагментация матрицы класса 7}
Г к 7 ix
§3.3. Дефрагментация матрицы класса р' ’ ’

§3.4. Дефрагментация матриц класса т}
ГЛАВА 4. ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ
§4.1. Обзор задач, сводимых к задаче дефрагментации
§4.2. Минимизация "окон" преподавателей в учебном расписании
§4.3. Оптимальное размещение TSR - программ в UMB
ГЛАВА 5. АСПЕКТЫ ПРОГРАММИРОВАНИЯ БАЗОВЫХ
АЛГОРИТМОВ
§5.1. Потоковые методы. Максимальный и допустимый потоки
§5.2. Взаимодействие приложения с внешними программами
Литература

Введение
ВВЕДЕНИЕ
Актуальность проблемы. В предлагаемой работе рассматривается комплекс взаимосвязанных задач комбинаторного и теоретико-графового характера, важнейшими из которых являются: а) задачи дефрагментации матриц различных классов - непрерывного расположения ненулевых элементов в каждой строке матрицы с сохранением множеств элементов в каждой линии матрицы; б) задачи разбиения множеств со структурированным элементами; в) задача о дефрагментации 0-1 матрицы без1 ограничения допустимых операций только перестановками столбцов.
Трудность для исследования ряда приведенных в работе задач, возникающих в различных областях науки, носит объективный характер, является результатом труднорешаемости соответствующих математических моделей. В качестве модели, объединяющей в себе характерные черты этих задач, рассматривается задача дефрагментации матриц.
Первым толчком к рассмотрению задач дефрагментации матрицы явились работы Фалкерсона и Г росса, которые ввели понятие связности единиц для строк матрицы с элементами 0-1. Впервые был поставлен вопрос о существовании перестановки столбцов, позволяющей расположить все единицы в каждой строке рядом. Первый полиномиальный алгоритм решения этой задачи был предложен в [16]; классическим решением считается довольно громоздкий алгоритм Буса и Люкера [8] с линейной временной сложностью. Более простые алгоритмы были предложены в работах [26], [19].
Симметричная задача может быть рассмотрена о перестановке строк.
Заметим, что задача дефрагментации матрицы является частным случаем задачи нахождения подматрицы со свойством связности единиц [46], ИР-полнота которой доказана в [7]. На некоторые замечания (см. [20]) к приведенному в [7] доказательству было указано автору данной работы проф. Са-лий В.Н.
1 Принятого в литературных источниках

Введение
Задачи дефрагментации матриц находят применение в теории графов [13], вычислительной биологии [2], в файловой структуре ЭВМ [25], в проблеме минимизации простоев при маршрутизации [19], [62] и везде, где преследуется цель неразрывного расположения объектов со свойством связности в некотором подклассе наборов.
Специалистами НИИ ПМА КБНЦ РАН был указан нам ряд областей, где находят применение частные случаи сформулированной проблемы (соответствующие задачи приведены в [38] под названиями "Создание генома", "Информационная сеть", "Кристаллы", "Дублирование опытов").
Целый класс матриц, интуитивно относимых в разряд дефрагментируемых, оставался за рамками исследований из-за ограничения множества допустимых для дефрагментации операций лишь перестановками столбцов. В работах Магомедова А.М. [61, 63, 68] и Альрашайда А. [37, 38] вопрос вытеснения нулевых элементов на крайние позиции строк матрицы - начальные и/или концевые - рассматривался без ограничений на используемые в преобразованиях операции; единственным требованием являлось сохранение множества элементов в каждой линии.
Предложенные нами модификации потоковых методов и результаты, полученные для задач разбиения множеств, позволили рассмотреть задачу дефрагментации для классов матриц, содержащих до семи столбцов, количество строк при этом не ограничено. Для матриц с большим количеством столбцов возникает переборная задача, которая делает использование этих методов нерациональным; перенести часть результатов на матрицы с неограниченным числом столбцов удалось лишь для некоторых частных случаев.
Отметим множественные пересечения с классическими труднорешаемыми задачами - как основной для работы задачи дефрагментации матрицы, так и ряда задач сопровождения. Перечислим некоторые из этих труднорешаемых задач [46].

лава 2. Разбиение множеств. §2.3. Множества со структурированными элементами.
Следствие 2.3.3. Лемма остается верной и при замене в ней термина "равно" на "не превышает".
2.3.4. Задача "Разбиение множества 3-элементпых наборов " (РЗ).
Ситуация для 3-элементных наборов, аналогичная рассмотренной в Лемме 2.3.2, шачителыю сложнее: не всякое множество 3-элементных наборов, содержащая эовно по 6 экземпляров каждого из чисел, допускает разбиение на два подмноже-;тва наборов, каждое из которых содержит по 3 экземпляра каждого из чисел.
В [38] приведен весьма сложный контрпример, принадлежащий Магомедову А..М., с 40 3-элементными наборами. Сложность контрпримера вызвана условием Зесповторности экземпляров внутри одного набора (следствие условия беспо-вторности ненулевых элементов в строках матрицы). Если допускать повторение экземпляров числа внутри набора, построение контпримера не вызывает затруднений.
В самом деле, пусть А={аі, а2, а3, а4, а5, а6}, аі =1:2:2, а2—1:2:2, а2=1:3:3, з4=1:3:3, 05=1:1:2, ав=2:3:3. Положим вначале м?і и м?2 пустыми семействами наборов. Т.к. наборы а/ па2 вместе содержат (4)2, то а і и а2 не могут быть одновременно включены в одно т и м>2: пусть а і включили ъм>},а2 — в\>2. Аналогично вынуждены поступить также и элементами а3 и а4: поскольку вместе эти два элемента содержат (4)3, они не могут входить одновременно в одно из ч?1 и м>2: пусть, для определенности, а3 включили в и’/, а4- в \ь .
В результатем>і={1:2:2, 1:3:3 }, м>2 ={1:2:2, 1:3:3}.
Гак как теперь каждое из содержит (2)3, то элемент а6 , также содержащий (2)3, не может быть включен ни в одно из этих семейств. Что и требовалось доказать.