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

• Грицак, Валерий Владимирович
• кандидат физико-математических наук
• 1983

Оглавление диссертации кандидат физико-математических наук Грицак, Валерий Владимирович

ВВЕДЕШЬ.4-II стр.

ГЛАВА I.ИССЛЕДОВАНИЕ АЛГЕБРАИЧЕСКИХ И КОМБИНАТОРНЫХ СВОЙСТВ СИСТЕМ НЕЗАВИСИМОСТИ И ЧАСТИЧНЫХ МАТРОИДОВ.

§1.1.Системы независимости и частичные матроиды.Основные определения и примеры . 12-21 стр.

§1.2.Структура -независимых матроидов и матроидных спектров .22-33 стр.

§1.3.Теоремы перестановочного типа для -независимого матроида . 34-38 стр.

§1.4.Категорные свойства матроидных спектров и -независимых матроидов.Построение прямого копроизведения и свободного универсального объекта . 39-46 стр.

ГЛАВА 2.АЛГОРИТМЫ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ КОМБИНАТОРНОЙ И ЦЕЛОЧИСЛЕННОЙ 0ПТ1ШЗЩИИ.

§2.1.Решение задачи нахождения независимого множества,максимального по Парето,для линейной многокритериальной оптимизации над матро ид ом .4-7-52 стр,

§2.2.Нахождение множества наибольшего веса для -независимого матроида . 53-57 стр.

§2.3.Построение полного множества Парето для задачи линейной многокритериальной оптимизации над матроидом . 58-61 стр.

§2.4.Алгоритмы сведения целочисленной матрицы к нормальной форме

Смита,форме Ярмита,форме Смита.62-74 стр.

§2.5.Решение задачи линейной целочисленной оптимизации над конечной абелевой группой.75-82 стр.

ГЛАВА 3.ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОЙ ЦЕЛОЧИСЛЕННОЙ ОПТШЗЩИИ.ШЧЙСЖТЕ'ЛЬНЫЙ ЭКСПЕРИМЕНТ. ПРИЛОЖЕНИЯ.

§3.1.Программная реализация алгоритма решения задачи линейной целочисленной оптимизации . 83-87 стр.

§3.2.Результаты вычислительного эксперимента с программной реализацией алгоритма решения задачи линейной целочисленной оптимизации на РВМ ЕС 1040-1060 . 88-91 стр.

§3.3.Постановки и решения задач оптимального раскроя материалов 92-97 стр.

Введение диссертации (часть автореферата) на тему «Алгебраические методы исследования некоторых задач дискретной оптимизации»

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

