Учебник reknow · 10 класс

Информатика: теория

10 тем — объяснения простым языком, формулы, рисунки и разобранные примеры. К каждой теме — тренажёр.

Классы:7 8 9 10 11 Информатика по всем классам →

Информация и измерение информации
Системы счисления
Кодирование текста и графики
Кодирование звука и передача данных
Элементы математической логики
Логические схемы и упрощение выражений
Алгоритмы, блок-схемы и исполнители
Программирование и трассировка
Массивы и последовательности
Компьютер, файловая система и сети

Тема 1 · Информатика

Информация и измерение информации

Простыми словами

Чтобы угадать задуманное число от 1 до 8, достаточно трёх вопросов «да/нет»: каждый ответ вдвое сужает выбор. Один такой ответ несёт 1 бит информации — это и есть единица её измерения.

Информационные процессы — это хранение, передача и обработка информации. Передача всегда идёт по одной схеме:

Помехи искажают сообщение — поэтому применяют помехоустойчивое кодирование

Свойства информации: объективность, достоверность, полнота, актуальность, полезность, понятность.

Понятие	Смысл
достоверность	информация отражает истинное положение дел
актуальность	информация важна именно в данный момент времени
полнота / понятность	содержит все нужные сведения / выражена понятным получателю языком
носитель информации	материальный объект, хранящий сведения (бумага, диск, флеш-память)
кодирующее устройство	преобразует сообщение к виду, пригодному для передачи по каналу связи; на приёме декодирующее — обратно
дискретный сигнал	величина принимает конечное число значений; аналоговый (непрерывный) — любые значения в диапазоне

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

Мощность алфавита $N$ — число различных символов. Все символы кодируются одинаковым числом бит $i$ (вес символа):

N = 2^{i}, I = K \cdot i

N

— мощность алфавита,

i

— бит на символ,

K

— число символов,

I

— объём сообщения в битах

$N$	2	4	8	16	32	64	128	256
$i$ , бит	1	2	3	4	5	6	7	8

Если $N$ — не степень двойки, $i$ округляют вверх: наименьшее $i$ , при котором $2^{i} \geq N$ . Для $N = 5$ нужно 3 бита: $2^{2} = 4 < 5 \leq 8 = 2^{3}$ .

Объём. $N = 16$ , $K = 96$ : $i = 4$ , $I = 96 \cdot 4 = 384$ бит $= 384 : 8 = 48$ байт.
Мощность. $I = 576$ бит, $K = 192$ : $i = 576 : 192 = 3$ , $N = 2^{3} = 8$ .
Длина. $N = 64$ , $I = 1536$ бит: $i = 6$ , $K = 1536 : 6 = 256$ символов.

В библиотеке 722 книги. Сколько бит нужно на номер? $2^{9} = 512 < 722 \leq 1024 = 2^{10}$ — 10 бит.

Чтобы сравнить объёмы сообщений в разных алфавитах, для каждого найдите $i$ по $N$ и посчитайте $K \cdot i$ . Длиннее — не значит больше: 100 символов из 256-символьного алфавита ( $800$ бит) «тяжелее» 300 символов из 4-символьного ( $600$ бит).

Содержательный подход: формула Хартли

Сообщение о том, что произошло одно из $N$ равновероятных событий, несёт

i = lo g_{2} N ⟺ N = 2^{i}

формула Хартли:

i

— количество информации в битах,

N

— число равновероятных исходов

Один бит — сообщение, уменьшающее неопределённость ровно в 2 раза. Если неопределённость уменьшилась в 8 раз, получено 3 бита: $8 = 2^{3}$ .

Из 8 пронумерованных карточек вынули одну: $i = lo g_{2} 8 = 3$ бита. Победитель турнира из 4 равных участников: $lo g_{2} 4 = 2$ бита.

Единицы измерения

Единица	Равна
1 байт	8 бит $= 2^{3}$ бит
1 Кбайт	1024 байта $= 2^{10}$ байт $= 2^{13}$ бит
1 Мбайт	1024 Кбайт $= 2^{20}$ байт
1 Гбайт	1024 Мбайт $= 2^{30}$ байт

$8$ Кбайт $= 8 \cdot 1024 \cdot 8 = 2^{3} \cdot 2^{10} \cdot 2^{3} = 2^{16} = 65536$ бит.

В школьном курсе и в задачах ЕГЭ приставки «кило-», «мега-», «гига-» перед байтом и битом означают умножение на 1024, если не сказано иначе. По стандарту СИ 1 kB = 1000 байт, а 1024 байта обозначают отдельно — 1 KiB (кибибайт); так считают производители дисков и скорость сетей.

Переводите в степени двойки: $1024 = 2^{10}$ , $8 = 2^{3}$ . Тогда умножение и деление превращаются в сложение и вычитание показателей.

Тема 2 · Информатика

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

Потренироваться: задания по теме →

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

Простыми словами

В числе 333 три тройки значат разное: 300, 30 и 3. Значение цифры зависит от её места — такая система называется позиционной. Компьютеру удобно считать не десятками, а двойками.

Позиционная система — значение цифры зависит от её места в записи. Основание $p$ — количество различных цифр в системе: в двоичной $0, 1$ ; в восьмеричной $0 \dots 7$ ; в шестнадцатеричной $0 \dots 9$ и $A = 10$ , $B = 11$ , $C = 12$ , $D = 13$ , $E = 14$ , $F = 15$ .

\overline{a_{n} \dots a_{1} a_{0}}_{p} = a_{n} \cdot p^{n} + \dots + a_{1} \cdot p^{1} + a_{0} \cdot p^{0}

a_{k}

— цифра в разряде

k

(разряды нумеруются справа налево с нуля),

p

— основание

10	2	8	16
10	1010	12	A
15	1111	17	F
64	1000000	100	40
255	11111111	377	FF

Перевод в десятичную и из десятичной

Из $p$ в 10: умножить каждую цифру на $p$ в степени номера разряда и сложить.

$532 1_{8} = 5 \cdot 8^{3} + 3 \cdot 8^{2} + 2 \cdot 8 + 1 = 2560 + 192 + 16 + 1 = 276 9_{10}$ .
$BF2_{16} = 11 \cdot 256 + 15 \cdot 16 + 2 = 305 8_{10}$ .

Из 10 в $p$ : делить на $p$ , выписывая остатки, пока частное не станет нулём; читать остатки снизу вверх.

$60$ в двоичную: $60 \to 30 \to 15 \to 7 \to 3 \to 1 \to 0$ , остатки $0, 0, 1, 1, 1, 1$ . Снизу вверх: $6 0_{10} = 11110 0_{2}$ .
$627$ в шестнадцатеричную: $627 = 39 \cdot 16 + 3$ , $39 = 2 \cdot 16 + 7$ , $2 = 0 \cdot 16 + 2$ → $27 3_{16}$ .

Двоичная ↔ восьмеричная и шестнадцатеричная

Так как $8 = 2^{3}$ и $16 = 2^{4}$ , двоичные цифры группируют по три (триады) для восьмеричной и по четыре (тетрады) для шестнадцатеричной. Группы отсчитывают справа, слева дописывают нули.

Делим на тетрады справа налево; неполную левую группу дополняем нулями

$101000111 0_{2}$ по триадам: $1 ∣ 010 ∣ 001 ∣ 110$ → $1216$ , то есть $121 6_{8}$ .

Помните наизусть $2^{0} \dots 2^{10}$ : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Тетрада $1111 = 8 + 4 + 2 + 1 = 15 = F$ .

Арифметика в системе с основанием $p$

Складывают столбиком: как только сумма в разряде достигает $p$ , вычитают $p$ и переносят 1 в старший разряд. При вычитании занимают у старшего разряда единицу, равную $p$ .

Двоичное сложение	Результат
$0 + 0$	0
$0 + 1$	1
$1 + 1$	10 (0 и перенос 1)
$1 + 1 + 1$	11 (1 и перенос 1)

$22 7_{16} + 32 1_{16}$ : $7 + 1 = 8$ , $2 + 2 = 4$ , $2 + 3 = 5$ → $54 8_{16}$ (переносов нет).
$1010011 1_{2} + 111011 1_{2} = 10001111 0_{2}$ . Проверка в десятичной: $167 + 119 = 286$ ✓

Проверить себя всегда можно переводом обоих чисел и результата в десятичную систему. Так же сравнивают числа в разных системах: переводят всё в десятичную.

Свойства двоичной записи

$2^{k}$ единица и

k

нулей:

2^{5} = 10000 0_{2}

$2^{k} - 1$

k

единиц подряд:

2^{4} - 1 = 111 1_{2}

Чётностьпоследний разряд 0 — чётное, 1 — нечётное

Число разрядовесли

2^{k - 1} \leq N < 2^{k}

, в записи

N

ровно

k

цифр

$1024 = 2^{10} \leq 1441 < 2048 = 2^{11}$ , значит в двоичной записи 1441 — 11 разрядов.

Тема 3 · Информатика

Кодирование текста и графики

Потренироваться: задания по теме →

Смешение цветов: свет и краски

Простыми словами

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

Все задачи темы сводятся к одной формуле «количество элементов × бит на элемент»:

I = K \cdot i

I

— объём в битах,

K

— число символов (или пикселей),

i

— бит на символ (или на пиксель)

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

ОднобайтовыеASCII, КОИ-8, CP-1251, CP-866: 1 байт

= 8

бит на символ, в таблице

2^{8} = 256

символов.

Unicode (UTF-16)2 байта

= 16

бит на символ,

2^{16} = 65536

кодов.

Пробелы, знаки препинания и переносы — тоже символы и тоже считаются.

16 страниц × 25 строк × 60 символов, ASCII.

$K = 16 \cdot 25 \cdot 60 = 24000$ символов.
$i = 8$ бит $= 1$ байт, значит $I = 24000$ байт.

Файл ASCII занимает 16 Кбайт: символов $16 \cdot 1024 = 16384$ (1 символ = 1 байт). При 4096 символах на странице это $16384 : 4096 = 4$ страницы.

Кодовая таблица

В кодовых таблицах буквы алфавита идут подряд: код следующей буквы на 1 больше. Зная код одной буквы, находим любую.

Код «А» равен 128 (CP-866). Буквы идут А Б В Г Д Е Ж З И Й К…

«К» — 11-я буква (без Ё), код $128 + 10 = 138$ .
В шестнадцатеричной: $138 = 8 \cdot 16 + 10$ , то есть $8A_{16}$ .
Слово «КЛМ»: $138 + 139 + 140 = 417$ . Сумма трёх подряд идущих кодов = утроенный средний код.

Буква Ё в большинстве таблиц стоит отдельно, вне алфавитного ряда. Считайте позиции по фрагменту таблицы, данному в задаче.

Кодирование графики

Растровое изображение — сетка пикселей. Глубина цвета $i$ — сколько бит отводится на один пиксель; число цветов палитры $N = 2^{i}$ .

4 цвета → 2 бита на пиксель

Глубина $i$ , бит	1	2	4	8	16	24
Цветов $N$	2	4	16	256	65 536	16 777 216

I = a \cdot b \cdot i (бит)

a \times b

— ширина и высота в пикселях,

i

— глубина цвета

Если число цветов не степень двойки, $i$ округляют вверх: 808 цветов → $2^{9} = 512 < 808 \leq 1024$ → 10 бит.

Растровоехранит цвет каждого пикселя; при увеличении видны «ступеньки». Форматы BMP, PNG, JPEG.

Векторноехранит описания геометрических примитивов (линий, окружностей, кривых) и их свойств; масштабируется без потери качества. Форматы SVG, CDR.

Цветовая модель RGB (красный, зелёный, синий) используется для экранов — цвет получается сложением излучения трёх цветов.

Задачи на изображения

$320 \times 200$ , 8 бит: $320 \cdot 200 \cdot 8$ бит $= 64000$ байт.

768 Кбайт, высота 768, 8 бит. Ширина $= \frac{768 \cdot 1024 \cdot 8}{768 \cdot 8} = 1024$ пикселя.

$512 \times 256$ занимает 256 Кбайт.

Перейдём к степеням двойки: $256 Кбайт = 2^{8} \cdot 2^{10} \cdot 2^{3} = 2^{21}$ бит; пикселей $2^{9} \cdot 2^{8} = 2^{17}$ .
$i = 2^{21} : 2^{17} = 2^{4} = 16$ бит на пиксель.
$N = 2^{16} = 65536$ цветов.

Объёмы относятся как произведения $a \cdot b \cdot i$ . Картинка вдвое больше по каждой стороне с глубиной 16 вместо 8 бит тяжелее в $2 \cdot 2 \cdot 2 = 8$ раз.

Самая частая ошибка — потерять множитель. Сначала всё переведите в биты ( $\times 8$ , $\times 1024$ ), потом делите.

Подробнее: модели цвета и вектор

RGB — аддитивная модель для экрана: красный, зелёный, синий; по 8 бит на канал дают 24 бита (True Color). CMYK — субтрактивная модель для печати.

Векторное изображение хранит не пиксели, а описания линий и фигур, поэтому не теряет качества при масштабировании.

Тема 4 · Информатика

Кодирование звука и передача данных

Потренироваться: задания по теме →

Простыми словами

Звук — непрерывная волна. Компьютер не может записать её целиком, поэтому много раз в секунду «замеряет» её высоту и записывает каждое измерение числом. Это дискретизация.

Фиолетовая — настоящий звук, точки — измерения, розовая ступенька — то, что записано в файл

Частота дискретизации $H$ сколько измерений в секунду, измеряется в герцах (Гц). 44 100 Гц — 44 100 замеров в секунду.

Глубина кодирования $b$ количество бит, отводимых на одно измерение сигнала. Больше бит — точнее уровень громкости.

Объём звукового файла

I = H \cdot b \cdot t \cdot k (бит)

H

— частота, Гц;

b

— глубина, бит;

t

— время, с;

k

— число каналов (моно 1, стерео 2)

