Министерство образования Московской области
Государственное бюджетное профессиональное
образовательное учреждение Московской области
Воскресенский колледж
Методические указания
к выполнению лабораторных работ по дисциплине
теория алгоритмов
для студентов специальностей
230115 «Программирование в компьютерных системах»
Разработала :
Вострякова А. В .– преподаватель ГБПОУ МО «Воскресенский колледж»
2015 г.
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Практикум содержит набор лабораторных работ по предмету «теория алгоритмов» во время проведения которых изучаются: основные принципы и приемы построения алгоритмических схем для различного рода задач, а также механизм реализации этих алгоритмов на языке высокого уровня.
Данные методические указания рассчитанный на студентов специальност:
230115 «Программирование в компьютерных системах»;
и содержат сведения необходимые для выполнения заданий лабораторного практикума. Для освоения изучаемого материала студентами выполняются индивидуальные задания.
Перечень лабораторных работ:
ЛАБОРАТОРНАЯ РАБОТА № 1«Разработка программ для Машины Поста»
ЛАБОРАТОРНАЯ РАБОТА № 2 «Разработка программ для Машины Тьюринга» ЛАБОРАТОРНАЯ РАБОТА № 3 «Разработка программ для алгорифмов Маркова»
ЛАБОРАТОРНАЯ РАБОТА №4 «Разработка программ с использованием рекурсивных функций»
ЛАБОРАТОРНАЯ РАБОТА №5 «Разработка программ с использованием алгоритмов перебора»
ЛАБОРАТОРНАЯ РАБОТА №6 «Разработка программ с использованием алгоритмов сортировки»
ЛАБОРАТОРНАЯ РАБОТА №7 «Составление алгоритма решения для системы линейных уравнений на алгоритмическом языке»
ЛАБОРАТОРНАЯ РАБОТА №8 «Составление алгоритма поиска кротчайшего пути»
ЛАБОРАТОРНАЯ РАБОТА № 1
Разработка программ для Машины Поста
Цель работы: развить аналитическое и логическое мышление учащихся, математическую интуицию, по средствам разработки алгоритмов задач для логических машин.
Задача работы: изучить программу имитатор машины Поста. Выработать навык составления алгоритмов для машины Поста.
Теоретическая часть
Формат команды машины Поста имеет вид: n K m
где:
n - номер текущей команды;
K - команда из системы команд машины Поста (см. табл. 1);
m - ссылка - номер команды, которая будет выполняться следующей.
Таблица 1. Система команд машины Поста
|
-->
|
Сдвиг каретки вправо, содержимое ленты не меняется.
|
|
Сдвиг каретки влево, содержимое ленты не меняется.
|
V
|
В обозреваемую секцию ставится метка "V". Выполнение этой команды возможно только в том случае, если обозреваемая секция пустая, в противном случае команда считается невыполнимой.
|
|
Каретка стирает метку в обозреваемой секции. Выполнение этой команды возможно только в том случае, если обозреваемая секция содержит метку, в противном случае команда считается невыполнимой.
|
? b1 , b2
|
Команда передачи. Проверяется содержимое текущей секции, если метки нет, то происходит передача управления команде с номером b1, иначе, если метка есть - команде с номером b2. Содержимое ленты не меняется.
|
!
|
Команда останова машины. Содержимое ленты не меняется. У команды остановки ссылка не обязательна.
|
Для того чтобы заполнить ленту достаточно подвести к ячейке указатель мыши и выполнить двойной щелчок левой кнопкой, или воспользоваться кнопкой .
- запоминает начальное состояние ленты.
- восстанавливает начальное состояние ленты.
- запускает алгоритм программы на выполнение.
- пошаговое выполнение программы.
- остановка выполнения программы.
Текст задания:
Отчет выполняется в электронном виде. Если строк таблицы для описания алгоритма программы не хватает их не обходимо добавить. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.
Вставить скриншот начального состояния ленты.
Отчет о выполнении задания
Вставить скриншот состояния ленты после выполнения алгоритма.
Заполнить таблицу вписав алгоритм программы комментируя каждую строку.
Номер команды
|
команда
|
отсылка
|
комментарий
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Контрольные вопросы:
-
Устройство машины Поста
-
Система команд машины Поста.
-
Алфавит машины Поста.
-
Варианты окончания выполнения программы на машине Поста.
Задания для выполнения лабораторных работ
Задача 1
Составить программу перевода информационной ленты из начального состояния в конечное:
1 вариант
2 вариант
3 вариант
4 вариант
5 вариант
6 вариант
7 вариант
8 вариант
9 вариант
10 вариант
11 вариант
12 вариант
Задача 2
Выполнить арифметические действия :
-
3+4, 4-2;
-
5+3, 3*2;
-
5-2, 2*2;
-
5-4, 6/2;
-
3+2, 4/2;
-
2+4, 2*4;
-
Задача 1
Составить программу для прохождения каретки от левой метки к правой. Количество пустых клеток между метками неизвестно.
Задача 2
Составить программу для заполнения всех клеток от левой метки до правой. Количество пустых клеток между метками неизвестно.
К.с.
|
…
|
۷
|
۷
|
۷
|
۷
|
۷
|
۷
|
۷
|
۷
|
۷
|
…
|
Задача 3
Составить программу перевода информационной ленты из начального состояния в конечное. Количество меток произвольное (не обязательно равно 4).
Задача 4
Составить программу перевода информационной ленты из начального состояния в конечное. Количество меток произвольное (не обязательно равно 4).
-
|