Алгебраический метод исследования задач дискретной оптимизации является одним из наиболее эффективных методов.Алгебраический подход к решению задач дискретной оптимизации,в сочетании с другими методами,разрабатывался в работах Биксби,Гомори,Журавлева Ю.И.,Емеличева В.А.,Ковалева М.М.,Леонтьева В.К.,Ловаса,Рыбникова К.А.,Корте,Сеймура,Сергиенко И.В.,Супруненко Д.А.,Трубина В.А., Ху,Шора Н.З.,Здмондса и ряда других авторов,см. [601 , [S3 j ,

ГШ , [4 63 , ГШ , [231 , № , [80] , [5Л , [31] , 1331 , гл] , WJ , [36] . № , ft 6] .

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

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

Впервые понятие матроида возникло в работе Уитни как формализация линейной независимости для специальных структур в теории графов.Применение теории матроидов к дискретным оптимизационным задачам началось несколько позже в работах Рдмондса,Татта, см. [S01 , [S3] ,в которых матроидам отводилась роль структур, лежащих в основании всей дискретной оптимизационной теории. Такая точка зрения оправдала себя только частично.Был построен так называемый (^ZttcL^ -алгоритм для нахождения множества максимального веса относительно действительной положительно-значной функции,заданной на элементах матроида (/И .Построены эффективные алгоритмы для решения задач о максимальных многопродуктовых потоках для более широких классов сетей [И] , [И] , [61] .Усовершенствованы алгоритмы минимального разбиения множества с весами [4 3] , 15П .Построены полиномиальные алгоритмы для решения задач декомпозиции графов и распознавания полной унимодулярности целочисленной матрицы,см. & J , [go] ,выбора минимальной подсистемы уравнений Теория матроидов успешно применяется и к решению прикладных технических задач,см. а] , [ей ,в теории планирования эксперимента .Область приложений теории матроидов постоянно расширяется.

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

Hi , [tf] , 163} было предпринято ряд попыток обобщения понятия матроида,с целью расширения их области применимости.Основными конструкциями,обобщающими понятие матроида,есть следующие.Понятие суперматроида,см.

16] ,а также [S3] .Полуматроида Ц9] . В -независимого матроида, см. [ft] .Биматроида [И ] .Гредоида, см. [?0]

Все вышеназванные конструкции,обобщающие понятие матроида,преследуют различные цели,но все они ,кроме полуматроидов и гредоидов, являются системами независимости. -независимый матроид и матро-идный спектр,а также гредоид и полуматроид,не являются,в общем случае, системами независимости.Причем,полуматроид и гредоид являются специальными случаями -независимого матроида,а ^ -независимый матроид является частным случаем матроидного спектра. Наглядно, -независимый матроид является комбинаторной конфигурацией^ которой для множеств с мощностью не меньшей, чем некоторое фиксированное целое число о^ выполняется аксиома независимости, а для множеств мощности меньшей,чем об выполняется не всегда.В матроидном спектре необходимо,чтобы аксиома независимости выполнялась для подмножеств с мощностями лежащими внутри нескольких целочисленных интервалов.Тем не менее, о^ -независимый матроид можно представить,если он не является вырожденным, в виде поочередных применений операций взиманий матроидов и отчуждений, теорема 1.2.2.Верна и обратная теорема,причем без условия невырожденности./Соответствующие определения и теоремы смотри в §1.2 и §1.1/.Такие конструкции являются достаточно общими,но и естественными,так как для них доказываются ряд классических теорем теории матроидов.Такими теоремами,например,являются теорема о равномощности базисов /теорема I.1.1/,перестановочная теорема для базисов /теорема 1.3.1/,так называемая обобщенная гипотеза Рота /теорема 1.3.2/.По поводу матроидных аналогов вышеназванных теорем см. 15П , [S8] , ft Я .На естественность обобщения указывают и теоремы I.I.2 и I.1.3,которые описывают частично упорядоченное множество матроидных спектров,заданных на фиксированном множестве.А также теоремы 1.4.I и 1.4.2,которые показывают возможность построения прямого копроизведения и свободного универсального объекта в категориях,являющихся аналогами категорий матроидов и свободных отображений, см. В Я, [J Я чем,эти конструкции являются практически единственными работающими в обычных матроидах,см. [?Я , [?«] , ГЦ] , Из] .

Достаточно полные обзоры по теории матроидов и ее приложениям содержатся в [Ш и 1гз] .

В значительном числе оптимизационных,в частности дискретных задачах,не существует единого критерия оптимизации,что привело к созданию методов многокритериальной оптимизации.По-поводу дискретных многокритериальных оптимизационных задач,см. , ['Н 2 ] 5

И J , ГЯ] , ГЯ] , D6 9I , [91] .

В §2.1 и §2.3 настоящей работы предлагаются алгоритмы решения линейной многокритериальной оптимизационной задачи /2.1.3/-/2.1.5/ над матроидом №\ , ГШ .Алгоритм 2.1 Л,на основании теоремы 2.1 Л,находит независимое множество заданного матроида,тлеющее максимальный вес по Парето относительно функций /2.1.1/. Оценка временной сложности /2.1.27/ алгоритма 2.1 Л показывает, что алгоритм является эффективным и тем самым пополняется список эффективных по Эдмондсу алгоритмов.

В некоторых прикладных многокритериальных оптимизационных задачах необходимо построение всех решений с целью их дальнейшего анализа.Алгоритм 2.3.1 из §2.3 находит полное множество Парето задачи /2Л.3/-/2Л.5/.

Алгоритм 2.2.1 из §2.2 вновь демонстрирует важность теорем из §1.2,на основании которых он строится.Алгоритм 2.2.1 находит об -независимое множество невырожденного об -независимого матроида максимального веса.Оценка временной сложности /2.2.19/ указывает на эффективность алгоритма 2.2Л,который в свою очередь пополняет список эффективно разрешимых задач.

Приведение целочисленных матриц к формам Смита и форме Зрми-та применяется для решения систем линейных уравнений в целых числах [Zi 1 ,в оптимальном управлении динамическими системами и других задачах.Впервые были введены в работах [Si] ,

В дискретной оптимизации формы Смита начали применяться после работы Гомори [60 ] ,где Оыло показано как их применять для сведения задачи линейной целочисленной оптимизации к задаче оптимизации над конечное абелевой группой,см. [35] , [9] ,Ц0].

В §2.4 приводятся алгоритмы 2.4.1,2.4.2 и 2.4.3,которые сводят целочисленную матрицу к соответствующим формам Смита,Ярмита и форму Смита к нормальной форме Смита.Оценки их временной сложности /2.4-.22/,/2.4.24/,/2.4.27/ лучше аналогичных оценок других алгоритмов

3S] ,что в сочетании с преимуществами алгоритма 2.5.1,решающего линейную групповую задачу,позволяет построить эффективную программную реализацию решения задачи линейной целочисленной оптимизации.эффективность программной реализации подтверждается и вычислительным экспериментом,результаты которого приведены в §3.2,решением прикладных инженерных задач животноводческого машиностроения из §3.3,акт внедрения программной реализации алгоритма находится в приложении к данной работее

Теперь о структуре работы.

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

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

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

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

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

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

I/Построение и исследование свойств теории частичных матроидов -объектов,для которых аксиома независимости гарантировано выполняется только для множеств фиксированной мощности,так называемых

-независимых матроидов и матроидных спектров.Доказательство теорем 1.2Л и 1.2.2,позволяющих сводить результаты о матроидах к

-независимым матроидам и представлять невырожденный о£ -независимый матроид в виде совокупности матроидов.А также,теорему I.2.3,которая сводит матроидный спектр к -независимому матро-иду и обратно.В частности,получены следующие результаты: а/доказана справедливость перестановочной теоремы для базисов

- не з ави симо г о матро ид а б/ доказана справедливость обобщенной гипотезы Рота для об -независимых матроидов,теорема 1.3.2. /В случае невырожденности/. 2/йсследованы категорные свойства частичных матроидов.Построены прямые копроизведения для категорий невырожденных ££ -независимых матроидов и о^ -независимых матроидов равной высоты ,и свободных отображений,теоремы 1.4.I и 1.4.2.Построены свободные универсальные объекты в категориях матроидных спектров, -независимых матроидов и свободных отображений,теорема 1.4.3. З/Исследованы структурные свойства частично упорядоченных множеств с£> -независимых матроидов и матроидных спектров,упорядоченных с помощью свободного отображения,теоремы I.I.2 и I.I.3. 4/На основании исследования свойств решения многокритериальных задач над матроидом получены алгоритмы решения следующих задач: а/задачи линейной многокритериальной оптимизации над матроидом, алгоритм 2.1.I,с оценкой временной сложности

Q(ln,ztoqyi) т), где YO- мощность основного множества матроида, WO - число функций, что расширяет класс эффективно разрешимых задач; б/зад,ачи нахождения полного множества Парето для линейной многокритериальной оптимизации над матроидом,алгоритм 2.3.1. 5/На основании исследования свойств -независимых матроидов,построен алгоритм решения задачи линейной оптимизации над -независимым матроидом,алгоритм 2.2.1,с оценкой временной сложности

