Контрольная работа по ТОИ

  • 11 дек. 2013 г.
  • 1441 Слова
Государственное образовательное учреждение
высшего профессионального образования
«Тобольская государственная социально-педагогическая академия
им. Д.И. Менделеева»



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






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

по дисциплине «Теоретические основы информатики»
направление 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. Составить программу машины Тьюринга, вычисляющей функцию [pic]
и проиллюстрировать ее работу.

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,...
tracking img