Дискретная математика для программистов реферат

Обновлено: 01.07.2024

План
1) Математика в программирование.
2) Области математики
3) Логика
4) Комбинаторика
5) Теория вероятностей
6)Теория вероятностей в играх
7) Математическая статистика
8) Линейная алгебра
9) Алгебра для игр
10) Теория графов
11) Теория сложности
12) Итоги

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

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

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

Математическая статистика
Следует отметить, что статистика и теория вероятности взаимосвязаны. Первый раздел
базируется на втором. Как правило, в вузах они изучаются обязательно. Сначала преподаются
вероятности, потом уже благодаря полученным данным можно выучить статистику.
Используется этот раздел также часто, как и теория вероятности. Он нужен практически в тех
же сферах.
Математическая статистика – важная наука для любого программиста. Чтобы разобраться с ней,
нужно иметь гибкое мышление и быть усидчивым. Мало просто походить на курсы,
позаниматься с репетитором. Этого будет достаточно, чтобы выучить основы и базу. Чтобы
действительно начать разбираться в этой теме – нет. В программировании она играет огромную
роль. Именно благодаря статистике создаются динамические программы. Не всегда можно
знать конечную цифру в выполняемом цикле, так как все данные вводятся с клавиатуры. Здесь
поможет именно статистика. В любых неоднозначных задачах следует прибегать к помощи
этого раздела математики. Для программистов она - как волшебная палочка. Главное - уметь ею
пользоваться.

Линейная алгебра
Этот раздел математики поможет освоить языки программирования.
Важные темы: матрицы и векторы, а также базовые операции над
матрицами. Почему они так важны? В любом языке
программирования при выполнении сложной задачи создается
матрица значений. Она работает таким же образом, как и в
математике. Чтобы уметь правильно оперировать функциями языка
программирования, нужно как следует подучить математику.

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

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

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

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

Определение булевых функций. Замкнутые классы, теорема Поста. Моделирование релейно-контактных схем и сумматоров. Основные положения математической логики. Неформальное определение алгоритма. Конечные автоматы и некоторые классические алгоритмы.

Рубрика	Математика
Вид	учебное пособие
Язык	русский
Дата добавления	30.07.2013
Размер файла	1,1 M

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Программа - это последовательность команд, а именно,

Проверим потактно результаты применения команд:

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

Данный пример показывает, что функция

Пусть имеется множество

NxN - прямое (или декартово) произведение.

Функцией называется однозначное отображение

Область определения - это подмножество , для которого определено отображение

то функция называется частично определенной; если

то функция называется тотальной.

Функция называется частично вычислимой, если существует МНР-программа для её вычисления в области определения.

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

Функция называется вычислимой если:

- функция является частично вычислимой.

Характеристическая функция предиката

Рассмотрим предикат . Его характеристическая функция - это такая функция , которая принимает значение 1, если

Предикат называется разрешимым, если его характеристическая функция вычислима.

Понятие рекурсии связано с фамилиями таких ученых, как Клини и Черч. Клини ввел понятие частичной рекурсивной функции. Им высказана гипотеза: все частичные функции являются частично рекурсивными (эта гипотеза недоказуема).

В силу тезиса Черча вычислимость эквивалентна рекурсивности (этот тезис также недоказуем).

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

Функция является общерекурсивной или рекурсивной, если она частично рекурсивна и всюду определена.

Три простейшие функции теории:

- функция, которая позволяет добавлять к аргументу единицу;

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

Три простейшие операции теории:

1. Суперпозиция. Пусть заданы следующие функции:

Суперпозицией функции , построенной с помощью функции , называется функция от тех же аргументов

которая представляет собой следующее:

Пример 1. Заданы следующие функции:

Пример 2. Дана функция

Требуется представить ее в сокрашенном виде. Для этого введем отдельные функции:

Введем новое обозначение:

Исходная функция приняла следующий вид:

Введем следующие обозначения:

2. Примитивная рекурсия. Пусть заданы следующие функции: - местная

Построение примитивной рекурсии:

Замечание. В случае требуется некоторое уточнение:

Основная идея сводится к вычислению функции при значении аргумента на основании вычисления этой же функции при значении аргумента .

Основные функции являются рекурсивными.

Сложность состоит в подборе и .

Пример. Доказать, что функция

Построим рекурсивную функцию с помощью следующей конструкции:

3. -оператор. Рассмотрим функцию

В некоторых случаях

Корней может оказаться несколько. C помощью -оператора считается возможным реализовать следующую последовательность операций:

- находят все корни при заданном ;

- среди всех корней выбирают наименьший.

3.4 Вычислимость по Тьюрингу

Алану Тьюрингу принадлежит идея построения гипотетической вычислительной машины. Опишем основные положения формальной теории машины Тьюринга.

1. Внешний алфавит

