"Использование математические знания при подготовке к ЕГЭ по информатике"

«Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа №1»

село Александровское

21. февраля 2014 год.

Доклад

на тему:

«Использования математические знания при подготовке  к  ЕГЭ по информатике».

Выполнила:  Хрусцелевская Н. В

учитель информатики и ВТ.

Александровское – 2022

Содержание доклада:

1. Формы обучения подготовки к ЕГЭ.  ………………………………….3

2. Материалы по подготовке к ЕГЭ: ………………………………………4

· Системы счисления ……………………………………………………….4

· Алгебра логики…………………………………………………………….8

· Кодирование информации………………………………………………..10

· Графы………………………………………………………………………13

Формы обучения подготовки к ЕГЭ.

Демоверсии различных лет очень похожи друг на друга; поэтому, разобравшись в одной, достаточно легко можно справиться и с остальными. Формы обучения рассматриваются разные. Такие как индивидуальная, фронтальная групповая.

         После прохождения какой-то темы, которая объединяет в себе несколько уроков, я провожу контроль знаний. Контроль состоит из заданий подобных заданиям ЕГЭ. Если ученик выполняет тест меньше 50%, то он устно к следующему занятию готовит теоретическую часть и готовится к практической части - тесту. Если же ученик и во второй раз показывает такой же результат, то в индивидуальном порядке происходит разбор тех тестовых заданий, в которых допущены ошибки.

Тестирование можно проводить в бумажном или электронном виде, тексты тестов и задания составляю, используя многочисленную литературу с готовыми текстами тестов по основным разделам базового курса. Стараюсь выбирать задания из имеющихся на сегодняшний день в базе данных контрольно-измерительных материалов (КИМ) для проведения ЕГЭ по информатике, из всевозможных демонстрационных, репетиционных и реальных вариантов ЕГЭ, а также из сборников для подготовки к ЕГЭ под редакцией Макаровой Н.В., Якушкина П.А , Чуркиной , Зорина и др, допущенных для подготовки к ЕГЭ Министерством образования и науки. Моя задача  при подготовке к урокам — выбрать из имеющегося материала задания, соответствующие теме урока.

         Кроме того, целесообразно использовать уже готовую электронную продукцию: «Репетитор по информатике Кирилла и Мефодия», «Информатика. Интерактивный задачник» и др. электронные тренажеры.

          Широкое использование систем тестового контроля не только позволяет подготовить учащихся к формату письменных экзаменов, проводимых в виде тестов, но является  несомненным подспорьем на уроках информатики. Такие тесты, умело составленные, могут выполнять не только контролирующие, но обучающие и закрепляющие функции, служить для осуществления как текущего или промежуточного, так и тематического или итогового контроля знаний.

С целью контроля прохождения всех заданий, а также наглядной картины «готовности»  ученика  к ЕГЭ следует проводить мониторинг каждого сдающего экзамен ученика. Таким образом, можно получить достоверную картину успехов каждого ученика, а ученик, свою очередь, узнает уровень своей подготовленности.

Материалы по подготовке к ЕГЭ:

·        Системы счисления.

·        Алгебра логики.

·        Графы.

·        Кодирование информации.

Задания к теме «Системы счисления»

Для решения этих задач необходимо знать:

Основные понятия:

цифра, число, системы счисления, позиционные системы счисления, основание системы счисления.

Цифра - символ, необходимый для записи чисел.

Например, в десятичной системе цифрами являются символы: 0,1,2,3,4,5,6,7,8,9.

Число служит мерой, определяет количество чего-либо. Число записывается комбинацией цифр. Например, число 25 (комбинация цифр "2" и "5").

Позиционные системы счисления - системы счисления, где позиция цифры влияет на ее значение. Например, "3" - три, "30"- тридцать,"300" - триста. В зависимости от своего положения (единицы, десятки, сотни) цифра "3" дает разные числовые значения.

Основание системы счисления - количество цифр, которые используются в системе счисления. Например, в десятичной системе счисление основание равно 10

. Наиболее часто в информатике используются системы счисления: двоичная, восьмеричная, шестнадцатиричная. 

Разбор задачи

Время выполнения-1 мин, уровень сложности - базовый

Сколько единиц в двоичной записи десятичного числа 255?

1

2

7

8

Решение:1 способ:

255 | 2     
2       127 | 2    
  5     12     63 | 2    
  4        7    6     31 | 2   
  15      6      3   2     15 | 2  
  14      1      2   11   14   7 |  2  
   1              1   10     1   6     3 | 2
                         1          1     2   1 
                                           1   

2 способ (метод быстрого перевода):

Число 255 меньше числа "2 в степени" на 1.

255=256−1=2⁸−1 (8 единиц).

Быстрый перевод числа из десятичной системы счисления в воичную.

Метод очень простой. Суть его такая: если число, которое нужно перевести из десятичной системы, равно числу "2 в степени", то это число в двоичной системе содержит количество нулей, равное степени. Впереди этих нулей добавляем "1". 

Примеры:

•         Переведем число 2 из десятичной системы. 2=2¹. Поэтому в двоичной системе число содержит 1 нуль. Впереди ставим "1" и получаем 10₂. 

•         Переведем 4 из десятичной системы. 4=2². Поэтому в двоичной системе число содержит 2 нуля. Впереди ставим "1" и получаем 100_2. 

•         Переведем 8 из десятичной системы. 8=2³. Поэтому в двоичной системе число содержит 3 нуля. Впереди ставим "1" и получаем 1000_2. 

              Если число, которое нужно перевести, меньше числа "2 в степени" на 1, то в двоичной системе это число состоит только из единиц, количество которых равно степени.

•         Переведем 3 из десятичной системы. 3=2²-1. Поэтому в двоичной системе число содержит 2 единицы. Получаем 11_2. 

•         Переведем 7 из десятичной системы. 7=2³-1. Поэтому в двоичной системе число содержит 3 единицы. Получаем 111_2. 

Разбор задачи

Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Ответ: 15

По заданию, число должно быть минимально, поэтому для системы с основанием 3 - это число 3, а с основанием 5 - это число 5. 

3|3        5|5
3 1        5  1
0           0

3₁₀=10₃ и 5₁₀=10₃

Чтобы остаток числа был равен 0-ю в обеих системах счисления (с остатком 3 и 5), десятичное число должно быть кратно числам: 3 и 5. 

3*5=15 - это и есть искомое десятичное число.

15|3         15|5
15 5         15  3
 0              0

15₁₀=50₃ и 15₁₀=30₅

Задания к теме: «Алгебра логики»

Для решения этих задач необходимо знать: 

Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно.

Логические операции - "связки": союзы  и частицы естественного языка, образующие из простых высказываний сложные, представленные в формальном виде.

Логическое выражение - простое или сложное логическое высказывание, представленное в формальном виде.

Законы алгебры логики - законы, позволяющие преобразовывать логические выражения.

Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).

Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь). 

Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций.

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

Разбор задачи

Дан фрагмент таблицы истинности выражения F.

Каким из приведённых ниже выражений может быть F?

¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7

¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7

x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7

x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7

№	x1	x2	x3	x4	x5	x6	x7	F
1	1	1	0	1	1	1	1	0
2	1	0	1	0	1	1	0	0
3	0	1	0	1	1	0	0	1

Решение: Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V).

Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.

В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.

Разбор задачи

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». 
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. 

Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? 
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: 2200

Запрос	Найдено страниц (в тысячах)
Фрегат | Эсминец	3400
Фрегат & Эсминец	900
Фрегат	2100

Решение:

Изобразим запросы в виде диаграмм Эйлера-Венна.

Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".

Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.

Задания к теме :  «Кодирование информации»

Кодирование символов  Объем сообщения определяется по формуле:  V=l*r, где l-длина сообщения (количество символов), r-разрешение. Разрешение-количество бит, выделенное на кодирование одного символа.  Кодировка Unicod: 1 символ кодируется 2 байтами или 16 битами. Закодированный символ представляется в виде в 16-чном коде с приставкой "U+". Например, код буквы "я" такой: U+044F  Кодировка КОИ-8: 1 символ кодируется 1 байтом или 8 битами.

Кодирование звука Объем звукозаписи (размер аудио файла)  определяют по формуле: V=υ*r*t*a, где υ-частота дискретизации, r-разрешение, t-время, a-коэффициент (для монозвука а=1, для стерео а=2).

Кодирование цвета Модель RGB (red-green-blue, красный-зеленый-синий) "Каждый Охотник Желает Знать Где Сидит Фазан".  данной модели для кодирования цвета выделено 3 байта, по 1 байту на каждый из трех  основных цветов. Поэтому интенсивность цвета может принимать  значение от 0 до 255 (28=256 комбинаций). Для примера, пусть цвета нужны яркие, интенсивность максимальна(255). Объем цвета определяется по формуле:N=2i

Кодирование изображений Объем изображения определяется по формуле: V=S*r,где S-площадь изображения, r- разрешение. Разрешение - сколько бит выделено на кодирование цветов. В модели RGB r=3 байта.

Разбор задачи

Время выполнения-2 мин, уровень сложности-базовый Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и 24-битным разрешением. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

1.0.2

2.2

3.3

4.4

Решение: Объем звукозаписи (размер аудиофайла) определяют по формуле:

V=υ*r*t*a,

где υ-частота дискретизации, r-разрешение, t-время, a-коэффициент.

υ=16 кГц=16*10³ Гц

r=24 бита=24\8=3 байта

t=1 мин=60 сек

a=1-для монозвука

V=16*10³*3*60*1=16*10³*3*6*10¹=16*18*10⁴=2⁴*2¹*9*(2*5)⁴=2⁹*9*5⁴=2⁹*5625 байт

Выразим в мегабайтах:

1 мегабайт=2²⁰

2⁹*5625\2²⁰=5625\2048=2,7≈3 мегабайта

Разбор задачи

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Ответ: 48

Решение: Количество различных комбинаций из "точек"  и "тире" определяется по формуле:

N=X^y,

где X - количество вариантов символов,

y - длина последовательности сигналов.

2 варианта символов: «точка» и «тире» (Х=2).

Длина последовательности 1 - 4 сигнала (y₁=4).

Длина последовательности 2 - 5 сигналов (y₂=5).

N₁=X^y₁=2⁴=16 комбинаций.

N₂=X^y₂=2⁵=32 комбинации.

N=N₁+N₂=16+32=48 комбинаций из "точек"  и "тире", т.е. могут быть закодированы 48 различных символов.

Задания к теме :  «Графы»

•         Граф  - Пара объектов G = ( X , Г )  ,где Х - конечное множество ,а  Г –конечное подмножество  прямого произведения  Х*Х  .  При этом   Х называется множеством вершин , а  Г - множеством дуг графа G .

•         Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.

•         Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .

•         Дуга- ребро ориентированного графа.

•         Граф называется  вырожденным, если у него нет рёбер.

•         Вершина Х называется  инцидентной  ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

•         Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ ÍV и множеством ребер (дуг) E₁Í E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁ . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Разбор задачи

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Ответ: 13

Решение:

Нарисуем путь из пункта А в Л. Начнем с конца, с пункта Л. К нему ведут дороги из И, Ж, К:

В пункт И ведет дорога из Д. В пункт Ж ведут дороги из Д, В, Е. В пункт К ведет дорога из Е. 

В пункт Д ведут дороги из Б и В. В пункт В ведут дороги из Б, А, Г. В пункт Е ведет дорога из Г.

В пункт Б ведет дорога из А. В пункт В ведут дороги из Б, А, Г. В пункт Г ведет дорога из А.

В пункт Б ведет дорога из А. В пункт Г ведет дорога из А.

В итоге путь из пункта А в Л выглядит так:

Посчитаем, сколько "А" получилось. Из каждой "А" идет свой маршрут. На рисунке 13 различных путей.

Разбор задачи C3 (демо ЕГЭ 2012)

Время выполнения-30 мин, уровень сложности- высокий

У исполнителя две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29?
Ответ обоснуйте.

Решение:

Нам нужно построить граф, описывающий выполнение команд Утроителя. Строим его до тех пор, пока не получим число 9. 29/3=9 с остатком. Числа больше 9 дают только одну программу, т.к. нельзя применить команду "умножить на 3".

Построим этот граф:

После выполнения 2-х команд получаем числа: 3, 6, 4, 9. Определим число программ-решений, для получения из каждого из них числа 29. 

Обозначим количество программ-решений для получения из числа n числа 29 как Р(n). 

Количество программ-решений для получения из 1-цы числа 29 определяется по формуле: N=P(3)+P(6)+P(4)+P(9).

Выберем из чисел 3, 6, 4, 9 самое большое. Это 9. Определим P(9):

10*3>29, поэтому к 29 ведет только 1 решение.

27*3>29, поэтому к 29 ведет только 1 решение.

Получили, P(9)=1+1=2. 

Остались числа: 3, 6, 4. Наибольшее из них число 6. Определим P(6):

18*3>29, поэтому к 29 ведет только 1 решение.

21*3>29, поэтому к 29 ведет только 1 решение.

24*3>29, поэтому к 29 ведет только 1 решение.

P(9)=2 решения.

Получили, P(6)=1+1+1+2=5.

Остались числа: 3,4. Наибольшее из них число 4. Определим P(4):

12*3>29, поэтому к 29 ведет только 1 решение.

15*3>29, поэтому к 29 ведет только 1 решение.

P(6)=5 решений.

Получили, P(4)=1+1+5=7.

Осталось число 3. Определим P(3):

Получили, P(3)=P(4)+P(9)=7+2=9.

N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы.

Краткое решение:

P(N)=1 при N>9.

P(9)=P(10)+P(27)=2 программы.

P(6)=P(9)+P(24)+P(21)+P(18)=2+1+1+1=5 программ.

P(4)=P(6)+P(15)+P(12)=5+1+1=7 программ.

P(3)=P(4)+P(9)=7+2=9 программ.

P(1)=P(3)+P(4)+P(6)+P(9)=9+7+5+2=23 программы.

• 1 слайд

  МАОУ СОШ №1 село Александровское
  Выполнила: Хрусцелевская Н. В
  учитель информатики и ВТ.
  Доклад
  «Использование математические знания при подготовке к ЕГЭ по информатике».
  на тему:
  

• 2 слайд

  Содержание доклада:
  2. Материалы по подготовке к ЕГЭ:
  
  Системы счисления
  Алгебра логики
  Кодирование информации
  Графы
  
  1. Формы обучения при подготовки к ЕГЭ.
  

• 3 слайд

  www.themegallery.com
  Company Logo
  Формы обучения при
  подготовки к ЕГЭ
  
  
  Домой
  Индивидуально
  дифференцированные
  технологии
  Объяснительно-
  иллюстративный
  метод
  Репродуктивный
  метод
  Проблемно-
  иллюстративный
  метод
  Исследовательский метод
  Коллективная
  Групповая
  Фронтальная
  
  Индивидуальная
  

• 4 слайд

  методы, приёмы, технологии
  подготовки к ЕГЭ
  
  
  www.themegallery.com
  Company Logo
  Домой
  Индивидуально
  дифференцированные
  технологии
  Личностно-
  ориентированные
  технологии
  Игровые технологии
  Компьютерные
  технологии
  Объяснительно-
  иллюстративный
  метод
  Репродуктивный
  метод
  Проблемно-
  иллюстративный
  метод
  Исследовательский метод
  

• 5 слайд

  Материалы по подготовке к ЕГЭ
  www.themegallery.com
  Задания к теме
  «Графы»
  Задания к теме
  «Системы счисления»
  Задания к теме
  «Кодирование информации»
  Задания к теме
  «Алгебра логики»
  

• 6 слайд

  Задания к теме
  «Системы счисления»
  Для решения этих задач необходимо знать: 
  Основные понятия:
  цифра, число, системы счисления, позиционные системы счисления, основание системы счисления.
  Цифра - символ, необходимый для записи чисел.
  Например, в десятичной системе цифрами являются символы: 0,1,2,3,4,5,6,7,8,9.
  Число служит мерой,определяет количество чего-либо. Число записывается комбинацией цифр. Например, число 25 (комбинация цифр "2" и "5").
  Позиционные системы счисления - системы счисления, где позиция цифры влияет на ее значение. Например, "3" - три, "30"- тридцать,"300" - триста. В зависимости от своего положения (единицы,десятки,сотни) цифра "3" дает разные числовые значения.
  Основание системы счисления - количество цифр, которые используются в системе счисления. Например, в десятичной системе счисление основание равно 10
  . Наиболее часто в информатике используются системы счисления: двоичная, восьмеричная, шестнадцатиричная. 
  

• 7 слайд

  Разбор задачи
  Сколько единиц в двоичной
  записи десятичного числа 255?
  
  1
  2
  7
  8
  Решение:1 способ:
  255 | 2     
  2       127 | 2    
    5     12     63 | 2    
    4        7    6     31 | 2   
    15      6      3   2     15 | 2  
    14      1      2   11   14   7 |  2  
     1              1   10     1   6     3 | 2
                           1          1     2   1 
                                             1   
  2 способ (метод быстрого перевода):
  
  
  Число 255 меньше числа "2 в степени" на 1.
  
  255=256−1=28−1 (8 единиц).
  Время выполнения-1 мин, уровень сложности - базовый
  

• 8 слайд

  Быстрый перевод числа из десятичной системы счисления в двоичную.
  Метод очень простой. Суть его такая: если число, которое нужно перевести из десятичной системы, равно числу "2 в степени", то это число в двоичной системе содержит количество нулей, равное степени. Впереди этих нулей добавляем "1". 
  

• 9 слайд

  Примеры:
  Переведем число 2 из десятичной системы. 2=21. Поэтому в двоичной системе число содержит 1 нуль. Впереди ставим "1" и получаем 102. 
  Переведем 4 из десятичной системы. 4=22. Поэтому в двоичной системе число содержит 2 нуля. Впереди ставим "1" и получаем 1002. 
  Переведем 8 из десятичной системы. 8=23. Поэтому в двоичной системе число содержит 3 нуля. Впереди ставим "1" и получаем 10002. 
  
  

• 10 слайд

  Если число, которое нужно перевести, меньше числа "2 в степени" на 1, то в двоичной системе это число состоит только из единиц, количество которых равно степени.
  Переведем 3 из десятичной системы. 3=22-1. Поэтому в двоичной системе число содержит 2 единицы. Получаем 112. 
  Переведем 7 из десятичной системы. 7=23-1. Поэтому в двоичной системе число содержит 3 единицы. Получаем 1112. 
  
  

• 11 слайд

  Разбор задачи
  Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?
  Ответ: 15
  По заданию, число должно быть минимально, поэтому для системы с основанием 3 - это число 3, а с основанием 5 - это число 5. 
  3|3        5|5
  3 1        5  1
  0           0
  
  310=103 и 510=103
  
  Чтобы остаток числа был равен 0-ю в обеих системах счисления (с остатком 3 и 5), десятичное число должно быть кратно числам: 3 и 5. 
  3*5=15 - это и есть искомое десятичное число.
  15|3         15|5
  15 5         15  3
   0              0
  1510=503 и 1510=305
  

• 12 слайд

  Задания к теме: «Алгебра логики»
  Для решения этих задач необходимо знать: 
  Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно.
  Логические операции - "связки": союзы  и частицы естественного языка, образующие из простых высказываний сложные, представленные в формальном виде.
  Логическое выражение - простое или сложное логическое высказывание, представленное в формальном виде.
  Законы алгебры логики - законы, позволяющие преобразовывать логические выражения.
  Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).
  Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь). 
  Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций.
  Диаграммы Эйлера-Венна - диаграммы, которые служат для наглядного представления всех вариантов пересечения нескольких множеств. В качестве множеств могут использоваться простые логические высказывания. Диаграмма строится для логического высказывания, которое содержит от одного до трех утверждений
  

• 13 слайд

  Разбор задачи
  Дан фрагмент таблицы истинности выражения F.
  
  
  Каким из приведённых ниже выражений может быть F?
  ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
  ¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
  x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
  x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7
  Решение: Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V).
  Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.
  В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.
  

• 14 слайд

  Разбор задачи
  В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». 
  В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. 
  Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? 
  Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
  Ответ: 2200
  

• 15 слайд

  Решение:
  Изобразим запросы в виде диаграмм Эйлера-Венна.
  Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".
  
  Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.
  

• 16 слайд

  Задания к теме :
  «Кодирование информации»
  Для решения этих задач необходимо знать: 
  

• 17 слайд

  Разбор задачи
  Время выполнения-2 мин, уровень сложности-базовый Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и 24-битным разрешением. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?
  1.0.2
  2.2
  3.3
  4.4
  Решение: Объем звукозаписи (размер аудиофайла) определяют по формуле:
  V=υ*r*t*a,
  где υ-частота дискретизации, r-разрешение, t-время, a-коэффициент.
  υ=16 кГц=16*103 Гц
  r=24 бита=24\8=3 байта
  t=1 мин=60 сек
  a=1-для монозвука
  V=16*103*3*60*1=16*103*3*6*101=16*18*104=24*21*9*(2*5)4=29*9*54=29*5625 байт
  Выразим в мегабайтах:
  1 мегабайт=220
  29*5625\220=5625\2048=2,7≈3 мегабайта.
  

• 18 слайд

  Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?
  Ответ: 48
  Разбор задачи
  Решение: Количество различных комбинаций из "точек"  и "тире" определяется по формуле:
  N=Xy,
  где X - количество вариантов символов,
  y - длина последовательности сигналов.
  2 варианта символов: «точка» и «тире» (Х=2).
  Длина последовательности 1 - 4 сигнала (y1=4).
  Длина последовательности 2 - 5 сигналов (y2=5).
  N1=Xy1=24=16 комбинаций.
  N2=Xy2=25=32 комбинации.
  N=N1+N2=16+32=48 комбинаций из "точек"  и "тире", т.е. могут быть закодированы 48 различных символов.
  

• 19 слайд

  Задания к теме : «Графы»
  Для решения этих задач необходимо знать: 
  Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г –конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .
  Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.
  Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .
  Дуга- ребро ориентированного графа.
  Граф называется вырожденным, если у него нет рёбер.
  Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.
  Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ÍV и множеством ребер (дуг) E1Í E, - такими, что каждое ребро (дуга) из E1 инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).
  

• 20 слайд

  На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
  
  Ответ: 13
  Разбор задачи
  Решение: Нарисуем путь из пункта А в Л. Начнем с конца, с пункта Л. К нему ведут дороги из И, Ж, К:
  В пункт И ведет дорога из Д. В пункт Ж ведут дороги из Д, В, Е. В пункт К ведет дорога из Е. 
  

• 21 слайд

  В пункт Д ведут дороги из Б и В. В пункт В ведут дороги из Б, А, Г. В пункт Е ведет дорога из Г.
  В пункт Б ведет дорога из А. В пункт В ведут дороги из Б, А, Г. В пункт Г ведет дорога из А.
  В пункт Б ведет дорога из А. В пункт Г ведет дорога из А.
  

• 22 слайд

  В итоге путь из пункта А в Л выглядит так:
  Посчитаем, сколько "А" получилось. Из каждой "А" идет свой маршрут. На рисунке 13 различных путей.
  

• 23 слайд

  Время выполнения-30 мин, уровень сложности - высокий
  У исполнителя две команды, которым присвоены номера:
  1. прибавь 1,
  2. умножь на 3.
  Первая из них увеличивает число на экране на 1, вторая – утраивает его.
  Программа для Утроителя – это последовательность команд.
  Сколько есть программ, которые число 1 преобразуют в число 29?
  Ответ обоснуйте.
  Разбор задачи
  

• 24 слайд

  Решение: Нам нужно построить граф, описывающий выполнение команд. Строим его до тех пор, пока не получим число 9. 29/3=9 с остатком. Числа больше 9 дают только одну программу, т.к. нельзя применить команду "умножить на 3".
  
  Построим этот граф:
  

• 25 слайд

  После выполнения 2-х команд получаем числа: 3, 6, 4, 9. Определим число программ-решений, для получения из каждого из них числа 29. 
  
  Обозначим количество программ-решений для получения из числа n числа 29 как Р(n). 
  
  Количество программ-решений для получения из 1-цы числа 29 определяется по формуле: N=P(3)+P(6)+P(4)+P(9).
  Выберем из чисел 3, 6, 4, 9 самое большое. Это 9. Определим P(9):
  

• 26 слайд

  10*3>29, поэтому к 29 ведет только 1 решение.
  
  27*3>29, поэтому к 29 ведет только 1 решение.
  Получили, P(9)=1+1=2. 
  
  Остались числа: 3, 6, 4. Наибольшее из них число 6. Определим P(6):
  

• 27 слайд

  18*3>29, поэтому к 29 ведет только 1 решение.
  21*3>29, поэтому к 29 ведет только 1 решение.
  24*3>29, поэтому к 29 ведет только 1 решение.
  P(9)=2 решения.
  
  Получили, P(6)=1+1+1+2=5.
  Остались числа: 3,4. Наибольшее из них число 4. Определим P(4):
  

• 28 слайд

  12*3>29, поэтому к 29 ведет только 1 решение.
  15*3>29, поэтому к 29 ведет только 1 решение.
  P(6)=5 решений.
  Получили, P(4)=1+1+5=7.
  Осталось число 3. Определим P(3):
  Получили, P(3)=P(4)+P(9)=7+2=9.
  N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы.
  Краткое решение:
  P(N)=1 при N>9.
  
  P(9)=P(10)+P(27)=2 программы.
  P(6)=P(9)+P(24)+P(21)+P(18)=2+1+1+1=5 программ.
  P(4)=P(6)+P(15)+P(12)=5+1+1=7 программ.
  P(3)=P(4)+P(9)=7+2=9 программ.
  P(1)=P(3)+P(4)+P(6)+P(9)=9+7+5+2=23 программы.
  

• 29 слайд

  www.themegallery.com
  Company Logo
  
  
  за
  Спасибо
  внимание
  

Задания к теме «Системы счисления»

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

Сколько единиц в двоичной записи десятичного числа 255?

1

2

7

8

Решение:1 способ:

255 | 2     
2       127 | 2    
  5     12     63 | 2    
  4        7    6     31 | 2   
  15      6      3   2     15 | 2  
  14      1      2   11   14   7 |  2  
   1              1   10     1   6     3 | 2
                         1          1     2   1 
                                           1   

2 способ (метод быстрого перевода):

Число 255 меньше числа "2 в степени" на 1.

255=256−1=2⁸−1 (8 единиц).

Быстрый перевод числа из десятичной системы счисления в двоичную.

Метод очень простой. Суть его такая: если число, которое нужно перевести из десятичной системы, равно числу "2 в степени", то это число в двоичной системе содержит количество нулей, равное степени. Впереди этих нулей добавляем "1". 

Примеры:

•         Переведем число 2 из десятичной системы. 2=2¹. Поэтому в двоичной системе число содержит 1 нуль. Впереди ставим "1" и получаем 10₂. 

•         Переведем 4 из десятичной системы. 4=2². Поэтому в двоичной системе число содержит 2 нуля. Впереди ставим "1" и получаем 100_2. 

•         Переведем 8 из десятичной системы. 8=2³. Поэтому в двоичной системе число содержит 3 нуля. Впереди ставим "1" и получаем 1000_2. 

              Если число, которое нужно перевести, меньше числа "2 в степени" на 1, то в двоичной системе это число состоит только из единиц, количество которых равно степени.

•         Переведем 3 из десятичной системы. 3=2²-1. Поэтому в двоичной системе число содержит 2 единицы. Получаем 11_2. 

•         Переведем 7 из десятичной системы. 7=2³-1. Поэтому в двоичной системе число содержит 3 единицы. Получаем 111_2. 

Разбор задачи

Запись десятичного числа в системах счисления с основаниями 3 и 5 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Ответ: 15

По заданию, число должно быть минимально, поэтому для системы с основанием 3 - это число 3, а с основанием 5 - это число 5. 

3|3        5|5
3 1        5  1
0           0

3₁₀=10₃ и 5₁₀=10₃

Чтобы остаток числа был равен 0-ю в обеих системах счисления (с остатком 3 и 5), десятичное число должно быть кратно числам: 3 и 5. 

3*5=15 - это и есть искомое десятичное число.

15|3         15|5
15 5         15  3
 0              0

15₁₀=50₃ и 15₁₀=30₅

Задания к теме: «Алгебра логики»

Разбор задачи

Дан фрагмент таблицы истинности выражения F.

Каким из приведённых ниже выражений может быть F?

¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7

¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7

x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7

x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7

№	x1	x2	x3	x4	x5	x6	x7	F
1	1	1	0	1	1	1	1	0
2	1	0	1	0	1	1	0	0
3	0	1	0	1	1	0	0	1

Решение: Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V).

Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.

В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.

Разбор задачи

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». 
В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. 

Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? 
Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Ответ: 2200

Запрос	Найдено страниц (в тысячах)
Фрегат | Эсминец	3400
Фрегат & Эсминец	900
Фрегат	2100

Решение:

Изобразим запросы в виде диаграмм Эйлера-Венна.

Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".

Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.

Задания к теме :  «Кодирование информации»

Разбор задачи

Время выполнения-2 мин, уровень сложности-базовый Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и 24-битным разрешением. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?

1.0.2

2.2

3.3

4.4

Решение: Объем звукозаписи (размер аудиофайла) определяют по формуле:

V=υ*r*t*a,

где υ-частота дискретизации, r-разрешение, t-время, a-коэффициент.

υ=16 кГц=16*10³ Гц

r=24 бита=24\8=3 байта

t=1 мин=60 сек

a=1-для монозвука

V=16*10³*3*60*1=16*10³*3*6*10¹=16*18*10⁴=2⁴*2¹*9*(2*5)⁴=2⁹*9*5⁴=2⁹*5625 байт

