ЕГЭ. Информатика

Системы счисления и двоичное представление информации в компьютере

• Четные числа оканчиваются на 0, нечетные – на 1.

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

• Если число N принадлежит интервалу 2^(k-1) <= N < 2^k, в его двоичной записи будет всего k цифр. Например, для числа 125: 2^6 = 64 <= 125 < 128 = 2^7, 125 = (1111101)2 (7 цифр).

• Числа вида 2k записываются в двоичной системе как единица и k нулей. Например: 16 = 2^4 = (10000)2.

• Числа вида 2^(k-1) записываются в двоичной системе k единиц. Например: 15 = (2^4)-1 = (1111)2.

• Если известна двоичная запись числа N, то двоичную запись числа 2*N можно легко получить, приписав в конец ноль. Например: 15 = (1111)2, 30 = (11110)2, 60 = (111100)2, 120 = (1111000)2.

• Для перевода отрицательного числа (-a) в двоичный дополнительный код нужно, перевести число (a-1) в двоичную систему счисления и сделать инверсию битов.

• Связь между двоичной и восьмеричной системой счисления. Например: (10001011101001)2 = 010 001 011 101 001 = 2 1 3 5 1 = (21351)8. Аналогично - из восьмеричной в двоичную.

• Связь между двоичной и шестнадцатеричной системой счисления. Например: (10001011101001)2 = 0010 0010 1110 1001 = 2 2 E 9 = (22E9)16. Аналогично - из шестнадцатеричной в двоичную.

• Для того, чтобы перевести отрицательное целое число из десятичной системы счисления в двоичную нужно перевести модуль числа в двоичную систему счисления с нужным количеством разрядов, затем сделать инверсию и прибавить к результату единицу.

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

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

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

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

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

• Количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно 2^k, где k – число отсутствующих строк. Например, полная таблица истинности выражения с тремя переменными содержит 2^3=8 строк, если заданы только 6 из них, то можно найти 2^(8-6)=2^2=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся).

Файловая система

• В масках, кроме «обычных» символов, допустимых в именах файлов, используются два специальных символа: звездочка «*» и знак вопроса «?». Звездочка «*» обозначает любое количество любых символов, в том числе, может обозначать пустую последовательность. Знак вопроса «?» обозначает ровно один любой символ.

• Пример подбора масок:

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

• Кодирование может быть равномерное и неравномерное: при равномерном кодировании все символы кодируются кодами равной длины, при неравномерном кодировании разные символы могут кодироваться кодами разной длины, что затрудняет декодирование.

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

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

Анализ простых алгоритмов

• Бит чётности – дополнительный контрольный бит, который добавляется к двоичному коду так, чтобы количество единиц в полученном двоичном коде стало чётным; если в исходном коде уже было чётное количество единиц, дописывается 0, если нечётное – дописывается 1.

• При добавлении к двоичной записи числа нуля справа число увеличивается в 2 раза.

Электронные таблицы

Анализ программ

• Формула для вычисления n-ого элемента арифметической прогрессии:

• Формула для вычисления суммы первых n членов арифметической прогрессии:

где (a)i – i-ый элемент последовательности, d – шаг (разность) последовательности.

Кодирование растровых изображений

• Для хранения растрового изображения нужно выделить в памяти I = N · i битов, где N – количество пикселей (вычисляется как произведение ширины рисунка на высоту (в пикселях)) и i – глубина цвета (количество бит, которые выделяются на хранение цвета одного пикселя) (разрядность кодирования).

• При глубине кодирования i битов на пиксель код каждого пикселя выбирается из 2^i возможных вариантов, поэтому можно использовать не более 2^i различных цветов.

Кодирование звука

• Частота дискретизации f определяет количество отсчетов, запоминаемых за 1 секунду: 1 Гц – один отсчет в секунду; 8 кГц – 8000 отсчетов в секунду.

• Глубина кодирования (разрешение) i – количество бит, которые выделяются на один отсчет.

• Для хранения информации о звуке длительностью t секунд, закодированном с частотой дискретизации f Гц и глубиной кодирования i бит требуется I = i*f*t бит памяти.

• При двухканальной (стерео) записи объем памяти, необходимый для хранения данных одного канала, умножается на 2.

• При повышении разрешения в 2 раза объём файла увеличивается в 2 раза, время – тоже в 2 раза.

• При снижении частоты дискретизации в 2 раза объём файла уменьшается в 2 раза, время – тоже в 2 раза.

• При увеличении пропускной способности канала связи (то же самое, что и скорость передачи данных) в 4 раза время передачи уменьшится в 4 раза.

Адресация в Интернете

• Адрес документа в Интернете (URL = Uniform Resource Locator) состоит из протокола, чаще всего http (для Web-страниц) или ftp (для файловых архивов; знаков ://, отделяющих протокол от остальной части адреса; доменного имя (или IP-адреса) сайта; каталога на сервере, где находится файл; имя файла.

• Принято разделять каталоги не обратным слэшем «\» (как в Windows), а прямым «/», как в системе UNIX и ее «родственниках», например, в Linux.

• Пример адреса (URL):

Здесь желтым маркером выделен протокол, фиолетовым – доменное имя сайта, голубым – каталог на сайте и серым – имя файла.

• Каждый компьютер, подключенный к сети Интернет, должен иметь собственный адрес, который называют IP-адресом (IP = Internet Protocol).

• IP-адрес компьютера – это 32-битное число; для удобства его обычно записывают в виде четырёх чисел, разделенных точками; каждое из этих чисел находится в интервале 0…255, например: 192.168.85.210.

• IP-адрес состоит из двух частей: адреса сети и адреса узла в этой сети, причём деление адреса на части определяется маской – 32-битным числом, в двоичной записи которого сначала стоят единицы, а потом – нули:

Та часть IP-адреса, которая соответствует единичным битам маски, относится к адресу сети, а часть, соответствующая нулевым битам маски – это числовой адрес узла.

• Если два узла относятся к одной сети, то адрес сети у них одинаковый.

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

• С помощью K бит можно закодировать Q = 2^K различных вариантов (чисел).

• Если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно Q = M^N.

Поиск количества путей

• Если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z.