Практическая работа №1 «Исполнители»

Begin

Task('c1');

ToPoint(1,3);

PenDown;

ToPoint(1,2);

End.

Результат работы окрашен в синий цвет.

 

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

1. Загрузите и выполните задания a2, a3, a4. При выполнении заданий воспользуйтесь справкой Pascal ABC раздел исполнитель «Робот».

 

2. Загрузите и выполните задания c2, c3, c4. При выполнении заданий воспользуйтесь справкой Pascal ABC раздел исполнитель «Чертежник».

 

Практическая работа №2 «Разработка программ машин Тьюринга для вычисления функций»

Цель: Формирование умений и навыков по разработке программ машин Тьюринга.

 

Задачи:

1. изучить устройство машины Тьюринга

2. научиться читать и выполнять программы, написанные для машины Тьюринга

3. научиться разрабатывать программы для машины Тьюринга.

 

Оснащение урока:

· Техническое: ПК, сканер, принтер, интерактивная доска

· Методическое: инструкционная карта, задание для самостоятельного выполнения

· Программное: Windows XP, тренажер «Машина Тьюринга».

Теоретические сведения: Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга.

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

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

1. Внешний алфавит. Конечное множество (обозначают буквой А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}. Непрерывную цепочку символов на ленте называют словом.

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

3. Внутренний алфавит. Конечное множество состояний каретки (автомата). Обозначается буквой Q={q1,q2...}. Одно из состояний - q1- должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние остановка.

Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

 

Автомат машины Тьюринга в процессе своей работы управляется программой, во время каждого шага которой выполняются последовательно следующие действия:

· Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

· Передвигаться на одну ячейку влево или вправо.

· Менять свое внутреннее состояние.

Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра: символ ai из выбранного алфавита A, направление перемещения каретки ("←” — влево, "→” — вправо, "точка” — нет перемещения) и новое состояние автомата qk. Например, команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.

 

Ход работы

1. В рабочей тетрадке запишите тему, цель и задачи работы.

2. Приступите к выполнению упражнений.

3. Выполните задание.

4. Сделайте вывод по работе.

 

Упражнение 1 На ленте записано число в двоичной системе счисления. Каретка находится где-то над числом. Требуется увеличить число на единицу.

 

Чтобы решить задачу, нам нужно:

· определить алфавит машины Тьюринга А,

· определить набор состояний Q,

· составить программу (т.е. для каждой пары (аi,qi) определить команду автомата.)

·

Алфавит машины Тьюринга, работающей с двоичными цифрами будет включать цифры 0, 1 и пробел a0. Т.е. А={1,0,a0}.

Определим возможные состояния:

1. q1 - автомат ищет правый конец слова (числа) на ленте

2. q2 - автомат увеличивает число на 1, проходя его слева направо и останавливается, закончив работу.

 

Напишем программу:

1 часть. q1 - автомат ищет правый конец слова (числа на ленте)

1)если в рабочей ячейке записано 0 - переместиться вправо

2)если в рабочей ячейке записано 1 - переместиться вправо

3) если в рабочей ячейке пробел, переместить каретку влево и перейти в состояние q2

Составим таблицу переходов для q1 т.о.:

 

	q1
	0 → q1
	1 → q1
a0	a0 ← q2

 

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

1) если в рабочей ячейке записана цифра 0, записать в нее 1 и стоп

2) если в рабочей ячейке записана цифра 1, выполнить перенос в старший разряд - записать в ячейку 0 и переместиться влево.

3) если в рабочей ячейке пробел, записать в нее 1 и стоп.

Добавим в нашу таблицу состояние q2:

 

алф\состояния	q1	q2
	0 → q1	1. q0
	1 → q1	0 ←
a0	a0 ← q2	1. q0

 

Построенная таблица и есть программа для машины Тьюринга.

Упражнение 2. Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над первой буквой слова слева. Завершается программа тогда, когда головка оказывается над пустым символом после самой правой буквы слова.

Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая.

Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

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

1. Построить таблицу машины Тьюринга, которая заменяет все единицы на нули, а все нули на единицы. Пример. Исходное число 111001. Результат – 000110.

2. Построить таблицу машины Тьюринга, которая удаляет из числа все нули, например, число 1001110 преобразует к виду 1111. Эта задача уже сложнее и требует ввести в рассмотрение более двух состояний.

3. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если число единиц в записи числа нечетное, и в состоянии NO– в противном случае.

4. Построить машину, имеющую два конечных состояния, условно обозначаемых как YES и NO. Машина должна завершить работу в состоянии YES, если в записи числа имеется три подряд идущих единицы, и в состоянии NO– в противном случае.

5. Построить машину Тьюринга, которая получает обратный порядок записи числа, например, исходное число 111001, результат 100111.

6. Построить машину Тьюринга, которая меняет местами соседние два элемента попарно. Пример. Исходное число 011001 заменяется на 100110.

 

Приложение 1

Базовые элементы блок-схем

Наименование	Обозначение	Функция
Блок начало-конец (пуск-остановка)		Элемент отображает выход во внешнюю среду и вход из внешней среды (наиболее частое применение − начало и конец программы). Внутри фигуры записывается соответствующее действие.
Блок действия		Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания: a = 10*b + c.
Логический блок (блок условия)		Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).
Предопределённый процесс		Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании − вызов процедуры или функции.
Данные (ввод-вывод)		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Соединитель		Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения её в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при том уникальное) обозначение.
Комментарий		Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.

 

 

Список литературы

 

