Дискретная математика что это такое
Дискретная математика
В контексте математики в целом дискретная математика часто отождествляется с конечной математикой — направлением, изучающим конечные структуры — конечные графы, конечные группы, конечные автоматы. И при этом можно выделить некоторые особенности, не присущие разделам, работающим с бесконечными и непрерывными структурами. Так, в дискретных направлениях как правило обширнее класс разрешимых задач, так как во многих случаях возможен полный перебор вариантов, тогда как в разделах, имеющих дело с бесконечными и непрерывными структурами, для разрешимости обычно требуются существенные ограничения на условия. В этой же связи в дискретной математике особо важную роль играют задачи построения конкретных алгоритмов, и в том числе, эффективных с точки зрения вычислительной сложности. Ещё одна особенность дискретной математики — невозможность применения для её экстремальных задач техник анализа, существенно использующих недоступные для дискретных структур понятия гладкости. В широком смысле, дискретной математикой могут считаться охваченными значительные части алгебры, теории чисел, математической логики.
В рамках учебных программ дискретная математика обычно рассматривается как совокупность разделов, связанных с приложениями к информатике и вычислительной технике: теория функциональных систем, теория графов, теория автоматов, теория кодирования, комбинаторика, целочисленное программирование.
Связанные понятия
Упоминания в литературе
Связанные понятия (продолжение)
Данная статья представляет собой обзор основных событий и тенденций в истории математики с древнейших времён до наших дней.
Дискретная математика для первокурсников: опыт преподавателя
Сегодня у меня необычный текст, совершенно не связанный с машинным обучением (для новых читателей: этот текст – часть блога компании Surfingbird, в котором я в течение последнего года рассказывал о разных аппаратах машинного обучения в приложении к рекомендательным системам). В этом посте математической части практически не будет, а будет описание очень простой программки, которую я написал для своих студентов. Вряд ли кто-то узнает для себя из этого поста много содержательно нового, но мне кажется, что некоторую ценность представляет сама идея – многие люди просто не задумываются о том, что «и так можно». Итак…
Постановка задачи
В этом семестре у меня началась несколько непривычная деятельность: я преподаю дискретную математику для первокурсников в петербургском филиале Высшей Школы Экономики; преподаю я давно, но, кажется, раньше никогда у меня не было студентов младше четвёртого-пятого курса. По ссылке можно найти краткое содержание курса, да и то неполное (курс ещё идёт), но речь не совсем об этом.
Думаю, большинство обитателей хабра хотя бы приблизительно помнят, что такое «дискретная математика для первокурсников»: пропозициональная логика, конъюнктивные и дизъюнктивные нормальные формы, базисы булевских функций, бинарные отношения, частичные порядки… В общем, ничего концептуально сложного, но это всё вещи, которыми надо овладеть очень прочно, на них держится любое математическое образование, и необходимость осознанно задумываться о них быстро станет непозволительной роскошью. Поэтому нужно много практических примеров и заданий, чтобы «набить руку».
В качестве одной из форм отчётности я выбрал «большое домашнее задание»: несколько как раз таких практических примеров, которые надо решать. У такой формы много плюсов: студенты работают в удобном им темпе, я тоже проверять могу сколько нужно, всё в письменном виде происходит, что всегда удобно. Но есть и минусы; главный минус прост – трудно сделать и проверить пятьдесят вариантов на пятьдесят студентов (на потоке их примерно столько и есть). А если дать один вариант на большую группу, понятно, что на выходе получишь красиво переписанные правильные ответы, особенно учитывая, что в такой базовой дискретной математике «ход решения» нередко просто отсутствует (как построить СДНФ – ну как, посмотреть на таблицу истинности да записать. ).
Чтобы обойти эту проблему, я решил написать простую программку, которая будет генерировать индивидуальное домашнее задание для каждого студента случайным образом. Идея чрезвычайно простая, но почему-то ни в свою бытность студентом, ни в более позднем преподавательском опыте я её ни разу не встречал – собственно, поэтому и пишу этот пост. Я приведу минимальный работающий пример, а потом покажу, что у меня в результате получилось.
Базовая технология понятна – нужно сделать LaTeX-заготовку, в которую вставлять конкретные задания для каждого студента. Совершенно всё равно, на каком языке это делать, мне исторически привычнее писать небольшие программки на C++, поэтому я и тут буду его использовать. Самый простой способ сделать это в C++, который я знаю, – это boost::format: достаточно сделать заготовки с плейсхолдерами вроде %1%, %2%, и потом можно вставлять туда что угодно (у boost::format есть и другие возможности, но нам они сейчас не понадобятся).
Итак, делаем шаблоны. Сначала общий шаблон «абстрактного LaTeX-документа»:
Потом конкретный шаблон собственно задания – его мы будем подставлять вместо %1%. Я здесь, как и обещал, привожу минимальный пример. Мы будем генерировать только одну задачку: по заданной булевской формуле перевести её в несколько других форм.
И теперь нам просто нужно сгенерировать, чем заполнить %3% (вместо %1% и %2% будут подставляться имя студента и номер группы). Для этого нужно научиться генерировать формулы. Сразу предупреждаю, что я плохой программист, и код ниже наверняка напоминает спагетти – в принципе, он работает, если кто-нибудь посоветует изящный рефакторинг, скажу спасибо.
Сначала надо завести структуру, которая будет хранить разные связки и типы узлов в формуле; для нашего минимального примера это лишнее, но мне надо было сделать ещё задачку про формулы алгебры множеств (объединения, пересечения да симметрические разности), и код про деревья формул хотелось переиспользовать. Поэтому вот глобальный объект, хранящий основную информацию:
Здесь мы создали «язык булевских формул», у которого пять бинарных связок (конъюнкция, дизъюнкция, импликация, XOR и эквивалентность) и одна унарная (отрицание). Седьмой тип узла – это переменная, у неё арность 0. В домашнем задании я ограничился формулами из четырёх переменных: меньше маловато, а больше становится слишком громоздко. Сюда же удобно записать генераторы случайного типа узла, случайной переменной, случайной бинарной связки (я пользовался распределениями из boost::random – опять же, очень удобно; хоть там и не так уж много чего реализовано, но нам сейчас много и не надо).
Такую структуру легко будет переиспользовать для формул алгебры множеств (это просто для сравнения, дальше GSet использоваться не будет):
Теперь создаём класс формулы. Булевская формула – это дерево, листьями которого служат переменные, а внутренними вершинами – логические связки. Мы хотим уметь генерировать формулы заданной глубины, поэтому в конструктор будем передавать, не пора ли сделать этот узел листом или, наоборот, обязательно бинарной связкой. Если нужно создать случайный узел, будем передавать тип g->TypesNo. Если узел оказался листом, ему нужно сгенерировать переменную (чтобы с большой вероятностью переменные попали все, мы просто берём их по кругу – формулы, конечно, не совсем случайные получаются, но это не страшно).
Теперь начинаем заполнять класс BNode. Главное для нас – чтобы формула успешно печаталась в LaTeX:
Кроме того, нужно будет уметь подсчитывать значение формулы на заданном наборе переменных:
Оставим пока класс BNode (мы к нему ещё вернёмся); теперь мы можем написать генератор случайной формулы. Будем генерировать формулу с заданной минимальной и максимальной глубиной (для поддержки минимальной глубины мы добавляли раньше в конструктор поле must_not_be_leaf):
Тут всё самоочевидно; единственное решение, которое я здесь принял – сделал унарные функции (т.е. отрицания) «бесплатными», не считающимися для глубины, иначе формулы получались бы слишком простыми. Кроме того, в булевской формуле логично запретить ставить два отрицания подряд, это бессмысленно; для этого нам и нужен был флаг must_be_binary в конструкторе.
И можно писать обработчик файла со списком студентов:
а затем и main, который читает файлы с форматами и процессит файлы со списками студентов:
Но постойте, слышу я голос внимательного читателя. Будет же ерунда получаться – небось, добрая половина так сгенерированных случайных формул окажутся тривиальными! Что верно, то верно – про половину не знаю, но даже одна случайно сгенерированная формула вида \varphi = x изрядно подмочит репутацию нашего метода. Давайте мы научимся это проверять. Для этого мы просто подсчитаем, сколько в формуле встречается связок и разных переменных, и потребуем, чтобы переменные встречались все, а связки – хотя бы две разные. Добавляем в BNode обход формулы:
и вписываем проверку формулы на разумность:
Можно ещё захотеть проверить, не является ли формула, скажем, всегда истинной, но я этого сознательно решил не делать – если сложная на вид формула вдруг окажется тождественно истинной, тем интереснее будет это задание для студента. А очевидные подформулы типа «x или не x» в нашем генераторе не будут получаться, потому что переменные перебираются по очереди, а не случайно.
Решения
Скептически настроенный читатель на этом месте разумно возразит: ну конечно, ты можешь сгенерировать over 9000 разных заданий, но ведь ты замучаешься их потом проверять! И действительно, проверять у каждого студента таблицу истинности – занятие для очень сильных духом людей, к которым я себя не отношу. Поэтому нашу программку надо будет модифицировать так, чтобы она могла облегчить и процесс проверки. Совсем автоматизировать его не получится (студенты всё равно будут сдавать работы, написанные в свободном формате от руки), поэтому достаточно будет просто сделать заранее самую противную часть этой работы.
Заводим другой LaTeX-шаблон для документа с ответами:
Я, опять же, ограничусь минимальным примером – давайте просто выведем таблицу истинности. Для этого нужно пройтись по всем возможным значениям переменных, посчитать истинностное значение формулы и красиво оформить результат в TeX’е. Добавляем два метода в класс BNode:
а затем добавляем это в process_one_student_file_boolean:
В результате в пару к файлу заданий (пример) получается соответствующий ему файл решений (тот же пример, решения), по которому проверять становится гораздо проще.
Заключение
И вот результат – полдня работы, а на выходе сколько угодно заданий с готовыми ответами, всё красиво оформлено и готово к выдаче студентам. Если интересно, каким получилось реальное задание, вот пример окончательного результата. Файл с ответами выкладывать не буду, чтобы лишний раз не подсказывать студентам – они сейчас как раз решают это домашнее задание. Думаю, если моё преподавание в ГУ-ВШЭ будет продолжаться, эта программка мне ещё не раз послужит; ближайший шанс её применить – билеты для письменного экзамена в тех же группах.
ДИСКРЕТНАЯ МАТЕМАТИКА
Смотреть что такое «ДИСКРЕТНАЯ МАТЕМАТИКА» в других словарях:
ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конечная математика … Большой Энциклопедический словарь
Дискретная математика — Дискретная математика область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а… … Википедия
дискретная математика — то же, что конечная математика. * * * ДИСКРЕТНАЯ МАТЕМАТИКА ДИСКРЕТНАЯ МАТЕМАТИКА, то же, что конечная математика (см. КОНЕЧНАЯ МАТЕМАТИКА) … Энциклопедический словарь
ДИСКРЕТНАЯ МАТЕМАТИКА — то же, что конец ноя математика … Естествознание. Энциклопедический словарь
«Дискретная математика» — научный журнал РАН, с 1989, Москва. Учредитель (1998) Отделение математики РАН. 4 номера в год … Энциклопедический словарь
Теория функциональных систем (дискретная математика) — У этого термина существуют и другие значения, см. Теория функциональных систем (значения). Теория функциональных систем раздел дискретной математики, занимающийся изучением функций, описывающих работу дискретных преобразователей. В теории… … Википедия
МАТЕМАТИКА — (греч. mathematike от mathema наука), наука, в которой изучаются пространственные формы и количественные отношения. До нач. 17 в. математика преимущественно наука о числах, скалярных величинах и сравнительно простых геометрических фигурах;… … Большой Энциклопедический словарь
Математика — Евклид. Деталь «Афинской школы» Рафаэля Математика (от др. греч … Википедия
математика — и; ж. [греч. mathēmatikē] 1. Наука о количественных отношениях и пространственных формах действительного мира. Высшая м. Элементарная м. Прикладная м. Законы математики. // Учебный предмет, изучающий эту науку. Экзамен по математике. Преподавать… … Энциклопедический словарь
Математика гармонии — Эта статья предлагается к удалению. Пояснение причин и соответствующее обсуждение вы можете найти на странице Википедия:К удалению/22 ноября 2012. Пока процесс обсуждени … Википедия
Дискретная математика: для чего они нужны, теория множеств
Содержание:
В дискретная математика Они соответствуют той области математики, которая отвечает за изучение набора натуральных чисел; то есть набор счетных конечных и бесконечных чисел, в котором элементы можно пересчитывать отдельно, один за другим.
Эти наборы известны как дискретные наборы; Примером этих наборов являются целые числа, графики или логические выражения, и они применяются в различных областях науки, в основном в информатике или вычислениях.
Описание
В дискретной математике процессы счетные, в их основе лежат целые числа. Это означает, что десятичные числа не используются и, следовательно, приближения или пределы не используются, как в других областях. Например, неизвестное значение может быть равно 5 или 6, но не 4,99 или 5,9.
С другой стороны, в графическом представлении переменные будут дискретными и даны из конечного набора точек, которые подсчитываются одна за другой, как показано на изображении:
Дискретная математика возникает из-за необходимости получить точное исследование, которое можно объединить и проверить, чтобы применить его в разных областях.
Для чего нужна дискретная математика?
Дискретная математика используется во многих областях. Среди основных можно выделить следующие:
Комбинаторный
Изучите конечные наборы, в которых элементы можно упорядочивать, комбинировать и подсчитывать.
Теория дискретного распределения
Изучите события, которые происходят в пространствах, где выборки могут быть счетными, в которых непрерывные распределения используются для аппроксимации дискретных распределений, или наоборот.
Теория информации
Это относится к кодированию информации, используемой для разработки, передачи и хранения данных, таких как аналоговые сигналы.
Вычисление
С помощью дискретной математики задачи решаются с использованием алгоритмов, а также того, что можно вычислить, и времени, которое требуется для этого (сложность).
Важность дискретной математики в этой области возросла в последние десятилетия, особенно для развития языков программирования и программирования. программное обеспечение.
Криптография
Он полагается на дискретную математику для создания структур безопасности или методов шифрования. Примером этого приложения являются пароли, отправляющие биты, содержащие информацию, отдельно.
Благодаря изучению свойств целых и простых чисел (теория чисел) эти методы безопасности могут быть созданы или уничтожены.
Логика
Для доказательства теорем или, например, проверки программного обеспечения используются дискретные структуры, которые обычно образуют конечное множество.
Теория графов
Он позволяет решать логические проблемы, используя узлы и линии, которые образуют тип графа, как показано на следующем изображении:
Это область, тесно связанная с дискретной математикой, потому что алгебраические выражения дискретны. Благодаря этому разрабатываются электронные схемы, процессоры, программирование (булева алгебра) и базы данных (реляционная алгебра).
Геометрия
Изучите комбинаторные свойства геометрических объектов, например плоского покрытия. С другой стороны, вычислительная геометрия позволяет разрабатывать геометрические задачи, применяя алгоритмы.
Теория множеств
В дискретной математике множества (конечные и бесконечные счетные) являются основной целью исследования. Теория множеств была опубликована Джорджем Кантором, который показал, что все бесконечные множества имеют одинаковый размер.
В математике существуют различные наборы, которые группируют определенные числа в соответствии с их характеристиками. Так, например, имеем:
Наборы именуются прописными буквами алфавита; а элементы названы строчными буквами в фигурных скобках (<>) и разделены запятыми (,). Обычно они представлены в виде диаграмм Венна и Кэролла, а также в виде вычислений.
С помощью основных операций, таких как объединение, пересечение, дополнение, различие и декартово произведение, наборы и их элементы управляются на основе отношения принадлежности.
Существует несколько классов множеств, наиболее изученными в дискретной математике являются следующие:
Конечный набор
Он состоит из конечного числа элементов и соответствует натуральному числу. Так, например, A = <1, 2, 3,4>— это конечное множество, состоящее из 4 элементов.
Бесконечный набор учетных записей
Это тот, в котором существует соответствие между элементами множества и натуральными числами; то есть из одного элемента могут быть последовательно перечислены все элементы набора.
Таким образом, каждый элемент будет соответствовать каждому элементу набора натуральных чисел. Например:
Это метод, используемый для решения непрерывных задач (моделей и уравнений), которые необходимо преобразовать в дискретные задачи, в которых решение известно с приближением решения непрерывной задачи.
С другой стороны, дискретизация пытается извлечь конечную величину из бесконечного множества точек; Таким образом, непрерывная единица превращается в отдельные единицы.
Обычно этот метод используется в численном анализе, например, при решении дифференциального уравнения, с помощью функции, которая представлена конечным количеством данных в своей области, даже если она является непрерывной.
Ссылки
Что происходит в вашем мозгу, когда вы едите шоколад или какао?
3 закона Менделя и горох: вот чему они нас учат