Математика для программиста. Изучать или забивать?

Введение

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

Апгрейд мозга

Мож­но мно­го написать о том, какое магичес­кое вли­яние ока­зыва­ет на ней­рон­ные свя­зи в моз­гу раз­ложение рядов Фурье. И о том, каким обра­зом про­качан­ные подоб­ным спо­собом изви­лины обес­печат тебе высокое качес­тво жиз­ни до кон­ца тво­их дол­гих дней. Но, во‑пер­вых, ты уже про это где‑то читал, а во‑вто­рых, ты и так умный, зачем тебе лиш­ние ней­рон­ные свя­зи?

По­это­му пояс­ним, какие кон­крет­но жиз­ненно важ­ные ски­лы мож­но раз­вить с помощью занятий матема­тикой.

Концентрация

Это качес­тво явля­ется важ­ней­шим для прог­раммис­та (пос­ле скром­ности). Дос­таточ­но мочь сос­редото­чить­ся на одной задаче в течение 10–15 минут, что­бы уметь писать код. Но если ты хочешь соз­давать что‑то реаль­но слож­ное и тра­тить минимум вре­мени на раз­работ­ку и отладку, то необ­ходимо при­обрести навык мно­гоча­совой гипер­концен­тра­ции. Он может быть врож­денным или нарабо­тать­ся через энное количес­тво лет работы (при наличии дед­лай­нов и необ­ходимос­ти решать нет­риви­аль­ные задачи). Решение интегра­лов, дифуров, рядов, тре­бующих дли­тель­ных раз­мышле­ний, силь­но уско­ряет про­цесс раз­вития этой моз­говой фун­кции (осо­бен­но если решать по 20 штук сра­зу). Но надо под­бирать мак­сималь­но слож­ные и объ­емные задачи для тво­его текуще­го уров­ня.

Воз­можно, у тебя быва­ют дни, ког­да край­не труд­но сос­редото­чить­ся и код не пишет­ся вооб­ще. Я в таких слу­чаях откры­ваю задач­ник Ска­нави и решаю один‑два при­мера из пер­вой час­ти. И сра­зу мыс­ли ста­новят­ся на свои мес­та, кра­сивые решения при­ходят на ум и жизнь налажи­вает­ся.

Есть леген­да о том, что в осо­бо важ­ных под­разде­лени­ях Microsoft (Google, Apple, Intel — под­ста­вить в зависи­мос­ти от лич­ных пред­почте­ний) компь­ютер работ­ника пре­рыва­ется каж­дый час и пред­лага­ет челове­ку решить неболь­шую матема­тичес­кую задачу. Таким обра­зом они повыша­ют про­изво­дитель­ность тру­да. Пред­ставь себе: четыре утра, дед­лайн, все уже готово, оста­лось отпра­вить пись­мо заказ­чику. А тут — опа! Все вык­люча­ется, и компь­ютер спра­шива­ет что‑то из раз­ряда «У Пети было пять каран­дашей, а у Васи?». Наде­юсь, подоб­ная сис­тема изде­ватель­ства над людь­ми не получи­ла мас­сового рас­простра­нения.

Терпение и настойчивость

Са­мое неп­рият­ное в работе прог­раммис­та — затянув­ший­ся про­цесс отло­ва оши­бок. Самое при­ятное (из того, что вооб­ще быва­ет в жиз­ни) — най­ти ошиб­ку в чужом коде пос­ле девяти часов поис­ка под­ряд.

Другие статьи в выпуске:

Хакер #187. Обходим Blizzard Warden

• Содержание выпуска
• Подписка на «Хакер»-60%

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

Оперативная память

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

Интуиция

Есть бай­ка о том, как тре­ниру­ют инту­ицию у аген­тов ФБР. Перед ними ста­вят две короб­ки, надо отга­дать, в какой лежит иско­мый пред­мет. Если человек не уга­дыва­ет — он получа­ет лег­кий, но болез­ненный раз­ряд тока. В ито­ге в нем про­сыпа­ется неверо­ятная спо­соб­ность выбирать вер­ное нап­равле­ние дей­ствий и мыс­лей. Неч­то ана­логич­ное про­исхо­дит и при решении матема­тичес­ких задач. Если на каком‑то эта­пе (в ситу­ации рав­нознач­ного выбора) повес­ти решение не по тому пути, то мож­но пол­часа идти в никуда. Пос­ле про­хож­дения некой кри­тичес­кой мас­сы неудач ты начина­ешь отме­чать за собой в разы мень­ше откло­нений от вер­ного нап­равле­ния (даже при решении задач абсо­лют­но нез­накомо­го фор­мата).

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

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

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

Это самая инте­рес­ная (на мой взгляд) из всех матема­тичес­ких наук и самая полез­ная для прог­раммис­та. Ее осно­ва — вза­имо­дей­ствие теории чисел с матема­тичес­кой логикой. Вклю­чает в себя мно­жес­тво раз­делов и под­разде­лов.

Теория алгоритмов

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

Вклад великих программистов в математику (и наоборот)

 

Эдсгер Дейкстра

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

 

Дональд Кнут

Я думаю, мно­гие читате­ли хоть раз в жиз­ни начина­ли читать его «Искусс­тво прог­рамми­рова­ния». Если ты дошел до чет­верто­го тома — напиши мне, чем там все закон­чилось, и твое фото мы опуб­лику­ем в сле­дующем номере на дос­ке почета. Кни­га нас­толь­ко тяжелая, что у самого Дональ­да пока не хва­тило тер­пения дописать ее до кон­ца (изда­но три с полови­ной тома из обе­щан­ных семи). Как прог­раммист он отли­чил­ся соз­дани­ем TeX и METAFONT. Фун­дамен­таль­ных откры­тий в матема­тике он не совер­шил, но про­делал огромную работу по сис­темати­зации и популя­риза­ции зна­ний в области теории алго­рит­мов.

 

Ричард Карп

Ос­новным вкла­дом это­го уче­ного в прог­раммист­скую науку было при­ложе­ние руки к соз­данию алго­рит­ма Рабина — Кар­па (поис­ка стро­ки в подс­тро­ке). В матема­тике его основным дос­тижени­ем явля­ется вклад в теорию NP-пол­ноты.

 

Ричард Хэмминг

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

 

Сеймур Пейперт

Пос­вятил кучу вре­мени теории искусс­твен­ного интеллек­та и внес в нее зна­читель­ный вклад. Автор мно­гочис­ленных ста­тей по матема­тике. Соз­дал язык Logo для обу­чения школь­ников осно­вам прог­рамми­рова­ния (я с него начинал в 90-е! — Прим. ред.).

 

Кристен Нюгорд

Один из авто­ров кон­цепции объ­ектно‑ори­енти­рован­ного прог­рамми­рова­ния. Соз­датель язы­ка симула (пер­вый язык с под­дер­жкой ООП). Так­же внес вклад в теорию вычис­литель­ных сис­тем.

Прак­тичес­кое при­мене­ние:

• Ал­горит­мы шиф­рования с исполь­зовани­ем теории чисел. При­мер: зна­мени­тый алго­ритм RSA осно­ван на слож­ности опре­деле­ния фак­ториза­ции двух целых чисел.

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

• Ор­ганиза­ция поис­ка и сор­тиров­ки боль­ших объ­емов дан­ных. Пояс­нение: любой поис­ковый робот содер­жит в сво­ей осно­ве слож­ней­шие алго­рит­мы ран­жирова­ния, опти­мизи­рован­ные для работы с зап­редель­ными объ­ема­ми информа­ции.

• Пос­тро­ение ком­пилято­ров, интер­пре­тато­ров и тран­сля­торов. Пояс­нение: теория ком­пилято­ров явля­ется пря­мой нас­ледни­цей теории алго­рит­мов, на которой и осно­выва­ются пра­вила пре­обра­зова­ния высоко­уров­невых син­такси­чес­ких конс­трук­ций в машин­ный код.

• Оп­тимиза­ция про­цес­са отладки прог­рамм. При­мер: ког­да ищешь ошиб­ку в длин­ном отрезке кода, то инту­итив­но при­меня­ешь метод интерва­лов: сна­чала ком­менти­руешь ниж­нюю полови­ну, смот­ришь, пра­виль­но ли выпол­няет­ся прог­рамма до середи­ны, если нет, то ком­менти­руешь еще чет­верть, если нет, то наобо­рот, осво­бож­даешь 25 про­цен­тов от ком­мента­риев. И так пока не най­дешь ту стро­ку, в которую зак­рался баг.

