Что такое алгоритм?! Часть первая

Проблема

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

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

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

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

Для компактного и полезного набора объяснений нужно:

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

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

Задуманная серия статей не претендует на полное решение указанной проблемы. Предпринимается небесспорная попытка сделать первый шаг на пути к этому решению. Этот шаг состоит в выделении структуры и свойств главного кирпичика программиста — Алгоритма.

Задача

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

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

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

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

Сразу возникает масса вопросов к этому определению:

• Что такое правило?
• Как, кому и для кого это правило можно задать?
• Что есть объединение совокупностью?
• Каким образом правила соотносятся с задачей?
• Что формирует класс задачи?
• Определяется ли способ формирования совокупности правилами и задачами?
• …

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

• Какова структура набора?
• Какие есть варианты действий и исполнителей?
• Существуют ли минимально возможное действие, минимальный набор необходимых действий?
• Каким образом действия встроены в исполнителя?
• Какие есть способы создания копии исполнителя (например, если исполнитель — человек)?
• Как действия зависят друг от друга в упорядоченном выполнении?
• Что есть задача кроме того, что она выполняется последовательностью действий?
• Как задача соотносится с исполнителем и с действиями?
• Возможно ли использовать решение задачи в качестве действия?
• Какие возможны варианты указания порядка действий?
• Если воспроизведение патефоном записи звуков леса является алгоритмом, то какова структура этой задачи?
• Если репликация ДНК является алгоритмом, то каков её исполнитель?
• Если исполнителем является Машина Тьюринга, то как с её использованием решить механическую задачу, например, воспроизведение звука?

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

«Алгоритм Мо»

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

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

Трюк в том, что правая граница суммарно сдвинется на \(O(n)\), потому что отрезки отсортированы, а левая — каждый раз на \(O(\sqrt n)\). Итоговая асимптотика решения будет \(O(q \sqrt n + n \sqrt n)\): изменение левых границ суммарно по всем блокам займёт \(O(q \sqrt n)\) операций, а правых — \(O(n \sqrt n)\),

struct query { int l, r, idx; }; // idx — это номер запроса, на который нужно ответить int a[maxn]; vector b[c]; int ans[maxq]; // массив ответов на запросы // где-то в main: for (query q : queries) b[q.l / c].push_back(q); for (int i = 0; i < c; i++) { sort(b.begin(), b.end(), [](query a, query b){ return a.r < b.r; }); for (int i = 0; i < c; i++) { int l = i * c, r = i * c — 1; // границы текущего отрезка int s = 0; // сумма на текущем отрезке for (query q : b) { while (r < q.r) s += a[++r]; while (l < q.l) s -= a[l++]; while (l > q.l) s += a[—l]; ans[q.idx] = s;

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

Примечание. Алгоритм назван по имени какого-то неизвестного китайца и принят под этим названием в фольклоре ICPC. Автору это не нравится, но что поделать: другого названия не придумали.

Вариации

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

Идея примерно такая же, как при сведении LCA к RMQ. Мы можем выписать эйлеров обход дерева (каждую вершину выписываем дважды — в моменты входа и выхода), и теперь задача сводится к задаче на массиве, только с одним исключением: мы должны добавлять в структуру только те элементы, которые содержатся на отрезке ровно 1 раз.

Использовать корневую декомпозицию как структуру. Часто от внутренней структуры в алгоритме Мо требуется что-то сложное, и мы пребегаем к использованию каких-то «тяжелых» структур, вроде дерева отрезков. Но данный случай отличается от обычных задач на обработку запросов: у нас обновлений \(O(n \sqrt n)\), а запросов всего \(O(n)\). Здесь эффективнее вместо дерева отрезков, требующего \(O(\log n)\) времени на оба типа запросов, взять структуру, которая быстро работает при обновлениях, и не очень быстро на самих запросах — например, корневую декомпозицию, которая работает за \(O(1)\) и \(O(\sqrt n)\) соответственно.

На самом деле, это примерно единственное место, где корневую эвристику как структуру использовать эффективнее всего — внутри другой корневой эвристики.

«3D Мо». Если очень захотеть, этот подход можно применять и в задачах, где надо обрабатывать запросы обновления. Для этого нужно ввести третий параметр get-запроса \(t\), который будет равен числу update-запросов до текущего get.

Снова отсортируем все get-запросы, но на этот раз в порядке \((\frac{t}{n^{\frac 2 3}}, \frac{l}{n ^{\frac{2}{3}}}, r)\), и обработаем их таким же алгоритмом, только в трёх измерениях. Время работы нового подхода будет \(O(n^{\frac{5}{3}})\), что доказывается аналогично исходному алгоритму.

Определение алгоритма

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

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

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

Если «действие = алгоритм», то определение можно попробовать переписать рекурсивно «алгоритм — это приводящая к решению задачи последовательность использования существующих алгоридействие» (атомарный алгоритм), которое можно использовать в разработке алгоритма;

Действие

Для начала рассмотрим «действие» и попробуем найти причину, обеспечивающую возможность использования существующего «действия» для создания нового алгоритма.

Этой причиной является возможность повторного использования «действия» с получением тождественного результата. Только тогда разработанный с использованием этого «действия» алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:

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

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

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

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

В рамках примера процесса «Земля-Яблоко» можно о следующие признаки:

• наличие процесса изменения (расстояния и параметров движения объектов);
• наличие объектов, взаимодействие которых вызывает такие изменения;
• наличие локальности процесса, то есть существование значения расстояния между объектами, с превышением которого их взаимодействие перестает вызывать процесс изменения, что делает невозможным использование «действия» (Земля и гипотетическое яблоко, находящееся вне солнечной системы).

Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры «действий» и контролируя особенности указанных признаков в описании структуры «действия».

Физические процессы

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

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

Химические процессы

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

Математические процессы

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

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

Интересно, что на примере древнего математика становится понятен смысл слова «сложить», которое отсылает нас к действию «класть» и к фразе «положить вместе».

Сложение и древний математик

Для математика, оперирующего камешками, сумма это «действие» со следующими характеристиками.

Исходные объекты:

• это сам «математик» (он взаимодействует со слагаемыми);
• лежащая отдельно кучка №1, содержащая и связывающая вместе камешки (подобно химическим связям), и обозначающая первое слагаемое;
• лежащая отдельно кучка камешков №2, обозначающая второе слагаемое.

Процессы:

• «математик» подходит к кучкам (физически изменяет расстояние между кучками и собой) и начинает с ними взаимодействие;
• «математик» объединяет две кучки (физически изменяет расстояние между двумя кучками или переносит все камешки одной кучки в другую, возможно, используя «действие» «Перенос по-одному» камешку)

Результирующие объекты:

• сформированная кучка камешков, обозначающая результат (сумму);
• «математик», отошедший от кучки результата и переставший на неё воздействовать.

Сложение и математик-абакист

У математика с абаком ситуация сложнее. Кучки разделены по значению на разрядные борозды.

Можно рассмотреть самый простой абак с двумя разрядами-бороздами. Пусть он будет десятичный. Тогда один камешек на борозде десятков соответствует десяти камешкам на борозде единиц. И 10 — это максимальное количество камешков на борозде единиц. По сравнению с действием первого математика меняется представление слагаемых. И в арсенале математика уже необходимы нескольких готовых «действий».

Действия:

• «Перенос по-одному» из борозды в борозду одинакового уровня (действие, позаимствованное у первого математика);
• «Перенос в десятки», которое необходимо выполнять, если борозда единиц полностью заполняется, тогда из неё убираются все камешки кроме одного, который переносится в борозду десятков.

Исходные объекты:

• это сам «математик» (он взаимодействует со слагаемыми);
• группа камешков №1, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих первое слагаемое;
• группа камешков №2, лежащих и удерживаемых двумя бороздами (единиц и десятков), и обозначающих второе слагаемое;

Процессы:

• «математик» подходит к группам борозд (физически изменяет расстояние между ними и собой) и начинает с ними взаимодействие;
• «математик» объединяет камешки из двух борозд единиц (физически изменяет расстояние между камешками, разрушает связи со старой бороздой и создает связи с новой) с использованием действий «Перенос по-одному» и «Перенос в десятки»;
• «математик» объединяет камешки из двух борозд десятков с использованием действия «Перенос по-одному»

Результирующие объекты:

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

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

Сложение и машина Тьюринга

Можно пойти чуть дальше и заменить математика в таких «действиях» на «управляющее устройство» машины Тьюринга. Тогда «ячейки ленты» машины Тьюринга будут содержать слагаемые.

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

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

Не для манки-кодеров: книги по алгоритмам и структурам данных

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

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

Algorithms, Etc.

Это лекции и другие учебные заметки к курсам по алгоритмам в Иллинойсском университете в Урбане-Шампейне. Помимо теории, на сайте можно найти большое количество домашних и экзаменационных заданий — правда, без ответов.

Algorithms (Алгоритмы на Java)

Читать Купить
Книга Седжвика и Уэйна «Алгоритмы на Java» является классическим справочным руководством, в котором содержится необходимый для программиста объем знаний в области алгоритмов, накопленных за последние несколько десятилетий.

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

Binary Trees

Небольшая методичка Стенфордского университета, целиком посвящённая двоичным деревьям. Внимание уделено как теории, так и задачкам с разборами решений, причём и на Java, и на C.

Linked List Basics

Linked List Problems

Ещё две методички из Стенфорда. Первая содержит теоретические материалы, посвящённые связным спискам, а вторая — 18 задач. Пригодятся всем, кто изучает C и хочет узнать о возможностях применения указателей.

Clever Algorithms: Nature-Inspired Programming Recipes

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

The Algorithm Design Manual

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

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

Жемчужины проектирования алгоритмов: функциональный подход

Купить
Отличная книга по алгоритмам, использующая неординарный подход.

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

Алгоритмы. Вводный курс

Купить
Если «Алгоритмы. Построение и анализ» — фундаментальный труд, призванный дать максимум информации по тем или иным алгори, написанная тем же профессором информатики Томасом Корменом, рассчитана на аудиторию, не готовую осилить труд в 1300 страниц. Так что если вы — один из таких, но, тем не менее, вам необходимо ознакомиться с алгоритмами, то эта книга для вас.

Алгоритмы. Построение и анализ

Купить
Ещё одна увесистая книга по алгоритмам, впервые изданная в 1990 году в Массачусетском технологическом институте с авторством местных преподавателей. Несмотря на то, что написана она простым и понятным языком, из-за объёма и подачи материала (каждая глава имеет законченный вид) использовать лучше в качестве справочника, периодически обращаясь к нужной информации.

Искусство программирования

Купить
Искусство программирования — монументальный труд Дональда Кнута. Серия книг состоит из 4 томов, каждый из которых охватывает определенные виды алгоритмов. Это классика, которую до сих пор в обязательном порядке проходят в ВУЗах. Материал подан в достаточно сложном формате, но и цель у книг особенная — рассказать наиболее полно о существующих алгоритмах.

Алгоритмические трюки для программистов

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

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

Алгоритмы. Справочник с примерами на C, C++, Java и Python

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

Planning Algorithms

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

Purely Functional Data Structures

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

Matters Computational

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

Text Algorithms

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

The Design of Approximation Algorithms

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

Data Structures and Algorithms

Авторы книги преследовали три цели: объяснить основные алгоритмы как можно проще и при этом точнее, снабдить их диаграммами и написать понятные листинги на псевдокоде, которые можно без особых проблем перевести на C++, C# и Java. Удалось ли им это — прочтите и узнаете