Стерео, 20 с, 44 100 Гц, 8 бит. $b = 8$ бит $= 1$ байт, поэтому сразу в байтах: $I = 44100 \cdot 1 \cdot 20 \cdot 2 = 1764000$ байт.

Моно, 7 500 Кбайт, 16 000 Гц, 32 бита. Сколько секунд?

Объём в байтах: $7500 \cdot 1024 = 7680000$ .
Одна секунда занимает $16000 \cdot 4 байта = 64000$ байт.
$t = 7680000 : 64000 = 120$ с.

Так же из формулы выражают $b = \frac{I}{H \cdot t \cdot k}$ и $H = \frac{I}{b \cdot t \cdot k}$ .

Не забудьте множитель 2 для стерео. И помните: 1 Кбайт $= 1024$ байта, а 1 кГц $= 1000$ Гц — эти «кило» разные.

Объём видео

Видео — последовательность кадров. Каждый кадр — растровое изображение.

I = a \cdot b_{пикс} \cdot i \cdot f \cdot t

a \times b_{пикс}

— размер кадра в пикселях,

i

— глубина цвета, бит;

f

— кадров в секунду;

t

— время, с

$320 \times 240$ , 8 бит (1 байт), 25 кадр/с, 20 с: $320 \cdot 240 \cdot 1 \cdot 25 \cdot 20 = 38400000$ байт $= 37500$ Кбайт.

Передача данных

Скорость передачи $v$ измеряется в битах в секунду (бит/с, Кбит/с). 1 Кбит/с $= 1024$ бит/с: $256$ Кбит/с $= 262144$ бит/с.

I = v \cdot t, t = \frac{I}{v}, v = \frac{I}{t}

I

— объём, бит;

v

— скорость, бит/с;

t

— время, с

192 Кбайт со скоростью 131 072 бит/с. В степенях двойки: $I = 192 \cdot 2^{13}$ бит, $v = 2^{17}$ бит/с. $t = \frac{192 \cdot 2 ^{13}}{2 ^{17}} = \frac{192}{16} = 12$ с.

128 Кбайт $= 2^{7} \cdot 2^{13} = 2^{20}$ бит. По каналу $2^{16}$ бит/с — $16$ с, по каналу $2^{19}$ бит/с — $2$ с. Быстрее на $14$ с.

Перед делением приведите объём и скорость к одинаковым единицам — проще всего всё в биты. Числа вида 65 536, 131 072, 524 288 — это $2^{16}$ , $2^{17}$ , $2^{19}$ : так считать легче.

Подробнее: сжатие

Коэффициент сжатия — во сколько раз уменьшился объём файла. Сжатие без потерь (ZIP, PNG) восстанавливает данные точно; сжатие с потерями (MP3, JPEG) отбрасывает незаметные для человека детали и потому даёт больший выигрыш.

Тема 5 · Информатика

Элементы математической логики

Потренироваться: задания по теме →

События и множества: круги Эйлера

Простыми словами

Высказывание — утверждение, про которое можно сказать «истинно» (1) или «ложно» (0). «Идёт дождь» и «есть зонт» — высказывания; «идёт дождь и нет зонта» — сложное высказывание, и его истинность вычисляется по правилам, как пример по арифметике.

Конъюнкция — общая часть, дизъюнкция — всё, что внутри хотя бы одного круга

Логические операции

$A$	$B$	$\neg A$	$A \land B$	$A \lor B$	$A \to B$	$A \equiv B$
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

$\neg$ инверсия, «не»меняет значение на противоположное

$\land$ конъюнкция, «и»1, только если оба 1

$\lor$ дизъюнкция, «или»0, только если оба 0

$\to$ импликация, «если…то»ложна ровно в одном случае:

A = 1

B = 0

$\equiv$ эквивалентностьистинна, когда значения совпадают

Сначала скобки, затем $\neg$ , затем $\land$ , затем $\lor$ , последними — $\to$ и $\equiv$ .

$\neg (B \to A) \land C$ при $A = 0$ , $B = 1$ , $C = 1$ .

$B \to A = 1 \to 0 = 0$ .
$\neg0 = 1$ .
$1 \land C = 1 \land 1 = 1$ .

Таблица истинности

Для $n$ переменных в таблице $2^{n}$ строк: для двух — 4, для трёх — 8, для четырёх — 16. Наборы выписывают в порядке возрастания двоичной записи: 000, 001, 010, 011, 100, 101, 110, 111.

$B \to (C \lor \neg A)$ .

Импликация ложна только при $B = 1$ и $C \lor \neg A = 0$ .
$C \lor \neg A = 0$ лишь при $C = 0$ , $A = 1$ . Итак, ложный набор один: $A = 1, B = 1, C = 0$ .
Истинных наборов $8 - 1 = 7$ .

