— Как я стал таким программистом?
— Я был умнее самых умных и упорнее самых упорных!
перефразированная цитата Скрудж МакДака
Буду честен перед читателем. Любой алгоритм, можно написать на любом языке полным по Тьюрингу — это значит, что вход и выход такой программы будут совпадать. Так почему здесь указан язык C++?
Потому что автор знает его лучше, чем Python\Java\etc, но это утверждение верно лишь частично. На самом деле есть несколько причин: этот язык в силу своих особенностей может общаться напрямую с машиной, то есть компилироваться в машинный код. Множество других языков тоже умеют компилироваться в машинный код, возразит читатель. Верно, на это возражение есть еще несколько причин. Язык C++ не принадлежит никому, изначально он и разрабатывался в Bell Labs1, но как и язык C корпорация решила не лицензировать оба языка, в отличии от системы Unix. Тогда почему не язык C спросит проницательный читатель? Ответ на этот вопрос тоже есть причина. Цель создание языка C была переписать Unix систему на другую архитектурную платформу с минимум усилий, и эту возложенную функцию авторами язык выполнил на отлично. Изначально язык C++ был задуман для облегчения написания диссертации Бьерна Страуструпа2 для обработки сетевого многопоточного трафика. Академическая среда повлияла на концепцию и философию языка3. Первый десяток лет язык так и оставался забавной академической игрушкой, пока не произошел случай. Математик Александр Степанов после не совсем удачной попытки внедрить его теорию обобщенного программирования4 в язык ADA обратил свой взор на язык C++. По иронии судьбы внедрение обобщенного программирования в язык было реализовано даже не в половину от теории, которую задумал Степанов, так как использовались математические контракты и концепты. Они небыли частью языка и не обрабатывались на уровне компилятора. Это и есть самая веская причина почему язык C++ подходит для информатики (компьютерные науки \ computer science), каждая новая версия языка (стандарт) привносит математическую строгость в язык и не теряет совместимость с наследием старой кодовой базы.
Я и так умею программировать
Исторически программисты появились не сразу, все это делали математики\физики\ученые, то есть составляли программу, которая автоматизирует математические расчеты. Эту историческую ретроспективу можно прочитать в статье Дейкстры5. С каждым поколением компьютеров расширялись его возможности, такими возможностями заинтересовались различные ведомства и корпорации. Появились задачи обработки документации, ведение учета. Примерно тогда нужно было обобщить категорию людей, которые составляют программы в профессию программист. Такие программисты все еще хорошо знали математику. Затем новые поколения компьютеров и их массовость, были достаточны надежными и дешевыми, чтобы за ними работали обычные работники предприятия, то есть выполняли свои задачи не используя языки программирования. Следующая итерация компьютеров достигла пика своего прогресса, теперь почти любой продвинутый пользователь компьютера, прочитавший несколько самых базовых концепций языков программирования таких как цикл, ветвление, вызов функции. Стали собирать из набора предоставленных модулей\функций свои программы. Понятие программист с каждым таким поколением выхолащивалось и превратилось в того, кто умело манипулирует «языковым конструктором». Поэтому часто в интернете спрашивают зачем программисту математика и другие наивные вопросы.
Информатика, зачем?
Термин информатика отделился от термина прикладной математики, потому что затрагивал автоматизированные вычисление математики, а также обработку физического мира — обработку различных сигналов. Многие авторитетные ученые все еще считают, что термин информатики (компьютерные науки \ computer science) избыточным. Здесь и далее математикой подразумеваются любые вычисление в том числе компьютерные, за исключением, где информатика подчеркивает контекст.
Компьютер (вычислитель) — это человек выполняющий математические расчеты (Рис. 1.), исторический термин. Почему люди делают механическую работу с подробной инструкцией? Ответ на этот вопрос переносит в древние времена. С античных времен Греции (возможно и раньше) человечество мечтало создать искусственного человека\автоматона, о чем свидетельствует древнегреческой миф о Талосе. Философы на протяжении всей истории человечества рассуждали каким должен быть искусственный мыслитель, параллельно многочисленные поколения математиков также хотели автоматизировать свой труд. Постепенное развитие наук и технологий. Дало возможность человечеству изготовить различные механизмы, сначала полу механические, а затем и полностью автоматические. Мечта человечества стала осуществляться появились, различные счетные устройства, такие как калькуляторы и автоматические картотеки. Через некоторое время был создан искусственный мозг — процессор, автоматический вычислитель — компьютер в современном его понимании.
Информатика помогает нагружать процессор задачами, которые человек не хочет\не может\не умеет вычислять сам.
-
Не хочет: тривиально, у вас есть некие математические формулы, которые требуют времени на вычисление и корректности результата. Человек может вычислить и сам, но эта рутинная операция, которая участвует в его научных исследованиях, пересчитывать коэффициенты каких-то свойств математики\физики. Вычисления такого рода отнимают значительную часть от исследовательской работы.
-
Не может: нужно вычислить число π до миллионного знака после запятой, человеку физически не хватить времени всей жизни чтобы это сделать, да сделать так чтобы не было ошибки в расчетах. Такую простую задачу решали еще первые компьютеры, сейчас математические требования на порядки выше, не хватит и всех людей на планете чтобы вычислить небольшую задачу, с которой компьютер справиться за пару секунд.
-
Не умеет: часто развитие математики хоть и открывает новые формулы, которые упрощают различные вычисления, но большая часть задач не имеет прямого решения (формулы), приходится изобретать. Различные приближенные алгоритмы, которые дают удовлетворительные решения задач, в том числе с использованием методов искусственного интеллекта это хоть и интересное направление математики, но это отдельная большая тема в данной статьи рассматриваться не будет.
Примеры
Базовый пример:
Нужно умножить произвольное число на четыре. Тривиальная математическая формула — это алгебраическая переменная и константа 4:
На языке процессора, в машинном коде, такая задача может иметь разную реализацию, на какой-то архитектуре это два сложения подряд (машина десятичная) переменной\регистра a. На другой это сдвиг регистра a на два бита влево (машина двоичная). Для читателя не знакомым с математикой может показаться что это причуда инженера, который проектировал процессор, но на самом деле это свойство математики, вспомните что, когда вы умножаете или делите на 10 двигаете запятую влево или вправо на один разряд. Точно также в двоичном представлении двигается разряд запятой. Читатель может возразить что в целых числах нет запятой. На самом деле есть и вот почему рассмотрим задачу: беззнаковое целочисленное деление на 3 всегда можно реализовать умножением7. В математике с вещественными числами это выглядит как a*0,(3). Но как поступить, когда у нас нет вещественных чисел. Нужно просто заранее знать коэффициент(точность) умножения и последующим сдвигом влево на количество значащих знаков в коэффициенте. Выглядит сложноватым, но на языке компьютера это выглядит как:
unsigned int a=43;//тут в качестве примера выбрано число 43
unsigned int b=0b01010101;//коэфф. деление на 3 с точностью 8 бит по формуле (2^8+1)/3
a=(a*b)>>8;//переменной\регистре получим ответ 14 что и требовалосьНа самом деле запятая в математике — это условность, разбивающая правую и левую часть разрядов на целые и дробные в любой системе счисления. Проницательный читатель может спросить зачем такие математические приемы, ведь уже в каждом современном языке есть умножение и деление, да еще и сразу с плавающей запятой. Ответ на этот вопрос заключается в том, что скорость процессора ограничена фундаментальными физическими константами. Различные математические приемы в научных вычислениях, сокращают количество работы процессора на дни, месяцы, и даже годы. Есть область работы процессоров реальном времени с физическим миром, например самый тривиальный пример, инжекторный впрыск топлива, если процессор не успеет вовремя рассчитать время и количество подачи топлива в нужный промежуток времени, машина может заглохнуть.
В мире информатики такие математические приемы, называются оптимизация, когда вместо решения в лоб, применяются такие изящные способы произвести вычисления.
Сложный пример:
Алгоритм — совокупность математических действий, решающая конкретную математическую задачу. Обычно программа — это совокупность алгоритмов. Например, рассчитать первые 100 простых чисел и вывести результат на экран. Первый алгоритм можно реализовать с помощью решета Эратосфена, а вот выводит на экран уже сложнейшая математическая задача, по сути, это синтез символов в реальном времени, так как компьютер хранит символы в виде зашифрованных числовых значений. Такую сложную задачу мы рассматривать не будем, так как она может занять не один том, если рассматривать различные приемы и тактики вывода символа, а также архитектуру экрана.
Поговорим о математическом анализе сложности алгоритмов. Хорошим классическим примером будет рассмотреть несколько алгоритмов сортировки.
Сортировка — это операция над некоторой последовательностью чисел(объектов), которая переставляет последовательность так, что числа в последовательности идут в порядке возрастания от малого к большему. Рассмотрим два алгоритма: Сортировка пузырьком \ Bubble sort8, Сортировка слиянием \ Merge sort9. (это два итеративных алгоритма, но детали реализации, нас не интересуют)
Сортировка пузырьком \ Bubble sort
void bubbleSort(int a[], int l)
{
int i;
int j;
for (i = 0; i < l - 1; i++)
for (j = 0; j < l - i - 1; j++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
} Сортировка слиянием \ Merge sort
void MergeSort(int a[], int l)
{
int BlockSizeIterator;
int BlockIterator;
int LeftBlockIterator;
int RightBlockIterator;
int MergeIterator;
int LeftBorder;
int MidBorder;
int RightBorder;
for (BlockSizeIterator = 1; BlockSizeIterator < l; BlockSizeIterator *= 2)
{
for (BlockIterator = 0; BlockIterator < l - BlockSizeIterator; BlockIterator += 2 * BlockSizeIterator)
{
LeftBlockIterator = 0;
RightBlockIterator = 0;
LeftBorder = BlockIterator;
MidBorder = BlockIterator + BlockSizeIterator;
RightBorder = BlockIterator + 2 * BlockSizeIterator;
RightBorder = (RightBorder < l) ? RightBorder : l;
int* SortedBlock = new int[RightBorder - LeftBorder];
while (LeftBorder + LeftBlockIterator < MidBorder && MidBorder + RightBlockIterator < RightBorder)
{
if (a[LeftBorder + LeftBlockIterator] < a[MidBorder + RightBlockIterator])
{
SortedBlock[LeftBlockIterator + RightBlockIterator] = a[LeftBorder + LeftBlockIterator];
LeftBlockIterator += 1;
}
else
{
SortedBlock[LeftBlockIterator + RightBlockIterator] = a[MidBorder + RightBlockIterator];
RightBlockIterator += 1;
}
}
while (LeftBorder + LeftBlockIterator < MidBorder)
{
SortedBlock[LeftBlockIterator + RightBlockIterator] = a[LeftBorder + LeftBlockIterator];
LeftBlockIterator += 1;
}
while (MidBorder + RightBlockIterator < RightBorder)
{
SortedBlock[LeftBlockIterator + RightBlockIterator] = a[MidBorder + RightBlockIterator];
RightBlockIterator += 1;
}
for (MergeIterator = 0; MergeIterator < LeftBlockIterator + RightBlockIterator; MergeIterator++)
{
a[LeftBorder + MergeIterator] = SortedBlock[MergeIterator];
}
delete SortedBlock;
}
}
}Не подготовленному читателю может показаться что алгоритм сортировка пузырьком будет работать быстрее чем сортировка слиянием, потому что строчек кода в первом алгоритме меньше. Но на самом деле все с точности на оборот, и количество строчек кода — это не метод оценки производительности алгоритма. Распространенное заблуждение в программировании (см. выше раздел Я и так умею программировать). Здесь нужен математический анализ. В информатике такой анализ алгоритмов называется «O» большое10.
Не будем вдаваться в тонкости доказательств, и примитивно оценим наше «O». Как правило сложность алгоритма заключается в начальной последовательности элементов, то есть вход с количеством n. Таким образом пройти все элементы алгоритмом один раз это O(n), а если алгоритм принимает на вход последовательность и не проходит ее хотя бы один раз то это O(1). Таким образом в алгоритме сортировка пузырьком, два цикла один внутри другого мы проходим последовательность n раз по n раз получается O(n2). В алгоритме один главный цикл это n проходов, и еще есть подциклы в совокупности они дают log n. Не будем вдаваться в подробности алгоритма, сравним их по нотации большое О. O(n2) > O(n log n) соответственно где больше, тот алгоритм и дольше вычисляется. При этом с точки зрения результата он эквивалентен. При подсчете большое О можно легко ошибиться, если вы взываете, какую-то функцию внутри цикла. Как функция использует вашу последовательность остается либо гадать, либо читать документацию к этой функции. Поэтому многие языки программирования с точки зрения математика не гарантируют ровным счетом ничего.
Это была только лишь небольшая вводная часть в мир информатики, конечно нужно знать гораздо больше, чтобы оптимизировать код и изобретать новые алгоритмы, важно не только понимать математику, но также погружаться в математическую историю, интересоваться наукой, изучать и практиковаться, и конечно же исследовать возникшие идеи. Быть может, ваш алгоритм расширит познания человечества или сэкономит триллиарды машино-часов.
Настоящий программист сочетает не только знания математика, но и быть инженером может изобретать! Например: новые взаимодействия компьютера и человека, даже на основе стандартных устройств ввода клавиатуры и мышки. Заниматься автоматизацией робототехники, и многое другое. Может быть физиком, которые рассчитывает симуляции физических процессов. Может быть астрономом, который программирует спутниковые радио-антенны.
-
Иллюстрация для титульной страницы. https://habr.com/ru/articles/147762/
-
Книга: Время UNIX. A History and a Memoir \ UNIX, A History and a Memoir Автор: Брайан Уилсон Керниган \ Brian Wilson Kernighan.
-
Книга: Дизайн и эволюция языка C++ \ The Design and Evolution of C++, Автор: Бьерн Страуструп \ Bjarne Stroustrup.
-
Раздел Филосовия С++ https://ru.wikipedia.org/wiki/C%2B%2B#Философия_C++ \ https://en.wikipedia.org/wiki/C%2B%2B#Philosophy
-
Книга: От математики к обобщенному программированию \ From Mathematics to Generic Programming, Автор: Александр Степанов, Дэниэл Э. Роуз \ Alexander A. Stepanov, Daniel E. Rose.
-
Статья: Смиренный программист EWD340 \ The Humble Programmer (EWD 340) автор: Эдсгер Вибе Дейкстра \ Edsger W. Dijkstra
-
Фото «Гарвардские вычислители»: https://ru.wikipedia.org/wiki/Гарвардские_вычислители \ https://en.wikipedia.org/wiki/Harvard_Computers
-
Книга: MMIX RISC-компьютер для нового тысячелетия \ MMIX a RISC Computer for the New Millennium, автор: Дональд Эрвин Кнут \ Donald Ervin Knuth. Глава 1.3.1 Задание 17 [M22].
-
https://ru.wikipedia.org/wiki/Сортировка_пузырьком \ https://en.wikipedia.org/wiki/Bubble_sort
-
https://ru.wikipedia.org/wiki/Сортировка_слиянием \ https://en.wikipedia.org/wiki/Merge_sort
-
https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое \ https://en.wikipedia.org/wiki/Big_O_notation