2. Внутренний алфавит

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

4. Управляющая головка. На каждом такте управляющая головка находится напротив некоторой ячейки.

Работа машины Тьюринга описывается набором команд, имеющих синтаксис

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

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

Гипотетическая машина Поста строится сходным образом.

Команды теории Поста называются приказами. Считаются заданными (выполнимыми) шесть приказов:

1. Записать 1 и перейти к приказу .

2. Записать 0 и перейти к приказу .

3. Сдвинуть вправо и перейти к приказу .

4. Сдвинуть влево и перейти к приказу .

5. Если в ячейке 1, то перейти к приказу .

6. Если в ячейке 0, то перейти к приказу .

Более детальное рассмотрение показывает, что машины Тьюринга и Поста эквивалентны.

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

и в виде потока команд.

Пример 1. Рассмотрим работу машины Тьюринга, заданную следующей таблицей:

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

Итак, слово 111 преобразовалось в слово 1111. Это значит, что вычислимой по Тьюрингу является функция, прибавляющая к целому числу единицу.

Целью работы машины Тьюринга является преобразование некоторого исходного слова в заданное.

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

1) применить несколько машин Тьюринга (для каждой задачи);

2) оставаясь в рамках одной машины Тьюринга, записать входные слова в различных областях одной ленты; финальное состояние первой задачи отождествить со стартовым состоянием второй.

Универсальной машиной Тьюринга называется машина, реализующая все задачи в заданном алфавите. К. Шеннон поставил вопрос о сложности универсальной машины Тьюринга, определив сложность как произведение количеств внутренних и внешних состояний.

К настоящему времени установлено, что для построения универсальной машины Тьюринга достаточно располагать четырьмя внутренними и шестью внешними состояниями.

4. КОНЕЧНЫЕ АВТОМАТЫ

4.1 Основные определения и способы задания

Основной рассматриваемый объект - конечный автомат (КА).

состоящая из таких объектов:

- множество входных сигналов;

- множество выходных сигналов;

- множество внутренних состояний;

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

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

Переход из одного состояния в другое осуществляется потактно. Пусть номер такта обозначен как t. Тогда

- канонические уравнения для КА.

Пример. Если A и B - улицы, то

Рис. 4.1. Перекресток

Внутренние состояния: - движение по улице A; - движение по улице B; - пешеходный переход после движения по улице A; - пешеходный переход после движения по улице B.

Пусть алфавит выходов содержит буквы А, Б, П, тогда

Рис. 4.2 иллюстрирует графический способ задания автомата.

Рис. 4.2. Размеченный граф автомата регулирования перекрестка

Матричный способ заключается во введении матриц отношений и :

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

и матрицы выходов

Автоматное отображение сигналов задается следующим образом:

Таким образом, получаем отображение входного слова

в выходное слово

а - расширенная функция перехода

Свойства автоматного отображения:

Эти свойства называются свойствами (условиями) автоматности отображения.

Рис. 4.3 Размеченный граф отображения

Построить граф автомата, классифицировать состояния, продемонстрировать внешнее поведение для слова длиной 20 (табл. 4.1).

Таблица 4.1 Варианты задания

4.2 Эквивалентность автоматов. Минимизация

Рассмотрим два автомата:

Состояния из множества автомата и соответственно из множества автомата В называются неразличимыми, если

Автоматы и называются неразличимыми, если для любого состояния

Рассмотрим изменения состояний и выходов автомата с изменением времени. На каждом такте подается входной сигнал (символ), преобразуется внутреннее состояние, возникает сигнал выхода. Рассмотрим следующий такт. Действия аналогичны:

Итак, автомат преобразует слова (как и машина Тьюринга, частным случаем которой является конечный автомат).

Рассмотрим состояние автомата . Состояние называется достижимым из состояния , если существует такое слово , что

Достижимые состояния образуют класс достижимых состояний (рис. 4.4).

Рис. 4.4 Достижимое состояние (а) и класс достижимых состояний (б)

Рассмотрим два автомата

Автоматы называются эквивалентными, если

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

На начальном этапе отыскиваем классы -эквивалентных неразличимых состояний (при ):

Приходим к автомату, внутренние состояния которого отождествляются с найденными классами эквивалентных состояний:

У полученного и исходного автоматов внешнее поведение одинаково.

Воспользовавшись данными, приведенными в табл. 4.2, выполнить следующее:

а) построить граф для каждого из заданных автоматов (рекомендуется использовать VISIO);

б) минимизировать автоматы, построить графы, проверить правильность минимизаций на словах длиной 20;

в) установить, эквивалентны ли заданные автоматы, проверить на слове длиной 20.

Таблица 4.2 Варианты задания

4.3 Автоматы Мили и Мура. Размеченные графы

Рассмотренные ранее автоматы - это классические автоматы Мили. Автомат Мура - это автомат, выходы которого зависят только от текущего состояния:

- алфавит входных сигналов;

- алфавит выходных сигналов;

Автомат Мура - частный случай автомата Мили.

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

При табличном задании автомата Мура вместо двух таблиц рассматривается одна, которая называется размеченной функцией перехода:

Несколько изменяется представление графа. Обозначение выхода ставится возле каждого узла (рис. 4.5).

Рис. 4.5 Графическое представление автомата Мура

4.4 Автоматные языки

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

Частные случаи практически важных КА (конечных автоматов):

(автомат задержки - это автомат Мура);

Рис. 4.6 Граф распознавания заданного слова

По графу строим таблицу, описывающую работу автомата-распознавателя:

Далее подаем некоторую строку. Подстрока считается выявленной, если на выходе появляется единица:

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

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

Словарь - это конечное множество.

Элементы словаря - символы (буквы).

Предложение - все конечные последовательности символов из заданного словаря.

- множество всех цепочек, построенных по данному словарю.

Множество содержит бесконечное количество элементов.

Грамматика - конечный механизм задания языка.

Существует два вида грамматик - порождающая и распознающая: первая - это механизм, позволяющий строить все допустимые предложения, вторая - отсеивает из множества те предложения, которые не принадлежат языку.

Синтаксис - правила построения языка.

4.5 Возможности автоматов

Счетчик. Требуется создать устройство, которое на каждом такте выдает целое число, большее предыдущего на единицу; при достижении некоторого предельного значения серия выводимых значений повторяется. Пусть предельное значение равно шести. Автомат, реализующий алгоритм, является автоматом Мура и может быть описан в стандартном виде:

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

Первая из цифр выводится на экран, вторая подается на выход, являющийся входом для следующего счетчика. Если на вход второго счетчика подается 0, то его состояние не меняется и на выход подается пустой символ. Если же подается единица, то он изменяет состояние так же, как и рассмотренный выше счетчик:

Однако следует отметить, что счетчики рассмотренного типа не позволяют считать до бесконечности. Это ограничение принципиально для конечных автоматов. Однако данной схемы достаточно для реализации обычных электронных часов [1].

Счетчик является примером так называемых автономных автоматов, входной алфавит которых содержит единственный символ. Если считать, что в каждой вершине графа имеется один выход, причем выходной сигнал совпадает с номером состояния, то он является эквивалентом отношения порядка, а граф автономного автомата - это простой ориентированный граф [2, 3]. Для входного слова достаточной длины выходное слово автономного автомата содержит периодически повторяющееся подслово.

Прежде всего отметим, что выходной алфавит конструируемого автомата не может состоять только из нуля и единицы, так как количество символов во входном и выходном словах должно быть одно и то же (требование автоматности).

Это требование удовлетворяется введением такого выходного алфавита:

С использованием основных методов и понятий дискретной математики и математической логики проведены несколько типовых расчётов по корректности алгоритмов и процессов, написанных на языке программирования Pascal (структурированный и компилируемый язык программирования, является базой для многих других известных языков программирования), разобраны принцип и работа экспертной системы с использованием множеств и предикатов. С помощью логики высказываний описаны базовые алгоритмы решения и проверки задач, которые представлены перед программистом при проверке корректности программы и отдельных её частей, с использованием предикатов (функция с областью значений , определенная n-й декартовой степени множества M) и составлении экспертной системы создана простая база данных (знаний) для получения информации из базы данных о британских королях и королевах и объяснены основные понятия математической логики и дискретной математики, которые применяются в ней.

1. Бондаренко В.А., Цыплакова О.Н., Родина Е.В Использование компьютерных математических систем в обучении математике // Информационные системы и технологии как фактор развития экономики региона: сб. научных статей по материалам Международной НПК. – Ставрополь: АГРУС Ставропольского ГАУ, 2013. – С. 46–50.

2. Долгих Е.В., Тынянко Н.Н. Теоретические экономико-математические модели // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75-летию Ставропольского государственного аграрного университета / Отв. редактор: Н.В. Кулиш, 2005. – С. 553–556.

4. Зепнова Н.Н., Кузьмин О.В. Применение методов дискретной математики при решении логических задач // Омский научный вестник. – 2014. – № 2 (130). – С. 14–17.

6. Попова С.В., Колодяжная Т.А. Применение алгоритмов при обучении математике в вузе // Моделирование производственных процессов и развитие информационных систем / Даугавпилсский университет, Латвия, Европейский Союз Белорусский государственный университет, Беларусь Днепропетровский университет экономики и права, Украина Московский государственный университет им. М.В. Ломоносова, Россия, Санкт-Петербургский государственный политехнический университет Северо-Кавказский государственный технический университет Ставропольский государственный университет Ставропольский государственный аграрный университет. – Ставрополь, 2011. – С. 278–281.