Часто проще посчитать, когда выражение ложно (для $\to$ и $\lor$ ) или истинно (для $\land$ ), и вычесть из $2^{n}$ .

Стёртую ячейку не угадывают, а вычисляют: берут из её строки значения переменных и подставляют в выражение. Для $(B \lor C) \to A$ при $A = 1$ ответ сразу 1: импликация с истинным следствием истинна.

Законы алгебры логики

Закон	Запись
де Моргана	$\neg (A \land B) = \neg A \lor \neg B$ ; $\neg (A \lor B) = \neg A \land \neg B$
замена импликации	$A \to B = \neg A \lor B$
поглощение	$A \land (A \lor B) = A$ ; $A \lor (A \land B) = A$
дистрибутивность	$A \land (B \lor C) = (A \land B) \lor (A \land C)$
противоречие и исключённое третье	$A \land \neg A = 0$ ; $A \lor \neg A = 1$
двойное отрицание	$\neg\neg A = A$

При отрицании скобки знак меняется: $\neg (A \land B)$ — это не $\neg A \land \neg B$ , а $\neg A \lor \neg B$ .

Тема 6 · Информатика

Логические схемы и упрощение выражений

Потренироваться: задания по теме →

Простыми словами

Лампочка в подъезде загорается, если нажата кнопка на первом или на втором этаже. Такие правила «включится/не включится» компьютер реализует логическими элементами — крошечными устройствами, которые получают сигналы 0 и 1 и выдают 0 или 1.

Элемент	Операция	Выход равен 1, когда…
И (конъюнктор)	$A \land B$	оба входа равны 1
ИЛИ (дизъюнктор)	$A \lor B$	хотя бы один вход равен 1
НЕ (инвертор)	$\neg A$	вход равен 0

Как читать схему

На схемах элементы — прямоугольники, сигналы идут по проводам слева направо. Подставляем значения входов, вычисляем выход каждого элемента и передаём дальше.

F = (A \land B) \lor \neg C

; при

A = 1, B = 0, C = 1

0 \lor 0 = 0

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

Последний элемент — И; на его входы приходят $\neg B$ (через инвертор) и выход ИЛИ от $A$ и $C$ . Значит, $F = \neg B \land (A \lor C)$ .

Стёртый элемент

Если подпись одного элемента стёрта, а дана таблица «входы → выход», перебираем кандидатов И, ИЛИ: подставляем каждый и смотрим, совпадают ли все строки таблицы.

На «?» приходят сигналы 0 и 1, а на выходе получилась 1. Элемент И дал бы $0 \land 1 = 0$ — не подходит; ИЛИ даёт $0 \lor 1 = 1$ — подходит. Проверяем остальные строки — и отвечаем ИЛИ.

Ищите строку, где входы элемента разные (0 и 1): только она отличает И от ИЛИ.

Упрощение выражений

Упрощают по законам алгебры логики: раскрывают импликацию $A \to B = \neg A \lor B$ , применяют законы де Моргана $\neg (A \land B) = \neg A \lor \neg B$ , $\neg (A \lor B) = \neg A \land \neg B$ , выносят общий множитель, пользуются поглощением.

Выражение	Равно	Выражение	Равно
$A \land 1$	$A$	$A \lor 0$	$A$
$A \land 0$	$0$	$A \lor 1$	$1$
$A \land A$	$A$	$A \lor A$	$A$
$A \land \neg A$	$0$	$A \lor \neg A$	$1$
$A \land (A \lor B)$	$A$	$(A \land B) \lor (A \land \neg B)$	$A$

(C \lor A) \lor (A \lor B) = A \lor B \lor C

Дизъюнкцию можно переставлять и группировать как угодно, а повторное $A \lor A = A$ .

\neg (A \to B) \lor B = \neg (\neg A \lor B) \lor B = (A \land \neg B) \lor B = A \lor B

Проверить упрощение можно таблицей истинности: у равносильных выражений все значения совпадают — 4 строки для двух переменных, 8 для трёх.

Тема 7 · Информатика

Алгоритмы, блок-схемы и исполнители

Потренироваться: задания по теме →

Простыми словами

Рецепт пирога — это алгоритм: понятные шаги, которые выполняются по порядку и приводят к результату. Повар — исполнитель: он делает только то, что умеет и что написано.

Алгоритм — точное и понятное предписание исполнителю выполнить конечную последовательность команд, приводящую к результату. Формальный исполнитель выполняет команды, не вникая в их смысл. Его описывают система команд (что он умеет), среда (где действует) и отказы (когда команда невыполнима).

