Тема : Вычисление информационного объема сообщения

Задачи для тренировки³:

1. 
   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 22 оканчивается на 4.
   
2. 
   В системе счисления с некоторым основанием число 12 записывается в виде 110. Укажите это основание.
   
3. 
   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 39 оканчивается на 3.
   
4. 
   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 29 оканчивается на 5.
   
5. 
   В системе счисления с некоторым основанием десятичное число 129 записывается как 1004. Укажите это основание.
   
6. 
   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 40 оканчивается на 4.
   
7. 
   В системе счисления с некоторым основанием число десятичное 25 записывается как 100. Найдите это основание.
   
8. 
   Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 27 оканчивается на 3.
   
9. 
   Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 26, запись которых в троичной системе счисления оканчивается на 22?
   
10. 
    Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в четверичной системе счисления оканчивается на 31?
    
11. 
    Укажите через запятую в порядке возрастания все десятичные натуральные числа, не превосходящие 17, запись которых в троичной системе счисления оканчивается на две одинаковые цифры?
    
12. 
    Укажите, сколько всего раз встречается цифра 3 в записи чисел 19, 20, 21, …, 33 в системе счисления с основанием 6.
    
13. 
    Укажите, сколько всего раз встречается цифра 1 в записи чисел 12, 13, 14, …, 31 в системе счисления с основанием 5.
    

B4 (высокий уровень, время – 10 мин)

• 
  условные обозначения логических операций
  

• 
  таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)
  
• 
  операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
  

• 
  операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:
  

• 
  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»
  
• 
  логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
  
• 
  логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)
  
• 
  правила преобразования логических выражений (слайд из презентации «Логика»):
  

Пример задания:

1. 
   это операция импликации между двумя отношениями и
   
2. 
   попробуем сначала решить неравенства
   ,
   
3. 
   обозначим эти области на оси X:
   

4. 
   вспомним таблицу истинности операции «импликация»:
   

   A	B	A → B
   0	0	1
   0	1	1
   1	0	0
   1	1	1

5. 
   согласно таблице, заданное выражение истинно везде, кроме областей, где и ; область истинности выделена зеленым цветом
   
6. 
   поэтому наибольшее целое число, удовлетворяющее условию – это первое целое число, меньшее , то есть, 7
   
7. 
   таким образом, верный ответ – 7 .
   

Возможные проблемы: в этом примере потребовалось применить знания не только (и не столько) из курса информатики, но и умение решать неравенства нужно не забыть правила извлечения квадратного корня из обеих частей неравенства (операции с модулями)

1. 
   сначала можно преобразовать импликацию, выразив ее через «ИЛИ» и «НЕ»:
   
2. 
   
   
3. 
   это значит, что выражение истинно там, где или
   
4. 
   дальнейшие действия точно такие же, как и в варианте 1.
   

Возможные проблемы: нужно помнить формулу для преобразования импликации

Еще пример задания:

1. 
   перепишем уравнение, используя более простые обозначения операций:
   

2. 
   из таблицы истинности операции «импликация» (см. первую задачу) следует, что это равенство верно тогда и только тогда, когда одновременно
   

3. 
   из первого уравнения следует, что хотя бы одна из переменных, K или L равна 1 (или обе вместе); поэтому рассмотрим три случая
   
4. 
   если K = 1 и L = 0, то второе равенство выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения
   

6. 
   если K = 1 и L = 1, то второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
   
7. 
   если K = 0, то обязательно L = 1 (из первого уравнения); при этом второе равенство выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения
   
8. 
   таким образом, всего получаем 4 + 3 + 3 = 10 решений.
   

Совет: лучше начинать с того уравнения, где меньше переменных

Возможные проблемы: есть риск потерять какие-то решения при переборе вариантов

Еще пример задания:

1. 
   запишем уравнение, используя более простые обозначения операций (условие «выражение ложно» означает, что оно равно логическому нулю):
   

2. 
   из формулировки условия следует, что выражение должно быть ложно только для одного набора переменных
   
3. 
   из таблицы истинности операции «импликация» (см. первую задачу) следует, что это выражение ложно тогда и только тогда, когда одновременно
   

4. 
   первое равенство (логическое произведение равно 1) выполняется тогда и только тогда, когда и ; отсюда следует (логическая сумма равна нулю), что может быть только при ; таким образом, три переменных мы уже определили
   
5. 
   из второго условия, , при и получаем
   
6. 
   таким образом, правильный ответ – 1000.
   

Возможные проблемы: переменные однозначно определяются только для ситуаций «сумма = 0» (все равны 0) и «произведение = 1» (все равны 1), в остальных случаях нужно рассматривать разные варианты не всегда выражение сразу распадается на 2 (или более) отдельных уравнения, каждое из которых однозначно определяет некоторые переменные

1. 
   запишем уравнение, используя более простые обозначения операций:
   

2. 
   заменим импликацию по формуле :
   

3. 
   раскроем инверсию сложного выражения по формуле де Моргана :
   

4. 
   упростим выражение :
   

5. 
   мы получили уравнение вида «сумма = 0», в нем все слагаемые должны быть равны нулю
   
6. 
   поэтому сразу находим
   
7. 
   таким образом, правильный ответ – 1000.
   

Замечание: этот способ работает всегда и дает более общее решение; в частности, можно легко обнаружить, что уравнение имеет несколько решений (тогда оно не сведется к форме «сумма = 0» или «произведение = 1»)

Возможные проблемы: нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой

Еще пример задания:

1. 
   запишем уравнение, используя более простые обозначения операций:
   

2. 
   это выражение с тремя переменными, поэтому в таблице истинности будет 2³=8 строчек; следовательно, двоичная запись чисел, по которым строятся столбцы таблицы А, В и С, должна состоять из 8 цифр
   
3. 
   

   А	В	С	X
   0	0	0
   0	1	1
   0	0	1
   1	0	1
   1	1	1
   0	1	0
   1	0	0
   1	1	0

   переведем числа 27, 77 и 120 в двоичную систему, сразу дополняя запись до 8 знаков нулями в начале чисел
   

4. 
   теперь можно составить таблицу истинности (см. рисунок справа), в которой строки переставлены в сравнении с традиционным порядком⁴; зеленым фоном выделена двоичная записи числа 27 (биты записываются сверху вниз), синим – запись числа 77 и розовым – запись числа 120:
   
5. 
   вряд ли вы сможете сразу написать значения функции Х для каждой комбинации, поэтому удобно добавить в таблицу дополнительные столбцы для расчета промежуточных результатов (см. таблицу ниже)
   
6. 
   заполняем столбцы таблицы:
   

А	В	С					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

7. 
   чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 10101011₂
   
8. 
   переводим это число в десятичную систему: 10101011₂ = 2⁷ + 2⁵ + 2³ + 2¹ + 2⁰ = 171
   
9. 
   таким образом, правильный ответ – 171.
   

Возможные проблемы: нужно помнить таблицы истинности логических операций легко запутаться в многочисленных столбцах с однородными данными (нулями и единицами)

1. 
   выполним пп. 1-5 так же, как и в предыдущем способе
   
2. 
   запишем уравнение, используя более простые обозначения операций:
   

3. 
   раскроем импликацию через операции И, ИЛИ и НЕ ():
   

4. 
   раскроем инверсию для выражения по формуле де Моргана:
   

5. 
   таким образом, выражение приобретает вид
   
6. 
   отсюда сразу видно, что Х = 1 только тогда, когда А = В или (А = 1 и В = С = 0):
   

   А	В	С	X	Примечание
   0	0	0	1	А = В
   0	1	1	0
   0	0	1	1	А = В
   1	0	1	0
   1	1	1	1	А = В
   0	1	0	0
   1	0	0	1	А = 1, В = С = 0
   1	1	0	1	А = В

7. 
   чтобы получить ответ, выписываем биты из столбца Х сверху вниз: Х = 10101011₂
   
8. 
   переводим это число в десятичную систему: 10101011₂ = 2⁷ + 2⁵ + 2³ + 2¹ + 2⁰ = 171
   
9. 
   таким образом, правильный ответ – 171.
   

Возможные проблемы: нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой