§ 1. Алгоритм и его свойства

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

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

Какими свойствами обладают алгоритмы?

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

Дискретность (прерывность, раздельность) — т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. (Например, вычисление периметра прямоугольника по известным измерениям может быть произведено за 2 шага: 1 - вычислить сумму длины и ширины, 2 - полученную сумму умножить на два.)

Определенность — т.е. каждая команда алгоритма должна быть четкой, однозначной и не оставлять места для произвола. (Благодаря этому свойству выполнение алгоритма носит механический хаpактеp и не требует никаких дополнительных указаний или сведений о решаемой задаче. Например, если в карте поиска клада указано "сделать сто шагов на север", то возникает ряд вопросов: от какой исходной точки, каков размер одного шага и т.д.)

Результативность (или конечность) - т.е. алгоритм должен приводить к решению задачи (к требуемому результату) за конечное число шагов. (Например, невозможно составить алгоритм подсчёта количества всех чётных чисел, т.к. общее количество всех чисел бесконечно.)

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

Детерминированность — т.е. исполнитель должен выполнять команды в строго определённой последовательности. (Например, при приготовлении чая, если одну команду "вскипятить воду в чайнике" переместить на последнее место, то в холодной воде чай так и не заварится.)

Задания для самостоятельного выполнения

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

2) Являются ли алгоритмами:
- правила техники безопасности в кабинете информатики,
- кулинарный рецепт,
- нахождение среднего арифметического нескольких чисел,
- список учеников класса,
- фонетический разбор слова,
- телефонный справочник?

3) Перечисли основные свойства алгоритмов (и проиллюстрируй их собственными примерами)

4) Записано 7 строк, каждая имеет свой индекс – от «0» до «6».
В «0»-й строке записана цифра 0 (ноль). Каждая строка состоит из двух повторений предыдущей и добавленного в конец своего индекса (1-й строке в конце добавлена цифра 1). Ниже показаны первые четыре строки. Сформированные по описанному правилу (в скобках указан индекс строки).
Вот первые 4 строки, созданные по этому правилу:
(0)               0
(1)               001
(2)               0010012
(3)               001001200100123
...
Сколько раз в общей сложности встречается в седьмой строке цифра 3?

5) Некоторый алгоритм из одной цепочки символов-цифр получает новую цепочку следующим образом. Сначала вычисляется длина исходной цепочки символов, если она четна, то из строки удаляется последний символ. Затем символы цепочки переставляются в обратном порядке. Если последний символ – четная цифра, то этот символ удаляется. После этого справа к получившейся цепочке приписывается эта же цепочка. Получившаяся таким образом цепочка является результатом работы алгоритма.
(Например, если исходной цепочкой была цепочка 845112, то результатом работы алгоритма будет цепочка 11541154, а если исходной цепочкой была 51196, то результатом работы алгоритма будет цепочка 6911569115.
Дана цепочка символов 2168. Какая цепочка символов получится, если к данной цепочке применить описанный алгоритм дважды (то есть применить алгоритм к данной цепочке, а затем к результату вновь применить алгоритм)?

Оглавление

§ 1. Алгоритм и его свойства