Билет ГОС экзамена (09.03.01 «Информатика и вычислительная техника», профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем») (2017 год)

Вариант 3Д171808

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

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

#include <windows.h>
#include <stdio.h>

unsigned long idA, idB;
void A (char c)
(
HANDLE chan;
char str [2];
unsigned long n;
chan = CreateNamedPipe (“\\\\.\\pipe\\ppp”, PIPE ACCESS_DUPLEX,
 PIPE_TYPE_MESSAGE | PIPE_READMODE_MESSAGE, 1, 4, 4, 0, 0);
Sleep (100);
TransactNamedPipe (chan, &c, 1, str, 2, &n, 0);
putchar (str[0]), putchar (str[1]);
)

void B (char c)
(
HANDLE chan;
char str [2] = (‘a’, ‘b’);
unsigned long n;
chan = CreateFile (“\\\\.\\pipe\\ppp”, GENERIC_READ | GENERIC_ERITE,
0, 0, OPEN_EXISTING, 0, 0);
ReadFile (chan, str, 1, &n, 0);
putchar (str[0]), putchar (str[1]);
str[1] = c;
WriteFile (chan, str, 2, &n, 0);
)

int main ()
(
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) A, (LPVOID) ‘c’, 0, &idA);
CreateThread (0, 0, (LPTHREAD_START_ROUTINE) B, (LPVOID) ‘d’, 0, &idB);
Sleep (1000);
return 0;
)


2. (2 балла). Дан бернулиевский источник с алфавитом K = {a, b, c, d, e, f}. Вероятности символов источника:
p(a)=0.1 p(b)=0.1 p(c)=0.1 p(d)=0.1 p(e)=0.1 p(f)=0.5.
Построить код Хаффмана для данного источника и определить его избыточность R (как разницу между средней длиной кодового слова SD и энтропией H).
3. (2 балла). Для предиката p на Прологе описаны правила:
p(_,[],[]):-!.
p(X,[X|L],L):-!.
p(X, [_|L],Z):-p(X,L,Z).
Какое значение получит Z после следующего обращения к этому предикату p(2, [3,6,2,7,9,1],Z)?

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

5. (2 балла). Для шифра Эль-Гамаля с параметрами p=31, g=3, cB=10, k=5 найти недостающие параметры и описать процесс передачи сообщения m=15 пользователю B.

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

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

8. (1 балл). Построить индексный массив, упорядочивающий данные по возрастанию (нумерация в массиве начинается с 1):
17 18 2 6 10 15 1 2 10 16

Полностью решенный билет ГОС экзамена (декабрь 2017).
Решения расписаны подробно.
Набрали максимальное количество баллов (16 баллов), оценка "отлично".
В архиве сами задания + решение каждого задания в отдельном файле.