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

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

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

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

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

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

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

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

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

Дискретная математика и комбинаторика. Джеймс Андерсон

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

Особое внимание автор уделил теории доказательств. Все подкреплено примерами

А в конце учебника можно найти упражнения и позаниматься.

Автор рекомендует читать книгу преподавателям и студентам технических специальностей. Также по этому учебнику можно самостоятельно изучить дискретную математику.

Базовые термины

По сути, вся линейная алгебра вертится вокруг нескольких понятий: векторы, скаляры, тензоры и матрицы, — всё это очень важно для машинного обучения, ведь благодаря им можно абстрагировать данные и модели. Например, каждая запись в каком-нибудь наборе данных может быть представлена в виде вектора в многомерном пространстве, а параметры нейронных сетей абстрагируются как матрицы

Каждое из понятий по своему специфично, так что рассмотрим их подробнее.

Скаляр

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

Вектор

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

Матрица

Матрица — это двумерный массив скаляров. Обозначается жирным шрифтом в верхнем регистре. Например, если говорить о матрице из вещественных чисел, где m рядов и n столбцов, записывается такая матрица вот так:Поскольку матрица — двумерный массив, элементы матрицы имеют два индекса:Две матрицы могут быть сложены или вычтены одна из другой, только если у матриц одинаковое количество рядов и столбцов. Две матрицы могут быть перемножены только тогда, когда количество столбцов первой матрицы соответствует количеству рядов второй. Например, вы можете умножить матрицу A размера m, n на матрицу B размера n, p. В результате вы получите матрицу C размера m, p. Формула умножения выглядит вот так:

Важно заметить, что матричное произведение дистрибутивно и ассоциативно:

Однако, иногда может понадобиться перемножить элементы матриц между собой. Такую операцию называют произведением Адамара (обозначается  A ∘ B). Матрицы также можно умножать на векторы и на скаляры. Интересно, что произведением матрицы и вектора будет вектор:

Тензор

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

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

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

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

Нормы

Иногда для работы с вектором нужно знать его размер. Для этого существуют специальные функции, которые называют нормами — Ln. Маленькая буква n обозначает количество измерений, в которых находится вектор. В зависимости от того, сколько измерений в вашем векторном пространстве, нормы будут разными. Наиболее известная норма — норма двумерного пространства (Евклидова норма). Чаще всего она представляет собой Евклидово расстояние от начала вектора до точки в пространстве, находящейся на конце этого вектора. При обобщении пространства на несколько измерений используют глобальную норму:На самом деле, нормой может быть любая функция, удовлетворяющая следующим требованиям:

1. f(x + y) ≤ f(x) + f(yv) (удовлетворяет неравенству треугольника).
2. f(ax) = |a| f(x) (является абсолютно масштабируемой).
3. Если f(x) = 0, то x = 0 (определена положительно).

Часто, когда вы создаёте ИИ-приложение, очень важно различать элементы, равные 0, и элементы, имеющие значение, близкое к 0. Для этого используется норма L1

Она проста и растёт с одинаковой скоростью во всех точках векторного пространства. Если любой элемент вектора x движется от 0 к a — эта функция вырастает на a:Как упоминалось выше, в глубоком обучении параметры нейронных сетей абстрагируются как матрицы. Следовательно, нужно знать размер матрицы, и с этим нам поможет норма Фробениуса:

Пространство элементарных исходов

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

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

Кроме того, рассматривают множества элементарных исходов — события (например, попадание в «десятку» — это концентрический круг маленького радиуса с мишенью). В дискретном случае всё достаточно просто: мы можем получить любое событие, включая или исключая элементарные исходы за конечное время. В непрерывном же случае всё гораздо сложнее: нам понадобится некоторое достаточно хорошее семейство множеств для рассмотрения, называемое алгеброй по аналогии с простыми вещественными числами, которые можно складывать, вычитать, делить и умножать. Множества в алгебре можно пересекать и объединять, при этом результат операции будет находиться в алгебре

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

Источники

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

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

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

Логика

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

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

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

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

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

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

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

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

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

Какие разделы математики нужны программисту? Речь идет в основном о дискретной

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

Далее рассмотрим каждую дисциплину отдельно.

Информатика

В школах курс информатики состоит из примерно таких уроков:

• как включить компьютер;
• как выключить компьютер;
• как открыть/создать/удалить папку;
• как работать в MS Word;
• как писать программы на Pascal и HTML в тетради.

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

Полезная литература:

• Иванов Б.Н. «Дискретная математика. Алгоритмы и программы. Расширенный курс».
• Есипов&nbspА. «Информация и информационные технологии».

Нужно: желающим.

Миф №3: язык программирования нужен для составления алгоритмов

