| | | | | | | | | | | | | | | | | | | | | | | | | | | | А | л | г | о | р | и | т | м | | и | | е | г | о | | с | л | о | ж | н | о | с | т | ь | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 13.11.95 | |
| | Под | алгоритмом | , если говорить неформально, можно понимать четко описанную | |
| последовательность действий, приводящую к определенному результату. | |
| |
| Понятие алгоритма очень долго оставалось интуитивным понятием. Только в |
| 30-е годы XX века в работах выдающихся математиков Д.Гильберта, А.Черча, |
| С.Клини, Э.Поста и А.Тьюринга были предложены формальные определения алгоритма |
| на основе понятия | рекурсивной функции | и на основе | описания алгоритмического | |
| процесса | . Тем самым сформировалась теория алгоритмов - новое направление в |
| математике, которое стало впоследствии теоретической основой развития |
| вычислительной техники. В настоящее время теория алгоритмов бурно развивается, |
| многие ее понятия проясняются и уточняются ( | доказуемость, разрешимость, | |
| эффективность | и др.). |
| Очень важным понятием в математике (интуитивно ясным, но не очень просто |
| формализуемым) является | сложность алгоритма | . Приведем простой пример. Пусть |
| требуется угадать задуманное число, про которое известно, что оно натуральное |
| и не превосходит 1000. Разрешается задавать вопросы, на которые можно ответить |
| "да" или "нет". Одним из способов (алгоритмов) угадывания может быть такой: |
| последовательно перебираются все числа от 1 до 1000 до тех пор, пока нужное |
| число не будет найдено. В худшем случае для этого потребуется 999 вопросов. |
| Однако можно предложить т другой алгоритм, позволяющий угадать число за 10 |
| вопросов: сначала выясняется, больше ли угаданное число 500 или нет, если да, |
| то больше 750 или нет и т.д. С каждым шагом число возможных кандидатов |
| уменьшается в два раза. Здесь сложностью алгоритма можно считать число |
| вопросов. Тогда первый алгоритм в 100 раз "сложнее" второго. |
| Если алгоритм проводит серии вычислений, сложностью алгоритма можно считать |
| число совершаемых операций. При этом, если в алгоритме встречаются только |
| умножение и сложение, под сложностью часто понимается только число умножений, |
| поскольку эта операция требует существенно большего времени. На практике |
| необходимо также учитывать стоимость операций, выполняемых алгоритмом, и т.п. |
| |
| В математической теории сложности вычислений рассматриваются алгоритмы |
| решения не конкретных задач, а так называемых | массовых задач | . Массовую задачу |
| удобно представлять себе в виде бесконечной серии индивидуальных задач. |
| Индивидуальная задача характеризуется некоторым | размером | , т.е. объемом входных |
| данных, требуемых для описания этой задачи. Если размер индивидуальной задачи |
| - некоторое натуральное число n, тогда сложность алгоритма решения массовой |
| задачи становится функцией от n. |
| рассмотрим алгоритм простого перебора всех двоичных ключей длины n. Ясно, |
| что таких ключей - 2^n, и поэтому в данном алгоритме 2^n шагов, т.е. его |
| сложность равна 2^n. Это простейший пример | экспоненциального | алгоритма (его |
| сложность выражается через n экспонентой). Большинство экспоненциальных |
| алгоритмов - это просто варианты полного перебора. |
| Рассмотрим теперь алгоритм умножения столбиком двух n-значных чисел. Он |
| состоит из n^2 умножений однозначных чисел, т.е. его сложность, измеренная |
| количеством таких умножений, равна n^2. Это - простейший пример |
| полиномиального | алгоритма (его сложность выражается через n полиномом). |
| Достаточно очевидно, что для решения одной и той же математической задачи |
| могут быть предложены различные алгоритмы. Поэтому под | сложностью задачи | |
| понимают минимальную сложность алгоритмов ее решения. |
| В математике есть много задач, для решения которых пока не удалось |
| построить полиномиальный алгоритм. К ним относится, например, задача |
| коммивояжера: есть n городов, соединенных сетью дорог, и для каждой дороги |
| указана стоимость проезда по ней; требуется указать такой маршрут, проходящий |
| через все города, чтобы стоимость проезда по этому маршруту была минимальной. |
| С.А. Дориченко, В.В. Ященко. 25 этюдов о шифрах | |
| |