Спецпроект: что повторить к ОГЭ по информатике, чтобы сдать его на высокий балл?

·    кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)

·    обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход

·    один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)

·    кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной длины, это затрудняет декодирование

·    закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;

·    закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;

·    условие Фано – это достаточное, но не необходимое условие однозначного декодирования.

·    четные числа оканчиваются на 0, нечетные – на 1;

·    числа, которые делятся на 4, оканчиваются на 00, и т.д.; числа, которые делятся на 2k, оканчиваются на k нулей

·    если число N принадлежит интервалу 2k-1 £ N < 2k, в его двоичной записи будет всего k цифр, например, для числа 125:

26 = 64 £ 125 < 128 = 27,    125 = 11111012  (7 цифр)

·    числа вида 2k записываются в двоичной системе как единица и k нулей, например:

16 = 24 = 100002

·    числа вида 2k-1 записываются в двоичной системе k единиц, например:

15 = 24-1 = 11112

если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например:
15 = 11112,          30 = 111102,         60 = 1111002,   120 = 11110002

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

·    для перевода отрицательного числа (-a) в двоичный дополнительный код нужно сделать следующие операции:

o   перевести число a-1 в двоичную систему счисления;

o   сделать инверсию битов: заменить все нули на единицы и единицы на нули в пределах разрядной сетки (см. пример Р-00 далее).

Построение и анализ таблиц истинности логических выражений:

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

¬ A, не A (отрицание, инверсия)

A Ù B, A и B (логическое умножение, конъюнкция)

A Ú B, A или B (логическое сложение, дизъюнкция)

A → B импликация (следование)

A º B эквивалентность  (равносильность)

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

A → B = ¬ A Ú B или в других обозначениях  A → B =

·    иногда для упрощения выражений полезны формулы де Моргана:

¬ (A Ù B) = ¬ A Ú ¬ B        

¬ (A Ú B) = ¬ A Ù ¬ B        

·    если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем  – «ИЛИ», «импликация», и самая последняя – «эквивалентность»

·    таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных

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

·    количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где  – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)

·    логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)

·    логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)

·    логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно

·    эквивалентность АºB  равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.

Источник: inf-ege.sdamgia.ru