Основы дискретной математики

Привет, хабр. В преддверии старта базового курса «Математика для Data Science» делимся с вами переводом еще одного полезного материала.

Об этой статье

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

ЧТО ТАКОЕ ДИСКРЕТНАЯ МАТЕМАТИКА?

Это область математики, изучающая объекты, которые могут принимать только уникальные отдельные значения.

Мы рассмотрим пять основных разделов в следующем порядке.

ЛОГИКА

Что такое логика?

Это наука о корректных рассуждениях. Мы будем использовать приемы идеализации и формализации. Неформальная логика изучает использование аргументов в естественном языке.

Формальная логика анализирует выводы с чисто формальным содержанием. Примерами формальной логики являются символическая логика и силлогистическая логика (о которой писал Аристотель).

Начнем с азов. Рассмотрим следующее высказывание на естественном языке:

«Если я голоден, я ем».

Пусть «голоден» будет посылкой A, а «ем» — следствием B. Попробуем формализовать:

A => B (то есть из A следует B)

NB. Посылка и следствие являются суждениями.

Логические выражения

Для нас важна форма, а НЕ содержание. Значение будет истинным, если оно соответствует форме.

Например, 10 4 — ИСТИНА.

Логические операции

Суждение P — это утверждение, которое может быть как истинным, так и ложным.

Обозначим истинное значение P единицей (1), а ложное значение P нулем (0).

Существует другое суждение; обозначим истинное значение Q единицей (1), а ложное значение Q нулем (0).

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

Источник

Дискретная математика для первокурсников: опыт преподавателя

Сегодня у меня необычный текст, совершенно не связанный с машинным обучением (для новых читателей: этот текст – часть блога компании 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:

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

Заключение

И вот результат – полдня работы, а на выходе сколько угодно заданий с готовыми ответами, всё красиво оформлено и готово к выдаче студентам. Если интересно, каким получилось реальное задание, вот пример окончательного результата. Файл с ответами выкладывать не буду, чтобы лишний раз не подсказывать студентам – они сейчас как раз решают это домашнее задание. Думаю, если моё преподавание в ГУ-ВШЭ будет продолжаться, эта программка мне ещё не раз послужит; ближайший шанс её применить – билеты для письменного экзамена в тех же группах.

Источник

Алгебра логики

Логические операции в порядке убывания приоритета

Например : A И B, A AND B, A & B, A · B, A * B, A ˄ B, A ∏ B, A ∩ B.

Например : A ИЛИ B, A OR B, A + B, A ˅ B, A U B.

Приоритет логических операций

Диаграммы Венна или в некоторых источниках Виенна, или Эйлера-Венна

Графы

Радиус, диаметр и центры графа

Эксцентриситет вершины графа — расстояние до максимально удаленной от нее вершины. Радиус графа — минимальный эксцентриситет вершин, а диаметр графа — максимальный эксцентриситет вершин. Центр графа образуют вершины, у которых эксцентриситет равен радиусу. Центр графа может состоять из одной, нескольких или всех вершин графа [Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. — М.: Издательство ФИЗМАТЛИТ, 2007. — 168 с.].

Задача. Дан граф с заданным весом ребер

Найти радиус, диаметр и центры графа.

Заданы веса ребер, поэтому граф называется взвешенный. Программа на C ++ в Visual Studio 2013:

# include «stdafx.h» // Visual Studio 2013

# include «algorithm» // для min, max в Visual Studio 2013

# include «iostream» // Visual Studio 2013

using namespace std ;

const int N = 9 ; // Количество вершин в графе

const int INF = 100000 ; // Число большее длины любого пути в графе

>; // Дистанции (вес) в графе

int e [ N ]; // Эксцентриситет вершин

int c [ N ]; // Центры графа

int rad = INF ; // Радиус графа

int diam = 0 ; // Диаметр графа

for ( int k = 0 ; k N ; ++ k )

for ( int i = 0 ; i N ; ++ i )

for ( int j = 0 ; j N ; ++ j )

d [ i ][ j ] = min ( d [ i ][ j ], d [ i ][ k ] + d [ k ][ j ]);

for ( int i = 0 ; i N ; i ++) <

for ( int j = 0 ; j N ; j ++) <

e [ i ] = max ( e [ i ], d [ i ][ j ]);

// Нахождение диаметра и радиуса

for ( int i = 0 ; i N ; i ++) <

cout «Diameter: » diam endl ;

cout «Radius: » rad endl ;

for ( int i = 0 ; i N ; i ++) <

system ( «pause» ); // Visual Studio 2013

Остовные деревья

Задача. Построить все остовные деревья неориентированного графа из предыдущей задачи.

Алгоритм порождения всех каркасов неориентированного графа [Окулов С. М. Программирование в алгоритмах [Электронный ресурс] / С. М. Окулов.—5-е изд. (эл.).—М. : БИНОМ. Лаборатория знаний, 2014.—383 с.] реализован на C ++ в Visual Studio 2013:

using namespace std ;

const bool Zero = 0 ; // Ноль

const int N = 9 ; // число узлов графа

bool Nnew [ N ]; // признак, просмотрена вершина графа или нет

int Turn [ N ]; // очередь

int Tree [ 2 ][ N ]; // список ребер, образующих каркас

int Down ; // нижний указатель

int Up ; // верхний указатель

int numb ; // число ребер в строящемся каркасе

int AllTrees ; // Всего остовных деревьев

if ( Down >= Up ) return ;

// Просмотр ребер, выходящих из вершины v

// Ребро включаем в каркас, так как вершина с номером j еще не в каркасе

Turn [ Up ] = j ; Up ++; // Включаем вершину j в очередь

// Исключаем ребро из каркаса:

AllTrees = AllTrees + 1 ;

cout «Tree N= » AllTrees endl ;

for ( i = 1 ; i numb ; i ++)

cout Tree [ 0 ][ i ] + 1 » » Tree [ 1 ][ i ] + 1 endl ;

/*Все ребра, выходящие из вершины с номером v, просмотрены.

Переходим к следующей вершине из очереди и так до тех пор,

пока не будет построен каркас.*/

Solve ( Turn [ Down ], 1 );

Turn [ 0 ] = 0 ; Down = 0 ; Up = 1 ; // в очередь первую вершину

cout » » A [ i ][ k ]; // Матрица смежности графа

cout «All trees: » AllTrees endl ;

cout «Press any key » endl ;

Конец выполнения программы:

Остов минимального веса. Алгоритм Крускала

Остовом минимального веса является остов, содержащий ребра с минимальным весом.

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

Элементы теории кодирования. Схема кодирования и декодирования

Кодирование сообщения кодом, контролирующим ошибки ( d ≥ 3). Например, кодом Хэминга.

Передача по информационному каналу или хранение сообщения (могут появиться ошибки).

Оценка кодового слова и исправление ошибок при их наличии средствами контроля и исправления ошибок кода.

Выходное сообщение = исходному сообщению.

Код Хэмминга

Пусть r – контрольные биты (разряды, символы, позиции), тогда

n = 2 r – 1 – длина кодовых слов,

k = 2 r – 1 – r = n – r – число информационных битов,

d – минимальное кодовое расстояние (число позиций, в которых отличаются любые два кодовых слова между собой), для кода Хэмминга d = 3.

Примеры кодов Хэмминга:

Граница Синглтона линейного кода

Граница Синглтона, названная в честь Сиглтона Р. К., устанавливает минимальное число контрольных символов в коде, контролирующем ошибки.

Пример двоичного кода, состоящего из 2 битов (разрядов, символов, позиций):

Список использованных источников с моими комментариями

Окулов С. М. Программирование в алгоритмах [Электронный ресурс] / С. М. Окулов.—5-е изд. (эл.).—М. : БИНОМ. Лаборатория знаний, 2014.—383 с.

Дискретная математика для школьников с алгоритмами на Паскале.

Зуев Ю.А. По океану дискретной математики: от перечислительной комбинаторики до современной криптографии. 2 тома. – М.: «Либроком», 2012.

Захарова Л.Е. Алгоритмы дискретной математики: Учебное пособие. – Моск. гос. ин-т электроники и математики. М., 2002, 120 с.

На Паскаль реализованы многие алгоритмы, графы. Имеется не большой список литературы, который полезно просмотреть.

Верещагин Н.К., Шень А. Лекции по математической логике и теория алгоритмов. Часть 1. Начала теории множеств. М.: МЦНМО, 1999. 128 с.

Хорошо представлена теория множеств, но некоторые значки не привычные.

Верещагин Н.К., Шень А. Лекции по математической логике и теория алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМО, 1999. 176 с.

Кирсанов М. Н. Графы в Maple. Задачи, алгоритмы, программы. — М.: Издательство ФИЗМАТЛИТ, 2007. — 168 с.

Лаконично описана теория графов

Подробно теория графов и алгоритмы определения радиуса, диаметра, центров графа

Альпин Ю.А., Ильин С.Н. Дискретная математика: графы и автоматы. Учебное пособие. — Казань: Казанский государственный университет им. В.И. Ульянова-Ленина, 2006. — 78 с

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

Публикации результатов творчества. Как написать и опубликовать научную статью, подать заявку на изобретение, написать, издать книгу. Теория написания, защиты диссертаций. Зарабатывание денег на идеях, изобретениях. Консультирование при создании изобретений, написании заявок на изобретения, научных статей, заявок на изобретения, книг, монографий, диссертаций. Соавторство в изобретениях, научных статьях, монографиях.

Теоретическая механика (теормех), сопротивление материалов (сопромат), детали машин, теория механизмов и машин (ТММ), технология машиностроения, технические дисциплины.

Теоретические основы электротехники (ТОЭ), электроника, основы цифровой, аналоговой электроники.

Подготовка студентов по физике, математике, информатике, школьников желающих получить много баллов (часть C) и слабых учеников к ОГЭ (ГИА) и ЕГЭ. Одновременное улучшение текущей успеваемости путем развития памяти, мышления, понятного объяснения сложного, наглядного преподнесения предметов. Особый подход к каждому ученику. Подготовка к олимпиадам, обеспечивающим льготы при поступлении. 15-летний опыт улучшения успеваемости учеников.

Высшая математика, алгебра, геометрия, теория вероятностей, математическая статистика, линейное программирование.

Аналитическая геометрия, начертательная геометрия, инженерная графика, черчение. Компьютерная графика, программирование графики, чертежи в Автокад, Нанокад, фотомонтаж.

Логика, графы, деревья, дискретная математика.

OpenOffice и LibreOffice Basic, Visual Basic, VBA, NET, ASP.NET, макросы, VBScript, Бэйсик, С, С++, Делфи, Паскаль, Delphi, Pascal, C#, JavaScript, Fortran, html, Маткад. Создание программ, игр для ПК, ноутбуков, мобильных устройств. Использование бесплатных готовых программ, движков с открытыми исходными кодами.

Создание, размещение, раскрутка, программирование сайтов, интернет-магазинов, заработки на сайтах, Web-дизайн.

Информатика, пользователь ПК: тексты, таблицы, презентации, обучение методу скоропечатания за 2 часа, базы данных, 1С, Windows, Word, Excel, Access, Gimp, OpenOffice, Автокад, nanoCad, Интернет, сети, электронная почта.

Устройство, ремонт компьютеров стационарных и ноутбуков.

Видеоблогер, создание, редактирование, размещение видео, видеомонтаж, зарабатывание денег на видеоблогах.

Понятное объяснение теории, ликвидация пробелов в понимании, обучение приемам решения задач, консультирование при написании курсовых, дипломов.

Выбор, достижение целей, планирование.

Обучение зарабатыванию денег в Интернет: блогер, видеоблогер, программы, сайты, интернет-магазин, статьи, книги и др.

Вы можете поддержать развитие сайта, оплатить консультационные услуги Ольшевского Андрея Георгиевича

Источник

Дискретные структуры: матан для айтишников

Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.

Хотя раньше такого понятия, как «дискретная математика» вовсе не было, это не значит, что не возникало дискретных задач: Абель, Дирихле, Фибоначчи, Эйлер, чьи имена возникают по ходу изучения дискретной математики, — отнюдь не наши современники! Но просто в те времена для выделения самостоятельной ветви математики ещё не сложилось критической массы задач и приёмов, не было видно взаимосвязей между ними. А большое количество плодотворных взаимосвязей между, на первый взгляд, различными понятиями, — то, что математики в своей науке очень ценят.

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?

Зачем это айтишнику

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

Рекурсия — это, дословно, возврат, обращение к самому себе. Хорошо известные вездесущие числа Фибоначчи проще всего определяются рекурсивно: первые два числа Фибоначчи равны единице, а каждое следующее число равно сумме двух своих предшественников: 1,1,2,3,5,8,… Таким образом, для вычисления очередного числа мы обращаемся к уже рассчитанным числам такого же вида. Трудно представить, как можно изучить функциональное программирование, да и многое из других областей информатики, не освоившись хорошо с рекурсией. Очень близкий процесс к рекурсии — это индукция, способ доказательства математических утверждений, при котором в доказательстве сложных случаев мы опираемся на более простые. Параллели с рекурсией очевидны, и действительно, обычное дело, когда индуктивное доказательство существования какого-то объекта можно переформулировать в описание рекурсивного способа построения этого объекта.

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

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

Ещё одно архиважное умение — считать точно и оценивать приблизительно количества. Например, как вычислить количество раз, которые выполняется операция сравнения в цикле:

Или вот ещё пример. Нужно из списка из 100 товаров выбрать 20, так, чтобы их суммарная стоимость была ровно 2000 рублей («без сдачи»). Это вариант классической задачи о рюкзаке. Допустим, ваш коллега, подумав ночь, предложил решать задачу перебором: перебрать всевозможные наборы из двадцати товаров, и, как только в ходе перебора возникнет нужный набор, выдать его в качестве ответа. Между прочим, характеристика «переборный» далеко не всегда ставит клеймо на алгоритме. Всё зависит от размера входных данных. Так вот, как прикинуть, удастся ли за разумное время решить перебором эту задачу выбора 20 объектов из 100?

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

Онлайн-курс «Дискретные структуры»

С верой в то, что перечисленные понятия из дискретной математики действительно не помешают любому программисту, а, скорее, помешает их незнание, я читаю соответствующий курс на факультете ФИВТ МФТИ. А недавно у меня появилась возможность сделать онлайн-курс, чем я с радостью воспользовался. Записаться на него можно по ссылке. Главное, чего я пожелаю всем записавшимся: не побоявшись трудностей, пройти курс до самого конца, и получить заслуженное звание Дипломированного Дискретчика. В общем, чтобы MOOC прошёл без мук и обогатил знаниями! Да и собственная корысть у меня тут тоже есть: чем больше онлайн-учеников у меня будет, тем большему я смогу научиться, читая обсуждения и наблюдая статистику решения задач. Ведь учиться учить тоже никогда не поздно!

Какие знания потребуются

Для прохождения первых двух модулей потребуются только школьные знания. Третий модуль потребует знание основ математического анализа на уровне «что такое предел» и «какая из функций x 20 или 2 x растёт быстрее (чему равны производные функций)». Для последних трёх модулей понадобится представление о том, что такое вероятность, условная вероятность, математическое ожидание, дисперсия. Также хорошо бы знать, что такое базис и размерность линейного пространства. Если с вероятностью и линейной алгеброй вы не знакомы, можно записаться заодно на эти вводные курсы. Тогда как раз, к моменту, когда нам потребуются эти знания, они у вас будут.

Post scriptum

Меня можно было бы упрекнуть в конфликте интересов, всё-таки я математик, и, естественно, хочу приобщить к своей секте как можно больше завсегдатаев Хабра. В своё оправдание могу сослаться на этот ответ на Quora. Под большей частью тем, перечисленных в этом ответе, я готов лично подписаться, в онлайн-курс многие из них вошли. Ещё сошлюсь на подборку мнений яндексоидов.

Источник