Темы, на которые стоит обратить внимание:

• струк­туры дан­ных (озна­ком­ление с этим воп­росом поможет быс­трее и глуб­же понять прин­ципы ООП);
• ре­кур­сивные алго­рит­мы;
• кри­терии оцен­ки качес­тва алго­рит­мов.

Книги:

• Ро­берт Сед­жвик. Алго­рит­мы на C++. Фун­дамен­таль­ные алго­рит­мы и струк­туры дан­ных.
• Ро­берт Сед­жвик, Кевин Уэйн. Алго­рит­мы на Java.
• То­мас Кор­мен. Алго­рит­мы: пос­тро­ение и ана­лиз.
• Ди­оми­дис Спи­нел­лис. Ана­лиз прог­рам­мно­го кода на при­мере Open Source.

Математическая логика

Без исполь­зования эле­мен­тарных логичес­ких выраже­ний (истинность которых про­веря­ется с помощью опе­рато­ра if) воз­можно написать раз­ве что Hello world. Ког­да мы объ­явля­ем перемен­ную типа Boolean, мы сно­ва исполь­зуем мат­логику.

Практическое применение:

• Низ­коуров­невое прог­рамми­рова­ние про­цес­соров (спой­лер: чита­ем статьи Анто­на Сысо­ева в этом и пре­дыду­щем выпус­ках). Пояс­нение: кон­такты мик­росхем име­ют все­го два сос­тояния — есть сиг­нал (1) и нет сиг­нала (0). И бла­года­ря такому дос­тижению челове­чес­кого разума, как мат­логика, потоки нулей и еди­ниц прев­раща­ются в неч­то весь­ма осмыслен­ное.

• Оп­тимиза­ция кода со слож­ными вет­вле­ниями. При­мер: пос­тро­ение таб­лицы истиннос­ти для все­воз­можных слу­чаев, про­веря­емых в вет­вле­нии в целях сок­ращения чис­ла бло­ков if/else.

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

• Прог­рамми­рова­ние битовых опе­раций. При­мер: запись прав дос­тупа в виде стро­ки нулей и еди­ниц (010100 — пер­вая циф­ра — чте­ние фай­лов, вто­рая — редак­тирова­ние и так далее) и их пос­леду­ющие изме­нения путем уста­нов­ки зна­чений битов. Прос­то и мак­сималь­но опти­мизи­рова­но.

• Рас­позна­вание обра­зов. Пояс­нение: любой гра­фичес­кий объ­ект пред­став­ляет собой совокуп­ность битов и, сле­дова­тель­но, может быть срав­нен с дру­гим гра­фичес­ким объ­ектом с при­мене­нием побито­вых опе­раций.

Темы, на которое стоит обратить внимание:

• бу­левы фун­кции;
• те­ория моделей;
• те­оре­ма Рай­са.

Книги:

• Алон­зо Чёрч. Вве­дение в матема­тичес­кую логику.
• А. К. Гуц. Матема­тичес­кая логика и теория алго­рит­мов. # Дру­гие раз­делы

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

Практическое применение:

• Мас­теры для поис­ка отве­та на воп­рос поль­зовате­ля (при­меня­ются в авто­мати­зиро­ван­ных сап­портах), пред­став­ляющие собой клас­сичес­кую экспертную сис­тему. При­мер: реали­зация англо­языч­ной базы зна­ний WolframǀAlpha, которой мож­но задавать воп­росы на челове­чес­ком язы­ке.

• Ре­али­зация ана­лиза­торов тек­ста в виде конеч­ных авто­матов. При­мер: под­прог­рамма, реали­зующая поиск и уда­ление ряда строк из про­изволь­ного тек­ста, может быть реали­зова­на в виде конеч­ного авто­мата.

