Комбінаторика в задачах штучного інтелекту

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автори:	Тимофієва, Н.К., Гриценко, В.І.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2017
Назва видання:	Управляющие системы и машины
Теми:	Фундаментальные и прикладные проблемы Computer Science
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/124958
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Комбінаторика в задачах штучного інтелекту / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2017. — № 2. — С. 6-19, 37. — Бібліогр.: 10 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124958
record_format	dspace
spelling	irk-123456789-1249582017-10-13T03:03:25Z Комбінаторика в задачах штучного інтелекту Тимофієва, Н.К. Гриценко, В.І. Фундаментальные и прикладные проблемы Computer Science Для деяких задач штучного інтелекту з використанням теорії комбінаторної оптимізації побудовано математичні моделі. Показано, що в задачах цього класу комбінаторні конфігурації можуть бути як аргументом цільової функції, так і вхідними даними. Для некоторых задач искусственного интеллекта с использованием теории комбинаторной оптимизации построены математические модели. Показано, что в задачах этого класса комбинаторные конфигурации могут быть как аргументом целевой функции, так и входными данными. The problems of the artificial intelligence are difficult by nature and are not always amenable to formalization. A lot of the applied problems of this class are reduced to the problems of the combinatorial optimization. This is because their vast part requires sorting of variants. A combinatorial nature is the characteristic of the search problems. The design methods do not always explain the search nature of the artificial intelligence problems. The detailed analysis of the problems of this class shows that the argument for the objective function is the different types of the combinatorial configurations. The method of creating the artificial intelligence with the use of the combinatorial optimization theory is represented. An objective function and defined argument for the combinatorial configurations of different types are formulated. As the system analysis shows, in the problems of this class the combinatorial configurations can be the argument for the objective function and input data. The use of the combinatorial optimization theory allows to set the combinatorial nature, to formulate the objective function, to identify the characteristics signs, which establish the similarity of the artificial intelligence problems. The expounded researches allow the identification the uncertainty cause of different kinds, which arises up in the process of their decision, and explain the nature of the input data vagueness. 2017 Article Комбінаторика в задачах штучного інтелекту / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2017. — № 2. — С. 6-19, 37. — Бібліогр.: 10 назв. — укр. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/124958 519.14+519.168 uk Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science
spellingShingle	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science Тимофієва, Н.К. Гриценко, В.І. Комбінаторика в задачах штучного інтелекту Управляющие системы и машины
description	Для деяких задач штучного інтелекту з використанням теорії комбінаторної оптимізації побудовано математичні моделі. Показано, що в задачах цього класу комбінаторні конфігурації можуть бути як аргументом цільової функції, так і вхідними даними.
format	Article
author	Тимофієва, Н.К. Гриценко, В.І.
author_facet	Тимофієва, Н.К. Гриценко, В.І.
author_sort	Тимофієва, Н.К.
title	Комбінаторика в задачах штучного інтелекту
title_short	Комбінаторика в задачах штучного інтелекту
title_full	Комбінаторика в задачах штучного інтелекту
title_fullStr	Комбінаторика в задачах штучного інтелекту
title_full_unstemmed	Комбінаторика в задачах штучного інтелекту
title_sort	комбінаторика в задачах штучного інтелекту
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2017
topic_facet	Фундаментальные и прикладные проблемы Computer Science
url	http://dspace.nbuv.gov.ua/handle/123456789/124958
citation_txt	Комбінаторика в задачах штучного інтелекту / Н.К. Тимофієва, В.І. Гриценко // Управляющие системы и машины. — 2017. — № 2. — С. 6-19, 37. — Бібліогр.: 10 назв. — укр.
series	Управляющие системы и машины
work_keys_str_mv	AT timofíêvank kombínatorikavzadačahštučnogoíntelektu AT gricenkoví kombínatorikavzadačahštučnogoíntelektu
first_indexed	2025-07-09T02:19:00Z
last_indexed	2025-07-09T02:19:00Z
_version_	1837134032858513408
fulltext	6 УСиМ, 2017, № 2 Фундаментальные и прикладные проблемы Computer Science УДК 519.14+519.168 Н.К. Тимофієва, В.І. Гриценко Комбінаторика в задачах штучного інтелекту Для некоторых задач искусственного интеллекта с использованием теории комбинаторной оптимизации построены математи- ческие модели. Показано, что в задачах этого класса комбинаторные конфигурации могут быть как аргументом целевой функ- ции, так и входными данными. Ключевые слова: искусственный интеллект, неопределенность, комбинаторная конфигурация, комбинаторная оптимизация, целевая функция, подобие задач комбинаторной оптимизации. Для деяких задач штучного інтелекту з використанням теорії комбінаторної оптимізації побудовано математичні моделі. Показа- но, що в задачах цього класу комбінаторні конфігурації можуть бути як аргументом цільової функції, так і вхідними даними. Ключові слова: штучний інтелект, невизначеність, комбінаторна конфігурація, комбінаторна оптимізація, цільова функція, подібність задач комбінаторної оптимізації. Вступ. Штучний інтелект охоплює широкий клас складних завдань, моделювання і розв’я- зання яких досягається відомими математични- ми методами, застосуванням експертних систем, нейронних мереж та інших засобів, що функціо- нують на принципах навчання і самонавчання. Серед цих методів виділимо стохастичні, логіко- лінгвіністичні методи, моделі Маркова, лінійне цілочислове програмування, теорію розпізна- вання образів [1–4]. Досить інтенсивно для розв’язання задач оптимізації штучного інтелек- ту використовується метод розповсюдження об- межень [5], генетичні алгоритми та методи, які класифікують як евристичні. Під евристичними алгоритмами, як правило, розуміють способи прийняття рішень, подібні до того, як це робить людина, та побудовані на інтуїтивних міркуваннях, що спираються на попередній досвід. Вони належать до напряму, що ґрунтується на розпізнаванні структури вхідної інформації, в яких неявно моделюється функція зору людини. До них відносять підхо- ди, які складно формалізувати та неможливо довести їхню точність. Використання евристи- чних алгоритмів дуже поширене в задачах розпізнавання різної природи. Для багатьох практичних проблем ці алгоритми чи не єдино можливий шлях для отримання задовільного рішення в реальному часі. Іноді такий алго- ритм може бути точним, тобто він знаходить дійсно найкраще рішення, але його називають евристичним через неможливість довести їхню точність Ці методи ефективні за швидкодією, але досить часто результат, одержаний за їх використання, далекого від оптимального. Розглянемо спосіб моделювання приклад- них задач із штучного інтелекту (розпізнаван- ня мовленнєвих сигналів, клінічна діагности- ка) з застосуванням теорії комбінаторної оп- тимізації. Сформулюємо цільову функцію та визначимо її аргумент, яким є комбінаторні конфігурації різних типів [6]. Як показує сис- темний аналіз, в задачах штучного інтелекту комбінаторні конфігурації можуть бути як ар- гументом цільової функції, так і вхідними да- ними. Використання теорії комбінаторної оп- тимізації дозволяє встановити їхню комбінато- рну природу, сформулювати цільову функцію в явному вигляді, виявити характерні ознаки, за якими встановлюється подібність задач штучного інтелекту. Загальна математична постановка задачі комбінаторної оптимізації Задачі цього класу [6], як правило, задають- ся однією або кількома множинами, наприклад A та B , елементи яких мають будь-яку при- роду. Назвемо ці множини базовими. Наявні два типи задач. В першому типі кожну з цих УСиМ, 2017, № 2 7 множин подамо у вигляді графа, вершинами якого є її елементи, а кожному ребру постав- лено у відповідність число Rclt  , яке назива- ють вагою ребра ( R – множина дійсних чисел); {1,..., }l n , {1,..., }t n  , n – кількість елементів множини A , n~ – кількість елементів множини B . Приймемо, що nn ~ . Між елементами цих множин існують зв'язки, числове значення яких назвемо вагами. Величини ltc назвемо вхідни- ми даними та задамо їх матрицями. В другому типі задач між елементами заданої множини зв'язків не існує, а вагами є числа Rvj  , },...,1{ nj  , яким у відповідність поставлено деякі властивості цих елементів, числові зна- чення яких задаються скінченними послідов- ностями, що також є вхідними даними. Ці ве- личини визначають значення цільової функції. Для обох типів задач із елементів однієї або кількох заданих множин, наприклад Aal  , },...,1{ nl , утворюється комбінаторна множи- на W – сукупність комбінаторних конфігура- цій певного типу (перестановки, вибірки різ- них типів, розбиття тощо). На елементах w комбінаторної множини W вводиться цільова функція )(wF . Необхідно знайти елемент w множини W , для якого )(wF набуває екстре- мального значення при виконанні заданих обме- жень, тобто функціонал 0 ( ) glob extr ( ) w W W F w F w    , де max}{min,extr  , 0W – підмножина, яка визначається обмеженнями задачі. За способом обчислення цільової функції виділимо задачі, в яких для певного варіанту розв'язку її значення обчислюється одночасно. Такі задачі назвемо статичними. Задачі, в яких в процесі їх розв'язання генерується по- точна інформація, за якою оцінюється резуль- тат, а пошук оптимального розв'язку прово- диться поетапно з обчисленням часткових сум цільової функції, назвемо динамічними. Змоделюємо вхідні дані задачі комбінаторної оптимізації першого типу скінченними послі- довностями. Подамо елементи h наддіагона- лей симетричної комбінаторної матриці )( kwQ комбінаторною функцією 1( ( ) , )\|k mf j w  1( ( (1) , ) ,..., ( ( ) , ))k k mf w f m w   , а елеме- нти h наддіагоналей симетричної матриці C – функцією натурального аргументу 1( ) \|mj  ( (1), ..., ( ))m   , де 2 )1(   nnm – кількість елементів h наддіагоналей матриць C та )( kwQ , 1,1  nh . Верхній індекс k ( },...,1{ qk  ) в kw – порядковий номер kw в W , q – кількість kw у W . Якщо матриці )( kwQ та C – несимет- ричні, то 1( ( ), )\|k mf j w та mj 1\|)( містять усі їх- ні елементи, а 2m n (або nnm ~ ). Функція цілі )( kwF набуде вигляду )(),)(()( 1 jwjfwF k m j j k   . (1) Невизначеність у штучному інтелекті. Прийняття рішень в прикладних задачах, зок- рема в задачах штучного інтелекту, прово- диться за умов невизначеності різного виду. Тобто, розв’язання задач з урахуванням різно- го їх виду є загальним випадком, а прийняття рішень без їх врахування – частковим випад- ком. Як і в задачах комбінаторної оптимізації, так і в задачах штучного інтелекту невизначе- ність пов’язана:  з неоднозначністю результату, одержаного за змодельованою цільовою функцією або ви- браною мірою подібності у разі нечіткої вхід- ної інформації, який не задовольняє мету до- слідження;  з вибором способу оцінки точності роботи певного алгоритму;  з особливою структурою множини комбі- наторних конфігурацій, що є аргументом ці- льової функції;  з неповною вхідною та поточною інфор- мацією;  з нечітко розробленими правилами об- робки та оцінки інформації;  з неоднозначністю при виборі оптималь- ного розв’язку за кількома критеріями в бага- токритеріальній оптимізації. 8 УСиМ, 2017, № 2 Отже, однією із задач штучного інтелекту є ситуація невизначеності. При розв’язанні зна- чної частини задач різних класів основна увага приділяється невизначеності, пов’язаної з не- повною вхідною та поточною інформацією, а також з нечіткими вхідними даними. В такому разі вирішення цієї проблеми проводять шля- хом аналізу поведінки системи за певний про- міжок часу. На основі аналізу встановлюється певна закономірність, яка враховується при прогнозуванні майбутніх результатів на пото- чному відліку часу. Якщо вхідну інформацію можна задати часовими послідовностями і для неї визначити фрактальну розмірність, то ви- користовують фрактальний аналіз, зокрема ме- тод нормованого розмаху (метод R/S) [7, 8]. Також одним із способів вирішення цієї ситуа- ції є розроблення самоналагоджувальних алго- ритмів генерування параметрів, які необхідно задавати як вхідні дані для розв’язання черго- вої задачі і які неможливо задати на початку обчислювального процесу. Це дозволяє в про- цесі розв’язання певної задачі автоматично ге- нерувати додаткову поточну інформацію з урахуванням прогнозу результатів. Для моделювання прикладних задач в межах теорії комбінаторної оптимізації необхідно ви- значити:  вид задачі (статична чи динамічна) за спо- собом обчислення цільової функції;  базові множини, якими задається задача;  тип задачі за вхідними даними;  аргумент цільової функції (комбінаторну конфігурацію);  змоделювати цільову функцію. Аналіз задач із штучного інтелекту показує, що вони належать як до першого, так і до дру- гого типу. Аргументом цільової функції в них є комбінаторні конфігурації різних типів, зок- рема вибірки (сполучення та розміщення як з повтореннями, так і без них, розбиття n -еле- ментної множини на підмножини тощо). Задачі цього класу можуть бути як статичними, так і динамічними. Комбінаторною конфігурацією назвемо будь-яку сукупність елементів, яка утворюєть- ся з усіх або з деяких елементів заданої мно- жини },...,{ 1 naaA  [6]. Позначимо її упоряд- кованою множиною ),...,( 1 kkk kwww   . Множину },...,{ 1 naaA  назвемо базовою. Під символом Awk l  розуміємо як окремі елементи, так і під- множини (блоки), },...,1{ nk  – кількість еле- ментів у Wwk  . Залежно від умови задачі  позначатимемо без індексу або з верхнім інде- ксом k . Дві нетотожні комбінаторні конфігу- рації kw та iw назвемо ізоморфними, якщо ik  . В прикладних задачах обчислювального ін- телекту аргументом цільової функції є різні типи вибірок. З поняттям вибірки пов'язують як власне операцію виділення підмножин за- даної множини, так і її результат: вибрану під- множину. В подальшому маємо на увазі друге поняття. Нехай задано базову множину 1{ ,..., }nA a a . З неї одержимо  -вибірку. Число  називають об'ємом вибірки. В -вибірках в залежності від умови задачі або враховується порядок розта- шування в них елементів (тоді їх називають -перестановками або -розміщеннями) або ні. Тоді вони називаються -сполученнями. То ж існують такі типи вибірок: упорядко- вані та неупорядковані. Останні це – сполу- чення без повторень і сполучення з повторен- нями. Упорядковані це – розміщення з повто- реннями і без них. Множина будь-якого типу вибірок складається з підмножин ізоморфних вибірок. Далі показано, що в задачі розпізна- вання та синтезу мовленнєвих сигналів в зада- чі клінічної діагностики аргументом цільової функції є сполучення без повторень та розмі- щення з повтореннями. Закономірність зміни значень цільової фун- кції в задачах комбінаторної оптимізації зале- жить від упорядкування комбінаторних конфі- гурацій (аргументу) Ww . Розглянемо струк- туру їхньої множини W . Підмножину WW  назвемо підмножиною ізоморфних комбінато- УСиМ, 2017, № 2 9 рних конфігурацій, якщо її елементи є такими. Множина W складається з підмножин ізомор- фних комбінаторних конфігурацій W . На під- множині W цільова функція змінюється так, як і на множині перестановок. Можна довести, що на множині перестановок і на підмножині ізоморфних комбінаторних конфігурацій за ви- користання цільової функції (1) ситуація неви- значеності зводиться до мінімуму. Але на мно- жині W , яка складається з підмножин ,WW  для певного їх впорядкування закономірність зміни значень функції (1) однакова незалежно від вхідних даних, а розв’язок задачі – неодно- значний. Тобто, в цьому разі виникає ситуація невизначеності, пов’язана зі структурою аргу- менту цільової функції. Оскільки в задачах штучного інтелекту множина комбінаторних конфігурацій упорядковується підмножинами WW  , то знаходження для них оптимально- го розв’язку за виразом (1) або лінійною функ- цією проводиться за умов невизначеності, пов’язаною із структурою аргументу. Прикладні задачі штучного інтелекту, в яких цільова функція залежить від кількох змінних, за цією ознакою розділяються на не- залежні підзадачі, які належать різним класам. Для їх розв’язання розробляються алгоритми, які поєднують два або більше методів та ґрун- туються на організації покрокових обчислень – ітераційного процесу, що породжує послідов- ність розв’язків у відповідності з вбудованими процедурами. Якщо останні – незалежні алго- ритми, орієнтовані на розв’язання задач пев- них класів, то вони називаються гібридними. Розв’язок задачі визначається на множинах комбінаторних конфігурацій різних типів. В цьому разі суть гібридного алгоритму полягає у поєднанні методів пошуку оптимального розв’язку, дійсного для кожної з заданих ком- бінаторних множин. В таких задачах штучного інтелекту як роз- пізнавання мовленнєвих сигналів та задача клінічної діагностики цільова функція зале- жить від кількох змінних, якими є різні типи комбінаторних конфігурацій. Тому для розв’я- зання вони потребують розроблення гібридних алгоритмів. До того ж за цією ознакою встано- влюється подібність цих задач [9]. Подібність задач штучного інтелекту, у яких цільова функція залежить від кількох змінних. Побудовані математичні моделі задач розпізнавання мовленнєвих сигналів та клініч- ної діагностики з використанням теорії комбі- наторної оптимізації показують, що обидві розділяються на три підзадачі:  структуризація бібліотеки еталонів;  пошук у бібліотеці еталонної інформації;  задача порівняння еталонної та вхідної ін- формації. Для обох класів задач аргументом цільової функції в першій підзадачі є розбиття n -еле- ментної множини на підмножини, в другій – розміщення без повторень, а в третій – сполу- чення без повторень. Розглянемо ці задачі. Розпізнавання мовленнєвих сигналів. Ця за- дача полягає у пошуку для вхідного сигналу найбільш правдоподібного еталонного сигналу з усіх можливих [2]. Для розв’язання цієї зада- чі необхідно провести пошук певного еталону в бібліотеці та порівняти його з вхідним сигна- лом. Аргументом цільової функції в ній вва- жають вхідний сигнал [2]. Моделювання задачі розпізнавання мовленнєвих cигналів показує, що аргумент цільової функції в ній – це комбі- наторні конфігурації різних типів. Розглянемо задачу порівняння еталонного та вхідного сигналів. Уведемо дві базові множи- ни },...,{ 1 naaA  та },...,{ ~1 i n ii bbB  , де Aa s – значення сигналу у відліку s , ns ,1 , а ii l Bb  відповідає відліку еталонного сигналу, l  }~,...,1{ n , }~,...,1{ qi , q~ – кількість еталонних сигналів. Вхідні дані, якими є ваги між еле- ментами Aas  та ii l Bb  , задамо несиметрич- ною матрицею nxnlscC ~ , номера стовпців якої збігаються з нумерацією елементів Aas  , а номера рядків – з нумерацією елементів ii l Bb  . Оскільки з кожної базової множини A та iB вибираються по одному елементу в 10 УСиМ, 2017, № 2 строгому порядку, то отримана комбінаторна конфігурація є розміщенням без повторення. Позначимо його Mk  , де M – їхня всіляка множина. Для визначення елементів Aas  та ii l Bb  , що вибираються з базових множин на k-му варіанті розв'язання задачі, введемо ком- бінаторну (0,1)-матрицю nnx k sl k gQ ~)()(  . Якщо 1)( k slg , то з множин A та iB вибрано пару ),( i ls ba , в іншому разі значення 0)( k slg . Для запису цільової функції в явному вигляді змоделюємо вхідні дані функціями натураль- ного аргументу. Елементи матриці C подамо числовою функцією ,\|)( 1 mj а матриці )( kQ  – комбінаторною mkjf 1\|),)((  , де nnm ~ . Задача порівняння еталонного та вхідного мовленнєвих сигналів полягає в знаходженні такого розміщення без повторень k , для яко- го    m j k j M k jfjF k 1 )),(()(max)( , де    m j k j jfj 1 )),(()( – інтегральна міра по- дібності, а ),()( i lsj bauj  – елементарна міра подібності, яка визначає подібність між елеме- нтами еталонного та вхідного сигналів. В підзадачі пошуку в бібліотеці еталонного сигналу як ваги між еталонним та вхідним си- гналами виступають величини інтегральних мір подібності )( kF  , числове значення яких подамо матрицею 'C . Номера стовпців цієї ма- триці збігаються з номерами еталонних сигна- лів, розміщених у бібліотеці. Рядок у ній один і відповідає номеру 1 вхідного сигналу A . Ос- кільки при порівнянні вхідного та еталонного сигналів із множин A та B вибираються два елементи, то утворена комбінаторна конфігу- рація є сполученням без повторення, яке по- значимо як '' Mk  , де 'M – їхня всіляка множина, ),...,( 1 i q i BBB  – множина еталонних сигналів. Уведемо комбінаторну (0,1)-матрицю qx t l t gQ 1 ' 1 ' )()(  . Якщо 1)( ' 1  t lg , то з мно- жин A та B вибрано пару ),( i lBA , в іншому ра- зі значення 0)( ' 1  t lg . Елементи матриці 'C подамо числовою функцією ,\|)( 1 1 '  nj а мат- риці )( ' tQ  – комбінаторною 1 1 ''' \|),)((  ntjf . Задача пошуку еталонного сигналу, який відповідає вхідному, полягає у пошуку такого сполучення без повторення 't , для якого     1 1 ''''' )),(()(max)( ' n j t j M t jfjF t , де  )(' j    m j k j jfj 1 )),(()( . Задача клінічної діагностики. Побудуємо ма- тематичну модель задачі клінічної діагностики як задачу комбінаторної оптимізації [10]. По- значимо )~,...,~{~ 1 naaA  множину захворювань, описання яких знаходиться в бібліотеці (мно- жина еталонів), де елемент ,sa A  {1,..., }s n , відповідає певному захворюванню, якому по- ставлено у відповідність характерні ознаки ),...,,( )()( 2 )( 1 )( ' t q ttt t vvvV  , ' tq – кількість ознак t -го захворювання. Вхідною інформацією в задачі клінічної діагностики є множина ознак ,~(~ 1vV  )~,...,~ ~2 qvv , що описує одне або кілька захворю- вань. Позначимо їх }~,...,~{~ 1 nbbB  , де Bbd ~~  – захворювання, яке потрібно визначити, n – кількість можливих захворювань, а qqt ~'  або qqt ~'  . Ознаки Vvr ~~  вхідної інформації ма- ють ті ж значення, що і описані в еталоні озна- ки )()( tt l Vv  , }~,...,1{ qr , },...,1{ ' tql . Задача полягає у пошуку для B~ з множи- ною ознак V~ найбільш правдоподібного одно- го або кількох еталонів із множини A~ )~,...,~{ 1 naa , тобто за вхідними ознаками вста- новлюється одне або кілька захворювань Bbd ~~  . Ознаки в цій задачі слугують критеріями, за якими оцінюється її розв’язок. Як і в розпізна- ванні мовленнєвих сигналів, для розв’язання цієї задачі необхідно провести пошук певного УСиМ, 2017, № 2 11 еталону в бібліотеці і порівняти його з вхідни- ми ознаками. Розглянемо задачу порівняння ознак еталону ),...,,( )()( 2 )( 1 )( ' t q ttt t vvvV  , які визначають t -е за- хворювання, та вхідних ознак )~,...,~,~(~ ~21 qvvvV  , за якими необхідно встановити діагноз. Позна- чимо )~,( )(' r t sl vvu елементарну міру подібності між елементами множин V~ і )(tV . Вважатиме- мо, що міри подібності між елементами )()( tt s Vv  та Vvr ~~  є вхідними даними. Їхні чи- слові значення задамо скінченною послідовні- стю (комбінаторною функцією натурального аргументу, яка залежить від розміщення без повторень i ). Задача порівняння еталону та вхідних ознак полягає в пошуку такого розмі- щення без повторення ),...,( * 1 * ' i q ii  , для яко- го змодельовані цільові функції набувають ма- ксимального значення. В задачі перебору еталонів )~,...,~{~ 1 naaA  як ваги між елементами Aas ~~  та вхідними да- ними V~ виступають значення інтегральних мір подібності, одержаних за заданими цільо- вими функціями у порівнянні ознак еталону та вхідних ознак. Задача пошуку бібліотечного еталону, який відповідає вхідному, полягає у пошуку такого сполучення без повторення, для якого значення часткових критеріїв, за якими оцінюється ре- зультат розв’язку, були б найбільшими. Як видно з постановки задач розпізнавання мовленнєвих сигналів та клінічної діагностики пошук еталону, подібного до вхідних даних, потребує повного перебору. За великих об’ємів інформації в базі даних ця задача в реальному часі є нерозв’язною. Для зведення її до розв’язної необхідно структуризувати бібліо- теку еталонів за певними ознаками. Тобто, на етапі структуризації бібліотеки для обох випа- дків розв’язується задача кластеризації, аргу- ментом цільової функції в якій є розбиття n - елементної множини на підмножини. Отже, як задача клінічної діагностики, так і розпізнавання мовленнєвих сигналів розділя- ються на три підзадачі: структуризацію бібліо- теки еталонів, пошук у бібліотеці еталонної ін- формації; порівняння еталонної та вхідної ін- формації. Аргументом цільової функції в них є різні типи вибірок та розбиття n -елементної множини на підмножини. Тобто за аргументом цільової функції ці задачі – подібні. Комбінаторні конфігурації як вхідні дані в штучному інтелекті. Такі конфігурації в за- дачах розпізнавання виступають також і як вхідні дані. В цих задачах проводиться розпі- знавання сигналів різної природи (мовленнєві сигнали, електрокардіограми, електроенцефа- лограми), які слугують для них вхідними да- ними. Далі показано, як використовуються ком- бінаторні конфігурації для розв’язання деяких задач з обчислювального інтелекту. Використання мультимножин у багато- дикторному розпізнаванні мовленнєвих сигна- лів. Мовленнєвий сигнал під дією певних чин- ників утворюється різноманітними комбінаці- ями активних та пасивних органів творення мови. Мовленнєві сигнали, що відповідають одному і тому ж слову, але вимовлені різними дикторами, відрізняються як частотою, так і величиною амплітуди. Визначення подібності вхідного та еталонного сигналів у багатодик- торних системах проводиться багатьма спосо- бами, наприклад [2]. Для ефективного розпі- знавання таких сигналів їхню математичну модель необхідно побудувати так, щоб до неї зводилися усі можливі вимовлені варіанти пе- вного слова (виразу). Мовленнєвий сигнал мо- делюється вибіркою – розміщенням з повто- реннями з n елементів Aas  по  , в якій враховується порядок елементів, },...,1{, ns  . Сигнали, які відображають одне і те ж слово, повторене кілька разів одним і тим же дикто- ром або різними дикторами, відрізняються тим, що отримані комбінаторні конфігурації містять різні елементи мовленнєвого апарату та різну їх кількість. Звідси – нечіткість у вхід- них даних. 12 УСиМ, 2017, № 2 Мовленнєвий сигнал (розміщення з повто- реннями) подамо мультимножиною. Вона фо- рмально визначається як пара ),( mA , де :m A N функція з A в множину N натура- льних чисел, тобто кожному елементу множи- ни A відповідає певне натуральне число, яке називається кратністю цього елемента. Мов- леннєвий сигнал задамо послідовністю ),...,,(\| ~21 ~ 1 n n ffff  , де jf – значення амплітуди у відліку j сигналу. Проведемо його сегмен- тацію на майже періодичні та неперіодичні відрізки відомим або розробленим алгорит- мом. Поточний майже період розділимо на k відліків та опишемо мультимножиною, яку за- дамо основою ),\|( 1 mf k , де k – величина, яка визначається експериментально та однакова для будь-якого відрізку сигналу. В l -му відлі- ку має бути лише одне значення lf . Еталон, за яким установлюється подібність майже періо- ду, моделюється аналогічно. Подібність визна- чаємо за виразами  ' ll ff та ''  ll mm , де ' lf – значення сигналу еталона у відліку l , ' lm – кратність елемента ' lf ;  , ' – мінімальні величини, за якими встановлюється подібність вхідного та еталонного сигналів, визначаються експериментально. Синтез індивідуального мовлення з викори- станням фрагментів природної мови. Задача синтезу мовленнєвих сигналів полягає у їх від- творенні за заданим текстом. Як правило, для розв’язання цієї задачі створюється бібліотека фрагментів, утворених із природних мовленнє- вих сигналів, або такі фрагменти створюються штучно [2]. Ця задача з використанням певних правил розв’язується об'єднанням майже пері- одів або ділянок сигналу, вибраних із бібліоте- ки, у фонеми, що відповідають певним звукам (відповідно буквам заданого тексту). Аргумент цільової функції в цій задачі – розміщення з повтореннями. Множину бібліотечних елемен- тів (фрагментів) позначимо },...,{ 1 naaA  , де ja – елемент, що відповідає майже періоду або ділянці мовленнєвого сигналу. Подамо штуч- ний сигнал заданого слова (речення) розмі- щенням з повтореннями ),...,( 1 kkk  , де ),...,( 1 tjj k t aa  – фонема, а Aa jl  – j -й біб- ліотечний елемент фонеми. Природний мов- леннєвий сигнал заданого слова (речення) по- значимо розміщенням з повтореннями ),...,( * * 1 *  , де ),...,( ** 1 *   sss – фонема, а si – її елемент. Задача синтезу мовленнєвих сигналів поля- гає у пошуку такого розміщення з повторення- ми ),...,( ** 1 * kkk  , для якого одержаний штуч- ний мовленнєвий сигнал відповідав би природ- ному його звучанню. Цільова функція набуває вигляду * 1 ( ) max ( ) ( ( ), ), k n k k j M j F j f j         де      * '' 1 1 * ),()( s q i jsjij agj – інтегральна міра по- дібності, а ),( * jsjij ag  – елементарна міра по- дібності, яка визначає подібність між штучни- ми фонемами ),...,( 1 tjj k t aa  , утвореними з еле- ментів Aaj  , та природними ),...,( ** 1 *   sss заданого природного сигналу, ),min(''  tq . Значення 1),)((  k j jf , якщо фонема k t утворена з елемента Aa j  , та 0),)((  k j jf в іншому випадку. Граматичні правила у синтезі мовленнєвих сигналів можна розглядати як міри подібності. Оскільки вони розроблені ґрунтовно, то за від- сутності умови відтворення індивідуальності голосу ця задача є розв’язною. Жіночий, чоло- вічий або дитячий голос залежить від частоти основного тону, амплітуди сигналу, тому ця задача є також розв’язною. Відтворення інди- відуального мовлення залежить від набагато складніших чинників: від мовленнєвого апара- ту індивідууму, від його емоційного стану, від особливості його психіки тощо. Оскільки ці параметри змоделювати досить складно, то по- ставлена задача не є розв’язною. Існуючі син- тезатори характеризуються досить високою натуральністю звучання, але не відтворюють УСиМ, 2017, № 2 13 особливості мовлення індивідууму. Експери- менти, проведені з використанням розроблено- го комплексу програм синтезу мовленнєвих сигналів з фрагментів природної мови показа- ли, що індивідуальність мовлення зберігається у майже періоді, відповідному основному тону tf та дифонах kf ~ , виділених з природного си- гналу. Але, якщо згенерувати сигнал з природ- них майже періодів так, що значення їхніх ам- плітуд iA та довжин tD (в дискретах) – одна- кові для усіх майже періодів, то голос звучить одноманітно, з металевим відтінком без будь- яких емоцій. Для природного звучання зі збе- реженням індивідуальності мовлення та емо- ційності необхідно, крім наявності природних майже періодів та дифонів, точно відтворити характерні параметри індивідууму: значення амплітуди сигналу, довжину майже періоду (на початку, посередині, в кінці сигналу, під наго- лосом), мінімальну кількість майже періодів K, при яких відтворюється певна фонема тощо. Експеримент показав, що навіть при виконанні оговорених умов, згенерований штучний мов- леннєвий сигнал набуває індивідуального зву- чання. Отже, відтворення індивідуального мо- влення характеризується такими параметрами: , , , ,i t t kA D K f f    . Математичний аналіз електрокардіограм з використанням комбінаторних конфігурацій. Електрокардіограма описується розміщенням з повтореннями. За допомогою розробленої про- грами проведемо сегментацію сигналу з метою встановлення частоти скорочень серця, трива- лості періоду систоли та діастоли, значень ам- плітуд зубців UTSRQP ,,,,, . Сегментація електрокардіограм проводиться кількома іте- раціями, що дозволяє досягати високої точнос- ті розв'язку задачі за невеликих затрат машин- ного часу. В результаті, по виділених майже періодичних ділянках електрокардіограми ви- значається довжина поточного майже періоду, що відповідає сумарній тривалості систоли та діастоли, та частота скорочень серця. Розроб- леними процедурами поточний майже період розбивається на два відрізки, один з яких від- повідає паузі (діастолі), а другий – систолі та містить зубці. У другому відрізку виділяються інтервали, в кожному з яких за значеннями си- гналу відтворюється унімодальна функція (вгну- та або опукла). Послідовністю фрагментів цих функцій визначаються зубці UTSRQP ,,,,, . За найбільшими та найменшими їх значеннями відшукуються величини інтервалів (тривалість періодів QP  , RQ  , SR  , TS  , UT  ). Відповідно визначається тривалість як систо- ли, так і діастоли. Отже, з викладеного випливає, що комбі- наторні конфігурації можуть також бути вхід- ними даними в задачах штучного інтелекту. Висновок. Комбінаторні підходи отрима- ють подальший розвиток у розв’язанні задач штучного інтелекту, як показало моделювання цих задач. В межах теорії комбінаторної опти- мізації можна виявити їхню комбінаторну при- роду, визначити аргумент цільової функції, яким є комбінаторні конфігурації різних типів. Ці дослідження дозволяють виявити причину невизначеності різних видів, яка виникає в процесі їх розв’язання, та пояснити природу нечіткості вхідних даних. В задачах цього кла- су комбінаторі конфігурації можуть бути як аргументом цільової функції, так і вхідними даними. За аргументом цільової функції вони розділяються на підзадачі, для розв’язання яких необхідно розробляти гібридні алгорит- ми. На прикладі задачі розпізнавання мовлен- нєвих сигналів та задачі клінічної діагностики описано спосіб визначення певних ознак, за якими встановлюється подібність задач з об- числювального інтелекту. 1. Шлезингер М., Главач В. Десять лекций по ста- тистическому и структурному распознаванию. – К.: Наук. думка, 2004, 546 с. 2. Винцюк Т.К. Анализ, распознавание и интерпрета- ция речевых сигналов. – Киев: Наук. думка, 1987, 262 с. 3. Файнзильберг Л.С. Математические методы оценки полезности диагностических признаков. – К.: Ос- віта України, 2010, 152 с. 4. Гупал А.М., Сергиенко И.В. Симметрия в ДНК. Ме- тоды распознавания дискретных последовательно- стей. – К.: Наук. думка, 2016, 227 с. 14 УСиМ, 2017, № 2 5. Квєтний Р.Н., Бісікало О.В., Назаров І.О. Визна- чення сенсу текстової інформації на основі моделі розповсюдження обмежень // Інформаційно-вимі- рювальні та обчислювальні системи і комплекси в технологічних процесах – 2012, № 1, С. 93–96. 6. Тимофієва Н.К. Теоретико-числові методи розв'я- зання задач комбінаторної оптимізації. Автореф. дис... докт. техн. наук / Ін-т кібернетики ім. В.М. Глушкова НАН України, Київ. – 2007, 32 с. 7. Савченко I.О. Фрактальний аналiз множин непов- них сум числових рядів: Автореф. дис... канд. фіз.- мат. наук / Iнститут математики НАН України, Ки- їв, 2016, 20 с. 8. Петерс Э. Фрактальный анализ финансовых рын- ков: приложение теории хаоса в инвестициях и экономике. – М.: Интернет-трейдинг, 2004, 304 с. 9. Тимофієва Н.К. Про подібність задач комбінатор- ної оптимізації та універсальність алгоритмів // Си- стемні дослідження та інформаційні технології, 2013, № 4, С. 27–37. 10. Тимофієва Н.К., Гриценко В.І. Аргумент цільової функції в задачі клінічної діагностики // УСиМ, 2012, № 3, С. 3–14. Поступила 09.03.2017 Тел. для справок: +38 044 502-6365 (Киев) E-mail: tymnad@gmail.com © Н.К. Тимофеева, В.И. Гриценко, 2017 Н.К. Тимофеева, В.И. Гриценко. Комбинаторика в задачах искусственного интеллекта Введение. Искусственный интеллект объединяет широ- кий класс сложных задач, моделирование и решение которых достигается известными математическими ме- тодами, применением экспертных систем, нейронных сетей и других средств, функционирующих на принци- пах обучения и самообучения. Среди этих методов вы- делим стохастические и логико-лингвинистические, моде- ли Маркова, линейное целочисленное программирова- ние, теорию распознавания образов [1–4]. Достаточно интенсивно для решения задач оптимизации искусст- венного интеллекта используются: метод распростране- ния ограничений [5], генетические алгоритмы и методы, классифицируемые как эвристические. Под эвристическими алгоритмами, как правило, по- нимают способы принятия решений так, как это делает человек, и построенные на интуитивных рассуждениях, которые опираются на предыдущий опыт. Они относят- ся к направлению, основанному на распознавании структуры входной информации, в котором неявно мо- делируется функция зрения человека. К ним относят сложно формализируемые подходы при невозможности доказательства их точности. Использование эвристиче- ских алгоритмов – достаточно распространенный под- ход в задачах распознавания разной природы. Для мно- гих практических проблем эти алгоритмы – единствен- ный путь получения приемлемого решения в реальном времени. Иногда такой алгоритм может быть точным, т.е. он находит действительно наилучшее решение, но его называют эвристическим из-за невозможности дока- зать их точность Эти методы эффективны по быстро- действию, но достаточно часто результат, полученный при их применении, далек от оптимального. Рассмотрим моделирование некоторых прикладных задач искусственного интеллекта (распознавание рече- вых сигналов, клиническая диагностика) с использова- нием теории комбинаторной оптимизации. Сформули- руем целевую функцию и определим ее аргумент, кото- рым являются комбинаторные конфигурации разных типов [6]. Как показывает системный анализ, в задачах этого класса комбинаторные конфигурации могут быть как аргументом целевой функции, так и входными дан- ными. Использование теории комбинаторной оптимиза- ции позволяет установить их комбинаторную природу, сформулировать целевую функцию в явном виде, обна- ружить характерные признаки, по которым устанавли- вается подобие задач искусственного интеллекта. Общая математическая постановка задачи ком- бинаторной оптимизации Задачи этого класса [6], как правило, задаются одним или несколькими множествами, например A и B, эле- менты которых имеют любую природу. Назовем эти множества базовыми. Имеется два типа задач. В первом типе каждое из этих множеств представим в виде графа, вершины которого – его элементы, а каждому ребру поставлено в соответствие число ltc R , которое назо- вем весом ребра (R – множество вещественных чисел); {1,..., }l n , {1,..., }t n  , n – количество элементов мно- жества A, n – количество элементов множества B. По- ложим, что n n  . Между элементами этих множеств существуют связи, числовое значение которых назовем весами. Величины ltc назовем входными данными и за- дадим их матрицами. Во втором типе задач между эле- ментами заданного множества связей не существует, а весами являются числа jv R , {1,..., }j n , которым в соответствие поставлены некоторые свойства этих эле- ментов, числовые значения которых задаются конечны- ми последовательностями, которые также являются УСиМ, 2017, № 2 15 входными данными. Эти величины определяют значе- ние целевой функции. Для обоих типов задач из элементов одного или не- скольких заданных множеств, например la A , {1,...l ..., }n , образуется комбинаторное множество W – сово- купность комбинаторных конфигураций определенного типа (перестановки, выборки разных типов, разбиения и др.). На элементах w комбинаторного множества W вводится целевая функция ( )F w . Необходимо найти элемент w множества W, для которого ( )F w принима- ет экстремальное значение при выполнении заданных ограничений, т.е. функционал 0 ( ) glob extr ( ) w W W F w F w    , где extr {min, max} , 0W – подмножество, определяе- мое ограничениями задачи. По способу вычисления целевой функции выделим задачи, в которых для определенного варианта решения ее значение вычисляется одновременно. Такие задачи назовем статическими. Задачи, в которых в процессе их решения генерируется текущая информация, по ко- торой оценивается результат, а поиск оптимального ре- шения проводится поэтапно с вычислением частичных сумм целевой функции, назовем динамическими. Смоделируем входные данные задачи комбинатор- ной оптимизации первого типа конечными последова- тельностями. Представим элементы h наддиагоналей сим- метричной комбинаторной матрицы ( )kQ w комбинатор- ной функцией 1 1( ( ), )\| ( ( (1), ),..., ( ( ), ))k m k k mf j w f w f m w    , а элементы h наддиагоналей симметричной матрицы C – функцией натурального аргумента 1( )\| ( (1),..., ( ))mj m    , где ( 1) 2 n nm   – количество элементов h наддиаго- налей матриц C и ( )kQ w 1, 1h n  . Верхний индекс k ( {1,..., }k q ) в kw – порядковый номер kw в W, q – количество kw в W. Если матрицы ( )kQ w и C – несим- метричны, то 1( ( ) , )\|k mf j w и 1( ) \|mj содержат все их элементы, а 2m n (или m n n  ). Функция цели ( )kF w принимает вид 1 ( ) ( ( ) , ) ( ) m k k j j F w f j w j     . (1) Неопределенность в искусственном интеллекте. Принятие решений в прикладных задачах проводится в условиях неопределенности разного вида, т.е. решение задач с учетом разного их вида является общим случаем, а принятие решения без их учета – частичным. Как и в задачах комбинаторной оптимизации, так и в задачах искусственного интеллекта неопределенность связана:  с неоднозначностью результата, полученного по смоделированной целевой функции или выбранной ме- рой подобия в случае нечеткой входной информации, который не удовлетворяет цели исследования;  с выбором способа оценки точности работы опре- деленного алгоритма;  с особенной структурой множества комбинаторных конфигураций, которые являются аргументом целевой функции;  с неполной входной и текущей информацией;  с нечетко разработанными правилами обработки и оценки информации;  с неоднозначностью при выборе оптимального ре- шения по нескольким критериями в многокритериаль- ной оптимизации. Следовательно, одной из задач искусственного ин- теллекта есть ситуация неопределенности. При решении значительной части задач разных классов основное внимание уделяется неопределенности, связанной с не- полной входной и текущей информацией, а также с не- четкими входными данными. В этом случае решают проблему путем анализа поведения системы за некото- рый промежуток времени. На основе этого анализа ус- танавливается определенная закономерность, которая учитывается при прогнозировании результатов на теку- щем промежутке времени. Если входную информацию можно задать часовыми последовательностями и для нее определить фрактальную размерность, то использу- ют фрактальный анализ, в частности метод нормируе- мого размаха (метод R/S) [7, 8]. Одним из способов ре- шения этой ситуации также является разработка само- настраивающихся алгоритмов генерирования парамет- ров, которые необходимо задавать как входные данные для решения следующей задачи и которые невозможно задать в начале вычислительного процесса. Это позво- ляет при решении конкретной задачи генерировать до- полнительную текущую информацию с учетом прогноза будущих результатов. Для моделирования прикладных задач в рамках тео- рии комбинаторной оптимизации необходимо опреде- лить:  вид задачи (статическая или динамическая) по спо- собу вычисления целевой функции;  базовые множества, которыми задается определен- ная задача;  тип задачи по входным данным;  аргумент целевой функции (комбинаторную кон- фигурацию);  смоделировать целевую функцию. Анализ задач искусственного интеллекта показывает, что они относятся как к первому, так и ко второму типу. Аргументом целевой функции в них выступают комби- наторные конфигурации разных типов, в частности вы- борки (соединения и размещения как с повторениями, так и без них), разбиение n-элементного множества на подмножества и пр. Задачи этого класса могут быть ста- тическими и динамическими. 16 УСиМ, 2017, № 2 Комбинаторной конфигурацией назовем любую со- вокупность элементов, которая образуется из всех или из некоторых элементов заданного множества 1{ ,..., }nA a a [6]. Обозначим ее упорядоченным мно- жеством 1( ,..., )k k k kw w w   . Множество 1{ ,..., }nA a a назовем базовым. Под символом k lw A понимаем как отдельные элементы, так и подмножества (блоки), {1,..., }k n  – количество элементов в kw W . В зави- симости от условия задачи  будем обозначать без ин- декса или с верхним индексом k . Две нетождествен- ных комбинаторных конфигурации kw и iw назовем изоморфными, если k i   . В прикладных задачах вычислительного интеллекта аргументом целевой функции выступают разные типы выборок. С понятием выборки связывают как собствен- но операцию выделения подмножеств заданного множе- ства, так и ее результат – выбранное подмножество. В дальнейшем подразумеваем второе понятие. Пусть задано базовое множество 1{ ,..., }nA a a . Из него получим  -выборку. Число  называют объемом выборки. В  -выборках в зависимости от условия зада- чи или учитывается порядок расположения в них эле- ментов (тогда их называют  -перестановками или  -раз- мещениями), или нет. В этом случае они называются  -со- четаниями. Следовательно, существуют такие типы выборок: упорядоченные и неупорядоченные. Последние это – сочетание без повторений и с повторениями. Упорядо- ченные это – размещение с повторениями и размещение без них. Множество любого типа выборок состоит из подмножеств изоморфных выборок. Далее показано, что в задаче распознавания и синтеза речевых сигналов, в задаче клинической диагностики аргументом целевой функции является сочетание без повторений и размеще- ние с повторениями. Закономерность изменения значений целевой функ- ции в задачах комбинаторной оптимизации зависит от упорядочения комбинаторных конфигураций (аргумен- та) w W . Рассмотрим структуру их множества W. Подмножество W W  назовем подмножеством изо- морфных комбинаторных конфигураций, если ее эле- менты – являются таковыми. Множество W состоит из подмножеств изоморфных комбинаторных конфигура- ций W . На подмножестве W целевая функция изме- няется так, как и на множестве перестановок. Можно доказать, что на множестве перестановок и на подмно- жестве изоморфных комбинаторных конфигураций при использовании целевой функции (1) ситуация неопреде- ленности сводится к минимуму. Но на множестве, со- стоящем из подмножеств, для определенного их упоря- дочения закономерность изменения значений функции (1) одинакова независимо от входных данных, а резуль- тат решения задачи – неоднозначен, т.е. возникает си- туация неопределенности, связанная со структурой ар- гумента целевой функции. Поскольку в задачах искусст- венного интеллекта множество комбинаторных конфигу- раций упорядочивается подмножествами W W  , то поиск для них оптимального решения по выражению (1) или линейной функцией проводится в условиях неопре- деленности, связанной со структурой аргумента. Прикладные задачи искусственного интеллекта, в которых целевая функция зависит от нескольких пере- менных, по этому признаку разделяются на независи- мые подзадачи, принадлежащие разным классам. Для их решения разрабатываются алгоритмы, совмещающие два или более методов и основаны на организации по- шаговых вычислений – итерационного процесса, кото- рый порождает последовательность решений в соответ- ствии со встроенными процедурами. Если встроенные процедуры – независимые алгоритмы, ориентированные на решение задач определенных классов, то они назы- ваются гибридными. Решение задачи определяется на множествах комбинаторных конфигураций разных ти- пов. В этом случае суть гибридного алгоритма заключа- ется в сочетании таких методов для поиска оптимально- го решения, которое было бы действительным для каж- дого из заданных комбинаторных множеств. В таких задачах искусственного интеллекта как рас- познавание речевых сигналов и задачи клинической диаг- ностики целевая функция зависит от нескольких перемен- ных, которыми являются разные типы комбинаторных конфигураций. Поэтому для их решения требуются раз- работки гибридных алгоритмов. По этому признаку ус- танавливается и подобие этих задач [9]. Подобие задач искусственного интеллекта, в ко- торых целевая функция зависит от нескольких пере- менных. Построенные математические модели задач рас- познавания речевых сигналов и клинической диагности- ки с использованием теории комбинаторной оптимиза- ции показывают, что они разделяются на три подзадачи:  структуризация библиотеки эталонов;  поиск в библиотеке эталонной информации;  задача сравнения эталонной и входной информа- ции. Для обоих классов задач аргументом целевой функ- ции в первой подзадаче является разбиение n -элемент- ного множества на подмножества, во второй подзадаче – размещение без повторений, а в третьей – сочетание без повторений. Рассмотрим эти задачи. Распознавание речевых сигналов. Задача распозна- вания речевых сигналов заключается в поиске для вход- ного сигнала наиболее правдоподобного эталонного из всех возможных эталонных сигналов [2]. Для решения этой задачи необходимо провести поиск определенного эталона в библиотеке и сравнить его со входным сигна- лом. Аргументом целевой функции в ней принимают входной сигнал [2]. Моделирование задачи распознава- УСиМ, 2017, № 2 17 ния речевых сигналов показывает, что аргументом целе- вой функции в ней есть комбинаторные конфигурации разных типов. Рассмотрим задачу сравнения эталонного и входного сигналов. Введем два базовых множества 1{ ,..., }nA a a и 1{ ,..., }i i i nB b b  , где sa A – значение сигнала в отсче- те s , 1,s n , а i i lb B соответствует отсчету эталонно- го сигнала, {1,..., }l n  , {1,..., }i q  , q – количество эта- лонных сигналов. Входные данные, которыми служат весы между элементами sa A и i i lb B , зададим не- симметричной матрицей s l n x n C c  , номера столбцов которой совпадают с нумерацией элементов sa A , а номера строк – с нумерацией элементов i i lb B . По- скольку из каждого базового множества A и iB выби- рается по одному элементу в строгом порядке, то полу- ченная комбинаторная конфигурация есть размещение без повторения. Обозначим его k M  , где M – их все- возможное множество. Для определения элементов sa A и i i lb B , которые выбираются из базовых множеств на k-м варианте решения задачи, введем ком- бинаторную (0,1)-матрицу ( ) ( )k k sl nx n Q g    . Если ( ) 1k slg   , то из множеств A и iB выбрана пара ( , )i s la b , в противном случае значение ( ) 0k slg   . Для записи целевой функции в явном виде смоделируем входные данные функциями натурального аргумента. Элементы матрицы C представим числовой функцией 1( ) \|mj , а матрицы ( )kQ  – комбинаторной 1( ( ) , )\|k mf j  , где m n n  . Задача сравнения эталонного и входного речевых сигналов заключается в нахождении такого размещения без повторений k , для которого 1 ( ) max ( ) ( ( ), ), k m k k j M j F j f j         где 1 ( ) ( ( ), ) m k j j j f j     – интегральная мера сходства, а ( ) ( , )i j s lj u a b  – элементарная мера сходства, опреде- ляющая сходство между элементами эталонного и вход- ного сигналов. В подзадаче поиска в библиотеке эталонного сигнала в качестве весов между эталонным и входным сигнала- ми выступают значения интегральных мер сходства ( )kF  , числовое значение которых представим матри- цей 'C . Номера столбцов этой матрицы совпадают с номерами эталонных сигналов, размещенных в библио- теке. Строка в ней одна и соответствует номеру 1 вход- ного сигнала A. Поскольку при сравнении входного и эталонного сигналов из множеств A и B выбираются два элемента, то образованная комбинаторная конфигура- ция является сочетанием без повторений, которое обо- значим как ' 'k M  , где 'M – их всевозможное множе- ство 1( ,..., )i i qB B B – множество эталонных сигналов. Вве- дем комбинаторную (0,1)-матрицу ' ' 1 1 ( ) ( )t t l x q Q g   . Если ' 1 ( ) 1t lg   , то из множеств A и B выбрана пара ( , )i lA B , в противном случае значение ' 1 ( ) 0t lg   . Эле- менты матрицы 'C представим числовой функцией ' 1 1( ) \|nj  , а матрицы '( )tQ  – комбинаторной ' ' ' 1 1( ( ) , )\|t nf j   . Задача поиска эталонного сигнала, соответствующе- го входному, заключается в нахождении такого сочета- ния без повторений ' t , для которого ' 1 ' * ' ' ' ' 1 ( ) max ( ) ( ( ), ) t n t t j M j F j f j          , где ' 1 ( ) ( ) ( ( ), ) m k j j j j f j       . Задача клинической диагностики. Построим мате- матическую модель задачи клинической диагностики как задачу комбинаторной оптимизации [10]. Обозна- чим 1{ ,..., ) n A a a   множество заболеваний, описание которых находится в библиотеке (множество эталонов), где элемент , {1,..., }sa A s n  , соответствует опреде- ленному заболеванию, которому поставлены в соответ- ствие характерные признаки ' ( ) ( ) ( ) ( ) 1 2( , ,..., ) t t t t t q V v v v , ' tq – количество признаков t-го заболевания. Входной ин- формацией в задаче клинической диагностики является множество признаков 1 2( , ,..., )qV v v v     , описывающее одно или несколько заболеваний. Обозначим их 1{ ,..., } n B b b   , где db B  – заболевание, которое необ- ходимо определить, n – количество возможных забо- леваний, а ' tq q или ' tq q . Признаки rv V  вход- ной информации имеют те же значения, что и описан- ные в эталоне признаки ( ) ( )t t lv V , {1,..., }r q  , '{1,..., }tl q . Задача заключается в поиске для B с множеством при- знаков V наиболее правдоподобного одного или несколь- ких эталонов из множества 1{ ,..., )nA a a   , т.е. по входным признакам устанавливается одно или несколько заболева- ний db B  . Признаки в этой задаче служат критериями, по которым оценивается ее решение. Как и в распознава- нии речевых сигналов, для решения этой задачи необхо- димо провести поиск определенного эталона в библиотеке и сравнить его со входными признаками. 18 УСиМ, 2017, № 2 Рассмотрим задачу сравнения признаков эталона ' ( ) ( ) ( ) ( ) 1 2( , ,..., ) t t t t t q V v v v , которые определяют t-е заболе- вание, и входных признаков 1 2( , ,..., )qV v v v      , по кото- рым необходимо установить диагноз. Обозначим ' ( )( , )t l s ru v v элементарную меру сходства между элемен- тами множеств V и ( )tV . Положим, что меры сходства между элементами ( ) ( )t t sv V и rv V  – входные дан- ные. Их числовые значения зададим конечной последо- вательностью (комбинаторной функцией натурального аргумента, зависящей от размещения без повторений i ). Задача сравнения эталона и входных признаков за- ключается в поиске такого размещения без повторения ' * * * 1( ,..., )i i i q     , для которого смоделированные целе- вые функции принимают максимальное значение. В задаче перебора эталонов 1{ ,..., ) n A a a   в качестве весов между элементами sa A  и входными данными V выступают значения интегральных мер сходства, полученные по заданным целевым функциям при срав- нении признаков эталона и входных признаков. Задача поиска библиотечного эталона, соответству- ющего входному, заключается в поиске такого сочета- ния без повторений, для которого значения частичных критериев, оценивающим результат решения, были бы наибольшими. Как видно из постановки задач распознавания рече- вых сигналов и клинической диагностики, поиск этало- на, подобного входным данным, нуждается в полном переборе. При больших объемах информации в базе данных эта задача в реальном времени – неразрешима. Для сведения ее к разрешимой необходимо структури- ровать библиотеку эталонов по определенным призна- кам, т.е. на этапе структуризации библиотеки для обоих случаев решается задача кластеризации, аргумент целе- вой функции в которой – разбиение n -элементного множества на подмножества. Итак, задача клинической диагностики и распозна- вание речевых сигналов разделяются на три подзадачи: структуризация библиотеки эталонов, поиск в библио- теке эталонной информации; сравнение эталонной и входной информации. Аргументом целевой функции в них есть разные типы выборок и разбиение n-элемент- ого множества на подмножества, т.е., по аргументу це- левой функции эти задачи – подобны. Комбинаторные конфигурации как входные дан- ные в вычислительном интеллекте. В задачах распо- знавания такие конфигурации выступают и как входные данные. В этих задачах проводится распознавание сиг- налов разной природы (речевые сигналы, электрокар- диограммы, электроэнцефалограммы), которые для них являются входными данными. Далее показано, как ис- пользуются комбинаторные конфигурации для решения некоторых задач искусственного интеллекта. Использование мультимножеств в многодиктор- ном распознавании речевых сигналов. Речевой сигнал под действием определенных факторов образуется раз- нообразными комбинациями активных и пассивных ор- ганов речевого аппарата. Речевые сигналы, соответству- ющие одному и тому же слову, произнесенные разными дикторами, отличаются как частотой, так и амплитудой. Определение подобия входного и эталонного сигналов в многодикторных системах проводится многими спосо- бами, например [2]. Для эффективного распознавания таких сигналов их математическую модель необходимо построить так, чтобы к ней сводились все возможные произнесенные варианты определенного слова (выраже- ния). Речевой сигнал моделируется выборкой – разме- щением с повторениями из n элементов as  A по  , в которой учитывается порядок элементов , {1,..., }s n . Сигналы, отражающие одно и то же слово, повторенное несколько раз одним и тем же диктором или разными дикторами, отличается тем, что полученные комбина- торные конфигурации содержат разные элементы рече- вого аппарата и разное их количество. Отсюда – нечет- кость во входных данных. Речевой сигнал (размещение с повторениями) пред- ставим мультимножеством. Оно формально определяется как пара ( , )A m где m:A N функция из A во множе- ство N натуральных чисел, т.е. каждому элементу мно- жества A соответствует определенное натуральное чис- ло, называемое кратностью этого элемента. Речевой сигнал зададим последовательностью 1 1 2\| ( , ,..., ),n nf f f f  где jf – значение амплитуды в отсчете j сигнала. Про- ведем его сегментацию на почти периодические и непе- риодические отрезки известным или разработанным алгоритмом. Текущий почти период разделим на k от- резков и опишем мультимножеством, заданным основой 1( \| , )kf m , где k – величина, определяемая эксперимен- тально и одинакова для любого отрезка сигнала. В l-м отсчете должно быть лишь одно значение lf . Эталон, по которому устанавливается подобие почти периода, мо- делируется аналогично. Подобие определяем по выра- жению ' l lf f   и ' ' l lm m   , где ' lf – значение сигнала эталона в отсчете l, ' lm – кратность элемента ' lf ;  , ' – минимальные величины, по которым уста- навливается подобие входного и эталонного сигналов, определяются экспериментально. Синтез индивидуальной речи с использованием фраг- ментов естественного языка. Задача синтеза речевых сигналов заключается в их воспроизведении по задан- ному тексту. Как правило, для решения этой задачи соз- дается библиотека фрагментов, образованная из естест- венных речевых сигналов, или такие фрагменты созда- ются искусственно [2]. Эта задача с использованием определенных правил решается объединением почти УСиМ, 2017, № 2 19 периодов или участков сигнала, выбранных из библио- теки, в фонемы, соответствующие конкретным звукам (соответственно буквам заданного текста). Аргумент це- левой функции в этой задаче – размещение с повторе- ниями. Множество библиотечных элементов (фрагмен- тов) обозначим 1{ ,..., }nA a a , где ja – элемент, соответ- ствующий почти периоду или участку речевого сигнала. Представим искусственный сигнал заданного слова (пред- ложения) размещением с повторениями 1( ,..., )k k k     , где 1( ,..., ) t k t j ja a   – фонема, а jla A – j-й библио- течный элемент фонемы. Естественный речевой сигнал заданного слова (предложения) обозначим размещением с повторениями * * 1 ( ,..., )    , где * * * 1( ,..., )s s s     – фонема, а * si – ее элемент. Задача синтеза речевых сигналов заключается в по- иске такого размещения с повторениями * * * 1( ,..., ),k k k     для которого полученный искусственный речевой сиг- нал соответствовал бы естественному его звучанию. Целевая функция принимает вид * 1 ( ) max ( ) ( ( ), ) k n k k j M j F j f j         , где ''* * 1 1 ( ) ( , ) q j ji js s i j g a       – интегральная мера сход- ства, а ( , )j ji jsg a  – элементарная мера сходства, опре- деляющая подобие между искусственными фонемами 1( ,..., ) t k t j ja a   , образованными из элементов ja A , и естественными * * * 1( ,..., )s s s     заданного естествен- ного сигнала, '' min( , *)tq    . Значение ( ( ) , ) 1k j f j   , если фонема k t образована из элемента ja A , и ( ( ) , ) 0k j f j   в другом случае. Грамматические правила в синтезе речевых сигналов можно рассматривать как меры сходства. Поскольку они разработаны основательно, то в отсутствие условия вос- произведения индивидуальности голоса эта задача – разрешима. Женский, мужской или детский голоса зави- сят от частоты основного тона и амплитуды сигнала, поэтому задача также разрешима. Воспроизведение ин- дивидуальной речи зависит от намного более сложных факторов: от речевого аппарата индивидуума, от его эмоционального состояния, особенности психики и др. Поскольку эти параметры смоделировать сложно, то поставленная задача неразрешима. Существующие син- тезаторы характеризуются достаточно высокой нату- ральностью звучания, но не воспроизводят особенности речи индивидуума. Эксперименты, проведенные по- средством разработанного комплекса программ синтеза речевых сигналов из фрагментов естественного языка, показал, что индивидуальность речи сохраняется в поч- ти периоде, соответствующем основному тону tf , и ди- фонах kf , выделенных из естественного сигнала. Но, если сгенерировать сигнал из естественных почти периодов так, что значение их амплитуд iA и длин tD (в дискретах) – одинаковы для всех почти периодов, то голос звучит одно- образно, с металлическим оттенком без эмоций. Для есте- ственного звучания с сохранением индивидуальности речи и эмоциональности необходимо, кроме наличия естествен- ных почти периодов и дифонов, точно воспроизвести ха- рактерные параметры индивидуума: значение амплитуды сигнала, длину почти периода (в начале, посредине, в кон- це сигнала, под ударением), минимальное количество поч- ти периодов K, при которых воспроизводится определен- ная фонема. Эксперимент показал, что даже при выполне- нии оговоренных условий, сгенерированный искусствен- ный речевой сигнал принимает индивидуальное звучание. Следовательно, воспроизведение индивидуальной речи ха- рактеризуется такими параметрами: , , , , .i t t kA D K f f  Математический анализ электрокардиограмм с использованием комбинаторных конфигураций. Элек- трокардиограмма описывается размещением с повторе- ниями. Используя разработанную программу, проведем сегментацию сигнала с целью установления частоты сокращений сердца, длительности периода систолы и диастолы, значений амплитуд зубцов P, Q, R, S, T, U. Сегментация электрокардиограмы проводится несколь- кими итерациями, что позволяет достичь высокой точ- ности решения задачи при небольших затратах машин- ного времени. В результате, по выделенным почти пе- риодическим участкам электрокардиограммы определя- ется длина текущего почти периода, соответствующего суммарной длительности систолы и диастолы, и частоты сокращений сердца. Разработанными процедурами те- кущий почти период разбивается на два отрезка, один из которых – пауза (диастола), а второй – систола и содер- жит зубцы. Во втором отрезке выделяются интервалы, в каждом из которых по значениям сигнала воспроизво- дится унимодальная функция (вогнутая или выпуклая). Последовательность фрагментов этих функций опреде- ляет зубцы P, Q, R, S, T, U. По наибольшими и наи- меньшими их значениями находятся величины интерва- лов (длительность периодов P – Q, Q – R, R – S, S – T, T – U). Соответственно определяется длительность систолы и диастолы. Из изложенного следует, что комбинаторные конфи- гурации могут быть также входными данными в задачах искусственного интеллекта. Заключение. Комбинаторные подходы получают даль- нейшее развитие в решении задач искусственного интел- лекта, как показало моделирование таких задач. В рамках теории комбинаторной оптимизации можно обнаружить их комбинаторную природу, определить аргумент целевой функции, которыми служат комбинаторные конфигурации разных типов. Окончание на стр. 37 УСиМ, 2017, № 2 37 Окончание статьи Н.К. Тимофеевой и др. Эти исследования позволяют обнаружить причину не- определенности разных видов, которая возникает в про- цессе их решения, объяснить природу нечеткости вход- ных данных. В задачах этого класса комбинаторные кон- фигурации могут быть как аргументом целевой функ- ции, так и входными данными. По аргументу целевой функции они разделяются на подзадачи, для решения которых необходимо разрабатывать гибридные алго- ритмы. На примере задачи распознавания речевых сиг- налов и задачи клинической диагностики описан способ определения конкретных признаков, по которым уста- навливается подобие задач искусственного интеллекта. UDC УДК 519.816 N.К. Tymofeyeva, V.I. Gritsenko Combinatorial is in a problems of artificial intellect Keywords: artificial intellect, uncertainty, combinatorial configuration, combinatorial optimization objective function, similarity of prob- lems of combinatorial optimization. The problems of the artificial intelligence are difficult by nature and are not always amenable to formalization. A lot of the applied problems of this class are reduced to the problems of the combinatorial optimization. This is because their vast part requires sorting of variants. A combinatorial nature is the characteristic of the search problems. The design methods do not always explain the search nature of the artificial intelligence problems. The detailed analysis of the problems of this class shows that the argument for the objective function is the different types of the combinatorial configurations. The method of creating the artificial intelligence with the use of the combinatorial optimization theory is represented. An objective function and defined argument for the combinatorial configurations of different types are formulated. As the system analysis shows, in the problems of this class the combinatorial configurations can be the argument for the objective function and input data. The use of the combinatorial optimization theory allows to set the combinatorial nature, to formulate the ob- jective function, to identify the characteristics signs, which establish the similarity of the artificial intelligence problems. The expounded researches allow the identification the uncertainty cause of different kinds, which arises up in the process of their decision, and explain the nature of the input data vagueness.  << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E> /BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e> /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e> /HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E> /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e> /LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e> /RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e> /SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e> /SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e> /UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e> /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice

Комбінаторика в задачах штучного інтелекту

Репозитарії

Схожі ресурси