Что такое дискретная математика?

[Mihr]

Этот вопрос почти спонтанно возник в одной из последних тем:

Anton_Peplov в сообщении #1666595 писал(а):

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

Someone в сообщении #1666616 писал(а):

Ага. А ещё я там встречал математическую логику, теорию множеств и топологию.

Евгений Машеров в сообщении #1666621 писал(а):

И даже перевод чисел из одной системы счисления в другую.

Я тоже когда-то говорил:

Mihr в сообщении #1577721 писал(а):

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

При всём при этом у меня всё же нет ощущения, будто дискретная математика - это такая вот "сборная солянка", куда можно запихнуть почти что угодно. Мне, скорее, представляется, что это - большая и разветвлённая часть математики, которую весьма трудно охватить одним учебником. Для сравнения: было бы совершенно нереально охватить одним учебником весь матанализ в широком смысле слова, то есть вместе со всеми дисциплинами, которые из него выросли или примыкают к нему: с дифференциальными уравнениями, вариационным исчислением, ТФДП, ТФКП, дифференциальной геометрией, теорией вероятностей и т.д. По всем этим разделам, как правило, существуют отдельные учебники со сложившейся тематикой. Но дискретная математика, несмотря на то, что отдельные её разделы имеют немалый возраст, - пока преимущественно в стадии становления. И стандартный круг её вопросов ещё не сложился.
Здесь мой первый вопрос к математикам: насколько верно такое впечатление? Или, всё же, с вашей точки зрения, термин "дискретная математика", скорее, условен, чем и впрямь отражает некое единство задач и методов? Интересно ваше мнение на этот счёт.

Второе. Сейчас я попытаюсь сделать небольшой обзор тем, которые мне встретились в разных учебниках дискретной математики. Хотелось бы узнать ваше мнение: какие из этих тем следовало было бы отнести к "ядру" дискретной математики, какие - к её "периферии", а какие - считать вообще притянутыми за уши? (Если, конечно, с тезисом о том, что за термином "дискретная математика" всё же стоит нечто единое, вы не спорите).

Сперва небольшой список учебников и пособий (в алфавитном порядке фамилий их авторов), которые в данный момент у меня под рукой, на них я стану ссылаться ниже.
1. Акимов О.Е. Дискретная математика. Логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003.
2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. М. - Ижевск, РХД, 2001.
3. Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика. Ростов-на-Дону: Феникс, 2003.
4. Белоусов А.И., Ткачев С.Б. . М.: МГТУ им. Баумана, 2002.
5. Горбатов В.А. Фундаментальные основы дискретной математики. М.: Физматлит, 2000.
6. Горбатов В.А., Горбатов А.В., Горбатова М.В. Дискретная математика. Учебник для студентов втузов. М.: АСТ - Астрель, 2003.
7. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998.
8. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М.: Лаборатория Базовых Знаний, 2002.
9. Набебин А.А. Логика и Пролог в дискретной математике. М.: Изд-во МЭИ, 1996.
10. Новиков Ф.А. Дискретная математика для программистов. Учебник. С.-П.: Питер, 2001.
11. Палий И.А. Дискретная математика. Курс лекций. М.: Эксмо, 2008.
12. Редькин Н.П. Дискретная математика. Курс лекций для студентов-механиков. С.П. - М. - Краснодар: "Лань", 2006.
13. Романовский И.В. Дискретный анализ. С.-П. - М.: Физматлит, 2001.
14. Судоплатов С.В., Овчинникова Е.В.. Дискретная математика. Учебник. М. - Новосибирск, 2005.
15. Шапорев С.Д. Дискретная математика. Курс лекций и практических занятий. С.-П.: БХВ-Петербург, 2006.

Ну, а теперь темы, которые в них встречаются:

- алгебраические структуры (группы, решетки, матроиды и др.) 1, 2, 4, 6, 8, 10, 11
- алгоритмы 2, 5, 9
- булевы функции 4, 6, 10, 11, 12
- k-значные функции 6
- графы 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15
- кодирование 10, 12, 13
- конечные суммы 7
- комбинаторика 3, 7, 8, 9, 10, 11, 12, 13, 14, 15
- множества 3, 4, 5, 6, 10, 11, 13, 14, 15
- отношения и отображения 4, 6, 10, 11, 13, 14
- рекуррентности 7, 8
- системы счисления 14
- теория автоматов 5, 9, 13
- целочисленные функции 7
- элементы матлогики 1, 3, 5, 9, 10, 11, 14
- элементы теории вероятностей (дискретная вероятность) 7, 13
- элементы теории чисел 7, 8

Просьба высказываться всем, кому есть, что сказать. Прежде всего интересует мнение математиков форума.

[drzewo]

лирика

(Оффтоп)

А для меня математика вообще вся делится на дискретную и непрерывную. Дискретная это та, которая не связана с понятием непрерывность в самом широком смысле.

[Gagarin1968]

[Mihr]

drzewo в сообщении #1666676 писал(а):

Дискретная это та, которая не связана с понятием непрерывность в самом широком смысле.

Тогда, видимо, следует разделить теорию вероятностей, теорию информации, да и некоторые другие разделы математики на две части. Чтобы одну часть такой дисциплины отнести к дискретной математике, другую - к непрерывной. Наверно, смысл в этом есть, но как-то это не радует.

Gagarin1968, спасибо, но это оглавление, вроде бы, ничего не добавляет к списку.

[Gagarin1968]

Mihr в сообщении #1666680 писал(а):

но это оглавление, вроде бы, ничего не добавляет к списку.

Кроме последней восьмой главы — там рассматривается программирование игр.
И не забудьте — книга издана 45(!) лет назад.

[Евгений Машеров]

Это именно "сборная солянка". Либо прелиминарный курс перед изучением, скажем, программирования, либо справочное пособие для нематематиков, содержащее отрывочные, но практически востребованные сведения. Пример первого - Кнут-Грэхем-Паташник, пример второго - Адельсон-Вельский.

[Mihr]

Gagarin1968 в сообщении #1666682 писал(а):

Кроме последней восьмой главы — там рассматривается программирование игр.

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

Gagarin1968 в сообщении #1666682 писал(а):

И не забудьте — книга издана 45(!) лет назад.

Не понял. Что это меняет?

Евгений Машеров, спасибо за ответ.

[Gagarin1968]

Mihr в сообщении #1666687 писал(а):

Gagarin1968 в сообщении #1666682 писал(а):

И не забудьте — книга издана 45(!) лет назад.

Не понял. Что это меняет?

То, что Ваш список учебников датирован уже началом XXI века, и если бы Вы Вашу разблюдовку дискретной математики из стартового поста писали бы в 1980 году, полагаю, она сильно отличалась бы от написанного сейчас.
Не считаете так?

[Mihr]

Gagarin1968 в сообщении #1666690 писал(а):

То, что Ваш список учебников датирован уже началом XXI века

В нём есть пара книг, изданных в конце 20-го века (1996-й и 1998-й гг.).

Gagarin1968 в сообщении #1666690 писал(а):

полагаю, она сильно отличалась бы от написанного сейчас.
Не считаете так?

Так я как раз и говорю, что фактически дискретная математика - в стадии становления. Естественно, за полвека этот раздел преобразился заметно. С этим я ведь и не спорю.

[Евгений Машеров]

Mihr в сообщении #1666687 писал(а):

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

Общую задачу ЦЛП к графам отнести будет трудновато. А, скажем, в задаче коммивояжёра графы в постановке - а потом куда-то деваются, методы решения не специфически "графские".

В математике есть разделы, которые работают преимущественно с дискретными понятиями, но они далеки друг от друга и при этом могут быть близки к работающим с непрерывными (скажем, 1 том Феллера про дискретные распределения, второй про непрерывные - но это одна дисциплина), так что выделять "дискретную математику", как полноценный признак, является пустым формализмом. Но ряд таких разделов имеет практическое применение, при этом для нематематиков достаточно "общего знакомства", понимания терминов и знания элементарных операций, а доказательства и вообще глубокое изучение можно опустить. При организации учебного процесса не принято давать курсы на несколько дней или даже недель, "квант учения" - семестр. Но даже односеместровый курс слишком обширен для одного из разделов, поэтому механически соединяют несколько полезных, но кратких подкурсов, объединяя названием "дискретная математика", поскольку традиционно основной курс высшей математики технического или экономического ВУЗа - матанализ, принципиально непрерывный (по крайней мере в объёме курса политеха и т.п.)
Вот конкретно по курсам.
Чтобы работать с реляционными базами данных, надо иметь понятие о множествах и операциях над ними.
Чтобы программировать условные операторы - надо знать операции матлогики.
Графы - и описание программ (хотя блок-схемы из моды вышли), и некоторые задачи оптимизации.
Теория автоматов - тоже программирование, но скорее embedded.
Полугруппы - формальное описание языков программирования.
Теория алгоритмов - вообще фундамент программирования.
Но для практического использования программистом из каждого раздела надо знать немногим больше названий и элементарных понятий.

(Оффтоп)

Я знаю карате, кунфу, тейквондо и ещё много других страшных слов!

Поэтому две недели на множества, неделя на логические операции, три недели на теорию графов, две недели на полугруппы, неделя на системы счисления, три недели на теорию алгоритмов, 12 недель - а в семестре 17, надо ещё 5, одну оставим на "повторение", и в 4 включим "дискретную оптимизацию".
Так и назовём - "дискретная математика". Если получится, изложим в учебном пособии, и даже в учебнике, и тоже его так назовём.

