1. Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - максимальное число, кратное 5.
3. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, кратных 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - количество чисел, кратных 4
5.Напишите программу, которая в последовательности натуральных чисел определяет сумму чисел, кратных 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 3. Количество чисел не превышает 100. В ведённые числа не превышают 300. Программа должна вывести одно число - сумму чисел, кратных 3.
7. Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, кратное 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число - максимальное число, кратное 4.
9. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, оканчивающихся на 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 3. Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число - количество чисел, оканчивающихся на 3.
13. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, оканчивающихся на 6. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 6. Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число - количество чисел, оканчивающихся на 6.
15. Напишите программу, к оторая в последовательности натуральных чисел определяет сумму чисел, кратных 5. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 5. Количество чисел не превышает 100. В ведённые числа не превышают 300. Программа должна вывести одно число - сумму чисел, кратных 5.
17. Напишите программу, которая в последовательности натуральных чисел определяет определяет сумму всех чисел, кратных 6 и оканчивающихся на 4. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: сумму всех чисел, кратных 6 и оканчивающихся на 4.
19. Напишите программу для решения следующей задачи. Камера наблюдения регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей, округляя значения скорости до целых чисел. Необходимо определить максимальную зарегистрированную скорость автомобиля. Е сли скорость хотя бы одного автомобиля была меньше 30 км/ч, выведите «YES», иначе выведите «N0». Программа получает на вх од число проехавших автомобилей N (1 < N < 30), затем указываются их скорости. Значение скорости не может быть меньше 1 и больше 300.Программа должна сначала вывести максимальную скорость, затем Y E S или NO.
| Входные данные | Выходные данные |
| no |
21. Напишите программу для решения следующей задачи. Камера наблюдения регистрирует в автоматическом режиме скорость проезжающих мимо неё автомобилей, округляя значения скорости до целых чисел. Необходимо определить максимальную зарегистрированную скорость автомобиля. Если скорость хотя бы одного автомобиля была не меньше 60 км/ч, выведите «YES», иначе выведите «N0».
Программа получает на вход число проехавших автомобилей N (1 =< N =< 30), затем указываются их скорости. Значение скорости не может быть меньше 1 и больше 300. Программа должна сначала вывести среднюю скорость с точностью до одного знака после запятой, затем «YES» или «N0».
23. 
| Входные данные | Выходные данные |
25. Напишите программу, которая в последовательности целых чисел определяет их сумму и количество чётных чисел, кратных 5. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: сумму последовательности и количество чётных чисел, кратных 5.
27. Напишите программу, которая в последовательности целых чисел определяет их сумму и подсчитывает разность количества положительных и отрицательных чисел последовательности. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: сумму чисел и разность количества положительных и отрицательных чисел.
28. Напишите программу, которая в последовательности целых чисел определяет их количество и подсчитывает сумму положительных чётных чисел, не превосходящих 256. Программа получает на вход целые числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа по модулю не превышают 30 000. Программа должна вывести два числа: длину последовательности и сумму положительных чётных чисел, не превосходящих 256.
29. Напишите программу, которая в последовательности натуральных чисел определяет количество всех чётных чисел, кратных 5. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: количество всех чётных чисел, кратных 5.
31. Напишите программу, которая в последовательности натуральных чисел определяет сумму всех чисел, кратных 7 и оканчивающихся на 2. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30 000. Программа должна вывести одно число: сумму всех чисел, кратных 7 и оканчивающихся на 2.
33. Напишите программу, которая в последовательности натуральных чисел определяет сумму всех чисел, кратных 8 и оканчивающихся на 6. Программа получает на вход натуральные числа, количество введённых чисел неизвестно, последовательность чисел заканчивается числом 0 (0 - признак окончания ввода, не входит в последовательность). Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число: сумму всех натуральных чисел, кратных 8 и оканчивающихся на 6.
35. Введите с клавиатуры 5 положительных целых чисел. Вычислите сумму тех из них, которые делятся на 4 и при этом заканчиваются на 6. Программа должна вывести одно число: сумму чисел, введенных с клавиатуры, кратных 4 и оканчивающихся на 6.
| Входные данные | Выходные данные |
37. Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, оканчивающееся на 4. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 4. Количество чисел не превышает 1000. В ведённые числа не превышают 30000. Программа должна вывести одно число - минимальное число, оканчивающееся на 4.
Математические основы информатики
А.Г. Гейн
Учебный план
| №_ГАЗЕТЫ | Лекция |
Лекция 1.
Что такое
“математические основы информатики”.
Почему
информатику нередко считают близкой род- Информация и ее кодирование. Математика кодов. Коды, исправляющие ошибки. Экономное кодирование. |
|
| Лекция 2
. Математические модели
формальных исполнителей.
Что такое формальная
обработка информации? Конеч- ные автоматы. Что первично: язык или исполнитель? Грамматика языка. Распознаваемые языки. Универсальные исполни- тели (машина Тьюринга, машина Поста). |
|
| Лекция 3 . Алгоритм и его свойства. Алгоритмическая неразрешимость. Вычислимость. Сложность. | |
| Контрольная работа № 1. | |
| Лекция 4.
Графы
. Графы и орграфы. В каких
задачах они возникают? Различные свойства графов
(эйлеровость, гамильто- новость, планарность, двудольность). Сети. Потоки в сетях. Представление графов. Основные алгоритмы на графах. |
|
| Лекция 5
. Логические модели в информатике.
Алгебра высказываний. Булевы функции.
Нормальные формы. Полные классы булевых функций. Релейно-контактные схемы. Вентили. Математические модели процессора и памяти компьютера. Предикаты и отношения. Реляционная алгебра. Теоретические основы реляционных СУБД. Языки логического программирования и их математическое основание. |
|
| Контрольная работа № 2. | |
| Лекция 6
. Компьютерная теория чисел и
вычислительная геометрия.
Зачем нужна теория
чисел в компьютерных науках? Гонка за простыми числами. Как разложить число на множители? Чем отличается теоретическая геометрия от вычислительной? Почему гладко на бумаге, но коряво на компьютере? Основные правила и алгоритмы вычислительной геометрии. |
|
| 23/2007 | Лекция 7
. Защита информации
. Защита
символьной информации. Что нужно защищать?
Электронная подпись. Системы верификации. Криптосистемы с открытым ключом. Защита графической информации. Математика электронных водяных знаков. |
| 24/2007 | Лекция 8 . Основы методики преподавания математических основ информатики. |
| Итоговая работа |
Лекция 2.
Математические модели формальных исполнителей
“Изяществу зябко в этом суетном свете”. Такую фразу сочинил компьютер по одной из первых программ генерации текстов на естественных языках. Но эмоция, переданная этой фразой, конечно, недоступна компьютеру. И смысл этой фразы компьютер понять не может. Потому что он - всего лишь формальный исполнитель.
В нашем общественном сознании слово “формальный” имеет, как правило, негативный оттенок. Презрительным клеймом “формалист” мы награждаем чиновника, который действует исключительно на основании данных ему предписаний, не желая вникать в суть поставленной перед ним проблемы.
Но всегда ли плохо быть формальным исполнителем? Будет ли рад хозяин овчарки, когда по команде “Фас!” его четвероногий друг задумается, стоит ли связываться с бандитом. Или когда самолет в ответ на движение пилотом штурвала продолжит лететь прежним курсом, потому что разворот делать не хочется. А оператор ядерного реактора, забросив инструкцию, будет управлять им по наитию. Согласитесь, что даже человеку временами быть формальным исполнителем просто необходимо. Что касается устройств для автоматической обработки информации, для них неформальный путь просто невозможен. Напомним, что, как отмечалось в лекции 1, информатика занимается изучением как раз процессов автоматизированной обработки информации.
Обработка (преобразование) информации - достаточно широко понимаемый информационный процесс. Под обработкой информации понимают получение новой информации из уже имеющейся или преобразование формы представления информации.
Детектив собрал улики и указал, кто совершил преступление. Математик сопоставил известные ему утверждения и доказал новую теорему. Д.И. Менделеев на основе информации о химических свойствах элементов сформулировал периодический закон. Во всех этих примерах в результате обработки информации появилась новая информация.
Обработкой информации следует признать и вычисление суммы двух чисел - ведь из двух известных данных получается новое, до того неизвестное. Обработкой информации является и, например, перевод предложения с русского языка на иностранный.
На первый взгляд между процессами
обработки информации, указанными в двух
предыдущих абзацах, большая разница. Главное
отличие здесь в том, что для розыска преступника
или доказательства новой теоремы нет и не может
быть указано жестких правил, как должна
обрабатываться исходная информация. Как говорят,
человек в этих случаях действует эвристически
.
Складывая два числа, мы уже руководствуемся
жестко указанными правилами. Такую работу можно
поручить техническому устройству, которое
способно понимать и исполнять предписанную ему
инструкцию. Устройства, управляемые с помощью
инструкций и выполняющие свою работу
автоматически, называют программируемыми и
говорят, что свою работу они исполняют формально.
В частности, можно говорить и о формальной
обработке информации. Исполнитель, производящий
такую обработку, не должен вникать в смысл
выполняемых им действий; поэтому формальная
обработка информации, как правило, касается
изменения формы ее представления, а не
содержания.
Итак, под обработкой информации удобно понимать любое преобразование ее содержания или формы представления.
Однако каким бы ни был способ обработки информации - формальным или эвристическим, существует нечто или некто, выполняющий эту обработку. Его обычно называют исполнителем .
Формальные исполнители могут быть устроены весьма по-разному. Чтобы их изучать, как и в любой науке, используется моделирование. Какие математические модели применяют для исследования формальных исполнителей, мы и расскажем в этой лекции.
§ 3. Формальный исполнитель: автомат
Человек весьма преуспел в создании разнообразных устройств, выполняющих ту или иную работу в соответствии с четкой инструкцией. При этом он уже не обязан постоянно находиться около этого устройства, чтобы управлять им. В этом случае говорят, что устройство выполняет работу автоматически, а само такое устройство называют автоматом .
В реальности автоматы бывают весьма разными. Это может быть автомат по продаже билетов на поезда пригородного сообщения, или автомат по расфасовке готовой продукции, или автомат по изготовлению каких-либо деталей. Автоматы последнего вида нередко называют промышленными роботами .
С точки зрения информатики совершенно все равно, из чего сделан автомат. Важно лишь то, что он воспринимает некоторые сигналы как команды и по каждой команде выполняет некоторое действие, переходя из одного состояния в другое. Поэтому можно считать, что каждый автомат описывается набором возможных состояний, списком допустимых команд и перечислением того, из какого состояния в какое переходит автомат под воздействием каждой команды. Например, если команд только две, то их можно обозначить буквами, скажем, a и b , или цифрами, состояния автомата - буквами q 1, q 2, ..., qm , а перечислить варианты перехода из одного состояния в другое можно с помощью таблицы (см. табл. 1).
Таблица 1
В клетке, стоящей на пересечении строки и столбца, указывается то состояние, в которое переходит автомат, находившийся в состоянии, которое указано в заголовке того же столбца, и получивший команду, указанную в заголовке той же строки. Каждому ясно, что такая таблица представляет собой информационную модель реального автомата.
Автомат можно описать и другой информационной моделью - орграфом*. Вершинами орграфа являются состояния автомата, дугами - переходы из одного состояния в другое. На каждой дуге имеется отметка, показывающая, по какой команде осуществляется переход. Тогда автомат, описанный табл. 2, изобразится так, как показано на рис. 1.
Таблица 2
Одно из состояний называется начальным - именно в нем находится автомат до начала работы. Договоримся начальное состояние всегда обозначать q 1. Некоторые из состояний являются заключительными - приведение автомата в это состояние является целью управления автоматом с помощью той или иной последовательности команд. Например, если это автомат по продаже железнодорожных билетов, то в начальном состоянии автомат ожидает, что в монетоприемник начнут поступать монеты. Конечных состояний два: выдача билета и возврат денег. Кроме того, имеются промежуточные состояния - подсчет суммы денег, переданных в автомат к этому моменту. Команды, переводящие автомат из одного состояния в другое, - это опускание монеты в монетоприемник, нажатие кнопки выдачи билета или нажатие кнопки возврата денег. Обозначать тот факт, что данное состояние конечное, будем буквой К в скобках около обозначения данного состояния. Например, q 2 (К).
Ясно, что целью управления автоматом является выдача ему такой последовательности команд, которая переводит его из начального состояния в какое-либо конечное. Поскольку каждая команда обозначена буквой, то набор команд, понимаемых данным автоматом, можно считать некоторым алфавитом А . Тогда последовательность команд, т.е. программа, будет записываться как слово в этом алфавите. Например, слово abа переводит автомат, описанный табл. 2, из начального состояния q 1 в состояние q 4 . Можно сказать, что слово abа задает на орграфе данного автомата некоторый маршрут из состояния q 1 в состояние q 4 .
Множество всех тех слов, которые переводят автомат из начального состояния в одно из конечных состояний, образует некий формальный язык. Этот язык называется языком, распознаваемым данным автоматом . Если для некоторого языка существует хотя бы один автомат, который этот язык распознает, то такой язык называют распознаваемым .
На рис. 2 изображен автомат, имеющий два состояния - q 1 (К) и q 2 - и понимающий две команды, которые обозначены цифрами 0 и 1. Легко сообразить, что распознаваемый этим автоматом язык состоит из тех и только тех слов, которые содержат четное количество единиц и любое количество нулей. Иными словами, этот автомат подсчитывает сумму цифр в числе, записанном в двоичной системе счисления.
Пусть теперь у нас имеется фиксированный алфавит А , и L - некоторое множество слов, составленное из символов данного алфавита. Всегда ли можно построить такой автомат, чтобы множество L было для него распознаваемым языком? Ответ отрицателен.
Теорема. Пусть А = {a , b }, L = {a n b n , где n пробегает множество всех натуральных чисел}. Множество L не является распознаваемым языком.
Запись a n , фигурирующая в формулировке этой теоремы, означает, что буква а повторена n раз.
Доказательство теоремы использует один из важнейших математических методов - от противного. Итак, предположим, что L - распознаваемый язык. Значит, существует такой автомат, который любым словом этого языка переводится в некоторое конечное состояние. Пусть этот автомат имеет k состояний. Рассмотрим слово a k b k . Оно принадлежит языку L и, следовательно, переводит этот автомат из начального состояния q 1 в некоторое конечное состояние q s . Поскольку буква а повторяется не меньшее число раз, чем количество состояний автомата, найдется такое состояние q t , которое за первые k применений буквы а будет пройдено дважды (см. рис. 3). Пусть первый раз автомат перейдет в состояние q t в результате применения a u , а следующий раз окажется в том же состоянии после применения a u + v . Рассмотрим слово a k + v b k . Ясно, что применение этого слова к начальному состоянию q 1 переведет его в то же самое конечное состояние q s . Это означает, что данное слово также распознаваемо данным автоматом и, значит, должно принадлежать языку L . Но в множестве L такого слова нет. Полученное противоречие показывает, что сделанное допущение неверно, т.е. автомата, для которого данное множество служило бы распознаваемым языком, не существует.
Рис. 3. Маршрут на орграфе автомата от начального состояния q 1 до конечного состояния q s (до состояния q t буква а на дугах стоит u раз, на цикле - еще v раз)
Раз не всякое множество слов представляет собой распознаваемый язык, возникает вопрос, какие множества годятся для этого. Математики нашли удобные способы описания распознаваемых языков, и эти способы легли в основу конструирования всех ныне существующих языков программирования.
Вопросы и задания
1. Какими двумя информационными моделями может быть представлен автомат?
2. Что такое язык, распознаваемый данным автоматом?
3. Какой язык называется распознаваемым?
4. Для автомата, изображенного на рис. 1, определите, в каком состоянии он будет находиться после исполнения последовательности команд
а) abba ; в) babaabaaa ;
б) ababbabbb ; г)* a n b n .
5. Для автомата, изображенного на рис. 2, составьте описание в форме таблицы.
6. Постройте в виде графа информационную модель автомата, заданного табл. 3.
Таблица 3
7. Какой язык над двухсимвольным алфавитом {0, 1} распознается автоматом, изображенным на рис. 4?
Рис. 4
8. Какой язык над двухсимвольным алфавитом {a , b } распознается автоматом, заданным табл. 3?
9. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, содержащих ровно 5 подряд идущих единиц.
10. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, содержащих ровно 5 единиц.
11. Изобразите в виде графа информационную модель автомата, который бы распознавал язык над алфавитом {0, 1}, состоящий из всех слов, начинающихся с единицы (т.е. этот автомат отличает натуральные числа, записанные в двоичной системе счисления, от произвольных последовательностей символов 0 и 1).
12. Среди перечисленных ниже языков L 1 , L 2 , L 3 , L 4 , определенных над двухсимвольным алфавитом {1; 2}, укажите распознаваемые. Для каждого из распознаваемых языков постройте распознающий его автомат, для каждого из нераспознаваемых языков докажите, что он нераспознаваем.
а) L 1 состоит из всех слов, которые представляют собой четные натуральные числа, начинающиеся с цифры 1;
б) L 2 состоит из всех слов, количество единиц в которых - это натуральное число, оканчивающееся цифрой 3;
в) L 3 состоит из всех слов, в которых количество двоек является простым числом;
г) L 4 состоит из всех слов, которые представляют собой натуральные числа, делящиеся на 3.
13. В чем с точки зрения информатики заключается разница “в жизни по законам” и “в жизни по понятиям”?
§ 4. Универсальный исполнитель
Компьютерные игры... Наверно, каждый, кто хоть однажды имел дело с компьютером, видел, а возможно, и сам играл в какую-либо компьютерную игру. На экране одни объекты в виде живых существ или технических устройств подчиняются командам играющего, другие - управляются компьютером, который исполняет заданную программу. Все эти объекты - формальные исполнители, каждый со своим набором допустимых действий. Только объекты эти не реальные, а имитируемые компьютером. Получается, что с помощью одного формального исполнителя имитируются другие.
Если попытаться сформулировать, что значит один исполнитель имитируется с помощью другого, то получится следующее. Говорят, что формальный исполнитель А имитирует формального исполнителя В , если
Каждому объекту, над которым выполняет действия исполнитель В , однозначно соответствует объект, над которым выполняет действия исполнитель А (имитация среды исполнителя);
Каждому допустимому действию исполнителя В над тем или иным объектом среды однозначно сопоставлено допустимое действие исполнителя А над соответствующим объектом его среды (имитация действий);
Каждая инструкция, составленная для исполнителя В и приводящая при ее исполнении к определенному результату (т.е. к определенному состоянию среды исполнителя и него самого), может быть преобразована имитацией допустимых действий в инструкцию для исполнителя А , исполнение которой приводит к соответствующему результату в среде исполнителя А .
Впрочем, предположение, что у исполнителей А и В разная среда, в которой они существуют, не принципиально с информационной точки зрения. Например, исполнитель А имеет дело с числами, а В преобразует графические изображения. Но вы уже знаете, что фактически в каждом из этих случаев речь идет о преобразовании подходящим образом закодированной информации. Более того, можно считать, что используется один и тот же двоичный код. В этом смысле можно считать, что среда исполнителя просто одинакова - информация, представленная в форме закодированного сообщения.
Один из важнейших вопросов теоретической информатики звучит так: существует ли такой формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя? Такого исполнителя естественно назвать универсальным . Легко понять, что как физическое устройство универсальный исполнитель не существует - ведь информация может кодироваться как угодно длинными сообщениями, а любой физический носитель конечен. Если же вести речь об универсальном исполнителе как идеальном объекте, то оказывается, что ответ на заданный вопрос положителен. И получен он был почти одновременно и независимо двумя выдающимися учеными - А.Тьюрингом (в 1936 г.) и Э.Постом (в 1937 г.). Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное - имитировать вообще любого формального исполнителя.
Универсального исполнителя принято называть машиной. Также принято давать машинам имена их изобретателей. Так что универсального исполнителя, придуманного А.Тьюрингом, называют машиной Тьюринга; исполнителя, описанного Э.Постом, - машиной Поста. Позже появились и другие универсальные исполнители, например, машина Минского.
Итак, можно считать, что у нас имеется сообщение, записанное в некотором алфавите, и его требуется преобразовать в другое сообщение. Конечно, написать инструкцию формальному исполнителю для обработки конкретной пары сообщений - дело нехитрое. Но вы уже знаете, что реальный интерес представляют инструкции (т.е. алгоритмы), позволяющие решать целый класс однотипных задач, - так называемое “свойство массовости алгоритма”. Например, такая задача: к любому сообщению приписать справа еще один заранее заданный символ. Если, скажем, последовательность одинаковых символов выступает кодом натурального числа - количество символов в последовательности и есть кодируемое натуральное число, - то фактически речь идет о создании алгоритма увеличения числа на 1.
Естественно считать, что сообщение записано на ленту. Более того, удобно представлять себе эту ленту разделенной на одинаковые клетки, и в каждой клетке записан ровно один символ сообщения. Поскольку сообщения могут быть как угодно длинными, то ленту договоримся представлять себе бесконечной. Пустые клетки будем считать заполненными символом “пробел”. Тем самым, мы объявили, что любой алфавит, который будет использоваться нами для записи сообщений на этой ленте, обязательно содержит “пробел”. Договоримся обозначать его а 0 . Остальные символы алфавита, используемого для записи сообщений на ленту, будем обозначать а 1 , а 2 , ..., а n . Если, к примеру, нам требуется записать задачу вычисления суммы двух чисел, то алфавит можно взять таким: а 0 ; 1; 2; 3; 4; 5; 6; 7; 8; 9; 0; ,; +; =. Для конкретной пары данных (т.е. двух чисел) запись на ленте может выглядеть, например, так, как показано на рис. 5.
Рис. 5
Мы, конечно, не будем на ленте в пустых клетках писать символ а 0, подразумевая его там. Кроме того, договоримся, что первый символ сообщения, отличный от пробела, всегда стоит в одной и той же клетке - на рис. 4 она отмечена Ї. Эту клетку будем называть начальной.
Сообщение, записанное на ленте, обрабатывается неким устройством, и результат снова записывается на ленту. Поскольку исполнитель формальный, он не вникает в смысл сообщения, а по составленной для него инструкции заменяет одни символы на другие. Нас не интересует, как физически осуществляется такая замена, поэтому можно представить, что вдоль ленты движется некий автомат, который считывает символ из клетки на ленте, обрабатывает полученную информацию, печатает в клетке другой символ (если это предписано инструкцией) и сдвигается к соседней клетке - вправо или влево.
Вы уже знаете, что каждый автомат описывается набором состояний. Принято обозначать состояния указанного считывающе-печатающего автомата буквами q 0 , q 1 , q 2 , ..., q m . При этом договоримся, что при включении автомата, т.е. в начале работы, он всегда находится в одном и том же состоянии, которое мы будем обозначать q 0 , и располагается напротив начальной клетки.
Таким образом, машина Тьюринга формально описывается набором двух алфавитов: А = {а 1 , а 2 , ..., а } и Q = {q 0 , q 1 , q 2 , ..., q m }. Алфавит А называется внешним и служит для записи исходных сообщений, алфавит Q называется внутренним и описывает набор состояний считывающе-печатающего устройства. Изображать машину Тьюринга будем так, как показано на рис . 6.
Рис. 6
На рис. 6 показан момент работы машины Тьюринга, когда считывающе-печатающее устройство обозревает третью клетку от начальной (в ней к этому моменту оказался символ а s 3) и находится в состоянии q k .
Итак, допустимые действия машины Тьюринга таковы:
Записать какой-либо символ внешнего алфавита в секцию ленты (символ, бывший там до того, затирается);
Сместиться в соседнюю секцию;
Сменить состояние на одно из обозначенных символом внутреннего алфавита;
Прекратить работу (остановиться).
Конечно, в этом перечислении в каждой строке указано не одно действие, а группа действий одного вида - действий “записать символ внешнего алфавита” столько, сколько этих символов, сместиться в соседнюю секцию можно вправо, а можно влево, действий по изменению состояния столько, сколько этих состояний (т.е. сколько символов внутреннего алфавита).
Теперь надо сказать, как записываются команды на выполнение указанных действий. Каждая команда машины содержит не более одного действия из каждой группы действий и имеет вид
Фактически команды выглядят так:
a i q j - в обозреваемую секцию записать a i , сместиться вправо (к следующей секции) и перейти в состояние q j ;
a i q j - в обозреваемую секцию записать a i , сместиться влево и перейти в состояние q j ;
a i Sq j - в обозреваемую секцию записать ai , остановиться и перейти в состояние q j .
Для осуществления действий машина Тьюринга имеет операционно-логический блок. У этого блока имеется два входа: через один из них поступает информация о том, какой символ стоит в обозреваемой ячейке, через другой - информация о том, в каком состоянии находится машина на данном шаге своей работы. Эта информация однозначно определяет, какую именно команду следует выполнить машине. Поскольку команда может содержать указание на выполнение трех действий - записи символа на ленту, смещения и смены состояния - операционно-логический блок имеет три выхода: запись символа A , смещение M и смена состояния Q (см. рис. 7).
Рис. 7. Операционно-логический блок машины Тьюринга
Поскольку у этого блока всего лишь два входа, его реакцию на символы, подаваемые на них, удобно представлять в виде прямоугольной таблицы, в которой строки и столбцы помечены символами внешнего и внутреннего алфавитов соответственно (см. табл. 4). В клетки таблицы записываются команды. Если машина находится напротив клетки, где написано a i , а ее состояние при этом есть q j , то выполняется команда, стоящая на пересечении строки, отмеченной символом ai , и столбца, отмеченного символом q j .
Таблица 4
Эту таблицу называют функциональной схемой данной машины; она-то и играет роль инструкции (программы) для машины Тьюринга. Из нее, в частности, видно, каковы внешний и внутренний алфавиты машины.
Пусть, к примеру, на ленте записана последовательность из некоторого количества одного и того же символа “*”. Тогда функциональная схема, приведенная в табл. 5, заставляет машину Тьюринга увеличить на одну количество звездочек в этой последовательности.
Таблица 5
Доказать, что машина Тьюринга является универсальным исполнителем, нельзя. Так же, например, как нельзя доказать закон сохранения энергии в физике. Но практика составления алгоритмов показывает, что любую задачу, которую сегодня умеет решать человек, можно запрограммировать на машине Тьюринга. Этот экспериментальный факт, называемый тезисом Тьюринга, формулируют так: для задачи существует алгоритм решения тогда и только тогда, когда имеется подходящая машина Тьюринга, посредством которой можно решить эту задачу.
Вопросы и задачи
1. Какого формального исполнителя называют универсальным?
2. Что такое машина Тьюринга?
3. Чем одна машина Тьюринга отличается от другой?
4. Что называют функциональной схемой машины Тьюринга?
5. Верно ли, что машина Тьюринга с написанной для нее функциональной схемой является конечным автоматом?
6. Изобразите в виде последовательности рисунков, как изменяется информация на ленте при работе машины Тьюринга, описанной функциональной схемой в табл. 5.
7. Следуя функциональной схеме, описанной табл. 5, машина Тьюринга приписывает к заданной последовательности звездочек еще одну звездочку слева. Составьте функциональную схему, согласно которой звездочка будет приписываться справа от заданной последовательности.
8. Работа машины Тьюринга описана следующей функциональной схемой:
Определите, какое сообщение будет на ленте после окончания работы машины, и укажите, напротив какой ячейки в этот момент будет находиться ее пишущий блок.
Рис. 8
Рис. 9
9. На ленте машины Тьюринга записана строка, состоящая из нескольких подряд идущих символов “*”, за ними следует несколько символов “#”, а в конце строки стоит символ “е” (один из возможных вариантов такой строки приведен на рис. 5).
Рис. 10
Для каждой из приведенных ниже функциональных схем определите, для решения какой задачи она предназначена. (Совет: чтобы получить убедительный ответ, примените функциональную схему к разным вариантам заполнения информационной ленты последовательностями символов внешнего алфавита.)
10. Пусть внешний алфавит состоит из символа “a 0 ” и цифр 0, 1, 2, ..., 9. На ленту записывается натуральное число. Придумайте машину Тьюринга и составьте для нее функциональную схему, согласно которой данное число будет увеличено на 1.
11. Пусть внешний алфавит состоит из символа “a 0 ” и цифр 0, 1, 2, ..., 9. На ленту записано натуральное число. Составьте функциональную схему для машины Тьюринга, с помощью которой на ленте будет записана сумма цифр этого числа. Ответ требуется записать правее исходного числа, отделив от него пробелом.
Рис . 11
P.S. Ощутить себя в роли машины Тьюринга небесполезно, но утомительно. Мы рекомендуем задания 8 и 9 проделать вручную. Что касается заданий 10 и 11, то ручное тестирование составленных вами функциональных схем может оказаться неэффективным. В связи с этим мы предлагаем воспользоваться компьютерной реализацией машины Тьюринга, созданной Р.Зартдиновым. Ее можно получить на сайте газеты “Информатика” (inf.1september.ru ). Вот как, к примеру, выглядит на этой машине функциональная схема из задания 8 в) - отличия состоят в том, что вместо буквы S изображен дорожный знак, а вместо символа “a 0 ” пишется “_” (при занесении команды в клетку таблицы нажимать, однако, надо клавишу “пробел”, а не “_”). Программа снабжена подробной справкой о том, как с ней работать. Интерфейс этой программы очень прост. Кроме того, описание данной реализации машины Тьюринга вы можете найти в газете “Информатика” № 8, 2006. Там же вы найдете разбор еще нескольких задач на программирование машины Тьюринга; надо только иметь в виду, что в них используется несколько иная (что совершенно непринципиально) система команд.
* Напомним, что граф - это совокупность точек, называемых вершинами , и линий, соединяющих некоторые из вершин. Если на линиях, соединяющих вершины, указано направление, то граф называется ориентированным (сокращенно орграфом ), а линии называются его дугами . В обычном графе, т.е. неориентированном, линии, соединяющие вершины, называются ребрами . Подробнее о графах речь пойдет в лекции 4.
| Планирование уроков и материалы к урокам | 6 классы | Планирование уроков на учебный год (ФГОС) | Исполнители вокруг нас
Урок 24
Исполнители вокруг нас
Работа в среде исполнителя Кузнечик
Формальные исполнители
Формальные исполнители
Выделяют два типа исполнителей: формальных и неформальных. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.
Например, при многократном прослушивании диска с любимой музыкой вы можете быть уверены, что она воспроизводится проигрывателем (формальным исполнителем) одинаково. Но вряд ли кому-нибудь из певцов (неформальному исполнителю) удастся несколько раз совершенно одинаково исполнить песню из своего репертуара.
Как правило, человек выступает в роли неформального исполнителя. Формальными исполнителями являются преимущественно технические устройства. Человек в роли неформального исполнителя сам отвечает за свои действия. За действия формального исполнителя отвечает управляющий им объект.
Рассмотрим более подробно множество формальных исполнителей. Формальные исполнители необычайно разнообразны, но для каждого из них можно указать круг решаемых задач, среду, систему команд, систему отказов и режимы работы.
1. Круг решаемых задач
. Каждый исполнитель создается для решения определенного класса задач.
2. Среда исполнителя
. Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя.
3. Система команд исполнителя
. Предписание о выполнении отдельного законченного действия исполнителя называется командой. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует СКИ - систему команд исполнителя.
4. Система отказов исполнителя
. Отказ «не понимаю» возникает тогда, когда исполнителю подается команда, не входящая в его СКИ. Отказ «не могу» возникает тогда, когда команда из СКИ не может быть им выполнена в конкретных условиях среды.
5. Режимы работы исполнителя
. Для большинства исполнителей предусмотрены режимы непосредственного и программного управления. В первом случае исполнитель ожидает команд от управляющего объекта и немедленно выполняет каждую поступившую команду. Во втором случае исполнителю сначала задаётся полная последовательность команд (программа), а затем он выполняет все эти команды в автоматическом режиме. Ряд исполнителей работает только в одном из названных режимов.
Исполнитель – человек, группа людей, животное или техническое устройство, способные выполнять определенный набор команд. Примеры: Объект - исполнитель!! Кнопка вкл/выкл электропитания на корпусе компьютера Переход в начало Пауза СтопПереход в конец Воспроизведение Система команд исполнителя – СD-плеера
Более сложный исполнитель. Работает по программам, созданным человеком. Программы выбирает человек. Машина работает автоматически. Более сложный исполнитель. Работает по программам, созданным человеком. Программы выбирает человек. Машина работает автоматически. Исполнитель - стиральная машина
Неформальные и формальные исполнители В роли неформального исполнителя чаще всего выступает человек В роли формального исполнителя чаще всего выступает техническое устройство Неформальный исполнитель сам отвечает за свои действия За действия формального исполнителя отвечает управляющий им объект
Формальный исполнитель Формальный исполнитель всегда одинаково выполняет одну и ту же команду. Автоматический фасовочно- упаковочный аппарат Для каждого формального исполнителя можно указать: круг решаемых задач; среду; систему команд; систему отказов; режимы работы.
Система отказов исполнителя Отказ «Не понимаю» возникает, если подается команда, не входящая в СКИ. Отказ «Не могу» возникает, если команда из СКИ не может быть выполнена в конкретных условиях среды. ? Стиральная машина не может выполнить команду «полоскание», если к машине не подведена вода. ?
Автоматизация - замена части труда человека работой машины: процесс решения задачи представляется в виде последовательности простейших операций; создаётся машина, способная выполнять эти операции в заданной последовательности; выполнение алгоритма поручается автоматическому устройству; человек освобождается от рутинной деятельности. Автоматизация
Самое главное Исполнитель – это человек, группа людей, животное или техническое устройство, способные выполнять заданные команды. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Для каждого формального исполнителя можно указать: –круг решаемых задач; –среду; –систему команд; –систему отказов; –режимы работы.
| § 2.1. Алгоритмы и исполнители
Урок 14
§ 2.1. Алгоритмы и исполнители
Ключевые слова:
Алгоритм
свойства алгоритма (дискретность; понятность; определённость; результативность; массовость)
исполнитель
характеристики исполнителя (круг решаемых задач; среда; режим работы; система команд)
формальное исполнение алгоритма
2.1.1. Понятие алгоритма
Каждый человек в повседневной жизни, в учёбе или на работе решает огромное количество задач самой разной сложности . Сложные задачи требуют длительных размышлений для нахождения решения; простые и привычные задачи человек решает не задумываясь, автоматически. В большинстве случаев решение каждой задачи можно разбить на простые этапы (шаги). Для многих таких задач (установка программного обеспечения, сборка шкафа, создание сайта, эксплуатация технического устройства, покупка авиабилета через Интернет и т. д.) уже разработаны и предлагаются пошаговые инструкции, при последовательном выполнении которых можно прийти к желаемому результату.
Пример 1. Задача «Найти среднее арифметическое двух чисел» решается в три шага:
1) задумать два числа;
2) сложить два задуманных числа;
3) полученную сумму разделить на 2.
Пример 2. Задача «Внести деньги на счёт телефона» подразделяется на следующие шаги:
1) подойти к терминалу по оплате платежей;
2) выбрать оператора связи;
3) ввести номер телефона;
4) проверить правильность введённого номера;
5) вставить денежную купюру в купюроприёмник;
6) дождаться сообщения о зачислении денег на счёт;
7) получить чек.
Пример 3.
Этапы решения задачи «Нарисовать весёлого ёжика» представлены графически:
Нахождение среднего арифметического, внесение денег на телефонный счёт и рисование ежа - на первый взгляд совершенно разные процессы. Но у них есть общая черта: каждый из этих процессов описывается последовательностями кратких указаний, точное следование которым позволяет получить требуемый результат. Последовательности указаний, приведённые в примерах 1-3, являются алгоритмами решения соответствующих задач. Исполнитель этих алгоритмов - человек.
Алгоритм может представлять собой описание некоторой последовательности вычислений (пример 1) или шагов нематематического характера (примеры 2-3). Но в любом случае перед его разработкой должны быть чётко определены начальные условия (исходные данные) и то, что предстоит получить (результат). Можно сказать, что алгоритм - это описание последовательности шагов в решении задачи, приводящих от исходных данных к требуемому результату.
В общем виде схему работы алгоритма можно представить следующим образом (рис. 2.1).
Рис. 2.1. Общая схема работы алгоритма
Алгоритмами являются изучаемые в школе правила сложения, вычитания, умножения и деления чисел, многие грамматические правила, правила геометрических построений и т. д.
Анимации «Работа с алгоритмом» (193576), «Наибольший общий делитель» (170363), «Наименьшее общее кратное» (170390) помогут вам вспомнить некоторые алгоритмы, изученные на уроках русского языка и математики (http://sc.edu.ru/).
Пример 4. Некоторый алгоритм приводит к тому, что из одной цепочки символов получается новая цепочка следующим образом:
1. Вычисляется длина (в символах) исходной цепочки символов.
2. Если длина исходной цепочки нечётна, то к исходной цепочке справа приписывается цифра 1, иначе цепочка не изменяется.
3. Символы попарно меняются местами (первый - со вторым, третий - с четвёртым, пятый - с шестым и т. д).
4. Справа к полученной цепочке приписывается цифра 2.
Получившаяся таким образом цепочка является результатом работы алгоритма.
Так, если исходной была цепочка А#В, то результатом работы алгоритма будет цепочка #А1В2, а если исходной цепочкой была АБВ@, то результатом работы алгоритма будет цепочка БА@В2.
2.1.2. Исполнитель алгоритма
Каждый алгоритм предназначен для определённого исполнителя.
Исполнитель - это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
Различают формальных и неформальных исполнителей . Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.
Рассмотрим более подробно множество формальных исполнителей. Формальные исполнители необычайно разнообразны, но для каждого из них можно указать следующие характеристики: круг решаемых задач (назначение), среду, систему команд и режим работы.
Круг решаемых задач . Каждый исполнитель создаётся для решения некоторого круга задач - построения цепочек символов, выполнения вычислений, построения рисунков на плоскости и т. д.
Среда исполнителя . Область, обстановку, условия, в которых действует исполнитель, принято называть средой данного исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Система команд исполнителя . Предписание исполнителю о выполнении отдельного законченного действия называется командой. Совокупность всех команд, которые могут быть выполнены некоторым исполнителем, образует систему команд данного исполнителя (СКИ). Алгоритм составляется с учётом возможностей конкретного исполнителя, иначе говоря, в системе команд исполнителя, который будет его выполнять.
Режимы работы исполнителя . Для большинства исполнителей предусмотрены режимы непосредственного управления и программного управления. В первом случае исполнитель ожидает команд от человека и каждую поступившую команду немедленно выполняет. Во втором случае исполнителю сначала задаётся полная последовательность команд (программа), а затем он выполняет все эти команды в автоматическом режиме. Ряд исполнителей работает только в одном из названных режимов.
Рассмотрим примеры исполнителей.
Пример 5. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.
Система команд Черепашки состоит из следующих команд:
1. Вперёд n (где n - целое число) - вызывает передвижение Черепашки на п шагов в направлении движения - в том направлении, куда развёрнуты её голова и корпус;
2. Направо m (где m - целое число) - вызывает изменение направления движения Черепашки на т градусов по часовой стрелке.
Запись Повтори k [<Команда1> <Команда2> ... <Командаn>]
означает, что последовательность команд в скобках повторится k раз.
Подумайте, какая фигура появится на экране после выполнения Черепашкой следующего алгоритма.
Повтори 12 [Направо 45 Вперёд 20 Направо 45]
Пример 6. Система команд исполнителя Вычислитель состоит из двух команд, которым присвоены номера:
1 - вычти 1
2 - умножь на 3
Первая из них уменьшает число на 1, вторая увеличивает число в 3 раза. При записи алгоритмов для краткости указываются лишь номера команд. Например, алгоритм 21212 означает следующую последовательность команд:
Умножь на 3
вычти 1
умножь на 3
вычти 1
умножь на 3
С помощью этого алгоритма число 1 будет преобразовано в 15:
((1 3 - 1) 3 - 1) 3 = 15.
Пример 7.
Исполнитель Робот действует на клетчатом поле, между соседними клетками которого могут стоять стены. Робот передвигается по клеткам поля и может выполнять следующие команды,
которым присвоены номера:
1 - вверх
2 - вниз
3 - вправо
4 - влево
При выполнении каждой такой команды Робот перемещается в соседнюю клетку в указанном направлении. Если же в этом направлении между клетками стоит стена, то Робот разрушается.
Что произойдёт с Роботом, если он выполнит последовательность команд 32323 (здесь цифры обозначают номера команд), начав движение из клетки А? Какую последовательность команд следует выполнить Роботу, чтобы переместиться из клетки А в клетку В, не разрушившись от встречи со стенами?
При разработке алгоритма:
1) выделяются фигурирующие в задаче объекты, устанавливаются свойства объектов, отношения между объектами и возможные действия с объектами;
2) определяются исходные данные и требуемый результат;
3) определяется последовательность действий исполнителя, обеспечивающая переход от исходных данных к результату;
4) последовательность действий записывается с помощью команд, входящих в систему команд исполнителя.
Можно сказать, что алгоритм - модель деятельности исполнителя алгоритмов.
2.1.3. Свойства алгоритма
Не любая инструкция, последовательность предписаний или план действий может считаться алгоритмом. Каждый алгоритм обязательно обладает следующими свойствами: дискретность, понятность, определённость, результативность и массовость.
Свойство дискретности означает, что путь решения задачи разделён на отдельные шаги (действия). Каждому действию соответствует предписание (команда). Только выполнив одну команду, исполнитель может приступить к выполнению следующей команды.
Свойство понятности означает, что алгоритм состоит только из команд, входящих в систему команд исполнителя, т. е. из таких команд, которые исполнитель может воспринять и по которым может выполнить требуемые действия.
Свойство определённости означает, что в алгоритме нет команд, смысл которых может быть истолкован исполнителем неоднозначно; недопустимы ситуации, когда после выполнения очередной команды исполнителю неясно, какую команду выполнять следующей. Благодаря этому результат алгоритма однозначно определяется набором исходных данных: если алгоритм несколько раз применяется к одному и тому же набору исходных данных, то на выходе всегда получается один и тот же результат.
Свойство результативности означает, что алгоритм должен обеспечивать получение результата после конечного, возможно, очень большого, числа шагов. При этом результатом считается не только обусловленный постановкой задачи ответ, но и вывод о невозможности продолжения по какой-либо причине решения данной задачи.
Свойство массовости означает, что алгоритм должен обеспечивать возможность его применения для решения любой задачи из некоторого класса задач. Например, алгоритм нахождения корней квадратного уравнения должен быть применим к любому квадратному уравнению, алгоритм перехода улицы должен быть применим в любом месте улицы, алгоритм приготовления лекарства должен быть применим для приготовления любого его количества и т. д.
Пример 8. Рассмотрим один из методов нахождения всех простых чисел, не превышающих некоторое натуральное число n. Этот метод называется «решето Эратосфена» по имени предложившего его древнегреческого учёного Эратосфена (III в. до н. э.).
Для нахождения всех простых чисел, не больших заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
1) выписать подряд все натуральные числа от 2 до n (2, 3, 4, ..., n);
2) заключить в рамку 2 - первое простое число;
3) вычеркнуть из списка все числа, делящиеся на последнее найденное простое число;
4) найти первое неотмеченное число (отмеченные числа - зачёркнутые числа или числа, заключённые в рамку) и заключить его в рамку - это будет очередное простое число;
5) повторять шаги 3 и 4 до тех пор, пока не останется неотмеченных чисел.
Более наглядное представление о методе нахождения простых чисел вы сможете получить с помощью размещённой в Единой коллекции цифровых образовательных ресурсов анимации «Решето Эратосфена» (180279).
Рассмотренная последовательность действий является алгоритмом, так как она удовлетворяет свойствам:
дискретности
- процесс нахождения простых чисел разбит на шаги;
понятности
- каждая команда понятна ученику 8 класса, выполняющему этот алгоритм;
определённости
- каждая команда трактуется и выполняется исполнителем однозначно; имеются указания об очерёдности выполнения команд;
результативности
- через некоторое число шагов достигается результат;
массовости
- последовательность действий применима для любого натурального n.
Рассмотренные свойства алгоритма позволяют дать более точное определение алгоритма.
Алгоритм - это предназначенное для конкретного исполнителя описание последовательности действий, приводящих от исходных данных к требуемому результату, которое обладает свойствами дискретности, понятности, определённости, результативности и массовости.
2.1.4. Возможность автоматизации деятельности человека
Разработка алгоритма - как правило, трудоёмкая задача, требующая от человека глубоких знаний, изобретательности и больших временных затрат.
Решение задачи по готовому алгоритму требует от исполнителя только строгого следования заданным предписаниям.
Пример 9. Из кучки, содержащей любое, большее трёх, количество каких-либо предметов, двое играющих по очереди берут по одному или по два предмета. Выигрывает тот, кто своим очередным ходом сможет забрать все оставшиеся предметы.
Рассмотрим алгоритм, следуя которому первый игрок наверняка обеспечит себе выигрыш.
1. Если число предметов в кучке кратно 3, то уступить ход противнику, иначе начать игру, взяв 1 или 2 предмета так, чтобы осталось количество предметов, кратное 3.
2. Своим очередным ходом каждый раз дополнять число предметов, взятых соперником, до 3 (число оставшихся предметов должно быть кратно 3).
Исполнитель может не вникать в смысл того, что он делает, и не рассуждать, почему он поступает так, а не иначе, т. е. он может действовать формально. Способность исполнителя действовать формально обеспечивает возможность автоматизации деятельности человека. Для этого:
1) процесс решения задачи представляется в виде последовательности простейших операций;
2) создаётся машина (автоматическое устройство), способная выполнять эти операции в последовательности, заданной в алгоритме;
3) человек освобождается от рутинной деятельности, выполнение алгоритма поручается автоматическому устройству.
САМОЕ ГЛАВНОЕ
Исполнитель - некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Для каждого формального исполнителя можно указать: круг решаемых задач, среду, систему команд и режим работы .
Алгоритм - предназначенное для конкретного исполнителя описание последовательности действий, приводящих от исходных данных к требуемому результату, которое обладает свойствами дискретности, понятности, определённости, результативности и массовости.
Способность исполнителя действовать формально
обеспечивает возможность автоматизации деятельности человека.
Вопросы и задания
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Дополняет ли презентация информацию, содержащуюся в тексте параграфа? Какими слайдами вы могли бы дополнить презентацию?
2. Что называют алгоритмом?
3. Подберите синонимы к слову «предписание».
4. Приведите примеры алгоритмов, изучаемых вами в школе.
5. Кто может быть исполнителем алгоритма?
6. Приведите пример формального исполнителя. Приведите пример, когда человек выступает в роли формального исполнителя.
7. От чего зависит круг решаемых задач исполнителя «компьютер»?
8. Рассмотрите в качестве исполнителя текстовый процессор, имеющийся на вашем компьютере. Охарактеризуйте круг решаемых этим исполнителем задач и его среду.
9. Что такое команда, система команд исполнителя?
10. Какие команды должны быть у робота, выполняющего функции:
а) кассира в магазине;
б) дворника;
в) охранника?
11. Перечислите основные свойства алгоритма.
12. К чему может привести отсутствие какого-либо свойства у алгоритма? Приведите примеры.
13. В чём важность возможности формального исполнения алгоритма?
14. Последовательность чисел строится по следующему алгоритму: первые два числа последовательности принимаются равными 1; каждое следующее число последовательности принимается равным сумме двух предыдущих чисел. Запишите 10 первых членов этой последовательности. Выясните, как называется эта последовательность.
15. Некоторый алгоритм получает из одной цепочки символов новую цепочку следующим образом. Сначала записывается исходная цепочка символов, после нее записывается исходная цепочка символов в обратном порядке, затем записывается буква, следующая в русском алфавите за той буквой, которая в исходной цепочке стояла на последнем месте. Если в исходной цепочке на последнем месте стоит буква «Я», то в качестве следующей буквы записывается буква «А». Получившаяся цепочка является результатом работы алгоритма. Например, если исходная цепочка символов была «ДОМ», то результатом работы алгоритма будет цепочка «ДОММОДН». Дана цепочка символов «КОМ». Сколько букв «О» будет в цепочке символов, которая получится, если применить алгоритм к данной цепочке, а затем ещё раз применить алгоритм к результату его работы?
16. Найдите в сети Интернет анимацию шагов алгоритма Эратосфена. С помощью алгоритма Эратосфена найдите все простые числа, не превышающие 50.
17. Что будет результатом исполнения Черепашкой (см. пример 5) алгоритма?
18. Запишите алгоритм для исполнителя Вычислитель (см. пример 6), содержащий не более 5 команд:
а) получения из числа 3 числа 16;
б) получения из числа 1 числа 25.
19. Система команд исполнителя Конструктор состоит из двух команд, которым присвоены номера:
1 - приписать 2
2 - разделить на 2
По первой из них к числу приписывается справа 2, по второй число делится на 2. Как будет преобразовано число 8, если исполнитель выполнит алгоритм 22212? Составьте алгоритм в системе команд этого исполнителя, по которому число 1 будет преобразовано в число 16 (в алгоритме должно быть не более 5 команд).
20. В какой клетке должен находиться исполнитель Робот (пример 7), чтобы после выполнения алгоритма 3241 в неё же и вернуться?
Свободное программное обеспечение:
система КуМир - Комплект учебных миров (скачать архив программы с сайта) или посетить страницу КуМир ((http://www.niisi.ru/kumir/)
