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

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

- **Canonical URL:** https://flashcards.world/flashcards/sets/1513741e-fae8-4e4f-a5e1-19b8ad15f7b4/
- **Markdown URL:** https://flashcards.world/flashcards/sets/1513741e-fae8-4e4f-a5e1-19b8ad15f7b4.md
- **Category:** ЕГЭ Профильная Математика, Информатика (КЕГЭ), Физика и Обществознание, Аттестация ФСФР / ЦБ РФ (Базовый и 1.0–5.0), Налоговый Консультант и ПДД ГИБДД
- **Level:** intermediate
- **Languages:** ru → ru
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-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)$. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/1513741e-fae8-4e4f-a5e1-19b8ad15f7b4/).
