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

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

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

Проблема коммивояжера
Иногда математика и вовсе не нужна // xkcd

Сразу скажу, что если вы программируете игры или разрабатываете софт для физиков, медиков или биологов — этого не хватит. Но для «бизнесовых» и повседневных программ — с запасом.

Интересные программисту области относятся к дискретной математике. Более конкретно:

  • логика,
  • комбинаторика,
  • теория вероятностей и матстатистика,
  • линейная алгебра,
  • теория графов,
  • теория сложности.

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

Логика

Логические переменные и операторы. Булева алгебра. Таблицы истинности.

Вполне возможно, что это проходят ещё в школе — я уже не помню, что там было ツ

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

Размещения и сочетания. Бином Ньютона и биномиальные коэффициенты. Разбиения. Формула включений и исключений.

Теория вероятностей и матстатистика

События и их вероятности. Комбинации и последовательности событий. Зависимые события и теорема Байеса.

Меры среднего значения выборки: арифметическое среднее, медиана и процентили. Матожидание, дисперсия, стандартное отклонение.

Случайные переменные и их свойства. Распределение вероятности.

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

Матрицы и векторы. Базовые операции над матрицами.

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

Гравы, подграфы, вершины и рёбра. Маршруты, пути и циклы. Операции над графами. Деревья. Раскраски.

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

Логарифм и экспонента. Арифметическая, геометрическая и прочие суммы.

Скорость роста функций и алгоритмов. O-нотация. Анализ алгоритмов.

⌘ ⌘ ⌘

Теперь о том, где этому учиться.

Все курсы бесплатные.

За скобками остались алгоритмы и структуры данных, потому что их обычно относят к «computer science», а не математике. Напишу о них в другой раз.