Тесты
<<  Задания ЕГЭ по информатике Экзамен ГИА по информатике  >>
Логика в задачах ГИА и ЕГЭ по информатике
Логика в задачах ГИА и ЕГЭ по информатике
Кодификатор и спецификация
Кодификатор и спецификация
Задания ГИА
Задания ГИА
Ответ
Ответ
Ответ: АГБВ
Ответ: АГБВ
Информация и информационные процессы
Информация и информационные процессы
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Задания ЕГЭ
Преемственность
Преемственность
Логические операции
Логические операции
Подмножество
Подмножество
Даны два отрезка
Даны два отрезка
Преобразуем формулу
Преобразуем формулу
Вернемся к импликации
Вернемся к импликации
Проверяются умения
Проверяются умения
Без чего не обойтись
Без чего не обойтись
Задачи ЕГЭ по информатике
Задачи ЕГЭ по информатике
Условные обозначения
Условные обозначения
Метод замены переменных
Метод замены переменных
Упрощаем, выполнив замену переменных
Упрощаем, выполнив замену переменных
Анализ системы
Анализ системы
Подсчет числа решений
Подсчет числа решений
Метод исключения части решений
Метод исключения части решений
Последовательное решение уравнений
Последовательное решение уравнений
Набор решений
Набор решений
Полученные решения
Полученные решения
Метод динамического программирования
Метод динамического программирования
Анализ условия
Анализ условия
Выявление закономерности
Выявление закономерности
Закономерности
Закономерности
Вывод формулы
Вывод формулы
Заполнение таблицы
Заполнение таблицы
Метод с использованием упрощений логических выражений
Метод с использованием упрощений логических выражений
Введем замену переменных
Введем замену переменных
Нет решений
Нет решений
Решения
Решения
Источники информации
Источники информации
Презентация «Задачи ЕГЭ по информатике». Размер 703 КБ. Автор: 11.

Загрузка...

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

содержание презентации «Задачи ЕГЭ по информатике.pptx»
СлайдТекст
1 Логика в задачах ГИА и ЕГЭ по информатике

Логика в задачах ГИА и ЕГЭ по информатике

Логика в задачах ГИА и ЕГЭ по информатике. Вишневская М.П., учитель информатики МАОУ «Гимназия №3» г. Саратова 10.02.2014.

2 Кодификатор и спецификация

Кодификатор и спецификация

Кодификатор и спецификация ГИА_2014. Кодификатор: Раздел 1. Информационные процессы Раздел 1.3.3 Логические значения, операции, выражения Спецификация: На уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как: ………………………………………………………. ? основные элементы математической логики; ……………………………………………………….

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, [Электронный ресурс].

«Задачи ЕГЭ по информатике»
Загрузка...
Сайт

5informatika.net

115 тем
5informatika.net > Тесты > Задачи ЕГЭ по информатике.pptx