— Правда, многие из нынешних языков программирования уже содержат «в себе» набор заранее составленных алгоритмов, которые разработчик может использовать в качестве готовых. Поэтому язык всё же немного облегчает процесс составления алгоритмов.
— То есть, если один программист составил какой-то алгоритм, то его тут же могут использовать другие?
— Да, и это происходит постоянно. Это одна из причин, почему отрасль IT так быстро развивается. Однако новые алгоритмы приходится составлять самому.
— А составь какой-нибудь прямо сейчас!
— Легко. Классический пример: у вас есть книга, в ней 1000 страниц. Вам нужно открыть в ней, к примеру, 875-ю страницу. Как бы вы стали это делать?
— Ну, просто пробежал от первой до 875-й, только и всего.
— Угу, и придётся тебе глядеть на номер каждой страницы. А представь, если все их уголки слиплись — сколько времени тогда пройдёт? А вот мне достаточно перебрать лишь 3 страницы!
— Как?
— Вначале я выберу страницу, которая находится посередине книги, то есть 500-ю. Потом посмотрю: в какую из образовавшихся половин должна попасть искомая страница?
— Во вторую. А дальше что?
— То же самое. Интервал с 500-й по 1000-ю я снова поделю надвое, открыв центральную страницу. Получится интервал от 750-й страницы до 1000-й, в нём я опять выберу центральную. Какой будет номер?
— 750 плюс 125… Так это же и есть 875!
— Вот видишь. Всего 3 действия! Даже если я буду не совсем точен при выборе центральной страницы, я всё равно найду нужную намного быстрее тебя. Этот алгоритм носит название «дихотомия». Хотя в реальности программисты используют куда более сложные алгоритмы.
— И ты можешь записать его на бумаге?
— Конечно. Где там моя ручка? — Ну как, алгоритм ясен?
— Хм… Да, и впрямь ясен.
— Сейчас он записан в виде, уже слегка похожем на реальный программный код.
— А в чём отличия?
— В реальном коде все слова будут написаны на английском, а также будет заранее описана структура «книга» (помните, что я раньше рассказывал про структуры данных?). Плюс, для действий «ищем» и «удаляем» тоже будут составлены свои алгоритмы. Но в целом — всё то же самое.
— И ты занимаешься этим изо дня в день?
— В основном.
— И тебе не скучно?
— Ничуть!

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

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

Миф №2: машина умеет думать

— В общем, код любой программы представляет собой набор команд, а компьютер их тупо исполняет.
— То есть, он не понимает сути самих команд? Но как он воспринимает текст, который я ввожу на экране?
— Когда ты крутишь педали на велосипеде — понимает ли он, что ему сейчас нужно поехать вперёд?
— Нет, но ведь едет. Поскольку его цепь преобразует вращение педалей во вращение колёса.
— Именно! Также и компьютер преобразует введённый тобой текст в набор чисел.
— Каким образом?
— У каждого символа текста есть свой числовой код, который знает компьютер. Это называется кодировкой. Например, английская «a» кодируется числом 97, а знак равенства — числом 61.
— Поэтому машина и может понимать текст, который мы ей сообщаем?
— Нет, она «понимает» не смысл. А лишь то, каким образом этот текст хранить, и как к нему обращаться.
— Выходит, сначала мы вводим текст, затем компьютер разбивает его на символы, а каждый символ уже представляет в виде числа?
— Верно. Сложные структуры представляются в виде более простых, которые и «понимает» машина.
   Скажите мне, из чего состоит жилой дом?
— Ну… Из этажей.
— А из чего состоят этажи? И так далее.
— Этажи — из стен. А стены — из кирпичей. А кирпичи…
— Вот числа для компьютера — это то же, что и кирпичи для дома. Символы — это стены. Отдельные предложения — этажи. А книги — целые дома! Но у программистов есть преимущество перед строителями.
— Какое?
— Строитель не может строить целыми этажами, он вынужден всегда класть кирпичи. Даже если некий сверхмощный подъёмный кран позволит ему строить готовые этажи, он не сможет строить им целые дома или жилые кварталы. А программист сможет! Раз он уже «обучил» машину понимать конечный текст — то, по сути, он «обучил» подъёмный кран строить готовый дом за одно действие.
— То есть, программист может использовать всё более и более сложные структуры данных?
— Да. Поэтому первая из составляющих его работы — представить понятные человеку данные (текст, изображение, звук) в виде объединения более простых данных, уже понятных компьютеру. Разработчик практически «с нуля» составляет структуру, которая должна полностью описывать понятную человеку вещь — причём таким образом, чтобы эта структура была легко расширяемой и изменяемой (ведь в программу часто приходится вносить какие-то новые возможности).
— Хех! Выходит, что он строит резиновые дома из съёмных панелей!
— Примерно так. Однако, ещё ему придётся не только описать, что же ему нужно построить — но и как всё это построить. То есть, придумать алгоритм. Это вторая из составляющих его работы.
— Программист придумывает алгоритм на каждое действие?
— Именно. Поэтому алгоритмов получается очень много. Но его работу облегчает то, что одни действия могут содержать в себе другие, уже описанные им ранее.
— И здесь ему на помощь приходит язык программирования?
— Не совсем…

Операции

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

Транспонирование матрицы

