Основные формулы для информатики егэ

Шпаргалка ЕГЭ по информатике. Все необходимое

Скачать шпаргалку для подготовки к ЕГЭ по информатике. Содержимое:
— Логика
— Системы счисления
— Кодирование информации
— Программирование
— Теория игр
и другое

Похожие материалы

Комментарии

Всего комментариев: 0

• Взрослым: Skillbox, Хекслет, Eduson, XYZ, GB, Яндекс, Otus, SkillFactory.
• 8-11 класс: Умскул, Лектариум, Годограф, Знанио.
• До 7 класса: Алгоритмика, Кодланд, Реботика.
• Английский: Инглекс, Puzzle, Novakid.

Формулы для заданий ЕГЭ по информатике

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

I = n * i

• n — количество символов
• i — количество бит на 1 символ (кодировка)

Формула для нахождения количества цветов в используемой палитре

i = log₂N

• N — количество цветов
• i — глубина цвета

Формула объема памяти для хранения растрового изображения

I = M * N * i

• I — объем памяти, требуемый для хранения изображения
• M — ширина изображения в пикселях
• N — высота изображения в пикселях
• i — глубина кодирования цвета или разрешение

Или

I = N * i битов

• N – количество пикселей (M * N)
• i – глубина кодирования цвета (разрядность кодирования)

Для указания объема выделенной памяти встречаются разные обозначения (V или I).

Формула объема звукового файла

I = β * ƒ * t * S

• I — объем
• β — глубина кодирования
• ƒ — частота дискретизации
• t — время
• S — количество каналов (S=1 для моно, S=2 для стерео, S=4 для квадро)

Формула объема переданной информации

I = V * t

• I — объем информации
• v — пропускная способность канала связи (измеряется в битах в секунду и пр.)
• t — время передачи

Формула скорости передачи данных

V = I / t

• I — объем информации
• v — пропускная способность канала связи (измеряется в битах в секунду и пр.)
• t — время передачи

Формулы преобразования

• 1 Мбайт = 2²⁰ байт = 2²³ бит,
• 1 Кбайт = 2¹⁰ байт = 2¹³ бит

1.     Кодирование
текста

2.        
Анализ  таблицы истинности

4. Бд  и  файловая система

6. Алгоритмы

Сколько  1, 0, целых A<X<B, вычислить, перевести (-а) в 2сс

Свойства чисел:

1.числа вида 2^k записываются в двоичной системе как единица и k нулей, например:16 = 2⁴ = 10000₂ (числа,
являющиеся степенями 2,3.. ( в любой СС!!)

2. числа вида 2^k-1 записываются в двоичной системе k единиц, например:      15 = 2⁴-1 = 1111₂ (числа
, предшествующие степеням «2»- состоят из «1» и на разряд меньше (в 3 из 2, 4
из 3 , т.е n-1))

3. Двоичное число (другая n CC), оканчивающееся — на 0 – четное(кратно n), — на 1- нечетное (и любое отличное от нуля  число в той СС
говорит о том, что число не кратно n).

Отрицательное число  = 

1) а-1       2) (а-1)из10 перводим в 2сс       3) первая 1
сохраняется,  все остальные цифры переворачиваем 1-0,0-1

10сс	2сс	8 сс	триады	16сс	тетрады
0	0	0	000	0	0000
1	1	1	001	1	0001
2	10	2	010	2	0010
3	11	3	011	3	0011
4	100	4	100	4	0100
5	101	5	101	5	0101
6	110	6	110	6	0110
7	111	7	111	7	0111
8	1000	10		8	1000
9	1001	11		9	1001
10	1010	12		A	1010
11	1011	13		B	1011
12	1100	14		C	1100
13	1101	15		D	1101
14	1110	16		E	1110
15	1111	17		F	1111
16	10000	20		10	10000

0+0=0	0-0=0	0*0=0
0+1=1	1-0=1	0*1=0
1+0=1	1-1=0	1*0=0
1+1=10	10-1=1	1*1=1

  

