Презентация по информатике: "ЕГЭ. Разбор заданий 2, 4, 6" (11 класс)

• 1 слайд

• 2 слайд

  Ниже представлены две таблицы из базы данных. Каждая строка Таблицы 2 содержит информацию о ребенке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке Таблицы 1.
  Определите на основании приведенных данных суммарное количество прямых потомков (т.е. детей, внуков, правнуков) Иоли А.Б.
  
  

• 3 слайд

• 4 слайд

  В первой таблице находим Иоли А.Б, ей соответствует ID 84
  Все остальное решение будет связано со второй таблицей: будем в ней искать ID родителя и соответствующего ему ID ребенка.
  Выполним задание при помощи дерева, подробно рассматривая каждый уровень иерархии: сначала детей родителя 84, затем по полученным ID — найдем внуков Иоли А.Б, затем правнуков и т.д.
  

• 5 слайд

  Посчитаем количество потомков: их 7
  Результат: 7
  
  

• 6 слайд

  Ниже представлены две таблицы из базы данных, в которых собраны сведения о сотрудниках некоторой организации. Каждая строка Таблицы 2 содержит информацию о сотруднике структурного подразделения и о его непосредственном руководителе, который, в свою очередь, является непосредственным подчиненным руководителя более высокого уровня. Информация представлена значением поля ID в соответствующей строке Таблицы 1.
  Определите на основании приведенных данных суммарное количество подчиненных (непосредственных и через руководителей более низкого уровня) Сидорова Т.И.
  

• 7 слайд

• 8 слайд

  В первой таблице находим Сидорова Т.И., ему соответствует ID 17
  Все остальное решение будет связано со второй таблицей: будем в ней искать ID руководителя и соответствующих ему ID подчиненных.
  Выполним задание при помощи дерева, подробно рассматривая каждый уровень иерархии: сначала непосредственных подчиненных руководителя 17, затем по полученным ID — найдем подчиненных подчиненных и т.д.
  

• 9 слайд

  Посчитаем количество подчиненных: 9
  Результат: 9
  
  

• 10 слайд

  Логическая функция F задаётся выражением 
  ¬x ∨ y ∨ (¬z ∧ w).
  На рисунке приведён фрагмент таб. истинности функции F, содержащий все наборы аргументов, при которых функция F ложна.
  Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
  

• 11 слайд

  Внешним действием (последним выполняемым) в исходном выражении является дизъюнкция:
  ¬x ∨ y ∨ (¬z ∧ w)
  Вспомним таб. ист-ти для дизъюнкции (логическое сложение):
  
  

• 12 слайд

  Чтобы исходное выражение было истинным, нужно, чтобы хотя бы один из операндов равнялся единице. Т.е. нельзя наверняка сказать, где будет 1, а где 0 (¬x= 1 или 0, y = 1 или 0, ¬z ∧ w = 1 или 0).
  Функция же ложна только в одном случае, — когда все операнды ложны. Поэтому будем искать по признаку лжи.
  В исходной таблице истинности во всех строках функция ложна. Чтобы понять в каком столбце должна находиться та или иная переменная, возьмем за основу строку, в которой только одна единица или только один нуль.
  

• 13 слайд

  Строка №1: в ней одна единица — первый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы ¬x = 0, иными словами x = 1. Значит первый столбец соответствует переменной x.
  
  

• 14 слайд

  Строка №3: в ней один нуль — четвертый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы y = 0. Значит четвертый столбец соответствует переменной y.
  
  

• 15 слайд

  Строка №2: в ней второй столбец равен единице, а третий — нулю. В исходном выражении ¬z ∧ w должно равняться 0, чтобы функция была ложной. Конъюнкция истинна только тогда, когда оба операнда истинны (=1); в нашем случае функция должна быть ложной, но пойдем от обратного. Если ¬z = 1, т.е. z = 0, а w = 1, то это неверно для нашего случая. Значит всё должно быть наоборот: z = 1, а w = 0. Таким образом столбец второй соответствует z, а столбец третий — w.
  
  

• 16 слайд

  Результат: xzwy
  

• 17 слайд

  Для кодирования букв О, В, Д, П, А решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления).
  Закодируйте последовательность букв ВОДОПАД таким способом и результат запишите восьмеричным кодом.
  
  
  

• 18 слайд

  Переведем числа в двоичные коды и поставим их в соответствие нашим буквам:
  О -> 0 -> 00
  В -> 1 -> 01
  Д -> 2 -> 10
  П -> 3 -> 11
  А -> 4 -> 100
  Теперь закодируем последовательность букв из слова ВОДОПАД:
  010010001110010
  
  
  

• 19 слайд

  Разобьем результат на группы из трех символов справа налево, чтобы перевести их в восьмеричную систему счисления:
  
  010 010 001 110 010
  ↓ ↓ ↓ ↓ ↓
  2 2 1 6 2
  
  Результат: 22162.
  
  
  

• 20 слайд

  Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для некоторых — из трех). Эти коды представлены в таблице:
  
  
  
  Какой набор букв закодирован двоичной строкой 1100000100110?
  

• 21 слайд

  Во-первых, проверяем условие Фано: никакое кодовое слово не является началом другого кодового слова. Условие верно.
  Сделаем дерево, согласно кодам в таблице:
  
  

• 22 слайд

  Сопоставим закодированное сообщение с кодами в дереве:
  110 000 01 001 10
  
  Результат: b a c d e.
  
  

• 23 слайд

  Исполнитель Счетчик преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
  Прибавь 5
  Умножь на 5
  Первая команда увеличивает число на экране на 5, вторая умножает его на 5.
  Программа для исполнителя Счетчик — это последовательность команд.
  Сколько существует программ, для которых при исходном числе 5 результатом является число 250, и при этом траектория вычислений содержит число 35 и не содержит числа 105?
  Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 9, 45, 50.
  
  

• 24 слайд

  Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:
  
  
  
  
  5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
  
  

• 25 слайд

  35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
  35 -> 105 — «ненужная» часть траектории;
  105 -> 250 — тоже «ненужная» часть.
  Чтобы вычислить результат, т.е. количество программ, необходимо:
  траектория 1 * (траектория 2 - (траектория 3 * * траектория 4))
  полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
  

• 26 слайд

  Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5!(5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
  Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
  

• 27 слайд

  Расчет отрезка 1: 5 -> 35
  Возьмем такое наименьшее число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
  5 не подходит: применимы две команды в интервале до 35: 5 + 5 = 10 и 5 * 5 = 25 10 подходит: применима только одна команда: 10 + 5 = 15, а 10 * 5 = 50 - больше 35.
  

• 28 слайд

  Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
  

• 29 слайд

  Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
  
  
  
  
  
  
  Итого получили две программы.
  Результат: 2
  
  
  

• 30 слайд

  Расчет отрезка 2: 35 -> 250
  Возьмем такое наименьшее число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
  55 т.к. 55 * 5 = 275 - это больше числа 250 Затем будем последовательно брать подходящие меньшие числа:
  
  
  
  

• 31 слайд

  Пояснение: поскольку это задача динамического программирования, то полученные в начале результаты, используются для дальнейших вычислений:
  для числа 45 мы взяли результат, полученный для числа 50 (2);
  для числа 40 мы взяли результат, полученный для числа 45 (3);
  для числа 35 мы взяли результат, полученный для числа 40 (4);
  Результат: 5
  
  
  
  

• 32 слайд

  Расчет отрезка 3: 35 -> 105
  Возьмем такое наименьшее число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
  35 т.к. 35 * 5 = 175 - больше числа 105
  
  
  
  
  
  Результат: 1
  
  
  
  

• 33 слайд

  Расчет траектории 4: 105 -> 250
  
  
  
  
  
  
  
  
  Результат: 1
  Посчитаем результат, согласно полученной формуле:
  траектория 1 * (траектория 2 - (траектория 3 * траектория 4)) 2 * (5 - 1 * 1) = 8
  Результат: 8