• Преподавателю
  • Информатика
  • Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Методические рекомендации по выполнению практикума по учебной дисциплине "Теория алгоритмов".Предназначены для студентов специальности 230115 Программирование в компьютерных системах при изучении вычислимости функций и машины Поста как универсального конечного автомата. При разработке практических заданий учитывались требования к результатам усвоения учебной дисциплины, сформулированные в ФГОС СПО III поколения.В результате освоения раздела обучающийся должен овладеть общими и профессиональными ...
Раздел Информатика
Класс -
Тип Другие методич. материалы
Автор
Дата
Формат doc
Изображения Есть
For-Teacher.ru - все для учителя
Поделитесь с коллегами:

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Министерство образования и науки Самарской области

Министерство имущественных отношений Самарской области

Государственное бюджетное образовательное учреждение

среднего профессионального образования

«Чапаевский губернский колледж»







МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ СТУДЕНТАМ ПО ВЫПОЛНЕНИЮ ПРАКТИКУМА ПО УЧЕБНОЙ ДИСЦИПЛИНЕ «Теория алгоритмов»

(Раздел 2. Конечные автоматы

Тема 2.2. Рекурсивные функции и понятие вычислимости)


специальность230115 Программирование в компьютерных системах













Чапаевск, 2014 год

Публикуется на основании решения

Методического совета

протокол №____

от _____________


Автор: Дикова В.Г., преподаватель общепрофессиональных и специальных дисциплин ГБОУ СПО «Чапаевский губернский колледж»

Редактор: Следкова М.П., заместитель директора по учебно-методической работе образовательной программы среднего профессионального образования ГБОУ СПО «Чапаевский губернский колледж»

Рецензент: Орлова Н.Н., старший преподаватель кафедры Высшей математики и информатики СФ МГПУ

Методические рекомендации предназначены для студентов специальности 230115 Программирование в КС при изучении вычислимости функций и машины Поста как универсального конечного автомата. Тематика практических заданий соответствует программе учебной дисциплины. Практикум предназначен для закрепления теоретического материала, формирования практических умений разработки алгоритмов по заданным параметрам.

Содержание

Стр.

Пояснительная записка

4

Теоретическая справка

5

Примеры решения задач

10

Задания для самостоятельной работы

22

Контрольные задания

24

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

25






Пояснительная записка

Методические рекомендации по выполнению практикума разработаны в помощь студентам специальности 230115 Программирование в КС для изучения раздела «Конечные автоматы» по дисциплине «Теория алгоритмов».

Тематика практических заданий соответствует программе учебной дисциплины. Практикум предназначен для закрепления теоретического материала, формирования практических умений разработки алгоритмов по заданным параметрам.

При разработке практических заданий учитывались требования к результатам освоения учебной дисциплины, сформулированные в ФГОС СПО III поколения.

В результате освоения раздела обучающийся должен овладеть общими и профессиональными компетенциями, а также

уметь:

  • строить принципиальные схемы конечных автоматов;

  • использовать систему команд машины Поста для записи алгоритма решения задачи;

  • предупреждать недопустимые действия, ведущие к аварийной остановке машины.

знать:

  • основные модели алгоритмов;

  • методы построения алгоритмов;

  • способы построения конечных автоматов;

  • устройство машины Поста;

  • систему команд машины Поста.

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

Практикум включает в себя теоретическую часть и набор задач с решениями.

Все задачи практикума сгруппированы по темам. Начинать знакомство с машиной Поста рекомендуется с первой темы "Применимость программ. Определение результата выполнения программ".

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

Теоретическая справка


Назначение машины Поста

Одним из центральных понятий информатики является понятие алгоритма. В 1936 году американский математик и логик Эмиль Леон Пост (1897-1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на "примитивность" машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый "тезис Поста": "Всякий алгоритм представим в форме машины Поста". Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) - программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие "всякий алгоритм", а с другой стороны - точное понятие "машина Поста". Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.

Машина Поста - это абстрактная (т.е. не существующая в арсенале действующей техники), но очень простая вычислительная машина. Она способна выполнять лишь самые элементарные действия, и потому ее описание и составление простейших программ может быть доступно ученикам начальной школы. Тем не менее, на машине Поста можно запрограммировать - в известном смысле - любые алгоритмы. Изучение машины Поста можно рассматривать как начальный этап обучения теории алгоритмов и программированию.


Состав машины Поста

Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой). Лента бесконечна и разделена на секции одинакового размера - ячейки.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

В каждый момент времени каретка указывает на одну из ячеек

