Условия существования непрерывных расписаний тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Магомедов, Абдулкарим Магомедович

• Магомедов, Абдулкарим Магомедович
• доктор физико-математических наук
• 2011

Оглавление диссертации доктор физико-математических наук Магомедов, Абдулкарим Магомедович

Введение

Глава 1. Построение и жёсткое уплотнение расписания

§ 1.1. Двухстадийное расслоение

1.1.1. Определение двухстадийного расслоения.

1.1.2. Выровненные разбиения.

1.1.3. Доказательство теоремы о двухстадийном расслоении

1.1.4. Вычислительные аспекты.

§ 1.2. КР-полнота задачи о непрерывном расписании

1.2.1. Примеры и применения.

1.2.2. МР-полнота задачи о непрерывном расписании

1.2.3. Полиномиальная сводимость трех задач.

1.2.4. №-полнота задачи уплотнения (ОД)-матрицы

1.2.5. Приложите к задаче передачи сообщений.

§ 1.3. Эвристический алгоритм уплотнения

1.3.1. Сдвиги по полупустым циклам. Гипотеза.

1.3.2. Жадный алгоритм решения задачи уплотнения

§ 1.4. Перечисление расписаний

1.4.1. Расписание с разделяемым доступом.

1.4.2. Построение двоичного дерева покрытий.

1.4.3. Завершение построения двоичного дерева.

1.4.4. Помечивание вершин, вывод рекуррентных формул

1.4.5. Организация вычислений.

Глава 2. Разбивающая реберная раскраска

§2.1. Непрерывная и разбивающая раскраски

2.1.1. Непрерывное расписание и разбивающая раскраска

2.1.2. Расписание длительности 4 для нагруженного семейства 2-предписаний.

2.1.3. Разбивающая раскраска (2р,р)-графа.

§ 2.2. Планарность и раскрашиваемость

2.2.1. Непланарность простого (6, 3)-графа.

2.2.2. Нераскрашиваемый простой (6,3)-граф.

§2.3. Применение динамического программирования

2.3.1. Примеры р-предписаний.

2.3.2. Сведения об ^-полноте.

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

глава 3. Нагруженные непрерывные расписания малой длительности

§3.1. Расписание длительности

3.1.1. Формулировка задачи составления учебного расписания

3.1.2. Отсутствие временных ограничений.

§ 3.2. Расписание длительности

3.2.1. Примеры уплотнимых и неуплотнимых расписаний

3.2.2. Теорема о дуэте.

3.2.3. Решение за полиномиальное время.

§3.3. Расписания длительности 5 без 1-предписаний

3.3.1. Построение сети

3.3.2. Теорема об условиях уплотнения.

Глава 4. Нагруженные непрерывные расписания для предписаний с взаимно-простыми длинами к, т — к или т

§4.1. Нагруженные расписания при к ^

4.1.1. Допустимый поток в сети Ni.

4.1.2. Уточнения и замечания. Случай к = 2, т ^ 0 (mod 2)

§4.2. Трудности уплотнения для предписаний длины А;, т — к или т

4.2.1. Каркас и пристройка расписания.

4.2.2. Разбиваемая пристройка.

4.2.3. Проблема выбора допустимого потока.

Глава 5. Методы факторизации и бездефектных потоков

§5.1. Нагруженные расписания для предписаний длины 2, m — 2, га

5.1.1. Комбинаторная форма теоремы Петерсена о факторизации

5.1.2. Модификация теоремы о факторизации графа . . . .•

§5.2. Условия уплотнения

5.2.1. Структура непрерывного расписания для предписаний длины 2,т-2иш.

5.2.2. Скелеты расписания и ассоциированного графа

§ 5.3. Бездефектный поток

5.3.1. Сеть с гомологичными парами дуг.

5.3.2. Теорема о бездефектном потоке.

5.3.3. Вычисление бездефектного потока.

Глава 6. Расписание для семейства 2-предписаний

§6.1. Разделяющая факторизация

6.1.1. Непрерывное расписание для нагруженного семейства

1- и 2-предписаний.

6.1.2. Факторизация, разделяющая два смежных ребра

6.1.3. Условия непрерывного размещения 1- и 2-предписаний

6.1.4. Факторизация, разделяющая две пары смежных рёбер

§ 6.2. Условия существования компромиссного разбиения для частично-4-регулярного графа

6.2.1. Пограничные условия.

6.2.2. Компромиссное разбиение для частично-4-регулярного графа.

6.2.3. Применение к построению расписания.

§6.3. Непрерывные расписания длительности 5 для 2-предписаний. Вопросы существования

6.3.1. Преобразования размещений с пресыщенными столбцами

6.3.2. Непрерывные расписания для 2-предписаиий.

§ 6.4. Непрерывные расписания нечетной длительности для 2-предписаний

6.4.1. Односторонние расписания.

6.4.2. Рёберная р-раскраска двудольного представления

6.4.3. Характеризация непрерывных расписаний

6.4.4. Проверка условий. Задача вычисления плотности графа

Введение диссертации (часть автореферата) на тему «Условия существования непрерывных расписаний»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Пусть множество N = {1,., п} требований (деталей, учебных групп, заданий и т.п.) обслуживается в системе Ь — {1,.,/} приборов (станков, преподавателей, процессоров и т. п.). Исходные данные к расписанию обслуживания: для каждого прибора ъ £ Ь задано "предписание" щ (неупорядоченный набор, мультимножество) с элементами из множества N, над каждым требованием из прибор г должен выполнить операцию единичной длительности; условия частичного предшествования отсутствуют, в любой момент времени каждое требование обслуживается не более чем одним прибором, и каждый прибор обслуживает не более одного требования. Обслуживание без простоев «активных» (приборов и др.) и «пассивных» компонентов (требований и др.) будем называть обслуживанием без «прерываний» и «задержек» соответственно.

Обозначим: П = {и>\,., щ }, гер^ — коэффициент (количество вхождений) элемента jEN в гер^ = гер^, т{£1) — тах(герп>7'). Всюду в дальнейшем предполагается, что наиболь-з шее число операций, предписанных отдельным приборам, не превышает наибольшее число операций, предписанных выполнить над отдельными требованиями (вертикальные скобки «| |» применены, как и в монографии [38], и для обозначения мощности, что не приводит к путанице со стандартным применением для обозначения абсолютной величины числа): шг\ ^ т(Г2), У г е Ц для такого семейства ^ расписание длительности т(Г2) существует всегда. Если герп 1 = • • • = герпп, то расписание (и семейство Q) будем называть нагрусисегтым. Процесс преобразования расписания к гшпрерывному расписанию, т.е. к расписанию без прерываний, будем называть уплотнением или жестким уплотнением] там, где это не вызывает разночтений, уплотнением удобно называть и само непрерывное расписание.

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

Задача о непрерывном расписании: существует ли для семейства предписаний непрерывное расписание длительности т(Г2) ?

Объектом изучения диссертации являются комбинаторные задачи и задачи теории расписаний, предметом изучения — условия существования и алгоритмы жесткого уплотнения расписания. Основным предметом изучения в диссертации являются различные задачи раскраски множества рёбер графов, ассоциированных с заданным семейством предписаний к расписанию. Это новый, введенный автором класс, включающий задачи различных типов рёберной раскраски.

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

Задачи жесткого уплотнения находят применение не только в задачах о расписаниях, но и в задачах сжатия информации (результаты Booth К. S., Lueker G. S., Fulkerson D.R., Gross O.A. о матрице со свойством связности) и в задачах оптимизации передачи сообщений по многоканальной сети.

Они тесно связаны также с направлением интервальной раскраски графов, первоначально введенным в работе А. С. Асратяна и Р. Р. Камаляна [1]. Наиболее важные результаты в данном направлении получили А. С. Асратян, Р. Р. Камалян, С. В. Севастьянов, В. Г. Визинг, В. А. Пяткин.

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

Задачи жесткого уплотнения выступают катализаторами достижений в области теории графов. Так, задача о непрерывном расписании длительности т(С1) для семейства О двухэлементных предписаний эквивалентна задаче о минимальном количестве цветов при жесткой инциденторной раскраске [27]. Её исследованрхе, в частности, инициировало новый подход (отличный, например, от принятого в [12]) к вычислению наибольшей плотности подграфа, что, в свою очередь, находит применение в изучении рейтинга сайтов и социальных сетей. Исследование жесткого уплотнения для предписаний мощности 2, т(П) — 2 или т(0,) привело к обобщению классического результата [21] о разбиении регулярного графа четной степени на 2-факторы, а также к выявлению полиномиально разрешимой подзадачи известной МР-полной задачи о потоке в сети с гомологичными дугами [37]. Из результата об ЫР-полноте задачи о непрерывном расписании вытекает КР-полнота одного из вариантов задачи об интервальной раскраске. Результаты по жесткому уплотнению тем самым помогают решить некоторые задачи теории графов.

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

Обзор результатов по теме диссертации и место результатов автора среди них. Семейство Г2 = {а^ | г е Ь} суть гиперграф с множеством вершин в каждом «ребре» которого вершина из N может присутствовать несколько раз. Для наглядности будем применять двудольное представление гиперграфа, для чего соотнесем семейству О, двудольный ассоциированный граф (7 = (X, У, Е): X = {х±,., хп}, У = {т/х,., ?//}, в котором количество ребер, соединяющих вершины хц € X и у1 е У, равно Отождествляя номер единицы времени обработки требования х^ прибором уг и номер цвета ребра получим задачу о рёберной раскраске графа С = (X, У, Е), эквивалентную задаче о расписании для семейства

Правильной рёберной раскраской графа цветами 1,2,3,. называется отображение /: Е(С£) —> {1,2,3,.}, такое, что /(ех) ф Ц^) для каждой пары смежных рёбер в\ и е^. Если для каждой вершины графа цвета инцидентных ребер образуют некоторый интервал, правильная рёберная раскраска графа цветами 1,2,3,. называется интервальной.

Ассоциированный с Г2 двудольный граф G с интервальной раскраской соответствует непрерывному расписанию для О, без задержек в обслуэ/си-вании каждого требования. Интервальная раскраска цветами из множества {1,2,.,£} называется интервальной ¿-раскраской, если каждый из цветов этого множества присвоен хотя бы одному ребру Через A(G) обозначается наибольшая степень вершины графа G. Ассоциированный с Ü, двудольный граф G с интервальной A (G)-раскраской соответствует непрерывному расписанию для длительности т(Г2) без задерэ/сек в осблуживании каждого требования.

А. С. Асратян и Р. Р. Камалян ([1], 1987) получили ряд результатов об интервальной раскраске графа, в частности, показали приложение задачи раскраски двудольного графа к устранению «окон» в школьном расписании. Предположительно, впервые на приложение задачи раскраски двудольного графа к устранению «окон» расписания указано в заметке А.М.Магомедова ([66], 1985).

Не всякий граф обладает интервальной раскраской; например, полный граф не является, очевидно, интервально раскрашиваемым. Двудольный граф G = (X, У, Е), в котором степени всех вершин из X равны а, а степени всех вершин из Y равны будем называть (а:, /?)-бирегулярным графом. Понятно, что (а, а)-бирегулярный граф G = (X, У, Е) обладает интервальной раскраской, поскольку множество рёбер Е допускает разбиение на а совершенных паросочетаний Е\,., Еа, поэтому для получения интервальной раскраски достаточно присвоить всем рёбрам каждого Ег цвет г. Нетривиальные примеры: интервальной раскраской обладают деревья и полные двудольные графы — результаты Н. М. Hansen ([13], 1992) и Р. Р. Камалян ([17], 1990), а также (2, /?)-бирегулярные графы: в случае четного ß — результат H.M.Hansen ([13], 1992), в случае нечетного ß — результат D.Hanson, С. О. M.Loten и В. Toft ([14], 1998) и, независимо, А. V. Kostochka ([19], 1995). Если выполнены дополнительные ограничения |o;i| — ••• = \üji\ = 2, то при четном m(Q) непрерывное расписание длительности т(0) существует всегда; при нечетном т(П) необходимые и достаточные условия существования такого расписания найдены Магоме-довым A.M. ([58],2010).

А. С. Асратян и Р. Р. Камалян ([2], 1994) доказали, что: 1) каждый ин-тервально раскрашиваемый граф G обладает правильной рёберной А((?)-раскраской; 2) задача о существовании интервальной раскраски регулярного графа является NP-полной. В работе Р. Р. Камаляна ([17], 1990) показано, что полный граф интервально t-раскрашиваем, если (и только если) а + Ъ - НОД(а, +

В статье ([16], 1995) T.Jensen и В. Toft сформулировали утверждение, что любой бирегулярный граф обладает интервальной раскраской. D. Hanson и С. О. М. Loten ([15], 1996) доказали, что для интервальной раскраски (а, Ъ)~ бирегулярного графа потребуется по меньшей мере а+6—НОД(а, Ъ) цветов. Так, для интервальной раскраски (3,4)-бирегулярного графа потребуется не менее 6 цветов; вопрос существования интервальной 6-раскраски для любого (3,4)-регулярного графа до сих пор остается открытым. Для (3,4)-бирегулярного графа G А. В.Пяткин ([22], 2004) доказал, что: 1) задача о существовании кубического подграфа, содержащего все вершины, степени которых в G равны 4, NP-полна; 2) если такой подграф существует, то граф G — интервалыю 6-раскрашиваем. Опираясь на первый из упомянутых результатов, А. С.Асратян и С. J. Casselgren доказали ([3], 2008) NP-полноту задачи о существовании интервальной 6-раскраски для (3, 6)-бирегулярного графа. В статье А. М. Магомедова ([85], 1991) обсуждается вопрос о роли кратных рёбер в качестве препятствий для интервальной 6-раскрашиваемости (3, 6)-бирегулярного графа и построен пример простого (без кратных рёбер) (3, 6)-бирегулярного графа, не допускающего интервальной 6-раскраски.

