Розмір шрифту

A

Комбінаторний аналіз

КОМБІНАТО́РНИЙ АНА́ЛІЗ — роз­діл математики, присвяче­ний вирішен­ню зав­дань вибору та роз­міще­н­ня елементів деякої, за­звичай скінчен­ної множини від­повід­но до за­даних правил. Результат такого вибору називають комбінатор. конфігурацією. Метою К. а. є ви­вче­н­ня ком­бінатор. конфігурацій, алгоритмів їхньої побудови, оптимізації таких алгоритмів, а також визна­че­н­ня кількості конфігурацій пев­ного класу. Гол. частину К. а. ста­новлять методи без­посеред. під­­рахунку кількості конфігурацій, метод твір. функцій, логічні, екс­тремал., геом. та ін. методи. При під­рахунку кількості комбінатор. конфігурацій важливу роль ві­ді­грає правило множе­н­ня (осн. принцип К. а.): якщо дію А можна здійснити m способами, а дію B — n способами, то заг. кількість усіх способів послідов. здій­снен­ня дій A і B дорівнює m • n. Най­простішими прикладами комбінатор. конфігурацій є роз­міщен­ня, пере­становки, комбінації. Як­що з множини M, що складаєть­ся з n елементів, послідовно по одному вибирають m елементів, то одержані набори (від­різняють­ся один від одного або елемента­ми, або їхнім порядком) нази­ва­ють роз­міще­н­нями з n елементів по m. Кількість таких роз­­міщень

Роз­міще­н­ня з n елементів по n називають пере­становками. Їхня кількість

Комбінації з n елементів по m — це всі можливі m-елементні під­­­множини з M; їхня кількість

Виникне­н­ня осн. понять і роз­виток К. а. від­бувалися паралель­но зі становле­н­ням тісно по­вʼя­заних із ним галузей математики, зокрема алгебри, чисел теорії та ймовірностей теорії. Його зародже­н­ня повʼязують із працями франц. учених Б. Паскаля (1623–62) і П. Ферми (1601–65) з теорії азарт. ігор, що й скла­ли основу теорії ймовірностей і одночасно містили принципи під­рахунку кількості комбінацій елементів скінчен. множини. Вста­новлений ними звʼя­зок між К. а. і теорією ймовірностей не­­­вдовзі став традиційним. Знач. внесок у систематич. роз­ви­ток комбінатор. методів зро­били нім. учений Г.-В. Лейбніц (1646–1716) і швейцар. математик Я. Бер­нул­лі (1654–1705). Вони ввели низку комбінатор. по­нять з їхнім за­стосува­н­ням до об­числень ймовірностей, що при­звело до виділе­н­ня комбіна­тор. методів у самост. роз­діл ма­тематики. Пізніше рос. учений швейцар. походже­н­ня Л. Ейлер (1707–83) започаткував один з осн. методів пере­рахунку комбі­натор. конфігурацій — метод твір. функцій. Особливий інтерес до К. а. науковці почали проявляти у 1950-х рр. у звʼязку з бурхливим роз­витком кібернетики та дис­крет. математики (див. Диск­ретний аналіз) і широким вико­ри­ста­н­ням електрон­но-обчислюв. техніки. Саме у цей період активізувалася зацікавленість класич. комбінатор. задачами. Нині К. а. використовують у багатьох компʼютер. науках, напр., для побудови й аналізу різноманіт. алгоритмів, знач. прогре­су досягнуто у комбінатор. ви­вчен­ні опуклих много­гран­ників, виявлено тісний звʼязок з алгеб­раїч. топологією. В Україні з роз­­­витком К. а. повʼязана школа А. Скорохода з тео­рії ймовірно­­стей.

Рекомендована література

Іконка PDF Завантажити статтю

Інформація про статтю


Автор:
Статтю захищено авторським правом згідно з чинним законодавством України. Докладніше див. розділ Умови та правила користування електронною версією «Енциклопедії Сучасної України»
Дата останньої редакції статті:
груд. 2014
Том ЕСУ:
14
Дата виходу друком тому:
Тематичний розділ сайту:
Підприємcтва
EMUID:ідентифікатор статті на сайті ЕСУ
3198
Вплив статті на популяризацію знань:
загалом:
121
сьогодні:
1
Бібліографічний опис:

Комбінаторний аналіз / В. І. Горбачук // Енциклопедія Сучасної України [Електронний ресурс] / редкол. : І. М. Дзюба, А. І. Жуковський, М. Г. Железняк [та ін.] ; НАН України, НТШ. – Київ: Інститут енциклопедичних досліджень НАН України, 2014. – Режим доступу: https://esu.com.ua/article-3198.

Kombinatornyi analiz / V. I. Horbachuk // Encyclopedia of Modern Ukraine [Online] / Eds. : I. М. Dziuba, A. I. Zhukovsky, M. H. Zhelezniak [et al.] ; National Academy of Sciences of Ukraine, Shevchenko Scientific Society. – Kyiv : The NASU institute of Encyclopedic Research, 2014. – Available at: https://esu.com.ua/article-3198.

Завантажити бібліографічний опис

ВСІ СТАТТІ ЗА АБЕТКОЮ

Нагору нагору