Главная › Новости

Задачи ЕГЭ по информатике

Опубликовано: 05.09.2018

Простое решение задания №2. Таблицы истинности. ЕГЭ по информатике и ИКТ - 2016.

Презентация «Задачи ЕГЭ по информатике» . Размер 703 КБ. Автор: 11 .

содержание презентации «Задачи ЕГЭ по информатике.pptx»

№	Слайд	Текст
1		Логика в задачах ГИА и ЕГЭ по информатике Логика в задачах ГИА и ЕГЭ по информатике. Вишневская М.П., учитель информатики МАОУ «Гимназия №3» г. Саратова 10.02.2014. Решение задания №27. ЕГЭ по информатике - 2017. Демоверсия ФИПИ.
2		Кодификатор и спецификация Кодификатор и спецификация ГИА_2014. Кодификатор: Раздел 1. Информационные процессы Раздел 1.3.3 Логические значения, операции, выражения Спецификация: На уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как: ………………………………………………………. ? основные элементы математической логики; ………………………………………………………. Решение задания №1. Демо ЕГЭ по информатике - 2019
3		Задания ГИА Задания ГИА. Решение: 0. 0. Число >50 число нечётное. Ответ: 123. НЕ (число >50) ИЛИ (число чётное) = 0.
4		Ответ Задания ГИА. Ответ: 5. 1. 1. 1. 1. 0. 1. 0. 1. 1. 0. 1. 0. 1. 0. 0. 1. 1. 1. 1. 1. 1. 1. 0. 0.
5		Ответ: АГБВ Задания ГИА. Ответ: АГБВ.
6		Информация и информационные процессы Кодификатор и спецификация ЕГЭ_2014. Кодификатор: Раздел 1. Информация и информационные процессы 1.5.1 Высказывания, логические операции, кванторы, истинность высказывания Спецификация: В КИМ ЕГЭ по информатике не включены задания, требующие простого воспроизведения знания терминов, понятий, величин, правил (такие задания слишком просты для итогового экзамена). …………………………………………………………………………… Формировать для логической функции таблицу истинности и логическую схему; формулировать запросы к базам данных и поисковым системам.
7		Задания ЕГЭ Задания ЕГЭ.
8		Задания ЕГЭ Задания ЕГЭ.
9		Задания ЕГЭ Задания ЕГЭ.
10		Задания ЕГЭ Задания ЕГЭ.
11		Преемственность Задания ЕГЭ - ГИА. Прослеживается преемственность между заданиями: №2 и А3 (Умение применять логические операции НЕ, И, ИЛИ); №18 и В12 (поиск в Интернете); возможно, между №12 и А6 (поиск в базах данных). Наибольшую сложность представляют задания А10 и В15 (!).
12		Логические операции Задание ЕГЭ А10. Логические операции с утверждениями о множествах связаны с операциями над множествами (теоретико-множественными операциями). Пусть А, В – некоторые множества. Их элементы принадлежат некоторому универсальному множеству U (в зависимости от задачи это может быть, например, множество целых чисел, множество точек на прямой и т.д.). Тогда верно следующее: Пусть X - произвольный элемент универсального множества U. Тогда следующие высказывания эквивалентны (?):
13		Подмножество Задание ЕГЭ А10. 2. Пусть А ? В, т.е. А – подмножество В, х – произвольный элемент универсального множества U. Тогда истинно высказывание: (x ? A) ? (x ? B). Обратно, пусть высказывание (x ? A) ? (x ? B) истинно при любом x ? U. Тогда А ? В. Обозначения: A ? B – пересечение множеств А и В A ? B – объединение множеств А и В U \ A – дополнение множества А до универсального множества U.
14		Даны два отрезка Задание ЕГЭ А10. На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула. Тождественно истинна, то есть принимает значение 1 при любом значении переменной х. 1) [0, 3] 2) [3, 11] 3) [11, 15] 4) [15, 17].
15		Преобразуем формулу Решение. Преобразуем формулу. По определению, (F ? G) ? (? F \/ G) Из формулы (1) получаем: ?(x? A) \/ (х?Р) \/ (х?Q) (2) Далее, (х?Р) \/ (х?Q) ? x?(P?Q) при любых x, P, Q. По условию, P = [2,10], Q = [6,14]. Т.о. P?Q = [2,14]. Перепишем формулу (2): ?(x? A) \/ (х?[2,14]).
16		Вернемся к импликации Решение. Вернемся к импликации: (x? A) ? (х?[2,14]) Эта формула истинна тогда и только тогда, когда принадлежность числа х отрезку А влечет принадлежность числа х отрезку [2,14]. Т.е. отрезок А должен быть подмножеством отрезка [2,14]. Из четырех предложенных отрезков этому условию удовлетворяет только отрезок [3,11]. 1) [0, 3] 2) [3, 11] 3) [11, 15] 4) [15, 17]. Ответ: 2.
17		Проверяются умения Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка.
18		Без чего не обойтись Без чего не обойтись!
19		Задачи ЕГЭ по информатике ! Без чего не обойтись!
20		Условные обозначения Условные обозначения. конъюнкция :A /\ B , A? B, AB, А&B, A and B дизъюнкция: A \/ B , A+ B, A | B, А or B отрицание: ? A , А, not A эквиваленция: A ? В, A ? B, A ? B исключающее «или»: A? B , A xor B.
21		Метод замены переменных Метод замены переменных. Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ? x2) \/ (x3 ? x4)) /\ (¬(x1 ? x2) \/ ¬(x3 ? x4)) =1 ((x3 ? x4) \/ (x5 ? x6)) /\ (¬(x3 ? x4) \/ ¬(x5 ? x6)) =1 ((x5 ? x6) \/ (x7 ? x8)) /\ (¬(x5 ? x7) \/ ¬(x7 ? x8)) =1 ((x7 ? x8) \/ (x9 ? x10)) /\ (¬(x7 ? x8) \/ ¬(x9 ? x10)) =1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.).
22		Упрощаем, выполнив замену переменных Шаг 1. Упрощаем, выполнив замену переменных. Решение. После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3 ) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4 ) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5 ) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) = t1? t2 = ¬(t1 ? t2 ) =1. t1 = x1? x2 t2 = x3? x4 t3 = x5? x6 t4 = x7? x8 t5 = x9? x10. ¬(t1 ? t2 ) =1 ¬(t2 ? t3 ) =1 ¬(t3 ? t4 ) =1 ¬(t4 ? t5 ) =1.
23		Анализ системы Шаг 2. Анализ системы. t1. t2. t3. t4. t5. ¬(t1 ? t2 ) =1 ¬(t2 ? t3 ) =1 ¬(t3 ? t4 ) =1 ¬(t4 ? t5 ) =1. 0. 1. 0. 1. 0. 1. 0. 1. 0. 1. Т.к. tk = x2k-1 ? x2k (t1 = x1? x2,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk=0 соответствуют две пары - (0,1) и (1,0) , а tk=1 – пары (0,0) и (1,1).
24		Подсчет числа решений Шаг 3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 25 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64.
25		Метод исключения части решений Метод исключения части решений. Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,…, y5, которые удовлетворяют всем перечисленным ниже условиям: (x1? x2)?(x2? x3)?(x3? x4)?(x4? x5) =1; ( y1? y2)?( y2? y3)?( y3? y4)?( y4? y5) =1; y5? x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y1,y2,…, y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.
26		Последовательное решение уравнений Решение. Шаг 1. Последовательное решение уравнений. Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1 ? 0, во всех других случаях (0 ? 0, 0 ? 1, 1 ? 1) операция возвращает 1. Запишем это в виде таблицы: Х1. 1. 0. Х2. 1. 0 1. Х3. 1. 0 1 1. Х4. 1. 0 1 1 1. Х5. 1. 0 1 1 1 1.
27		Набор решений Шаг1. Последовательное решение уравнений. Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6=36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5? x5 =1. Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0.
28		Полученные решения Сопоставим полученные решения. Там, где y5=1, не подходят x5=0. таких пар 5. Количество решений системы : 36-5=31. Ответ: 31 Понадобилась комбинаторика!!!
29		Метод динамического программирования Метод динамического программирования. Сколько различных решений имеет логическое уравнение x1 ? x2 ? x3 ? x4 ? x5 ? x6 = 1, где x1, x2, …, x6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
30		Анализ условия Решение Шаг 1. Анализ условия. NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации! Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X1 ? X2) ? X3) ? X4) ? X5) ? X6 = 1.
31		Выявление закономерности Шаг 2. Выявление закономерности. Рассмотрим первую импликацию, X1 ? X2. Таблица истинности: X1. X2. X1 ?X2. 0. 0. 1. 0. 1. 1. 1. 0. 0. 1. 1. 1. Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.
32		Закономерности Шаг 2. Выявление закономерности. Подключив к результату первой операции x3 , получим: F(x1,x2). x3. F(x1,x2)?x3. 0. 0. 1. Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3). 0. 1. 1. 1. 0. 0. 1. 1. 1. 1. 0. 0. 1. 1. 1. 1. 0. 0. 1. 1. 1.
33		Вывод формулы Шаг 3. Вывод формулы. Т.о. можно составить формулы для вычисления количества нулей Ni и количества единиц Ei для уравнения с i переменными: ,
34		Заполнение таблицы Шаг 4. Заполнение таблицы. Заполним слева направо таблицу для i=6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: Число переменных. 1. 2. 3. 4. 5. 6. Число нулей Ni. 1. 1. 3. 5. 11. 21. Число единиц Ei. 1. 2*1+1=3. 2*1+3=5. 11. 21. 43. Ответ: 43. :
35		Метод с использованием упрощений логических выражений Метод с использованием упрощений логических выражений. Сколько различных решений имеет уравнение ((J ? K) ?(M ? N ? L)) ? ((M ? N ? L) ? (¬J ? K)) ? (M ? J) = 1 где J, K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
36		Введем замену переменных Решение. Заметим, что J ? K = ¬J ? K Введем замену переменных: J ? K=А, M ? N ? L =В Перепишем уравнение с учетом замены: (A ? B)?(B ? A) ?(M ? J)=1 4. (A ? B) ?(M ? J)=1 5. Очевидно, что A ? B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M ? J=1 Это возможно, если: M=J=0 M=0, J=1 M=J=1.
37		Нет решений Решение. Т.к. A ? B, то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые , 4 решения: ¬J ? K= M ? N ? L. K. N. L. 0. 0. 0. 0. 0. 1. 0. 1. 0. 0. 1. 1.
38		Решения Решение. 10. При M=J=1 получаем 0+К=1*N*L, или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8. K. N. L. 0. 0. 0. 0. 0. 1. 0. 1. 0. 1. 1. 1.
39		Источники информации Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/, [Электронный ресурс]. http://kpolyakov.narod.ru/school/ege.htm, [Электронный ресурс].
«Задачи ЕГЭ по информатике»