В результате выполнения этой операции появляется так называемая транспонированная матрица. По сути, это зеркальное отображение матрицы по главной диагональной линии, которая начинается в верхнем левом и идёт в правый нижний угол. Транспонированной матрицей от матрицы A будет матрица AT (также A′, Atr, tA или At). Кроме того, транспонированную матрицу можно получить, записав ряды матрицы A как столбцы матрицы AT, а столбцы матрицы A — как ряды матрицы AT.

Умножение единичной матрицы на вектор

Существует такое понятие как единичная матрица. Если умножить её на вектор, значения вектора не меняются. Элементы главной диагонали единичной матрицы имеют значение 1, а все остальные равны 0:

Перед тем, как вы продолжите, немного информации о диагональной матрице (она очень похожа на единичную). Все элементы матрицы, за исключением тех, что находятся на главной диагонали, равны нулю. Но, в отличие от единичной, на главной диагонали диагональной матрицы элементы имеют значение, не равное 1. Получается, единичная матрица — это вид диагональной матрицы. Они очень полезны для некоторых алгоритмов.

Умножение на обратную матрицу

Обратная матрица определяется следующим образом:

Если умножить матрицу A на обратную ей матрицу A-1, получится единичная матрица. Обратная матрица похожа на обратное число. То есть для a обратным числом будет 1/a. Если обычное число умножить на обратное ему, получится единица: a * 1/a = 1. Здесь то же самое, только с матрицами. Но, увы, это работает только с квадратными матрицами.

Псевдоинверсия Мура-Пенроуза

Для неквадратных матриц нужно применять псевдоинверсию Мура-Пенроуза:Где U, D и V — сингулярное разложение матрицы A. Псевдоинверсия D+ матрицы D создаётся путём взятия элементов, обратных элементам матрицы, и её дальнейшим транспонированием. Но будьте осторожны с концепцией обратной матрицы A-1, потому что пока что она больше используется в теории, чем на практике. Это обусловлено тем, что вычислительные способности современных компьютеров позволяют дать лишь приблизительный ответ.

Преобразование матрицы в скаляр

Бывает, что нужно преобразовать матрицу в скаляр, для этого нужно найти определитель, он обозначается или . Так как преобразование возможно только с ними, вот пример с матрицей 2×2:Напоследок про линейную зависимость. Набор векторов будет линейно зависим, если хотя бы один вектор может быть представлен как комбинация других векторов из набора. Иначе набор будет линейно независим. Обычно векторы x и y будут линейно независимы, только если значения для скаляров a и b, удовлетворяющих ax + by = 0, будут равны a = b = 0.

Кое-что о числах

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

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

Вообще класс, пишем блочный тест с помощью JUnit для массива:

Все работает, даст 3, все как положено — давай в продакшен. За такое реально можно лишиться работы… Есть нечто, чего я до сих пор не могу понять. Почему разработчики компилятора разрешают компилировать этот код без ошибок и предупреждений? Давай возьмем другой массив:

Вроде бы почти все то же самое, но вернет… 0. Почему так? Давай просто выведем массив на экран:

Одна из первых вещей, которые должен знать любой программист: никогда, ни при каких обстоятельствах нельзя сравнивать числа с плавающей точкой на равенство. Почему вообще так происходит? Потому что так устроено двоичное представление чисел с плавающей точкой :). Только на эту тему можно написать не одну, а несколько статей. Здесь я не буду приводить лишних умных слов, таких как «машинный эпсилон», а просто дам рекомендацию для сравнения двух чисел: если , то можно считать их равными. Величину eps можно подобрать исходя из задачи (это просто достаточно малое число). Вообще, с числами в компьютере связано много интересного, а с числами с плавающей точкой особенно, потому что далеко не все понимают, как это на самом деле работает. Вот прекрасный пример (тоже из Java): выражение вернет !

Многие читатели знают слова «мантисса» и «экспонента», а подробное описание подобных эффектов явно выходит за рамки статьи, так что я всего лишь дам полезные ссылки для начала:

• IEEE 754;
• Пара слов о числах с плавающей точкой в Java.

Здесь же просто отмечу кое-какие полезные факты. Числа с плавающей точкой и целые числа ведут себя по-разному в одних и тех же ситуациях. К примеру, деление на 0 в случае целых чисел приводит к возникновению исключения, а вот в случае чисел с плавающей точкой — к появлению значений , и (если 0,0 разделить на 0). Переполнение также работает по-разному:

В предыдущем примере у нас была функция . Кстати, функция вычисления абсолютного значения интересна сама по себе, особенно для целых чисел (для разных типов используются разные функции), и может создать тебе очень большие проблемы (особенно в больших проектах). Предлагаю подумать о том, всегда ли модуль возвращает корректный результат, то есть можем ли мы вообще полагаться на то, что результат модуля всегда больше либо равен 0? Ведь этому нас учат в школе и в университете. Проблема в том, что даже целые числа хранятся в памяти так, что что-нибудь не работает. Подумаем в этом направлении, возьмем любое целое со знаком: пусть 32 бита, диапазон значений такого числа от –2^31 до 2^31 – 1.

Кто-нибудь видит проблемное место? Отрицательная часть длиннее положительной! На практике это означает, что «заведомо положительное» число равно –2 147 483 648.