В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Иными словами, состояние ленты - это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Заметим, что наличие метки в ячейке можно интерпретировать как "1", а отсутствие - "0". Такое двоичное представление информации подобно представлению, используемому практически во всех современных ЭВМ.

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

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

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Приведем список недопустимых действий, ведущих к аварийной остановке машины:

  • попытка записать 1 (метку) в заполненную ячейку;

  • попытка стереть метку в пустой ячейке;

  • бесконечное выполнение (вообще говоря, это трудно назвать аварийным остановом, но бессмысленное повторение одних и тех же действий - зацикливание - ничуть не лучше вышеперечисленного).

Машина Поста, несмотря на внешнюю простоту, может производить различные вычисления, для чего надо задать начальное состояние каретки и программу, которая эти вычисления сделает. Машиной эта математическая конструкция названа потому, что при ее построении используются некоторые понятия реальных машин (ячейка памяти, команда и др.). Условимся каждый шаг программы обозначать номером. Команды машины будем обозначать следующим образом:

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Будем говорить, что мы можем применить программу к текущему состоянию машины Поста, если выполнение программы не приведет к зацикливанию, т.е. рано или поздно мы выполним команду останов.

Пример программы, которая не применима ни к одному состоянию машины Поста:

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)


Рассмотрим задачу для машины Поста и ее решение.

Задача. На ленте проставлена метка в одной-единственной ячейке. Каретка стоит на некотором расстоянии левее этой ячейки. Необходимо подвести каретку к ячейке, стереть метку и остановить каретку слева от этой ячейки.

Решение. Сначала попробуем описать алгоритм обычным языком. Поскольку нам известно, что каретка стоит напротив пустой ячейки, но неизвестно, сколько шагов нужно совершить до пустой ячейки, мы можем сразу сделать шаг вправо; проверить, заполнена ли ячейка; если она пустая, то повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку. Как только мы ее найдем, мы выполним операцию стирания, после чего нужно будет лишь сместить каретку влево и остановить выполнение программы.

Программа для машины Поста:

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Примеры решения задач

Пояснения к условиям задач

1) В задачах под массивом понимается последовательность подряд идущих меток, ограниченная пустыми ячейками.

2) Если в задаче говорится, что на ленте задано число в унарной системе, то имеется в виду, что натуральное число n закодировано с помощью массива длины n.

3) В задачах при описании начального состояния ленты будем указывать то, что записано начиная с самой левой непустой ячейки и заканчивая самой правой непустой ячейкой. При этом будем использовать следующие обозначения: n подряд идущих меток будем обозначать 1n, а m пустых ячеек - 0m. При обозначении одной заполненной или пустой ячейки будем писать просто 1 или 0, соответственно.

К примеру, запись "12012" будет соответствовать записи "11011" на ленте.

4) Если не сказано ничего о местонахождении каретки в начальный момент времени, то будем считать, что каретка обозревает ячейку с самой левой меткой.


Применимость программ. Определение результата выполнения программ


1. Выяснить, применимы ли программы к заданным состояниям машины Поста, указать результат работы машины Поста для каждого состояния.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Ответы:

a) 1) 1110011000

2) зацикливание

3) 1001011000

b) 1) зацикливание

2) 010011

3) 01010110

c) 1) зацикливание (…111)

2) зацикливание (…1111001)

3) зацикливание (1010111…)

2. Определить состояние, в котором окажется машина Поста в результате выполнения программы при заданном начальном состоянии ленты.

Пояснение: выделенная цифра, например 1, означает, что эту ячейку каретка обозревает в начальный момент времени.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

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

a) 1) 110000001

2) 11000001

b) 1) 1100101

2) 10001

3) 111111


Арифметические задачи

Программы для решения всех задач этого раздела могут быть интерпретированы как выполнение элементарных арифметических операций. Важно показать, как с помощью простейших операций, которыми располагает машина Поста, можно выполнять арифметические операции - основу любого современного процессора.

3. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива.

Решение.

1. ? 2; 3 (команды 1 и 2 - передвигаем каретку к массиву)

2. -> 1

3. -> 4 (команды 3 и 4 - передвигаем каретку к концу массива)

4. ? 5; 3

5. V 6 (команды 5-7 - ставим 2 метки в конце массива)

6. -> 7

7. V 8

8. !

4. Даны два массива меток, которые находятся на не-
котором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Решение.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

5. На ленте задана последовательность массивов, включающая в себя один и более массивов. При этом два соседних массива отделены друг от друга одной пустой ячейкой. Необходимо на ленте оставить один массив длиной равной сумме длин массивов, присутствовавших изначально. Каретка находится над крайней левой меткой первого (левого) массива.

Решение.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

6. На ленте заданы два массива - m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

Решение. Запишем решение алгоритма в словесной форме.

1. Ищем правый край массива m, двигаясь слева направо.

2. Стираем правую метку массива m.

3. Ищем правый край массива n, двигаясь слева направо.

4. Стираем левую метку массива n.

5. Проверяем, мы стерли последнюю метку в массиве n (в этом случае следующая справа ячейка должна быть пустой)?

6. Если стерли последнюю метку, то конец алгоритма.

7. Иначе ищем правый конец массива m, двигаясь справа налево.

8. Переход на шаг 2.

1. -> 2 (команды 1-3: ищем левую метку массива m)

2. ? 3; 1

3. <- 4

4. X 5 (стираем левую метку массива m)

5. ? 6; 7

6. -> 5

7. X 8 (стираем левую метку массива n)

8. -> 9

9. ? 12; 10 (стерли последнюю метку в массиве n?)

10. <- 11 (ищем левый край массива m)

11. ? 10; 4

12. !

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

Решение.

1. -> 2

2. ? 3; 1 (идем до конца первого массива)

3. <- 4

4. X 5 (удаляем крайний правый элемент 1-го массива)

5. <- 6

6. ? 14; 7 (проверяем, что в 1-м массиве еще остались метки)

7. -> 8

8. ? 7; 9

9. X 10 (удаляем первую метку 2-го массива)

10. -> 11

11. ? 17; 12 (проверяем, что во 2-м массиве еще остались метки, иначе - завершение)

12. <- 13

13. ? 12; 4

14. -> 15 (мы удалили полностью 1-й массив)

15. ? 14; 16

16. X 17

17. !

8. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.

Решение. В результате работы программы справа от исходного массива будет сформирован новый массив удвоенной длины, исходный массив будет стерт.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

9. На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.

Решение.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)


Ориентация на ленте

10. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

Решение.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

11. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.

Решение.

1. X 2 (удаляем левую метку массива)

2. -> 3

3. ? 4; 2 (передвигаем каретку к концу массива)

4. V 5 (ставим справа от массива метку, раннее нами была удалена самая левая метка)

5. -> 6

6. ? 7; 10 (проверяем, передвинули ли мы уже наш массив к заданной метке)

7. <- 8

8. ? 9; 7 (идем к левой метке массива)

9. -> 1 (и начинаем все сначала)

10. !

12. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.

Решение. Этот алгоритм решения заимствован из замечательной книги В.А. Успенского "Машина Поста". Мы не знаем, в какую сторону нам надо двигаться, но, в какую бы сторону мы ни пошли, может случиться, что метка стоит в другой стороне. Очевидно, что нам надо двигаться попеременно, то в одну сторону, то в другую, постоянно увеличивая размах своих колебаний. Но как определить момент, когда надо поворачивать, т.е. менять направление? Выход из положения есть. Вначале работы выставим метки слева и справа от исходного положения каретки, а затем будем ходить между ними и передвигать их.

1. V 2 (выставили левую метку)

2. -> 3

3. ? 5; 4

4. ! (нашли метку, конец)

5. V 6 (выставили правую метку)

6. <- 7 (ищем левую метку)

7. ? 6; 8

8. X 9 (стираем левую метку)

9. <- 10

10. ? 11; 4

11. V 12 (передвигаем левую метку)

12. -> 13 (ищем правую метку)

13. ? 12; 14

14. X 15 (стираем правую метку)

15. -> 3 (повторяем действия)

Действия над заданным на ленте множеством меток

13. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.

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

1. -> 2

2. X 3

3. -> 4

4. ? 5, 2 (удаляем метки справа от исходного положения)

5. <- 6

6. V 7

7. <- 8 (возвращаемся к исходному положению)

8. ? 7; 9

9. <- 10

10. X 11

11. <- 12

12. ? 13; 10 (удаляем метки слева от исходного положения)

13. -> 14

14. V 15

15. -> 16

16. ? 15; 17 (возвращаемся к исходному положению)

17. X 18 (удаляем метку, соответствующую исходному положению каретки)

18. !

14. На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали nрасположенных подряд ячеек.

Решение. Идея решения состоит в последовательном придвижении каждой отдельной метки к уже сформированному массиву. Считаем, что каретка находится над левой меткой массива. Программа решения данной задачи эквивалентна программе сложения произвольного количества чисел (см. задачу 6).

15. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.

Решение.

1. -> 2

2. ? 3; 1 (идем до конца нечетного массива)

3. -> 4

4. ? 5; 6 (смотрим, есть ли еще массивы)

5. ! (массивов больше нет - завершение)

6. X 7 (удаляем четный массив)

7. -> 8

8. ? 9; 6

9. -> 10

