Выполнение расчетно-графических работ

Имени Иммануила Канта

 

Задания и методические указания для выполнения лабораторных работ студентами по дисциплине ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ

 

 

Калининград

 

Выполнение расчетно-графических работ

РГР выполняются в полном соответствии с методическим указаниями, которые имеются по каждой из девяти РГР. Это значит, что в отчете о РГР должен присутствовать текст, рисунки, таблицы и расчеты, которые даны в методических указаниях. Никакие другие формы представления результатов домашней работы студента не принимаются и возвращаются на переделку. Не стоит также «слепо» копировать файл методических указаний и «превращать» его в файл отчета о РГР.

РГР выполняются студентом самостоятельно. Идентичность (устанавливается преподавателем) двух или более отчетов о РГР приводит к смене номеров вариантов для каждого студента и повторному выполнению расчетов, оформлению и рецензированию преподавателем.

 

Оформление расчетно-графических работ

РГР оформляются на стандартных листах писчей бумаги с использованием текстового редактора и печатаются на принтере, кегль шрифта Time New Roman – 14. Отчет о РГР подшивается в папку. Отчет о РГР начинается со стандартного титульного листа на котором указывается (сверху - вниз): учебное заведение, кафедра, название и номер РГР, автор, дата выполнения, проверяющий с указанием ученой степени, ученого звания, фамилии и имени, отчества, дата проверки, город, год.

После титульного листа следует содержание с указанием разделов и станиц.

Далее идет текст отчета с рисунками, таблицами, расчетами разбитый на соответствующие методическим указаниями разделы.

Далее следует список использованной литературы.

Оформленные не аккуратно отчеты о РГР возвращаются на доработку.

Резолюция на титульном листе проверенной преподавателем РГР «Устранить замечания» требует от студента следующего: 1. Внимательно ознакомиться с замечаниями преподавателя, которые даны по тексту РГР; 2. Дать исправления в специальном разделе в конце РГР «Работа над замечаниями». В этом разделе отмеченное преподавателем место в тексте должно быть дано верно, без ошибок; 3. Листы с ошибками не удалять, текст РГР заново не перепечатывать; 4. Сдать РГР на повторную проверку.

Резолюция на титульном листе РГР «Обратите внимание на мои замечания» требует от студента следующего: 1. Внимательно ознакомиться с замечаниями преподавателя, которые даны по тексту РГР; 2. Дать исправления в специальном разделе в конце РГР «Работа над замечаниями». В этом разделе отмеченное преподавателем место в тексте должно быть дано верно, без ошибок; 3. Листы с ошибками не удалять, текст РГР заново не перепечатывать; 4. На повторную проверку РГР не сдавать.

 

 

Расчетно-графическая работа №1

Тема: «Системы счисления».

1 Теоретическая часть

1.1 Виды сигнала

Сигнал может быть дискретным и непрерывным (аналоговым).

Дискретный сигнал слагается из счетного множества (т.е. такого множества, элементы которого можно пересчитать) элементов (говорят – информационных элементов).

Например, дискретным является сигнал «кирпич». Он состоит из следующих двух элементов (это синтаксическая характеристика данного сигнала): красного кольца на белом фоне, красного прямоугольника внутри кольца.

Именно в виде дискретного сигнала представлена та информация, которую сейчас осваивает читатель. Можно выделить следующие ее элементы: разделы (например, «Теоретическая часть»), подразделы (например, «Виды сигнала»), абзацы, предложения, отдельные фразы, слова и отдельные знаки (буквы, цифры, знаки препинания и т.д.).

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

Набор самых «мелких» элементов дискретного сигнала называется алфавитом, а сам дискретный сигнал называют также сообщением.

Непрерывный сигнал – отражается некоторой физической величиной, изменяющейся в заданном интервале времени. В виде непрерывного сигнала представлена настоящая информация для тех студентов – потребителей, которые посещают лекции по информатике и через звуковые волны (иначе говоря, голос лектора), носящие непрерывный характер, воспринимают материал.

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

 

1.2 Преобразования сигнала

Для преобразования аналогового сигнала в дискретный используется процедура, которая называется квантованием. Различают два вида квантования – по времени и по уровню (дискретизацию).

Квантование по времени – замена непрерывной (по времени и по уровню) функции x(t) (рис. 4.1а) некоторым множеством непрерывных (по уровню) функций x(t_i) (на рис. 1б i = {1,2,3,4}).

x x

x (t₃) x (t₃)

x (t₂) x (t₄) x (t₂) x (t₄)

x (t₁) x (t₁)

x (t)

t₁ t₂ t₃ t₄ t t₁ t₂ t₃ t₄ t

а) б)

Рис. 4.1. Иллюстрация к квантованию по времени:

а) аналоговый сигнал x (t) до квантования;

б) дискретный (по времени) сигнал x (t) – результат квантования.

 

Очевидно, дискретизация связана с потерей информации. В самом деле, дискретный сигнал на рис. 1б не показывает, как ведет себя исходный сигнал в моменты времени, например, между t₃ и t₄. Иначе говоря, дискретизация связана с некоторой погрешностью e, которая зависит от шага дискретизации Dt = t_i – t_i-1: при малых значениях шага дискретизации число точек замера высоко, и теряется мало информации; очевидно, картина обратная при больших шагах дискретизации. Погрешность дискретизации e в каждый момент времени t определяется по формуле:

e(t) = x (t) – v(t), (1.1)

где v(t) – функция восстановления, которая по дискретным значениям восстанавливает x (t).

Виды дискретизации различаются по регулярности отсчетов:

1) равномерная дискретизация, когда Dt постоянно;

2) неравномерная дискретизация, когда Dt переменно, причем этот вид, в свою очередь, делится на подвиды:

- адаптивную, когда Dt меняется автоматически в зависимости от текущего изменения сигнала. Это позволяет увеличивать шаг дискретизации, когда изменения сигнала x (t) незначительны, и уменьшать – в противном случае;

- программируемую, когда Dt изменяется оператором или в соответствии с заранее выставленными условиями, например, в фиксированные моменты времени.

Квантование по уровню - преобразование непрерывных (по уровню) сигналов x (t_i) в моменты отсчета t_i в дискретные. В результате непрерывное множество значений сигнала x (t_i) в диапазоне от x_min до x_max преобразуется в дискретное множество значений x_k – уровней квантования (рис. 4.2). Шаг квантования D x определяется по формуле:

D x = x_j – x_j-1.

Можно сказать, что квантование по уровню – это измерение сигнала. В самом деле, по рис. 4.2б видно, что сигнал x (t₁) составляет 0 уровней квантования (k = 0), а сигнал x (t₄) – 2 уровня квантования (k = 2).

x (t) x (t)

x 2

x (t₃) x _max x (t₃)

x min

x 1

x (t₂) x (t₄) x (t₂) x (t₄)

x (t₁) x (t₁)

t₁ t₂ t₃ t₄ t t₁ t₂ t₃ t₄ t

а) б)

Рис. 4.2. Иллюстрация к квантованию по уровню:

а) аналоговые по уровню (но дискретные по времени) сигналы x (t_i) до квантования;

б) квантованные по уровню сигналы x (t_i).

 

При квантовании по уровню не всегда сигнал x (t_i) совпадает с уровнем квантования (см. сигнал x (t₂) на рис. 4.2б). В таком случае поступают одним из следующих способов:

1) x (t_i) отождествляют с ближайшим значением (в нашем примере – с x ₂);

2) x (t_i) отождествляют с ближайшим меньшим (или большим) значением. Тогда при отождествлении с ближайшим большим значением сигнал x (t₂) отождествится с x ₂ независимо от того, насколько близко он к этому уровню квантования находится. При отождествлении с ближайшим меньшим значением сигнал x (t₂) отождествится с x ₁ также независимо от того, насколько близко он к этому уровню квантования находится.

Очевидно, и при квантовании по уровню возникает погрешность квантования e(x _k):

e(x _k) = x (t_i) - x _k. (1.2)

Погрешность квантования по уровню тем меньше, чем меньше шаг квантования.

Виды квантования по уровню:

1) равномерное, когда диапазон изменения сигнала разбивается на m одинаковых частей. Тогда, зная размер шага квантования, для представления x _k достаточно знать число k.

2) неравномерное, когда диапазон изменения сигнала разбивается на m различных частей.

 

1.3 Системы счисления

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

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

 

 

Тогда полное число получается по формуле:

(1.3)

где l – количество разрядов числа,

i – порядковый номер разряда,

m – основание системы счисления,

a_i – множитель, принимающий любые целочисленные значения от 0 до m -1, и соответствующий цифре в i -й позиции числа.

Например, для десятичного (m = 10) числа 345 его полное значение рассчитывается по формуле:

3*10² + 4*10¹ + 5*10⁰ = 345.

Римские числа являются примером полупозиционной системы образования числа: так, в числах IX и XI знак I обозначает в обоих случаях единицу (признак непозиционной системы), но будучи расположенным слева от знака X (обозначающего десять), вычитается из десяти, а при расположении справа – прибавляется к десяти. В первом случае полное значение числа равно 9, во втором – 11.

В современной информатике используются в основном три системы счисления (все – позиционные): двоичная, шестнадцатеричная и десятичная.

Двоичная система счисления используется для кодирования дискретного сигнала, потребителем которого является вычислительная техника. Такое положение дел сложилось исторически, поскольку двоичный сигнал проще представлять на аппаратном уровне. В этой системе счисления для представления числа применяются два знака – 0 и 1.

Шестнадцатеричная система счисления используется для кодирования дискретного сигнала, потребителем которого является хорошо подготовленный пользователь – специалист в области информатики. В такой форме представляется содержимое любого файла, затребованное через интегрированные оболочки операционной системы, например, средствами Norton Commander в случае MS DOS. Используемые знаки для представления числа – десятичные цифры от 0 до 9 и буквы латинского алфавита – A, B, C, D, E, F.

Десятичная система счисления используется для кодирования дискретного сигнала, потребителем которого является так называемый конечный пользователь – неспециалист в области информатики (очевидно, что и любой человек может выступать в роли такого потребителя). Используемые знаки для представления числа – цифры от 0 до 9.

Соответствие между первыми несколькими натуральными числами всех трех систем счисления представлено в табл. 4.1.

 

Таблица 4.1

Десятичная система	Двоичная система	Шестнадцатеричная система
		A
		B
		C
		D
		E
		F

 

Для различения систем счисления, в которых представлены числа, в обозначение двоичных и шестнадцатеричных чисел вводят дополнительные реквизиты:

- для двоичных чисел – нижний индекс справа от числа в виде цифры 2 или букв В или b (binary – двоичный), либо знак B или b справа от числа. Например, 10₂ = 10_b = 10_B = 10B = 10b;

- для шестнадцатеричных чисел - нижний индекс справа от числа в виде числа 16 или букв H или h (hexadecimal – шестнадцатеричный), либо знак H или h справа от числа. Например, 3AB₁₆ = 3AB_H = 3AB_h = 3ABH = 3ABh.

Для перевода чисел из одной системы счисления в другую существуют определенные правила.

 

1.4 Правила перевода чисел из одной системы счисления в другую

Правила перевода различаются в зависимости от формата числа – целое или правильная дробь (дробь, знаменатель которой больше числителя (например, ¹/₂, ⁵/₆ и т.д.)). Для вещественных чисел используется комбинация правил перевода для целого числа и правильной дроби.

Правила сложения

Пример 16. Сложить двоичные числа 1101₂ и 11011₂.

Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов: 5 4 3 2 1

₊ 1 1 0 1₂

1 1 0 1 1₂

Процесс образования результата по разрядам описан ниже:

а) разряд 1 формируется следующим образом: 1₂ + 1₂ = 10₂; 0 остается в разряде 1, 1 переносится во второй разряд;

б) разряд 2 формируется следующим образом: 0₂ + 1₂ + 1₂ = 10₂, где вторая 1₂ – единица переноса; 0 остается в разряде 2, 1 переносится в третий разряд;

в) третий разряд формируется следующим образом: 1₂ + 0₂ + 1₂ = 10₂, где вторая 1₂ – единица переноса; 0 остается в разряде 3, 1 переносится в разряд 4;

г) четвертый разряд формируется следующим образом: 1₂ + 1₂ + 1₂ = 11₂, где третья 1₂ – единица переноса; 1 остается в разряде 4, 1 переносится в пятый разряд;

д) пятый разряд формируется следующим образом: 1₂ + 1₂ = 10₂; где вторая 1₂ – единица переноса; 0 остается в разряде 5, 1 переносится в шестой разряд.

Таким образом:

₊ 1 1 0 1₂

1 1 0 1 1₂

10 1 0 0 0₂.

Проверим результат. Для этого определим полные значения слагаемых и результата:

1101₂ = 1*2³ +1*2² + 0*2¹ + 1*2⁰ = 8 + 4 + 1 = 13;

11011₂ = 1*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰ = 16 + 8 + 2 + 1 = 27;

101000₂ = 1*2⁵ + 0*2⁴ + 1*2³ + 0*2² + 0*2¹ + 0*2⁰ = 32 + 8 = 40.

Поскольку 13 + 27 = 40, двоичное сложение выполнено верно.

Пример 17. Сложить шестнадцатеричные числа 1С₁₆ и 7В₁₆.

Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов: 2 1

₊ 1 С₁₆

7 В₁₆

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

а) разряд 1 формируется следующим образом: С₁₆ + В₁₆ = 12 + 11 = 23 = 17₁₆; 7 остается в разряде 1; 1 переносится в разряд 2;

б) разряд 2 формируется следующим образом: 1₁₆ + 7₁₆ + 1₁₆ = 9₁₆, где вторая 1₁₆ – единица переноса.

 

Таким образом:

₊ 1 С₁₆

7 В₁₆

9 7₁₆.

Проверим результат. Для этого определим полные значения слагаемых и результата:

1С₁₆ = 1*16¹ + 12*16⁰ = 16 + 12 = 28;

7В₁₆ = 7*16¹ + 11*16⁰ = 112 + 11 = 123;

97₁₆ = 9*16¹ + 7*16⁰ = 144 + 7 = 151.

Поскольку 28 + 123 = 151, сложение выполнено верно.

 

Правила вычитания

Вычесть из двоичного числа 101₂ двоичное число 11₂.

Запишем алгебраические слагаемые в столбик в порядке «уменьшаемое – вычитаемое» и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов: 3 2 1

_- 1 0 1₂

1 1₂

Процесс образования результата по разрядам описан ниже:

а) разряд 1 формируется следующим образом: 1₂ – 1₂ = 0₂;

б) разряд 2 формируется следующим образом: поскольку 0 < 1 и непосредственное вычитание невозможно, занимаем для уменьшаемого единицу в старшем разряде 3. Тогда разряд 2 рассчитывается как 10₂ – 1₂ = 1₂;

в) третий разряд формируется следующим образом: поскольку единица была занята в предыдущем шаге, в разряде остался 0.

Таким образом:

_- 1 0 1₂

1 1₂

1 0₂.

Проверим результат. Для этого определим полные значения слагаемых и результата. По табл. 4.1 имеем:

101₂ = 5; 11₂ = 3; 10₂ = 2.

Поскольку 5 – 3 = 2, вычитание выполнено верно.

Пример 19. Вычесть из шестнадцатеричного числа 97₁₆ шестнадцатеричное число 7В₁₆.

Запишем алгебраические слагаемые в столбик в порядке «уменьшаемое – вычитаемое» и пронумеруем разряды, присвоив младшему разряду номер 1:

 

номера разрядов: 2 1

_- 9 7₁₆

7 В₁₆

Процесс образования результата по разрядам описан ниже:

а) разряд 1 формируется следующим образом: поскольку 7₁₆ < В₁₆ и непосредственное вычитание невозможно, занимаем для уменьшаемого единицу в старшем разряде 2. Тогда 17₁₆ – В₁₆ = 23 – 11 = 12 = С₁₆;

б) разряд 2 формируется следующим образом: поскольку единица была занята в предыдущем шаге, разряд 2 уменьшаемого стал равным 8₁₆. Тогда разряд 2 рассчитывается как 8₁₆ – 7₁₆ = 1₁₆.

Таким образом:

_- 9 7₁₆

7 В₁₆

1 С₁₆.

Для проверки результата используем данные из примера 17.

 

Правила умножения

Пример 20. Умножить двоичное число 101₂ на двоичное число 11₂.

Запишем множители в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов: 3 2 1

_* 1 0 1₂

1 1₂

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

а) умножение множимого на разряд 1 множителя дает результат: 101₂ * 1₂ = 101₂;

б) умножение множимого на разряд 2 множителя дает результат: 101₂ * 10₂ = 1010₂. Здесь значение разряда 2 множителя сформировано по принципам формирования значения числа в позиционных системах счисления;

в) для получения окончательного результата складываем результаты предыдущих шагов: 101₂ + 1010₂ = 1111₂.

Для проверки результата найдем полное значение сомножителей и произведения (см. табл. 4.1):

101₂ = 5; 11₂ = 3; 1111₂ = 15.

Поскольку 5 * 3 = 15, умножение выполнено верно: 101₂ * 11₂ = 1111₂.

Пример 21. Умножить шестнадцатеричное число 1С₁₆ на шестнадцатеричное число 7В₁₆.

Запишем множители в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов: 2 1

_* 1 С₁₆

7 В₁₆

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

а) умножение множимого на разряд 1 множителя дает результат: 1С₁₆ * В₁₆ = 28 * 11 = 308 = 134₁₆;

б) умножение множимого на разряд 2 множителя дает результат: 1С₁₆ * 70₁₆ = 28 * 112 = 3136 = С40₁₆. Здесь значение разряда 2 множителя сформировано по принципам формирования значения числа в позиционных системах счисления;

в) для получения окончательного результата складываем результаты предыдущих шагов: 134₁₆ + С40₁₆ = D74₁₆.

Для проверки результата найдем полное значение сомножителей и произведения, воспользовавшись результатами примера 17 и правилами формирования полного значения числа:

1С₁₆ = 28; 7В₁₆ = 123;

D74₁₆ = 13*16² + 7*16¹ + 4*16⁰ = 3444.

Поскольку 28 * 123 = 3444, умножение выполнено верно: 1С₁₆ * 7В₁₆ = D74₁₆.

Правила деления

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

Пример 22. Разделить двоичное число 1111₂ на двоичное число 11₂.

Решение задачи представим схемой:

_-1111₂ 11₂

11₂ 101₂

_-011₂

11₂

0₂

Для проверки правильности результата воспользуемся данными из примера 20. Они показывают, что деление выполнено верно: 1111₂ / 11₂ = 101₂.

 

2 Задание

Выполнить подробные (как в примерах теоретической части; если применяются формулы, то указать какие с полным их описанием) переводы и арифметические действия над числами, выбранными в соответствии с вариантом задания:

1) Перевод целого числа A из десятичной системы счисления – в двоичную и шестнадцатеричную.

2) Перевод целых чисел B и С из двоичной и шестнадцатеричной систем счисления соответственно – в десятичную.

3) Перевод целого числа B из двоичной системы счисления в шестнадцатеричную.

4) Перевод целого числа C из шестнадцатеричной системы счисления в двоичную.

5) Перевод правильной дроби (1/A+0.68) (округление до 4-ого знака) из десятичной системы счисления – в двоичную и шестнадцатеричную. Перевод выполнить до четырех значащих цифр после запятой.

6) Перевод правильных дробей D и E из двоичной и шестнадцатеричной систем счисления соответственно – в десятичную.

7) Перевод правильной дроби D из двоичной системы счисления в шестнадцатеричную.

8) Перевод правильной дроби E из шестнадцатеричной системы счисления в двоичную.

9) Перевод из десятичной системы счисления в шестнадцатеричную числа, целая часть которого равна (A+A), а дробная − 3*A. Перевод выполнить до четырех значащих цифр после запятой.

10) Сложить двоичные числа B и 110(B). Проверить результат.

11) Сложить шестнадцатеричные числа C и 7(C). Проверить результат.

12) Вычесть из двоичного числа (B)1110двоичное число B. Проверить результат.

13) Вычесть из шестнадцатеричного числа (C)987шестнадцатеричное число C. Проверить результат.

14) Умножить двоичное число B на двоичное число 110(B). Проверить результат.

15) Умножить шестнадцатеричное число C на шестнадцатеричное число 7(C). Проверить результат.

 

3 Содержание отчета

1) Сформулировать задание в соответствие с вариантом (подробно).

2) Выполнить подробно все переводы, арифметические действия над числами и проверки, описанные в задании, выделяя каждый отдельно.

 

4 Варианты задания

 

Номер варианта	A	B	C	D	E
				0,1010011	0,110A
			1F	0,1110010	0,1FA
			2E	0,1010101	0,2EB
			3D	0,1100110	0,3DC
			4C	0,1111111	0,4CD
			5B	0,1011100	0,5BE
			6A	0,1000001	0,6AF
			8F	0,1011110	0,8F10
			9E	0,1000011	0,9E1
			10D	0,1110000	0,10D2
			11C	0,1101101	0,11C3
			12B	0,1010000	0,12B4
			13A	0,1001111	0,13A5
			14F	0,1010000	0,14F6
			15E	0,1100101	0,15E7
			16D	0,1101010	0,16D8
			17C	0,1101111	0,17C9

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

1. Гашков С.Б. Системы счисления и их применение.— М.: МЦНМО, 2004. г.

2. Топоркова О.М. Информатика: Учебн. пособ. – Калининград: КГТУ, 2001.

3. Фомин С.В. Системы счисления. — М.: Наука, 1987 г.

 

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

1. Афанасьев В.В. Теория вероятностей в вопросах и задачах: http://cito-web.yspu.org/link1/metod/theory/theory.html

2. Топоркова О.М. Информатика: Учебн. пособ. – Калининград: КГТУ, 2001.

3. Яглом А. М., Яглом И. М. Вероятность и информация. — М.: «Наука», 1973.

Правила выполнения НАМ.

Прежде всего, задается некоторое входное слово Р. Где именно оно записано – не важно, в НАМ этот вопрос не оговаривается.

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

На следующем шаге это слово Р′ берется за исходное и к нему применяется та же самая процедура, т.е. формулы снова просматриваются сверху вниз начиная с самой верхней и ищется первая формула, применимая к слову Р′, после чего выполняется соответствующая подстановка и получается новое слово Р′′. И так далее:

Р → Р′ → Р′′ → …

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

Необходимые уточнения:

1. Если на очередном шаге была применена обычная формула (α→β), то работа НАМ продолжается.

2. Если же на очередном шаге была применена заключительная формула (α β), то после её применения работа НАМ прекращается. То слово, которое получилось в этот момент, и есть выходное слово, т.е. результат применения НАМ к входному слову.

3. Если на очередном шаге к текущему слову неприменима ни одна формула, то и в этом случае работа НАМ прекращается, а выходным словом считается текущее слово.

Таким образом, НАМ останавливается по двум причинам: либо была применена заключительная формула, либо ни одна из формул не подошла. То и другое считается «хорошим» окончанием работы НАМ. В обоих случаях говорят, что НАМ применuм к входному слову.

Однако может случиться и так, что НАМ никогда не остановится; это происходит, когда на каждом шаге есть применимая формула и эта формула обычная. Тогда говорят, что НАМ неприменим к входному слову. В этом случае ни о каком результате нет и речи.

Nbsp;   i ... |=1i+1   Для упорядочения составления протоколов информационную ленту ограничивают только в одну сторону, т. е. существуют левые и правые полуленты. В зависимости от используемой полуленты приняты различные схемы записи конфигураций машины Тьюринга (табл. 5.2).     Таблица 5.2 Стандартная Информационная полулента конфигурация правая левая Начальная qn|x 1+1# |x 2+ 1#...#|x n+ 1 |x 1+1# |x 2+ 1#...#|x nqn| Конечная qk|y + 1 |yqk|   Работу машины Тьюринга удобно представлять протоколом, таблицей и графом. При протокольной записи все команды должны быть записаны упорядоченным списком. На заключительном шаге должно быть получено значение заданной функции, т. е. y=f(x1, x2,...xn). Например, 1) qnai —>qiajD; 2) qiak —>qjaiD; ................................. n) q|am—>qkanC. При табличном описании каждая строка имеет имя текущего состояния машины, а столбец–имя символа внешней памяти. Тогда элементами таблицы являются правые части команд (qjaiD).   Таблица 5.3   Текущее Символы vt   состояние аi ак ... am   qn qiajD ...       qi ... qjaiD   ...   ... ... ... ... ...   qi ... ... ... qkanC   Табличная форма описания машины более компактна и позволяет применить матричные методы анализа для оптимизации структуры алгоритма. При графовом представлении вершинами графа являются состояния машины Тьюринга, а дугами — переходы в те состояния, которые предусмотрены командой. При этом на дуге указывают считываемый символ /записываемый символы в обозреваемой ячейке и команда на перемещение головки (рис. 5.2). Граф машины Тьюринга, реализующей заданный алгоритм, часто называют граф-схемой алгоритма (ГСА). Рисунок 5.2 ― Граф-схема машины Тьюринга Пример 1 машины Тьюринга. T2:= базовая функция Сn=1 на правой полуленте: T2: qо|x + 1#®qk||#; Протокол T2. 1) qо|®q1# П; 2) q1|®q1# П; 3) q1#®q2# |Л; 4) q2 #®qk|C. Текущее Символы vt состояние # qо q1 #П — q1 q1 #П Q2 |Л q2 — q1 |C   Рисунок 5.3 ― Граф алгоритма базовой функции Сn=1   Пример 2 машины Тьюринга. T4:= базовая функция Im,n на правой полуленте: T4: qo|1x1+1 # |2x2+1 #...#|mxm+1#...#|nxn+1#®qk|xm+1#, где |i - слово на i-м месте информационной ленты, |xi+1 – число “палочек”. Чтобы найти на информационной ленте i-е слово, следует установить счетчик |m, указывающий место слова |mxm+1 в последовательности слов. T4: qo|m #|1x1+1#|2x2+1#...#|mxm+1#|nxn+1 ® qk|mxm+1. Текущее Символы vt   состояние | # )   qo q1 #П - -   q1 q1 |П q2)П -   q2 q2 #П q3)Л -   q3 - q3 #Л q4)Л   q4 q4 |Л q5 # П -   q5 q6 #П - q8 #П   q6 q6 |П - q7)П   q7 - q7 #П q2 #П   q8 - q8 #П q9 #П   q9 q9 |П q10 #П -   q10 q10 #П q11 #П -   q11 q10 #П q12 #Л -   q12 q13 |Л q12 #Л -   q13 q13 |Л q14 #П -   q14 qk |C - -     На рис. 5.4 приведен граф, реализующий базовую функцию Im,n.   Это позволит при каждом проходе вправо, отмечая один символ в слове |m, удалять очередное слово |m-1, предшествующее |mxi+1. Для организации вычисления такой функции необходимо увеличить число символов алфавита внешней памяти, что позволит уменьшить число состояний управляющего устройства и упорядочить весь процесс вычисления. Пусть Vт = {|, #, (}. Считывающая головка находится под первым символом слова счетчика |m. При подаче команды “старт” стирается первый символ слова |m и начинается перемещение головки вправо. После прочтения всех символов слова |m по команде q1#®q2) П ставится скобка, закрывающая оставшиеся символы слова |m, и головка перемещается на слово |x1+1. По команде q2| ®q2#П стираются все символы слова |1x1+1 и ставится закрывающая скобка q2#®q3)Л. Начинается перемещение считывающей головки влево за очередным символом слова |m-2.   Рисунок 5.4 ― Граф базовой функции Im,n   Так организован цикл. Затем управляющее устройство стирает второе слово, третье и т. д. пока есть символы “|” в счетчике. После стирания всех символов в счетчике по команде q5)®q8#П головка стирает закрывающую скобку, пробегает все пробелы “#”, по команде q8)®q9#П фиксирует место слова |mxm+1, пробегает все символы слова |mxm+1 и продолжает удалять все слова справа от слова |mxm+1по командам q10|®q10#П и q11|®q10#П. Если при чтении ленты в соседних ячейках будут символы “#”, то конец и головка возвращается на первый символ слова |mxm+1 по командам: q11#®q12#Л, q12#®q12#Л, q12|®q13|Л, q13|®q13|Л, q13#®q14#П и q14|®qk|C.     Пример 3 машины Тьюринга. T6 копирование m раз слово |x+1 на правой полуленте: T6: qо|x+1# ® qk|1x +1#|2x+1 #..#|mx+1#. Для того, чтобы выполнить m копий, необходимо занести на информационную ленту счетчик., т.е. изменить начальную конфигурацию машины, определяющий число копий |m: T6: qо|m #|x+1# ® qk|1x +1 # |2x+1 #..#|mx+1#. При каждом проходе вправо в слове |m удаляется один символ, затем выполняется обычное копирование слова |x+1, маркируя каждый переносимый символ командой q2|®q3(П и закрывая слово |x+1 командой q3#®q4(П. После переноса всех символов слова |x +1 головка возвращается на самый левый символ слова |m и стирает его. Пусть Vт.={|, #, (,)}.           Текущее Символы vt состояние | # ( ) qо q1 #П - - q8 #П q1 q1 |П q2)П - q2)П q2 q3 (П - q2)П q2)П q3 q3 |П q4)П - q4)П q4 q4 |П q5 |Л - - q5 q5 |Л - q6 (П q5)Л q6 q3 (П - - q7)Л q7 q7 |Л q7 #П q7 (Л q7)Л q8 q9 |Л - q8 (П q8)П q9 qk |C q9 #П q9 |Л q9 #Л   Рисунок 5.5 ― Граф алгоритма тиражирования слова |x+1   Процесс продолжается до тех пор, пока не будут удалены все символы в слове 1m. После этого следует удалить все вспомогательные символы "("и")" и поставить головку машины в начало первого слова |x+1. Множество команд представлены таблицей, а работа машины показана графом на рис. 5.5.   2 Примеры задач 1. Вычисление произведения двух чисел в унарном коде. 2. Выделить типовые машины Тьюринга, реализующие элементарные служебные и базовые функции. qн|x # |y # |z # |s # |t Þ qk|(y¸z) # |(x+t) Для каждой машины Тьюринга составить таблицу поведения и нарисовать граф. Усеченное вычитание» выполнить для x>y>z>s>t и x<y<z<s<t.   3 Задание Для выбранной в соответствии с вариантом задания задачи (две части): 1) Разработать протокол нормального алгоритма Маркова. 2) Разработать граф-схему нормального алгоритма Маркова. 3) Разработать протокол, таблицу переходов и граф состояний машины Тьюринга с правой полулентой. 4) Отладить протокол с помощью эмулятора машины Тьюринга. 5) Сделать выводы.   4 Содержание отчета 1) Условие задачи в соответствии с вариантом. 2) Определение понятия «Нормальный алгоритм Маркова». 3) Протокол нормального алгоритма Маркова, решающего задачу. 4) Граф-схема нормального алгоритма Маркова, решающего задачу. 5) Математическая модель машины Тьюринга. 6) Протокол машины Тьюринга, решающей задачу. 7) Таблица переходов машины Тьюринга, решающей задачу. 8) Граф состояний машины Тьюринга, решающей задачу. 9) Результаты отладки машины Тьюринга на эмуляторе. 10) Анализ результатов и выводы.   5 Варианты задания Ниже даны варианты задания, состоящего из двух частей. Первая часть – условие задачи, которая должна быть решена нормальным алгоритмом Маркова. Вторая часть – условие задачи, которая должна быть решена машиной Тьюринга.   Первая часть задания. 1. A = {f,h,p}. В слове P заменить все пары ph на f. 2. A = {f,h,p}. В слове P заменить на f только первую пару ph, если такая есть. 3. A = {a,b,c}. Приписать слово bac слева к слову P. 4. A = {a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы. 5. A={a,b,c}. Заменить