Сопоставлять
значений переменных с функциями                    (начинать с «одиночных»)

1. Отрицание
(НЕ,¬ , Ā) меняет знаки: < на >=,> на<=.<= на
>, >= на <

2.
Логическое умножение (И, •, ˄, &)

3.
Логическое сложение (ИЛИ, +, ˅, |)

Порядок
выполнения операций: ( ), не, и, или, →,º ….

А	не(А)	А	В	А ˄ В	А	В	А ˅ В	А	В	А→В	А	В	АºВ
1	0	0	0	0	0	0	0	0	0	1	0	0	1
0	1	0	1	0	0	1	1	0	1	1	0	1	0
		1	0	0	1	0	1	1	0	0	1	0	0
		1	1	1	1	1	1	1	1	1	1	1	1

1)внимательно читать задание

2)файловая система:?-точно 1 знак, *-произвольное количество или
их отсутствие

 Автомат(10 СС):

1)определяем СС

2)записываем правило a+b, c+d или другое

3)определяем порядок записи  ­, ¯

4) определяем максимально возможное числов этой СС и
максимальные суммы(!!!помнить о правилах сложения в разных СС)

5) помним о разрядах числа (десятки, сотни, единицы)

Автомат(2СС): четное оканчивается 0, нечетное на 1.

Обработка искаженных сообщений, Калькулятор и др.

5. Декодирование (условие Фано)

Условие Фано: ни одно кодовое слово
не является началом другого кодового слова (дерево 0-1): минимальный код,
короткое слово, сумма кодовых слов, только для конкретного слова и др.

Алгоритм Хаффмана
(оптимальный префиксный код): для самого частого- самый короткий код. Самое
частое повторение обычно 1 бит(0),самые малые повторения обычно 2-3 бита
(умножаем и складываем все ветви)

9.        
Кодирование информации (+передача)

7. Анализ диаграмм и таблица Excel

8. Анализ программ (цикл  while)

Звук:  I=n*i*f*t (n-кол-во дорожек, i-бит на отсчет, f-частота дискретизации ,t-время)

1)
запись близка  2) секунды-минуты

3)
перезаписывают  один и тот же файл — пропорция

1кГц=1000Гц, моно-1, стерео-2, квадро -4, …

Графика: I=k*i, N=2ⁱ(k –кол-во пикселей (200dpi= 200ppi=200*200)

                              i -инф. вес 1 пикселя, N-количество цветов)   

1)определить кол-во цветов 

2)не может превышать <
, >=, > , <=

3) перезаписывают  один и тот же файл — пропорция

4) сохраняют каждые t сек(мин)

Передача информации: I_бит=V_{бит/сек}*t_сек ,  V =I_/t,   t=I/V

 I – размер файла, V – скорость , t – время передачи.

1)сравнение
способов передачи А и Б и на сколько

Наименьшая
единица информации 1 бит

1
байт = 8 бит = 2³бит

1Кбайт(килобайт)
= 1024байт = 2¹⁰байт

1Мбайт(мегабайт)
= 1024Кбайт = 2¹⁰Кбайт

1Гбайт(гигабайт) = 1024Мбайт = 2¹⁰Мбайт

	0	1	2	3	4	5	6	7	8	9	10	11
	20	21	22	23	24	25	26	27	28	29	210	211
N	1	2	4	8	16	32	64	128	256	512	1024	2048

S передачи информации	«Байт в сек» и «бит в сек»
1 Кбит/сек = 1024 _бит/сек 1 Мбит/сек = 1024 Кбит/сек 1 Гбит/сек = 1024 Мбит/сек	1 байт/сек = 8бит/сек 1 Кбайт/сек = 8Кбит/сек 1 Мбайт/сек = 8Мбит/сек

!!!Важно в формулу подставлять значения в одинаковых единицах
измерения и переводить конечный результат в запрашиваемые в задаче единицы.

1)по формулам    2) по пропорции 

1)геометрическая или арифметическая прогрессия

2)условие выполнения цикла (с предусловием)

1)вычисляем значения в ячейках по формулам какие можно

