Демонстрационный вариант заданий второго этапа по профилю «Компьютерные науки и науки о данных»

Задача 1

Сколько существует пар целых чисел a и b, таких что 19a + 14b = 1, и {|a|, |b|} < 100.

Решение

Одно из решений находится через вычисление коэффициентов линейного представления НОД(19; 14) как вычисление коэффициентов Безу:

19 = 14 ⋅ 1 + 5; 14 = 5 ⋅ 2 + 4; 5 = 4 ⋅ 1 + 1, следовательно 1 = 5 ⋅ 1 − 4 ⋅ 1 = 5 ⋅ 1 − (14 ⋅ 1 − 5 ⋅ 2) ⋅ 1 = 5 ⋅ 3 − 14 ⋅ 1 = (19 ⋅ 1 − 14 ⋅ 1) ⋅ 3 − 14 ⋅ 1 = 19 ⋅ 3 − 14 ⋅ 4.

Таким образом (3; −4) — одно из решений. Другие решения получаются добавлением (вычитанием) 14 к значению a с одновременным вычитанием (добавлением) 19 из b:

a = 3 + 14n,
b = −4 − 19n.

Решения будут удовлетворять условию при n = −5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5.

Ответ: 11.

Задача 2

Из полного графа K₁₁ на 11 вершинах удалили 45 рёбер, чтобы получить как можно больше компонент связности. Сколько компонент связности получилось?

Решение

В полном графе на 11 вершинах (11 ⋅ 10) / 2 = 55 рёбер. После удаления 45 рёбер их останется 10.

Если удалить рёбра так, чтобы остался полный граф K₅ на 5 вершинах, в котором 10 рёбер, то оставшиеся 6 вершин будут другими компонентами связности.

Ответ: 7.

Задача 3

В данной задаче символом ⊕ обозначено исключающее ИЛИ (XOR), а чертой сверху — булева инверсия. Рассмотрим выражение x₁ ⊕ x₂ ⊕ x₃ ⊕ … ⊕ x₂₀, в котором каждый из символов x_i заменяется равновероятно и независимо на один из символов true, false, a, a, b, b. Какова вероятность того, что полученное выражение окажется тождественно равно true (независимо от значений a и b)?

Решение

Заметим, что модель равносильна такой двухэтапной процедуре:

• ЭТАП 1. В исходном выражении случайным образом каждый x_i можно заменить на false, a или b, получив выражение, тождественно равное одному из следующих четырёх: {false, a, b, a ⊕ b}. Это вытекает из основных свойств связки XOR: false ⊕ p = p и p ⊕ p = false.
• ЭТАП 2. В выражении, полученном на предыдущем этапе, над каждым из двадцати “слагаемых” независимо с вероятностью 1/2 поставить инверсию. В результате этого второго шага значение всего выражения либо останется неизменным, либо инвертируется, при этом вероятность получить неинвертированное и инвертированное выражение совпадают.

Из сказанного следует, что ответ равен половине от вероятности получить false на первом этапе выбора. Эта вероятность, в свою очередь, равна вероятности заменить среди x₁, …, x₂₀ чётное количество символов на a и чётное на b. Удобно посчитать это по формуле полной вероятности, в зависимости от того, сколько x_i было заменено на false. Пусть ровно k таких x_i. Нас интересуют только чётные k.

Итоговый ответ: 1/8 ⋅ (1 + (1/3)¹⁹).

Ответ: 1/8 ⋅ (1 + (1/3)¹⁹).

Задача 4

Отметьте недостатки полностью ассоциативного кэша:

1. Высокие затраты при промахе
2. Подходит не для всех видов оперативной памяти
3. Высокий процент промахов
4. Сложность реализации

Задача 5

На вход программе подаются строки вида: Марка_авто, модель_авто, год_выпуска, пробег, которые заканчиваются словом «Конец». Напишите программу, которая выводит ответ на вопрос: Автомобили каких марок имеют пробег больше 100000?

Решение

data = []
res = set()
s = input()
while s != 'Конец':
    data.append(s.split(','))
    s = input()

for i in data:
    if int(i[3]) > 100000:
        res.add(i[0])
print('n'.join(sorted(list(res))))

Задача 6

Напишите на языке С++ шаблонный класс MyVector, представляющий собой динамически расширяющийся массив. Деструктор класса должен освобождать память, занимаемую массивом.

Решение

#include <iostream>
#include <cstring>

template <class T>
class MyVector{
   const int delta = 3;
   T *arr;
   size_t capacity;
   size_t size;

   void expansion(){
       capacity+=delta;
       T *tmp = new T[capacity];
       std::memcpy(tmp, arr, sizeof(T) * size);
       delete[]arr;
       arr = tmp;
   }

public:
   MyVector(){ size = 0; capacity = delta; arr = new T[capacity]; }
   ~MyVector(){ delete[] arr; }
   void pushBack(T elem){ if(size >= capacity) expansion(); arr[size] = elem; size++; }
   void pushFront(T elem){ insert(elem, 0); }
   int count(){ return size; }
   void print(){ for(int i=0; i<size; i++){ std::cout<<arr[i]<<' '; } std::cout<<std::endl; }
};

Задача 7

Что такое видеостраница?

• Веб-страница, на которой воспроизводится видео
• Память, необходимая для хранения полного образа экрана
• Память, в которой хранится видеофайл

Задача 8

IP-адрес хоста 192.168.15.158. Маска подсети 255.255.255.224. Определите адрес сети.

Решение

На заданный IP-адрес 192.168.15.158 необходимо наложить маску 255.255.255.224. Для этого необходимо записать адрес и маску в двоичном виде и совершить операцию И:

11000000.10101000.00001111.10011110
11111111.11111111.11111111.11100000
11000000.10101000.00001111.10000000 = 192.168.15.128

Ответ: 192.168.15.128

Задача 9

В базе данных хранится информация о сотрудниках. Известно количество записей:

1. Возраст сотрудника > 40 в отделе логистики – 3 записи.
2. Мужчин в возрасте >30 в отделе логистики – 10 записей.
3. Женщин в возрасте >30 в отделе логистики и маркетинга – 5 записей.
4. Женщин в возрасте >30 в отделе маркетинга – 2 записи.

Сколько сотрудников в возрасте от 30 до 40 работает в отделе логистики?

Решение

Из п. 3 и п. 4 следует, что женщин в возрасте >30 в отделе логистики 3. Мужчин в возрасте >30 в отделе логистики – 10. Итого в отделе логистики работает 13 человек в возрасте >30. Из них 3 человека в возрасте >40. Следовательно, сотрудников отдела логистики в возрасте от 30 до 40 – 10.

Ответ: 10.

Задача 10

Вам даны правила фильтрации межсетевого экрана. Определите, есть ли в них противоречия (аномалии).

Rule	Protocol	Source IP	Source port	Destination IP	Destination port	Action
1	*	10.19.55.124	*	10.12.32.21–10.12.32.22	1–80	Allow
2	TCP	172.19.55.*	*	10.12.32.21	80	Allow
3	TCP	192.168.5.64	*	10.12.32.23	23	Allow
4	TCP	172.19.55.121	*	10.12.32.21	80	Allow

Ответ: избыточность правила 4 (относительно 2).

Задача 11

Для входа в помещение используется 4-х значный пин-код — ХХХХ. Известно, что пин-код является простым числом, при этом первая цифра равна последней цифре. Задержка между попытками входа в систему равна 1 секунде. За какое максимальное количество времени (в секундах) можно гарантированно получить пин-код?

Ответ: 117 с.

Задача 12

Была получена дейтаграмма от сервера на порту 2021: e0 ea eb 3b e7 18 a8 5f a2 41 a3 40 a8 5d b4 50 d5 3f d5 3e c6 0a a6. Определите, что послал сервер.

Решение

Порт отправителя 2021 (07e5 в hex). Ключ: e0ea XOR 07e5 = e70f. Применяя ключ к данным, получаем расшифровку.

Ответ: OPENDOORS_2021!

Задача 13

Имеется набор данных с характеристиками человека, при которых рекомендуется использовать разные типы линз. Какая модель машинного обучения должна быть построена?

• regression function
• cluster model
• decision tree
• association rules

Задача 14

Имеется набор данных показаний акселератора и гироскопа автомобиля. Какой тип нейронной сети лучше использовать для классификации состояний автомобиля?

• a. полносвязанные нейронные сети
• b. рекуррентные нейронные сети
• c. самоорганизующиеся карты Кахонена
• d. обратные нейронные сети
• e. прямые нейронные сети

Задача 15

Вычислить с помощью алгоритма Naïve Bayes нормализованную вероятность проведения игры для условий: Weather = Sun и Temperature = Hot.

Решение

P(Play = No | Sun, Hot) = 0,2; P(Play = Yes | Sun, Hot) = 0,05. Нормализация: 0,05 / (0,05 + 0,2) = 0,2.

Ответ: 20%.