Поисковые алгоритмы решения задач условной псевдобулевой оптимизации тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Масич, Игорь Сергеевич

• Масич, Игорь Сергеевич
• кандидат физико-математических наук
• 2004

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

Введение

1 Постановка задачи. Необходимый математический аппарат

1.1 Состояние проблемы

1.2 Свойства пространства булевых переменных

1.3 Классы псевдобулевых функций

1.4 Постановка задачи оптимизации

1.5 Свойства множества допустимых решений задачи

1.6 Идентификация свойств псевдобулевых функций

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

1.6.2 Идентификация свойств посредством квадратичной аппроксимации

1.6.2.1 Способы квадратичной аппроксимации псевдобулевых функций

1.6.2.2 Определение свойств квадратичной функции Выводы

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

2.1 Составление обобщенной функции со штрафом

2.2 Регулярные точные алгоритмы безусловной оптимизации

2.3 Локальный поиск

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

2.3.2 Локальный поиск для условной оптимизации

2.4 Схема метода ветвей и границ

2.4.1 Общая схема метода ветвей и границ

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

2.4.3 Приближенные алгоритмы метода ветвей и границ

2.4.4 Условная оптимизация изотонных псевдобулевых функций 56 Выводы

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

3.1 Классы задач условной псевдобулевой оптимизации

3.1.1 Свойства функций ограничений

3.1.2 Свойства целевых функций

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

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

3.3.1 Случай монотонной целевой функции

3.3.2 Случай унимодальной целевой функции

3.3.3 Случай целевой функции общего вида

3.4 Алгоритмы псевдобулевой оптимизации с унимодальными 81 функциями ограничений

3.4.1 Случай монотонной целевой функции

3.4.2 Случай унимодальной целевой функции

3.4.3 Случай целевой функции общего вида

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

3.5.1 Случай монотонной целевой функции

3.5.2 Случай унимодальной целевой функции

3.5.3 Случай целевой функции общего вида

3.6 Системьрограничений 91 Выводы

4 Приближенные*алгоритмы условной псевдобулевой оптимизации

4.1 Случайный поиск граничных точек

4.2 Гриди алгоритмы

4.2.1 Основные принципы и обоснование гриди эвристики

4.2.2 Гриди алгоритмы для условной псевдобулевой оптимизации

4.2.3 Оценка точности гриди алгоритмов

4.3 Адаптивный случайный поиск

4.4 Экспериментальные исследования приближенных алгоритмов 108 Выводы

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

Актуальность, темы., Решение большинства реальных задач в области принятия решещщ требует формализации рассматриваемой ситуации, в которой следует осуществить» выбор, в виде оптимизационной задачи определенного ^ класса. Оптимальный выбор одной изнескольких допустимых альтернатив * по определенному критерию соответствует присвоению переменным формализованной задачи конкретных значений? из области допустимых, значений. Часто переменные могут принимать лишь одно из двух значений - ноль или единица. Соответствующие задачи называются задачами-оптимизации? с булевыми переменными или- задачами псевдобулевой оптимизации.

Как правило, при- решении- практических проблем; исследователь имеет дело с конкретной? постановкой задачи ■ условной псевдобулевой оптимизации. Данная работа; направлена на построение алгоритмов ■ решения' классов задач, покрывающих: все множество задач; условной псевдобулевой оптимизации: Кроме того, большинство известных методов предполагает задание целевых функций и ограничений? в виде алгебраических выражений, в то время как во многих; реальных задачах часть функций либо все функции* заданы, алгоритмически, что делает невозможным, применение к ним стандартных алгоритмов; и требует разработки поисковых процедур оптимизации. В то же время анализ многих практических задач, сводящихся к задачам псевдобулевой -оптимизации; позволяет выявить в них некоторые особенности в виде конструктивных: свойств, присущих как; целевым; функциям, так и ограничениям, накладываемым условиями задачи.,Следует также отметить, что при решении конкретной задачи полезно иметь информацию об эффективности алгоритмов, что дает возможность подобрать алгоритм с подходящей трудоемкостью.

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

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

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

Поставленная цель определила следующие основные задачи исследования:

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

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

3. Исследование эффективности известных методов решения задач условной псевдобулевой оптимизации.

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

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

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

Методы исследования. Аппарат теории множеств, теории вероятностей, исследования операций, дискретной оптимизации, математического программирования. Элементы теории вычислительной сложности.

Научная новизна работы:

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

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

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

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

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

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

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

Теоретическая и практическая ценность работы

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

Основные защищаемые положения:

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

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

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

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

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

Апробация работы. Основные положения и отдельные результаты диссертационной работы докладывались и обсуждались на всероссийских конференциях «Решетневские чтения» (2001-2003 гг.), на международной научно-практической конференции "САКС-2001" (г. Красноярск), на XL международной^ научной конференции "Студент и научно-технический у прогресс" (г. Новосибирск) в. 2002 году, на V международном: симпозиуме

ИнтеллектуальнБю- системы INTELS'2002» (г. Калуга), на всероссийских конференциях «Туполевские чтения» (г. Казань) в 2002-2003 гг., на всероссийской научно-технической конференции «Совершенствование технологии поиска и разведки, добычи и переработки полезных ископаемых» (г. Красноярск) в 2003 году, на всероссийской; научной конференции «Королевские чтения», (г. Самара) в 2003 г., на всероссийской научной. I конференции «Наука. Технологии. Инновации» (г. Новосибирск) в 2003 г.

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

Публикации^По теме диссертации: автором опубликовано девятнадцать работ.

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Масич, Игорь Сергеевич

Выводы

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

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

-4-

Заключение

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

Основныерюзультаты работы:

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

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

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

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

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

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

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

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

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

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

1. Антамошкин, А.Н. Системный анализ: проектирование, оптимизация и приложения / А.Н: Антамошкин и др. Красноярск: САА и СО РИА, 1996, т.1 -334"с.,,т.2 -290 с.

2. Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными ЛД.Н. Антамошкин. Томск: Изд-во Томского ун-та, 1987, 218 с.

3. Антамошкин, А.Н. Регулярная < оптимизация псевдобулевых функций >■ / А.Н. Антамошкиц^ Красноярск: Изд-во Красноярского ун-та, 1989, 284 с.

4. Антамошкин, А.Н. Регулярный: алгоритм оптимизации загрузки оборудования / А.Н. Антамошкин; Д.А'. Дегтерев, И.С. Масич // Труды конф. «Информационные недра Кузбасса». Кемерово: КемГУ, 2003, с. 59-61.

5. Антамошкин, А.Н. Гриди алгоритмы, и локальный поиск для условной псевдобулевой оптимизации / А.Н: Антамошкин, И.С. Масич // Электронный журнал "Исследовано в России", 177, стр. 2143-2149;, 2003 г. http://zhurnaliape.relarn.ru/articles/2003/177.pdf

6. Антамошкин, А.Н. Идентификация; свойств псевдобулевых. функций / А.Н. Антамоиташ, И.С. Масич // Электронный журнал "Исследовано в России", 130, стр. 1391-1396. 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/130.pdf

7. Антамошкин, А.Н: Не улучшаемый: алгоритм- условной- оптимизации-монотонных; псевдобулевых функций; / А.Н: Антамошкин, И.С. Масич; // Электронный журнал "Исследовано в России", 64, стр. 703-708, 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/064.pdf

8. Масич // Электронный журнал "Исследовано в России", 51, стр. 544-546, 2004 г. http://zhurnal.ape.relarn.ru/articles/2004/051 .pdf

9. Антамошкин, А.Н. Эффективные алгоритмы условной оптимизации монотонных псевдобулевых функций; / А.Н. Антамошкин, И.С. Масич // Вестник СибГАУ: Сб. науч. тр. / Под. ред. проф. Г.П. Белякова; СибГАУ. -Вып. 4. Красноярск, 2003, с. 60-67.

10. Антамошкин, А.Н. Оптимизация полимодальных псевдобулевых функций / А.Н. Антамошкин, B.C. Рассохин // ОФАП Минвуза РСФСР. Инв.№85119.М., 1985, 43 с.

11. Береснев, В Л: Математические модели планирования, развития систем, технических средств / В. Л. Береснев // Дискретный анализ и исследование операций. Серия 2. 1997, том 4, № 1, с.4-29.

12. Береснев, B.JI. Алгоритмы минимизации для некоторых классов полиномов от булевых переменных / В;Л. Береснев, А.А. Агеев // Модели и методы оптимизации: Сб. науч. тр. Новосибирск: Наука, 1988. Том 10. с.5-17.

13. Береснев, В.А. Экстремальные задачи стандартизации / B:JI. Береснев, Э.Х. Гимади, В.Т. Дементьев. Новосибирск: Наука, 1978; - 333 с.

14. Вайнгауз, A.M. Оптимизация изотонных функций с булевыми переменными / A.M. Вайнгауз // Деп. в ВИНИТИ; 3761 В86. Кемерово, 1986, 49 с.

15. Гене, Г. В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы (обзор) / Г. В. Гене, Е. В. Левнер // Известия АН СССР. Техническая кибернетика, 1976, № 6, с. 84-92.

16. Гене, Г7В. Эффективные приближенные алгоритмы для комбинаторных задач / Г. В. Гене, Е. В: Левнер М., 1981. - 68 с.

17. Гришухин, В.П. Полиномиальность в простейшейзадаче размещения / В.П. Гришухин // Препринт ЦЭМИ АН СССР. М., 1987, 64 с.

18. Дегтерев, Д.А. Оптимизация загрузки технологического оборудования предприятия / Д.А. Дегтерев, И.С. Масич, Г.А. Нейман // Вестник Ассоциации выпускников КГТУ. Вып. 8 / Красноярск: ИПЦ КГТУ, 2002, 166-170 с.

19. Дегтерев, Д.А. Поиск граничных точек в задаче условной оптимизации монотонных псевдобулевых функций / Д.А. Дегтерев, И.С. Масич // Объединенный научный журнал. «ТЕЗАРУС», Москва, 2003 № 2-3, 89-95 с.

20. Дюбин,- КЙТ Жадные- алгоритмы для- задачи- о ранце: поведение в среднем / Г.Н. Дюбин, А.А. Корбут// Сиб. ж. индустр. мат. 2, N2(4), 1999. - с. 68-93.

21. Журавлев, Ю. И. Локальные алгоритмы для задач линейного целочисленного программирования / Ю. И. Журавлев, Ю. Ю. Финкельштейн // В кн.: Проблемы кибернетики. М.: Наука,JL965, вып. 14, с. 289-295.

22. Имануилов,. П:А. Решение задачи формирования кредитного портфеля банка методом Мивер / П.А. Имануилов, В.А. Пуртиков // Вестник НИИ СУВПТ выпуск №5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко.- Красноярск: НИИ СУВПТ, 2000.

23. Казаковцев, JI.A. Подходы к автоматизации задач планирования ассортимента на торговых предприятиях / Л.А. Казаковцев // Вестник НИИ СУВПТ выпуск 1^5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко.- Красноярск: НИИ СУВПТ, 2000.

24. Ковалев, И. В. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами / И: В; Ковалев// Дис. док. техн. наук. Красноярск: КГТУ, 1997, 238 с.

25. Ковалев, М. М. Дискретная оптимизация (целочисленное программирование) / М. М. Ковалев. Минск, 1977. - 191 с.

26. Корбут, А.А. Дискретное программирование / А.А. Корбут, Ю.Ю. Финкелыитейн М. Наука. Гл. ред. физ.-мат. лит. 1969, 389 с.

27. Лбов, Tv'C. Выбор эффективной системы зависимых признаков / Г. С. Лбов. В; кн.: Вычислительные системы. Новосибирск: ИМ СО АН СССР, 1965, вып. 19, с. 21*94.

28. Лбов, Г. С. Программа "Случайный поиск с адаптацией для выбора эффективной системы зависимых признаков" 7 Г. С. Лбов. В кн.: Геология и математика. Новосибирск: Наука, 1970, с. 204-219.

29. Масич, И.С. Метод ветвей и границ в задаче оптимизации систем отказоустойчивого программного обеспечения / И.С. Масич // Научная сессия ТУ СУР / Материалы докладов межрегиональной научно-технической конференции / ТУ СУР, Томск, 2002, с. 31-34.

30. Масич, И.С. Отбор существенных факторов; в виде задачи псевдобулевой оптимизации / И.С. Масич // Решетневские. чтения: Тез. докл. VII Всерос. науч. конф./ СибГАУ. Красноярск, 2003, с. 234-235.

31. Нейман, Г.А. Регулярные алгоритмы псевдобулевой оптимизации систем отказоустойчивого программного обеспечения / Г.А. Нейман // Вестник НИИ СУВПТ выпуск №5: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 2000.

32. Нейман, Г.А. Метод случайного поиска граничной точки / Г.А. Нейман, Н.А. Филатов // Вестник НИИ СУВПТ: вып. 7: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 2001, с. 84-87.

33. Пападимитриу, X. Комбинаторная оптимизация / X. Пападимитриу, К.54 W

34. Стайглиц. Алгоритмы и сложность: Пер. с англ. - М:: Мир, 1985. - 512 с.

35. Попов, А.А. Оптимизационные методы формирования мультиверсионного программного обеспечения критичных по надежности систем управления / А.А. Попов // Дис. . канд. техн. наук. / Красноярск: НИИ СУВПТ, 2002, 192 с.

36. Попов, Rfor. Структурная оптимизация систем отказоустойчивого программного обеспечения / А.А. Попов, И.Н. Давыдов // Вестник НИИ СУВПТ выпуск №2: Сб. научн. трудов / Под общей ред. профессора Н.В. Василенко Красноярск: НИИ СУВПТ, 1999, с. 47-63.

37. Растригин, JI.А. Адаптация сложных систем / JI.A. Растригин. Рига: Зинатне.- 1981-. - 375 с.

38. Растригин, JI.A. Случайный поиск / Л.А. Растригин. М.: Знание, 1979,64 с.

39. Растрищн, Л.А. Решение задач разношкальной оптимизации методами случайного поиска / Л.А. Растригин, Э.Э. Фрейманис // Проблемы случайного поиска, 1988, выцЦ^, с. 9-25.

40. Семенкин, Е.С. Оптимизация технических систем / Е.С. Семенкин Е.С., О.Э. Семенкина, С.П. Коробейников. Красноярск: СИБУП, 1996, 358 с.

41. Семенкина, О.Э. Оптимизация управления сложными системами методом обобщенного локального поиска / О.Э. Семенкина, В.В. Жидков. М.: МАКС Пресс, 2002. - 215 с.

42. Сергиенко, И.В. Приближенные методы решения дискретных задач оптимизации 7 И.В. Сергиенко, Т.Т. Лебедева, В.А. Рощин. Киев: Наукова думка, 1981.-272 с.

43. Сигал, И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы / И.Х. Сигал, А.П. Иванова. Учеб. пособие. - М.: ФИЗМАТЛИТ, 2002. - 240 с.

44. Стоян, Ю.Г. Об одном отображении комбинаторных множеств в евклидово пространство / Ю.Г. Стоян // Препринт ИПМаш АН УССР. Харьков, 1982,33 с.

45. Финкельштейн, Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Ю.Ю. Финкельштейн. — М.: Наука, 1976. -264 с.

46. Хачатуров, В.Р. Аппроксимационно-комбинаторный метод и некоторые-а* ' ^