Дискретний аналіз
ДИСКРЕ́ТНИЙ АНА́Л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єнко, Н. З. Шор
Рекомендована література
- Глушков В. М. Синтез цифровых автоматов. Москва, 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.