Ассоциированный с семейством Q двудольный граф G = (X, У, Е) будем называть (hi, ^ &2)-графом, а семейство — соответственно (ki, ^ &2)-семейством, если dGxj = ki Vxj е X; dGiji < к2 V^ G У. (0.1)

В статье А. М. Магомедова ([86], 1991) доказано, что задача о непрерывном расписании для (4, ^ 4)-семейства разрешима за полиномиальное время.

Отметим, что приведенное в [86] доказательство без существенных изменений переносится и на "близкое" утверждение о разрешимости задачи интервальной А(С)-раскраски двудольного графа G, A(G) = 4, за полиномиальное время. Это утверждение было сформулировано и доказано K.Giaro в ([11], 1997), где получен и существенно более сильный результат об NP-полноте соответствующей задачи при А(С) = 5. В заметке А. М. Магомедова ([66], 1985) рассмотрены необходимые условия раскраски для (5, ^ 5)-графа.

NP-полноту задачи об интервальной раскраске двудольного графа в общем случае доказал С.В.Севастьянов ([39], 1990). ChoY. и Sahni S. доказали ([6], 1981) NP-полноту задачи о непрерывном расписании при дополнительном условии: если начато обслуживание требования некоторым прибором, то до завершешш этого обслуживания (возможно, с задержками), другой прибор не может обслуживать данное требование. Доказательство NP-полноты задачи о непрерывном расписании в формулировке, несколько отличной от нашей, получили А. В. Струсевич и Е. Р. Ерошина ([40], 1989). Видоизменением рхдеи этих авторов А.М.Магомедов показал, что задача о непрерывном расписании является NP-полной даже при дополнительных ограничениях на мощности предписаний ([53], 2009).

Пусть расписание для семейства Q задана матрицей М размеров I х т с элементами из множества {0} U N: если Mi^ = j, то при j е N прибор г обслуживает требование j в момент времени к, при j = 0 прибор г в момент времени к не обслуживает никакого требования. Элементы мноэ/сества N всюду в дальнейшем будем называть буквенными элементами {или, коротко: буквами).

Пусть все буквенные элементы матрицы М заменены на единицы и требуется проверить, можно ли, с сохранением количеств нулей pi единиц в каждой линии (столбце или строке), преобразовать полученную матрицу к такому виду, где единицы в каждой строке располагаются рядом, в подряд идущих ячейках. Из результата Fulkerson D.R., Gross O.A. ([10], 1965) вытекает, что задача разрешима за полиномиальное время, если в таком преобразовании допускаются лишь операции перестановки столбцов. А.М.Магомедов показал (гл. 1), что при отсутствии ограничений на разрешённые операции задача становится NP-полной.

Если |cji| = • • • = \lüi\ = 2, то для каждого LJi = (¿i, ¿2) G О заменим в двудольном ассоциированном графе конструкцию из рёбер (ж^,^), (%i2,yi) и вершины yi одним новым ребром (х^, Х{2). Полученный граф G = (X, Е) назовем графом, ассоциированным с О; «половинки» нового ребра, инцидентные соответственно вершинам х^ и Х{2, называются сопряэ/сетсыми инциденторами (под инцидентором понимается упорядоченная пара, состоящая из вершины pi ргацидентного ей ребра). В докторской диссертацрш А. В. Пяткрша ([36], 2009) исследованы разнообразные аспекты задачи ин-циденторной раскраскр! — определения минимального числа цветов, в которые можно раскрасить все инциденторы графа с соблюдением заданных условий на цвета смежных (примыкающих к одной и той же вершрше) и сопряженных инцртденторов. Как показал А. В. Пяткин, модель инцидеитор-ной раскраски эффективна при исследованрш задачи передачи сообщенрШ в локальной сети связи [35]—[34] pi в задачах теории расписаний. В нашей ^термршологир! один из вопросов, поставленных в статье В. Г. Визинга ([27], 2005) формулируется как вопрос об NP-полноте задачи определения минимального количества цветов, позволяющих раскрасить инциденты неориентированного мультиграфа так, чтобы: а) все смежные инциденторы имели разные цвета; б) цвета любой пары сопряженных инциденторов различались точно на 1. Задача эквивалентна задаче о существовании непрерывного расписания длительности m(Q) для семейства Г2 из 2-предписаний.

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

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

• А. А. Сапоженко (идеи известной книги [28] по дискретной математике явились ключевыми для некоторых из рассмотренных в работе задач; кроме того, благодаря советам проф. А. А. Сапоженко исследованы несколько значимых для целостности работы задач),

• В. К. Леонтьев (работе «Дискретные экстремальные задачи 25» автор обязан первоначальными сведениями о проблеме NP-полноты),

• S. A. Even, A. Itai, A. Shamir (классическая задача о составлении учебного расписания аккумулирует ряд важных направлений исследования),

• S. Sahni (NP-полнота задачи построения оптимального расписания для трех приборов, когда требование, обслуживание которого начато некоторым прибором, не может обслуживаться другим прибором до завершения его обслуживания данным прибором),

• В. А. Струсевич и Е. Р. Ерошина (NP-полнота аналогичной задачи для не менее двух приборов в предположении, что в процессе обслуживания каждого требования не допускаются задержки),

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

• D.R.Fulkerson и O.A.Gross (задача о матрице со свойством связности),

• В. Г. Визинг (вклад данного исследователя в теорию графов общеизвестен; в частности, исследование задачи об инциденторной раскраске имеет важное приложение к задачам о непрерывных расписаниях),

• А. В. Пяткин (задачи об инциденторной раскраске, о кубическом подграфе в (4,3)-бирегулярном графе и др.),

• А. С. Асратян и Р. Р. Камалян (интервальная раскраска различных видов двудольных графов),

