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

1. (3 балла) Указать, что выдаст на экран следующая программа:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <conio.h>
using namespace std;
const int MAXL=40, N=5;
struct node{
 char *name;
 bool vo;
 node *next;
 node(char *_name, bool _vo):vo(_vo){
  name=new char[MAXL];
  strcpy(name,_name);
  next=NULL;
 }
 ~node(){
  delete [] name;
 }
};
Проанализировать работу программы и написать последовательность символов, выводимых на консоль.
#include <windows.h>
#include <stdio.h>

unsigned long idA, idB;

void A ()
{
MSG msg;
PeekMessage (&msg, 0, 0, 0, PM_NOREMOVE), Sleep (1);
putchar ('a');
PostThreadMessage (idB, WM_USER, 'b', 0);
putchar ('d');
PostThreadMessage (idB, WM_USER+1, 'c', 0);
GetMessage (&msg, 0, 0, 0);
putchar (msg.lParam);
}

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):
15 2 1 8 10 8 11 4 3 6.

В данном предварительном билете подробное решение заданий, которые будут на гос.экзамене.