Для чего нужна дискретная математика

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

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

Как изучать математику

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

21 ноября в 10:50, онлайн, беcплатно

В освоении математики есть два уровня понимания. Первый уровень — идейный. Это осознание того, для чего нужны определенные объекты, какая задача решается и где это используется. Второй уровень понимания — детальный; это подробное изучение подробностей решения задачи. Иногда нужно разобраться в задаче на детальном уровня понимания, но в большинстве случаев — достаточно идейного.

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

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

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

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

Логика

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

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

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

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

Ресурсы:

• На Codeforces в разделе «Архив» стоит потренироваться на задачах как минимум класса С — многие из них содержат подводные камни;
• Проект The KeY to Software Correctness подойдет тем, кому интересно, как можно автоматически доказывать правильность работы кода. Он автоматизирует проверку кода на Java;
• Автоматический доказатель теорем z3, написанный Microsoft, для тех, кто пользуется другими языками. Краткая инструкция по его использованию находится на ресурсе rise4fun.

Комбинаторика

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

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

Ресурсы:

• С основами можно ознакомиться на сайте Mathprofi, который посвящен прозрачному и популярному описанию математики;
• Если вы владеете английским, можете посмотреть более продвинутую книгу An Introduction to Combinatorics and Graph Theory;
• Задачи по комбинаторике можно взять из задачника «Дискретная математика», в конце есть ответы.

Теория вероятностей

Иногда на собеседовании интервьюер, дабы проверить насколько крут кандидат, задает такую задачу: «Вот у нас есть отрезок, который начинается с числа А и заканчивается числом Б. Мы кидаем на него две точки случайным образом. Какая будет средняя длина наибольшего отрезка?» или же «Пусть у нас есть треугольник, на вершине которого сидит муха. Пусть она перелетает с вершины на вершину за 3 секунды и отдыхает на каждой вершине по секунде, каждый раз случайно выбирая себе путь. Через какое время она в среднем вернется в начальную точку?».

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

Теория вероятности делится на две части: дискретную и непрерывную. Хотя в теории дискретная — это подкласс непрерывной, методы решения задач несколько различаются. Опять же лучше начинать с простого — дискретная теория вероятности часто сводится к комбинаторным задачам. И теоретическая часть у дискретной формулируется проще.

Непрерывная теория вероятности для полного понимания требует знания элементарных основ мат. анализа, в частности понятия интеграла, хотя многие задачи требуют лишь умения считать площади простых фигур. Именно непрерывная теория вероятности является фундаментом для математической статистики и машинного обучения. Поэтому, если хотите работать в этой области, стоит начать с изучения книги Ричарда Хэнсена Probability Theory and Statistics или Probability Theory with Simulations.

Ресурсы:

• MathProfi — сайт, на котором доступно и просто изложена высшая математика. На нём есть множество разделов с теорией, таблицами и задачами, в том числе и по теории вероятностей
• Книга Чарльза М. Гринстеда и Лори Снелла Introduction to Probability.

Теория графов

Слышали ли вы задачу о мостах Кенигсберга?

«Можно ли пройти по всем семи мостам города Кенигсберга, не проходя по каждому из них дважды?». Нам известно, что ответ на эту задачу — нет. Решить подобные задачи помогает теория графов.

Графы — это очень удобные формализованные представления нелинейных структур, которые довольно часто встречается в прикладных задачах. В отличие от простых линейных структур, таких как массивы или списки, работа с графами более сложна.

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

Ресурсы:

• Познакомиться с основными понятиями можно в краткой методичке «Введение в теорию графов»;
• По части алгоритмов можно заглянуть на сайт e-maxx и наш;
• Практиковаться можно на задачах с Codeforces, там есть задачи на графах.

Теория чисел и криптография

Задумывались ли вы, почему к простым числам такой большой интерес? Почему работает шифрование RSA? Чем отличается http от https и что такое сертификат безопасности?

Все эти вопросы изучает криптография. Сразу скажем, что эта наука достаточно сложная и не интуитивная — бывает непонтяно, как реализовать тот или иной алгоритм совершенно безошибочно. Тем не менее алгоритмы в криптографии не могут быть «чуть-чуть нерабочими». Малейшая ошибка может привести к компрометации всей криптографической системы.

Дискретная оптимизация

Чтобы найти экстремум (максимум либо минимум) функции, надо взять ее производную и приравнять к нулю. Решение уравнения дает локальный экстремум. Но если вам нужно искать максимум не на каком-то промежутке, а только по целым числам, то вам уже нужно будет задумываться о том, какое из соседних целых чисел нужно выбрать. Когда задача многомерная, вариантов с целыми числами становится все больше, и выбирать приходится из все увеличивающегося количества. Но бывают случаи еще хуже — когда вовсе нет никакой непрерывной функции, от которой можно было бы взять производную. Или же когда количество вариантов очень велико (в том случае, когда сами варианты нужно вычислять).

Бывает, что в таких задачах нельзя найти точное решение за приемлемое время — его можно получить только полным перебором. Такова, например, задача Коммивояжера, или задача линейного программирования. Иногда можно отказаться от точного решения, и использовать некоторые приближения. Обо всем этом можно узнать в курсе Discrete Optimization на Coursera.

Источники

Небезызвестная серия курсов Introduction to Discrete Mathematics for Computer Science на Coursera по дискретной математике. Она довольно обширна и дает общее представление о всех нужных областях дискретной математики — логике, комбинаторике, теории вероятностей, теории графов, теории чисел и криптографии. Последний курс затрагивает проблему дискретной оптимизации.

Кроме того, для тех, кому не очень нравится формат курсов, будет полезной книга Discrete Mathematics. An Open Introduction. Книга довольно большая и подробная, поэтому можно сделать упор на основных понятиях и определениях.

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

Что дальше?

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

Учусь на первом курсе ХНУРЭ на специальности Программная инженерия. Есть куча предметов и естественно есть не нужные. Не могу понять, нахера нужна ДМ?
1) Насколько важно высококвалифицированному программисту знать ее?

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

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

Области математики

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

Изучать приведенные в статье разделы математики до самых глубин не нужно. Достаточно знать основы и свободно в них разбираться. Если понадобятся более углубленные знания, их всегда можно получить из интернета.

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

Логика

Математик и программист – профессии, которые взаимосвязаны. Математику программирование, можно сказать, не нужно. Программисту разбираться во многих математических понятиях очень важно. Рассмотрим, чем полезна логика.

Компьютер состоит из материальных деталей и программного обеспечения. Все они не могут работать без математической логики. Сейчас она используется широко во время применения различных языков программирования, позволяя делать программы максимально удобными и нересурсозатратными. Что собой представляет утилита? Это последовательная система, которая выполняет команды, вшитые в нее или же поступающие с устройств ввода-вывода. Если рассматривать понятие «программа» более детально, то можно заметить участие логики во всем этом процессе.

В 30-х годах 19 века появились первые идеи вычислительной машины. Тогда логика стала одной из фундаментальных структур. Сам математический раздел начал стремительно развиваться в начале 20 века. Исследования, которые тогда были проведены, положили начало всем языка программирования, основанным на алгоритмическом выполнении команд.

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

Что касаемо более подробных разделов логики, которые стоило бы изучить, то нужно отметить булеву алгебру, логические переменные и операторы, таблицы истинности.

Комбинаторика

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

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

Также нужно отметить, что комбинаторика используется для работы маршрутизации в сетях. Искусственные нейронные сети также созданы на ее основе. Благодаря этому разделу математики происходит разработка искусственного интеллекта. Комбинаторика является неотъемлемой и в криптографии.

Следует отметить, что этот раздел математики требует развитого мышления, в чем помогает изучение логики. Как уже становится понятно, эти разделы связаны между собой и тесно переплетены. Именно поэтому их объединяют воедино под названием «дискретная математика».

Теория вероятностей

Те программисты, которые работают аналитиками данных, должны хорошо разбираться в теории вероятностей. Почему? Чтобы машинные методы работы не казались «волшебством», нужно разбираться в математической статистике. Она базируется на теории вероятностей.

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

Теория вероятностей в играх

Если программист собирается разрабатывать игры, а не сидеть в аналитическом отделе компании, ему все равно придется разобраться с теорией вероятности. Чтобы было понятно, зачем это нужно, рассмотрим простой случай. К примеру, объектом разработки является шутер. Механика стрельбы – практически главный элемент в таком программном проекте. Те шутеры, где оружие стреляет максимально точно, вряд ли понравится большинству игрокам. Поэтому следует добавлять разброс. Сделать точки максимально рандомными не следует. Это повлечет за собой проблемы с точной настройкой и нарушит игровой баланс. Если использовать знания из теории вероятности, то можно взять случайные показатели, а по их распределению сделать анализ того, как будет работать то или иное оружие с заданным разбросом. Так можно откорректировать игру.

Разбирая, какая роль математики в профессии программиста, относительно теории вероятности следует сказать, что благодаря этой науке создаются нейросети, биржевые торговые роботы, крипто-анализ и алгоритмы шифрования. Кроме того, машинное обучение – сфера, где использована математическая статистика и теория вероятности. Без них не обойтись.

Математическая статистика

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

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

Что изучать в теории вероятности и математической статистике

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

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

Линейная алгебра

Этот раздел математики поможет освоить языки программирования. Важные темы: матрицы и векторы, а также базовые операции над матрицами. Почему они так важны? В любом языке программирования при выполнении сложной задачи создается матрица значений. Она работает таким же образом, как и в математике. Чтобы уметь правильно оперировать функциями языка программирования, нужно как следует подучить математику.

Алгебра для игр

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

Теория графов

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

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

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

Изучать в этом разделе советуем графы и все, что с ними связано (вершины, ребра, подграфы). Также нужно обратить внимание на пути, циклы и маршруты. Следует разобраться с тем, какие операции могут совершаться над графами.

Теория сложности

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

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

Итоги

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