Компьютерный ЕГЭ по информатике (КЕГЭ ФИПИ) — Кодирование, логика, сети, динамика и теория игр

Алгоритмические модели и математический аппарат компьютерного ЕГЭ по информатике ФИПИ (27 заданий за 235 минут, 29 первичных баллов): формула Хартли и условие Фано, системы счисления, алгебра логики, маски подсетей, рекурсия, динамическое программирование и теория игр.

Category
ЕГЭ Профильная Математика, Информатика (КЕГЭ), Физика и Обществознание, Аттестация ФСФР / ЦБ РФ (Базовый и 1.0–5.0), Налоговый Консультант и ПДД ГИБДД
Level
intermediate
Languages
ru → ru
Cards
32
Markdown
Компьютерный ЕГЭ по информатике (КЕГЭ ФИПИ) — Кодирование, логика, сети, динамика и теория игр (.md)

Flashcards (32)

#Front (Term / Question)Back (Definition / Answer)ExampleMultiple-Choice Options
1Какой приём используется для нахождения наименьшей или наибольшей длины отрезка $A$, при котором логическая формула с отрезками истинна для любого $x$?Раскрывают импликацию в дизъюнкцию и находят множество точек $x$, где часть без $A$ ложна: отрезок $A$ обязан перекрыть эту область.
2Как определить чётность числа и остаток от деления на $q^k$ непосредственно по его записи в позиционной системе счисления с основанием $q$?Остаток по модулю $q^k$ дают $k$ младших цифр; чётность при чётном $q$ зависит от последней цифры, при нечётном $q$ — от суммы цифр.
3Как в многопроцессорной задаче о параллельном выполнении зависимых процессов (задание 22 КЕГЭ) вычисляется время завершения зависимого процесса $B$?Процесс $B$ стартует сразу по завершении самого позднего из его предшественников: $T(B) = \max T(A_k) + t(B)$.
4Как по количеству единиц и нулей в строках и столбцах однозначно сопоставить переменные частично заполненной таблице истинности в задании 2 КЕГЭ?Генерируют все наборы с нужным значением функции и проверяют все перестановки переменных на точное совпадение с фрагментом таблицы.
5В чём состоит ловушка побайтового округления при расчёте памяти для хранения $M$ серийных идентификаторов в задании 11 КЕГЭ?Сначала битовый объём одного идентификатора округляется вверх до целого числа байт, и только затем умножается на количество $M$.
6Чему равно общее количество адресов в подсети и число адресов для назначения компьютерам, если двоичная запись маски подсети содержит $n$ единиц?В маске остаётся $(32 - n)$ нулей для номера узла: всего в сети $2^{32 - n}$ адресов, а рабочим узлам доступно $2^{32 - n} - 2$ адреса.
7Как с помощью префиксных сумм за линейное время $O(n)$ найти непрерывный подотрезок максимальной суммы, кратной числу $k$, в задании 27 КЕГЭ?Для каждого остатка $r$ по модулю $k$ хранят минимальную прошлую префиксную сумму с тем же остатком $r$ и вычитают её из текущей суммы.
8Сколько цифр $(q - 1)$ и нулей содержит запись разности $q^n - q^m$ (при целых $n > m \ge 0$) в позиционной системе счисления с основанием $q$?В системе с основанием $q$ запись числа $q^n - q^m$ состоит ровно из $(n - m)$ старших цифр $(q - 1)$ и $m$ младших нулей.
9Как вычисляется информационный объём несжатого звукового файла длительностью $t$ секунд при частоте дискретизации $f$ герц, разрешении $i$ бит и $k$ каналах?Объём аудиозаписи равен $I = k \cdot f \cdot i \cdot t$ бит (моно — $k = 1$, стерео — $k = 2$, квадрозапись — $k = 4$).
10Как преобразуется логическая импликация $A \to B$ и как формулируются два закона де Моргана для отрицания конъюнкции и дизъюнкции?$A \to B \equiv \neg A \vee B$; де Морган: $\neg(A \wedge B) \equiv \neg A \vee \neg B$ и $\neg(A \vee B) \equiv \neg A \wedge \neg B$.
11Какое рекуррентное соотношение динамического программирования решает задачу о сборе роботом максимальной суммы монет на таблице при шагах вправо и вниз?В каждой клетке $S_{i,j} = A_{i,j} + \max(S_{i-1,j},\, S_{i,j-1})$, причём переход через перегороженную стеной границу запрещается.
12Как переводится развёрнутая запись числа $\overline{a_{k} a_{k-1} \dots a_1 a_0}_q$ из системы счисления с основанием $q$ в десятичную систему?Значение равно сумме произведений цифр на степени основания $\sum a_j \cdot q^j$, причём каждая цифра удовлетворяет $0 \le a_j < q$.
13По какому ключу необходимо отсортировать отрезки заявок в классической жадной задаче выбора максимального числа непересекающихся мероприятий (задание 26)?Заявки сортируют по неубыванию времени окончания и последовательно берут каждую заявку, начало которой не меньше конца предыдущей.
14Почему прямое рекурсивное вычисление $F(n)$ при огромных $n$ в задании 16 КЕГЭ приводит к переполнению стека и как его устранить?Глубокая рекурсия переполняет стек вызовов; её заменяют итеративным циклом снизу вверх, кэшированием значений или упрощением формулы.
15Какова официальная структура, длительность и распределение 29 первичных баллов компьютерного ЕГЭ по информатике (КЕГЭ ФИПИ)?Выполняется полностью на компьютере за 235 минут и включает 27 заданий: задания 1–25 дают по 1 баллу, задания 26 и 27 — по 2 балла.
16По какому правилу подсчитывается количество допустимых кодовых слов длины $m$ с ограничениями на соседние символы в задании 8 КЕГЭ?По комбинаторному правилу произведения либо перебором размещений и перестановок с отсевом запрещённых соседних сочетаний символов.
17Как в задаче об упаковке или конференц-зале (задание 26 КЕГЭ) максимизировать размер последнего выбранного элемента при сохранении максимального числа элементов?Жадным алгоритмом находят наибольшее число элементов $M$, затем заменяют последний выбранный элемент максимально возможным подходящим.
18В чём состоит метод «двух указателей» для поиска самой длинной подстроки с не более чем $k$ вхождениями заданного символа в задании 24 КЕГЭ?Правый указатель расширяет окно, а при превышении счётчика над $k$ левый сдвигается вправо до восстановления условия за $O(n)$.
19По какой формуле рассчитывается информационный объём несжатого растрового изображения размером $X \times Y$ пикселей с палитрой до $N$ цветов?Глубина цвета $i$ определяется из неравенства $2^i \ge N$, а полный информационный объём изображения равен $I = X \cdot Y \cdot i$ бит.
20Что проверяет выражение с поразрядной конъюнкцией $(x \,\&\, m = 0) \to \dots$ для неотрицательных целых чисел в задании 15 КЕГЭ?Условие $x \,\&\, m = 0$ означает, что во всех двоичных разрядах, где в битовой маске $m$ стоят единицы, у числа $x$ стоят нули.
21Как сопоставить пункты графа дорог с номерами строк весовой таблицы в задании 1 КЕГЭ при наличии симметрии графа?Сопоставляют степени вершин и набор степеней их соседей, а при зеркальной симметрии графа проверяют оба изоморфных варианта нумерации.
22Как записывается формула Хартли для равномерного кодирования алфавита мощности $N$ и как найти информационный объём сообщения из $K$ символов?Разрядность символа равна наименьшему целому $i$ с условием $2^i \ge N$, а информационный объём текста равен $I = K \cdot i$ бит.
23Когда истинны логическая эквивалентность $A \equiv B$ и строгая дизъюнкция (сложение по модулю два) $A \oplus B$ в таблицах истинности?Эквивалентность $A \equiv B$ истинна при равенстве операндов, а строгая дизъюнкция $A \oplus B$ истинна при разных значениях.
24Как за время $O(\sqrt{x})$ найти все парные натуральные делители большого числа $x$ при проверке масок и простых множителей в задании 25 КЕГЭ?Перебирают делители $d$ до $\sqrt{x}$: каждое деление нацело даёт пару делителей $d$ и $x/d$ (при $d^2 = x$ делитель берут один раз).
25Как формулируется прямое условие Фано и зачем при построении двоичного дерева кодов проверяют наличие свободной ветви для остальных букв алфавита?Ни одно кодовое слово не служит началом другого; если в алфавите есть ещё буквы, в двоичном дереве обязана остаться свободная ветвь.
26Какие два специальных адреса внутри любой подсети зарезервированы стандартом и не могут назначаться отдельным рабочим станциям?Адрес самой сети (все разряды номера узла равны $0$) и широковещательный адрес подсети (все разряды номера узла заполнены единицами).
27Как формально определяются выигрышная за 1 ход ($W_1$), проигрышная за 1 ход ($L_1$) и выигрышная за 2 хода ($W_2$) позиции в теории игр (задания 19–21)?Из $W_1$ есть ход в конец игры; из $L_1$ все ходы ведут в $W_1$; из $W_2$ есть хотя бы один ход в проигрышную позицию $L_1$.
28Чем относительная, абсолютная и смешанная адресация ячеек различаются при копировании формулы вдоль строк и столбцов электронной таблицы?При копировании относительные ссылки смещаются, абсолютные остаются неизменными, а в смешанных фиксируется только строка или столбец.
29Чем первичный ключ реляционной таблицы отличается от внешнего ключа при связывании таблиц базы данных в задании 3 КЕГЭ?Первичный ключ уникально определяет каждую строку своей таблицы, а внешний ключ ссылается на первичный ключ связанной таблицы.
30Как по тридцатидвухразрядному сетевому адресу узла и маске подсети вычисляется адрес самой сети (задание 13 КЕГЭ)?Адрес сети получают поразрядной конъюнкцией двоичной записи каждого из 4 байтов сетевого адреса узла с соответствующим байтом маски.
31Почему в задании 19 КЕГЭ при формулировке «после неудачного первого хода Пети Ваня выигрывает первым ходом» нельзя требовать победы при любой игре Пети?При неудачном ходе Пети достаточно наличия хотя бы одного хода из начальной кучи в $W_1$, а не попадания в $W_1$ при всех ходах Пети.
32Как рекуррентно вычислить число программ исполнителя из числа $a$ в $b$ с обязательным прохождением через $c$ и избеганием вершины $d$ (задание 23)?В запрещённой точке полагают $K(d) = 0$, а число путей находят произведением двух участков: $K(a \to c) \cdot K(c \to b)$.