Дискретная математика

Материал из Циклопедии
Перейти к: навигация, поиск
Дискретная математика. Вводная лекция // Евразийский открытый институт [29:16]

Дискретная математика — раздел математики, занимающийся изучением дискретных структур (то есть структур, к которым не может применяться понятие непрерывности, см. Дискретность). Часть дискретной математики, изучающая конечные структуры (например, конечные группы, графы, машины Тьюринга), называется конечной математикой.

В расширенном смысле дискретная математика делится на теорию чисел, вычислительную математику, математическую логику, комбинаторный анализ, а также новые направления исследований — теорию графов, теорию кодирования, целочисленное программирование, теорию автоматов, расписаний, ЭВМ, программирование и др., в которых объекты исследований имеют дискретный характер.

[править] История

Элементы дискретной математики возникли в глубокой древности и развивались параллельно с другими разделами математики. Например, тогдашние типичные задачи, связанные со свойствами целых чисел (истоки теории чисел): поиск алгоритмов сложения и умножения натуральных чисел (Египет, 2-е тысячелетие до н. э.), задачи суммирования и делимости натуральных чисел в пифагорейской школе (6 в. до н. э.).

[править] Общие подходы

На практике чаще всего одновременно присутствуют свойства непрерывности и дискретности, конечности и бесконечности; при решении конкретных задач широко используется прием замены непрерывной модели ее дискретным аналогом. В дискретной математике вместе с построением алгоритмов решения отдельных задач выявляются вопросы алгоритмической разрешимости, оценки вычислительной сложности алгоритмов, выявление трудноразрешимых задач и др.

[править] Литература

  • Яблонский С.В. Введение в дискретную математику. М., 1979.
  • Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика: Пер. с англ. М., 1980.
  • Пападимитриу Х.Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность: Пер. с англ. М., 1985.


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты