Задание 16. Анализ алгоритмов: ЕГЭ по информатике

Задание 16 ЕГЭ по информатике проверяет умение анализировать простейшие алгоритмы управления исполнителями и вычислительные алгоритмы. В экзаменационном варианте встречаются два типа задач: логическое выражение с делимостью и отрезком (нужно найти наибольшее/наименьшее A, при котором выражение…

Что нужно знать

• Задание 16 относится к части 1, ответ — краткое число, вносимое в бланк без пробелов и единиц измерения.
• Логическая задача: выражение вида ДЕЛ(x, A) ∨ ((x ∈ B) → ¬ДЕЛ(x, m)) должно быть истинно при любом целом положительном x.
• Импликация P → Q ложна только когда P истинно, а Q ложно; равносильна ¬P ∨ Q.
• Отрицание ДЕЛ(x, m) означает, что x не делится на m нацело.
• Для выполнения выражения при всех x нужно, чтобы множество чисел, где выражение ложно, было пустым.
• Удобно перейти к множествам: пусть M_A — числа, делящиеся на A, M_B — отрезок B, M_m — числа, делящиеся на m. Тогда условие: M_A ∪ (¬M_B ∪ ¬M_m) = все числа, то есть M_A должно покрывать те числа, где (x ∈ B) и ДЕЛ(x…

Термины и понятия

• Импликация: логическая операция A → B, ложна только когда A истинно, B ложно; равносильна ¬A ∨ B.
• ДЕЛ(n, m): утверждение «натуральное число n делится без остатка на натуральное число m».
• Отрезок B: множество чисел x, удовлетворяющих неравенству a ≤ x ≤ b.
• НОД: наибольший общий делитель двух или более натуральных чисел.
• Система счисления с основанием 22: позиционная система, алфавит цифр 0–9, A–L (где A=10, B=11, …, L=21).
• Цифра x: неизвестная цифра в записи числа в системе счисления, может принимать целые значения от 0 до основания минус 1.
• Кратность: число a кратно числу b, если a делится на b без остатка.
• Частное от деления: результат деления одного числа на другое нацело.

Частые ошибки

• Неверное раскрытие импликации: путают A → B с B → A или забывают, что импликация ложна только в одном случае.
• Ошибка при раскрытии отрицания: ¬ДЕЛ(x, m) интерпретируют как ДЕЛ(x, m), теряют отрицание.
• Не учитывают, что x — целое положительное, и рассматривают отрицательные или нулевые значения.
• При решении логической задачи находят A как делитель только одного числа, но не проверяют все числа из отрезка, делящиеся на m.

Как пройти тему

В курсе «Информатика» тема «Задание 16. Анализ алгоритмов» занимает 6 занятий по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Задание 11. Кодирование изображений и звука
• Задание 18. Системы счисления
• Задание 24. Обработка символьных данных
• Задание 25. Обработка натуральных чисел
• Задание 26. Массивы и последовательности

← Предыдущая тема: Задание 15. Основные понятия и законы математической логики
Следующая тема: Задание 17. Алгоритм обработки числовой последовательности

Все темы: ЕГЭ по информатике