10. ? 5; 1 (смотрим: есть ли еще массивы)

16. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.

Решение. Идея решения такова: будем "считать" массивы слева направо, удаляя каждый "посчитанный" массив. При этом слева от последовательности оставшихся массивов будем держать массив меток, длина которого соответствует числу "посчитанных" массивов.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

17. На ленте машины Поста расположен массив из 2n - 1 меток. Составить программу удаления средней метки массива.

Решение. Идея решения состоит в следующем: во вторых ячейках от каждого края массива ставим "маячки-пузырьки" (эти ячейки делаем пустыми). Далее последовательно перемещаем к центру левый и правый пузырьки. Эти пузырьки встретятся ровно на центральном элементе исходного массива. При реализации программы надо отдельно учесть три случая: n = 1, n = 3, n > 3. Считаем, что в начале работы каретка стоит на самой левой метке массива.

1. -> 2

2. ? 3; 4

3. <- 4 (n = 1)

4. Х 5

5.

6. -> 7

7. ? 8; 6

8. 9

9. <- 10

10. ? 20; 11

11. Х 12 (n > 3)

12. <- 13

13. ? 14; 12

14. V 15 (дошли до левого конца)

15. -> 16

16. X 17

17. -> 18

18. ? 19; 17

19. V 9 (дошли до правого конца)

20. ! (стерли центральную метку, конец)

18. На ленте машины Поста расположен массив из 2n ячеек. Составить программу, по которой машина Поста раздвинет на расстояние в одну ячейку две половины данного массива.

Решение. Идея решения состоит в следующем. Сначала между двумя левыми и двумя правыми метками ставим "маячки" - пустые клетки. Первым ставим левый маячок. Затем поочередно сдвигаем эти маячки к центру. Как только маячки сомкнутся, вместо правого маячка ставим метку, идем к правому краю массива и удаляем самую правую метку. Для простоты решения считаем, что каретка стоит под самой левой меткой.

19. Написать программу, которая осуществляет преобразование 1n01m -> 1m01n (n Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) 1 и m Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) 1).

Решение. Правый массив длины m остается на месте, левый массив переносится слева направо относительно неподвижного массива.

Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)

Задания для самостоятельной работы

  1. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

  2. Нахождение суммы любого количества массивов, которые отделены друг от друга одной ячейкой. Каретка находится над крайней левой меткой первого массива.

  3. Дан массив из N Меток. Сделать из него массив, в котором будет 2N+1 меток. Если полученный массив делится нацело на 3, то справа от него, через одну пустую ячейку, поставить две метки; если нет - то три метки. Каретка находится над крайней левой меткой.

  4. Произвести умножение двух чисел. Каретка располагается над пустой ячейкой, которая разделяет данные массивы.

  5. Составить программу нахождения разности двух целых неотрицательных чисел a и b. Если a меньше b, то перед разностью через одну пустую ячейку поставить метку. Каретка находится над крайней левой меткой левого числа.

  6. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.

  7. Дано N массивов меток. После последнего массива на расстоянии более трёх пустых ячеек находится одна метка. Массивы разделены тремя пустыми ячейками. Количество меток в массиве >=2. Если количество меток в массиве кратно трём, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

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

  9. Написать длину слова целым без знака.

  10. На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.

  11. На ленте расположены два массива разной длины. Каретка обозревает крайний элемент одного из них. Составьте программу для машины Поста, сравнивающую длины массивов и стирающую больший из них.

  12. Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

Контрольные задания


1. Написать программы для машины Поста, которые обладают следующими свойствами:

  • программа применима к любому состоянию машины Поста;

  • программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния - бесконечная;

  • программа не применима ни к какому состоянию машины Поста, и зона работы для любого начального состояния ограничена одним и тем же числом ячеек, не зависящим от выбранного начального состояния ленты;

  • программа применима к состояниям 13n (n Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) 1) и не применима к состояниям 13n+a, где a = 1, 2 и n Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) 1;

  • программа применима к состояниям 1a01a, где a Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) 1, и не применима к 1a01b, a Методические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста) b (a и bМетодические рекомендации по выполнению практикума по учебной дисциплине Теория алгоритмов (Машина Поста)1).

2. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.


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

  1. В.И.Игошин. Математическая логика и теория алгоритмов. [Текст]: В.И. Игошин. - М.: Академия, 2010 г. - 448 с.

  2. Б.Я. Фалевич. Теория алгоритмов. [Текст]: Б.Я. Фалевич. - М.: Машиностроение, 2012 г. - 160 с.

  3. Интернет-ресурс.softsearch.ru/programs/45-346-interpretator-mashiny-posta-download.shtml.


© 2010-2022