Предварительный вариант билета государственного экзамена по направлению 09.03.01 - «Информатика и вычислительная техника». 2018 г.

1. (3 балла) Указать, что выдаст на экран следующая программа:

2. (3 балла) Проанализировать работу программы и написать последовательность символов, выводимых на консоль.

3. (2 балла) Дан бернуллиевский источник с алфавитом K = {a, b, c, d, e, f}. Вероятности символов источника: p(a)=0.1, p(b)=0.05, p(c)=0.05, p(d)=0.05, p(e)= 0.05, p(f)=0.7. Построить код Хаффмана для данного источника и определить его избыточность R (как разницу между средней длиной кодового слова SD и энтропией H).

4. (2 балла) Для предиката p на Прологе описаны правила:
p([_,_],L,L):-!.
p([X|L1],L2,L):–p(L1,[X,X|L2],L).
Какое значение получит L после следующего обращения к этому предикату
p([2,5,6,3,4],[],L)?


5. (2 балла) Оптимальным образом расставить скобки при перемножении матриц
М1[2x5], M2[5x7], M3[7x3], М4[3x8], M5[8x4].
Какова трудоемкость умножения при оптимальной расстановке скобок?

6. (2 балла) Для шифра Шамира с параметрами P= 17, Ca= 5, Cb = 7, найти недостающие параметры и описать передачу сообщения m=6.

7. (2 балла) Построить электронную подпись RSA c параметрами P = 5, Q = 11 , D = 13 для сообщения m, значение хеш-функции которого равно 6.

8. (2 балла) Определить высоту случайного дерева поиска (СДП), построенного для последовательности данных: 15 2 1 8 10 8 11 4 3 6.

9. (1 балл) Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1):

Подробное решение билета. 2018 год.