особенности, группы и режимы поиска и оценки алгоритмов - от леса к деревьям.

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

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

Обзор содержания:

  • Что такое алгоритм и в чем его смысл?
  • Особенности и характеристики алгоритма.
  • Как мы классифицируем алгоритмы? И как определить, какой использовать?

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

Выражаясь языком математики и информатики, алгоритм относится к конечной последовательности четко определенных инструкций, реализуемых компьютером, обычно для решения класса задач или выполнения вычислений [1-2]. Алгоритмы необходимы для обработки данных и информации в компьютерах. Исторически сложилось так, что компьютеры - это люди, которые могут выполнять процесс вычислений с помощью ряда операций. Таким образом, древность алгоритмов восходит к вавилонской математике c. 2500 г. до н.э. [2] - алгоритм деления. Греческие математики использовали концепцию алгоритма для исследования паттернов чисел, таких как алгоритм Евклида, который представляет собой метод нахождения наибольшего общего делителя для двух чисел. И метод Эратосфена для нахождения простых чисел [2].

Вообще говоря, алгоритм - это серия инструкций, выраженных для агента, способного выполнить такой процесс. Дальнейшие формализации предполагают, что алгоритм выражается полной по Тьюрингу системой [3–4]. Формальная система, скажем язык программирования, называется полной по Тьюрингу, если она может имитировать абстрактные машины Тьюринга. Другими словами, полный по Тьюрингу язык теоретически способен выражать все задачи, выполняемые компьютерами [5], как машины Тьюринга должны быть теоретическим представлением компьютера. Следовательно, такое выражение алгоритмов не только упрощает, но и логически формализует ряд процедур.

Об алгоритмах выражения

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

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

  • Описание высокого уровня: утверждение, которое описывает алгоритм без обязательного указания деталей реализации.
  • I описание реализации: директивы, которые определяют реализацию, правдоподобно по отношению к языку, например псевдокоды или код C ++.

Таким же образом структуры данных и алгоритмы представляются абстрактно (что только вникает в суть вопроса) до того, как они могут быть реализованы в базе кода [4]. Чтобы представить себе данный случай, нужно начать с высокоуровневого (абстрактного) описания: каковы ожидаемые результаты для этих входов? Какие основные процедуры? Среди прочего, для этого могут быть полезны диаграммы «ввод-обработка-вывод» (IPO).

При выражении алгоритмов следует иметь в виду, что они должны быть краткими, поскольку расплывчатые выражения приводят к путанице, которая может повлиять на время, необходимое для реализации алгоритма. В этом смысле естественный язык не должен оставаться без ограничений; ограниченный естественный язык на самом деле является искусственным языком [6]. Мы не будем далее говорить о лингвистических особенностях этих выражений, поскольку понятие алгоритма не зависит от языка: по практическим соображениям мы должны специфицировать и ограничивать лингвистические особенности, чтобы учитывать простоту, организацию и ясность, когда выражаем алгоритмы. Дело в том, что алгоритм должен быть кратким (описательным и императивным).

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

Особенности алгоритма [4]

Поскольку ситуация меняется, мы сталкиваемся с разными рамками проблем; нам также поручено сформулировать различные варианты нашего рецепта - алгоритмы.

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

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

Характеристики алгоритма

Хотя алгоритмы описывают процедуры, не все процедуры можно назвать алгоритмами. В этом смысле алгоритм должен обладать следующими характеристиками [7]:

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

Как мы классифицируем алгоритмы? И как определить, какой использовать?

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

Поскольку производительность с течением времени является важным показателем того, какой алгоритм подходит для данной задачи, пространственная и временная сложность данного алгоритма служит картой того, в каком направлении мы будем двигаться в поисках нашего алгоритма. При этом важно отметить, что теоретическая конструкция, которая классифицирует алгоритм в соответствии с его временем выполнения и требованиями к пространству в наихудшем сценарии, называется Big-O [4,7].

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

График выше показывает рост алгоритма с течением времени при заданном количестве входов (элементов). Тем не менее, алгоритмы, принадлежащие O (log n) и O (1) [читаются как big-O из log n и big-O of 1], идеальны для данной задачи. Однако не все проблемы решаются алгоритмом, принадлежащим классам O (1) и O (log n). Следовательно, нужно оценить компромиссы.

Использованная литература:

[1] Math Vault (нет данных). Окончательный словарь высшего математического жаргона. Получено по адресу: https://mathvault.ca/math-glossary/#algo.

[2] Шабер, Жан-Люк (2012). История алгоритмов: от камешка до микрочипа. Springer Science & Business Media. С. 7–8. ISBN 9783642181924.

[3] Минский, М. (1967). Вычисления: конечные и бесконечные машины (Первое изд.). Прентис-Холл, Энглвуд-Клиффс, штат Нью-Джерси. ISBN 978–0–13–165449–5.

[4] Стивенс Р. (2019). Основные алгоритмы: практический подход к компьютерным алгоритмам с использованием Python и C. Джон Вили и сыновья.

[5] Ян С.Ю. (2019). Предварительные вычислительные операции. В статье Киберкриптография: применимая криптография для безопасности киберпространства (стр. 143–172). Спрингер, Чам.

[6] Окрент, А. (2013). Искусственные языки. obo в лингвистике. DOI: 10.1093 / obo / 9780199772810–0164.

[7] Tutorialspoint (без даты). Структуры данных | Основы алгоритмов. Источник: https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm.