Глава 5.        Элементы теории алгоритмов

Практические работы

Практическая работа № 36.           
Машина Тьюринга

1.       Наберите программу из учебника (или из презентации), которая увеличивает двоичное число на 1 и проверьте её работу.

Будет ли правильно работать эта программа, если вначале каретка расположена справа от числа? Почему?

Ответ:

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

3.       Опишите алгоритм работы программы для машины Тьюринга:

Ответ:

При каком начальном состоянии ленты и положении каретки эта программа зацикливается?

Ответ:

4.       Составьте программу для машины Тьюринга, которая заменяет в двоичном числе все 0 на 1 и все 1 на 0 (из числа 10101100 получается 01010011). Каретка находится слева от числа.

Описание состояний:

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

Описание состояний:

6.       Составьте программу для машины Тьюринга, которая увеличивает троичное число на 1. Каретка находится справа от числа.

Описание состояний:

При каком начальном положении каретки эта программа зацикливается?

Ответ:

7.       Составьте программу для машины Тьюринга, которая уменьшает двоичное число на 1. Каретка находится над числом.

Описание состояний:

При каком начальном положении каретки эта программа зацикливается?

Ответ:

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

Описание состояний:

9.       Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая переставляет последний символ в начало строки. Каретка находится над первым символом строки.

Описание состояний:

10.   *Дана строка, состоящая только из символов «а» и «б». Составьте программу для машины Тьюринга, которая сортирует символы, то есть переставляет все буквы «а» в начало строки. Каретка находится над первым символом строки. Используйте состояния, которые перечислены род таблицей.

Описание состояний:

11.   *Составьте программу для машины Тьюринга, которая складывает два числа в двоичной системе, разделенные на ленте знаком «+».

12.   *Составьте программы для машины Тьюринга, которые увеличивают и уменьшают на единицу число, записанное в десятичной системе счисления.

13.   Составьте программы для машины Тьюринга, которые выполняют сложение и вычитание двух чисел в десятичной системе счисления.

Практическая работа № 37.           
Машина Поста

1.       Что делает следующая программа для машины Поста?

Ответ:

Как она будет работать при различных начальных состояниях ленты?

Ответ:

2.       Напишите программу для машины Поста, которая неприменима (то есть зацикливается) при любом начальном состоянии ленты.

3.       Напишите программу для машины Поста, которая увеличивает на 1 число, записанной в унарной системе счисления. Каретка стоит над первой (самой левой) отметкой.

4.       Решите задачу 2 при условии, что в начале работы каретка расположена где-то справа от  записи числа.

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

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

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

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

9.       *Напишите программу для машины Поста, которая складывает два числа, записанных в унарной системе. Числа расположены на неизвестном расстоянии друг от друга. Каретка находится над левой границей первого (левого) числа.

10.   **Напишите программу для машины Поста, которая складывает несколько натуральных чисел. Каждое число кодируется как последовательность расположенных рядом отметок (в унарной системе счисления). Числа отделены друг от друга пробелами. Каретка находится справа от первого числа.

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

Практическая работа № 38.           
Нормальные алгорифмы Маркова (НАМ)

1.       Что делает следующий НАМ, если применить его к символьной цепочке, состоящей из нулей и единиц:

Ответ:

Как будет работать этот алгоритм при различных начальных состояниях ленты?

Ответ:

2.       Напишите НАМ, который «сортирует» цифры двоичного числа так, чтобы сначала стояли все нули, а потом – все единицы.

Ответ:

3.       Напишите НАМ, который удаляет последний символ строки, состоящей из цифр 0 и 1. Какую операцию он выполняет, если рассматривать строку как двоичную запись числа?

Ответ:

4.       Напишите НАМ, который умножает двоичное число на 2, добавляя 0 в конец записи числа.

Ответ:

5.       Напишите НАМ, который переводит число из двоичной системы счисления в единичную (унарную).

Ответ:

6.       Дано слово, состоящее из букв «а», «б» и пробелов. Постройте нормальный алгоритм Маркова, который символы «а» переносит влево, символы «б» – вправо, а пробелы оставляет посередине.

Ответ:

7.       Дано число в унарной системе счисления (от 1 до 15), сразу после числа стоит точка. Напишите НАМ, который представляет это число в виде суммы степеней двойки (например, для числа 15 нужно получить «8+4+2+1»), и удаляет точку в конце.

Ответ:

8.       *Напишите НАМ, который переводит число из четверичной системы счисления в двоичную. Используйте специальный знак (например, *), который отделяет обработанную часть числа от необработанной.

Ответ:

9.       **Дана последовательность скобок. Напишите НАМ, который проверяет правильность скобочной структуры (парность и вложенность скобок). Например, выражение ()()(())(()())(())() – правильное, а  выражения

()()(())(()())(()))( и ()()(())(()())(())) – неправильные.

Если все правильно, лента должна быть пустой, если выражение неверное, на ленте должны остаться «неправильные» скобки.

10.   **Напишите НАМ, который увеличивает на единицу число, записанное в троичной системе счисления. Используйте специальные символы (например, # и *) для обозначения начала числа и того разряда, который нужно увеличивать первым.

11.   **Напишите НАМ, который уменьшает на единицу число, записанное в троичной системе счисления. Используйте специальные символы (например, # и *) для обозначения начала числа и того разряда, который нужно уменьшать первым.

12.   **Напишите НАМ, который складывает два числа в двоичной системе счисления. Числа разделены знаком «+», например, из строки «1011+1101» нужно получить «11000». Используйте алгоритм, в котором последовательно первое число увеличивается на 1, а второе – уменьшается на 1, пока второе не станет равно 0.

Практическая работа № 39.           
Вычислимые функции

1.       Целое число n записано на ленте в унарной системе счисления (как последовательность из n меток). Напишите программу для машины Поста, которая вычисляет функцию

и таким образом доказывает разрешимость этой задачи. В начальный момент каретка стоит над первой меткой числа.

Ответ:

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

Целое число n записано в унарной системе счисления.

Ответ:

Практическая работа № 40.           
Инвариант цикла

1.       Определите инвариант цикла для следующего алгоритма двоичного поиска (предполагается, что элементы массива A отсортированы по неубыванию):

 L:= 1; R:= n + 1

 нц пока L < R - 1

   c:= div(L + R, 2)

   если X < A[c] то

     R:= c

   иначе

     L:= c

   все

 кц

Ответ:

Используя найденный инвариант, определите, какой именно элемент массива будет найден, если в массиве есть несколько элементов, равных X.

Ответ:

Как нужно изменить инвариант (и цикл!), чтобы найти первый элемент, равный X?

Ответ:

2.       Определите инвариант для следующего цикла.

 k := 0; b := 1

 нц пока k < n 

   k := k + 1

   b := b * a

 кц

Ответ:

Что будет вычислено в переменной b?

Ответ:

3.       Определите инвариант для следующего цикла.

 k := n; b := 1

 нц пока k > 0 

   k := k - 1 

   b := b * a

 кц

Ответ:

Что будет вычислено в переменной b?

Ответ:

4.       Запишите предусловие и постусловие для алгоритма вычисления сумму всех делителей числа.

Ответ:

5.       Запишите предусловие и постусловие для алгоритма проверки числа на простоту.

Ответ:

6.       Запишите предусловие и постусловие для алгоритма определения количества слов в символьной строке.

Ответ:

7.       Запишите предусловие и постусловие для алгоритма двоичного поиска в отсортированном массиве.

Ответ:

8.       Запишите предусловие и постусловие для алгоритма перестановки элементов массива в обратном порядке.

Ответ:

9.       Запишите предусловие и постусловие для алгоритма преобразования числа из символьной записи в значение целого типа.

Ответ:

10.   Предложите другие начальные значения переменных ,  и  в алгоритме быстрого возведения в степень (см. Пример 4 в §37 учебника). Инвариант цикла должен сохраниться.

Ответ:

11.   Оцените сложность алгоритма быстрого возведения в степень при , где m – натуральное число.

Ответ:

Практическая работа № 40а.

Сложность вычислений

1.       Запишите алгоритм, который находит все делители натурального числа.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

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

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

3.       Запишите алгоритм, который находит количество положительных элементов массива.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

4.       Запишите алгоритм, который находит три минимальных элемента массива.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

5.       Запишите алгоритм, который находит количество элементов массива, равных минимальному элементу.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

6.       Запишите алгоритм, который находит (и выводит на экран) символы, которые встречаются в символьной строке более одного раза.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ:

7.       Алфавит языка племени «тумба-юмба» содержит k символов. Запишите алгоритм построения всех возможных слов этого языка, имеющих длину n символов.

Ответ:

Какие элементарные операции в нём можно выделить?

Ответ:

Оцените количество этих операций.

Ответ:

Определите асимптотическую сложность алгоритма.

Ответ: