Управление исполнителями

Что такое алгоритм?
Алгоритм — это точное описание порядка действий некоторого исполнителя.
Исполнитель – это устройство или одушевлённое существо (человек), способное понять и выполнить команды, составляющие алгоритм.
Формальные исполнители: не понимают
(и не могут понять) смысл команд.
Алгоритм – это порядок выполнения действий.

Исполнитель Робот
стенка
Система команд исполнителя (СКИ):
вверх
вниз
вправо
влево
Состояние исполнителя:
Среда — это обстановка, в которой работает исполнитель.

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

Необязательные свойства алгоритма
? Конечность (результативность) — для корректного набора данных алгоритм должен заканчиваться с некоторым результатом (не зацикливаться).
? Корректность — для допустимых исходных данных алгоритм должен приводить к правильному результату.
? Массовость — алгоритм можно использовать для решения множества однотипных задач с различными исходными данными (решение «в буквах»).

Одна задача – много алгоритмов
Задача. Вычислите
S = 1 + 2 + 3 + 4 + 5 + … + 99 + 100
Решение К.Ф. Гаусса:
1 + 100 = 2 + 99 = 3 + 98 = …
= 50 + 51 = 101
S = 50 · 101 = 5050

Управление исполнителями
Ручное (непосредственное, «с пульта»):
Программное (по готовой программе):
бортовой компьютер
Программа — это алгоритм, записанный на языке, понятном компьютеру.

Управление исполнителями
§ 30. Способы записи алгоритмов

Алгоритм «О»
Словесная форма:
Даны два натуральных числа. Пока первое число не меньше второго, заменять его на разность первого и второго. Результат работы алгоритма — полученное первое число.
3
1
2
2
неоднозначность естественных языков

Алгоритм «О»
По шагам:
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4 (Стоп).
Шаг 2. Заменить a на a – b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
не все знают русский язык

Алгоритм «О»
Блок-схема:
начало и конец алгоритма
ввод и вывод данных
условие (выбор)
операции с данными
начало
конец
a < b?
a ← a – b
a, b
a
да
нет
Условные обозначения
присвоить a значение a – b

Ручная прокрутка (трассировка)
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Заменить a на a – b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
4

Переменные
Переменная — это величина, значение которой можно изменять во время работы алгоритма.
Вход: два натуральных числа, a и b.
Шаг 1. Если a < b, перейти к шагу 4.
Шаг 2. Заменить a на a – b.
Шаг 3. Перейти к шагу 1.
Шаг 4. Стоп.
Результат: значение a.
a ← a – b
или
a := a – b
присваивание значения

Языки программирования
Программа — это алгоритм, записанный на языке, понятном компьютеру.
101110000000111100000000
101110110000010000000000
0011101111000011
0111110000000100
0010101111000011
1110101111111000
1100110100100000
Алгоритм «О»:
сложно писать и понимать программы

Язык ассемблера
101110000000111100000000
101110110000010000000000
0011101111000011
0111110000000100
0010101111000011
1110101111111000
1100110100100000
mov ax, 15
mov bx, 4
m: cmp ax, bx
jl end
sub ax, bx
jmp m
end: int 20h
Машинные коды:
Язык ассемблера:
Ассемблер — это программа, которая переводит символьную запись команд в машинные коды.
зависят от процессора!
непереносимость программ

Языки высокого уровня
1) легко понимаются человеком
2) не «привязаны» к командам конкретного процессора
Школьный алгоритмический язык:
цел a, b
a:=15
b:=4
нц пока a>=b
a:=a-b
кц

Языки высокого уровня
1957: FORTRAN = FORmula TRANslator
для решения научных задач
1972: С (Д. Ритчи, К. Томпсон)
С++, C#, Java, JavaScript, …
1991: Python (Г. ван Россум)
Для программирования сайтов:
PHP, JavaScript
Логическое программирование:
Prolog
Учебные языки:
BASIC, Паскаль, Школьный алгоритмический язык

Управление исполнителями
§ 31. Примеры исполнителей

Формальный исполнитель
Формальный исполнитель — это исполнитель, который одну и ту же команду всегда понимает однозначно и выполняет одинаково.
23321
→ А
443
2114
2334
21

Исполнитель Черепаха
вперед 30
вправо 90
вперед 30
вправо 90
вперед 30
вправо 90
вперед 30
вправо 90
градусов
повтори 4 [ вперед 30 вправо 90 ]
число сторон
повтори 12 [ вперед 50 вправо 45 ]
повтори 10 [ вперед 50 вправо 60 ]
шагов

Исполнитель Черепаха
повтори 4 [ вперед 30 вправо 45 ]
незамкнутая ломаная
повтори 45 [ вперед 30 вправо 45
вправо 45]
повтори 12 [ вправо 15 вперед 30
вправо 45 ]
повтори 5 [ вправо 15 вперед 30
вправо 15 ]
повтори 15 [ вправо 80 вперед 30
влево 35 ]

Исполнитель Удвоитель
Работает с одним числом и умеет выполнять с ним две операции (команды):
1. прибавь 1
2. умножь на 2
Программа – это последовательность номеров команд, которые нужно выполнить.
Программа 12211
2
начальное число
3
6
12
13
14
1
2
2
1
1
результат

Исполнитель Удвоитель
прибавь 1
умножь на 2
Какие числа можно получить?
при целом x ≥ 0 x, x+1, x+2, …
при целом x < 0
любые целые
Программа 1212
x
x+1
1
2(x+1)
2
2x+3
1
4x+6
2
а 34?

Исполнитель Шифровальщик
Если цепочка символов начинается с гласной буквы, Шифровальщик переставляет последнюю букву в начало слова, а если с согласной, то меняет местами первую и вторую буквы.
Этот алгоритм применили к слову КОТИК. Какое слово получилось?
Этот алгоритм дважды применили к слову КОТИК. Какое слово получилось?
КОТИК → ОКТИК
КОТИК → ОКТИК → КОКТИ

Исполнитель Шифровальщик
Если в цепочке символов чётное количество букв, Шифровальщик добавляет в середину слова букву Я, а если нечётное – удваивает среднюю букву.
Этот алгоритм применили к слову КОТИК. Какое слово получилось?
Этот алгоритм дважды применили к слову КОТИК. Какое слово получилось?
КОТИК → КОТТИК
КОТИК → КОТТИК → КОТЯТИК

Исполнитель Шифровальщик
АБВГДЕЁЖЗИКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
ПРИВЕТ ВАСЯ
А→Б
П→Р
РСКГЁУ ГБТА
Б→В
Я→А
Р→С
Шифр Цезаря
АВМПЛП
Расшифруйте:
НПСЛПГЭ
ЛМАЛТБ
← ЯБЛОКО
← МОРКОВЬ
← КЛЯКСА

Управление исполнителями
§ 32. Оптимальные программы

Что такое оптимальная программа?
Оптимальная программа — это самая лучшая программа по какому-то показателю.
Напишите две программы для Удвоителя:
3 → … → 7

Составление программы
Используя команды:
1. прибавь 1
2. умножь на 2
написать самую короткую программу, которая из 6 получает 28.
Ответ: 122
6
7
25
1
дерево вариантов
12
8
14
13
24
9
16
15
28
14
26
48
2
1
1
1
1
1
2
2
2
2
2
1
1
2
2
2