Алгоритмизация. Алгоритм и его формальное исполнение

1.

Алгоритмизация
Алгоритм и его
формальное
исполнение
1

2.

3.

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

4.

Основные понятия
Исполнитель алгоритма – это тот объект,
для управления которым составлен
алгоритм.
Исполнитель алгоритма – человек или
техническое устройство, выполняющий
определённую
последовательность
действий. У каждого исполнителя есть
свой перечень команд, которые он может
исполнить.
Такой перечень называется системой
команд исполнителя (СКИ).
4

5.

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

6.

Свойства алгоритмов
Каждая команда алгоритма
однозначное действие. Это
называется точностью
должна определять
свойство алгоритма
Детерминированность (определённость) — при
каждом запуске алгоритма с одними и теми же
исходными данными получается один и тот же
результат. Детерминированный алгоритм следует
единственным путём от входных данных к результату.
6

7.

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

8.

Формальное исполнение
алгоритма
Алгоритм
позволяет
формализовать
выполнение
информационного процесса.
Если алгоритм обладает перечисленными свойствами,
то работа по нему будет производится исполнителем
формально ( не вникает в содержание поставленной
задачи, а выполняет последовательность действий).
На этом основана работа программно управляемых
исполнителей-автоматов
8

9.

Что такое программа?
Программа – это алгоритм, записанный на языке
исполнителя.
Иначе можно сказать так: алгоритм и программа не
отличаются по содержанию, но могут отличаться по
форме.
Для алгоритма строго не определяется форма его
представления.
Алгоритм
можно
изобразить
графически, можно – словесно, можно – какиминибудь специальными значками, понятными только
его автору, Но программа должна быть записана
только на языке исполнителя.
9

10.

Алгоритмизация и программирование, Паскаль, 10 класс
10
Способы записи алгоритмов
• естественный язык
установить соединение
пока не принята команда «стоп»
принять команду
выполнить команду
завершить сеанс связи
• псевдокод
установить соединение
нц
принять команду
выполнить команду
кц_при команда = 'stop'
завершить сеанс связи
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

11.

Алгоритмизация и программирование, Паскаль, 10 класс
11
Способы записи алгоритмов
• блок-схема
установить
соединение
принять
команду
выполнить
команду
нет
• программа
setConnection;
repeat
cmd:= getCommand;
executeCommand(cmd);
until cmd = "stop";
closeConnection;
«стоп»?
да
завершить
соединение
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

12.

13.

Решение задач по теме
Алгоритм и
Исполнитель

14.

Пример 1
Цепочка из трех бусин, помеченных латинскими
буквами, формируется по следующему правилу.
В конце цепочки стоит одна из бусин A, B, C.
На первом месте – одна из бусин B, D, C, которой нет
на третьем месте.
В середине – одна из бусин А, C, E, B, не стоящая на
первом месте.
Какая из перечисленных цепочек создана по этому
правилу?
1) CBB
2) EAC
3)BCD
4) BCB

15.

Цепочка из трех бусин, помеченных латинскими буквами,
формируется по следующему правилу. В конце цепочки стоит одна
из бусин A, B, C. На первом месте – одна из бусин B, D, C, которой
нет на третьем месте. В середине – одна из бусин А, C, E, B, не
стоящая на первом месте. Какая из перечисленных цепочек создана
по этому правилу?
1) CBB
2) EAC
3)BCD
4) BCB
Решение (краткий вариант):
проверяем первое условие: «В конце цепочки стоит одна из бусин
A, B, C». Ему не удовлетворяет цепочка BCD, ее можно вычеркнуть:
1) CBB
2) EAC
3)BCD
4) BCB
проверяем второе условие: «На первом месте – одна из бусин B, D,
C, которой нет на третьем месте». Ему не удовлетворяют
цепочки EAC (на первом месте – E) и BCB (на первом и третьем
местах стоит буква B), поэтому остается только вариант CBB:
1) CBB
2) EAC
4) BCB
проверяем третье условие: «В середине – одна из бусин А, C, E, B,
не стоящая на первом месте». К счастью, оставшаяся цепочка
CBB ему удовлетворяет.
Таким образом, правильный ответ – 1.

16.

Пример 2
В понедельник в одном из классов должно быть проведено
4 урока – по математике, физике, информатике и биологии.
Учителя высказали свои пожелания для составления
расписания.
1. Учитель математики хочет иметь первый или второй урок,
2.
учитель физики - второй или третий урок,
3.
учитель информатики – первый или четвертый,
4.
учитель биологии – третий или четвертый.
Какой вариант расписания устроит всех учителей школы?
(Обозначения: М – математика, Ф – физика, И – информатика, Б
– биология)
1) ИМБФ
2) МФБИ
3) МИФБ
4) МБФИ

17.

Решение
В задании требуется выбрать один верный вариант
из четырех предложенных.
Можно решить эту задачу не рассматривая все
возможные варианты составления расписания, а
проанализировать лишь предложенные
варианты ответа.
1. Учитель математики хочет иметь первый или
второй урок. Значит, «М» должна быть на 1-м
или 2-м месте. Пока все предложенные
варианты ответа нам подходят:
1) ИМБФ 2) МФБИ 3) МИФБ 4) МБФИ

18.

2. Учитель физики хочет иметь второй или третий
урок. Значит, вариант 1) ИМБФ («Ф» на 4-м
месте) нам не подходит.
Из предложенных вариантов остаются:
2) МФБИ 3) МИФБ 4) МБФИ
3. Учитель информатики хочет иметь первый или
четвертый уроки. Значит, вариант 3) МИФБ («И»
на 2-м месте) не подходит. Остается:
2) МФБИ 4) МБФИ
4. Учитель биологии хочет иметь третий или
четвертый уроки. Значит, вариант 4) МБФИ («Б»
на 2-м месте) не подходит. Остается: 2) МФБИ
Ответ: 2.

19.

Пример 3
Витя пригласил своего друга Сергея в гости, но не
сказал ему код от цифрового замка своего
подъезда, а послал следующее SMS-сообщение: «в
последовательности чисел 3, 1, 8, 2, 6 все числа
больше 5 разделить на 2, а затем удалить из
полученной последовательности все четные
числа». Выполнив указанные в сообщении
действия, Сергей получил следующий код для
цифрового замка:
1)
2)
3)
4)
3, 1
1, 1, 3
3, 1, 3
3, 3, 1

20.

Ответ - 3

21.

Пример 4
Лена забыла пароль для входа в Windows XP, но
помнила алгоритм его получения из символов
«A153B42FB4» в строке подсказки. Если
последовательность символов «В4» заменить на
«B52» и из получившейся строки удалить все
трехзначные
числа,
то
полученная
последовательность и будет паролем:
1) ABFB52
2) AB42FB52
3) ABFB4
4) AB52FB

22.

Ответ - 1

23.

Пример 5

24.

Пример 6

25.

Пример 7

26.

Пример 8

27.

Черепашья графика
Большие возможности для изучения
алгоритмизации дают Исполнители,
работающие по принципу черепашьей
графики.
Идея черепашьей графики происходит из
учебного языка ЛОГО, созданного в конце
ХХ века американским психологом
С.Пейпертом. В ЛОГО включен
графический исполнитель Черепашка

28.

Пример 9

29.

Пример 10

30.

Примером реализации
черепашьей графики
может служить
Среда Л-ГРАФ