Oc-windows.ru

IT Новости из мира ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Программирование для математиков

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

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

  • Статьи , 20 мая 2018 в 18:51
  • Типичный программист

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

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

Как изучать математику

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

В освоении математики есть два уровня понимания. Первый уровень — идейный. Это осознание того, для чего нужны определенные объекты, какая задача решается и где это используется. Второй уровень понимания — детальный; это подробное изучение подробностей решения задачи. Иногда нужно разобраться в задаче на детальном уровня понимания, но в большинстве случаев — достаточно идейного.

20 апреля , онлайн, 10 900–29 800 ₽

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

Дискретная математика

Область математики, которая занимается дискретными структурами (например: графами, автоматами, утверждениями в логике). Основное ее отличие от обычной математики, которую вы изучали в школе, — ее объекты не могут изменяться так же гладко, как и вещественные числа.

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

Логика

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

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

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

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

Ресурсы:

  • На Codeforces в разделе «Архив» стоит потренироваться на задачах как минимум класса С — многие из них содержат подводные камни;
  • Проект The KeY to Software Correctness подойдет тем, кому интересно, как можно автоматически доказывать правильность работы кода. Он автоматизирует проверку кода на Java;
  • Автоматический доказатель теорем z3, написанный Microsoft, для тех, кто пользуется другими языками. Краткая инструкция по его использованию находится на ресурсе rise4fun.

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

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

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

Ресурсы:

  • С основами можно ознакомиться на сайте Mathprofi, который посвящен прозрачному и популярному описанию математики;
  • Если вы владеете английским, можете посмотреть более продвинутую книгу An Introduction to Combinatorics and Graph Theory;
  • Задачи по комбинаторике можно взять из задачника «Дискретная математика», в конце есть ответы.

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

Иногда на собеседовании интервьюер, дабы проверить насколько крут кандидат, задает такую задачу: «Вот у нас есть отрезок, который начинается с числа А и заканчивается числом Б. Мы кидаем на него две точки случайным образом. Какая будет средняя длина наибольшего отрезка?» или же «Пусть у нас есть треугольник, на вершине которого сидит муха. Пусть она перелетает с вершины на вершину за 3 секунды и отдыхает на каждой вершине по секунде, каждый раз случайно выбирая себе путь. Через какое время она в среднем вернется в начальную точку?».

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

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

Непрерывная теория вероятности для полного понимания требует знания элементарных основ мат. анализа, в частности понятия интеграла, хотя многие задачи требуют лишь умения считать площади простых фигур. Именно непрерывная теория вероятности является фундаментом для математической статистики и машинного обучения. Поэтому, если хотите работать в этой области, стоит начать с изучения книги Ричарда Хэнсена Probability Theory and Statistics или Probability Theory with Simulations.

Ресурсы:

  • MathProfi — сайт, на котором доступно и просто изложена высшая математика. На нём есть множество разделов с теорией, таблицами и задачами, в том числе и по теории вероятностей
  • Книга Чарльза М. Гринстеда и Лори Снелла Introduction to Probability.

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

Слышали ли вы задачу о мостах Кенигсберга?

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

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

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

Ресурсы:

  • Познакомиться с основными понятиями можно в краткой методичке «Введение в теорию графов»;
  • По части алгоритмов можно заглянуть на сайт e-maxx и наш;
  • Практиковаться можно на задачах с Codeforces, там есть задачи на графах.

Теория чисел и криптография

Задумывались ли вы, почему к простым числам такой большой интерес? Почему работает шифрование RSA? Чем отличается http от https и что такое сертификат безопасности?

Все эти вопросы изучает криптография. Сразу скажем, что эта наука достаточно сложная и не интуитивная — бывает непонтяно, как реализовать тот или иной алгоритм совершенно безошибочно. Тем не менее алгоритмы в криптографии не могут быть «чуть-чуть нерабочими». Малейшая ошибка может привести к компрометации всей криптографической системы.

Дискретная оптимизация

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

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

Источники

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

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

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

Что дальше?

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

Программирование для математиков

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

В 1980 году на мехмате МГУ был введен новый курс программирования

На мехмате МГУ в начале 50-х Алексей Андреевич Ляпунов читал первый учебный курс по принципам программирования. В 1980 году здесь же возникает новый курс программирования, который в конечном итоге оказал серьезное влияние не только на несколько поколений «мехматян», но и в целом на преподавание информатики в стране.

В заголовок статьи мы вынесли название учебника по мехматскому курсу программирования, который вышел восемью годами позже. Авторы курса Геннадий Викторович Лебедев и Анатолий Георгиевич Кушниренко подчеркивают, что название это отражало не просто принадлежность предмета главному математическому факультету страны. К 80-м стало очевидно, что мехмат, проложивший дорогу преподаванию теоретического программирования, уже не имеет соответствующего его высокой научной планке курса по этому предмету. Преподавание программирования сводилось к изложению Фортрана — языка, авторитет которого в сфере научных расчетов был непререкаем, и описанию архитектуры машин IBM 360, с которых делались наши ЕС ЭВМ. Качество этих курсов никак не отвечало мехматским требованиям. Вызревала потребность в абсолютно новом курсе, способном внести вклад в общую математическую культуру студентов.

Теперь его авторы уверены, что в итоге, когда курс окончательно сформировался, им удалось достигнуть этой цели. Правда, накануне 1 сентября 1980 года такие глобальные идеи не формулировались. Просто молодые преподаватели решили, что каждый студент, пришедший на первое занятие по программированию, должен уйти с него с распечаткой готовой программы. Для этого решили написать пакет программ с использованием библиотек системы «Асфор» — сокращенной версии Фортрана, разработанной на мехмате специально для программирования студенческих задач. Студенты должны были построить алгоритм передвижения некого «путника» через заданный набор препятствий и составить программу, состоящую только из вызовов стандартных программ. Дальше оставалось только собрать нужные перфокарты с набитыми на них программами, запустить их обработку и получить результат.

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

«В последнюю ночь в полном отчаянии и от безысходности в голове родилась шальная мысль, что Фортран здесь не нужен. Надо написать интерпретатор. С этой идеи и стартовал мехматский курс», — вспоминает Лебедев. За два часа был написан интерпретатор, обрабатывающий линейные операторы вновь придуманного языка с русской лексикой. Первое занятие прошло с полным успехом. Вся группа ушла с выполненными программами и уже приобретенным опытом исправления типовых ошибок. В прежних курсах студенты получали первые результаты не раньше чем через два-три месяца освоения языка.

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

По образному выражению авторов курса, в его основе лежат «три кита», которые призваны помочь студенту приобрести навыки грамотного программирования систем объемом в несколько тысяч строк. Это понятие исполнителя, технология «сверху вниз» и развитые структуры данных. Первое понятие, придуманное Владимиром Борисовичем Бетелиным, создатели курса сами освоили при решении вполне конкретных задач и обнаружили, что с его помощью можно с успехом строить самые большие и сложные системы. Фактически исполнитель — пакет программ, работающих над общими данными, — предшественник объектно-ориентированного программирования, экземпляр класса в современной терминологии.

Два других кита — технология программирования «сверху вниз», cхематическое изображение которой вынесено на обложку учебника, и иерархия структур данных с описанием методов реализации одних структур на базе других — важнейшие компоненты, без которых не обходится программист-практик. Мехматский курс программирования действительно закладывал базу для грамотной разработки сложных систем. Однако только изложение важных понятий, не подкрепленное практикой, мало что дало бы студентам. Поэтому в курсе предлагалось разобраться с несколькими законченными проектами (построение выпуклой оболочки, реализация компилятора с языка арифметических формул, построение изображения полиэдра) и, что самое главное, модифицировать эти проекты, то есть, изучив 6-8 тыс. строк эталонных программ, добавить тысячу-другую своих. Так студент на практике закреплял полученные теоретические знания и одновременно готовился к реальной работе. Ведь в жизни часто все так и происходит — решение задачи сводится к модификации готовых программных систем.

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

Опасения эти были безосновательны. Новая постановка преподавания программирования на мехмате не мешала изучению классических математических дисциплин. Оказалось, что сильные студенты вполне способны увлечься таким «приземленным» занятием, как программирование, найдя его интересным и своевременным. Создатели курса вложили в него всю свою энергию, увлеченность и талант. «Мы были довольно яркие ребята и делали курс с большим вкусом и интересом», — вспоминает с присущим ему юмором Кушниренко. К середине 80-х на курсе программирования для математиков была взращена группа молодых специалистов, которая вместе с ветеранами составила элиту факультетского программистского сообщества.

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

-Наталья Дубова, «ОТКРЫТЫЕ СИСТЕМЫ»

Поделитесь материалом с коллегами и друзьями

Читать еще:  Программа для создания презентаций онлайн на русском
Ссылка на основную публикацию
Adblock
detector
×
×