Математика для программиста
В университете меня три года пичкали функциональным анализом, дифференциальными уравнениями и теорией функций комплексного переменного. Считаю это преступлением против юности: как и большинству программистов, эти знания никогда не понадобились.
В этой заметке я расскажу, какие (небольшие) кусочки математики действительно пригодятся программисту и как их освоить за несколько месяцев. Если вы уже программируете — можно использовать как чек-лист для самопроверки.
Сразу скажу, что если вы программируете игры или разрабатываете софт для физиков, медиков или биологов — этого не хватит. Но для «бизнесовых» и повседневных программ — с запасом.
Интересные программисту области относятся к дискретной математике. Более конкретно:
- логика,
- комбинаторика,
- теория вероятностей и матстатистика,
- линейная алгебра,
- теория графов,
- теория сложности.
Сами по себе они довольно жирные, но программисту достаточно самых основ, углубляться не обязательно.
Логика
Логические переменные и операторы. Булева алгебра. Таблицы истинности.
Вполне возможно, что это проходят ещё в школе — я уже не помню, что там было ツ
Комбинаторика
Размещения и сочетания. Бином Ньютона и биномиальные коэффициенты. Разбиения. Формула включений и исключений.
Теория вероятностей и матстатистика
События и их вероятности. Комбинации и последовательности событий. Зависимые события и теорема Байеса.
Меры среднего значения выборки: арифметическое среднее, медиана и процентили. Матожидание, дисперсия, стандартное отклонение.
Случайные переменные и их свойства. Распределение вероятности.
Линейная алгебра
Матрицы и векторы. Базовые операции над матрицами.
Теория графов
Гравы, подграфы, вершины и рёбра. Маршруты, пути и циклы. Операции над графами. Деревья. Раскраски.
Теория сложности
Логарифм и экспонента. Арифметическая, геометрическая и прочие суммы.
Скорость роста функций и алгоритмов. O-нотация. Анализ алгоритмов.
⌘ ⌘ ⌘
Теперь о том, где этому учиться.
- Курс Основы дискретной математики закрывает большую часть тем, рекомендую. Рассчитан на два месяца.
- Теорию сложности можно посмотреть в курсе Введение в дискретную математику, четвёртый модуль.
- Основы линейной алгебры очень доступно рассказаны в курсе Machine Learning, первая неделя, модуль Linear Algebra Review.
Все курсы бесплатные.
За скобками остались алгоритмы и структуры данных, потому что их обычно относят к «computer science», а не математике. Напишу о них в другой раз.
★ Подписывайтесь на новые заметки.