О {п(уь-к)кг), где УЬ- мощность основного множества -независимого матроида^ 1>Ъ- мощность его спектра,в случае, когда -независимый матроид является невырожденным,пополняя класс эффективных алгоритмов . б/На основании теоретических исследований свойств целочисленных матриц,теоремы 2.4.1 и 2.4.2,получены новые алгоритмы приведения целочисленной матрицы к нормальной форме Смита,форме Смита и форме Ррмита с улучшенной оценкой временной сложности /алгоритмы 2.4.1,2.4.2 и 2.4.3/.

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

Все вышеуказанные результаты являются но вбили и принадлежат автору.

Работа выполнена в отделе экономической кибернетики Института кибернетики АН УССР им.В.М.Глушкова.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Грицак, Валерий Владимирович

ЗАКЛЮЧЕНИЕ В заключении перечислю/! основные результаты диссертационной работы.

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

С, -независимых матроидов; б/доказана справедливость обобщенной гипотезы Рота для -независимых матроидов. /В случае невырожденности сС-н.м./. 2/йсследованы категорные свойства частичных матроидов.В частности,построены прямые копроизведения и свободные универсальные объекты,соответственно , ^ -независимых матроидов /невырожденных/ и свободных отображений,и с£ -независимых матроидов и матроидных спектров.

З/Исследованы структурные свойства множеств об -независимых матроидов и матроидных спектров,упорядоченных с помощью свободного отображения.В частности показано,что множество Ох К-Х) всех матроидных спектров фиксированной сигнатуры и над фиксированным множеством ОС является выпуклым подмножеством множества всех матроидных спектров той же сигнатуры,определенных над тем же множеством,но произвольного ранга S.£ (0^/4,., о^к") .Построены максимальные и минимальные элементы соответствующих частично упорядоченных множеств.

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

0((уьг locf Уь) Wb) , где УЬ -мощность основного множества, W\j -число функций; б/нахождение полного множества Парето для линейной многокритериальной оптимизационной задачи над матроидом. 5/На основании исследования свойств ^ -независимого матроида построен алгоритм нахождения ^ -независимого множества максимального веса для невырожденного -независимого матроида с оценкой временной сложности

О (иЛи,- к) кг) , где УЬ -мощность основного множества ^ -независимого матроида, a Pb -мощность его спектра.

6/Построен новый алгоритм решения задачи линейной оптимизации над конечной абелевой группой.Его эффективность демонстрируется результатами вычислительного эксперимента и оценками временной сложности, а также величиной объема необходимой оперативной памяти. 7/На основании исследований алгебраических свойств целочисленных матриц получены алгоритмы приведения целочисленной матрицы к нормальной форме Смита,форме Смита и форме Ррмита с оценкой временной сложности лучшей,чем у известных алгоритмов.

8/На основании алгоритмов из б/ и 7/ построен алгоритм решения зец-дачи линейной целочисленной оптимизации.Проведен вычислительный эксперимент,показавший эффективность программной реализации данного алгоритма.

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

-юо

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

1. Axo А.Допкрофт Дж.,Ульман Дж.Построение и анализ вычислительных алгоритмов.М.,Мир,1979,536 с.

2. Алексеев В.Б.Использование симметрии при нахождении ширины частично упорядоченного множества.-Дискретный анализ,1974,вып.26,с.20 -35.

3. Биркгоф Г.,Барти Т.Современная прикладная алгебра.М.,Мир,1976, 400 с.

4. Букур И.,Деляну А.Введение в теорию категорий.М.,Мир,1972,259 с.

5. Виноградов И.М.Основы теории чисел.М.,Наука,1972,168 с.

6. Виноградская Т.М.Среднее значение числа неподчиненных решений в многокритериальных задачах.-Известия АН СССР,сер."Техническая кибернетика" ,1976,№2,с.36-38.

7. Виноградекая Т.М.,Гафт М.Г.Точная верхняя оценка числа неподчиненных решений в многокритериальных задачах.-Автоматика и телемеханика , 1974 5 !>'9, с Л11 -118.

8. Гришухин В.П.О среднем числе итераций алгоритма Балаша.-В кн.: Исследования по дискретной математике.М.,Наука,1973,с.58-68.

9. Грицак В.В. Системы независимости матроидного типа.- ДАН УССР, сер.А,1982,Е9,с.61-63.

10. Грицак В.В. О некоторых многокритериальных задачах для систем независимости.-Тезисы докладов II Всесоюзного совещания "Методыи программы решения оптимизационных задач на графах и сетях" Улан-Удэ,24-26 августа 1982 г.,часть 2.Новосибирск,1982,с.38-40.

11. Шуравлев Ю.И. Локальные алгоритмы вычисления информации.-Кибернетика, 1965 ,г!-1, с. 12-21.

12. Емеличев В.А.,Ковалев М.М.,Кравцов М.К. Многогранники,графы, оптимизация. М.,Наука,1981,341 с.

13. Квлев В.И. Программа,реализующая асимтотический алгоритм.-Экономика и математические методът,1981,т Л7,!;-2,с.388.

14. Ковалев М.М.Дискретная оптимизация /целочисленное программирование/ .Минск,БГУ,1977,192 с.

15. Ковалев М.М. Полиэдральные полуматроиды.-Известия АН БССР, сер. физ.-мат. наук, 1979,11-3,с.8-12.

16. Кострикин А.И.Манин Ю.И. Линейная алгебра и геометрия. М., МГУ,1980,318 с.

17. Кофман А.,Анри-лабордер А. Методы и модели исследования операций. Целочисленное программирование.М.,Мир,1977,432 с.

18. Ленг С. Алгебра.М.Мир.1968,564 с.

19. Леонтьев В.К. Дискретные экстремальные задачи.-В кн.:Итоги науки и техники,сер.Теория вероятностей,математическая статистика, теоретическая кибернетика.".М.,ВИНИТИЛ979,с.39-101.

20. Леонтьев В.К. Алгебраическая структура некоторых задач дискретного программирования.-В сб."Проблеммы кибернетики",вып.26. М.,Наука,1973,с.279-290.

21. Литвак Б.Г.,Найвельт А.В.Опорные групповые элементы в алгоритме групповой оптимизации.-В кн.:Исследования по дискретной оптимизации. М.,Наука,1976,с Л87-203.

22. Майника Алгоритмы оптимизации на сетях и графах.М.,Мир,1979, 321 с. •

23. Михалевич B.C.,Сергиенко И.В. и др.Результаты экспериментального исследования эффективности методов включенных в пакет прикладных программ ДИСПРО.-Киев:ИК АН УССР,1980,67 с.

24. Михалевич B.C.,Сергиенко И.В.,Лебедева Т.Г.,Шор Н.З.,Рощин В.А., Стукало А.С.,Трубин В.А.Пакет прикладных программ ДИСПРО,предназначенных для решения задач дискретного программирования.-Кибернетика,1981,РЗ,с.117-135.

25. Подиновский В.В.,Ногин В.Д.Паретно-оптимальные решения многокритериальных задач.М.,Наука,1982,254 с.

26. Ревякин A.M.Об одной конструкции в категориях комбинаторных геометрий.-ДАН СССР,1976,т.229,с.1055-1058.

27. Рыбников К.А.Введение в комбинаторный анализ.-М.,МГУ,1972, 228 с.

28. Сергиенко И.В. О применении метода вектора спада для решения задач оптимизации комбинаторного типа.-Управляющие системы и машины, 1975,Р2,с.86-94.

29. Супруненко Д.А.О значении линейной формы на множестве подстановок . -Кибернетика, 1968,\"2, с. 59-63.

30. Супруненко Д.А.,Метельский Н.Н.Задача о назначениях и минимизация линейных форм на симметрической группе.-Кибернетика,1973, РЗ,с.64-68.

31. Ху Т.Целочисленное программирование и потоки в сетях.М.,Мир, 1974,519 с.

32. Шор Н.З.Метод отсечения с растяжением пространства для решения задач выпуклого программирования.-Кибернетика,1977,PI, с.9495. 37