[Mihr]

Евгений Машеров в сообщении #1666693 писал(а):

Общую задачу ЦЛП к графам отнести будет трудновато.

Да, согласен. Но я писал сокращённо. Скажем, вместо "элементы матлогики" можно было написать отдельно "алгебра логики", "исчисление высказываний", "предикаты". Только зачем? Хотелось обозначить предмет в общих чертах, особо не расписывая в деталях.

Евгений Машеров в сообщении #1666693 писал(а):

Поэтому две недели на множества, неделя на логические операции, три недели на теорию графов, две недели на полугруппы, неделя на системы счисления

Я имел в виду не столько учебные планы и сроки их выполнения, сколько конкретное содержание предмета. По одной только комбинаторике существуют отдельные учебники. Их в неделю изучения не впихнёшь. Равно как и курсы, подобные "Конкретной математике" Кнута. Лично мне этот курс представляется достаточно цельным, вполне заслуживающим отдельного названия.

[EUgeneUS]

Евгений Машеров в сообщении #1666683 писал(а):

Это именно "сборная солянка". Либо прелиминарный курс перед изучением, скажем, программирования,

плюс 1005000

У меня был курс "Дискретной математики", но не общепотоковый, а в рамках специализации, "на кафедре".
Насколько помню, туда входило:
1. Булева алгебра.
2. Комбинаторика и её применение в теории вероятностей. По крайней мере, задачи про третью даму и четвертого валета решали, как учебные
3. Теория автоматов.

[Евгений Машеров]

Mihr в сообщении #1666695 писал(а):

Я имел в виду не столько учебные планы и сроки их выполнения, сколько конкретное содержание предмета. По одной только комбинаторике существуют отдельные учебники. Их в неделю изучения не впихнёшь. Равно как и курсы, подобные "Конкретной математике" Кнута. Лично мне этот курс представляется достаточно цельным, вполне заслуживающим отдельного названия.

Ещё раз. Это "сборная солянка", разные по содержанию дисциплины, механически объединённые ради удобства организации учебного процесса или по библиографическим соображениям.
(Скажем, на сайте twirpx в разделе "Математика" есть подраздел "Дискретная математика", включающий:
Булева алгебра
Комбинаторика
Теория автоматов
Теория графов
При этом матлогика - самостоятельный подраздел, в "Методах оптимизации" много книг по дискретной оптимизации, дискретные структуры общей алгебры там, в "Общей алгебре", а дискретные распределения теорвера в "Теории вероятностей", аналогично в "Теории игр", а принципиально дискретная "Теория чисел" тоже самостоятельный подраздел. То есть "Дискретная математика" появилась потому, что есть несколько небольших, в данном случае по числу книг на сайте, дисциплин, и их надо куда-то положить)

Что касается "Конкретной математики", то она, как определили авторы, "математические основы информатики". Именно компендиум сведений, необходимых для полноценной работы в области программированияалгоритмики (можно рисовать формы в 1С или картинки для мульфильмов, и вполне себя числить программистом, поскольку никакой самостоятельной разработки алгоритмов, ниже анализа их, такая работа не предусматривает). При этом она не совпадает с курсами "Дискретной математики", включая в себя обычно туда не входящую теорию чисел и теорию вероятностей, а также вовсе не дискретный асимптотический анализ.

[Mihr]

Евгений Машеров в сообщении #1666699 писал(а):

Что касается "Конкретной математики", то она... не совпадает с курсами "Дискретной математики"

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

Евгений Машеров в сообщении #1666699 писал(а):

включая в себя обычно туда не входящую теорию чисел и теорию вероятностей

Обычно - да, но в курсы некоторых авторов элементы этих разделов включены.

Евгений Машеров в сообщении #1666699 писал(а):

а также вовсе не дискретный асимптотический анализ

Да. И, по-моему, это всё, что есть "не дискретного" в данном курсе. Но ведь название курса и расшифровывается как "континуально-дискретная математика", должно же быть в таком курсе хоть что-то "не дискретное".

EUgeneUS в сообщении #1666697 писал(а):

плюс 1005000

В таком случае разные части такого курса должны быть практически независимы друг от друга. Как тогда быть с тем, что аппарат алгебры логики вовсю используется в задаче минимизации булевых функций, а также в решении некоторых задач на графах (поиск экстремальных внутренне/внешне устойчивых множеств вершин графа, поиск оптимальной вершинной раскраски графа), а для построения хроматических полиномов оказываются полезными факториальные степени, которые рассматриваются у Кнута, и которые оказываются тесно связанными с комбинаторными числами Стирлинга? Как-то это не похоже на механическое соединение разнородных элементов.

[drzewo]

(Оффтоп)

Mihr в сообщении #1666680 писал(а):

Тогда, видимо, следует разделить теорию вероятностей, т

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