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

Визначення і загальна характеристика

ДИСКРЕ́ТНИЙ АНА́Л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ї геом. проектува­н­ня.

Літ.: Глушков В. М. Синтез цифровых автоматов. Москва, 1962; Зыков А. А. Теория конечных графов. Новосибирск, 1969; Червак Ю. Ю. Об одном методе отсечений для дис­кретных задач // УМЖ. 1971. № 6; Пере­пелица В. А. Асимптотический подход к решению некоторых экстремальных задач на графах // Про­блемы кибернетики. 1973. Вып. 26; Глушков В. М., Капитонова Ю. В., Летичевский А. А. Автоматизация проектирования дис­кретных устройств. К., 1975; Танаев В. С., Шкурба В. В. Введение в теорию расписаний. Москва, 1975; Шор Н. З. Методы минимизации недиф­ференцируемых функций и их приложения. К., 1979; Глушков В. М. Основы без­бумажной технологии. Москва, 1982; Донец Г. А., Шор Н. З. Алгебраический подход к про­блеме раскраски плоских графов. К., 1982; Михалевич В. С., Кукса А. И. Методы последовательной оптимизации в дис­кретных сетевых задачах оптимального рас­пределения ресурсов. Москва, 1983; Михалевич В. С., Трубин В. А., Шор Н. З. Оптимизацион­ные задачи производствен­но-транс­порт­ного планирования. Москва, 1986; Коваленко И. Н., Левитская А. Н., Савчук М. Н. Из­бран­ные задачи вероятностной комбинаторики. К., 1986; Стоян Ю. Г., Яковлев С. В. Математические модели и оптимизацион­ные методы геометрического проектирования. К., 1986; Глушков В. М., Капитонова Ю. В., Мищенко А. Т. Логическое проектирование дис­кретных устройств. К., 1987; Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычислительных систем. Москва, 1988; Сергиенко И. В. Математические модели и методы решения задач дис­кретной оптимизации. К., 1988; Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки. Про­грам­мирование. Изд. 3-е. К., 1989; Коваленко И. Н., Наконечный А. Н. При­ближен­ный расчет и теория надежности. К., 1989; Шор Н. З., Стеценко С. И. Квадратичные экстремальные задачи и недиф­ференцируемая оптимизация. К., 1989; N. Z. Shor. Nondifferentiable optimization and polynomial problems. Boston; Dordrecht, 1998.

І. В. Сергiєнко, Н. З. Шор

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