• А. С. Асратян и С. J. Casselgren (задача о 6-интервальной раскраске (6,3)-брфегулярного графа и др.),

• К. Giaro (сложность задач интервальной раскраски двудольного графа G с A(G) = 4 и 5),

• Н. М. Hansen, D. Hanson, С. О. М. Loten и В. Toft (утверждение об интервальной раскрашиваемости двудольного (2, /3)-бирегулярного графа).

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

Методика исследований. В работе используются как известные методы, так и новые методы, разработанные автором для решения некоторых задач. К числу известных относятся методы теории графов (паро-сочетания в двудольных графах; реберно-вершинные инцидентные паросо-четания; потоки в сетях; разновидности ребёрной раскраски: правильной, непрерывной, интервальной, инциденторной), комбинаторики (разбиения; эвристические методы; методы динамического программирования), теории сложности вычислений (метод полиномиальной сводимости). Новые методы pi подходы: метод построения непрерывного расписания длительности 4 (гл. 3), метод вычисления бездефектного потока и модификация метода 2-факторизации (гл. 5), а также новый подход к вычислению наибольшей плотности подграфа (гл. 6).

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

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

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

Основными результатами диссертации являются:

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

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

3. Доказательство КР-полноты задачи о непрерывном расписании и задачи уплотнения (0,1)-матрицы. Выяснение структуры уплотнения нагруженного расписания.

4. Условия и алгоритм уплотнения нагруженного расписания длительности 4.

5. Модификация теоремы о 2-факторизации регулярного графа.

6. Теорема о бездефектном потоке и процедура проверки его существования.

7. Условия и алгоритм уплотнения для семейства предписаний длины 2, т — 2 и т.

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

9. Доказательство разрешимости задачи о непрерывном расписании для семейства О, с 2-предписаниями за полиномиальное время.

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

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

Всесоюзная научная конференция по моделированию и оптимизации учебного процесса с использованием ЭВМ (Московский Энергетический Институт, 1985); Всесоюзный семинар "Системное моделирование производства, распределения и потребления" (Воронеж, 1986); Всероссийская научно-методическая конференция "Компьютерные технологии в высшем образованрга" (Санкт-Петербург, 1994); Международный симпозиум "Интеллектуальные системы" (МГТУ им. Баумана, Махачкала, 1994); Всероссийская научно-техническая конференция "Современные информационные технологии в управлении" (Махачкала, 2003); Международная конференция "Современные проблемы математики" (Махачкала, 2004); XIV международная конференция "Проблемы теоретической кибернетики" (Пенза, 2005); IX Международный семинар "Дискретная математика и её приложения", посвященный 75-летию со дня рождения академика О.Б.Лупанова (МГУ, 2007); V международная конференция по математическому моделированию, посвященная 75-летию академика В. Н. Монахова (Якутск, 2007); Всероссийская научно-практическая конфереренция с международным участием "Информационные технологии в профессиональной деятельности и научной работе" (Йошкар-Ола, 2008); XV международная конференция "Проблемы теоретической кибернетики" (Казань, 2008); X Белорусская математическая конференция (Минск, 2008); IV Всероссийская конференция "Проблемы оптимизации и экономические приложения" (Омск, 2009); VIII Международная научная конференция "Дискретные модели в теории управляющих систем" (МГУ, 2009); III Всероссийская научная конференция "Методы и средства обработки информации" (МГУ, 2009); Международная научная конференция "Дискретная математика, алгебра и их приложения" (Минск, 2009); International conference "Optimization and applications"(Petrovac, Montenegro, September 21-25, 2009); XVIII международная школа-семинар "Синтез и сложность управляющих систем" им. академика О. Б. Лупанова (Пенза, 2009); X международная школа-семинар "Дискретная математика и приложения" (МГУ, 2010); XXIII Международная научная конференция "Математические методы в технике и технологиях" (Саратов, 2010).

Диссертация прошла апробацию на следующих семинарах: на семинаре Отдела математики и информатики Дагестанского научного центра РАН 11.02.2010 (руководитель И. И. Шарапудинов); на семинаре Отдела математических проблем распознавания и методов комбинаторного анализа сектора математических методов распознавания и прогнозирования ВЦ РАН 20.04.2010 (руководитель В.К.Леонтьев); на заседаниях семинаров кафедры математической кибернетики факультета ВМиК МГУ 22.05.2009 и 23.04.2010 (руководитель А. А. Сапоженко), на межвузовском семинаре г. Махачкала 23.11.2010 (руководитель А. К. Рамазанов).

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

В журналах из списка ВАК опубликованы 12 статей, три компьютерные программы автора зарегистрированы в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (РОСПАТЕНТ). Две статьи приняты к печати редакциями журналов «Математические заметки» и «Известия Саратовского гос. ун-та».

Под руководством автора по теме диссертации защищены две кандидатские диссертации (А.Рашайда — в 2000 г., А.З.Якубов — в 2003 г.), одна представлена к защите (М. М. Сиражудинов). Несколько студенческих работ, выполненных под руководством автора, удостоены дипломов региональных, российских и международных конкурсов.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, содержащих в совокупности 19 параграфов, заключения и списка литературы (119 наименований). Полный объем диссертации — 183 страницы.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Магомедов, Абдулкарим Магомедович

Заключение

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

В исходных данных к составлению расписания учебных занятий, наряду с семейством предписаний, обычно оговаривается ряд дополнительных ограничений. Наиболее часто встречаются ограничения двух типов: на промежутки времени, разрешеннные тем или иным преподавателям, или на аудитории, разрешенные для тех или иных занятий. Если ограничения первого типа могут служить причиной NP-пoлнoты задачи [9], то, как показано в §1.1, ограничения второго типа не оказывают столь существенного влияния на статус сложности задачи.

За исключением § 1.4, всюду в работе предполагается условие неразделяемого доступа. Своеобразие рассмотренного в §1.4 «компьютерного» решения задачи перечисления расписаний заключается в том, что программным путем сгенерирована система рекуррентных формул для определения мощности семейства всех расписаний для случая, когда параметр т (длительность расписания) принимает «малые» значения, а диапазон значений параметра п (количество учебных групп) «значителен»; например, т ^ 10, п > 100.

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

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

По определению непрерывного расписания, наименьшее значение длительности расписания, при котором условие непрерывности может нарушиться, равно 3. Результат п. 6.4.1 о том, что (2,^ 3)-граф С = (X, У, Е) является графом непрерывного расписания тогда и только тогда, когда существует полное паросочетаиие множества X с множеством У (теорема 6.4.1), используется в доказательстве одного из наиболее важных результатов работы — об условиях существования непрерывных расписаний нечетной длительности для семейства 2-предписаний О, (теорема 6.4.3 в §6.4).

Возможности успешного (с точки зрения существования эффективных точных алгоритмов) уплотнения расписания для семейства Q исчерпываются уже при т(Г2) .= 4: в п. 3.2.2 доказано, что нагруженное расписание класса Р1^2Ъ 4} Д0ПУскает уплотнение тогда и только тогда, когда обладает дуэтом; при т(Г2) = 4 задача о непрерывном расписании допускает решение за полиномиальное время. В § 3.3 задача решена при m(Q) — 5 для класса нагруженных семейств вида Р^ъАьу Заметим, что результат Giaro К. [11] об NP-полноте задачи при m{ß) = 5 не вполне исчерпывает рассмотрение. В частности, представляет интерес следующая задача.

Задача: является ли задача о непрерывном расписании длительности 5, в которой количество букв в каждой строке принадлежит множеству Q — {2,3}, NP-полной ?

Заметим, что если Q = {2} или Q = {3}, то задача разрешима за полиномиальное время. Неизвестно и решение следующей задачи.

Задача: существует ли класс задач |Q| > ¿)ля которого задача о непрерывном расписании разрешима за полиномиальное время ?

Теорема 1.2.1 об NP-полноте задачи о непрерывном расписании получила в п. 1.2.2 следующее уточнение: задача остается NP-полной даже в случае, когда требуется, чтобы в каждой строке все равные буквы размещались рядом, а также в случае предписаний длины не более [у] (теорема 1.2.2).

Задача: найти наибольшее к, такое, что задача о непрерывном расписании для семейства О. = остается NP-полной при \ш{\ ^ m(Q)/k.

В связи с доказанной в п. 1.2.4 теоремой 1.2.5 об NP-полноте задачи «Уплотнение (ОД)-матрицы» сформулируем следующую задачу.

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

Суть одной из "точек ветвления" исследования проста (лемма 2.1.4): при р = q = 2 для нагруженного семейства р-предписаний fl со свойством т = m(Q) = pq всегда существует непрерывное расписание длительности т.

• Направление 1: для фиксированного q = 2 задача исследуется при р = 3,4,.

Теорема 2.1.3 утверждает, что для произвольного р > 2 можно указать нагруженное семейство ^-предписаний Q, ш(Г2) = 2р, для которого непрерывное расписание не существует. Подчеркнем, что даже случай р = 3 представляет серьезные трудности. Перечислим некоторые из них. Стремлением выяснить роль кратных рёбер среди причин, препятствующих построению непрерывного расписания, объясняется рассмотрение вопроса непланарности простого (6, 3)-графа (теорема 2.2.1) и внимание, уделенное в §2.2 построению простого пераскрашиваемого (6, 3)-графа с количеством вершин, равным 60.

Задача: найти простой иераскрашиваемый (6,3)-граф с наименьшим числом вершин.

Итог в поиске эффективного точного алгоритма подводит приведенный в п. 2.3.2 результат A. S.Asratyan и С. J. Casselgren [3]: задача об интервальной 6-раскраске (6,3)-графа NP-полна. Этим фактом инициирован разработанный в 2.3.2 метод динамического программирования; аналогичное объяснение имеет и выяснение в §4.2 роли разбиваемой пристройки.

• Направление 2: постоянная длина предписаний принимается равной 2 и рассматриваются нагруженные семейства Г2 с т(Г2) = 2р. Итог данного направления подводит комбинаторная форма теоремы Пе-терсена о факторизации (теорема 5.1.1).

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

• С одной стороны, результат, достигнутый для семейств 2-предписаний Г2 с m(Q) = 2р, доведен до общего случая семейств 2-предписаний в §6.4, где рассмотрен случай нечетного m(Q): найдены необходимые и достаточные условия существования непрерывного расписания (теорема 6.4.3); в п. 6.4.4 предложено решение задачи вычисления плотности графа и построен эффективный алгоритм проверки этих условий. В отличие от подхода, предложенного в [12], алгоритм предоставляет принципиальную возможность учитывать структуру графа при оценке сложности.

Задача: пусть М(у,е) - время, требуемое для нахождения пропускной способности минимального разреза в сети с v вершинами и е ребрами; существует ли алгоритм вычисления в графе G — (V,E), \V\ — n, \Е\ — т, подграфа наибольшей плотности за время, меньшее, чем 0(М(п, п + т) logn) ?

• С другой стороны, представляется естественным расширить класс семейств с четным т(Г2) путем включения семейств, содержащих, наряду с 2-предписаниями, и предписания длины т-2ит. Отметим, что для случая нечетного т задача для семейств с предписаниями аналогичного типа решена в п. 4.1.2, где найдены необходимые и достаточные условия.

В случае четного т потребовались новые теоретико-графовые результаты: в §5.1 получены обобщения теоремы Петерсена о 2-факторизации (теоремы 5.1.2 и 5.1.3), в §5.2 изучена структура непрерывного расписания для нашего случая и задача сведена к существованию скелета расписания (теорема 5.2.1), а в § 5.3 разработан метод бездефектного потока, применением которого удалось установить, что рассматриваемая подзадача известной ЫР-полной задачи о максимальном потоке в сети с гомологичными дугами допускает решение за полиномиальное время. На основе перечисленных результатов сформулированы необходимые и достаточные условия существования непрерывного расписания.

• Для обозначения третьего направления укажем на простое наблюдение: теорема Петерсена о 2-факторизации связного графа четной степени т допускает элементарное доказательство, если т = 2к, к € Z+\ к — 2, 3,В самом деле, построим эйлеров цикл и пометим его последовательные рёбра чередующимися метками 1 и 2 (существенно, что число рёбер чётно). Затем повторим действия для каждого из двух остовных подграфов степени 2к~г, образованных 1- и 2-рёбрами соответственно, и так до тех пор, пока не получим остовные подграфы степени 2.

Данный подход с простым подготовительным разбиением на две части с последующими переразбиваниями, дополненный методом постепенного приближения к некоторому нужному свойству, достигаемому в заключительной итерации, применяется и в других местах работы: так, леммы 1.1.1 и 6.4.2 являются подготовительными для лемм 1.1.4 и 6.4.3 соответственно, которые, в свою очередь, используются в доказательствах теорем 1.1.1 и 6.4.3.

В связи с теоремой Петерсена напомним сформулированную в § 1.3 задачу.

Задача: заданы четное т и нагруженное (I х т)-расписание для 2-предписаний; верно ли, что такое расписание всегда можно преобразовать к непрерывному расписанию путем выполнения сдвигов по полупустым циклам?

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

Список литературы диссертационного исследования доктор физико-математических наук Магомедов, Абдулкарим Магомедович, 2011 год

1. Асратян, А. С. Интервальные раскраски рёбер мультиграфа Текст. / А. С. Асратян, Р. Р. Камалян // Прикладная математика. - 1987. -Вып. 5. - Ереван: Изд-во Ереван, ун-та. - С. 25-34.

2. Asratian, A. S. Investigation on interval edge-colorings of graphs Text. / A. S. Asratian, R. R. Kamalian // J.Combin. Theory Ser. 1994. - В 62 P. 34-43.

3. Asratian, A. S. Some results on interval edge colorings of (a, (3)-biregular bipartite graphs Text. / A. S. Asratian, C. J. Casselgren [Text] // Department of Mathematics. 2007. - Linkoping University S-581 83 Linkoping, Sweden.

4. Booth, K. S. PQ tree algorithms Text. // Doctoral Thesis, Dept. of Electrical Engineering and Computer Science. 1975. - University of California, Berkley C. A.

5. Brooks, R. L. On colouring the nodes of a network Text. // Proc. Cambridge Phil. Soc. 1941. - Vol. 37. - P. 194-197.

6. Cho, Y. Preemptive scheduling of independent jobs with release and due times on open, flow and job shops Text. / Y. Cho, S. Sahni // Oper. Res.,- 1981. V. 29,- No. 3. - P. 511-512.

7. Chvatal, V. Text. // Private communication. 1976.

8. Edmonds, J. Theoretical improvements in algorithmic efficiency for network flow problems Text. / J. Edmonds, R. M. Karp // Journal of the ACM. 1972. - 19. - P. 248-264.

9. Even, S. On the complexity of timetable and integral multi-commodity flow problems Text. / S. Even, A. Itai, A. Shamir // SIAM J. on Сотр.- 1976. V. 5. - No. 4. - P. 691-703.

10. Fulkerson, D. R. Incedence matrices and interval graphs Text. / D.R. Fulkerson, 0. A. Gross // Pacific J. Math. 1965. - 15. - P. 835-855.

11. Giaro, K. The complexity of consecutive A-coloring of bipartite graphs: 4 is easy, 5 is hard Text. // Ars Combin. 1997. - 47. - P. 287-298.

12. Goldberg, A. V. Finding a maximum density subgraph Text. // Technical Report Identifier: CSD-84-171.

13. Hansen, H. M. Scheduling with minimum waiting periods (in Danish) Text. // Master's Thesis, Odense University. 1992. - Odense, Denmark.

14. Hanson, D. On interval colourings of bi-regular bipartite graphs Text. / D. Hanson, C.O.M. Loten, B. Toft // Ars Combin. 1998. - 50. -P 23-32.

15. Hanson, D. A lower bound for interval colouring bi-regular bipartite graphs Text. / D. Hanson, C.O.M. Loten // Bull. Inst. Combin. Appl. 1996. - 18. - P 69-74.

16. Jensen, T. Graph coloring problems Text. / T. Jensen, B. Toft // Wiley-Interscience. 1995. - John Wiley & Sons, Inc., New York.

17. Kamalian, R. R. Interval edge-colorings of graphs Text. // Doctoral Thesis, Novosibirsk. 1990.

18. Karp, R. M. Reducibility among combinatorial problems Text. / R. M. Karp in R. E. Miller and J.W. Thatcher (eds.) // Complexity of Computer Computations. 1972. - Plenum Press, New York. - P. 85103.

19. Kostochka, A. V. Unpublished manuscript Text. 1995.

20. Malhotra, V. M. An 0(\V|3) algorithm for maximum flows in networks Text. / V.M. Malhotra, M. Pramodh Kumar, S.N. Maheshwari // Inform. Process. Lett. 1978. - 7. - P. 277-278.

21. Petersen, J. Die theorie der regulären graphen Text. // Acta Math. -1891. 15. - P. 193-220.

22. Pyatkin, A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs Text. // J. of Graph Theory. 2004. -Vol. 47. - No. 2. - P. 122-128.

23. Reinhard, D. Graph Theory Text. // Fourth Edition. 2010. - SpringerVerlag, New York. - 451 p.

24. Stockmeyer, L.J. Planar 3-colorability is NP-complete Text. // SIGACT News. 1973. - Vol. 5. - No. 3. - P. 19-25.

25. Ullman, J.D. Complexity of sequencing problems Text. / J. D. Ullman in G. F. Goffman (ed) // Computer and Job Shop Theory. 1976. - New York: John Wiley. - P. 139-164.

26. Берж, К. Теория графов и ее применения Текст. М.: Наука, 1962.- 320 с.

27. Визинг, В. Г. Жёсткая раскраска инциденторов в неориентированных мультиграфах Текст. // Дискрет, анализ и исслед. операций. Сер. 1. 2005. - Т. 12. - N 3. - С. 48-53.

28. Гаврилов, Г. П. Задачи и упражнения по дискретной математике: Учеб. пособие. 3-е изд., перераб. Текст. / Г. П. Гаврилов, A.A. Са-поженко. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

29. Грэхем, Р. Конкретная математика. Основание информатики: Пер. с англ. Текст. / Р. Грэхем, Д. Кнут, О. Паташник. М.: Мир, 1998.- 703 с.

30. Гэрри, М. Вычислительные машины и труднорешаемые задачи. Текст. / М. Гэрри, Д. Джонсон. М.: Мир, 1982. - 416 с.

31. Найк, Д. Стандарты и протоколы Интернета Текст. М.: Издательский отдел «Русская редакция»ТОО «Channel Trading Ltd.», 1999. -384 с.

32. Новиков, Ф. А. Дискретная математика для программистов Текст.- СПб.: Питер, 2001. 304,

33. Ope, О. Теория графов Текст. М.: Наука. Гл. ред. физ.-мат. лит., 1980. - 336,

34. Плеханова, Н. С. Передача сообщений в локальной сети с двумя центральными ЭВМ Текст. / Н. С. Плеханова, A.B. Пяткин // Дискрет. анализ и исслед. операций. Сер. 1. 2002. - Т. 9. - N 2. - С. 91-99.

35. Пяткин, А. В. Некоторые задачи оптимизации расписания передачи сообщений в локальной сети связи Текст. // Дискрет, анализ и исслед. операций. 1995. - Т. 2. - N 4. - С. 74-79.

36. Пяткин, А. В. Раскраска инциденторов и другие задачи на графах: алгоритмический аспект Текст. / Докторская диссертация. 2009.

37. Sahni, S. Computationally related problems Text. // SIAM J. Comput.,- 1974. No 3. - P. 262-279.

38. Свами, M. Графы, сети и алгоритмы Текст. / М. Свами, К. Тхула-сираман. М.: Мир, 1984. - 455 с.

39. Севастьянов, C.B. Об интервальной раскрашиваемости рёбер двудольного графа Текст. // Методы дискретного анализа. 1990. -Т. 50. - С. 61-72.

40. Танаев, В. С. Теория расписаний. Многостадийные системы Текст. / B.C. Танаев, Ю.Н. Сотсков, В. А. Струсевич. М.: Наука, 1989. -328 с.

41. Форд, JI.P. Потоки в сетях Текст. / JI. Р. Форд, Д. Р. Фалкерсон. -М.: Мир, 1966. 276с.

42. Основные публикации автора по теме диссертации

43. Магомедов, А. М. Задания по программированию и алгоритмы Текст. Махачкала: Изд.-во ДГУ, 1989. - 25 с.

44. Магомедов, А. М. Теория трудоемкости алгоритмов Текст. Махачкала, изд-во ДГУ, 1992. - 81 с.

45. Магомедов, А. М. Связное расписание Текст. Махачкала: Изд-во ДГУ, 1994. - 78 с.

46. Магомедов, А. М. Двумерная графика в проектах Delphi Текст. // Вестник Дагестанского научного центра РАН. 2004. - N 18. - С. 5-8.

47. Магомедов, А. М. Размещение неделимых 2-слов в матрице как задача факторизации графа Текст. // Вестник Дагестанского научного центра РАН. 2006. - N 23. - С. 5-14.

48. Магомедов, А. М. Жесткий директивный срок для многопроцессорного расписания без прерываний и отношений предшествования Текст. // Вестник Дагестанского научного центра РАН. 2007. - N 28. - С. 5-11.

49. Магомедов, А. М. К вопросу оптимизации расписания Текст. // Известия Волгоградского государственного технического университета: межвуз. сб. науч. ст. 2008. - Вып. 5. - N 8(46). - С. 40-43.

50. Магомедов, A.M. Уплотнение расписания с директивным сроком, кратным количеству занятий каждого преподавателя Текст. // Ма-тем. заметки. 2009. - Т. 85. - N 1. - С. 65-72.

51. Магомедов, А. М. О существовании компромиссного разбиения для частично-4-однородного графа Текст. // Матем.заметки (принята к печати на март 2011 г.).

52. Магомедов, А. М. К вопросу о рёберной раскраске двудольного графа Текст. // Дискретная математика. 2009. - Т. 21. - Вып. 2. -С. 153-159. -

53. Магомедов, А. М. Дефрагментация таблицы перестановок из четырех столбцов Текст. // Дискретная математика. 2009. - Т. 21. -Вып. 4. - С. 95-104.

54. Магомедов, А. М. Непрерывное расписание для специализированных процессоров без отношения предшествования Текст. // Вестнрж Московского Энергетического Института. 2009. - N 5. - С. 14-17.

55. Магомедов, А. М. Условия существования непрерывных расписаний длительности пять Текст. / А. М. Магомедов, А. А. Сапоженко // Вестник МГУ, сер. Вычислительная математика и кибернетика. -2010. Т. 34. - N 1. - С. 39-44.

56. Магомедов, А. М. Непрерывность расписаний для 3-элементных предписаний Текст. // Вопросы современной науки и практики. Университет им. В. И. Вернадского. 2010. N 10-12(31). - С. 82-89.

57. Магомедов, А. М. Расслоение множества рёбер двудольного графа Текст. // Научно-технические ведомости СПбГПУ. Раздел «Математика». 2010. - N 4(109). - С. 150-155.

58. Магомедов, А. М. Расписание с двухэлементными предписаниями Текст. // Известия Саратовского гос. университета. Новая серия. Серия Математика. Механика. Информатика. Принята к печати в 2011 г.1. Прочие публикации

59. Магомедов, А. М. Мультимедийное прочтение / А. М. Магомедов, Т. А. Магомедов, М.А. Магомедов // Программа для ЭВМ. Свидетельство N 2010611946 о гос. регистр, прог. для ЭВМ от 15.03.2010.

60. Магомедов, А. М. Распознавание строчных букв кириллицы / А. М. Магомедов, Т. А. Магомедов, М. А. Магомедов // Программа для ЭВМ. Свидетельство N 2010612224 о гос. регистр, прог. для ЭВМ от 02.03.2010.

61. Магомедов, А. М. Компьютерная карта РД. Программа для ЭВМ / А. М. Магомедов, Т. А. Магомедов, Т. И. Шарапудинов // Свидетельство N 2010612223 о гос. регистр, прог. для ЭВМ от 24.03.2010.

62. Магомедов, А. М. Сдвиг по полупустому циклу для уплотнения графика работы нескольких исполнителей Текст. // Деп. в ВИНИТИ N 7225-84.

63. Магомедов, А. М. Распределение элементов в фрагменте таблицы Кэли Текст. // Деп. в ВИНИТИ N 7222-84. 8 с.

64. Магомедов, А. М. К вопросу минимизации разделяющих нулей в строках матрицы Текст. / А. М. Магомедов // Деп. в ВИНИТИ N 7224-84. 8 с.

65. Магомедов, А. М. Раскраска графа с непрерывным спектром Текст. // Деп. в ВИНИТИ N 478-85.

66. Магомедов, А. М. Аналог теоремы Холла Текст. // Деп. в ВИНИТИ N 447-85. 7 с.

67. Магомедов, А. М. Теорема о п.н.п. с ограничениями Текст. // Деп. в ВИНИТИ N 7155В-85. 7 с.

68. Магомедов, А. М. Уплотнение булевой матрицы Текст. // Деп. в ВИНИТИ N 6530-85. 7 с.

69. Магомедов, А. М. Построение паросочетаний Текст. // Деп. в ВИНИТИ N 8409В-85. -8 с.

70. Магомедов, А. М. Составление школьного расписания на ЭВМ Текст. // Деп. в ЦНТИ Педагогика N 221-85. 18 с.

71. Магомедов, А. М. Составление школьного расписания на ЭВМ Текст. // В кн.: Материалы Всесоюзной научной конференции по моделированию и оптимизации учебного процесса с использованием ЭВМ. 1985. - Москва.: Изд-во МЭИ. - 4с.

72. Магомедов, А. М. Минимизация простоев Текст. // Тезисы Всесоюзного семинара «Системное моделирование производства, распределения и потребления». Часть 2. 1986. - Воронеж. - (2с).

73. Магомедов, А. М. Выделение двух множеств непересекающихся двудольных паросочетаний Текст. // Деп. в ВИНИТИ N 7332-86. -9 с.

74. Магомедов, А. М. К вопросу о существовании непересекающихся паросочетаний Текст. // Деп. в ВИНИТИ N 7957-86. 4 с.

75. Магомедов, А. М. Выделение групп двудольных паросочетаний с ограничениями Текст. // Деп. в ВИНИТИ N 8069-В-86 Зс.

76. Магомедов, А. М. Условия существования паросочетаний Текст. // в сб. «Функ. анализ, теория функций и их приложения». 1987. -Махачкала: Изд-во ДГУ. - 4 с.

77. Магомедов, А. М. Уплотнение матрицы перестановок из шести столбцов Текст. // Деп. в ВИНИТИ N 8700-В87. 8 с.

78. Магомедов, А. М. Тривиальное учебное расписание Текст. // Деп. в ЦНТИ Педагогика. 1989. - 9 с.

79. Магомедов, А. М. Программирование на языке ассемблера (уч. пособие, 57 с.) Текст. // 1989. Махачкала: Изд-во ДГУ.

80. Магомедов, А. М. Нахождение кратчайших периодических путей в графе Текст. // Деп. в ВИНИТИ 10.11.89 6759-1989. 8 с.

81. Магомедов, А. М. Об одном доказательстве КР-полноты задачи о 3-раскрашиваемости графа Текст. / А. М. Магомедов, Ш. М. Алиев // Деп. в ВИНИТИ 10.11.89 6760-1989.

82. Магомедов, А. М. Сильная ЫР-полнота задачи о матрице со свойствами псевдосвязности Текст. // Деп. в ВИНИТИ 6761-138910.11.89. -6с.

83. Магомедов, А. М. Псевдополиномиальный алгоритм решения задачи уплотнения матрицы для одного частного случая Текст. / А. М. Магомедов // Деп. в ВИНИТИ 6762-1989 (5с).

84. Магомедов, А. М. К вопросу об условиях уплотнения матрицы из 6 столбцов Текст. // Деп. в ВИНИТИ, 1991. 6 с.

85. Магомедов, А. М. Условия и алгоритм уплотнения матрицы из 4 столбцов Текст. // Деп. в ВИНИТИ 175-В92, 1992. 7 с.

86. Магомедов, А. М. О составлении факультетского учебного расписания Текст. // Сб. трудов ДГУ. Махачкала. - 2 с.

87. Магомедов, А. М. Вопросы уплотнения факультетского учебного расписания Текст. // Сб. трудов ДГУ. Махачкала. - 1 с.

88. Магомедов, А. М. Семейство двудольных паросочетаний с ограничениями Текст. // В сб. «Функ. анализ, теория функций и их приложения». 1993. - Махачкала. - 4 с.

89. Магомедов, А. М. Электронный справочник «Алгоритмы и программы» Текст. // Тезисы Всероссийской научно-методической конференции «Компьютерные технологии в высшем образовании». 1418.03.94. - Санкт-Петербург. - С. Е56.

90. Магомедов, А. М. К вопросу о расписании мультипроцессорной системы Текст. // Труды междунар. симпозиума «Интеллектуальные системы». МГТУ им. Баумана. 1994. - Махачкала. - 5 с.

91. Магомедов, А. М. К вопросу об оптимальном размещении ТЭЯ-программ Текст. // Вестник ДГУ. 1997. - 5 с.

92. Магомедов, А. М. Условия связываемости матрицы Текст. / А. М. Магомедов, А. Рашайда // Вестник ДГУ. 1998. - 2 с.

93. Магомедов, А. М. Матрица расписания с двумя ненулевыми элементами в строке Текст. // Вестник ДГУ. 1999. - Вып. 4 - 4с.

94. Магомедов, А. М. Согласование таблицы Текст. / А. М. Магомедов, А. Рашайда // Вестник ДГУ. 2002. - 7 с.

95. Магомедов, А. М. Построчная оптимизация разреженной матрицы Текст. // Вестник ДГУ. 2002. - 1с.

96. Магомедов, А. М. КР-полные проблемы интерфейса 1ЕЕЕ-1394 Текст. // Тезисы Всероссийской научно-технической конференции «Современные информационные технологии в управлении», ДГТУ. -2003. Махачкала, ДГТУ. - 4 с.

97. Магомедов, А. М. Равнодефицитное разбиение списка по элементу Текст. // Вестник ДГУ. 2004. - Зс.

98. Магомедов, А. М. К вопросу о маршрутизации Текст. // Материалы международной конференции «Современные проблемы математики». 2004. - Махачкала. - С. 47.

99. Магомедов, А. М. Дефрагментация разреженных матриц как задача разбиения графа на остовные подграфы специального типа Текст. //В кн.: Материалы международной конференции «Современные проблемы математики». 2004. - Махачкала. - С. 48-54.

100. Магомедов, А. М. Неразрывное размещение наборов в строках матрицы без повтора элементов в столбцах Текст. // Вестник ДГУ. -2005. 6 с.

101. Магомедов, А. М. Дефрагментация матриц с 2q и Зq ненулевыми элементами в строке Текст. // Региональная науч.-практ. конференция «Компьютерные технологии в науке, экономике и образовании», 17-19 ноября 2005. 2005. - 4с.

102. Магомедов, А. М. Условия уплотнения расписания Текст. // V международная конференция по математическому моделированию, посвященная 75-летию академика В.Н.Монахова: Тез.докл. Под редакцией И.Е.Егорова. 2007. - Якутск: изд-во ООО «РИЦ Офсет». -С. 65.

103. Магомедов, А. М. О модификации характеризации Бержа Текст. // Проблемы теоретической кибернетики. Тезисы докладов XV международной конференции (Казань, 2-7 июня 2008г). Под редакцией Ю.И.Журавлева. 2008. - Казань: Отечество. - С. 77.

104. Магомедов, A.M. Условия существования расписаний малой длительности Текст. // Материалы IV Всероссийской конференции «Проблемы оптимизации и экономические приложения», Омский гос. ун-т, 29 июня 4 июля 2009 г. - 2009. - С. 148.

105. Магомедов, A.M. Разбиение семейства мультимножеств Текст. // Дискретная математика, алгебра и их приложения: Тез. докл. Между-нар. науч. конф. Минск, 19-22 октября 2009 г. 2009. - Мн.: Институт математики HAH Беларуси. - С. 101-102.

106. Магомедов, А. М. Два частичных паросочетания в двудольном графе специального вида Текст. // Межд. школа-семинар «Дискретная математика и приложения», МГУ. - 1-6 февраля 2010.