Информатика логика егэ поляков

Что это такое? Здесь представлены материалы для подготовки к ЕГЭ по информатике. В отличие от известной литературы, для большинства задач из демо-вариантов ЕГЭ сравниваются несколько способов решения, анализируются их достоинства и недостатки, возможные проблемы и «ловушки». Приведены рекомендации, позволяющие выбрать эффективные методы решения каждой конкретной задачи. Автор признателен О.А. Тузовой (г. Санкт-Петербург) за обсуждение этих материалов и конструктивную критику. Спасибо всем, кто присылал и присылает мне замечания, предложения, сообщения об опечатках и неточностях. Особая благодарность Н.Н. Паньгиной (г. Сосновый Бор) за взаимовыгодное сотрудничество и разностороннюю поддержку проекта. Автор будет благодарен за новые отзывы по поводу представленных здесь материалов для подготовки к ЕГЭ по информатике. Если вы заметили ошибку или у вас просто есть что сказать по существу вопроса, пишите. Тренажёр компьютерного ЕГЭ ЕГЭ по информатике в 2023 году будет проводиться в компьютерной форме. На этом сайте вы можете попробовать, как это будет выглядеть в тренажёре. Он является копией официального тренажёра, но позволяет загружать любой вариант из генератора. Кроме того, после завершения пробного экзамена вы узнаете, сколько баллов вы набрали бы на ЕГЭ, если бы отправили такие ответы. Попробуйте: Авторские семинары Если вы хотите пригласить авторов учебника в свой город для проведения выездного семинара, пишите. Робот-Blockly Робот-Blockly — это версия исполнителей Робот и Водолей, программы для которых составляются из готовых блоков, как в Scratch. Это избавляет учеников от синтаксических ошибок, которые неминуемо возникают при ручном наборе текстовой программы. Программа подходит для вводного курса алгоритмизации в 5-6 (и даже более старших) классах. У программы есть оффлайн-версия, которую можно использовать без доступа к Интернету. Вы можете создавать свои наборы задач, а не только использовать готовые. Коллеги тащат то, что не приколочено… Мартынов Антон Иванович, председатель предметной комиссии по информатике Ульяновской области, опубликовал представленные здесь рекомендации по решению задач части C под своим именем в официальном аналитическом отчете (Ульяновск, 2009). Актуальные публикации В.С. Попов. Новая задача ЕГЭ по информатике № 22: решение с помощью графа // Потенциал: Математика, Физика, Информатика, № 8, 2022. К.Ю. Поляков. Особенности решения задач 25 и 26 в компьютерном ЕГЭ по информатике. Материалы вебинара для учителей г. Сочи, 24.03.2021. К.Ю. Поляков. Динамическое программирование в задачах обработки последовательностей ЕГЭ по информатике. К.Ю. Поляков. Задачи на анализ логических выражений в ЕГЭ по информатике. // Информатика в школе, № 9, 2019, с. 29–35. А.Н. Сидоров Задача 18 ЕГЭ по информатике: логическое выражение с делимостью. Н.Л. Конина Задачи 18 с делимостью. Н.И. Герасименко Задачи 18 с делителями в КИМ ЕГЭ по информатике. К.Ю. Поляков Линейное (и нелинейное) программирование в задаче 18 ЕГЭ по информатике (презентация). К.Ю. Поляков, Битовые операции в задаче 18 КИМ ЕГЭ по информатике. Часть 2. К.Ю. Поляков, Множества и логика в задачах ЕГЭ // Информатика, № 10, 2015, с. 38-42. Е.А. Мирончик. Алгебра предикатов и построение геометрических моделей на ЕГЭ по информатике // Информатика, № 3, 2019, с. 40-47. См. также полный список статей. Что еще посмотреть? Тренажёр для подготовки к компьютерному ЕГЭ Тесты для подготовки к ЕГЭ (для системы NetTest) Онлайн-тесты для подготовки к ЕГЭ Генератор тренировочных вариантов ЕГЭ Программное обеспечение Статьи, презентации Видеоматериалы Дополнительные материалы Материалы прошлых лет (демо-варианты, анализ, разбор задач) Вопросы и ответы Отзывы Новости теперь и в Telegram-канале 9 марта 2023 г.     Исправлено условие задаче 8.330.     Исправлен ответ к задаче 14.403. 5 марта 2023 г.     Новые задачи для тренировки 8, 9. 4 марта 2023 г.     Новые задачи для тренировки 14.     Новые задачи для тренировки 1-3, 7-9, 12-16, 19-25, 27 (А. Богданов).     Новая задача для тренировки 8 (А. Малышев).     Новая задача для тренировки 17 (Д. Статный). 3 марта 2023 г.     Новые задачи для тренировки 26.     Новые задачи для тренировки 23 (Д. Муфаззалов). 2 марта 2023 г.     Новые задачи для тренировки 27. 28 февраля 2023 г.     Новая задача для тренировки 27 (А. Бойко). 25 февраля 2023 г.     Новые задачи для тренировки 17 (И. Митин).     Новые задачи для тренировки 23, 24, 25.     Новые задачи для тренировки 23 (М. Шагитов).     Новая задача для тренировки 27 (А. Рогов). 24 февраля 2023 г.     Новые задачи для тренировки 25, 26 (А. Рогов). 23 февраля 2023 г.     Изменено условие и ответ к задаче 26.94. Приложение для ОС Android Багрепорты, замечания, предложения можно присылать на форум. Официальные материалы Тренажёры для подготовки к компьютерному ЕГЭ (КЕГЭ) Лицензионное соглашение Все опубликованные ниже материалы для подготовки к ЕГЭ по информатике могут быть свободно использованы в некоммерческих целях при условии сохранения авторства. Без письменного согласия автора ЗАПРЕЩАЕТСЯ: 1) публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах; 2) распространение неполных или измененных материалов; 3) включение материалов в сборники на любых носителях информации; 4) получение коммерческой выгоды от продажи или другого использования материалов. Использование и скачивание материалов означает, что вы приняли условия этого лицензионного соглашения. Скачать все сразу Пароль к архиву — kpolyakov.spb.ru Информация Системы счисления Логика Пользовательский курс Алгоритмизация и основы программирования Ответы и решения

Этот сайт больше не обновляется. Сайт К. Полякова «Преподавание, наука и жизнь» переехал по адресу kpolyakov.spb.ru. Новый адрес страницы, к которой вы обратились: Пожалуйста, обновите свои закладки. Через 5 секунд вы будете перенаправлены на новый сайт автоматически. ЕГЭ по информатике Генератор вариантов ЕГЭ Спасибо! Ваше сообщение было успешно отправлено. Что это такое? Здесь вы можете можете построить вариант теста в формате ЕГЭ, основанного на материалах К. Полякова для подготовки к ЕГЭ по информатике. Источники задач: демо-варианты ФИПИ, литература для подготовки к ЕГЭ, тренировочные и диагностические работы МИОО, тесты Яндекса, собственные разработки автора и читателей. Готовые варианты База данных содержит 20 различных полных вариантов ЕГЭ, то есть по 20 разных задач каждого типа. Остальные варианты генерируются методом случайных перестановок. С помощью переключателей можно выбрать нужные группы задач, например, только задания группы В. Построить вариант Учитель может сгенерировать случайный вариант и сообщить ученикам его код. Ученики вводят этот код и получают точно такой вариант, который построил учитель. С помощью переключателей можно выбрать нужные группы задач, например, только задания группы В. Комментарии Вы можете написать свои отзывы и пожелания по поводу генератора вариантов ЕГЭ по информатике. Если у вас нет учетной записи в социальной сети ВКонтакте, можно отправить сообщение прямо с этого сайта.

К. Ю. Поляков Множества и логика в задачах ЕГЭ по информатике Множества и логика в задачах ЕГЭ // Информатика, № 10, 2015, с. 38 -42. К. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

2 Множества и логика в задачах ЕГЭ по информатике Постановка задачи На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение (x P) → (((x Q) ¬(x A)) → ¬(x P)) истинно при любом значении переменной х. Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}. Известно, что выражение (x P) → (((x Q) ¬(x A)) → ¬(x P)) истинно при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A. ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

3 Множества и логика в задачах ЕГЭ по информатике Постановка задачи Для какого наибольшего натурального числа А выражение ¬ДЕЛ(x, А) (ДЕЛ(x, 6) ¬ДЕЛ(x, 4)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)? Определите наименьшее натуральное число A, такое что выражение (x & 53 0) ((x & 41 = 0) (x & A 0)) тождественно истинно? ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

4 Множества и логика в задачах ЕГЭ по информатике Что нужно знать о множествах? A U – универсальное множество (все натуральные) (делятся на 6) – дополнение A до универсального множества (НЕ делятся на 6) ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

5 Множества и логика в задачах ЕГЭ по информатике Что нужно знать о множествах? A B A∙B – пересечение (A B) A B A+B – объединение (A B) ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

6 Множества и логика в задачах ЕГЭ по информатике Множества и логические функции Множество задаётся логической функцией A x A A(x) = 1 A A B ÓК. Ю. Поляков, 2016 -2017 x A∙B x A+B http: //kpolyakov. spb. ru

7 Множества и логика в задачах ЕГЭ по информатике Базовые задачи (ЕГЭ) Задача 1. Каким должно быть множество A для того, чтобы множество A + B совпадало с универсальным множеством? Другие решения: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

8 Множества и логика в задачах ЕГЭ по информатике Базовые задачи (ЕГЭ) Задача 2. Каким должно быть множество A для того, чтобы множество совпадало с универсальным множеством? ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

9 Множества и логика в задачах ЕГЭ по информатике Общий подход к решению 1. Свести задачу к одной из базовых задач Задача 1. Задача 2. Использовать готовое решение: Задача 1. Задача 2. ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

10 Множества и логика в задачах ЕГЭ по информатике Задачи с отрезками На числовой прямой даны два отрезка: P = [37; 60] и Q = [40; 77]. Укажите наименьшую возможную длину такого отрезка A, что выражение (x P) → (((x Q) ¬(x A)) → ¬(x P)) истинно при любом значении переменной х. Вводим утверждения: P = (x P), Q = (x Q), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

11 Множества и логика в задачах ЕГЭ по информатике Задачи с отрезками Упрощение выражения: Задача 1 Решение: P = [37; 60], Q = [40; 77] Amin = [40; 60] ÓК. Ю. Поляков, 2016 -2017 длина 20 http: //kpolyakov. spb. ru

12 Множества и логика в задачах ЕГЭ по информатике Задачи с отрезками-II На числовой прямой даны два отрезка: P = [10; 20] и Q = [25; 55]. Укажите наибольшую возможную длину такого отрезка A, что выражение (x A) → ((x P) (x Q)) истинно при любом значении переменной х. Вводим утверждения: P = (x P), Q = (x Q), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

13 Множества и логика в задачах ЕГЭ по информатике Задачи с отрезками-II Упрощение выражения: Задача 2 Решение: P = [10; 20], Q = [25; 55] Нельзя перекрыть! 10 20 25 Amax = [25; 55] ÓК. Ю. Поляков, 2016 -2017 55 x длина 30 http: //kpolyakov. spb. ru

14 Множества и логика в задачах ЕГЭ по информатике Множества чисел Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}. Известно, что выражение (x P) → (((x Q) ¬(x A)) → ¬(x P)) истинно при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A. Вводим утверждения: P = (x P), Q = (x Q), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

15 Множества и логика в задачах ЕГЭ по информатике Множества чисел Упрощение выражения: Задача 1 Решение: P = {2, 4, 6, 8, 10, 12}, Q = {4, 8, 12, 116} Amin = {4, 8, 12} ÓК. Ю. Поляков, 2016 -2017 сумма 24 http: //kpolyakov. spb. ru

16 Множества и логика в задачах ЕГЭ по информатике Множества чисел-II Элементами множеств А, P и Q являются натуральные числа, причём P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20} Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }. Известно, что выражение ((x A) → ¬(x P)) (¬(x Q) → ¬(x A)) истинно при любом значении переменной х. Определите наибольшее возможное количество элементов множества A. Вводим утверждения: P = (x P), Q = (x Q), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

17 Множества и логика в задачах ЕГЭ по информатике Множества чисел-II Упрощение выражения: Решение: Задача 2 P = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20} Q = { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 } Amax = { 3, 9, 15, 21, 24, 27, 30 } ÓК. Ю. Поляков, 2016 -2017 7 шт. http: //kpolyakov. spb. ru

18 Множества и логика в задачах ЕГЭ по информатике Делимость Для какого наибольшего натурального числа a выражение ¬ДЕЛ(x, a) (ДЕЛ(x, 6) ¬ДЕЛ(x, 4)) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)? DN – множество чисел, делящихся на N A = Da – множество чисел, делящихся на a Вводим утверждения: DN = (x DN), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

19 Множества и логика в задачах ЕГЭ по информатике Делимость Упрощение выражения: Задача 1 Решение: D 6∙D 4 = D 12 D 6∙D 4 A=Da max 12 Одновременно делятся на 6 и на 4! любой делитель 12! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

20 Множества и логика в задачах ЕГЭ по информатике Amin amax Почему максимальное число a дает минимальное множество A? a=6 0 6 12 18 24 30 36 x a=12 0 12 24 36 x a=24 ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

21 Множества и логика в задачах ЕГЭ по информатике Делимость-II Для какого наибольшего натурального числа a выражение ¬ДЕЛ(x, a) (¬ ДЕЛ(x, 21) ¬ДЕЛ(x, 35)) тождественно истинно? DN – множество чисел, делящихся на N A = Da – множество чисел, делящихся на a Вводим утверждения: DN = (x DN), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

22 Множества и логика в задачах ЕГЭ по информатике Делимость-II Упрощение выражения: Задача 1 Решение: D 21+D 35 = Da D 21+D 35 < Da Делятся на 21 или на 35! нет такого a! max Общий делитель 21 и 35! ÓК. Ю. Поляков, 2016 -2017 7 http: //kpolyakov. spb. ru

23 Множества и логика в задачах ЕГЭ по информатике Делимость-III Для какого наименьшего натурального числа a выражение ДЕЛ(x, a) (¬ ДЕЛ(x, 21) ДЕЛ(x, 35)) тождественно истинно? DN – множество чисел, делящихся на N A = Da – множество чисел, делящихся на a Вводим утверждения: DN = (x DN), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

24 Множества и логика в задачах ЕГЭ по информатике Делимость-III Упрощение выражения: Задача 2 Решение: нет такого a! ÓК. Ю. Поляков, 2016 -2017 Не делятся на 21 или делятся на 35! http: //kpolyakov. spb. ru

25 Множества и логика в задачах ЕГЭ по информатике Делимость-III Переход к другой импликации: ! Если число делится на a и на 21, оно должно делиться на 35! Делится на A и на 21: k, m – натуральные Делится на 35: Этот сомножитель добавляется с помощью A! ÓК. Ю. Поляков, 2016 -2017 min 5 http: //kpolyakov. spb. ru

26 Множества и логика в задачах ЕГЭ по информатике Делимость-IV Для какого наименьшего натурального числа a выражение (ДЕЛ(x, a) ДЕЛ(x, 21)) ДЕЛ(x, 18) тождественно истинно? DN – множество чисел, делящихся на N A = Da – множество чисел, делящихся на a Вводим утверждения: DN = (x DN), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

27 Множества и логика в задачах ЕГЭ по информатике Делимость-IV ! Если число делится на A и на 21, оно должно делиться на 18! Делится на A и на 21: Делится на 18: Эти сомножители добавляются с помощью A! ÓК. Ю. Поляков, 2016 -2017 min 18 http: //kpolyakov. spb. ru

28 Множества и логика в задачах ЕГЭ по информатике Делимость-V Для какого наименьшего натурального числа a выражение ¬ДЕЛ(x, 18) (¬ДЕЛ(x, 21) ¬ДЕЛ(x, a)) тождественно истинно? DN – множество чисел, делящихся на N A = Da – множество чисел, делящихся на a Вводим утверждения: DN = (x DN), A = (x A) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

29 Множества и логика в задачах ЕГЭ по информатике Делимость-IV Задача 2 Решение: нет такого a! Делятся на 18 или на 21! Варианты: ! Нельзя перекрывать другие числа! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

30 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Определите наименьшее натуральное число a, такое что выражение (x & 53 0) ((x & 41 = 0) (x & a 0)) тождественно истинно. ? Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 Число a определяет множество Za или условие A. http: //kpolyakov. spb. ru

31 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Что такое Z 53: биты 5 4 3 2 1 0 53 = 110101 x = abcdef x & 53 = ab 0 d 0 f = 0 Что такое : биты 5 4 3 2 1 0 53 = 110101 x = abcdef x & 53 = ab 0 d 0 f 0 ÓК. Ю. Поляков, 2016 -2017 Биты 5, 4, 2, 0 числа x нулевые! Среди битов 5, 4, 2, 0 числа x есть ненулевые! http: //kpolyakov. spb. ru

32 Множества и логика в задачах ЕГЭ по информатике Главная ошибка После упрощения: биты 5 4 3 2 1 0 21 = 010101 11 = 001011 Вывод: Натуральные числа! ! ? ÓК. Ю. Поляков, 2016 -2017 Логические значения! Это ИНОГДА проходит! Это min или max? http: //kpolyakov. spb. ru

33 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции биты 5 4 3 2 1 0 53 = 110101 Z 53 30 = 011110 Z 30 63 = 111111 = 53 or 30 ÓК. Ю. Поляков, 2016 -2017 Биты 5, 4, 2, 0 числа x нулевые! Биты 4, 3, 2, 1 числа x нулевые! http: //kpolyakov. spb. ru

34 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции биты 5 4 3 2 1 0 53 = 110101 Z 53 30 = 011110 Z 30 20 = 010100 = 53 and 30 Биты 5, 4, 2, 0 числа x нулевые! Биты 4, 3, 2, 1 числа x нулевые! Только в одну сторону! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

35 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Двойственность операций И и ИЛИ Доказательство: только для левой части импликации! От противного: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

36 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Биты 4, 2 и 0 нулевые! биты 4 3 2 1 0 21 = 10101 ! Биты 4 и 0 нулевые! биты 4 3 2 1 0 17 = 10001 Множество единичных битов c входит во множество единичных битов b! 0 биты 4 3 2 1 0 21 = 10101 ÓК. Ю. Поляков, 2016 -2017 биты 4 3 2 1 0 1 7 = 00111 http: //kpolyakov. spb. ru

37 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции ? Для каких x? Если в числе x не равен 0 хотя бы один бит, который равен 1 в b or c ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

Множества и логика в задачах ЕГЭ по информатике 38 Побитовые логические операции Вариант 1: Вариант 2: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

39 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Вариант 1: ! a – любое! Вариант 2: ! Множество единичных битов a входит во множество единичных битов b! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