Свойство	Что означает
Дискретность	состоит из отдельных завершённых шагов
Понятность	все команды входят в систему команд исполнителя
Определённость (детерминированность)	каждый шаг выполняется однозначно, без произвола
Результативность (конечность)	за конечное число шагов получается результат
Массовость	применим к целому классу исходных данных

«Друг Помог Очень Рано Маме» — Дискретность, Понятность, Определённость, Результативность, Массовость.

Блок-схемы

Овалначало и конец

Параллелограммввод и вывод данных

Прямоугольникдействие: присваивание, вычисление

Ромбпроверка условия; два выхода «да» и «нет»

Любой алгоритм собирается из трёх базовых конструкций: следование (шаги по очереди), ветвление (выбор по условию), повторение (цикл).

Цикл с предусловием: условие проверяется до тела цикла

Как выполнить блок-схему

Блок-схему выполняют «вручную» — заводят таблицу трассировки: столбец на каждую переменную и строку на каждый шаг.

Схема на рисунке выше. Что выведется и сколько раз выполнится тело цикла?

Проверка $k \leq 4$	$s$	$k$
—	0	1
$1 \leq 4$ да	3	2
$2 \leq 4$ да	6	3
$3 \leq 4$ да	9	4
$4 \leq 4$ да	12	5
$5 \leq 4$ нет — выход	вывод $s = 12$

Тело выполнилось 4 раза — столько, сколько раз условие было истинно.

Ввод $x = 7$ . Ромб: « $x > 5$ ?». «Да» → $y := 2 x$ , «нет» → $y := x + 10$ . Вложенный ромб на ветке «да»: « $y > 12$ ?» «да» → $y := y - 6$ .

$7 > 5$ — идём по «да»: $y = 14$ .
$14 > 12$ — снова «да»: $y = 14 - 6 = 8$ .
Вывод: $8$ .

Число повторений цикла — это число истинных проверок условия, а не число всех проверок (последняя, ложная, тело не запускает). И следите, что в теле меняется раньше: если сначала $k := k + 1$ , а потом $s := s + k$ , к $s$ прибавляется уже новое $k$ .

Исполнитель Удвоитель

Команды: 1 — прибавь 1, 2 — умножь на 2. Программа — строка из цифр-команд, выполняется слева направо.

Число $7$ , программа $221$ : $7 \cdot 2 = 14$ , $14 \cdot 2 = 28$ , $28 + 1 = 29$ .

Сколько программ переводят $A$ в $B$ ? Считаем от $A$ вверх: число программ $f (n)$ равно сумме $f$ для тех чисел, из которых в $n$ попадают одной командой.

f (n) = f (n - 1) + f (\frac{n}{2}) (второе слагаемое — если n чётно и \frac{n}{2} \geq A), f (A) = 1

динамика «с конца»

$n$	1	2	3	4	5	6	7	8
$f (n)$	1	1+1=2	2	2+2=4	4	4+2=6	6	6+4=10

Ответ: 10 программ. Например, $f (6) = f (5) + f (3)$ : в 6 приходят из 5 (+1) и из 3 (×2).

Слагаемое $f (n /2)$ берётся, только если $n /2 \geq A$ : из чисел меньше начального не начинают. Для «из 6 получить 45» не учитываем $f (3)$ .

Робот на клетчатом поле

Команды «вправо» и «вверх». Если цель на $a$ клеток правее и на $b$ выше, наименьшее число команд равно $a + b$ (обходить препятствия не нужно — назад робот ходить не умеет).

Число кратчайших путей: в каждую клетку приходят слева или снизу, поэтому число путей в клетку = сумма чисел в клетке слева и снизу. Без препятствий это число сочетаний:

P = C_{a + b}^{a} = \frac{( a + b )!}{a ! b !}

a

— шагов вправо,

b

— шагов вверх

Из С в Ц: 3 шага вправо и 2 вверх,

C_{5}^{3} = 10

путей, наименьшее число команд

5

3 вправо и 7 вверх: $C_{10}^{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$ путей, а наименьшее число команд $3 + 7 = 10$ .

Тема 8 · Информатика

Программирование и трассировка

Потренироваться: задания по теме →

Простыми словами

Программа — инструкция для очень исполнительного, но ничего не понимающего помощника. Чтобы узнать, что он напечатает, надо пройти программу вместо него, строка за строкой, записывая значения переменных. Это и есть трассировка.

Запись	Смысл	Пример
`=`	присваивание	`a = 7`
`==`, `!=`	сравнение: равно, не равно	`x % 8 == 0`
`//`	целая часть частного	`17 // 5` → 3
`%`	остаток от деления	`17 % 5` → 2
`**`	степень	`2 ** 3` → 8
`print()`, `input()`	вывод, ввод

a = 12; b = 71; y = (a + b) // 7: $83 : 7 = 11$ (ост. 6), выведется 11.

Ветвление

if x < 17:
    y = x - 5
elif x % 8 == 0:
    y = x + 7
else:
    y = x * x - 4

Условия проверяются сверху вниз; как только очередное истинно, выполняется его ветвь, остальные пропускаются. Тело ветви выделяется отступом — именно отступ, а не скобки, задаёт границы блока.

$x = 44$ : $44 < 17$ — нет; $44 mod 8 = 4 \neq = 0$ — нет; значит else: $44 \cdot 44 - 4 = 1932$ .

elif проверяет следующее условие, если все предыдущие оказались ложными; else срабатывает, когда ложны все. Операции: ** — возведение в степень, // — целочисленное деление, % — остаток, == — сравнение «равно», != — «не равно».

Циклы

for i in range(a, b): — $i$ пробегает $a, a + 1, \dots, b - 1$ ; всего $b - a$ повторений. Правая граница не входит!

Цикл for i in range(2, 11) выполнится

11 - 2 = 9

раз

while условие: — тело повторяется, пока условие истинно. Условие проверяется перед каждым повтором; если оно никогда не станет ложным — зацикливание.

i = 3; s = 0; k = 0
while s < 40:
    s = s + i * 2
    i = i + 2
    k = k + 1
print(i)

Шаг	$s$	$i$	$k$	$s < 40$ ?
старт	0	3	0	да
1	6	5	1	да
2	16	7	2	да
3	30	9	3	да
4	48	11	4	нет — выход

Напечатается $i = 11$ . Строка таблицы — значения после очередного выполнения тела.

Внимательно смотрите, что печатают ( $s$ , $i$ или $k$ ) и в каком порядке меняются переменные в теле: s = s + i * 2 стоит до i = i + 2, значит к $s$ прибавляется старое $i$ .

Обработка цифр числа

n % 10 — последняя цифра числа, n // 10 — число без последней цифры. Цикл while n > 0 перебирает цифры справа налево.

n = 48483
s = 1
while n > 0:
    s = s * (n % 10)
    n = n // 10
print(s)

Цифры по очереди: 3, 8, 4, 8, 4.
Произведение: $3 \cdot 8 \cdot 4 \cdot 8 \cdot 4 = 3072$ .

Начальное значение подсказывает смысл: s = 0 и s + … — сумма; s = 1 и s * … — произведение; k = 0 и k + 1 — счётчик.

Тема 9 · Информатика

Массивы и последовательности

Потренироваться: задания по теме →

Простыми словами

Массив — это ряд пронумерованных ячеек, как шкафчики в раздевалке. Чтобы взять вещь, достаточно знать номер шкафчика — индекс.

Массив (в Питоне — список) хранит элементы под номерами. Нумерация начинается с нуля: у массива из $n$ элементов индексы $0, 1, \dots, n - 1$ . Обращение к элементу: A[i]; len(A) — количество элементов.

A = [4, 7, 2, 9]: print(A[0], A[3]) выведет 4 9

Типовые алгоритмы

Задача	Идея
сумма элементов	`s = 0`, в цикле `s = s + A[i]`
количество по условию	`k = 0`, в цикле `if условие: k = k + 1`
максимум	`m = A[0]`, в цикле `if A[i] > m: m = A[i]`
индекс максимума	`im = 0`, в цикле `if A[i] > A[im]: im = i`
линейный поиск	идём по элементам слева направо, пока не встретим нужный
среднее арифметическое	сумма, делённая на количество элементов

A = [14, 15, 21, 16, 1, 6, 11]
s = 0
for i in range(len(A)):
    if i % 2 == 0:
        s = s + A[i]
print(s)

Условие на индекс, а не на значение: берём $i = 0, 2, 4, 6$ .
$A [0] + A [2] + A [4] + A [6] = 14 + 21 + 1 + 11 = 47$ .

A = [15, 22, 22, 19, 4, 10], в цикле A[i] = A[i] - 1, затем s = s + A[i]. Каждый элемент уменьшился на 1: $s = (15 + 22 + 22 + 19 + 4 + 10) - 6 = 92 - 6 = 86$ .

Если искомое число стоит под индексом 6, алгоритм выполнит $6 + 1 = 7$ сравнений — по одному на каждый просмотренный элемент.

Самая частая ошибка — «сдвиг на единицу». Индексы с нуля: «индекс наибольшего» на 1 меньше, чем его «номер по счёту». range(len(A)) даёт $0 \dots n - 1$ .

Массив — набор элементов одного типа, у каждого свой номер (индекс); к элементу по индексу обращаются за одно действие: A[3]. Сумма — накопитель s = 0 и в цикле s += A[i]; количество подходящих — счётчик k = 0, который увеличивают при выполнении условия. Чтобы поменять местами два элемента, нужна вспомогательная переменная: t = A[i]; A[i] = A[j]; A[j] = t (в Питоне можно и A[i], A[j] = A[j], A[i]). Рекуррентная формула задаёт член последовательности через предыдущие.

Рекуррентные последовательности

Рекуррентная формула задаёт первый член и правило получения следующего из предыдущего, например $a_{1} = 3$ , $a_{n + 1} = 2 a_{n} + 1$ . Чтобы найти $n$ -й член, заполняют таблицу по шагам.

$a_{1} = 6$ , $a_{n + 1} = 2 a_{n} + 4$ . Найти $a_{5}$ .

$n$	1	2	3	4	5
$a_{n}$	6	$2 \cdot 6 + 4 = 16$	36	76	156

Номер в таблице — это $n$ . Чтобы дойти от $a_{1}$ до $a_{8}$ , нужно сделать 7 шагов, а не 8.

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

Тема 10 · Информатика

Компьютер, файловая система и сети

Потренироваться: задания по теме →

Простыми словами

Компьютер похож на кухню: процессор — повар, оперативная память — рабочий стол (всё под рукой, но вечером убирают), внешняя память — шкаф с продуктами (хранится долго).

Устройство	Назначение
Процессор (АЛУ и УУ)	выполняет команды и арифметико-логические операции, управляет работой всех устройств
Оперативная память (ОЗУ)	хранит выполняемую программу и данные во время работы; энергозависима — при выключении всё стирается
Внешняя память	долговременное хранение: жёсткий диск, SSD, флеш-память
Устройства ввода	клавиатура, мышь, сканер, микрофон
Устройства вывода	монитор, принтер, колонки

Все узлы обмениваются данными через магистраль — шины данных, адреса и управления.

Программное обеспечение

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

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

Системы программированиятрансляторы, среды разработки, отладчики — для создания программ.

Вопрос «нужна ли эта программа, чтобы компьютер вообще работал?» Да — системное ПО; нет, она для дела пользователя — прикладное.

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

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

Полное имя: C:\АРХИВ\ИСТОРИЯ\zadacha.pas

Маска задаёт группу имён: * — любая последовательность символов (в том числе пустая), ? — ровно один символ.

Маска urok*.d?c: подходит urokab.doc (* = «ab», ? = «o») и urok.dac; не подходит urok1.docx (после «d» должно быть ровно два символа).

Звёздочка может означать и пустую строку: маске *kod*.txt подходит и kod.txt.

Сети и IP-адрес

Топологии локальных сетей: шина, звезда, кольцо, дерево. IP-адрес — четыре числа от 0 до 255 через точку (каждое — один байт). Маска подсети выделяет в нём адрес сети: адрес сети $=$ IP $\land$ маска (поразрядное И).

Байт маски 255 — байт адреса переписывается; 0 — получается 0; другое число — переводим оба в двоичную и делаем поразрядное И.

IP 10.149.202.191, маска 255.255.255.192.

Первые три байта маски — 255: 10.149.202 переписываем.
Четвёртый: $191 = 1011111 1_{2}$ , $192 = 1100000 0_{2}$ , И даёт $1000000 0_{2} = 128$ .
Адрес сети: 10.149.202.128.

Адрес ресурса в Интернете: протокол://сервер/путь/имя_файла.

Безопасность

Не открывать вложения от незнакомых отправителей; использовать сложные пароли и двухфакторную аутентификацию; обновлять антивирус; никому не сообщать коды из СМС.

Информатика: теория

Оглавление

Информация и измерение информации

Простыми словами

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

Содержательный подход: формула Хартли

Единицы измерения

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

Простыми словами

Перевод в десятичную и из десятичной

Двоичная ↔ восьмеричная и шестнадцатеричная

Арифметика в системе с основанием p

Свойства двоичной записи

Кодирование текста и графики

Простыми словами

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

Кодовая таблица

Кодирование графики

Задачи на изображения

Кодирование звука и передача данных

Простыми словами

Объём звукового файла

Объём видео

Передача данных

Элементы математической логики

Простыми словами

Логические операции

Таблица истинности

Законы алгебры логики

Логические схемы и упрощение выражений

Простыми словами

Как читать схему

Стёртый элемент

Упрощение выражений

Алгоритмы, блок-схемы и исполнители

Простыми словами

Блок-схемы

Как выполнить блок-схему

Исполнитель Удвоитель

Робот на клетчатом поле

Программирование и трассировка

Простыми словами

Ветвление

Циклы

Обработка цифр числа

Массивы и последовательности

Простыми словами

Типовые алгоритмы

Рекуррентные последовательности

Компьютер, файловая система и сети

Простыми словами

Программное обеспечение

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

Сети и IP-адрес

Безопасность

Арифметика в системе с основанием $p$