Дискретний аналіз

ДИСКРЕ́ТНИЙ АНА́ЛIЗ — галузь математики, предметом дослідже­н­ня якої є властивості структур скiнченого (або злічен­ного) характеру, що виникають як у самiй математицi, так i в її за­стосува­н­нях. У рамках Д. а. виділяють низку тiсно повʼязаних мiж собою роз­дiлiв, кожний з яких можна вважати самост. наук. напрямом: математична логiка; теорiя автоматiв (зокрема й цифрових); бульовi функцiї та оптимiзацiя їх канонiч. пред­ставлень; про­блеми верифiкацiї та оптимiзацiї алгоритмiв i про­грам; теорiя чисел i дiофантовi рiвня­н­ня; теорiя графiв, пере­лiчувальнi та екс­трем. задачi на графах; теорiя скiнчених груп; теорiя складностi алгоритмiв; ймовiрнiсна комбiнаторика, теорiя кодува­н­ня; комбiнаторна топологiя та геом. пере­лiчувальнi задачi й оцiнки; методи роз­вʼязува­н­ня задач дис­крет. i бульового про­грамува­н­ня (точнi, на­ближенi), дво­їстi оцiнки для цих задач та ін. Роз­виток елементiв Д. а. роз­почався ще в античнi часи (Пiфагор, Дiофант, Аристотель, Платон), вiдродився у 16–17 ст. (П. Ферма, Ґ. Ляйбнiц, І. Ньютон, Й. Кеплер та iн.), а деякi роз­дiли сформувалися як самостiйнi напрями у 18–19 ст. (К. Ґаусс, Дж. Буль, П. Лаґранж, А.-М. Лежандр, Е. Ґалуа, Н. Абель, К. Кляйн, П. Чебишов та iн.). Серед учених, які працювали в Українi в галузi Д. а., — академік С.-Петербур. АН П. Чебишов, М. Кравчук, В. Глушков, Л. Калужнін, В. Михалевич, О. Зиков. Так, В. Глушков органiзував в Iн-ті кібернетики АН УРСР (Київ) школу теор. основ iнформатики, у якій дослідж. присвяч., зокрема, пита­н­ням теорiї цифр. автоматiв, алгебри пере­творе­н­ня про­грам, теорiї проектува­н­ня обчислюв. комплексiв, алгоритмам автоматизацiї доведень; виховав плеяду вiдомих вчених у цій галузі, серед них К. Ющенко, О. Летичевський, Ю. Капiтонова, Г. Цейтлiн. В. Михалевич спільно зi своїми учнями (Н. Шором, В. Шкурбою, А. Куксою, В. Волковичем) роз­робив методи послiдовної комбiнатор. оптимiзацiї для комбiнатор. задач оптим. проектува­н­ня, теорiї роз­кладiв. I. Сергiєнко створив школу на­ближ. методiв роз­вʼязува­н­ня задач дис­крет. оптимiзацiї, теорiї їх стiйкостi. I. Коваленко спільно з учнями здійснив аналiз імовiрніс. комбiнатор. задач, якi зустрiчаються в теорiї кодува­н­ня, матем. статистицi, теорiї надiйностi. Н. Шор заснував школу недиференцi­йовної оптимiзацiї; його методи за­стосованi при дослiдж. оцiнок у комбiнатор. задачах і вирiшен­нi про­блем теорiї складностi оптимiзац. алгоритмiв. В. Трубiн за­пропонував оригiн. методи дослiдж. комбiнатор. задач вибору й синтезу складних мереж. Ю. Стоян створив у Харковi школу геом. проектува­н­ня. Значний внесок у роз­виток теорiї графiв в Українi зробили О. Зиков і Г. Донець.

Серед ви­дань, якi систематично публiкують дослідж. у галузi Д. а., — «Кiбернетика i системний аналiз». Укр. вченi мають свiт. ви­зна­н­ня досягнень у низці важл. про­блем Д. а., зокрема щодо штуч. iнтелекту, багатоконвеєрних ЕОМ, складностi паралел. алгоритмiв, на­ближ. і точних методiв бульового, дис­крет. й мiшаного про­грамува­н­ня, синтезу мереж, нових моделей i методiв оцiнок для екс­трем. задач на графах, у теорiї роз­кладiв, теорiї ймовiрніс. комбiнатор. задач, теорiї геом. проектува­н­ня.

Завантажити статтю