Математика для программиста

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

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

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

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

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

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

Почитайте:

Рона Хаггарти «Дискретная математика для программистов»

Логика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А вы как считаете нужна математика для программиста? Если не то почему? Ждём ваших ответов в нашем чате