1. Семакин И.Г. основы алгоритмизации и программирования: учебник для студентов среднего профессионального образования. – М.Издательский центр «Академия», 2012 – 400с.

2. Колдаев В.Д. Основы алгоритмизации и программирования: Уч. пособие/-М.: ИД «ФОРУМ»:ИНФРА-М, 2012.-416с.

3. О. В. Горбатова. Информатика: Учебник для техникумов и колледжей ж.-д. транспорта. -М: ГОУ «Учебно-методический центр по образованию на железнодорожном транспорте», 2012. - 242 с.

4. Дополнительные источники:

5. Брукшир Дж. Информатика и вычислительная техника 7-е изд.- СПб.: Питер, 2004-620с.

6. http://it.kgsu.ru/TI_7/oglav.html

7. http://fvn2009.narod.ru

8. http://www.iiikt.narod.ru

9. http://book.kbsu.ru

Практическая работа №1 «Исполнители»

Цель: Формирование умений и навыков по программированию простейших исполнителей.

 

Задачи:

1. научиться использовать Pascal ABC исполнители «Робот», «Чертежник»

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

 

Оснащение урока:

· Техническое: ПК, сканер, принтер, интерактивная доска

· Методическое: инструкционная карта, задание для самостоятельного выполнения

· Программное: Windows XP, Pascal ABC & Programming Task book Mini Edition.

Теоретические сведения: Исполнителем будем называть устройство, способное выполнять определенный набор команд. Обычно с исполнителем связано некоторое поле, на котором он работает.

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

В Pascal ABC реализованы исполнители Робот и Чертежник. Особенность выполнения программы для исполнителей Робот и Чертежник состоит в следующем: команды программы записываются в память исполнителя, и только после завершения программы исполнитель начинает движение согласно заложенной в него программе.

 

Ход работы

1. Запустите среду Pascal ABC.

2. Изучите учебно-тренировочные упражнения. Учебно-тренировочные упражнения и выполненные задания сохраните в вашу рабочую папку на сетевом диске.

3. Приступите к выполнению задания для самостоятельной работы.

4. Сделайте вывод по практической работе и запишите его.

 

Упражнение 1 – «Исполнитель Робот»

Закрасить помеченные клетки.

 

Решение:

Шаг 1. Подключим к программе модуль Robot и вызовем в начале программы процедуру Task, передав ей в качестве параметра имя задания:

uses Robot;
begin
Task('a1');
end.

Запустим программу (F9), чтобы увидеть окно Робота с графическим изображением задания (рис. 1):

Рисунок 1 –окно программы «Исполнитель Робот»

Шаг 2. Наберем несколько команд Робота:

uses Robot;
begin
Task('a1');
Right; Right; Right; Right;
end.

Запустим программу, после чего нажмем Enter или кнопку «Пуск» чтобы Робот начал выполнять заложенную в него программу (рис. 2):

Рисунок 2 – окно выполнения программы

После окончания движения Робота осуществляется проверка, все ли помеченные клетки закрашены и находится ли Робот в конечной клетке. Поскольку это не выполняется, то задание не считается выполненным. Можно повторить путь Робота, нажав кнопку «Заново» и вновь кнопку «Пуск».

Шаг 3. Выполним неверную команду, в результате которой Робот врежется в стенку:

uses Robot;
begin
Task('a1');
Right; Right; Right; Right;
Up; Up; Left;
end.

После запуска программы и нажатия Enter получим следующее окно (рис. 3):

Рисунок 3 – окно выполнения программы

Заметим, что состояние Робота окрасилось в красный цвет, и последняя команда Left не выполнилась - после фатальной ошибки Робот прекратил выполнение задания.

Шаг 4. Исправьте ошибку самостоятельно и выполнините задание до конца (рис. 4):

Рисунок 4 – Окно выполнения программы (программа выполнена, верно)

Упражнение 2 – «Исполнитель Чертежник»

Исполнитель Чертежникпредназначен для построения рисунков и чертежей на плоскости с координатами. Чертежник имеет перо, которое он может поднимать, опускать и перемещать. При перемещении опущенного пера за ним остается след.

Исполнитель Робот и поле, на котором он работает, отображаются следующим образом:

Рисунок 5 – результат работы программы «Исполнитель Чертежник»

 

Здесь маленький квадрат изображает Чертежника, красным цветом изображены отрезки, которые надо нарисовать, а синим - уже нарисованные Чертежником отрезки. Когда перо Чертежника опущено, он изображается квадратом меньшего размера.

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

uses Drawman;

begin
Task('c1');
end.

В конце программы перо Чертежника должно быть поднято и находиться в начале координат.

Команды исполнителя Чертежник содержатся в модуле Drawman:

ToPoint(x,y)– перемещает перо Чертежника в точку (x,y);
OnVector(a,b)– перемещает перо Чертежника на вектор (a,b);
PenUp – поднимает перо Чертежника;
PenDown – опускает перо Чертежника.

Для решения задния добавим в код программы строки

uses Drawman;

Begin

Task('c1');

ToPoint(1,3);

PenDown;

ToPoint(1,2);

End.

Результат работы окрашен в синий цвет.

 

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

1. Загрузите и выполните задания a2, a3, a4. При выполнении заданий воспользуйтесь справкой Pascal ABC раздел исполнитель «Робот».

 

2. Загрузите и выполните задания c2, c3, c4. При выполнении заданий воспользуйтесь справкой Pascal ABC раздел исполнитель «Чертежник».