Дискретная математика
Дискретная математика — раздел математики, занимающийся изучением дискретных структур (то есть структур, к которым не может применяться понятие непрерывности, см. Дискретность). Часть дискретной математики, изучающая конечные структуры (например, конечные группы, графы, машины Тьюринга), называется конечной математикой.
В расширенном смысле дискретная математика делится на теорию чисел, вычислительную математику, математическую логику, комбинаторный анализ, а также новые направления исследований — теорию графов, теорию кодирования, целочисленное программирование, теорию автоматов, расписаний, ЭВМ, программирование и др., в которых объекты исследований имеют дискретный характер.
История[править]
Элементы дискретной математики возникли в глубокой древности и развивались параллельно с другими разделами математики. Например, тогдашние типичные задачи, связанные со свойствами целых чисел (истоки теории чисел): поиск алгоритмов сложения и умножения натуральных чисел (Египет, 2-е тысячелетие до н. э.), задачи суммирования и делимости натуральных чисел в пифагорейской школе (6 в. до н. э.).
Общие подходы[править]
На практике чаще всего одновременно присутствуют свойства непрерывности и дискретности, конечности и бесконечности; при решении конкретных задач широко используется прием замены непрерывной модели ее дискретным аналогом. В дискретной математике вместе с построением алгоритмов решения отдельных задач выявляются вопросы алгоритмической разрешимости, оценки вычислительной сложности алгоритмов, выявление трудноразрешимых задач и др.
Литература[править]
- Яблонский С.В. Введение в дискретную математику. М., 1979.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика: Пер. с англ. М., 1980.
- Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность: Пер. с англ. М., 1985.
 ↑ [+] | |
|---|---|