2) соотносим числовые величины и графические изображения
(подбираем число или формулу).    Диапазон ячеек А1:D2 от первой ячейки до
последней.    Весь круг соответствует сумме всех значений, по которым
строится диаграмма. Отдельные сектора пропорциональны доле одного значения в
общей сумм

  
В формулах * — умножение, / — деление, $ — абсолютная ссылка,  при
копировании формулы значение не меняется

10. Перебор слов и СС

1)размещения(с повторениями,  букву сколько угодно раз)Варианты =

2)перестановки (без повторов, букву 1 раз, буквы разные) Р=n!

2)перестановки (без повторов, букву 1 раз, есть одинаковые буквы
разные) Р=n!/n₁! ^.n2!..

4) вероятности  формула Шеннона.

5)Слова(определяем СС (= количество букв), переводим в ту СС, из
той в 10)

— На каком месте стоит слово +1

— Какое слово стоит под номером -1

3. Анализ информационной модели

15.  Количество путей

Соотносим количество пересечений дорог и узлов вершин графа,
анализ начинаем с графа (вершин графа)

Город	Откуда	Кол-во путей
А	—	1
Б	А	1
В	АБ	2
……	….	…..

Потеря  маршрутов, считая «вручную»

Траектория через А и
не через Б –внимательно!

22. Оператор ветвления

Строим дерево внимательно через те точки, которые указаны в
траектории

11.Рекурсия (функция возврата к самой себе)

14.  Алгоритмы формальных исполнителей

1) Вызов функций F(n) или/и G(n)  от предыдущих значений

2) Количество напечатанных

3) Сумма напечатанных

4) Какие выведет числа (!!!Важен порядок вызова (обращения к
рекурсии).

-если write
стоит в начале, то прямой последовательный обход.

— если write
стоит после какой-то первой функции, то выполняется вызов по этой ветке до
конца, по окончанию вызывается оставшаяся функция.

— если write
стоит после всех функций, аналогично предыдущему

Чертежник

Начал и вернулся туда же: (х,у)+…-…=(0,0)

Вернулся в другую точку: (х,у)+…-…=(х₁,у₁)

Повтори  n 
раз   n*(3+2-4…)

Замена команды n*(а+2-4…)=0,   n*(b+3-8….)=0

1)отдельно считаем смещение по x и по y;

2)внимательно читаем вопрос;

3)даём ответ на вопрос, поставленный в задаче.

Робот:  клетка начала и конца
считается закрашенной, движение идет до упора и по условию.

Редактор: циклы считаем с НАЧАЛА!!!

17. Запросы интернета (Диаграммы Эйлера Венна)

23. Логические уравнения

19. Одномерные массивы

Знак
«&»-пересечение запросов (и) , а «|»-объединение запросов (или)

1) Обозначаем зоны запросов буквами a,b,c,d,e,f…..

2) !!! Два множества могут не пересекаться (просматриваем суммы 
пересечений и объединений)

А ˄ В	А ˅ В	А→В	АºВ	А¹В
1 и 1	1 и 1	1-1	1 и 1	0 и 1
	0 и 1	0-0	0 и 0	1 и 0
	1 и 0	0-1

1) замена переменных, если нужно

2) последовательное решение уравнений

Решение системы уравнений – это битовая цепочка (битовый вектор-
единичный объект)

3) уравнения–ограничения на битовый вектор (комбинации)

4) кол-во решений находиться по правилам комбинаторики (чаще
всего аⁿ)

5) варианты комбинаций истинности и лжи для ˄,˅,→, º

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

г) двумерные
массивы(прямоугольная матрица A[i] , B[i]

Цикл for в цикле for
(выполняется первый внешний цикл, потом полностью выполняется внутренний цикл
for, далее 2 эл из 1, и все из
2го ) (прямоугольная матрица)

16. Уравнения в различных СС

26. Стратегия (теория игр)

13.  Вычисление количества информации

21. Анализ программы с
подпрограммами

1)помнить,
что любое число в степени в соответвующей СС=

2)выражения
упрастить и определить СС, если сс 2,3,4,5,…..при вычитании 1  получается на
1 меньше чем СС.

3)
числа  в конце переводим в нужную СС

4)
если произведение степени и числа, применяем правила арифменики  в той СС
(арифметические операции выполняются в одной СС)

5) если
степень числа * на число, применяем арифметические правила той сс в которой
производиться *.

Важно!!!
Арифметика возможна только в одной и той же СС

Описывать стратегию для «выигравшего- выигрышную стратегию, для
проигравшего- все стратегии» (строим дерево игры)

1) камни (камни две кучи, 2 разных хода)

2) фишки (расстояние

3) карточки(таблички) с числами, убирать дубль, если нужно
укоротить, ставить дубль если нужно удлинить

4) слова (считаем количество букв в словах) Игрок 1- нечетные
ходы, Игрок 2- четные ходы

I=k*i, N=2ⁱ  (N-алфавит, k–количество
символов в тексте, i–
инф. вес 1 символа:

КОИ-8(8 бит),  ASCII(8 бит),  Unicode (16
бит), др)

1) количество вариантов (кто прошел –это N из него находим  i  ( N=2ⁱ ), а  I=k*i –это всего.

2) пароли и номера авто: доп. сведения + код+ пароль

!!!Внимательно читать условие (сведения могут быть в 2 коде или
другой СС)

1) Квадратичные
(биквадратные)  уравнения:

Точки минимума = ,  =у(или через F`(x)

Можно искать точки
(max, min), и
значения функций в точке (fmax, fmin). Оценивать
знаки  ­, ¯ функции.

!!!Обязательно
проверять проверять  значения на концах отрезков.

2) вызов функции k=10,64 и
т.п. min или max число

Если ­+1, то
интервал А £ 
х <В

Если ¯-1,  то
интервал А <  х £В

12. IP-адресация

20. Анализ алгоритма с циклами и ветвлениями

24.  Поиск ошибки в программе

25. Обработка
массива

0₁₀=00000000₂    255₁₀=11111111₂

маска-11111111.11111111.11111000.00000000 (1….потом  0)

1)мах количество 1 или 0 в маске

2)мах и min байт
маски

3) 2 байт маски, если 3 =0

4) сколько различных значений маски (сколько масок, варианты)

5)количество ПК  в сети (2 в степени нулей маски )

6) номер ПК в сети (нули маски в проекции на ip-адрес)

7) два ip принадлежат
одной сети (однозначная маска для обоих)

Номер компьютера

Количество адресов в сети

1) Алгоритм Евклида (2 переменные и разность), НОД
прописан в условии, в условии смотреть какое х  нужно вывести х>100, 150…

Выражаем L
через х, L кратно НОД, далее проверяем на числах.

Вычисление НОД(а,b)= НОД(а-b,b)= НОД(а,b—a)

Заменяем большее из двух чисел разностью большего и меньшего до
тех пор, пока они не станут равны. НОД(14,21)= НОД(14,7)= НОД(7,7)=7

Если разница велика и нужно определить количество шагов.
Заменяем большее остатком от деления на меньшее до тех пор, пока меньше не
станет равно нулю. НОД(21,28) (28mod21=7)= НОД(21,7) (21mod7=0)=НОД(0,7)=7

2) Обработка цифр в числе:

— на выводе отмечаем, какие числа выводит программа (указаны в
условии)

— ВАЖНО!!!определить СС в которой обрабатываются числа

x: = а div 10, x: = а div 2, x: = а div 3 , x: = а div 4 , x: = а div 5

ЗНАТЬ!!! числа входящие в конкретную СС (0- число четное!!!)

Перебор цифр в числе за счет цикла ( while x>0  ) пока оно не равно нулю.

— если  определяют не просто число , а разрядное (трехзначное,
двузначное)- это дополнительное условие (первое двузначное-10_n, трехзначное 100_n и т.д конечная граница определяется переводом из 10 сс в нужную)

ЯЗЫК программирования Pascal не понимает другие СС, кроме 10!!

После решения задачи в какой-то СС , переводим полученное число
в 10СС

!!!Проверка на четность:

— в четных СС по последней цифре (0,2,4,6,8 СС)

— нечетных СС по сумме цифр в числе (1,3,5,7,9 СС)

Схема
решения задачи: прогнать задачу на требуемом числе или
на любом удобном Þ чаще всего можно сразу ответить на 1 и 3
вопрос задачи (найти ошибки)  (прогнать и убедиться в правильности)  Þ  после
выполнить 2 задание задачи (найти число работающее правильно )

Решая
задачу делить ее на части:

1)
что выводит (writeln(…)) и
запрашивает readln(…))

2) проверять
инициализацию переменных s:=0, p:=1, k:=0

3)
проверяем условия циклов и условий  (правила их работы) и  сам алгоритм

Проверка
на степень: n=a^k   Þ  , т.е if n=1.

    Формулу для вычисления n-ого элемента арифметической прогрессии: а_n=a₁+d(n-1) формулу для вычисления суммы первых n членов арифметической прогрессии:,           
где a_i – i-ый
элемент последовательности,d – шаг (разность) последовательности

1) Организация ввода данных (уже есть)

2) Инициализация начальных значений некоторых переменных (требуется
задать!)

3)Обработка данных (требуется организовать!)

4) Вывод данных (требуется организовать!)

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

ВАЖНО!!! не писать программу полностью, а «дописать» её в рамках
уже организованного ввода, а также  заданного количества переменных и их
типов: необходимо дописать инициализацию, организовать обработку и вывод.

Для проверки на кратность использовать —

a[i] mod
2 <> 0 (Кратность  n)

18. Логические выражения

1. Если формула истинна (равна 1), и  после упрощения A без
отрицания, то используется закон: A_min = ¬B

    Если формула истинна (равна 1), и после
упрощения A с отрицанием, то используется закон:A_max =
B

2. Если формула ложна (равна 0), и после
упрощения A без отрицания,  то используется закон: A_max =
¬B

Если формула ложна (равна 0), и 2. после
упрощения A с отрицанием, то используется закон: A_min =
B, где B — известная часть выражения

Алфавитный подход

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

I = log₂ N.

Например, в русском языке 32 буквы (буква ё обычно не используется), т. е. количество событий будет равно 32. Тогда информационный объем одного символа будет равен:

I = log₂ 32 = 5 битов.

Если N не является целой степенью 2, то число log₂N не является целым числом, и для I надо выполнять округление в большую сторону. При решении задач в таком случае I можно найти как log₂N’, где N′ — ближайшая к N степень двойки — такая, что N′ > N.

Например, в английском языке 26 букв. Информационный объем одного символа можно найти так:

N = 26; N’ = 32; I = log₂N’ = log₂(2⁵) = 5 битов.

Если количество символов алфавита равно N, а количество символов в записи сообщения равно М, то информационный объем данного сообщения вычисляется по формуле:

I = M · log₂N.

Примеры решения задач

Пример 1. Световое табло состоит из лампочек, каждая из которых может находиться в одном из двух состояний («включено» или «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 50 различных сигналов?

Решение. С помощью n лампочек, каждая из которых может находиться в одном из двух состояний, можно закодировать 2ⁿ сигналов. 2⁵ < 50 < 2⁶, поэтому пяти лампочек недостаточно, а шести хватит.

Ответ: 6.

Пример 2. Метеорологическая станция ведет наблюдения за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100, которое записывается при помощи минимально возможного количества битов. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.

Решение. В данном случае алфавитом является множество целых чисел от 0 до 100. Всего таких значений 101. Поэтому информационный объем результатов одного измерения I = log₂101. Это значение не будет целочисленным. Заменим число 101 ближайшей к нему степенью двойки, большей 101. Это число 128 = 27. Принимаем для одного измерения I = log₂128 = 7 битов. Для 80 измерений общий информационный объем равен:

80 · 7 = 560 битов = 70 байтов.

Ответ: 70 байтов.