7. Попова С.В., Смирнова Н.Б. Элементы алгоритмизации в процессе обучения математике в высшей школе // Современные проблемы развития экономики и социальной сферы: сборник материалов Международной научно-практической конференции, посвященной 75–летию Ставропольского государственного аграрного университета / Ответственный редактор: Н.В. Кулиш, 2005. – C. 526–531.

8. Смирнова Н.Б., Попова С.В. Основные принципы проектирования компьютерной математической модели // Сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75-летию СтГАУ / Ответственный редактор: Н.В. Кулиш, 2005. – С. 185–189.

9. Смирнова Н.Б., Попова С.В. Модели, подходы к классификации моделей // Экономика регионов России: анализ современного состояния и перспективы развития: сборник научных трудов по материалам Ежегодной 69-й научно-практической конференции, посвященной 75–летию СтГАУ / Ответственный редактор: Н.В. Кулиш, 2005. – С. 181–185.

10. Смирнова Н.Б., Попова С.В., Хачатурян Р.Е. Использование логической символики при обучении математике в вузе // Совершенствование информационных и коммуникационных технологий с целью активизации учебного процесса в вузе. – Ставрополь, 2006. – С. 191–195.

Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Большинство задач исследования операций (распределение ресурсов, сетевое планирование и управление, календарное планирование) описываются математическими моделями дискретного программирования [2, 9].

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

End

Поделим алгоритм на части и зафиксируем обозначения пред- и постусловий.

Подстановки показывают, что высказывания:

Таким образом, предикат

Алгоритм условных высказываний тоже поддается такому доказательству, необходимо только отразить альтернативные пути в алгоритме [6].

Предположим, что высказывание

if условие then

вводит предусловие P и в конце даёт условие Q. Поэтому необходимо доказать истинность двух предикатов:

Теория множеств используется для наиболее удобного описания массы концепций в информатике. Одним из примеров применения теории множества в программировании является база данных. Возьмём за пример экспертную систему [10].

Экспертная система создаётся с целью подмены собой специалистов в данной области. Реализуется это благодаря накоплению базы знаний известных событий с определением набора правил вывода, из-за чего ответы на запросы могут быть выведены логическим путём из базы знаний.

Родитель (Георг I, Георг II) жена (София, Георг I)

Родитель (Георг III, Георг IV) жена (Вильгельмина, Георг II)

Родитель (Георг III, Вильгельм IV) жена (Шарлотта, Георг III)

Родитель (Георг III, Эдвард) жена (Каролина, Георг IV)

Родитель (Эдвард, Виктория) жена (Аделаида, Вильгельм IV)

Родитель (Виктория, Эдвард VII) жена (Виктория, Альберт)

Родитель (Эдвард VII, Георг V) жена (Александра, Эдвард VII)

Родитель (Георг V, Эдвард VIII) жена (Виктория Мари, Георг V)

Родитель (Георг V, Георг VI) жена (Елизавета, Георг VI)

Родитель (Георг V, Елизавета II) жена (Елизавета II, Филипп)

Родитель (Виктория, Элис)

Родитель (Элис, Виктория Альберта)

Родитель (Виктория Альберта, Филипп)

Родитель (x, y) означает, что x является родителем y, а жена (x, y) означает, что x – жена y. Это стандартное чтение предикатов, используемых языками программирования, как, например, PROLOG [4].

Сформулируем правило вывода для получения информации о матерях из системы. Необходимо обозначить правило мать(x) так, чтобы положительный ответ на этот запрос формировался только в том случае, если x – жена чьего-то родителя или x – женщина и родитель. Правило такого вывода определяется таким образом:

Но данное правило вывода не найдёт всех матерей из-за того, что база данных не полная – в ней не записаны, например, дети Елизаветы Второй. Полученный результат показывает трудности, возникающие при попытках ограничения реального мира рамками математической модели [5, 8].

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

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

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

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

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

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

Логика

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

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

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

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

Дополнительные сведения о комбинаторике

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

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

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

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

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

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

Математическая статистика

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

Математическая статистика – важная наука для любого программиста. Чтобы разобраться с ней, нужно иметь гибкое мышление и быть усидчивым. Мало просто походить на курсы, позаниматься с репетитором. Этого будет достаточно, чтобы выучить основы и базу. Чтобы действительно начать разбираться в этой теме – нет. В программировании она играет огромную роль. Именно благодаря статистике создаются динамические программы. Не всегда можно знать конечную цифру в выполняемом цикле, так как все данные вводятся с клавиатуры. Здесь поможет именно статистика. В любых неоднозначных задачах следует прибегать к помощи этого раздела математики. Для программистов она - как волшебная палочка. Главное - уметь ею пользоваться.

Что изучать в теории вероятности и математической статистике

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итоги

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

Читайте также: