Логика и алгоритмы
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)

Слайд 1

Слайд 2

Соответствие заданий ЕГЭ-2021 и ЕГЭ-2020  ЕГЭ- 20 21 ЕГЭ- 20 20 Сложность Время Материал 1 3 Б 3 Анализ информационных моделей (графов) 2 2 Б 3 Таблицы истинности логических функций 3 4-1 Б 3 Поиск и сортировка в базах данных 4 5 Б 2 Кодирование и декодирование 5 6-1 Б 4 Выполнение и анализ простых алгоритмов 6 8 Б 4 Анализ программы с циклом 7 9-1 Б 5 Кодирование растровых изображений 8 10 Б 4 Кодирование данных, комбинаторика  9 – ( К 10) Б 6 Встроенные функции в электронных таблицах  10 – Б 6 Поиск слов в текстовом документе

Слайд 3

Соответствие заданий ЕГЭ-2021 и ЕГЭ-2020  ЕГЭ- 20 21 ЕГЭ- 20 20 Сложность Время Материал 11 13 П 3 Вычисления информационного объёма 12 14 П 4 Выполнение алгоритмов для исполнителя 13 15 П 3 Поиск количества путей в графе 14 16 П 5 Позиционные системы счисления 15 18 П 5 Основные понятия математической логики.  16 11 (К11) П 9 Вычисление значений рекурсивной функции.  17 К4 П 15 Проверка делимости  18 – П 6 Динамическое программирование 19 26 П 6 Теория игр 20 26 П 6 Теория игр 21 26 П 10 Теория игр 22 2 0 П 7 Анализ программы с циклами и ветвлениями 23 22 П 8 Динамическое программирование

Слайд 4

РАССМАТРИВАЕМЫЕ ЗАДАНИЯ ОГЭ  O ГЭ- 20 21 Сложность Время Материал 1 Б 3 Единицы измерения количества информации 2 Б 4 Кодирование и декодирование информации 3 Б 3 Логические значения, операции, выражения 4 Б 3 Моделирование объектов и процессов 5 Б 6 Алгоритм, свойства алгоритмов, способы записи алгоритмов 6 Б 4 7 Б 3 Сохранение информационных объектов из компьютерных сетей и ссылок на них для индивидуального использования (в том числе из Интернета) 8 П 5 Поиск информации 9 П 4 Проектирование и моделирование 10 Б 3 Единицы измерения количества информации

Слайд 5

РАССМАТРИВАЕМЫЕ ЗАДАНИЯ ОГЭ  O ГЭ- 20 21 Сложность Время Материал 11 Б 6 Поиск информации в файлах и каталогах компьютера 12 Б 6 Определение количества и информационного объёма файлов, отобранных по некоторому условию 13 П 25 Создавать презентации (вариант задания 13.1) или создавать текстовый документ (вариант задания 13.2) 14 В 30 Умение проводить обработку большого массива данных с использованием средств электронной таблицы 15 В 45 Создавать и выполнять программы для заданного исполнителя (вариант задания 15.1) или на универсальном языке программирования (вариант задания 15.2)

Слайд 6

Немного теории если в выражении нет скобок, сначала выполняются все операции «отрицание», затем – «конъюнкция», затем – «дизъюнкция», «импликация», «эквивалентность» дизъюнкция A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно) конъюнкция A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно) импликация А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно эквивалентность А  B равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1

Слайд 7

Задание 2 Уровень: базовый Время: 3 мин Тема : Анализ таблиц истинности логических выражений. Что проверяется: Умение строить таблицы истинности и логические схемы. Основные способы решения: - решение логического уравнения - построение таблицы истинности с помощью Excel

Слайд 8

Способы решения задания 2 Решение логического уравнения F = ( x  y )  ¬( y  z )  ¬ w = 1 1. 2 . (x, y, z, w) = (1, 0, 1, 0) (x, y, z, w) = (0, 1, 0, 0) (x, y, z, w) = (1, 1, 0, 0) Ответ: zyxw z y x w F 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1

Слайд 9

Способы решения задания 2 Построение таблицы истинности с помощью Excel F = ( x  y )  ¬( y  z )  ¬ w = 1 заполняем первую часть таблицы, перечисляя все комбинации переменных в порядке возрастания двоичного кода. для каждой строчки определяем выражения, входящие в логическое произведение, а затем – значение функции. сортируем строки таблицы по столбцу H по убыванию. удаляем строки, где функция равна 0; можно также скрыть вспомогательные столбцы E, F, G дальше рассуждаем так же, как и при теоретическом решении Ответ: zyxw 1 2 3-4

Слайд 10

Задание 2 (ПРИМЕР)

Слайд 11

Способы решения задания 2 Решение логического уравнения F = ( x  ¬ y  ¬ z )  (¬ x  y ) = 1 1) (x, y, z) = (0, 1, 0) 2) (x, y, z) = (0, 0, 0); (0, 0, 1) 3) (x, y, z) = (1, 1, 1); (1, 1, 0) Ответ: zyx

Слайд 12

Способы решения задания 2 Построение таблицы истинности с помощью Excel заполняем первую часть таблицы, перечисляя все комбинации переменных в порядке возрастания двоичного кода. для каждой строчки определяем выражения, входящие в логическое произведение, а затем – значение функции. делаем сложную сортировку сначала по столбцу С, затем по столбцу В по возрастанию. можно скрыть вспомогательные столбцы D , E Получаем таблицу идентичную в задании Ответ: zyx 1 2 3-5

Слайд 13

Задание 15 (ЕГЭ), Задание 3 (ОГЭ) Уровень: повышенный Время: 5 мин Тема : Основные понятия математической логики. Что проверяется: Знание основных понятий и законов математической логики Основные способы решения: - аналитическое - программное Виды заданий: - предикаты ДЕЛ( n, m) - побитовая конъюнкция - числовая плоскость - множества Уровень: базовый Время: 3 мин Тема : Основные понятия математической логики. Что проверяется: Логические значения, операции, выражения Основные способы решения: - аналитическое Виды заданий: - значение логического выражения Решение: (x > 16) и (x четно ) => x = 18

Слайд 14

Задание 15 (Предикаты ДЕЛ( N, m ))

Слайд 15

Аналитическое решение задания 15 Решение задач с предикатом ДЕЛ( n, m ) введём обозначения: ДЕЛ( x,А ) = A, ДЕЛ(x, 6 ) = D 6 , ДЕЛ(x, 9 ) = D 9 перепишем выражение в виде раскроем импликации: согласно закону де Моргана получим: сведём выражение к единственной импликации: сформулируем правило, которое мы получили: если значение x делится на 6 и делится на 9, то оно делится на A ; если значение x делится на 6 и делится на 9, то оно делится на наименьшее общее кратное НОК(6,9)=18, поэтому наибольшее значение A , удовлетворяющее условию, равно 18 Ответ: 18

Слайд 16

Программное решение задания 15 Решение задач с предикатом ДЕЛ( n, m ) преобразуем исходную формулу в ДЕЛ( x,А ) V ¬ (ДЕЛ(x,6) V ¬ДЕЛ(x,9) Так как формула должна быть тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х), то необходимо, чтобы выполнилось хоть одно условие в этом выражении. программа проверяет выражение на истинность каждое слагаемое полным перебором для возрастающих значений A; предполагаем, что наибольшее A не превышает 1000 если после отработки внутреннего цикла переменная countX стала равна 1000, то это говорит о том, что при всех числах Х хоть одно из слагаемых будет равно True ; тогда текущее значение А подходит и записывается в массив a после работы программы в массиве оказываются значения: [1, 2, 3, 6, 9, 18] Ответ : 18

Слайд 17

Задание 15 (Побитовая конъюнкция)

Слайд 18

Аналитическое решение задания 15 Решение задач с поразрядными операциями Введём обозначения: Z 28 = ( x & 28 = 0), Z 45 = ( x & 45 = 0), Z 48 = ( x & 48 = 0), A = ( x & a = 0) перепишем исходное выражение и преобразуем его, используя свойство импликации: перейдем к импликации, используя закон де Моргана: преобразуем выражение в правой части по формуле , выполнив поразрядную дизъюнкцию (операцию ИЛИ): 28 = 011100 45 = 101101 28 or 45 = 111101 = 61 Получаем (1)

Слайд 19

Аналитическое решение задания 15 для того, чтобы выражение (1) было истинно для всех x , нужно, чтобы двоичная запись числа 48 or a содержала все единичные биты числа 61. Таким образом, с помощью числа a нужно добавить те единичные биты числа 61, которых «не хватает» в числе 48: 48 = 110000 a = **11*1 61 = 111101 биты, обозначенные звездочками, могут быть любыми. поскольку нас интересует минимальное значение a , все биты, обозначенные звездочкой, можно принять равными нулю. получается A = 2 3 + 2 2 + 2 0 = 13 Ответ: 13 .

Слайд 20

Программное решение задания 15 Решение задач с поразрядными операциями преобразуем исходную формулу в Так как формула должна быть тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х), то необходимо, чтобы выполнилось хоть одно условие в этом выражении. программа проверяет выражение на истинность каждое слагаемое полным перебором для возрастающих значений A; предполагаем, что A не превышает 1000 если после отработки внутреннего цикла переменная countX стала равна 1000, то это говорит о том, что при всех числах Х хоть одно из слагаемых будет равно True ; тогда текущее значение А подходит и записывается в массив a после работы программы будет выведено число 13 Ответ : 13

Слайд 21

Программное решение задания 15

Слайд 22

Задание 15 ( числовая плоскость ) особенность этой задачи – «уход» авторов от привычных обозначений переменных, x и y ; поскольку мы будем работать с графиками на плоскости, удобнее всё же вернуться к стандартным переменным x и y ( 5x + 6y > 57) ∨ ((x ≤ A)  (y < A))

Слайд 23

Аналитическое решение задания 15 первое выражение (5 x + 6 y > 57) не зависит от выбора A таким образом, нам нужно выбрать значение A так, чтобы условие ( x < A ) and ( y ≤ A ) выполнялось при всех x и y , для которых ложно ( 5 x + 6 y > 57), то есть истинно ( 5 x + 6 y  57 ) Нужно также учесть, что x и y положительны и добавить ещё два ограничения: ( x  1 ) and ( y  1), таким образом, получаем треугольник, ограниченный линиями (5 x + 6 y = 57) and ( x  1 ) and ( y  1 ) для всех точек этого треугольника с целочисленными координатами должно выполняться условие ( x ≤ A )  ( y < A )

Слайд 24

Аналитическое решение задания 15 это значит, что треугольник (точнее, все его точки с целочисленными координатами) должен оказаться внутри квадрата со стороной A , причем в силу нестрогого неравенства ( x ≤ A ) правая граница квадрата (она выделена жирной синей линией) может совпадать с точками треугольника. находим точку пересечения прямых 5 x + 6 y = 57 и x = 1: y  8,67; поскольку нужно выполнить условие ( y < A ) , получаем A > 8 находим точку пересечения прямых 5 x + 6 y = 57 и y = 1: x = 10,2; поскольку нужно выполнить условие ( x  A ) , получаем A  10 оба условия нужно выполнить одновременно, поэтому выбираем наиболее жёсткое: A  10, что даёт A min = 10. Ответ: 1 0 .

Слайд 25

Программное решение задания 15

Слайд 26

задание 16 Уровень: повышенный Время: 9 мин Тема : Рекурсия. Рекурсивные процедуры и функции Что проверяется: Вычисление рекуррентных выражений 1.5.3. Индуктивное определение объектов. 1.1.3. Умение строить информационные модели объектов, систем и процессов в виде алгоритмов. Основные способы решения: - аналитическое - программное - с помощью Excel

Слайд 27

Аналитическое решение задания 1 6 Решение (ручной счёт от первого значения): Начиная вычисления с малых значений n, сразу записываем в таблицу известное значение F (1) = 1, затем последовательно вычисляем F (2) = 2 + F (1) = 3 по формуле для чётных n F (3) = 2  F (1) = 2 по формуле для нечётных n F (4) = … … F (2 6 ) = 2 6 + F (2 5 ) = 4122 Ответ: 4122 n 1 2 3 4 5 6 7 8 9 … 26 F(n) 1 3 2 6 4 1 0 8 1 6 1 6 4122

Слайд 28

Решение с использованием excel и программы

Слайд 29

Задания 19 - 21 Уровень: повышенный Время: 6 + 6 + 10 мин Тема: Теория игр. Поиск выигрышной стратегии. Что проверяется: Умение анализировать алгоритм логической игры. Умение найти выигрышную стратегию игры. Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию.

Слайд 30

Задание 22 (ЕГЭ), Задание 6 (ОГЭ) уровень : повышенный , базовый В ремя : 7 мин , 4 мин Тема: Анализ программы, содержащей циклы и ветвления. Что проверяется: Умение анализировать алгоритм, содержащий ветвление и цикл Основные способы решения: - аналитическое - программное

Слайд 31

Аналитическое решение задания 22 рассмотрим первый цикл: Q = 9 L = 0 while x >= Q: L = L + 1 x = x - Q поскольку переменная L сначала равна 0 и увеличивается на 1 с каждым шагом цикла, она играет роль счётчика повторения цикла на каждой итерации цикла мы вычитаем Q из x до тех пор, пока x не станет меньше Q ; фактически мы определяем, сколько раз «поместится» Q в x из предыдущих рассуждений следует, что это операция деления, при этом после завершения цикла в переменной L находится частное, а в x –остаток от деления введённого значения на Q рассмотрим строки после цикла: M = x if M < L: M = L L = x их роль состоит в том (это легко проверить ручной прокруткой), что значения M и L меняются местами, если только M < L; это означает, что значения частного и остатка (сначала L , потом M ) будут выведены в порядке возрастания нам нужно определить наибольшее число, при котором частное и остаток равны 4 и 5; для получения именно большего числа нам нужно взять как частное наибольшее из двух заданных чисел то есть 5 (соответственно, за остаток принять 4); поскольку делили на 9, искомое число равно 5  9 + 4 = 49 Ответ: 49

Слайд 32

Программное Решение задания 22 Написать функцию, в которую заключить текст программы , кроме вывода значений L и M . Функция возвращает TRUE , если L == 4 и M == 5 В основной программе написать цикл: for x in range(1,1001): if LM45(x): print ( x ) Вывод программы: Ответ: 49

Слайд 33

Решение задания 6 Найти пары, у которых по крайней мере одно из значений > 10. Таких пар 5 : (11, 2), (1, 12), ( 11, 12 ), (-11, 12), (-12, 11) Ответ: 5

Слайд 34

Задание 2 3 ( ЕГЭ ), Задание 5 (ОГЭ) 2 3 (повышенный уровень, время – 8 мин) Тема : динамическое программирование. Что проверяется: Умение анализировать результат исполнения алгоритма уровень : повышенный , базовый В ремя : 8 мин , 6 мин Тема: Динамическое программирование. Что проверяется: Умение анализировать результат исполнения алгоритма Основные способы решения: - аналитическое - программное - с помощью Excel

Слайд 35

Аналитическое решение задания 23 Искомое количество программ равно произведению количества программ, получающих из числа 1 число 10, на количество программ, получающих из числа 10 число 20. Пусть R(n) — количество программ, которые число 1 преобразуют в число n, а P(n) — количество программ, которые число 10 преобразуют в число n. 1. Если n не делится на 2, то тогда R(n) = R(n - 1). Аналогично P(n) = P(n - 1) 2. Если n делится на 2, тогда R(n) = R(n - 1) + R(n / 2). Аналогично P(n) = P(n - 1) + P(n / 2) R(1) = 1 R(2) = R(1) + R(2/2) = 1 + 1 = 2 R(3) = R(2) = 2 R(4) = R(3) + R(4/2) = 2 + 2 = 4 R(5) = R(4) = 4 R(6) = R(5) + R(6/2) = 4 + 2 = 6 R(7) = R(6) = 6 R(8) = R(7) + R(8/2) = 6 + 4 = 10 R(9) = R(8) = 10 R(10) = R(9) + R(10/2) = 10 + 4 = 14 P(10) = 1 P(11) = P(10) = 1 P(12) = P(11) + P(12/2) = 1 + 0 = 1 P(13) = P(12) = 1 P(14) = P(12) + P(14/2) = 1 + 0 = 1 P(15) = P(14) = 1 P(16) = P(15) + P(16/2) = 1 + 0 = 1 P(17) = P(16) = 1 P(18) = P(17) + P(18/2) = 1 + 0 = 1 P(19) = P(18) = 1 P(20) = P(19) + P(20/2) = 1 + 1 = 2 Ответ: 14 * 2 = 28

Слайд 36

Программное Решение задания 23 создаём массив T = 20 K = [0]*(T+1) константа T означает наибольшее число, которое нужно получить; размер массива на единицу больше, элемент K[0] мы использовать не будем, так удобнее (ведь нас интересуют числа, начиная с 1) записываем в первый элемент единицу: K[1] = 1 функция , которая заполняет по приведённым выше формулам элементы массива с индексами от s+1 до n (элемент K[s] должен быть уже заполнен!) def fillArr (s, n ): for i in range(s+1,n+1): K[ i ] = K[i-1] if i % 2 == 0 and i // 2 >= s: K[ i ] += K[ i //2] в условие добавилась вторая часть ( i //2 >= s ) для того, чтобы не захватывать значения K[ i ] при i

Слайд 37

Решение задания 23 с помощью excel

Слайд 38

Аналитическое решение задания 5 Проведем анализ программы: 11211 Запишем траекторию вычисления программы из числа 6: Значит искомое число b = 10, т.к. 8*10 = 80 Ответ: 10 1 1 2 1 1 7 8 81 82

Слайд 39

Задание 15 (ОГЭ) Уровень : высокий Время : 45 мин Тема : Программирование Что проверяется: Создавать и выполнять программы для заданного исполнителя (вариант задания 15.1) или на универсальном языке программирования (вариант задания 15.2)

Слайд 40

Задание 15.1

Слайд 41

Решение Задания 15.1 Алгоритм # Пропускаем клетку, в которой стоит Робот. вправо # Двигаемся вправо, пока не дойдём до прохода в горизонтальной стене. # Закрашиваем пройденные клетки. нц пока не сверху свободно закрасить вправо кц # Двигаемся дальше до горизонтальной стены. нц пока сверху свободно вправо кц # Двигаемся вправо, пока не дойдём до вертикальной стены. # Закрашиваем пройденные клетки. нц пока справа свободно закрасить вправо кц # Двигаемся вниз, пока не дойдём до прохода в вертикальной стене. # Закрашиваем пройденные клетки. нц пока не справа свободно закрасить вниз кц # Двигаемся дальше до вертикальной стены. нц пока справа свободно вниз кц # Двигаемся вниз, до конца вертикальной стены. # Закрашиваем пройденные клетки . нц пока не справа свободно закрасить вниз кц Программа в исполнителе Кумир

Слайд 42

Задание 15.2

Слайд 43

Решение Задания 15.2 Паскаль var n , i, a, k: integer; begin readln (n ); k := 0; for i := 1 to n do begin readln (a ); if (a mod 4 = 0) and (a mod 7 <> 0) then k := k + 1; end ; writeln (k ) end . Python n = int ( input() ) k=0 for I in range(n): a = int (input()) if a % 4 == 0 and a % 7 != 0: k += 1 p rint(k)