33. G/lcock Ж., P. On Uu, tuwnftfa^e SiAm-loz o^ iAi Ьъши c^ж/б&гы1. Л^гкя/ J979} &J2 b 238. Ж.} j? Oft (Л1 ялМ39. {2/&<z&z7., jbAnden,-X! M

34. Jys^^&xtm of МяХАгт-а&яя/ Sw^am

35. З^дгмг Ж 0*ъ Vu, komo/oyy- of ^гя-тл&г^с УшХг&Ж. ///У. & £2/о.

36. ЗкмАаъйС Я. £.} ЖомъгуъсосАьг 76. fyUn^rrbtzZ42. Л. Jliodwytoyr Ягбс&ьгЖ^ //// / а/?^ р. 2 И-241ж, iz, ; tzsz, /колеса?5 19Щ jo. Sl-iOl47

37. C/lOf)£ Ж^ flota, &- С. &С0- Ог^ггЛъоа^у^ 7 {970, 3 $8/о.46. Ссошш^гсот, UT Ж, £

38. G^cc^u, £ О, joъо^э-гъёу ^о-ъ о/ iAz/ {Z^n^oc-cc^b jtlooffluаЛлзсё f$73i * 39, /J?I to. 4 f-M

39. С. (ZfbotAe/i ^■cAa^^-e jeUsybeatiu ^оъоош. f & tlej fi/zjb. Iff-ttt.58. ^bC-dAxyoA^Z/гл&ъ&бб ia vo19*i Ъ 2i} jo. ЮfrbbttvcwU -сшуоб (у(льбосс 9 {981 ^ ь. aAt, jo. 169- 19160. (?<?<*<уь>&гу St £-. On, тл %,-bej /О ,0 г

40. J'tsO^eosM. b/ъ0С. . (Z-eseotC. See. &. S3, a/si, jo.to&K iA& STLCO^ Тйьиьбшг О&^ъЖ; Сь&маЬЫ;96 ft Si к jo.

41. XL. £ tfJbO ~bl/bwv lou XXAbd али?ъСтлль6 joK/Stom^. XL А'ШЬ'ъи^. - tocu? jo&coyi ^ OUSlsfcGiZ, oj- OjpMsCLbioibody bUUsCtSlscMb ^i980 t b. p. 8' is.66. %<aAL & ыСуогМАтл jet wboLbo^uoU.

42. Л(ум£о ШоМьтьо(£Ьсл, &J9, fl/Н, р.ш-ш.

43. M. XCjop^oooctoon^ oj- wbodsboid iAtObf^to u^u^fMbi^ MjiLuvu j3bo^?lbmi.

44. Ыь C/OVbj^bVfrCt Oib PvOV'CLbUMLj Mjot. 40-if. Яомьоьуьись, 1919, 36 р.68. %OAbVbCOfo. Я, ^OUtlbVWb XL. 9<)lyYU0WbloU, vU/^O-iMomi job оош^ииШь^ Uu cmd %ozmJjU Wum/oJL j-оьш oj- сои, bwtojifc тсЖиос,.- 5ГЛ Mtfm. otv towf. , ШУ, b. л/M, p. Ш.

45. KlUvb ЮМм.7 УЬомъиуШ tcLw-cc^cL. XCtb wC

46. CjOtotikm, job Ькл YMAsOUjplL, obj-ocjtcbb Сш-Ьс^&ь £6ФЪ</ССЪ ^ОФЬСО'ИЫ^Ь^^С^ ръо-бб&т,.19SZ, Ъ 9 , л/М, p. ЪП-ЪИ.70. llovbts Я7 ^оъс/иъ Яу. fybcrthmiscrticscuc Фшх

47. Ьоиыл cjbtod^ -obLcjtibitkm^.33 (№ь: ^Vbditwt рл окошэтЖъос co^ol Орьъооtoom. ъслоосьсА f Яор. a/? sass Oil, i98it Sp

48. Хшу I P. I. 0*v dsjo-ococoUz^ctloib d wscutbOicU.- dtoooUa L*b GLjofol ШШъ.^ПО^Ъ.ьгь.М-т.

49. KusMj J.fii. Bims(U<wicU cuvucL мъоикЬсшАл

50. CLqUouk/cu oi<b nbcotkuvbcuUa, isu ь. во $ p.ZSS-ZkS. ' '73. &OA VvbOjyucu, Ы. Oib pvocLbucU oj- KbouUoioU$Uo<bUt PvodAe^v^a, im 1 ь. зб, /f*l, /?. kl-ff.

51. XObcufc bo. ttbootboiab moutdbwsq co^otl wwa,y>f>M0CCti0HA.- of towUiybecto^ioLC$ku>ty t то, шЛи 33 zs, V Z08

52. Noito+V R Jtofamcum & Щ Ыьц Ш. 0. И а<ыьjoJbi&oU/ bopzMJMrtootoon oj- msCuUoicU.- 51 AM 1 ow ШоМь., тз, v. p. м- m.

53. П^пьоиь fkotpi f.a. fblmivb muMrCb1.slba, ojr UytLOUO dUfinjCLsMAC/CLl SI ДМ7o<uu*sClL Oib {gjo ь 8 a/= {p. 19'k0. ' '

54. УЬ^^ОУЬ Qt fvM&Uc<KA ШЪсЬ bOWsfa+VOUtOuCCt qMWA&bdll . fvMMA,CU&OQi>Uof- the QsmmmsC/oohs 1%(d2bbMbctJsic/CuL <lodvta,mt, b. Z38, f>. 3SS' 383.78. fbytoyw %, <2. Susvuct/Ou oj ikb bouUsyovf ol

55. ЖсйМ^а&мсб Яя&ьбипмьбшу7 tp.zib. Mb- ZZ3.обоС tffa&oiy, . : tZcaоб&^с- f^cM } 433 ft.6>J } a , jb> S6>9- S33.1. СС&^&б'ь&лс, У^е^^ско^^1. Уш^Алсиp 32f jo. $-3i91. jk&tbtl -ds. d> иоъъ-гу о/jo 389- 398,