Предмет: Основы теории информации

Экзаменационные билеты для итоговой аттестации

(2011-2012 учебный год)

Семестр: 10

Предмет: Основы теории информации

Специальность: 050202 «Информатика»

Группа: Т-5

Преподаватели: Гибадулина Г. В., Пучкова Е.А.

Билет № 1

1. Информатизация общества. Этапы информационного развития общества.

2. Выполните действия:

а) 1001000011, 1₍₂₎+10001101, 101₍₂₎

б) 415, 24₍₈₎+1345, 04₍₈₎

в) 1101100₍₂₎´ 101₍₂₎

г) 516₍₈₎´ 64₍₈₎.

Билет № 2

1. Черты информационного общества. Противоречия информационного общества.

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

а) 563₈ = …..₃

б) 0, 25₁₀ = …₂

Представьте в двухбайтовом формате числа:

в) 349

г) -134

Билет № 3

1. Понятие информации. Свойства информации. Виды информации. Информационные процессы.

2. Решить задачу линейного программирования:

Билет № 4

1. Кодирование информации. Кодирование и декодирование. Данные и информация. Единицы измерения информации.

2. На ленте имеется массив из n отмеченных ячеек. Указатель обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.

Билет № 5

1. Различные подходы к измерению информации. Формула Хартли. Формула Шеннона. Кодирование чисел с фиксированной запятой. Кодирование чисел с плавающей запятой.

2. Найти диаметр, радиус и центры графа.

Билет № 6

1. Системы счисления. Десятичная, двоичная, восьмеричная и шестнадцатеричная системы счисления. Перевод чисел в различные системы счисления.

2. Относительно трех участников соревнований Антонова, Борисова и Волкова были высказаны предположения, что если Волков будет в тройке победителей, то и Антонов тоже; Антонов и Волков будут или не будут в призерах соревнований одновременно; Антонов не будет призером или среди победителей будут Борисов и Волков. После соревнований оказалось, что одно из предположений ложно. Кто из спортсменов был в призерах?

Билет № 7

1. Арифметические действия в различных системах счисления.

2. Три друга – Петр, Роман и Сергей – учатся на математическом, физическом и химическом факультетах. Если Петр математик, то Сергей не физик. Если Роман не физик, то Петр - математик. Если Сергей не математик, то Роман – химик. Определите специальности каждого.

Билет № 8

1. Кодирование текста. Информационный вес символа. Разные системы цифрового кодирования текста. Код Фано. Код Хаффмана.

2. Составьте для графов всевозможные матрицы:

а)

б)

Билет № 9

1. Компьютерная графика. Виды компьютерной графики. Цветовые модели. Кодирование графической информации.
2. Двумя способами докажите, что данная формула является тавтологией ~ .

Билет № 10

1. Кодирование звуковой информации. Кодирование видеоинформации.

2. Составить нормальный алгоритм Маркова нахождения числа, на единицу меньшего данного. Число представлено в десятичной системе счисления.

Билет № 11

1. Математическая логика. Понятие. Умозаключение. Высказывание. Основные операции над высказываниями.

2. Выполните действия:

а) 10011011, 011₍₂₎+1111100001, 0011₍₂₎

б) 1364, 44₍₈₎+1040, 2₍₈₎.

в) 1001100100, 01₍₂₎-10101001, 1₍₂₎

г) 1405₍₈₎-346₍₈₎.

Билет № 12

1. Формулы алгебры высказываний, их виды. Отношение равносильности. Логическое следствие.

2. Составить блок-схемы с использованием цикла со счетчиком и цикла с предусловием для решения задачи: определить сумму чисел, кратных 7 в интервале от 1 до 1000.

Билет № 13

1. Понятие алгоритма и его основные свойства. Исполнители алгоритмов. Способы представления алгоритмов. Понятие алгоритмического языка. Блок-схемы.

2. Найти сумму чисел a = E2₁₆ и b = 110011_2. Ответ представьте в системе счисления с основанием 2, 8, 10, 16.

Билет № 14

1. Формализация понятия алгоритм. Машина Поста. Машина Тьюринга. Нормальные алгоритмы Маркова.

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

Билет № 15

1. Основные понятия и отношения теории графов. Способы представления графов.

2. а) Рассчитайте время звучания стереоаудиофайла (в минутах), если при 8-битном кодировании и частоте дискретизации 32 кГц его объем равен 0, 5 Мбайт.

б) При составлении сообщения использовали 128-символьный алфавит. Каким будет информационный объём такого сообщения, если оно содержит 5125 символов? (ответ выразите в мегабайтах).

Билет № 16

1. Модель. Моделирование. Классификации моделей. Математическая модель. Виды математических моделей. Компьютерная модель.

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

Билет № 17

1. Инструментарий компьютерного математического моделирования. Этапы компьютерного математического моделирования.

2. Составить код Фано для кодирования фразы «хохлатые хохлушки хохотом хохотали». Каков процент сжатия по отношению к равномерному кодированию?

Билет № 18

1. Предикаты, их классификация. Отношения между предикатами. Операции кванторов.

2. Составить код Хаффмана для кодирования фразы «хохлатые хохлушки хохотом хохотали». Каков процент сжатия по отношению к равномерному кодированию?

Билет № 19

1. Связные графы. Двудольные графы. Плоские графы. Деревья. Диаметр, радиус и центры графа.

2. Начальная строка была получена из обычного арифметического выражения путем удаления всех символов, кроме открывающихся и закрывающихся круглых скобок. Составьте нормальный алгоритм, который приводит эту строку к строке " ВЕРНО" либо " НЕВЕРНО" в зависимости от того, верно или неверно были расставлены скобки в исходной.

Билет № 20

1. Формализация. Основной тезис формализации. Формализация текстовой информации. Представление информации в табличной форме и форме графа.

2. Построить машину Тьюринга, вычисляющую числовую функцию , определённую на множестве N.