Лекция 14. Алгоритмы и их свойства

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

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

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

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

Происхождение термина «алгоритм» связано с математикой. История его возникновения такова. В IХ веке в Багдаде жил ученый ал(аль)-Хорезми (полное имя Мухаммед Бен Мусса ал-Хорезми, т.е. Мухаммед сын Мусы из Хорезма), математик, астроном, географ. В одном из своих трудов он описал десятичную систему счисления и впервые сформулировал правила выполнения арифметических действий над целыми числами и обыкновенными дробями. Арабский оригинал этой книги был утерян, но остался латинский перевод ХII в., по которому Западная Европа ознакомилась с десятичной системой счисления и правилами выполнения арифметических действий.

Ал-Хорезми стремился к тому, чтобы сформулированные им правила были понятными. Достичь этого в IХ в., когда еще не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и т.д.), было трудно. Однако ему удалось выработать четкий стиль строгого словесного предписания, который не давал читателю возможность уклониться от предписанного или пропустить какие-нибудь действия.

Правила в книгах ал-Хорезми в латинском переводе начинались словами «Алгоризми сказал». В других латинских переводах автор именовался как Алгоритмус. Со временем было забыто, что Алгоризми (Алгоритмус) – это автор правил, и эти правила стали называть алгоритмами. Многие столетия разрабатывались алгоритмы для решения все новых и новых классов задач, но само понятие алгоритма не имело точного математического определения.

В настоящее время понятие алгоритма уточнено, и сделано это в ХХ веке в рамках науки, называемой теорией алгоритмов.

Будем рассматривать алгоритм как программу действий для решения задач определенного типа.

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

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

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

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

Дискретная структура алгоритмов хорошо вида в алгоритмах выполнения арифметических действий. Например, алгоритм нахождения суммы чисел 34 + 23 формулируется так:

1) Пишу десятки под десятками, а единицы под единицами.

2) Складываю единицы: 4 + 3 = 7, пишу 7 под единицами.

3) Складываю десятки: 3 + 2 = 5, пишу 5 под десятками.

3. Каждый шаг программы, задающей алгоритм, должен состоять из выполнимых действий. Это означает, что предусмотренные действия были выполнимы теми исполнителями, которым она адресована. Так, например, задание «решить уравнение х + 9 = 17» один ученик уверенно выполняет и получает искомое значение переменной х, так как владеет всеми действиями, необходимыми для решения простейших уравнений.

2) вспомни правило, как найти значение неизвестного;

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

Как видно из примера, под словом «действие» понимаются не только математические операции, но оно имеет и более широкий смысл.

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

Все сказанное характеризует свойство алгоритма, называемое свойством понятности.

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

5. Программа, задающая алгоритм, должна быть применима к любой задаче рассматриваемого типа. Другими словами, каждый алгоритм решения линейного уравнения первой степени применяется для решения всех уравнений вида ах + b = 0. В этом состоит свойство массовости алгоритма.

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

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

1) определить значение истинности высказывания А;

2) определить значение истинности высказывания В;

3) определить значение истинности высказывания А ∧ В.

Так как операция конъюнкции коммутативна, т.е. А ∧ В ⇔ В ∧ А, то пункты 1) и 2) можно поменять местами. Такой выбор последовательности шагов осуществляет исполнитель-человек, но не машина. Если свойства детерминированности и дискретности сохраняются с некоторой степенью точности, т.е. в программе возможна перестановка шагов или она содержит желательные, но не обязательные шаги, то мы имеем не алгоритм, а алгоритмическое предписание. Однако, несмотря на различия между этими понятиями, часто алгоритмические предписания называются алгоритмами.

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: