Проект методы решения задач егэ по информатике

Научно-практическая конференция

«Шаг в будущее»

Тема доклада «Методы решения заданий ЕГЭ по информатике»

Выполнил ученик 11 класса МБОУ СОШ с.Хондергей

Монгуш Ай-Херел

Руководитель: Ховалыг Ш.Г., учитель информатики

Февраль 2019г.

Тема: «Методы решения задач ЕГЭ по информатике»

Проблема: Как успешно сдать ЕГЭ?

По окончанию школы каждый ученик должен сдать ЕГЭ. Немалые несдавшие ЕГЭ учащиеся не получают аттестаты. А для успешной сдачи ЕГЭ нужна тщательная подготовка. Поэтому вопрос «Как успешно сдать ЕГЭ?» остается актуальным для всех выпускников. Поэтому я выбрал тему «Методы решения задач ЕГЭ по информатике».

Цель: изучить методы решения заданий единого государственного экзамена по информатике

Задачи:

1. Собрать различные задания из тренировочных вариантов ЕГЭ;
2. Решить задачи ЕГЭ;
3. Выявить, сколькими разными способами можно решить данные задачи.

Гипотеза:

Если научиться решать задачи ЕГЭ по информатике с разными способами, то можно успешно сдать ЕГЭ по информатике.

Рассмотрим несколько заданий из ЕГЭ.

Задача 1.

Сколько единиц в двоичной записи восьмеричного числа 3458?

1 способ. Число из восьмеричной системы счисления перевести в десятичную. Из десятичной системы счисления перевести в двоичную.

3458 = 3*82 + 4*81 + 5*80= 192+32+5=229.

22910 = 111001012.              Вычислить количество 1 в двоичной записи.

                                                                             Ответ: 5.

2 способ.  Таблица соответствия.

 См слайд 8.

3 способ. С помощью таблицы степени 2.

См. слайд 9.                                               1             1              1             0               0             1              0              1

3458 = 22910

229 = 128+64+32+4+1.

Наибольшее число 128. Под таблицей отметим 1.

128 есть. Отметим 1.

64 есть – отметим 1.

32 есть – отметим 1.

4 есть. Отметим 1.

1 есть. Отметим 1.

В остальных случаях отметим 0.

Получилось двоичное число 11100101.

В двоичном числе количество единиц   — 5.     Ответ 5.

4 способ. С помощью позиции чисел.

Представим число с помощью степеней двойки

229 = 128+64+32+4+1 = 27 + 26 + 25 + 22 + 20. Наибольший степень эта 7. Отметим позиции числе от 7 до 0.

Позиции: 7   6   5   4   3   2   1  0.            Отмети если 27 есть, то под числом 7                  

                  1    1   1   0   0   1   0  1           отметим 1. Если 26 есть,то под числом

                                                                  6 отметим 1. А если 23 нет среди  

                                                                   слагаемых, поставим 0 и т. д.

Получилось двоичное число 11100101. Количество единиц 5.

 Правильность выполнения задания можно проверить с помощью калькулятора.

Задача 5.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А — 10, Б — 00, В — 010, Г – 110. Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

1 способ: Посмотрим на таблицу. Нам понадобится восьмиричная СС. Между числами 010 и 110 лежит 3 числа. Среди них наименьшее 011.

2 способ графический. Построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветки 0, а каждой правой 1.

Задача 10.

Рассмотрим 3 случая:

1. Буква А встречается в слове ровно 1 раз.
2. Буква А встречается в слове ровно 2 раза.
3. Буква А встречается в слове не более двух раз.

1 случай. Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква А используется ровно 1 раз. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

2 случай. Саша составляет четырехбуквенные слова, в которых есть только буквы Е, Д, А, Н и К, причём в каждом слове буква А используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

3 случай. Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, причём в каждом слове буква А используется не более двух раз, и при этом может стоять только на первом или на последнем местах. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

Задача 17.

Запрос «или» вычисляется по этой формуле.

Ш|Т = Ш + Т – Ш&Т.  Обозначили через Ш – количество страниц запроса «Шахматы».

                                                                 Через Т – количество страниц запроса «Теннис».

Из этой формулы выразим количество страниц запроса «Шахматы».

Есть два способа решения задания:

1 способ – выписать все нужные программы, построить дерево программ.

2 способ – подсчитать число программ, не выписывая их явно, а написав формулу, которая позволяет найти количество программ получения данного числа, если уже известно количество программ для получения меньших чисел (при таком решении удобно заполнять таблицу).

Из числа 3 нужно получить 23.

Есть две команды.

1. Прибавить 1
2. Умножь на 2.

Эти две команды записываем в обратными командами.

1.  Х-1 (не прибавляем, а наоборот вычитаем 1)
2. х/2 (не умножаем, а делим на 2).

Получилось 2 новые команды.

Их записываем в таблицу.

На первом  столбце таблицы записывали числа от 3 до 23. На 2 и 3 столбцах обратные команды. На последнем столбце количество программ.

1 строка. Проверяем первую команду. От трех вычитаем 1 получается 2. Число 2 не входит траекторию. Ничего не записываем. Проверяем вторую команду. 3 делим на 2. Единица получается, тоже не входит в траекторию. Ничего не записываем. Само число 3 это 1 программа.

2 строка. 4-1=3. Число 3 входит в траекторию. Поэтому 1 программа.

3 строка.  1 программа.

Таким образом, суммируются программы.

Вывод:

• Научился решать задачи ЕГЭ.
• Способы решения заданий ЕГЭ по информатике немного.

Литература:

• Информатика и ИКТ. Подготовка к ЕГЭ. Тренировочные варианты.
• Интернет-ресурсы.
• Видеоуроки.

Проект «Методы решения задач ЕГЭ по информатике»

Проект «Методы решения задач ЕГЭ по информатике»

Скачать:

Предварительный просмотр:

Тема доклада «Методы решения заданий ЕГЭ по информатике»

Выполнил ученик 11 класса МБОУ СОШ с.Хондергей

Руководитель: Ховалыг Ш.Г., учитель информатики

Тема: «Методы решения задач ЕГЭ по информатике»

Проблема: Как успешно сдать ЕГЭ?

По окончанию школы каждый ученик должен сдать ЕГЭ. Немалые несдавшие ЕГЭ учащиеся не получают аттестаты. А для успешной сдачи ЕГЭ нужна тщательная подготовка. Поэтому вопрос «Как успешно сдать ЕГЭ?» остается актуальным для всех выпускников. Поэтому я выбрал тему «Методы решения задач ЕГЭ по информатике».

Цель: изучить методы решения заданий единого государственного экзамена по информатике

1. Собрать различные задания из тренировочных вариантов ЕГЭ;
2. Решить задачи ЕГЭ;
3. Выявить, сколькими разными способами можно решить данные задачи.

Если научиться решать задачи ЕГЭ по информатике с разными способами, то можно успешно сдать ЕГЭ по информатике.

Рассмотрим несколько заданий из ЕГЭ.

Сколько единиц в двоичной записи восьмеричного числа 345 8 ?

1 способ. Число из восьмеричной системы счисления перевести в десятичную. Из десятичной системы счисления перевести в двоичную.

345 8 = 3*8 2 + 4*8 1 + 5*8 0 = 192+32+5=229.

229 10 = 11100101 2 . Вычислить количество 1 в двоичной записи.

2 способ. Таблица соответствия.

3 способ. С помощью таблицы степени 2.

См. слайд 9. 1 1 1 0 0 1 0 1

Наибольшее число 128. Под таблицей отметим 1.

128 есть. Отметим 1.

64 есть – отметим 1.

32 есть – отметим 1.

4 есть. Отметим 1.

1 есть. Отметим 1.

В остальных случаях отметим 0.

Получилось двоичное число 11100101.

В двоичном числе количество единиц — 5. Ответ 5.

4 способ. С помощью позиции чисел.

Представим число с помощью степеней двойки

229 = 128+64+32+4+1 = 2 7 + 2 6 + 2 5 + 2 2 + 2 0 . Наибольший степень эта 7. Отметим позиции числе от 7 до 0.

Позиции: 7 6 5 4 3 2 1 0. Отмети если 2 7 есть, то под числом 7

1 1 1 0 0 1 0 1 отметим 1. Если 2 6 есть,то под числом

6 отметим 1. А если 2 3 нет среди

слагаемых, поставим 0 и т. д.

Получилось двоичное число 11100101. Количество единиц 5.

Правильность выполнения задания можно проверить с помощью калькулятора.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А — 10, Б — 00, В — 010, Г – 110. Укажите кратчайшее кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

1 способ: Посмотрим на таблицу. Нам понадобится восьмиричная СС. Между числами 010 и 110 лежит 3 числа. Среди них наименьшее 011.

2 способ графический. Построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветки 0, а каждой правой 1.

Рассмотрим 3 случая:

1. Буква А встречается в слове ровно 1 раз.
2. Буква А встречается в слове ровно 2 раза.
3. Буква А встречается в слове не более двух раз.

1 случай. Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, причём в каждом слове буква А используется ровно 1 раз. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

2 случай. Саша составляет четырехбуквенные слова, в которых есть только буквы Е, Д, А, Н и К, причём в каждом слове буква А используется ровно 2 раза. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

3 случай . Саша составляет пятибуквенные слова, в которых есть только буквы А, Б, В, Г, причём в каждом слове буква А используется не более двух раз, и при этом может стоять только на первом или на последнем местах. Каждая из других допустимых букв может встречаться любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, необязательно осмысленная. Сколько существует таких слов, которые может написать Саша?

Запрос «или» вычисляется по этой формуле.

Ш|Т = Ш + Т – Ш&Т. Обозначили через Ш – количество страниц запроса «Шахматы».

Через Т – количество страниц запроса «Теннис».

Из этой формулы выразим количество страниц запроса «Шахматы».

Есть два способа решения задания:

1 способ – выписать все нужные программы, построить дерево программ .

2 способ – подсчитать число программ, не выписывая их явно, а написав формулу, которая позволяет найти количество программ получения данного числа, если уже известно количество программ для получения меньших чисел ( при таком решении удобно заполнять таблицу ).

Из числа 3 нужно получить 23.

Есть две команды.

Эти две команды записываем в обратными командами.

1. Х-1 (не прибавляем, а наоборот вычитаем 1)
2. х/2 (не умножаем, а делим на 2).

Получилось 2 новые команды.

Их записываем в таблицу.

На первом столбце таблицы записывали числа от 3 до 23. На 2 и 3 столбцах обратные команды. На последнем столбце количество программ.

1 строка. Проверяем первую команду. От трех вычитаем 1 получается 2. Число 2 не входит траекторию. Ничего не записываем. Проверяем вторую команду. 3 делим на 2. Единица получается, тоже не входит в траекторию. Ничего не записываем. Само число 3 это 1 программа.

2 строка. 4-1=3. Число 3 входит в траекторию. Поэтому 1 программа.

3 строка. 1 программа.

Таким образом, суммируются программы.

• Научился решать задачи ЕГЭ.
• Способы решения заданий ЕГЭ по информатике немного.

• Информатика и ИКТ. Подготовка к ЕГЭ. Тренировочные варианты.
• Интернет-ресурсы.
• Видеоуроки.

«Яндекс» открыл доступ к нейросети «Балабоба» для всех пользователей

Старинная английская баллада “Greensleeves” («Зеленые рукава»)

Позвольте, я вам помогу

Как представляли себе будущее в далеком 1960-м году

Источник

старое Информатика ЕГЭ 1 задание

Объяснение задания 1 ЕГЭ по информатике

«Перевод всех используемых в задании чисел в десятичную систему сам по себе не является ошибкой, но приводит к лишним вычислениям и увеличению вероятности арифметической ошибки»

Системы счисления и представление информации в памяти ПК

Для решения 1 задания следует вспомнить и повторить следующие темы:

Двоичная система счисления

Количество цифр или основание системы: 2
Цифры (алфавит): 0, 1

Перевод чисел из 10-й сист. сч-я в двоичную

Перевод чисел из 2-й сист. сч-я в 10-ую

При работе с большими числами, лучше использовать разложение по степеням двойки:

Разложение по степеням двойки

Восьмеричная система счисления

Количество цифр или основание системы: 8
Цифры (алфавит): 0, 1, 2, 3, 4, 5, 6, 7

Перевод чисел из 10-й сист. сч-я в 8-ую

Перевод чисел из 8-й системы счисления в 10-ую

Перевод из 8-й сист. сч-я в 2-ую и обратно триадами

Шестнадцатеричная система счисления

Количество цифр или основание системы: 16
Цифры (алфавит): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A (10), B (11), C (12), D (13), E (14), F (15)

Перевод из 10-й сист. сч-я в 16-ую

Перевод из 16-й сист. сч-я в 10-ую

Перевод из 2-й с. сч-я в 16-ую и обратно тетрадами

Полезности для двоичной системы счисления:

• числа, которые в 2-ной системе счисления оканчиваются на 0 — четные, на 1 — нечетные;
• соответственно, числа, которые делятся на 4, будут оканчиваться на 00, и т.д.; таким образом, выведем общее правило:
• если число N находится в интервале 2 k-1 ≤ N k , в его двоичной записи будет ровно k цифр, например, для 126:
• если число имеет вид 2 k , то оно записывается в двоичной системе как единица и k нулей, например:
• если число имеет вид 2 k -1, то оно записывается в двоичной системе k единиц, например:
• если известна двоичная запись N, то двоичную запись числа 2•N можно легко получить, приписав в конец ноль, например:

Тренировка работы с системами счисления (эти задания отсутствуют в ЕГЭ с 2021г.)

Сколько единиц в двоичной записи шестнадцатеричного числа 2AC1₁₆?

✍ Решение:

• В шестнадцатеричной с-ме счисления числа от 10 до 15 представлены буквами латинского алфавита: A-10, B-11, C-12, D-13, E-14, F-15.
• Необходимо вспомнить двоичные коды чисел от 1 до 15 (см. теорию выше на странице), так как для перевода 16-ричного в двоичную с-му достаточно каждую цифру отдельно записать в виде четверки двоичных цифр (тетрады):
• в этой записи 6 единиц

Результат: 6

Подробный разбор 1 задания с объяснением просмотрите на видео:

Сколько существует целых чисел x, для которых выполняется неравенство 2A₁₆ ), то количество целых, удовлетворяющих условию:

Результат: 6

Подробное решение данного 1 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

Сколько значащих цифр в двоичной записи десятичного числа 129?
1) 6
2) 2
3) 7
4) 8

✍ Решение:

• Выполним перевод из десятичной с-мы счисления в двоичную делением на 2, справа будем записывать остатки:
• Перепишем остатки снизу вверх, начиная с последней единицы, которая уже не делится на два:
• Посчитаем количество разрядов в получившемся двоичном числе. Их 8, и все они значащие (незначащими могут быть только нули слева, например, 010 — это то же самое, что 10). Правильный ответ под номером 4

Результат: 4

Сколько существует натуральных чисел x, для которых выполняется неравенство

Вычислите значение выражения AE₁₆ – 19₁₆.
В ответе запишите вычисленное значение в десятичной системе счисления.

✍ Решение:

• Переведем уменьшаемое и вычитаемое в десятичную систему счисления:
• Найдем разность:

Результат: 149

Петя и Коля загадывают натуральные числа. Петя загадал число Х, а Коля число У. После того, как Петя прибавил к Колиному числу 9, а Коля к Петиному числу 20, сумма полученных чисел при записи в двоичной системе счисления представляет собой пять единиц.

Чему равна изначальная сумма загаданных мальчиками чисел? Ответ запишите в двоичной системе счисления. Основание указывать не надо.

✍ Решение:

• Перепишем условие задачи в более понятном виде:
• Переведем 11111₂ в десятичную систему счисления и вычтем из полученного результата числа Коли и Пети, чтобы получить просто сумму (x + y):
• Переведем полученный результат в двоичную систему счисления:

Результат: 10

Укажите наибольшее четырёхзначное восьмеричное число, четверичная запись которого содержит ровно 2 тройки, не стоящие рядом. В ответе запишите только само восьмеричное число, основание системы счисления указывать не нужно.

✍ Решение:

• Вспомним, что в восьмеричной системе максимальная цифра 7, а в четверичной — 3. Попробуем выполнить перевод наибольшего восьмеричного числа в четверичную систему, не учитывая условие с нестоящими подряд тройками. Выполним перевод через двоичную систему счисления:
• Таким образом, чтобы получить наибольшее четверичное число, содержащие две не стоящие подряд тройки, нужно в его двоичной записи удалить по одной единице из всех групп, кроме двух, относящихся к старшим разрядам и не стоящих подряд:
• Переведем результат в 8-ю систему счисления:

Результат: 7352

Задан отрезок [a, b]. Число a – наименьшее число, восьмеричная запись которого содержит ровно 3 символа, один из которых – 3. Число b – наименьшее число, шестнадцатеричная запись которого содержит ровно 3 символа, один из которых – F.

Определите количество натуральных чисел на этом отрезке (включая его концы).

✍ Решение:

• Перепишем условие задачи в более понятном виде, подставив значения для чисел a и b:
• Переведем числа в десятичную систему счисления и найдем длину отрезка, выполнив разность этих чисел:

Результат: 205

Для хранения целого числа со знаком используется один байт.

Сколько единиц содержит внутреннее представление числа (-116)?

✍ Решение:

Для перевода отрицательного числа в двоичную систему счисления воспользуемся следующим алгоритмом:

Источник

Автор: Губаев Максим Станиславович

Место работы/учебы (аффилиация): МАОУ Лицей №39 города Нижний Тагил Свердловской области, 11 класс

Единый государственный экзамен по информатике необходим тем, кто планирует поступать в российские вузы на специальности, связанные с IT-технологиями. Этот экзамен нужен тем, кто хочет стать программистом, разработчиком, специалистом по информационным технологиям. Единый государственный экзамен по информатике будет проходить на компьютерах уже с 2021 года. Новая модель реализована в виде компьютерной системы тестирования, а ее апробация прошла в нашем городе осенью 2019. Смысл новой модели состоит в том, что все задания выпускники будут выполнять при помощи компьютеров и с применением различных языков программирования и программного обеспечения.

В настоящее время все большую популярность приобретает язык Python. Одна из причин популярности Python  – более простое и компактное оформление, чем в других языках. Это самый популярный язык общего назначения: он используется для машинного обучения, аналитике, разработке игр и в науке о данных. В данной работе будет применение языка Python в решении задач компьютерного ЕГЭ по информатике.

Объект работы – процесс решения задач компьютерного ЕГЭ по информатике.

Предмет работы – средства решения задач компьютерного ЕГЭ по информатике.

Цель работы – провести обзор возможностей языка программирования Python в решении задач компьютерного ЕГЭ по информатике.

Задачи:

• рассмотреть основы языка программирования Python;
• выделить типы задач компьютерного ЕГЭ по информатике и, по возможности, решить их средствами языка программирования Python;
• сравнить эффективность программ, написанных на языках Pascal, C и Python.

Методы решения задач на логику в ЕГЭ по
информатике

В спецификации контрольных измерительных материалов  для проведения в
2017 году  единого государственного экзамена  по информатике и ИКТ существуют  два
задания повышенной и высокой сложности (18,23) связанных со знанием основных
понятий и законов математической логики, которые для многих учащихся
действительно оказались сложными.

Уровни сложности заданий: Б – базовый; П – повышенный; В –
высокий.

Задание 18. Знание
основных понятий и законов математической логики

Рассмотрим способы решения
задания 18, которое является вариативным и может включать следующие возможные
варианты заданий:

1.               
задачи  с отрезками 

2.               
задачи  с множествами 

3.               
задачи  с делителями

4.               
задачи  с побитовыми операциями 1) Задачи с отрезками

Пример 1.1.         Задание
18 (демо 2015)

На числовой прямой даны два
отрезка: P = [37; 60] и Q = [40; 77].

Укажите наименьшую возможную
длину такого отрезка A, что формула

(x  P) → (((x  Q) / ¬(x  A)) →
¬(x 
P)) истинна при любом значении переменной х, т.е. принимает значение
1 при любом значении переменной х.  Решение

1.
Преобразуем формулу:

 P → ((Q / ¬
A) → ¬P) = ¬P / (¬Q / A / ¬P) =

= ¬P / ¬Q / A / ¬P
= ¬P / ¬Q / A  

¬P / ¬Q / A  = 1 

2.
Рисуем отрезки: 

Задача может быть сведена к типовой
задаче с множествами (задача 1)

A / X = 1       X =
¬P / ¬Q 

A_min
= ¬X      A_min = ¬(¬P / ¬Q) = P / Q         Ответ: 20

Пример 1.2. 
       Задание 18 (ТР 2017) На числовой прямой даны два отрезка: P =
[10, 34] и Q = [18,40]. 

Отрезок A таков, что формула  ¬(x

A) → ((x 
P) → ¬(x 
Q)) истинна при любом значении переменной х. Какое наименьшее количество точек,
соответствующих нечётным целым числам, может содержать отрезок A?

Решение

1. Преобразуем формулу: ¬ A
→ (P → ¬Q) = A / (P → ¬Q) =

= A / (¬P / ¬Q) = A
/ ¬P / ¬Q  

A / ¬P / ¬Q  = 1  2. Рисуем отрезки: 

3. Находим решение:  количество
точек, соответствующих нечётным целым числам на отрезке [18, 34] (34 – 18)/2 =
16/2 = 8

Ответ: 8

2)  Задачи
с множествами

Пример 2.1.         Задание
18 (ТР 2014)

Элементами множества А являются натуральные числа.
Известно, что выражение:

(x{2, 4, 6, 8, 10, 12})→(((x{3, 6, 9, 12, 15}) / ¬(xA))→ ¬(x{2, 4, 6, 8, 10, 12}))   истинно
(т. е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное значение суммы элементов
множества A.

Решение:

1.    
Обозначим:  P = {2, 4, 6, 8, 10, 12}   Q = {3, 6, 9, 12, 15} 

2.     Преобразуем
выражение:

P   
→ ((Q / ¬A) → ¬P) = = ¬P / (¬(Q / ¬A)) /
¬P) =

 = ¬P / ¬Q / A /
¬P = ¬P / ¬Q / A = 1

3.     Приводим
к типовой задаче с множествами:

A / (¬P / ¬Q)  = 1

A _min =
¬(¬P / ¬Q)  (см. задача 1) A _min = P / Q

Это числа, которые есть и в P, и в Q, а это числа 6 и 12.
Их сумма равна 18.

Ответ: 18

Пример 2.2.         Задание
18

Элементами множества А, 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)) истинно (т. е. принимает значение 1) при любом значении переменной х.
Определите наибольшее возможное количество элементов множества A.

Решение

Преобразуем выражение

(A → ¬ P) /
(¬Q → ¬A) = (¬A / ¬P) / (Q / ¬A) =

= ¬A / Q / ¬A / ¬P
/ Q / ¬P / ¬A  = ¬A / (Q / 1 / ¬P) / ¬P / Q =

= ¬A / ¬P / Q = 1

A _max = ¬P
/ Q  (задача 2)

Это числа, которые есть  в Q и нет в
P. A _max = {3, 9, 15, 21, 24, 27, 30} Ответ: 7

3)  Задачи
с делителями

Пример 3.1. 

Для какого наибольшего
натурального числа A выражение

¬ДЕЛ(x, A) → (¬ДЕЛ(x, 21) /
¬ДЕЛ(x, 35)) тождественно истинно (принимает значение 1 при любом
натуральном значении переменной  x)

Выражение ДЕЛ(n,
m) обозначает утверждение «натуральное число n делится без остатка на
натуральное число m» Решение:

1.    
Обозначим  A = ДЕЛ(x, A),  P = ДЕЛ(x, 21),  Q = ДЕЛ(x, 35)

2.     Преобразуем
выражение

¬A → (¬P / ¬Q)
= A / ¬P / ¬Q = 1

3.    
Приводим к типовой задаче с множествами:

A_min  =
¬(¬P / ¬Q)     (задача 1)

A_min  = P
/ Q

P   = {21, 42, 63,
84, …} – множество всех чисел, которые делятся на 21

Q = {35, 70, 105, 140, …} –
множество всех чисел, которые делятся на 35 P / Q = {21, 35, 42, 63, 70, 84,
105, 140…} – множество чисел, которые делятся на 21 или на 35.

A=ДЕЛ(x, A). Каким должно
быть число A, чтобы получить множество P/Q? A = 3, 5, 7, 14, 15, 21…  НОД (21, 35) = 7. 

 Ответ: 7

Пример 3.2. 

Для какого наименьшего
натурального числа A выражение

ДЕЛ(x, A) → (¬ДЕЛ(x, 21) / ДЕЛ(x,
35)) тождественно истинно (принимает значение 1 при любом натуральном
значении переменной  x)

Выражение ДЕЛ(n,
m) обозначает утверждение «натуральное число n делится без остатка на
натуральное число m» Решение:

1.    
Обозначим  A = ДЕЛ(x, A),  P = ДЕЛ(x, 21),  Q = ДЕЛ(x, 35)

2.     Преобразуем
выражение

A → (¬P / Q) =
¬A / ¬P / Q = 1

3.     Приводим
к типовой задаче с множествами: A_max  = ¬P / Q    (см. задача 2)

P   = {21, 42, 63,
84, …} – множество всех чисел, которые делятся на 21

Q = {35, 70, 105, 140, …} –
множество всех чисел, которые делятся на 35 ¬P / Q = {35, 70, 105,
140…} – множество всех чисел, которые не делятся на 21 плюс множество чисел,
которые делятся на 35. 

A=ДЕЛ(x, A). Каким должно быть A, чтобы
получить множество ¬P/Q? A = 5,
7, 35 …   Ответ: 5

4) Задачи с
побитовыми операциями

Пример 4.1.         Задание
18 (демо 2016)

Для какого наименьшего
неотрицательного целого числа А формула:

x&25 ≠ 0
→ (x&17 = 0 → x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при
любом неотрицательном целом значении переменной х)? Решение:

1.    
Введем обозначения:  P = (x&25 ≠ 0),  _Q =
(x&17 = 0),  A = (x&А ≠ 0)

2.    
Преобразуем выражение:

P→ (Q → A)
= 1, 

P  Q  A = 1

3.     Приводим
к типовой задаче с множествами: A_min = (P  Q ) =  P  Q    (задача
1)

4.    
Запишем числа 25 и 17 в двоичной системе:

номер бита 4 3 2 1 0

25₁₀ = 1 1 0 0 1₂    x&25
≠ 0 хотя бы один из битов 4,3,0  должен быть = 1      

17₁₀
= 1 0 0 0 1₂    x&17 = 0  биты  4 и 0 должны быть равны 0 
A_min=0 1 0 0 0₂  = 8₁₀      x&А ≠ 0 
бит 3 должен быть равен 1 

Как же описать
эту операцию?  В числе A нужно обязательно сделать единичными биты,
которые равны 1 в числе P и равны 0 в числе Q. Ответ: 8 Пример
4.2. 

Для какого наименьшего
неотрицательного целого числа А формула:

x&35 ≠ 0
→ (x&31 = 0 → x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при
любом неотрицательном целом значении переменной х)? Решение

1.    
Введем обозначения: P = (x&35 ≠ 0),  _Q =
(x&31 = 0),     A = (x&А ≠ 0)

2.     Преобразуем
выражение:

P→ (Q → A)
= 1

P  Q  A = 1

3.    
Приводим к типовой задаче с множествами:

A_min = (P  Q ) = P  Q    (см.
задача 1)

4.     Запишем
числа 35 и 31 в двоичной системе:

номер бита 5 4 3 2
1 0

35₁₀ = 1 0 0 0 1 1₂    x&35 ≠ 0 хотя
бы один из битов 5,1,0 должен быть=1 

31₁₀ = 0 1 1 1 1 1₂    x&31 = 0  биты 
4, 3, 2, 1, 0 должны быть равны 0 A_min = 1 0 0 0 0 0₂  = 32₁₀      x&А ≠
0    бит 5 должен быть равен 1 

В числе A нужно обязательно сделать
единичными биты, которые равны 1 в числе P и равны 0 в числе Q. Ответ:
32

Пример 4.3.         Задание
18 (демо 2017)

Для какого наименьшего
неотрицательного целого числа А формула x&51 = 0 / (x&41 = 0
→ x&А ≠ 0)

тождественно истинна (т.е. принимает значение 1 при
любом неотрицательном целом значении переменной х)? Решение:

1.    
Введем обозначения: Z₅₁= (x&51 = 0), Z₄₁
= (x&41 = 0), A
=(x&А ≠ 0)

2.    
Преобразуем выражение:

     Z₅₁ +
(Z₄₁ → A)
= Z₅₁ + Z₄₁
+ A
= 

= (Z41  A) → Z51 = Z41 or A → Z51  

3.     Запишем
числа 51 и 41 в двоичной системе:

номер бита 5 4 3 2 1 0

     51₁₀
= 1 1 0 0 1 1₂

     4110 = 1 0 1 0 0 12                       

      Amin =   1 0 0 1 02  = 1810          

В числе A нужно обязательно сделать единичными биты,
которые равны 1 в числе P и равны 0 в числе Q.

Ответ: 18

Задание 23. Анализ
уравнений или систем логических уравнений

Решение — битовый
вектор

Поскольку все переменные, входящие в решение уравнения
или системы уравнений, логические (0 или 1), решение можно рассматривать как
цепочку нулей и единиц длиной N. Такие цепочки называют битовыми цепочками,
или битовыми векторами. 

При анализе систем логических уравнений удобно не
исключать поочередно неизвестные, а рассматривать битовый вектор–решение как
целое, как единый объект. Результатом такого анализа будет описание множества
векторов-решений, которое позволит подсчитать количество решений. До того, как
исследовать возможные решения, систему бывает полезно упростить или
использовать замену переменных. 

Вначале мы разберем несколько простых уравнений и систем, а затем перейдем
к более сложным, которые использовались в задачах ЕГЭ прошлых лет.

Простые случаи:

Пример 1. 

Найти число решений уравнения 

(х₁ = х₂)  (х₂ = х₃)
…  (х₄
= х₅) = 1.

Решение:

Все “сомножители” имеют форму х_i =х_i+1, они
должны быть равны 1. Это значит, что любые два соседних бита должны быть равны.
Существует всего две таких цепочки: 000000, 111111. Ответ:  2 

Пример 2. 

Найти число решений уравнения 


(х₁ = х₂) 
 (х₂
= х₃) …  (х₅
= х₆) = 1.

Решение:

Все “сомножители” имеют форму (x_i=x_i+1),
они должны быть равны 1. Это значит, что каждые два соседних бита должны быть
различны, то есть нули и единицы в битовой цепочке чередуются. Существует всего
две таких цепочки: 101010, 010101. Ответ:  2 

Пример 3. 

Найти число решений уравнения 

(х₁ →
х₂) 
(х₂ → х₃) …  (х₅
→ х₆) = 1.

Решение (вариант 1):

Подобно рассмотренным выше
задачам, все импликации: 

(х₁ →
х₂), …, (х₅ → х₆)
должны быть истинны. 

Импликация a →b ложна только при a = 1 и b
= 0.  Поэтому, если битовый вектор X = х1 х2… х6 — решение данного
уравнения, и в нем встретилась единица, то правее нее будут только единицы
(сочетание “10” запрещено!). Таким образом, уравнение имеет семь решений:

000000, 000001, 000011, 000111, 001111, 011111, 111111.

Каждое решение определяется тем,
в какой позиции первый раз встречается единица: на 1-м, 2-м, …, 6-м месте или
вообще не встречается. Ответ:  7 

Решение (вариант 2):

Такое уравнение может быть
записано в виде системы уравнений:

(х₁ →
х₂) = 1

(х₂ →
х₃) = 1

…

(х₅ →
х₆) = 1.

Для первого уравнения (х1→х2)=1
существует 3 решения: 00, 01, 11.

Для системы из двух уравнений: 

(х₁ →
х₂) = 1

(х₂ → х₃)
= 1 существует 4 решения: 000, 001, 011, 111. Решая систему из 3 уравнений
можно увидеть, что добавление в систему еще одного уравнения добавляет еще 1
решение. Таким образом, для такой системы уравнений, в которой  есть n
переменных число решений равно n+1.  Ответ:  7 

Пример 4. 

Найти число решений системы
уравнений 

(¬ х₁ / х₂) = 1

(¬ х₂ / х₃) = 1

(¬ х₃ / х₄) = 1

…

(¬ х₁₀₂₂ / х₁₀₂₃) = 1.

Для такой системы уравнений, в которой  есть n переменных число
решений равно n+1.  Ответ:  1024 

Пример 5. 

Найти число решений уравнения 

((х₁  /  х₂)→ х₃)  ((х₂ 
/  х₃)→
х₄) …
 ((х₄ 
/  х₅)→
х₆) = 1.

Решение:

Все сомножители
имеют форму ((х_i + х_i+1)→ х_i+2),
они должны быть равны 1, то есть недопустима импликация 1 → 0. 

Поскольку левая часть импликации
— это логическая сумма двух соседних битов, а правая — следующий за ними бит,
можно сделать вывод: слева от каждого нулевого бита (начиная с третьего) должны
обязательно стоять два нуля. 

Этому условию удовлетворяют
цепочки вида: все нули, потом — все единицы: 111111, 011111, 001111, 000111, 
000011, 000001, 000000. 

Кроме того, этому уравнению
удовлетворяет еще одна цепочка: 101111.  Всего уравнение имеет восемь решений.

Ответ:  8 

Задания из демонстрационных вариантов ЕГЭ

Покажем, как использовать такой подход для решения
систем логических уравнений из демонстрационных вариантов ЕГЭ по информатике  Пример
6.

Сколько различных решений имеет система логических
уравнений 

(x₁  x₂)
 (x₂
 x₃)
 (x₃
 x₄)
= 1

(y₁  y₂)
 (y₂
 y₃)
 (y₃
 y₄)
= 1 (z₁  z₂)
 (z₂
 z₃)
 (z₃
 z₄)
= 1  x₁  y₂
 z₃ 
= 0 где x₁,
…, x₄, y₁, …, y₄, z₁, …, z₄, – логические
переменные? 

В ответе не нужно перечислять все различные наборы
значений переменных, при которых выполнено данное равенство. В качестве ответа
нужно указать количество таких наборов.

Решение (использование свойств битовых цепочек): 1) перепишем систему с более
понятными обозначениями:

(x₁ 
x₂)(x₂ 
x₃)(x₃ 
x₄) 1

(y₁ 
y₂)(y₂ 
y₃)(y₃ 
y₄) 1

(z₁ 
z₂)(z₂ 
z₃)(z₃ 
z₄) 1 x₁ 
y₂ 
z₃ 
0

2)   
первые 3 уравнения однотипны; рассмотрим первое из них:

(x₁ 
x₂)(x₂ 
x₃)(x₃ 
x₄) 1

3)   
рассмотрим решение этого уравнения как битовую цепочку X  x1x2x3x4

4)   
все импликации должны быть равны 1, в цепочке X запрещена
комбинация 10, поэтому после первой единицы далее следуют только единицы; вот
все 5 решений X:

X 
=  0000    0001    0011    0111    1111

5)    второе и
третье уравнения не зависят от первого и имеют такую же структуру; вот все их
решения Y 
y₁y₂y₃y₄ и Z  z₁z₂z₃z₄ :

Y 
=  0000    0001    0011    0111    1111

Z 
=  0000    0001    0011    0111    1111

6)    если бы
система состояла бы только из первых трёх уравнений, общее количество решений
было бы равно 5 ∙ 5 ∙ 5 = 125 

7)    теперь
рассмотрим последнее уравнение, связывающее X, Y и Z: x₁  y₂  z₃  0

    таким
образом, нужно исключить все решения, где x₁  y₂  z₃ 1

9)   
у нас есть одно решение X
с x₁ 1, два решения Y с y₂ 1 и три решения Z с z₃ 1; поэтому из 125 нужно отбросить 1 ∙ 2 ∙ 3 = 6 решений;
остаётся 125 – 6 = 119 решений Ответ: 119.

Пример 7.

Сколько различных решений имеет система логических
уравнений 

(x₁  y₁)
 ((x₂
 y₂)
 (x₁
 y₁))
= 1

(x₂  y₂)
 ((x₃
 y₃)
 (x₂
 y₂))
= 1 …

(x₅  y₅)
 ((x₆
 y₆)
 (x₅
 y₅))
= 1 x₆  y₆ 
= 1

где
x₁, …, x₇, y₁, …, y₇, –
логические переменные? В ответе не нужно перечислять все различные наборы
значений переменных, при которых выполнено данное равенство. В качестве ответа
нужно указать количество таких наборов.

Решение
(использование свойств битовых цепочек):

1)     
перепишем систему
с более понятными обозначениями:

(x₁  y₁)(x₂ 
y₂ 
x₁ 
y₁) 1

(x₂  y₂)(x₃ 
y₃ 
x₂ 
y₂) 1

                       L                                     

(x₅ 
y₅)(x₆ 
y₆ 
x₅ 
y₅) 1 x₆ 
y₆ 1

2)     
первые 5 уравнений однотипны, отличаются только сдвигом номеров
переменных

3)     
будем рассматривать каждое решение как пару битовых цепочек

X  x1x2x3x4x5x6 и Y  y1y2y3y4y5y6

4)     
выполним замену переменных z₁  x₁  y₁, z₂ 
x₂ 
y₂, K, z₆ 
x₆ 
y₆

5)     
тогда получаем систему

(z₂ 
z₁) 1

(z₃ 
z₂) 1

L

(z₆ 
z₅) 1 которую можно свернуть в
одно уравнение:

(z₂ 
z₁)(z₃ 
z₂)K(z₆ 
z₅) 1

6)     
в каждой скобке запрещена комбинация 10, это значит, что в цепочке Z  z₁z₂z₃z₄z₅z₆ запрещена комбинация 01

7)     
это значит, что цепочка Z имеет структуру «сначала все единицы, потом все
нули», вот все 7 возможных цепочек длиной 6: 111111 111000 000000 111110 110000
111100 100000

     
теперь нужно перейти к исходным переменным, то есть, к цепочкам

X  x1x2x3x4x5x6 и Y  y1y2y3y4y5y6

9)     
пусть z_i 
x_i 
y_i 
0; в исходном уравнении есть ещё
ограничение

(xi 

y_i ) 1, это та скобка, которую мы «временно забыли»,
получаем систему

z_i 
x_i 
y_i 
0

                                           

xi  yi 1 первое уравнение означает,
что x_i 
y_i , второе говорит о
том, что, по крайней мере, одно из этих значение равно 1; таких пар две: (0;1)
и (1;0)

10)  это
означает, что каждый ноль в цепочке
Z даёт два
решения в исходных переменных

11)  теперь исследуем вариант z_i 
x_i 
y_i 1; добавляя ограничение

(xi  
y_i ) 1, получаем систему

z_i 
x_i 
y_i 1

                                           

xi

yi 1 первое уравнение означает,
что x_i 
y_i 1, второе говорит о том, что, по крайней мере, одно
из этих значение равно 1; существует только одна такая пара: (1;1)

12) 
таким образом, каждый ноль в цепочке Z увеличивает в два раза число решений в исходных переменных,
а единицы не меняют количества

13)  например,
цепочка Z = 111111 не
содержит нулей и даёт только одно решение

14) 
цепочка Z = 111110 содержит
один ноль и даёт 2¹ =
2 решения

15)  цепочка Z = 111100 содержит
два ноля и даёт 2² =
4 решения

16) 
общее количество решений системы
2⁰ + 2¹ + 2² +2³ + 2⁴ +
2⁵ +2⁶ = 127. Ответ: 127.

Пример 8  Задание 23
(ТР 2017)

Сколько существует различных наборов
значений логических переменных  x₁, x₂, … x₅,
y₁, y₂, … y₅, которые удовлетворяют всем
перечисленным ниже условиям?  

¬ (x₁ / y₁)
/ (x₂ / y₂) = 1 

¬ (x₂ / y₂)
/ (x₃ / y₃) = 1 

¬ (x₃ / y₃)
/ (x₄ / y₄) = 1 

¬ (x₄ / y₄) / (x₅ / y₅)
= 1  

В ответе не нужно перечислять все
различные наборы значений переменных x₁, x₂, … x₅,
y₁, y₂, … y₅, при которых выполнена данная
система равенств.  В качестве ответа Вам нужно указать количество таких
наборов.  

Решение (использование
свойств битовых цепочек): 1) Перепишем
систему уравнений, используя свойство импликации:

(x₁ 
y₁) 
(x₂ 
y₂) = 1

(x₂ 
y₂) 
(x₃ 
y₃) = 1

(x₃ 
y₃) 
(x₄ 
y₄) = 1

(x₄ 
y₄) 
(x₅ 
y₅) = 1

2)     
Все уравнений системы однотипны, отличаются только сдвигом
номеров переменных

3)     
будем рассматривать каждое решение как пару битовых цепочек X  x1x2x3x4x5
и Y 
y1y2y3y4y5

4)     
выполним замену переменных z₁  x₁ y₁, z₂ 
x₂ 
y₂, K, z₅ 
x₅ 
y₅

5)     
тогда получаем систему

(z₂ 
z₁) 1

(z₃ 
z₂) 1

L

(z₆ 
z₅) 1 которую можно свернуть в
одно уравнение:

(z₂ 
z₁)(z₃ 
z₂)K(z₆ 
z₅) 1

6)     
в каждой скобке запрещена комбинация 10, это значит, что в цепочке Z  z₁z₂z₃z₄z₅z₆ запрещена комбинация 01

7)     
это значит, что цепочка Z имеет структуру «сначала все единицы, потом все
нули», вот все 6 возможных цепочек длиной 5:

                         11111 11110
     11100     11000     10000     00000

     
теперь нужно перейти к исходным переменным, то есть, к цепочкам

X  x1x2x3x4x5
и Y 
y1y2y3y4y5

9)     
пусть z_i 
x_i 
y_i 
0; конъюнкция равно нулю в трех
случаях.  

Это означает что каждый ноль в
цепочке Z даёт три решения в исходных переменных.

10) 
теперь
исследуем вариант z_i 
x_i 
y_i 1; конъюнкция равно единице
только в одном случае. Это означает, что каждая единица в цепочке Z даёт
одно решение в исходных переменных.

11) 
таким образом, каждый ноль в цепочке Z увеличивает в три раза число решений в исходных переменных,
а единицы не меняют количества

12)  например,
цепочка Z = 11111 не
содержит нулей и даёт только одно решение

13) 
цепочка Z = 11110 содержит
один ноль и даёт 3¹ =
3 решения

14)  цепочка Z = 11100 содержит
два ноля и даёт 3² =
9 решений и так далее

15)  общее
количество решений системы 3⁰
+ 3¹ + 3² +3³ + 3⁴ + 3⁵
= 364.

Ответ: 364