Выразим в мегабайтах:

1 мегабайт=2²⁰

2⁹*5625\2²⁰=5625\2048=2,7≈3 мегабайта

Разбор задачи

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т. д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)?

Ответ: 48

Решение: Количество различных комбинаций из "точек"  и "тире" определяется по формуле:

N=X^y,

где X - количество вариантов символов,

y - длина последовательности сигналов.

2 варианта символов: «точка» и «тире» (Х=2).

Длина последовательности 1 - 4 сигнала (y₁=4).

Длина последовательности 2 - 5 сигналов (y₂=5).

N₁=X^y₁=2⁴=16 комбинаций.

N₂=X^y₂=2⁵=32 комбинации.

N=N₁+N₂=16+32=48 комбинаций из "точек"  и "тире", т.е. могут быть закодированы 48 различных символов.

Задания к теме :  «Графы»

Разбор задачи

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

Ответ: 13

Решение:

Нарисуем путь из пункта А в Л. Начнем с конца, с пункта Л. К нему ведут дороги из И, Ж, К:

В пункт И ведет дорога из Д. В пункт Ж ведут дороги из Д, В, Е. В пункт К ведет дорога из Е. 

В пункт Д ведут дороги из Б и В. В пункт В ведут дороги из Б, А, Г. В пункт Е ведет дорога из Г.

В пункт Б ведет дорога из А. В пункт В ведут дороги из Б, А, Г. В пункт Г ведет дорога из А.

В пункт Б ведет дорога из А. В пункт Г ведет дорога из А.

В итоге путь из пункта А в Л выглядит так:

Посчитаем, сколько "А" получилось. Из каждой "А" идет свой маршрут. На рисунке 13 различных путей.

Разбор задачи

Время выполнения-30 мин, уровень сложности- высокий

У исполнителя две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.
Сколько есть программ, которые число 1 преобразуют в число 29?
Ответ обоснуйте.

Решение:

Нам нужно построить граф, описывающий выполнение команд Утроителя. Строим его до тех пор, пока не получим число 9. 29/3=9 с остатком. Числа больше 9 дают только одну программу, т.к. нельзя применить команду "умножить на 3".

Построим этот граф:

После выполнения 2-х команд получаем числа: 3, 6, 4, 9. Определим число программ-решений, для получения из каждого из них числа 29. 

Обозначим количество программ-решений для получения из числа n числа 29 как Р(n). 

Количество программ-решений для получения из 1-цы числа 29 определяется по формуле: N=P(3)+P(6)+P(4)+P(9).

Выберем из чисел 3, 6, 4, 9 самое большое. Это 9. Определим P(9):

10*3>29, поэтому к 29 ведет только 1 решение.

27*3>29, поэтому к 29 ведет только 1 решение.

Получили, P(9)=1+1=2. 

Остались числа: 3, 6, 4. Наибольшее из них число 6. Определим P(6):

18*3>29, поэтому к 29 ведет только 1 решение.

21*3>29, поэтому к 29 ведет только 1 решение.

24*3>29, поэтому к 29 ведет только 1 решение.

P(9)=2 решения.

Получили, P(6)=1+1+1+2=5.

Остались числа: 3,4. Наибольшее из них число 4. Определим P(4):

12*3>29, поэтому к 29 ведет только 1 решение.

15*3>29, поэтому к 29 ведет только 1 решение.

P(6)=5 решений.

Получили, P(4)=1+1+5=7.

Осталось число 3. Определим P(3):

Получили, P(3)=P(4)+P(9)=7+2=9.

N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы.

Краткое решение:

P(N)=1 при N>9.

P(9)=P(10)+P(27)=2 программы.

P(6)=P(9)+P(24)+P(21)+P(18)=2+1+1+1=5 программ.

P(4)=P(6)+P(15)+P(12)=5+1+1=7 программ.

P(3)=P(4)+P(9)=7+2=9 программ.

P(1)=P(3)+P(4)+P(6)+P(9)=9+7+5+2=23 программы.

Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно.

Логические операции - "связки": союзы  и частицы естественного языка, образующие из простых высказываний сложные, представленные в формальном виде.

Логическое выражение - простое или сложное логическое высказывание, представленное в формальном виде.

Законы алгебры логики - законы, позволяющие преобразовывать логические выражения.

Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).

Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь). 

Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций.

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