• Про­екти­рова­ние реляци­онных СУБД. Пояс­нение: как гла­сит нулевое пра­вило Код­да, «реляци­онная СУБД дол­жна быть спо­соб­на пол­ностью управлять базой дан­ных, исполь­зуя свя­зи меж­ду дан­ными». Так вот, свя­зи меж­ду дан­ными в клас­сичес­кой реляци­онной СУБД опти­мизи­руют­ся с помощью теории гра­фов.

Темы, на которое стоит обратить внимание:

• те­ория гра­фов;
• эк­спертные сис­темы;
• асин­хрон­ная логика;
• фор­маль­ные грам­матики;
• ко­неч­ные авто­маты.

Книги:

• Род Хаг­гарти. Дис­крет­ная матема­тика для прог­раммис­та.
• С. В. Яблон­ский. Вве­дение в дис­крет­ную матема­тику.
• Н. Крис­тофидес. Теория гра­фов: алго­рит­мичес­кий под­ход.

Акинатор

Есть такая замеча­тель­ная онлайн‑игра — «Аки­натор». Суть ее прос­та — загады­вай любого пер­сонажа, отве­чай на 20 воп­росов про него, и джинн выда­ет фотог­рафию задуман­ного героя. Прог­рамма никог­да не оши­бает­ся (если ее не дурить), уга­дыва­ет даже Бьер­не Стра­устра­па и Кри­са Кас­пер­ски. Соз­дает­ся впе­чат­ление бесов­ско­го про­исхожде­ния дан­ной игры, но «Аки­натор» все­го лишь при­мер огромной само­обу­чающей­ся экспертной сис­темы.

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

Зна­ние этой науки — must have для любого челове­ка, занято­го тес­тирова­нием мало‑маль­ски слож­ных сис­тем (гра­мот­ное при­мене­ние этой науки спо­соб­но сок­ратить количес­тво тес­тов на порядок). Так­же исполь­зует­ся для ана­лиза дан­ных с целью получе­ния прак­тичес­ки полез­ных выводов.

Практическое применение:

• Вы­явле­ние опти­маль­ных клас­сов экви­вален­тнос­ти в тес­тирова­нии. Пояс­нение: класс экви­вален­тнос­ти в тес­тирова­нии — это совокуп­ность тес­тов, при­водя­щих к оди­нако­вому резуль­тату.
• Гра­мот­ная опти­миза­ция pair-wise тес­тирова­ния. Пояс­нение: pair-wise — это метод сок­ращения количес­тва тес­тов путем одновре­мен­ного тес­тирова­ния двух парамет­ров вмес­то одно­го.
• Пос­тро­ение выборок для иссле­дова­ния каких‑либо явле­ний или объ­ектов. При­мер: рас­чет количес­тва тес­тов, которо­го было бы дос­таточ­но, что­бы в слу­чае их пра­виль­ного выпол­нения быть пол­ностью уве­рен­ным в безот­казнос­ти сис­темы.

Темы, на которое стоит обратить внимание:

• ста­тис­тичес­кие методы;
• те­ория при­нятия решений;
• ста­тис­тика слу­чай­ных про­цес­сов и вре­мен­ных рядов;
• ста­тис­тичес­кое модели­рова­ние.

Книги:

• В. Е. Гмур­ман. Теория веро­ятностей и матема­тичес­кая ста­тис­тика.
• А. А. Боров­ков. Теория веро­ятностей.
• Ген­ри Уор­рен, мл. Алго­рит­мичес­кие трю­ки для прог­раммис­тов.

Заключение

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

• бе­зого­вороч­но уве­ровал в необ­ходимость изу­чения всех видов и под­видов матема­тичес­кой науки;
• чет­ко понял, какие имен­но раз­делы матема­тичес­кой науки боль­ше все­го нуж­ны прог­раммис­там в целом и тебе в час­тнос­ти;
• сос­тавишь лич­ный план матема­тичес­кого селф‑девелоп­мента и воп­лотишь его в жизнь;
• ста­нешь мегак­лас­сным IT-спе­цом, вне­сешь все­лен­ски зна­чимый вклад в науку, зарабо­таешь кучу денег и подаришь каж­дому чле­ну редак­ции нашего жур­нала по спор­тивно­му авто­моби­лю (спи­сок приш­лем по пер­вому тре­бова­нию).