40 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Метод А. В. Здвижковой (г. Армавир): ! Строим импликацию так, чтобы избавиться от всех инверсий! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

41 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции Биты 5, 3, 0 нулевые! Решение: Логическое ИЛИ между битами! биты 5 4 3 2 1 0 41 = 101001 a = ? ? ? 1 1 53 = 110101 amin = 101002 = 20 ÓК. Ю. Поляков, 2016 -2017 Биты 5, 4, 2, 0 нулевые! ? Другие a? http: //kpolyakov. spb. ru

42 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции-II Определите наибольшее натуральное число a, такое что выражение (x & a 0) ((x & 20 = 0) (x & 5 0)) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

43 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции-II Упрощение выражения (до суммы): Импликация без инверсий: Решение: биты 4 3 2 1 0 Биты 4, 2 нулевые! 20 = 10100 5 = 00101 amax = 101012 = 21 a = 1, 4, 5, 16, 17, 20, 21 Биты 2, 0 нулевые! ? ? Другие a? Сколько? 23 – 1 = 7 ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

44 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции-III Определите наибольшее натуральное число a, такое что выражение (x & a 0) ((x & 12 = 0) (x & 21 = 0)) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

45 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции-III Упрощение выражения: ! От него ничего не зависит! Решение: биты 4 3 2 1 0 12 = 1100 1 21 = 1 10101 ? amax = 11002 = 12 Другие a? a = 4, 8, 12 22 – 1 = 3 ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

46 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции-IV Определите наименьшее натуральное число a, такое что выражение ( (x & 28 0) (x & 45 0)) ((x & 48 = 0) (x & a 0)) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

47 Множества и логика в задачах ЕГЭ по информатике Побитовые операции–IV Упрощение выражения: Решение: биты 5 4 3 2 1 0 28 = 11100 45 = 101101 = 111101 48 = 110000 11 1 a = ? ? ? = 111101 ÓК. Ю. Поляков, 2016 -2017 Логическое ИЛИ между битами! ? Другие a? amin = 11012 = 13 http: //kpolyakov. spb. ru

48 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (V) (А. Г. Гильдин). Определите наименьшее натуральное число a, такое что выражение (x & 19 = 0) (x & 38 0) ((x & 43 = 0) ((x & a = 0) (x & 43 = 0))) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

49 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (V) Упрощение выражения: ! Решение: биты 5 4 3 2 1 0 ? 43 = 101011 Какие подходят? Все, у которых единицы только в разрядах 5, 3, 1 и 0! a = 1, 2, 3, 8, 9, 10, 11, 32, 33, 34, 35, 40, 41, 42, 43 ÓК. Ю. Поляков, 2016 -2017 Не влияют на решение! 24 – 1 = 15 http: //kpolyakov. spb. ru

50 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (VI) (М. В. Кузнецова). Определите наименьшее натуральное число a, такое что выражение (( (x & 13 0) (x & a 0)) (x & 13 0) ((x & a 0) (x & 39 = 0)) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

51 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (V) Упрощение выражения: Решение: биты 5 4 3 2 1 0 13 = 1101 1 39 = 1 100111 ÓК. Ю. Поляков, 2016 -2017 ! Не влияет на решение! a = 1, 4, 5, 8, 9, 12, 13 http: //kpolyakov. spb. ru

52 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (V) Вариант с другими числами: Решение: биты 5 4 3 2 1 0 53 = 110101 21 = 10101 ! ! Всегда 1! a – любое! Множество единичных битов числа 21 входит во множество единичных битов числа 53! ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

53 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (VI) Определите наименьшее натуральное число a, такое что выражение ((x & 23 0) (x & 45 0)) ((x & a 0) (x & 23 0)) тождественно истинно. Вводим множества: ZN = {x: x & N = 0} Вводим утверждения: ZN = (x ZN), A = (x Za) Заданное условие: ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

54 Множества и логика в задачах ЕГЭ по информатике Побитовые логические операции (V) Упрощение выражения: или ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

55 Множества и логика в задачах ЕГЭ по информатике Нерешаемая задача Попытка решения: биты 5 4 3 2 1 0 43 = 101011 a = ? ? ? 1 48 = 110000 ! ÓК. Ю. Поляков, 2016 -2017 Логическое ИЛИ между битами! С помощью a можно добавить биты, но нельзя убрать! http: //kpolyakov. spb. ru

56 Множества и логика в задачах ЕГЭ по информатике Конец фильма ПОЛЯКОВ Константин Юрьевич д. т. н. , учитель информатики ГБОУ СОШ № 163, г. Санкт-Петербург [email protected] ru ÓК. Ю. Поляков, 2016 -2017 http: //kpolyakov. spb. ru

Материалы для подготовки к ЕГЭ по информатике К. Ю. Полякова

Лицензионное соглашение

Все опубликованные ниже материалы для подготовки к ЕГЭ по информатике могут быть свободно использованы
в некоммерческих целях при условии сохранения авторства. Без письменного согласия автора
ЗАПРЕЩАЕТСЯ:

1. публикация материалов в любой форме, в том числе размещение материалов на других Web-сайтах;
2. распространение неполных или измененных материалов;
3. включение материалов в сборники на любых носителях информации;
4. получение коммерческой выгоды от продажи или другого использования материалов.

Скачивание материалов означает, что вы приняли условия этого лицензионного соглашения.

Информация (задания 4, 7, 8, 11)

Системы счисления (задание 14)

Логика (задания 2, 15)

Пользовательский курс (задания 1, 3, 9, 10, 13)

Алгоритмизация и основы программирования (задания 5, 6, 12, 16−27)

Ответы и решения

———-
Оригинал страницы: http://kpolyakov.spb.ru/school/ege.htm.

Public user contributions licensed under
cc-wiki license with attribution required

1


К.Ю. Поляков, М.А. Ройтберг, Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг

2


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Постановка задачи (ЕГЭ-2011) : Решаемость 3,2% Сколько решений имеет система уравнений: где– логические переменные.

3


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Методы решения 3 1)замена переменных 2)последовательное подключение уравнений 3)метод отображения (Е.А. Мирончик) «Информатика. Первое сентября» 1. Е. А. Мирончик, Метод отображения // Информатика, 10, 2013, с Е.А. Мирончик, Люблю ЕГЭ за В15, или Еще раз про метод отображения // Информатика, 7-8, 2014, с «Информатика. Первое сентября» 1. Е. А. Мирончик, Метод отображения // Информатика, 10, 2013, с Е.А. Мирончик, Люблю ЕГЭ за В15, или Еще раз про метод отображения // Информатика, 7-8, 2014, с трудоёмко длинная запись решения 2012: Решаемость 13,2%

4


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Аналогии с алгеброй 4 Алгебра Логика Элементарные уравнения: линейные, квадратные. Элементарные уравнения не выделяются. Методы преобразования: законы сложения и умножения, формулы сокращенного умножения, свойства степеней. Методы преобразования: законы логики (см. далее). Обычно уравнение имеет одно или несколько решений. Уравнение может иметь большое, но конечное число решений.

5


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – I 5 A. Свойства 0, 1 и отрицания Свойства 0 и 1 Свойства отрицания

6


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – II 6 Б. Дизъюнкция и конъюнкция Сочетательный закон Переместительный закон Закон поглощения Распределительный закон Правила де Моргана

7


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Формулы логики – III 7 В. Импликация и эквивалентность Определение импликации Свойства импликации Эквивалентность

8


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Основные идеи 8 1)Решение системы уравнений – это битовая цепочка (битовый вектор) 2)Битовый вектор рассматривается как единый объект. 3)Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов). 4)Нужно выделить элементарные уравнения и записать ограничения «на русском языке». 5)Количество решений находится по правилам комбинаторики. для любого i

9


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 9 Задача 1. «соседние биты одинаковы» Решения: 00000, Задача 2. «соседние биты различны» Решения: 01010, «биты чередуются»

10


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Типичные ограничения 10 Задача 3. «запрещена комбинация 10» Решения: , , , , , , «после первой единицы все следующие биты – 1» «все нули, потом все единицы» Для уравнения с N переменными: N+1 решений.

11


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 11 Задача 4. «запрещена комбинация 1 0» Решения: , , , , , , «слева от каждого нулевого бита (начиная с 3-го) должны стоять два нуля» «все нули, потом все единицы» Для уравнения с N переменными: N+2 решений. «запрещена комбинация » и ещё:

12


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 12 Задача 5. «запрещена комбинация 00» Сколько есть цепочек длиной N, в которых нет двух соседних нулей? ?

13


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример Все цепочки длиной нет 00! непересекающиеся множества! {0, 1}{01, 10, 11}

14


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Более сложный пример 14 1, 1, 2, 3, 5, 8, 13, 21, 34, … Числа Фибоначчи {0, 1}{01, 10, 11} Рекурсия: ЕГЭ-11 (B6) Динамическое программирование: ЕГЭ-22 (B13), ЕГЭ-15 (B9) !

15


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё пример 15 Задача 6. «запрещена комбинация 1 0» «после двух единиц подряд следуют только единицы»

16


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, И снова – рекуррентные уравнения 16 Структура решения: 11 1 «хвост»«голова» нет комбинации 11 последний бит – 0 : одна «голова» (пустая) : одна «голова» (0) «голов»

17


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Последний пример 17 Задача 7. Последовательность выполнения: запрещена комбинация 1 0 на последнем шаге Сколько решений у уравнения Начальное значение:

18


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «запрещено 00» «после двух единиц идут только единицы» Если не трогать : 11 1 «хвост»«голова» «запрещено 00 и 11» «биты чередуются»

19


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Варианты отличаются местом последнего нуля: , , , , , , , , Учитываем : 1 решение 2 решения нулевых бита, 2 2 вариантов

20


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Как перевести на русский язык? ?

21


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ «очередной бит равен хотя бы одному из 2-х следующих» «запрещены комбинации 100 и 011» 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются. 1)сначала цепочка нулей, потом биты чередуются (1/0) 2)сначала цепочка единиц, потом биты чередуются … … = 20 «после 01 или 10 биты чередуются»

22


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ

23


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ решений: X = 0000, 0001, 0011, 0111, решений: Y = 0000, 0001, 0011, 0111, 1111 без ограничений! Связь X и Y:

24


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ X: Y:Y: = 15

25


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Замена переменных: …

26


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ К одному уравнению: Решения:

27


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Демо-вариант ЕГЭ Переход к исходным переменным: Каждый бит в Z даёт удвоение вариантов в X! ! 5 бит

28


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 28 Замена переменных:

29


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 29 Решение: «запрещена комбинация 01» «все единицы, потом – все нули» 8 решений: Но в z i ! !

30


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Ещё одна задача (2015) 30 2 решения: (0;1) и (1;0) 1 решение: (1;1) Каждый 0 удваивает количество решений! ! ZZ X,Y =

31


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Основные шаги решения 31 1)упрощение уравнений с помощью эквивалентных преобразований 2)замена переменных (если возможно) 3)исследование структуры всех решений 4)подсчёт количества решений по формулам комбинаторики

32


Системы логических уравнений в задачах ЕГЭ по информатике К.Ю. Поляков, М.А. Ройтберг, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург РОЙТБЕРГ Михаил Абрамович д.ф.-м.н., зав. кафедрой АТП ФИВТ МФТИ, зам. руководителя Федеральной комиссии по разработке КИМ ЕГЭ по информатике и ИКТ