СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ

Благодаря готовым учебным материалам для работы в классе и дистанционно

Скидки до 50 % на комплекты
только до 11.07.2025

Готовые ключевые этапы урока всегда будут у вас под рукой

Организационный момент

Проверка знаний

Объяснение материала

Закрепление изученного

Итоги урока

ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ.Свойства алгоритма

Категория: Информатика

Нажмите, чтобы узнать подробности

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

Просмотр содержимого документа
«ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ.Свойства алгоритма»

Свойства алгоритма


ПОНЯТЬ


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

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

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

Шаг алгоритма для разных исполнителей может быть различной степени детализации.

Пример

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

Алгоритм 1

Алгоритм 2

  1. Ввести значения переменных а и b

  2. Перемножить введенные значения, результат записать в R

  3. Сообщить результат R

  1. Ввести значения переменных a, b

  2. Вычислить абсолютное значение первой переменной, результат записать в a1

  3. Вычислить абсолютное значение второй переменной, результат записать в b1

  4. Перемножить значения а1 и b1, результат записать в R

  5. Если переменные a и b одного знака, то приписать R знак “+”, иначе приписать R знак “–”

  6. Сообщить результат R

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

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


2. Определенность (детерминированность). Свойство определённости включает в себя два аспекта. С одной стороны, каждый шаг алгоритма должен пониматься исполнителем однозначно – единственным образом, не допуская множественности толкований. Не допускаются двусмысленность, апелляция к “здравому смыслу”, недоговоренность и т.д. С другой стороны, после выполнения каждого очередного шага должно быть точно определено, завершено ли исполнение алгоритма или же какой шаг будет выполняться следующим. То есть каждый шаг и порядок его выполнения должны быть точно и однозначно определены.


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

Пример

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

Программа, написанная на одном из языков программирования (например, Basic) не будет являться алгоритмом для транслятора с другого языка (например, Pascal).


4 Результативность. Исполнение алгоритма должно приводить к какому-либо результату за конечное число шагов.

Пример

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

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

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

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

Замечание 2. Абсолютно точные результаты возможны лишь при строго теоретических расчетах. На практике результаты получаются с определенной погрешностью (различают погрешности измерения, вычисления, моделирования и др.). Например, погрешность фиксации результатов на беговых дистанциях при помощи ручного секундомера составляет примерно 0,03 сек.; использование комплекса электронной аппаратуры снижает погрешность до 0,001 сек.

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


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

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

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

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

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


Перечисленные свойства являются основными для алгоритмов. Есть еще два дополнительных свойства: эффективность и массовость.


6. Эффективность. Это свойство позволяет оценить ресурсы, необходимые для выполнения алгоритма.

Заметим, что говорить об эффективности имеет смысл, если сравниваются разные алгоритмы решения одной и той же задачи. Оценивают алгоритмы по трудоёмкости, точности вычислений, времени решения и так далее. Как правило, когда мы говорим об эффективности алгоритма, то имеем в виду сравнение различных алгоритмов с точки зрения одного заранее выбранного критерия. При решении задач с помощью компьютера такими критериями выступают объем необходимой памяти, количество операций, необходимость подключения дополнительных устройств или программ. Как ни странно, наиболее эффективные алгоритмы всегда самые простые, но найти их бывает очень трудно. Разрабатывая алгоритм, нужно помнить совет Альберта Эйнштейна: «Все должно быть сделано настолько просто, насколько это возможно, но не проще».


7. Массовость. Свойство массовости также включает в себя два аспекта. С одной стороны, алгоритм целесообразно разрабатывать в случае, если его можно будет применять для решения множества однотипных задач, варьируя, в допустимых пределах, исходные данные. То есть алгоритм применяется многократно к различным исходным данным, удовлетворяющим условию задачи. Например, алгоритм решения квадратного уравнения обладает свойством массовости, так как его можно применить для любых a, b, c, причём а≠0.

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

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


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

  1. совокупность возможных исходных данных;

  2. совокупность возможных результатов;

  3. совокупность возможных промежуточных результатов;

  4. правило начала;

  5. правила непосредственной обработки данных;

  6. правило окончания;

  7. правило извлечения (сообщения) результата.

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

Пример

При решении квадратного уравнения ax2+bx+c=0 исходными данными будут коэффициенты а, b, c. Результатом будет либо сообщение, что корней нет, либо значение одного корня, либо значения двух корней. Промежуточным результатом будет значение дискриминанта. Начало алгоритма возможно, если введены значения коэффициентов. Обработка данных идет в соответствии с методом нахождения корней уравнения по дискриминанту. Правило окончания – получения одного из возможных результатов. Результат можно вывести на дисплей или записать в файл.


ЗНАТЬ


Свойства алгоритма

Название свойства

Содержание свойства

Дискретность


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

Детерминированность


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

Понятность,

ясность

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

Результативность

Исполнение алгоритма должно приводить к решению поставленной задачи за конечное число шагов.

Правильность

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

Эффективность


Простота, изящество алгоритма.

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

Массовость

в). Алгоритм целесообразно разрабатывать в случае, если:

- его можно применять для решения множества однотипных задач, изменяя в допустимых пределах исходные данные;

- требуется безошибочно и быстро обработать большой массив данных.


Параметры алгоритма:

  1. совокупность возможных значений исходных данных;

  2. совокупность возможных значений результатов;

  3. совокупность возможных промежуточных результатов;

  4. правило начала;

  5. правила непосредственной обработки данных;

  6. правило окончания;

  7. правило вывода результата.


УМЕТЬ


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


  1. Сформулируйте алгоритм решения линейного уравнения ax+b=0 для любых возможных значений коэффициентов а и b. Какими свойствами он обладает? Из каких элементарных шагов состоит? Кто может быть исполнителем Вашего алгоритма?


3. Дана последовательность действий:

1. Задать значения переменных М и N - целые положительные числа

2. Если М

3. Положить М равным M - N (то есть уменьшить значение М на N)

4. Повторить действия, начиная с пункта 2

5. Сообщить значение переменной М

Докажите, что эта последовательность является алгоритмом вычисления остатка от деления числа М на число N.

Сколько элементарных шагов потребуется выполнить, если М = 37, N = 12? Что будет являться результатом выполнения алгоритма?


4. Следующие алгоритмы отличаются друг от друга только порядком выполнения 3 и 4 шагов. Будут ли совпадать результаты выполнения алгоритмов?


Алгоритм 1


Алгоритм 2

1. Пусть А равно 3

2. Пусть В равно 5

3. Заменить А на сумму А + В

4. Заменить В на разность В - А

5. Сообщить значения А и В


1. Пусть А равно 3

2. Пусть В равно 5

3. Заменить В на разность В - А

4. Заменить А на сумму А + В

5. Сообщить значения А и В


ПРАКТИКУМ


Работа с исполнителем Черепашка.

Система команд Черепашки (N, U, K – натуральные числа):

по - перо опусти

пп - перо подними

вп N - вперёд на N шагов

нд N - назад на N шагов

пр U - направо на U градусов

лв U- налево на U градусов

повтори K [ команда1 команда2 …] - повторение команд K раз


Составить программы для создания изображений:

1

2

3




4

Составить программу, выполняя которую Черепашка «напишет» Ваше имя




Скачать

Рекомендуем курсы ПК и ППК для учителей

Вебинар для учителей

Свидетельство об участии БЕСПЛАТНО!