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

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

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

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

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

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

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

Логика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⌘ ⌘ ⌘

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

• Курс Основы дискретной математики закрывает большую часть тем, рекомендую. Рассчитан на два месяца.
• Теорию сложности можно посмотреть в курсе Введение в дискретную математику, четвёртый модуль.
• Основы линейной алгебры очень доступно рассказаны в курсе Machine Learning, первая неделя, модуль Linear Algebra Review.

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

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