Какое утверждение верно для класса функций скорости роста сложности алгоритма, сложность которых растет с той же скоростью, что и данная функция?

A) функция  принадлежит этому классу, если при всех значениях аргумента , больших некоторого порога , значение  для некоторого положительного числа с;

B) функция g принадлежит этому классу, если  для всех , больших некоторого порога , и для некоторой положительной константы с;

C) &этот класс представляет собой пересечение двух классов, ;

D) , если  для некоторой константы с;

E) если сложность первого алгоритма принадлежит классу О большое от сложности второго, то, значит, второй алгоритм не лучше первого решает поставленную задачу.

27. *****

Какое утверждение не верно для класса функций скорости роста сложности алгоритма, сложность которых растет медленнее, чем данная функция?

A) функция  принадлежит этому классу, если при всех значениях аргумента , больших некоторого порога , значение  для некоторого положительного числа с;

B) &функция g принадлежит этому классу, если  для всех , больших некоторого порога , и для некоторой положительной константы с;

C) если предел отношения g(n)/f(n) существует и он меньше бесконечности, то ;

D) , если  для некоторой константы с;

E) если сложность первого алгоритма принадлежит классу О большое от сложности второго, то, значит, второй алгоритм не лучше первого решает поставленную задачу.

28. *****

Математическое и программное обеспечение информационной системы это

A) взаимосвязанная совокупность средств, ме­тодов и персонала, используемых для хранения, обработки и выдачи ин­формации в интересах достижения поставленной цели

B) любой объект, который одновременно рассматривается и как единое целое, и как объединенная в интересах достижения поставленных целей совокуп­ность разнородных элементов

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

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

E) &совокупность математических методов, моделей, алгоритмов и программ для реализации целей и задач информационной системы, а также нормального функционирования комплекса технических средств

29. *****

Энтропия события определяется по формуле

A) & , где  вероятность i -го исхода события

B) , заданная длина и глубина числа N

C) , где  и  — начальная (до получения информации) и конечная (после получения информации) вероятности достижения цели

D) , где m (i) функция меры содержательностисобытия i

E) , где К количествовозможных исходов опыта

30. *****

 

Задания для текущего, рубежного и промежуточного контроля

ВАРИАНТ 1

1. В корзине лежат белые и черные шары. Среди них 75 черных шаров. Сообщение о том, что из корзины достали белый шар, несет 2 бита информации. Сколько всего в корзине шаров?

2. Построить машину Поста, осуществляющую левый сдвиг головки МП (с конца массива меток на начало).

3. Перевести число из десятичной системы в указанную 55555.555®q=11

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 2

1. Растровый графический файл содержит черно-белое изображение (без градаций серого) размером 200х135 точек. Какой объем памяти требуется для хранения этого файла?

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁+++++ (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 798.65® q = 7

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 3

1. Растровый файл, содержащий черно-белый (без оттенков серого) квадратный рисунок, имеет объем 400 байт. Рассчитайте размер стороны квадрата (в пикселях).

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₀_11х11_

Набор правил	Набор правил
q0_→q0R	q4a→q4aR
q01→q0R	q4=→q4=R
q0×→q1×R	q41→q41R
q11→q2aR	q4_→q51R
q21→q21L	q5_→q2*L
q2a→q2aL	q6a→q61R
q2=→q2=L	q6×→q7×R
q2×→q3×L	q7a→q7aR
q31 → q4aR	q71→q2aR
q3a→q3aL	q7=→q8=L
q3_→q6_R	q8a→q81L
q4×→q4×R	q8×→q9S

3. Перевести число из десятичной системы в указанную 6345.21® q =12

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 4

1. Объем изображения, размером 40х50 пикселей, составляет 4000 байт. Сколько цветов изображение использует?

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁370, где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 75.23®q = 4

 

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 5

1. Известно, что видеопамять компьютера имеет объем 512 Кбайт. Разрешающая способность экрана 640 на 200 пикселей. Сколько страниц экрана одновременно разместится в видеопамяти при палитре 16 цветов?

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁) (() ((), где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 321.45®q = 8

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 6

1. Подсчитать, сколько места будет занимать одна минута цифрового звука на жестком диске или любом другом цифровом носителе, записанного с частотой 42.7 кГц и разрядностью 8 бит.

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁ bbbaab, где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 548.6®q = 12

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 7

1. Подсчитать, сколько места будет занимать одна минута цифрового звука на жестком диске или любом другом цифровом носителе, записанного с частотой 15 кГц и разрядностью 32 бит

2. Построить машину Поста, осуществляющую транспозицию (перестановку X меток и Y меток местами)

3. Перевести число из десятичной системы в указанную 65.6 ® q = 9

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 8

1. Подсчитать, сколько места будет занимать одна минута цифрового звука на жестком диске или любом другом цифровом носителе, записанного с частотой 29 кГц и разрядностью 16 бит.

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁25, где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 8065.21®q=13

 

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 9

1. Какой объем данных имеет моноаудиофайл, длительность звучания которого 1 секунда, при среднем качестве звука (32 бит, 19.5 кГц)?

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁15, где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 3987.5®q=11

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 10

1. Рассчитайте объем стереоаудиофайла длительностью 15 секунд при 20-битном кодировании и частоте дискредитации 38.4 кГц.

2. Построить машину Поста, осуществляющую перенос первой метки в конец массива меток.

3. Перевести число из десятичной системы в указанную 567.42®q=15

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 11

1. Определите количество уровней звукового сигнала при использовании 8-битных звуковых карт.

2. Построить машину Поста, осуществляющую удвоение массива меток.

3. Перевести число из десятичной системы в указанную 7358.3®q=14

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 12

1. Сообщение, записанное буквами из 64-х символьного алфавита, содержит 57 символов. Какой объем информации оно несет?

1. В произвольном месте ленты записано число. Написать программу увеличения числа на 4 для машины Поста.
2. Перевести число из десятичной системы в указанную 4502.625®q=16

 

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 13

1. Племя Мульти имеет 16-х символьный алфавит. Племя Пульти использует 32-х символьный алфавит. Вожди племен обменялись письмами. Письмо племени, Мульти содержало 80 символов, а письмо племени Пульти — 70 символов. Сравните объемы информации, содержащейся в письмах.

2. Построить машину Поста, осуществляющую правый сдвиг головки МП (с начала массива меток на конец).

3. Перевести число из десятичной системы в указанную 658.7® q = 6

--------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 14

1. Информационное сообщение объемом 1,5 Кбайта содержит 3072 символа. Сколько символов содержит алфавит, при по­мощи которого было записано это сообщение?

2. В произвольном месте ленты записано число. Написать программу увеличения числа на 5 для машины Поста.

3. Перевести число из десятичной системы в указанную 484.15®q=11

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 15

1. Объем сообщения, содержащего 2048 символов, составил 1/512 часть Мбайта. Каков размер алфавита, с помощью которого записано сообщение?

2. В произвольном месте ленты записано число, не меньше 4. Написать программу уменьшения числа на 4 для машины Поста.

3. Перевести число из десятичной системы в указанную 856.04® q = 7

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 16

1. Для записи текста использовался 256-символьный алфавит. Каждая страница содержит 25 строк по 60 символов в строке. Какой объем информации содержат 6 страниц текста?

2. В произвольном месте ленты записано число, не меньше 5. Написать программу уменьшения числа на 5 для машины Поста.

3. Перевести число из десятичной системы в указанную 467.04® q = 9

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 17

1. Сообщение занимает 4 страницы по 30 строк. В каждой строке записано по 80 символов. Сколько символов в использован­ном алфавите, если все сообщение содержит 7200 байт.

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации q₁/////_///, где (a₀-пробел, H – стоп)

3. Перевести число из десятичной системы в указанную 14.6® q = 3

 

------------------------------------------------------------------------------------------------------------------------

ВАРИАНТ 18

1. Сообщение занимает 2 страницы и содержит 1/16 Кбайта ин­формации. На каждой станице записано 256 символов. Какова мощность использованного алфавита?

2. Сделать потактовое выполнение приведенной машины Тьюринга для начальной конфигурации 10-q₀7

3. Перевести число из десятичной системы в указанную 842.14® q = 5

 

 

МЕТОДИЧЕСКИЕ РАЗРАБОТКИ (РЕКОМЕНДАЦИИ)

№	Название методических разработок (рекомендации)
1.	Киселёва Е.А. Теоретические основы информатики. Методические указания к лабораторным работам для студентов специальности «5В011100 - Информатика»