Некоторые задачи дискретного разбиения и дефрагментации и методы их решения тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

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

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

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

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

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

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

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

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

§2.3. Множества со структурированными элементами.

§2.4. Поиски "нетрадиционных" алгоритмов разбиения.

ГЛАВА 3. ДЕФРАГМЕНТАЦИЯ СТРОК ТАБЛИЦЫ РАСПИСАНИЯ

Г к 7 п

§3.1. Дефрагментация матриц класса р ' !' '. а 7 пл

§3.2. Дефрагментация матрицы класса p^s 67} .^

§3.3. Дефрагментация матрицы класса

§3.4. Дефрагментация матриц класса С-2 т}.

ГЛАВА 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] под названиями "Создание генома", "Информационная сеть", "Кристаллы", "Дублирование опытов").

Целый класс матриц, интуитивно относимых в разряд дефрагменти-руемых, оставался за рамками исследований из-за ограничения множества допустимых для дефрагментации операций лишь перестановками столбцов. В работах Магомедова A.M. [61, 63, 68] и Альрашайда А. [37, 38] вопрос вытеснения нулевых элементов на крайние позиции строк матрицы - начальные и/или концевые - рассматривался без ограничений на используемые в преобразованиях операции; единственным требованием являлось сохранение множества элементов в каждой линии.

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

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

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

Дополнение до матрицы со свойством связности" - исследуется преобразование (0-1)- матрицы к матрице, обладающей свойством связности единиц, путем замены не более К ненулевых элементов.

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

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

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

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

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

Введенные в § 1.1 обозначения и определения имеют для работы сквозной характер. Основная проблема - исследование условий дефрагментации строк матрицы М, содержащей в каждом столбце, кроме нулей, некоторую перестановку чисел 1, 2, .п, с сохранением множества элементов в каждой линии - сформулирована в виде задачи распознавания. В §1.2 рассмотрена матрица Sign (М), разрешимость которой является необходимым условием дефрагментации матрицы М. В процессе доказательства полиномиальной сводимости известной ./VP-полной задачи "Разбиение" к задаче дефрагментации матрицы Sign (М) получена простая схема структуры дефрагментирован-ной матрицы, что для дальнейших исследований оказалось существенно более благотворным, чем сознательно поставленная цель установить NP-полноту задачи дефрагментации 0-1 матрицы. Рассмотрение в §1.3 дефрагментации простого класса матриц послужило введением в методику использования потоковых методов в задачах дефрагментации, незагроможденность многочисленными деталями дальнейших рассмотрений способствовала также выявлению роли трансверсалей в проверке условий дефрагментации. Примененный в §1.3 теоретико-графовый инструментарий исследования получил некоторое развитие в § 1.4, где основу процесса преобразования матрицы составляет набор совершенных паросочетаний в двудольном графе, инициированный допустимым потоком в транспортной сети.

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

В §2.1 сформулирована и решена задача разбиения множества на два подмножества, ближайшие по суммам весов, рассмотрена задача перечисления разбиений. После изложения в §2.2 схемы решения задачи разбиения множества на п подмножеств мы решили опустить непринципиальный и громоздкий текст ее дополнения до множественного разбиения на ближайшие подмножества. Такого же подхода мы придерживались, например, и воздерживаясь от неизбежно пространного изложения процесса дефрагментации для случая, когда строка матрицы порядка кхт содержит 1 или т-1 ненулевых элементов, т.к. такое изложение не привносит принципиальных дополнений в алгоритм, приведенный в §3.2 для случая т=7. Базовым для последующего в Главе 3 исследования задач дефрагментации является §2.3, где приведен ряд утверждений комбинаторного и теоретико-графового характера о разрешимости задач разбиения множеств со структурированными элементами.

Намеченные в §2.4 варианты "нетрадиционных" подходов к разработке алгоритмов разбиения множеств со структурированными элементами нам показались перспективными, однако развить их до эффективного аппарата не удалось.

В третьей главе рассматриваются условия дефрагментации матриц класса р1к'7'п}. Необходимые и достаточные условия дефрагментации сформулированы в §3.1-§3.3 в терминах потоков в транспортных сетях.

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

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

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

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

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

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

Компьютерная поддержка работы в основном осуществлялась с использованием среды Дельфи. Для перекрестной проверки полученных результатов на заключительном этапе выполнения работы автор воспользовался пакетом DiscreteMath известной системы компьютерной математики Mathematica 4 [96] (например, функцией NetworkFlow - для вычисления максимального потока в сети, Contract, GridGraph - для построения графов) и пакетом networks системы Maple 6 [97] (функциями flow, draw - аналогичными вышеупомянутым, и др.).

Научные положения, выносимые на защиту:

- теоремы о необходимых и достаточных условиях дефрагментации матриц классов p\h2^7y-р\ЗА7\ > P^J^y Р\2,т-2,т} '

- полиномиальные алгоритмы дефрагментации.

- результаты о разбиении множеств со структурированными элементами;

- теорема об КР-полноте задачи дефрагментации;

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

Публикации и апробация работы. По теме диссертации опубликованы 9 работ. Основные результаты диссертации докладывались на годичных итоговых конференциях Дагестанского госуниверситета (1996г. - 2002г.), на 2-й научной сессии ДО международной академии информатизации (1996 г.), на семинаре посвященном проблемам математической кибернетики ДНЦ РАН (2002 г.), на семинаре лаборатории вычислительного эксперимента Ростовского госуниверситета под рук. д.ф.-м.н. Крукиера Л.А. (2003 г.), на научном семинаре Дагестанского регионального центра новых информационных технологий под рук. д.т.н. проф. Ахмедова С.А. (2000 г.), на совместном семинаре кафедр факультета КН и ИТ Саратовского госуниверситета (2002).

Объем работы. Содержание работы изложено на 101 страницах, список использованной литературы содержит 97 наименований.

1. Aho A.V., and J.D.Ullman. Private communication. 1972.

2. Annextein F., Swaminathan R. On testing consecutive ones property in parallel. Descrete Appl. Math. 88. 1998. P.7-28.

3. Anstee R.P., Nam Yunsum. More sufficient conditions for graph to have factors. Discrete Math. - 1998. - 184, №1-3. - P.15-24.

4. Anstee R.P.,Caccetta L. Orthogonal matchings. Discrete Math. - 1998. -179, №1-3. -P.37-47.

5. Armstrong Ronald D., Chenwei, Goldfard Donald.

6. Balinski Michel, Ralier Gujiaume. Graphs and marriages. Amer. Math. Mon. - 1998. - 105, №5. - P.430-445.

7. Booth K.S. PQ Tree Algorithms, Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkley C.A. 1975.

8. Booth K.S., Lueker G.S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Systems Sci. 13 (3), 1976.-P. 335-379.

9. Burkhard R.E., He Y., Kellerer H. A linear compound algorithm for uniform machine scheduling. Computing. - 1998. - 61, №1. - P. 1-9.

10. Computational experience with setups. Comput. and Oper.

11. Daniels Richard 1., Hua Stella Y. Heuristics for parallel-machine flexible -scheduling problems with unspecified job assignment. Webster Scott Comput. and Oper. Res. - 1999. - 26, №2 - P.143-155.

12. Dantzig G.B., W.O.Blattner, and M.R.Rao, "All shortest routes from a fixed origin in a graph", in Theory of Graphs: International Symposium, Gordon and Breach, NY, 85-90 (1967).

13. Deogun J.S., Gopalakrishnan K. Consecutive retrieval property-revisited. Inform. Process Lett. 69. 1999. P. 15-20.

14. Edmonds Y. and Karp R.M., Teoretical Improvements in Algorithmic Efficiency for Network Flow Problems. -Y. ACM.-1972. -Vol.19.- P.248-264

15. Flammini М., Gambosi G., Salomone S. Boolean Reuting, Lecture Notes in Comput. Sci., Vol. 725, Springer, Berlin, 1993.

16. Fulkerson D.R., Gross O.A. Incedence matrices and interval graphs. Pacific J. Math. 15, 1965. P.835-855.

17. Gnan D.J., Zhu Xuding. Multiple capacity vehicle routing on paths. Discrete Math. - 1998. - 11, №4. - P.590-602.

18. Goldberg Andrew V., Rao Satish. Flows in undirected unit capacity networks. Discrete Math. 1999. - 1999.- 12, №1 - P. 1-5.

19. Habib M., McConell R., Paul C.,Viennot L. Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoret. Comput. Sci. 234. 2000. P.59-84.

20. Hajiaghayi M.T., Ganjali Y. A note on the Consecutive Ones Submatrix problem. Information Processing Letters 83, 2002. P. 163-166.

21. Hind Hugh, Zhao Yue. Edge colorings of graphs embeddable in surface of low genus. Discrete Math. 1998 - 190, №1-3. - P. 107-114.

22. Itai A., and M. Rodeh, "Some matching problems" in Automata, languages and programming, Lecture Notes in Computer Science, Vol. 52, Spring, Berlin, 258-268 (1979).

23. Jonson D.S. Near-Opimal Bin Packing Algorithms, Doctoral Thesis, Dept. of Mathematics, Massachusetts Institute of Technology, Cambridge, 1973.

24. Karp, R.M. "Reduciblity among combinatorial problems", in N.E.Miller and J.W.Thatcher (eds), Complexity of Computer Computations, Plenum Press, New York, 1972, 85-103.

25. Kou L.T. Polinomial complete consecutive information retrieval problems, SIAM J. Comput. 6. 1977. P.67-75.

26. Lu Changhong, Yao Tianxing. The strong edge colouring of cycles and complete graphs. Math. Biguartely. - 1998. - 15, №2. - P.186-190.

27. Meidanis j., Porto O., Telles J.P. On the consecutive ones property. Diskrete Appl. Math. 88, 1998. P.325-354.

28. Res. 1998. - 25, №5. -P.351-366.

29. Rios Mercado Roger Z., Bard Jonathan F.

30. Sahni S. Approximate algorithms for the u/i knapsack problem. J.assoc: Comput. Mach. 22, 115-124 (1975).

31. Sahni, S., "Computationally related problems", SIAM J. Comput. 3, 262-279 (1974).

32. Shiraishi shuji. A remark on maximum matching of line graphs. Discrete Math. - 1998. - 179, №1-3. - P.289-291.

33. Strongly polynomial dual simplex methods for the maximum flow problem. -Math. Programm. A. 1998. - 80, №1.- P. 17-33.

34. Tuza Zsolt. Graph coloring with local constraints. -Discuss. Math. Graph Theory. 1997. - 17, №2. - P. 161-228.

35. Yuan jinjiang. Induced matching extendable graphs. J. Graph Thery. -1998. 28, №4. - P.203-213.

36. Альрашайда А. Об оптимизации матрицы. Вестник ДГУ.- Выпуск 4. -Махачкала, 1999г.-С.2.

37. Альрашайда А. Оптимизация мультизадачного графика по временному критерию. 2000 //канд.дис.

38. Ахо А., Ульман, Д., Хопкрофт Д . Построение и анализ вычислительных алгоритмов. М.:Мир, 1979. - 536С.

39. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, Физматгиз, 1974.-366С.

40. Басангова Е.С. Нахождение эйлерова цикла в смешанном графе. в сб. Модели и дискретные структуры. -Элиста: Калмыц. гос. ун-т, 1996. -С.58-61.

41. Белов В.В. и др. Теория графов. М.: Высшая школа, 1976. - 392С.

42. Березин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. М.: Советское радио, 1974. - 304С.

43. Блох А.Ш. Граф схемы и алгоритмы. - Минск: Высшая школа, 1987. -141С.

44. Турина Л.Г. Оптимизация: теория и алгоритмы. М.: Наука, 1973. -244С.

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

46. Данкан Р. Профессиональная работа в MS DOS: пер. с англ. М.: Мир, 1993.-509с.

47. Дж.Просиз. Управление памятью в DOS 5: М.: Мир, 1994. 240с.

48. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 1999 г. -279с.

49. Емеличев В.А., Мельников О.И. , Сарванова В.И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. - 384С.

50. Зубов B.C. Справочник программиста. Базовые методы решения графовых задач и сортировки. М.: Информационно-издательский Дом "Фи-линъ", 1999.-256с.

51. Зыков A.A. Основы теории графов. М.: Наука, 1987, - 384С.

52. Иванова В.В., Березовский В.К. Методы алгоритмизации непрерывных производственных процессов. М.: Наука, 1975. - 400С.

53. Камерон П. Линт Дж. Теория графов, теория кодирования и блок-схемы. -М.: Наука, 1980- 139С.

54. Конвей Р.В., Максвелл В.Л. , Миллер Л. Теория Расписаний. М.: Наука, 1975. - 360С.

55. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения, -М.: Мир, 1965.-302С.

56. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978. 432С.

57. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

58. Магомедов A.M. Аналог теоремы Холла. Деп. в ВИНИТИ № 447-85, 1985.-7С.

59. Магомедов A.M. Выделение двух множеств непересекающихся двудольных паросочетаний. Деп. в ВИНИТИ № 7332, 1986. 9С.

60. Магомедов A.M. К вопросу минимизации разделяющих нулей в строках матрицы. Деп. в ВИНИТИ № 7224, 1984. 8с

61. Магомедов A.M. Минимизация простоев. Тезисы Всесоюзн.семинара «Системное моделирование производства, распределения и потребления», ч.2. Воронеж, 1986. 2с.

62. Магомедов A.M. Псевдополиномиальный алгоритм решения задачи уплотнения матрицы для одного частного случая. Деп. в ВИНИТИ №67621389, 1989.-5с.

63. Магомедов A.M. Раскраска графа с непрерывным спектром. Деп. в ВИНИТИ №478, 1985.-Зс.

64. Магомедов A.M. Сдвиг по полупустому циклу для уплотнения графика работы нескольких исполнителей. Деп. в ВИНИТИ № 7225, 1984. 9с.

65. Магомедов A.M. Сильные NP-полные задачи о матрице со свойством псевдосвязности. Деп. в ВИНИТИ №6761-1389, 1989. 6с.

66. Магомедов A.M. Теорема о п.н.п. с ограничениями. Деп. в ВИНИТИ № 7155В-85, 1989.-7с.

67. Магомедов A.M. Условия и алгоритм уплотнения матрицы из 4 столбцов. Деп. в ВИНИТИ, 1991. 7с.

68. Магомедов A.M., Альрашайда А. Матрица расписания с двумя ненулевыми элементами в строке. Вестник ДГУ. Выпуск 4. - Махачкала, 1999. -4с.

69. Магомедов A.M., Альрашайда А. Необходимые условия уплотнимости матрицы перестановок из 5 столбцов. Вестник ДГУ. Выпуск 1. - Махачкала, 1998.-с.130-131.

70. Магомедов A.M., Альрашайда А., Якубов А.З. Оптимальное размещение TSR-программ. Вестник ДГУ. Выпуск 4. - Махачкала, 1997. - с. 133138.

71. Новиков O.A., Петухов С.И. Прикладные вопросы теории массового обслуживания. М.: Советское радио, 1969. - 399с.

72. Овчаров A.A. Прикладные задачи теории массового обслуживания. М.: Машиностроение, 1969. - 323с.

73. Оре О. Теория графов. М., Физматгиз, 1968. - 352с.

74. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. —М.: Мир, 1985. 510с.

75. Рейнголод Э., Нивергельт Ю. , Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476с.

76. Романовский И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977. -352с.

77. Саульев В.К. Математические модели теории массового обслуживания. М.: Статистика, 1979. - 96С.

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

79. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. М.: Наука, 1975. - 256С.

80. Танаев B.C., Гордон B.C., Шафранский Я. Теория расписания. Одностадийные системы. М.: Наука, 1984. - 382С.

81. Фролов А.Б. и др. Прикладные задачи дискретной математики и сложность алгоритмов. М.: Издательство МЭИ, 1997.

82. Фаронов В.В. Турбо Паскаль 7.0. Практика программирования. Учебное пособие. -М.: "Нолидж", 1997 432С.

83. Федоров А.Г. Delphi 6.0 для всех. КомпьютерПресс, 2002. - 544 С.

84. Финогенов К.Г. Самоучитель по системным функциям MS/DOS. М.:МП «МАЛИП», 1993 262С.

85. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1963.

86. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.-520С.

87. Якубов А.З. Вытеснение окон в матрице расписания. Деп. в ВИНИТИ № 1838-В2002, 2002.-9С.

88. Якубов А.З. Дефрагментация матриц класса . «Вестник молодыхученых Дагестана», №3, 2003 г., ДНЦ РАН.

89. Якубов А.З. Дефрагментация строк матрицы перестановок. Деп. в ВИНИТИ № 1638-В2002, 2002. ЮС.

90. Якубов А.З. К вопросу об оптимизации параллельной формы численных алгоритмов. Вестник ДГУ, Махачкала, 1998. 4С.

91. Якубов А.З. Метод динамического программирования в решении задачи «Разбиение». Вестник ДГУ, 2002 г. 5С.

92. Якубов А.З. Об уплотнимости матрицы перестановок в случае 7 столбцов. Вестник ДГУ, 2001. 1С.

93. Якубов А.З. Распараллеливание алгоритма решения краевой задачи на машинах с распределенной памятью. Сб.ст. "Труды молодых ученых".-Выпуск 1, Махачкала 1996. - с.64-68.

94. Якубов А.З. Состояние и перспективы развития языков параллельного программирования. Материалы 2-й научной сессии Дагестанского отделения Международной академии информатизации, 1996. с.33-37.

95. Дьяконов В. Mathematica 4: учебный курс. СПб.: Питер, 2001. - 656с.

96. Дьяконов В. Maple 6: учебный курс. СПб.: Питер, 2001. - 608с.rour:-a-05