1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите {0,1}.
Решение: внешний алфавит машины будет следующим: {, 0, 1}.
Будем считать начальной следующую конфигурацию: q11…p. Для того, чтобы прибавить 1 к двоичному числу n сначала необходимо "отогнать" головку машины вправо и установить ее под последней (самой младшей) цифрой двоичного числа. Если последняя цифра числа есть 0, то достаточно заменить 0 на 1 и завершить процесс, то есть перевести головку (машину) в заключительное состояние q0.
Если же последняя цифра числа есть 1, то необходимо заменить ее на 0, а головку сдвинуть влево, чтобы "увидеть" следующий разряд двоичного числа. Если окажется, что этот разряд содержит 0, то заменить 0 на 1 и опять-таки перевести головку (машину) в заключительное состояние q0. Если же этот разряд содержит 1, необходимо заменить ее на 0 и опять сдвинуть головку влево. И так далее, до тех пор, пока либо не встретится разряд, содержащий 0, либо головка дойдет до первого слева пустого символа . В любом из этих случаев 0 или следует заменить на 1 и перевести головку (машину) в заключительное состояние q0.
Программа машины, прибавляющей 1 к двоичному числу, имеет вид:
| q11 q11R q10 q10R q1 q2L q20 q31H q21 q20L | q2 q01H q31 q31L q30 q30L q3 q0R.
|
2. Пусть требуется перевести запись натурального числа n, изображенного в виде последовательности n "палочек" (|) n 1, в двоичную запись в алфавите {0,1}. Т.е. конфигурация q1|||…| должна быть преобразована в q012…p , где 12…p - двоичная запись n.
Решение: в качестве внешнего алфавита машины берем алфавит:{, |, 0,1}.
Опишем алгоритм решения задачи в словесной форме:
"Отогнать" головку машины влево до первого пустого символа, заменить этот символ нулем (0).
"Отогнать" головку машины вправо до последней черточки, заменить ее пустым символом. Запомнить, что 1 из унарного представления числа n вычтена.
Установить головку под младшим разрядом формируемого двоичного числа и прибавить к двоичному числу 1 (так как мы делали это при построении предыдущей машины). Запомнить, что 1 к двоичному числу прибавлена.
Пункты 2 и 3 повторять до тех пор, пока не исчерпается исходное число, то есть на ленте не останется "палочек".
Головку отогнать в крайнюю левую позицию полученного двоичного числа и остановить машину.
Программа работы машины имеет вид:
| q1| q1|L q1q20R q2| q2|R q2 q3L q3| q4 L q4 | q4|L q40 q51R q41q40L | q4 q51R q51 q51R q50 q50R q5| q2|H q5 q6 L q61 q61L q60 q60L q6 q0R |
- Оглавление
- Задания для самостоятельного выполнения
- 1. Задайте множество а перечислением его элементов:
- 3. Пусть (X, y ) - координаты точек плоскости. Укажите штриховкой множествa a b и a b:
- Практическое занятие №2. Операции над множествами Задания для самостоятельного выполнения
- 1. Изобразите с помощью диаграмм Эйлера-Венна в двух вариантах расположения следующие множества:
- Практическое занятие №3. Равносильные преобразования множеств
- Задания для самостоятельного выполнения
- 1. Докажите тождества:
- Практическое занятие №4. Отображение и отношение множеств
- Задания для самостоятельного выполнения
- 1. Для отображения f: {10,20,30,40} {а,б,в,г}, заданного рисунком, найдите f({10,40}), f({10,20,30}), f - 1(б), f - 1 ({а,в}), f - 1 ({б,в,г}).
- 3. Выясните, к какому типу относятся отображения f1: а в и f2: а в.
- 4. Пусть f: {1,2,3} {1,2,3}, g: {1,2,3} {1,2,3}, h: {1,2,3} {1,2,3} – отображения, показанные на рисунке:
- Контрольные вопросы по теме «Элементы теории множеств»
- Глава 2. Элементы математической логики Практическое занятие №6. Основы алгебры логики
- 1. Элементы логики высказываний
- 2. Равносильные преобразования формул алгебры логики
- Задания для самостоятельного выполнения
- 1. Переформулируйте высказывания, если необходимо. Разбейте составные высказывания на простые и запишите их с помощью логической символики. Постройте таблицу истинности.
- 2. Вычислите значения выражений:
- 3. Постройте таблицы истинности формулы алгебры логики:
- Практическое занятие №7. Основы алгебры логики
- Задания для самостоятельного выполнения
- 1. Найдите суперпозицию функций для формул:
- 2. Постройте канонические формы для функций:
- 3. С помощью теоремы о полноте установите полноту системы:
- 4. Булевская функция f(X, y, z) задана таблично. Представьте эту же функцию формулой логики и функциональной схемой:
- Практическое занятие №9. Применение алгебры логики
- 1. Минимизация логических функций
- 2. Применение булевых функций для анализа и синтеза дискретных устройств. Упрощение и преобразование комбинационных схем
- 3. Применение булевых функций для анализа и синтеза релейно-контактных схем. Упрощение и преобразование релейно-контактных схем.
- Задания для самостоятельного выполнения
- 1. Минимизируйте методом Квайна - МакКласски булеву функцию f(x1, x2 ,x3, x4) , заданную таблицей истинности:
- 2. Укажите функцию f(x1, x2, x3, x4), реализуемую схемой из функциональных элементов:
- 3. Требуется произвести анализ и, если возможно, упрощение переключательных схем, приведенных на следующих рисунках:
- Практическое занятие №10. Применение алгебры логики
- Контрольные вопросы на тему: «Логические основы информатики»
- Глава 3. Элементы логики предикатов Практическое занятие №11. Понятие предиката.
- 1. Постройте матрицу одноместного предиката р(X), если:
- Задания для самостоятельного выполнения
- 1.Постройте матрицу одноместного предиката q(X), если:
- 2. Изобразите геометрически множество истинности одноместных предикатов g(X) и p(X), если:
- 3. Изобразите геометрически множество истинности предиката p(X), решив систему неравенств:
- 4. Изобразите геометрически множество истинности двуместного предиката a(X, y).
- 5. Изобразите геометрически множество истинности двуместного предиката q(X,y).
- Практическое занятие №12. Операции над предикатами и кванторами.
- 1. Пусть предикат q(X,y) определен на конечных множествах:
- Задания для самостоятельного выполнения
- Практическое занятие №13. Формулы логики предикатов.
- 1. Приведите формулу логики предикатов к приведенной форме:
- 3. Приведите формулу логики предикатов к предваренной нормальной форме XyP(X, y) XyQ(X, y).
- Задания для самостоятельного выполнения
- Практическое занятие №13. Применение логики предикатов.
- Задания для самостоятельного выполнения
- 1. Запишите аксиомы положительных величин на языке логики предикатов, используя ограниченные кванторы:
- 2. Запишите некоторые аксиомы действительных чисел на языке логики предикатов, используя ограниченные кванторы:
- 3. Подберите элементарные предикаты и запишите следующие высказывания:
- 5. Запишите определения на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
- 6. Запишите теоремы и свойства на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
- 0) Основная теорема алгебры.
- 7. Запишите теоремы на языке логики предикатов, используя ограниченные кванторы, и постройте их отрицания:
- Глава 4. Элементы теории алгоритмов
- Задания для самостоятельного выполнения
- 1. Опишите алгоритмы в словесной форме:
- 2. Опишите алгоритмы в словесно-формульной форме:
- 4.2.Практическое занятие №15. Виды алгоритмов.
- 1. Опишите графическим способом алгоритм расчета нормы расхода гербицида (л/га) по формуле:.
- Задания для самостоятельного выполнения
- 2. Опишите алгоритмы в графической форме. Даны положительные вещественные числа X и y. Присвойте целой переменной z:
- 1. Опишите графическим способом алгоритм вычисления значения выражения:
- Задания для самостоятельного выполнения
- 4. Даны действительные числа X, y и z. Вычислите:
- Практическое занятие №16. Виды алгоритмов.
- 1.Составьте блок-схему алгоритма вычисления среднеквадратической взвешенной по формуле:
- 2.Составьте блок-схему алгоритма вычисления суммы кубов последовательности, состоящей из положительных чисел до первого введенного отрицательного числа.
- Задания для самостоятельного выполнения
- Практическое занятие №17. Машина Тьюринга.
- 1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите {0,1}.
- 3. Составьте программу машины Тьюринга, подсчитывающую число вхождений символа a в слово р в алфавите {a, b, c}.
- Задания для самостоятельного выполнения
- 1. Постройте машину Тьюринга,
- 3. Постройте машину Тьюринга, осуществляющую перевод натурального числа n
- 4. Постройте машину Тьюринга,
- Рекомендуемая литература