Дискретные структуры (DS)

Дискретные структуры являются фундаментальной основой информатики. Под фундаментальными мы имеем в виду то, что сравнительно небольшое число ученых будут работать непосредственно в этой дисциплине, однако во многих других областях компьютерных наук требуется умение работать с понятиями дискретных структур. Дискретные структуры включают в себя важный материал из таких областей, как теория множеств, логика, теория графов и комбинаторика.

Сведения из теории дискретных структур широко используются не только в структурах данных и алгоритмах, но и во всех остальных разделах информатики.

Сведения из теории дискретных структур широко используются не только в структурах данных и алгоритмах, но и во всех остальных разделах информатики. Например, при проверке формальных спецификаций, верификации, а также в криптографии необходимо уметь создавать и понимать формальные доказатель­ства. Понятия теории графов используются в сетях, операционных системах и компиляторах. Теория множеств находит применение в программной инженерии и базах данных.

По мере развития информатики, все более и более сложные методы анализа оказывают влияние на практические проблемы для того, чтобы освоить вычис­лительные средства будущего, сегодняшним студентам потребуется твердое зна­ние дискретных структур.

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

Следует отметить, что есть важные темы из этих двух областей, которые в некоторых школах будут включать в курсы с названиями "дискретные структуры" и "Дискретная математика", некоторым понадобится один курс, остальным два. В апреле 2007 года SIGCSE комитет выступил с подробным докладом по трем моделям односеместрового курса по дискретной математике, отвечающим критериям, сформулированным в CS2001. Эти модели по-прежнему применимы с учетом скорректированного в CS2008 объема знаний.