Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Интуитивное представление об алгоритмах

Интуитивное представление об алгоритмах


Общее понятие алгоритма


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


Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаем, что они регламентированы определенным алгоритмом — четкой системой инструкций. Например, наши действия при входе в магазин "Универсам" (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролеру, взять свою сумку, переложить в нее продукты, сдать корзину, покинуть магазин). Второй пример — приготовление манной каши (500 мл молока довести до кипения, при тщательном помешивании засыпать 100 г манной крупы, при помешивании довести до кипения и варить 10 минут). Автоматизм выполнения этих и многих других действий не позволяет нам осознавать их алгоритмическую сущность.


Но есть немало таких действий, выполняя которые, мы тщательно следуем той или иной инструкции. Это главным образом непривычные действия, профессионально не свойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для пленки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению: "Содержимое большого пакета растворить в 350 мл воды при температуре 18— 20 °С. Там же растворить содержимое малого пакета. Объем раствора довести до 500 мл. Раствор профильтровать. Проявлять 3—4 роликовых фотопленки". Второй пример: если вы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания.


Большое количество алгоритмов встречается при изучении математики буквально с первых классов школы. Это прежде всего алгоритмы выполнения четырех арифметических действий над различными числами — натуральными, целыми, дробными, комплексными. Вот пример такого алгоритма: "Чтобы из одной десятичной дроби вычесть другую, надо: 1) уравнять число знаков после запятой в уменьшаемом и вычитаемом; 2) записать вычитаемое под уменьшаемым так, чтобы запятая оказалась под запятой; 3) произвести вычитание так, как вычитают натуральные числа; 4) поставить в полученной разности запятую под запятыми в уменьшаемом и вычитаемом".


Вот пример алгоритма сложения приближенных чисел. Найти сумму чисел [math]p,\,q[/math] и [math]s[/math], где [math]p=3,\!1416,~ q=2,\!718[/math] и [math]s=7,\!45[/math].


1. Выделим слагаемое с наименьшим числом десятичных знаков. Таким слагаемым является число 7,45 (два десятичных знака).


2. Округлим остальные слагаемые, оставляя в них столько десятичных знаков, сколько их имеется в выделенном слагаемом: [math]3,\!1416=3,\!14;~ 2,\!718=2,\!72[/math].


3. Выполним сложение приближенных значений чисел: [math]3,\!14+2,\!72+7,\!45= 13,\!31[/math].


Итак, [math]p+q+s\approx13,\!31[/math].


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


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


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




Неформальное понятие алгоритма


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


Каждый алгоритм предполагает наличие некоторых начальных, или исходных, данных, а в результате применения приводит к получению определенного искомого результата. Например, в алгоритме с проявителем начальные данные — содержимое большого и малого пакетов, вода. Искомый результат — готовый к употреблению проявитель для пленки. При вычислении ранга матрицы начальными данными служит прямоугольная таблица, составленная из [math]m\cdot n[/math] рациональных чисел, результат — натуральное число, являющееся рангом данной матрицы.

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


Существенной чертой алгоритма является его массовый характер, т. е. возможность применять его к обширному классу начальных данных, возможность достаточно широко эти начальные данные варьировать. Другими словами, каждый алгоритм призван решить ту или иную массовую проблему, т.е. решать класс однотипных задач. Например, задача нахождения наибольшего общего делителя чисел 4 и 6 есть единичная проблема (можно решить ее и без применения алгоритма Евклида), но задача нахождения наибольшего общего делителя произвольных натуральных чисел [math]m[/math] и [math]n[/math] — уже проблема массовая. Суть алгоритма Евклида состоит в том, что он приводит к желаемому результату вне зависимости от выбора конкретной пары натуральных чисел, в то время как при решении указанной единичной проблемы можно предложить такой способ, который окажется неприменимым для другой пары натуральных чисел.


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


Говоря о начальных данных для алгоритма, имеют в виду так называемые допустимые начальные данные, т.е. такие начальные данные, которые сформулированы в терминах данного алгоритма. Так, к числу допустимых начальных данных для алгоритма варки манной каши никак не отнесешь элементы множества натуральных чисел, а к числу начальных данных алгоритма Евклида — молоко и манную крупу (или даже комплексные числа).


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


Пример 31.1. Приведем пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 5,1 и 3 являются для него допустимыми начальными данными, применение к которым алгоритма деления приводит к искомому результату 1,7. Иная картина возникает для чисел 20 и 3, которые также представляют собой допустимые начальные данные. Для них получается алгоритмический процесс:


Деление в столбик

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


Пример 31.2. Теперь приведем пример алгоритма, заходящего в тупик, безрезультатно обрывающегося. Вот его предписания.


1. Исходное число умножить на 2. Перейти к выполнению п. 2.
2. К полученному числу прибавить 1. Перейти к выполнению п. 3.
3. Определить остаток [math]y[/math] от деления полученной в п. 2 суммы на 3. Перейти к выполнению п. 4.
4. Разделить исходное число на [math]y[/math]. Частное является искомым результатом. Конец.

Пусть натуральные (целые положительные) числа будут допустимыми начальными данными для этого алгоритма. Для числа 6 алгоритмический процесс будет проходить так:


1-й шаг: [math]6\cdo2=12[/math]; переходим к п. 2;
2-й шаг: [math]12+1=13[/math]; переходим к п. 3;
3-й шаг: [math]y=1[/math], переходим к п. 4;
4-й шаг: [math]6\,\colon1=6[/math]. Конец.

Искомый результат равен 6. Иначе будет протекать алгоритмический процесс для исходного данного 7:


1-й шаг: [math]7\cdo2=14[/math]; переходим к п. 2;
2-й шаг: [math]14+1=15[/math]; переходим к п. 3;
3-й шаг: [math]y=0[/math]; переходим к п. 4;
4-й шаг: [math]7\,\colon0[/math] — деление невозможно. Процесс зашел в тупик, натолкнулся на препятствие и безрезультатно оборвался.

Итак, подводя итоги обсуждению характерных свойств и особенностей алгоритма, можем сформулировать следующее интуитивно описательное определение этого понятия.


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


Отметим в заключение, что сам термин "алгоритм" (или "алгорифм") происходит от имени великого среднеазиатского ученого Мухаммеда аль-Хорезми (787 — ок. 850). В своем трактате, написанном по-арабски, латинская версия которого относится к XII в. и начинается словами "Dixit algorizm", т.е. "Сказал аль-Хорезми", им среди прочего была описана индийская позиционная система чисел и сформулированы правила выполнения четырех арифметических действий над числами в десятичной записи.




Необходимость уточнения понятия алгоритма


Понятие алгоритма формировалось с древнейших времен, но до конца первой трети XX в. математики довольствовались интуитивным представлением об этом объекте. Термин "алгоритм" употреблялся в математике лишь в связи с теми или иными конкретными алгоритмами. Утверждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием.


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


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


Первые работы по уточнению понятия алгоритма и его изучению, т.е. по теории алгоритмов, были выполнены в 1936–1937 гг. математиками А.Тьюрингом, Э. Постом, Ж.Эрбраном, К.Гёделем, А.А. Марковым, А.Чёрчем. Было выработано несколько определений понятия алгоритма, но впоследствии выяснилось, что все они равносильны между собой, т.е. определяют одно и то же понятие.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved