Контрольная работа

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

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

«Тобольская государственная социально-педагогическая академия

им. »

Кафедра информатики, ТиМОИ

КОНТРОЛЬНАЯ РАБОТА

по дисциплине «Теоретические основы информатики»

направление 050200.62 – Физико-математическое образование (бакалавр), профиль подготовки «Информатика»

физико-математический факультет

отделение заочного обучения

III курс, 6 семестр

2010-2011 уч. год

Составил: ст. преподаватель

кафедры информатики, ТиМОИ

Тобольск – 2011

Вариант-1

1. Выполнить перевод чисел из одной системы счисления в другую:

1)  1101010010102 → Х8

2)  1001011001,012 → Х10

3)  594810 → Х16

2. Получить двоичный код числа Z = 8210 и преобразовать его в код Грея ZG.

3. Преобразовать код Грея ZG = 10101000101100 в двоичный код.

4. Используя методику Шеннона-Фано провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,09; p(z2) = 0,15; p(z3) = 0,24; p(z4) = 0,01; p(z5) = 0,26; p(z6) = 0,07; p(z7) = 0,16; p(z8) = 0,02.

Вычислить среднее число разрядов на знак.

5. Используя алгоритм Хаффмена провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,09; p(z2) = 0,15; p(z3) = 0,24; p(z4) = 0,01; p(z5) = 0,26; p(z6) = 0,07; p(z7) = 0,16; p(z8) = 0,02.

Вычислить среднее число разрядов на знак.

6. Получить двоичный код числа Z = 3710 и определить для него код Хемминга.

7. Определить значение числа, переданного с использованием кода Хемминга 1010001011010, если при передаче имела место однократная ошибка.

8. Построить таблицу переходов и граф переходов для машины Тьюринга, заданной программой:

q1 a → q2 R, q1 b→ R, q1 0→ q6 L, q2 a → q3 c R, q2 b → q4 c R, q3 a → a R, q3 b → q4 a R, q3 0 → q5 a L, q4 a → q3 b R, q4 b → b R, q4 0 → q5 b L, q5 b → L, q5 c → q1 a R, q6 a → L, q6 b → L, q6 c → a L, q6 0 → q0 R.

Применить машину Тьюринга из задания 1 к следующим начальным конфигурациям и определить заключительные конфигурации:

A)  bbaba

B)  abbbaab

C)  abaaba

9.  Составить программу машины Тьюринга, вычисляющей функцию

и проиллюстрировать ее работу.

10. Докажите, что одноместная функция f(x) принадлежит классу примитивно рекурсивных функций: f(x) = x

11. Докажите, что двухместная функция f(x, y) принадлежит классу примитивно рекурсивных функций: f(x, y) = x∙(y + 1)

12. Построить нормальный алгоритм Маркова для вычисления функции f(x) = x – 1 в двоичной системе счисления.

Вариант-2

1. Выполнить перевод чисел из одной системы счисления в другую:

1)  5А4D716 → Х8

2)  465710 → Х8

3)  1101001101,0112 → Х10

2. Получить двоичный код числа Z = 7410 и преобразовать его в код Грея ZG.

3. Преобразовать код Грея ZG = 00110110010101101 в двоичный код.

4. Используя методику Шеннона-Фано провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,12; p(z2) = 0,01; p(z3) = 0,08; p(z4) = 0,19; p(z5) = 0,23; p(z6) = 0,02; p(z7) = 0,31; p(z8) = 0,04.

Вычислить среднее число разрядов на знак.

5. Используя алгоритм Хаффмена провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,12; p(z2) = 0,01; p(z3) = 0,08; p(z4) = 0,19; p(z5) = 0,23; p(z6) = 0,02; p(z7) = 0,31; p(z8) = 0,04.

Вычислить среднее число разрядов на знак.

6. Получить двоичный код числа Z = 4610 и определить для него код Хемминга.

7. Определить значение числа, переданного с использованием кода Хемминга 1110010100110010, если при передаче имела место однократная ошибка.

8. Построить таблицу переходов и граф переходов для машины Тьюринга, заданной программой:

q1 0 → q5 R, q2 a→ R, q2 b→ R, q2 0 → q3 1 R, q2 1 → R, q3 a → L, q3 b → L, q3 c → q5 R, q3 0 → q0, q3 1 → L, q4 a → 0 L, q4 b → 0 L, q4 c → 0 L, q4 0 → R, q4 1 → q0 L, q5 a → q2 c R, q5 b → R, q5 0 → q3 L, q5 1 → q4 L.

Применить машину Тьюринга из задания 1 к следующим начальным конфигурациям и определить заключительные конфигурации:

A)  0aaaaa

B)  0aaababa

C)  0bbbbb

9. Составить программу машины Тьюринга, вычисляющей функцию

и проиллюстрировать ее работу.

10. Докажите, что одноместная функция f(x) принадлежит классу примитивно рекурсивных функций: f(x) = x + 5

11. Докажите, что двухместная функция f(x, y) принадлежит классу примитивно рекурсивных функций: f(x, y) = x + y + 2

12. Построить нормальный алгоритм Маркова для вычисления функции f(x) = x – 1 в восьмеричной системе счисления.

Вариант-3

1. Выполнить перевод чисел из одной системы счисления в другую:

1)  320810 → Х2

2)  100011010,112 → Х10

3)  615238 → Х16

2. Получить двоичный код числа Z = 9110 и преобразовать его в код Грея ZG.

3. Преобразовать код Грея ZG = 01001101100100 в двоичный код.

4. Используя методику Шеннона-Фано провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,05; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,15; p(z5) = 0,22; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,10.

Вычислить среднее число разрядов на знак.

5. Используя алгоритм Хаффмена провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,05; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,15; p(z5) = 0,22; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,10.

Вычислить среднее число разрядов на знак.

6. Получить двоичный код числа Z = 2910 и определить для него код Хемминга.

7. Определить значение числа, переданного с использованием кода Хемминга 110100110011101, если при передаче имела место однократная ошибка.

8. Построить таблицу переходов и граф переходов для машины Тьюринга, заданной программой:

q1 a → q2 R, q1 b→ R, q1 0→ q6 L, q2 a → q3 c R, q2 b → q4 c R, q3 a → a R, q3 b → q4 a R, q3 0 → q5 a L, q4 a → q3 b R, q4 b → b R, q4 0 → q5 b L, q5 b → L, q5 c → q1 a R, q6 a → L, q6 b → L, q6 c → a L, q6 0 → q0 R.

Применить машину Тьюринга из задания 1 к следующим начальным конфигурациям и определить заключительные конфигурации:

A)  baaab

B)  aababbb

C)  bbaba

9. Составить программу машины Тьюринга, вычисляющей функцию

и проиллюстрировать ее работу.

10. Докажите, что одноместная функция f(x) принадлежит классу примитивно рекурсивных функций: f(x) = 2∙x + 1

11. Докажите, что двухместная функция f(x, y) принадлежит классу примитивно рекурсивных функций: f(x, y) = x + 4∙y

12. Построить нормальный алгоритм Маркова для вычисления функции f(x) = x – 1 в пятеричной системе счисления.

Вариант-4

1. Выполнить перевод чисел из одной системы счисления в другую:

1)  1001110100,1012 → Х10

2)  260738 → Х2

3)  410310 → Х16

2. Получить двоичный код числа Z = 8510 и преобразовать его в код Грея ZG.

3. Преобразовать код Грея ZG = 10001011001010 в двоичный код.

4. Используя методику Шеннона-Фано провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,15; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,14; p(z5) = 0,12; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,11.

Вычислить среднее число разрядов на знак.

5. Используя алгоритм Хаффмена провести эффективное кодирование группы из восьми элементов, имеющих следующие характеристики:

p(z1) = 0,15; p(z2) = 0,13; p(z3) = 0,20; p(z4) = 0,14; p(z5) = 0,12; p(z6) = 0,07; p(z7) = 0,08; p(z8) = 0,11.

Вычислить среднее число разрядов на знак.

6. Получить двоичный код числа Z = 5310 и определить для него код Хемминга.

7. Определить значение числа, переданного с использованием кода Хемминга 01101001100110, если при передаче имела место однократная ошибка.

8. Построить таблицу переходов и граф переходов для машины Тьюринга, заданной программой:

q1 0 → q5 R, q2 a→ R, q2 b→ R, q2 0 → q3 1 R, q2 1 → R, q3 a → L, q3 b → L, q3 c → q5 R, q3 0 → q0, q3 1 → L, q4 a → 0 L, q4 b → 0 L, q4 c → 0 L, q4 0 → R, q4 1 → q0 L, q5 a → q2 c R, q5 b → R, q5 0 → q3 L, q5 1 → q4 L.

Применить машину Тьюринга из задания 1 к следующим начальным конфигурациям и определить заключительные конфигурации:

A)  0abbaaba

B)  0bbabaab

C)  0aaaaaaab

9. Составить программу машины Тьюринга, вычисляющей функцию

и проиллюстрировать ее работу.

10. Докажите, что одноместная функция f(x) принадлежит классу примитивно рекурсивных функций: f(x) = 4∙x

11. Докажите, что двухместная функция f(x, y) принадлежит классу примитивно рекурсивных функций: f(x, y) = (x + 1)∙y

12. Построить нормальный алгоритм Маркова для вычисления функции f(x) = x – 1 в десятичной системе счисления.