Формулы и лайфхаки

1Компьютер: информация, аппаратное и программное обеспечениеНачальный

Информация, её виды и информационные процессы

К уроку

Устройство компьютера: процессор, память и материнская плата

К уроку

N = f · t

где:

Nчисло тактов
fтактовая частота, Гц (1 ГГц = 1000 МГц = 10⁹ Гц)
tвремя, с

Герц — это «один раз в секунду»: частота показывает, сколько тактов в секунде.

N = 2ⁿ

где:

nразрядность шины адреса (число битов)
Nчисло ячеек памяти (байтов), к которым можно обратиться

Если каждая ячейка — 1 байт, можно обратиться к N байтам памяти.

Устройства ввода и вывода

К уроку

N = a · b

где:

Nчисло пикселей на экране
a, bчисло пикселей по горизонтали и по вертикали (разрешение a × b)

Число пикселей — произведение двух чисел разрешения.

d (см) = d (дюйм) · 2,54

где:

dдиагональ экрана

Чтобы перевести дюймы в сантиметры, умножьте на 2,54.

t = N / vt = N / v

где:

tвремя печати, мин
Nчисло страниц
vскорость принтера, стр./мин

Когда два принтера работают вместе, их скорости складываются.

Файловые системы и место на диске

К уроку

k = ⌈V / c⌉, V_disk = k · ck = ⌈V / c⌉, V_disk = k · c

где:

Vинформационный объём (размер) файла
cразмер кластера (в тех же единицах, что и V)
kчисло кластеров, занятых файлом
⌈ ⌉округление вверх: если есть дробная часть, берут следующее целое
V_diskместо, занимаемое файлом на диске

Место на диске — наименьшее кратное размера кластера, не меньшее размера файла.

ΔV = V_disk − V

где:

ΔVнеиспользуемое место в последнем кластере файла

Для каждого файла пустое место — от 0 до c − 1 байт; в среднем около половины кластера.

2Текстовые и табличные процессорыНачальный

Текстовые процессоры: редактирование, форматирование и клавиши

К уроку

Электронная таблица: адреса, диапазоны и формулы

К уроку

N = (S₂ − S₁ + 1) · (R₂ − R₁ + 1)

где:

Nчисло ячеек в диапазоне
S₁, S₂номера первого и последнего столбцов (A = 1, B = 2, …)
R₁, R₂номера первой и последней строк

Число столбцов × число строк. Не забывай «+1»: от B до F — 5 столбцов, а не 4.

Столбец′ = Столбец + Δс, Строка′ = Строка + Δr

где:

Δсна сколько столбцов формулу сдвинули вправо (+) или влево (−)
Δrна сколько строк вниз (+) или вверх (−)

Правило применяют к каждой части адреса отдельно. Часть, перед которой стоит $, не меняется. При вырезании и вставке (Ctrl+X → Ctrl+V) адреса в формуле вообще не меняются.

Функции в электронной таблице

К уроку

AVERAGE(D) = SUM(D) / COUNT(D)AVERAGE(D) = SUM(D) / COUNT(D)

где:

Dдиапазон (или список аргументов)
COUNT(D)количество чисел в D — пустые и текстовые ячейки не считаются

Среднее — это сумма, делённая на число ячеек с числами, а не на число всех ячеек.

TIME(ч; м; с) = ч/24 + м/1440 + с/86400TIME(ч; м; с) = ч/24 + м/1440 + с/86400

где:

ч, м, счасы, минуты, секунды
24, 1440, 86400число часов, минут и секунд в сутках

TIME возвращает долю суток (от 0 до 1). Умножив на 24, получишь часы, на 24 · 60 — минуты.

RADIANS(α) = α · π / 180RADIANS(α) = α · π / 180

где:

αугол в градусах
π / 180π / 1801° в радианах ≈ 0,01745

180° = π радиан. Для обратного перевода в Excel есть функция DEGREES.

=RAND()*(b − a) + a → a ≤ x < b

где:

a, bконцы промежутка; RAND() · (b − a) растягивает длину, + a сдвигает промежуток

Если нужно целое число, добавляют функцию целой части INT: =INT(RAND()*6)+1 даёт числа от 1 до 6, как игральная кость.

Диаграммы в электронной таблице и их элементы

К уроку

p = x / S · 100%, α = x / S · 360°p = x / S · 100%, α = x / S · 360°

где:

xзначение ячейки, соответствующей сектору
Sсумма всех значений диапазона
pдоля сектора в процентах
αцентральный угол сектора

Проценты всех секторов в сумме дают 100%, углы — 360°. Если меняется одно значение, меняется и S, поэтому меняются все проценты.

3Кодирование и измерение информацииСредний

Измерение информации: бит, байт и единицы измерения

К уроку

N = 2ⁱ

где:

Nчисло различных кодируемых вариантов (символов, цветов, уровней…); для алфавита — мощность алфавита
iчисло бит в коде одного варианта — количество информации, которое несёт один вариант (символ)

Из i бит составляется 2ⁱ различных кодов. Если известно N, то i = log₂N; если N не степень двойки, i округляют вверх.

1 Кбайт = 2¹³ бит 1 Мбайт = 2²³ бит 1 Гбайт = 2³³ бит

где:

2³ = 8множитель между байтом и битом
2¹⁰ = 1024множитель между соседними единицами (байт → Кбайт → Мбайт → Гбайт)

В битах показатели равны 3, 13, 23, 33, 43: у каждой следующей единицы показатель больше на 10.

I = K · i

где:

Iинформационный объём сообщения (бит)
Kчисло символов в сообщении
iинформационный объём одного символа (бит); N = 2ⁱ

Для текста из нескольких страниц K = число страниц · строк на странице · символов в строке.

I = v · t

где:

Iобъём переданной информации (бит)
vскорость передачи (бит/с)
tвремя передачи (с)

Отсюда t = I / v и v = I / t. Сначала переведи объём в биты, а время — в секунды.

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

К уроку

I = K · 8 бит (ASCII) I = K · 16 бит (UNICODE)

где:

Iинформационный объём текста
Kчисло всех символов текста: буквы, цифры, пробелы, знаки препинания

Это частный случай формулы I = K · i: в ASCII i = 8, в UNICODE i = 16. Один и тот же текст в UNICODE занимает вдвое больше места, чем в ASCII.

i = I / K, N = 2ⁱi = I / K, N = 2ⁱ

где:

iчисло бит на один символ
Iобъём текстовой части (бит); объём рисунков сначала вычитают
Kчисло символов
Nмощность алфавита

Ключ к обратным задачам: сначала выдели объём текста, потом раздели на число символов.

Компьютерная графика: кодирование растровых и векторных изображений

К уроку

N = 2ⁱ

где:

Nчисло цветов (оттенков) в палитре
iглубина цвета — число бит в коде одного пикселя

Если палитра не степень двойки, i округляют вверх: для 100 цветов нужно 7 бит (2⁷ = 128). В заданиях DİM это звучит так: «каждый цвет кодируется минимально возможным числом бит».

V = W · H · i

где:

Vинформационный объём растрового изображения (бит)
Wчисло пикселей по ширине
Hчисло пикселей по высоте
iглубина цвета (бит), N = 2ⁱ

Сначала найди i по палитре, затем перемножь и переведи биты в нужные единицы: 2¹³ бит = 1 Кбайт, 2²³ бит = 1 Мбайт.

V₂ / V₁ = (W₂ / W₁) · (H₂ / H₁) · (i₂ / i₁)V₂ / V₁ = (W₂ / W₁) · (H₂ / H₁) · (i₂ / i₁)

где:

W₂ / W₁, H₂ / H₁W₂ / W₁, H₂ / H₁во сколько раз изменились ширина и высота
i₂ / i₁i₂ / i₁отношение глубин цвета — не палитр!

Когда палитра уменьшается в 2ᵏ раз, глубина цвета уменьшается на k бит, а объём — не в 2ᵏ раз, а в i₁ / (i₁ − k) раз.

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

К уроку

V = f · i · t · k

где:

Vобъём звукового файла (бит)
fчастота дискретизации (Гц)
iглубина кодирования (бит)
tдлительность записи (с)
kчисло каналов: моно 1, стерео 2

По сути это «число измерений × биты одного измерения»: f · t · k измерений по i бит.

V = W · H · i · n · t

где:

W · H · iобъём одного кадра (бит), как у растрового изображения
nчастота кадров (кадр/с)
tдлительность видео (с)

Если есть звуковая дорожка, прибавь и её объём f · i · t · k. Формула даёт объём несжатого видео.

k = V₀ / Vk = V₀ / V

где:

kкоэффициент сжатия — во сколько раз уменьшился файл
V₀объём до сжатия
Vобъём сжатого файла

Для потокового звука и видео вместо объёмов можно сравнивать скорости в бит/с.

4Системы счисления и логикаСредний

Системы счисления: позиционные системы и двоичная система

К уроку

N = aₖ·bᵏ + aₖ₋₁·bᵏ⁻¹ + … + a₁·b + a₀

где:

Nзначение числа в десятичной системе
bоснование системы (b ≥ 2)
aᵢцифра в i-м разряде, 0 ≤ aᵢ ≤ b − 1
kномер старшего разряда: количество цифр − 1

Развёрнутая запись числа. Разряды нумеруются справа налево, начиная с 0. Вычислив эту сумму, мы переводим число из любой системы в десятичную.

Nₘₐₓ = bᵏ − 1, Nₘᵢₙ = bᵏ⁻¹

где:

kколичество цифр
bоснование системы

Наибольшее и наименьшее k-значные числа в системе с основанием b. Всего таких чисел bᵏ − bᵏ⁻¹ = (b − 1)·bᵏ⁻¹.

N = b·q + r, 0 ≤ r ≤ b − 1

где:

qнеполное частное
rостаток — последняя цифра числа в системе с основанием b

Метод деления работает для любого основания: делим на b. Короткое следствие: двоичное число, оканчивающееся на 0, чётное, а на 1 — нечётное.

2ⁿ = 100…0₂ (1 и n нулей), 2ⁿ − 1 = 11…1₂ (n единиц)

где:

nпоказатель степени

Число нулей = количество цифр − число единиц. Например, 2⁹ − 1 = 511 = 111111111₂ — девять единиц.

2ᵏ⁻¹ ≤ N < 2ᵏ

где:

Nнатуральное число
kколичество цифр в двоичной записи N

Если неравенство выполняется, в двоичной записи N ровно k цифр. Например, 512 ≤ 1000 < 1024, поэтому 1000 = 1111101000₂ — десятизначное число.

Восьмеричная и шестнадцатеричная системы счисления

К уроку

N = aₖ·8ᵏ + … + a₂·64 + a₁·8 + a₀, 0 ≤ aᵢ ≤ 7

где:

Nзначение числа в десятичной системе
aᵢвосьмеричная цифра в i-м разряде

Развёрнутая запись восьмеричного числа. При обратном переводе делим на 8: остаток — последняя цифра.

N = aₖ·16ᵏ + … + a₂·256 + a₁·16 + a₀, 0 ≤ aᵢ ≤ 15

где:

aᵢшестнадцатеричная цифра: 0–9 или A = 10, …, F = 15

Развёрнутая запись шестнадцатеричного числа. При переводе из десятичной делим на 16; остатки 10–15 записываются одной буквой.

b = 2ᵐ ⇒ 1 цифра системы с основанием b = m бит: 8 = 2³ → 3 бита, 16 = 2⁴ → 4 бита

где:

mчисло битов на одну цифру

То же правило работает для 4 = 2²: в 4-ричной системе биты группируют по два.

n битов → ⌈n/3⌉ восьмеричных цифр, ⌈n/4⌉ шестнадцатеричных цифрn битов → ⌈n/3⌉ восьмеричных цифр, ⌈n/4⌉ шестнадцатеричных цифр

где:

nколичество двоичных цифр
⌈x⌉наименьшее целое число, не меньшее x

Если n делится на 4 (на 3), округлять не нужно: 2²⁴ битов → 2²⁴ : 2² = 2²² шестнадцатеричных цифр.

Арифметические действия в различных системах счисления

К уроку

s = q·b + r → в разряд пишем r, q переносим в следующий разряд

где:

sсумма цифр разряда и переноса
bоснование системы
rзаписываемая цифра, 0 ≤ r ≤ b − 1
qперенос

При сложении s ≤ 2(b − 1) + 1, поэтому перенос всегда 0 или 1; при умножении q может быть больше.

если a < c: цифра = a + b − c, левый разряд уменьшается на 1

где:

aцифра уменьшаемого
cцифра вычитаемого
bоснование системы

Самый частый случай в двоичной системе: 10₂ − 1₂ = 1₂, то есть 2 − 1 = 1.

N·bᵏ: справа приписываем k нулей; N : bᵏ: отбрасываем последние k цифр — это остаток

где:

Nчисло, записанное в системе с основанием b
kсдвиг (количество разрядов)

Общий вид десятичного правила 37·100 = 3700. В двоичной системе умножить на 2 — сдвинуть на один разряд влево, разделить на 2 — на один разряд вправо.

хранимый результат = (a + c) mod 2ⁿ

где:

a, cслагаемые (целые числа без знака)
nчисло битов в ячейке
modостаток от деления

Если сумма не больше 2ⁿ − 1, переполнения нет и результат верный.

Системы счисления: задачи с неизвестным основанием

К уроку

aₖ…a₁a₀ₓ = aₖ·xᵏ + … + a₁·x + a₀, x > наибольшей цифры

где:

xнеизвестное основание — натуральное число, x ≥ 2
aᵢцифры числа

Условие на цифры: основание больше всех цифр равенства. Корни уравнения, не удовлетворяющие этому условию, отбрасываются.

N = b·q + r, 0 ≤ r < b ⟹ b | (N − r), b > r

где:

rпоследняя цифра N в системе с основанием b (остаток)
b | MM делится на b без остатка

Последняя цифра = остаток от деления N на основание.

bᵏ⁻¹ ≤ N < bᵏ

где:

kколичество цифр N в системе с основанием b

Выбирают все натуральные основания b ≥ 2, удовлетворяющие этому двойному неравенству.

mm…mₙ (k цифр) = nᵏ − 1, m = n − 1

где:

nоснование системы
mнаибольшая цифра системы

Например, mmₙ = (n − 1)·n + (n − 1) = n² − 1: 77₈ = 63, 66₇ = 48.

2ⁿ − 2ᵐ = 11…1 00…0₂ (n − m единиц, m нулей), n > m

где:

n, mпоказатели степеней

Например, 2⁸ − 2³ = 256 − 8 = 248 = 11111000₂: пять единиц, три нуля.

(2ᵃ + 2ᶜ)² = 2²ᵃ + 2ᵃ⁺ᶜ⁺¹ + 2²ᶜ, a − c ≥ 2

где:

a, cпоказатели степеней, a > c

При a − c ≥ 2 три степени различны, поэтому в двоичной записи квадрата ровно три единицы; количество цифр равно 2a + 1.

5МоделированиеСредний

Модели и моделирование

К уроку

S = S₀ · (1 + p/100)ⁿS = S₀ · (1 + p/100)ⁿ

где:

S₀начальная сумма (манаты)
pгодовой процент банка (%)
nчисло лет
Sсумма на счёте через n лет

Математическая модель банковского вклада: каждый год сумма увеличивается в (1 + p/100) раза.

h = h₀ − g · t² / 2h = h₀ − g · t² / 2

где:

h₀начальная высота (м)
gускорение свободного падения, ≈ 9,8 м/с²
tвремя от начала падения (с)
hвысота в момент t (м)

Динамическая модель свободного падения; допущение: сопротивлением воздуха пренебрегаем.

Табличные информационные модели: решение логических задач с помощью таблиц

К уроку

n · (n − 1) / 2n · (n − 1) / 2

где:

nчисло объектов (сёл, команд)

Число различных пар из n объектов: в симметричной таблице нужно ровно столько разных чисел, а ненулевых клеток вдвое больше — n · (n − 1).

в каждой строке ровно один «+» · в каждом столбце ровно один «+»

Правило взаимно однозначного соответствия: в таблице n × n в конце n знаков «+» и n · (n − 1) знаков «–».

сумма итогов по строкам = сумма итогов по столбцам = число знаков «+»

Контрольная сумма: если каждый из 6 человек купил 2 вещи, то сумма по столбцам тоже должна быть 6 · 2 = 12.

(a₁ + a₂ + … + aₙ) / n(a₁ + a₂ + … + aₙ) / n

где:

a₁, …, aₙчисла (количество страниц, баллы)
nколичество чисел

Среднее арифметическое. Найти его и понять, какому объекту оно соответствует, — часто первый шаг задачи на порядок.

Древовидные информационные модели

К уроку

m = n − 1

где:

nчисло узлов дерева
mчисло рёбер (ветвей)

Каждый узел, кроме корня, соединён со своим родителем ровно одним ребром, поэтому рёбер на одно меньше, чем узлов.

диск:\папка₁\папка₂\…\имя.расширение

где:

диск:\корневая папка диска, например C:\
папка₁ … папкаₖпапки на пути от корня к файлу, сверху вниз
имя.расширениеимя и расширение файла

Полное имя файла — единственный путь от корня к файлу.

n = 1 + k + k² + … + kʰ, yarpaqlar = kʰ

где:

kчисло потомков у каждого внутреннего узла (у всех одинаковое)
hвысота дерева; все листья на уровне h
nобщее число узлов

Полное дерево: на каждом уровне узлов в k раз больше. При k = 2 n = 2ʰ⁺¹ − 1.

Графы как информационные модели: матрица смежности и число путей

К уроку

deg(A₁) + deg(A₂) + … + deg(Aₙ) = 2 · m

где:

deg(Aᵢ)степень i-й вершины
mчисло рёбер

Правило «рукопожатий»: каждое ребро принадлежит двум вершинам и учитывается в сумме степеней дважды. Значит, сумма степеней всегда чётна.

m = n · (n − 1) / 2m = n · (n − 1) / 2

где:

nчисло вершин
mчисло рёбер в полном графе

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

неориентированный граф: N₁ = 2 · m орграф: N₁ = m

где:

N₁число единиц в матрице смежности
mчисло рёбер (дуг)

В орграфе дуга X → Y даёт единицу только в одной клетке — на пересечении строки X и столбца Y; такая матрица обычно несимметрична.

N(X) = N(Y₁) + N(Y₂) + … + N(Yₖ), N(A) = 1

где:

N(X)число различных путей из A в X
Y₁, …, Yₖвсе вершины, из которых в X ведёт стрелка (прямая дорога)

В начальную вершину пишут 1; число в каждой вершине — сумма чисел в вершинах, откуда в неё входят стрелки.

N(A → K, D-dən keçməklə) = N(A → D) · N(D → K)

где:

N(A → D)число путей из A в D
N(D → K)число путей из D в K (пишем 1 в D и считаем заново)

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

6АлгоритмыСредний

Алгоритм, его свойства и способы описания

К уроку

переменная = выражение

где:

переменнаяместо, куда записывается новое значение; старое стирается
выражениевычисляется по текущим значениям переменных

Правило присваивания: сначала вычисляется правая часть, затем результат записывается в переменную слева

Разветвляющиеся алгоритмы

К уроку

D = b² − 4·a·c

где:

Dдискриминант: D > 0 — два корня, D = 0 — один корень, D < 0 — действительных корней нет
a, b, cкоэффициенты уравнения a·x² + b·x + c = 0 (a ≠ 0)

Три случая разделяют два ромба: сначала D > 0, затем D = 0

(год % 4 = 0 и год % 100 ≠ 0) или год % 400 = 0

где:

%остаток от деления; «год % 4 = 0» — год делится на 4
≠не равно

Правило високосного (366-дневного) года григорианского календаря — классическое составное условие

Циклические алгоритмы и таблица трассировки

К уроку

S = S + x; P = P · x; k = k + 1

где:

Sсумма; начальное значение 0
Pпроизведение; начальное значение 1 (с 0 оно навсегда останется 0)
kколичество (счётчик); начальное значение 0

Три «накопительные» переменные цикла и их начальные значения

r = n % 10, n = n // 10

где:

n % 10последняя цифра числа (остаток от деления на 10)
n // 10число без последней цифры (целочисленное деление)

Цикл по цифрам: пока n > 0, берём последнюю цифру и отбрасываем её

a₀ + p·k ≥ b₀ − q·k ⇒ k = ⌈(b₀ − a₀) / (p + q)⌉a₀ + p·k ≥ b₀ − q·k ⇒ k = ⌈(b₀ − a₀) / (p + q)⌉

где:

a₀, b₀начальные значения переменных (a₀ < b₀)
p, qприрост a и уменьшение b на каждом шаге
kчисло повторений цикла «a < b»
⌈ ⌉округление вверх: 10,875 → 11

Цикл останавливается, как только a ≥ b: разрыв сокращается на p + q за шаг

Построение блок-схем: письменные задания

К уроку

S = 1 − 1/3 + 1/5 − 1/7 + … , aᵢ = k / (2·i − 1), k = −kS = 1 − 1/3 + 1/5 − 1/7 + … , aᵢ = k / (2·i − 1), k = −k

где:

iномер слагаемого, от 1 до N
2·i − 1знаменатель i-го слагаемого: 1, 3, 5, 7, …
kзнак: начинается с 1 и на каждом шаге становится −k (1, −1, 1, …)

Общий член знакочередующегося ряда: знак хранится в отдельной переменной

y = 2·x + 5, если x < 3; y = x² − 4, если x ≥ 3

где:

xцелое число, вводимое на каждом шаге цикла
yзначение функции: ромб выбирает одну из двух формул

Задача: вычислить y для n чисел и вывести сумму значений, больших 20

Алгоритмы сортировки

К уроку

K = n(n − 1) / 2K = n(n − 1) / 2

где:

Kчисло сравнений в худшем случае
nколичество элементов в списке

7Программирование на Python (школьный курс)Средний

Языки программирования и Python: переменные, ввод и вывод

К уроку

a = b · (a // b) + a % b, 0 ≤ a % b < b

где:

aделимое (целое число)
bделитель, b > 0
a // bнеполное частное
a % bостаток

Деление с остатком: // и % всегда работают в паре. Проверка: частное, умноженное на делитель, плюс остаток должно дать делимое.

( ) → ** → * / // % → + −2 ** 3 ** 2 = 2 ** 9 = 512

Приоритет операций (убывает слева направо). Операции одного уровня * / // % выполняются слева направо, а ** — справа налево: 2 ** 3 ** 2 = 2 ** 9 = 512. ** сильнее унарного минуса: -2 ** 2 = −4.

n = 100·a + 10·b + c ⇒ a = n // 100, b = n // 10 % 10, c = n % 10

где:

nтрёхзначное натуральное число
aцифра сотен
bцифра десятков
cцифра единиц (последняя)

n % 10 всегда даёт последнюю цифру, а n // 10 — число без последней цифры. Цифры чисел любой длины с помощью циклов разбираются в уроке «Операции над числами: цифры, делители и простые числа».

Условный оператор: if, elif, else и составные условия

К уроку

арифметика → == != < > <= >= → not → and → or

Приоритет убывает слева направо: сначала арифметика, затем сравнения, потом not, and и в самом конце or. Сомневаешься — ставь скобки: программа станет и правильной, и понятной.

Быстрый способ: периодические таблицы и подсчёт «Yes»

• Если узор повторяется каждые k шагов, смотри на n % k и распределяй остатки по ветвям — достаточно выписать вручную один-два «периода».
• В задаче «сколько раз Yes?» разбей условие на части: если одна из частей, соединённых or, истинна, остальное проверять не нужно; для and хватает одного ✗ (Python и сам вычисляет именно так, «по короткой схеме»).
• Считая символы, выписывай только те print, которые действительно выполняются, и складывай их символы.

Операторы цикла: for, while, шаг цикла, break, continue и вложенные циклы

К уроку

N = ⌈(b − a) / d⌉N = ⌈(b − a) / d⌉

где:

Nчисло итераций; если выражение меньше или равно 0, цикл не выполняется ни разу
aначальное значение
bконечное значение (не входит)
dшаг (может быть отрицательным)
⌈x⌉x, округлённое вверх до ближайшего целого

Число итераций range(a, b, d). Последнее значение переменной цикла равно a + (N − 1) · d. При шаге 1 просто N = b − a; для всех целых чисел отрезка [a; b] пишут range(a, b + 1), и N = b − a + 1.

K = b // m − (a − 1) // m

где:

Kколичество натуральных чисел отрезка [a; b], кратных m
a, bконцы отрезка (натуральные числа)
mделитель

Подсчёт без цикла: на [1; b] кратных m ровно b // m, вычитаем те, что лежат на [1; a − 1]. Именно так считают вместо трассировки циклов по большим промежуткам.

N = N₁ · N₂

где:

Nобщее число выполнений внутреннего тела
N₁итерации внешнего цикла
N₂итерации одного прохода внутреннего цикла

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

Быстрый способ: считаем, не раскручивая цикл

• Число итераций: ⌈(b − a) / d⌉, при шаге 1 просто b − a; на отрезке [a; b] лежит b − a + 1 целое число.
• Кратные m на [a; b]: b // m − (a − 1) // m.
• Не трассируй цикл больше чем на 100 итераций: раздели числа на группы по условию и посчитай каждую группу формулой — так делают и официальные разборы экзамена.
• В таблице трассировки оставляй только меняющиеся столбцы: итерация, условие (✓/✗), переменные.
• Если граница внутреннего цикла зависит от внешней переменной, выпиши числа внутренних итераций и сложи: 5 + 4 + 3 + 2.

Операции над числами: цифры, делители и простые числа

К уроку

d = n % 10 n = n // 10

где:

dпоследняя цифра (0…9)
%остаток от деления
//целочисленное деление: дробная часть отбрасывается, число становится на одну цифру короче

Две главные команды цикла по цифрам. Цикл работает с условием while n > 0:.

n // pow(10, k) % 10 n % pow(10, k) n // pow(10, k)

где:

n // pow(10, k) % 10k-я цифра справа (k = 0 — единицы, 1 — десятки, 2 — сотни)
n % pow(10, k)число из последних k цифр
n // pow(10, k)число, оставшееся после отбрасывания последних k цифр

Любую цифру можно взять и без цикла: 5682 // 100 % 10 = 6, 5682 % 100 = 82, 5682 // 1000 = 5.

r = r * 10 + n % 10

где:

rперевёрнутое число; в начале r = 0
n % 10очередная последняя цифра

Перевёрнутое число: для 5682 r = 2, 28, 286, 2865. Проверка на палиндром: после цикла r == m (m — копия исходного числа).

a * pow(10, c) + n n * 10 + a

где:

cколичество цифр числа n (счётчик цикла по цифрам)
aдобавляемая цифра

Приписать цифру a к числу слева и справа.

n % i == 0, i = 1, 2, …, n

где:

iпроверяемый кандидат в делители
c == 2если делителей ровно 2, n — простое

Цикл по делителям: for i in range(1, n + 1): и внутри if n % i == 0:.

pow(a, 0.5) == int(pow(a, 0.5))

где:

pow(a, 0.5)квадратный корень из a, дробное число (49 ** 0.5 → 7.0)
int(…)отбрасывает дробную часть

Если корень — целое число, a — полный квадрат. В решениях ГЭЦ встречается и запись a ** (1/2) — это то же самое.

НОД(a; b) = НОД(b; a % b), НОД(a; 0) = a

где:

a % bостаток от деления a на b
b = 0останавливаемся, когда остаток равен 0: ответ — a

Алгоритм Евклида. В учебниках есть и вариант с вычитанием: вычитай меньшее число из большего, пока числа не станут равны.

НОК(a; b) = a · b / НОД(a; b)НОК(a; b) = a · b / НОД(a; b)

где:

a · bпроизведение двух чисел

Наименьшее общее кратное сразу получается из НОД.

S = 1 + 1/2 + 1/3 + … + 1/n n! = 1 · 2 · 3 · … · nS = 1 + 1/2 + 1/3 + … + 1/n n! = 1 · 2 · 3 · … · n

где:

s = s + 1 / is = s + 1 / iшаблон суммы в цикле
p = p * iшаблон факториала (в начале p = 1)

i — переменная цикла: for i in range(1, n + 1):.

Анализ программы: от результата к входным данным

К уроку

n = n₀ + k · d s = s₀ · qᵏ

где:

n₀, s₀значения до цикла
dчисло, прибавляемое на каждом шаге (n = n + d)
qчисло, на которое умножают на каждом шаге (s = s * q)
kчисло итераций

Сложение даёт арифметическую прогрессию, умножение — геометрическую.

усл(x₍ₖ₋₁₎) — истинно, усл(xₖ) — ложно

где:

xₖзначение переменной цикла после k итераций, выраженное через ввод (например, s₀ + k · m)

Условие того, что цикл выполнится ровно k раз.

x // q = y ⇔ q · y ≤ x ≤ q · y + q − 1

где:

qделитель (a = a // q)
yрезультат целочисленного деления

Шаг назад через целочисленное деление: наименьшее x = q · y, наибольшее x = q · y + q − 1.

количество = R − L + 1 1 + 2 + … + k = k(k + 1) / 2количество = R − L + 1 1 + 2 + … + k = k(k + 1) / 2

где:

L, Rнаименьший и наибольший подходящий ввод
k(k + 1) / 2k(k + 1) / 2сумма первых k натуральных чисел

Количество целых чисел на отрезке и сумма с растущим шагом.

Строки и операции над ними

К уроку

s[i] s[-1] = s[len(s) - 1]

где:

s[i]символ с индексом i (тоже строка)
len(s)количество символов; последний индекс — len(s) − 1

s[len(s)] вызывает ошибку (IndexError): такого индекса нет.

s[a:b:c]

где:

aначальный индекс (включается); если не указан — с начала
bконечный индекс (не включается); если не указан — до конца
cшаг; по умолчанию 1; отрицательный шаг идёт справа налево

Срез идёт от a до b − 1 с шагом c. s[::-1] — перевёрнутая строка; при c = 1 в срезе b − a символов.

NBa = (Dkod + 2 · Dyazılı) · 100 / 33NBa = (Dkod + 2 · Dyazılı) · 100 / 33

где:

NBaотносительный балл за открытые задания
Dkodчисло верных кодируемых ответов (0–5)
Dyazılıсумма баллов за письменные задания (0–3)

Закрытая часть добавляет 100/33 · (Dq − Yq/4); максимум по предмету — 100. Письменное задание весит столько же, сколько два задания с кодируемым ответом.

8Базы данныхПродвинутый

Базы данных: модели, СУБД и связанные таблицы

К уроку

Запросы, поиск и сортировка в базе данных

К уроку

M(A AND B) = M(A) ∩ M(B)

где:

M(A)номера записей, удовлетворяющих условию A
∩пересечение: входят в оба множества

AND — должны выполняться оба условия: остаются общие номера.

M(A OR B) = M(A) ∪ M(B)

где:

∪объединение: входят хотя бы в одно множество

OR — должно выполняться хотя бы одно условие: номера объединяются без повторов.

M(NOT A) = U \ M(A)

где:

Uвсе записи таблицы
\разность: из U убираем M(A)

NOT — остаются записи, не удовлетворяющие условию.

NOT (A AND B) = (NOT A) OR (NOT B) · NOT (A OR B) = (NOT A) AND (NOT B)

где:

A, Bлюбые условия

Законы де Моргана: при внесении NOT в скобки AND и OR меняются местами.

9Сети, интернет и информационная безопасностьПродвинутый

Поиск в интернете: поисковые системы и запросы

К уроку

n(A OR B) = n(A) + n(B) − n(A AND B)

где:

n(A), n(B)число страниц, найденных по запросам A и B
n(A AND B)число страниц, где есть оба слова
n(A OR B)число страниц, где есть хотя бы одно из слов

Формула включений и исключений для двух множеств. Если известны три величины из четырёх, находится и четвёртая.

n(A AND NOT B) = n(A) − n(A AND B)

где:

n(A AND NOT B)число страниц, где есть A, но нет B

Из круга A вычитается общая часть, а не весь B!

n(A OR B OR C) = n(A) + n(B) + n(C) − n(A AND B) − n(A AND C) − n(B AND C) + n(A AND B AND C)

где:

n(A AND B AND C)число страниц, где есть все три слова (центр, часть 7)

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

Кибербезопасность: пароли, фишинг и конфиденциальность

К уроку

C = Aᴸ

где:

Cколичество возможных паролей
Aмощность алфавита — сколько разных символов можно использовать
Lдлина пароля (количество символов)

Формула N = 2ⁱ из первого урока — частный случай: там в алфавите было всего 2 символа, 0 и 1.

Защита информации и криптография

К уроку

y = (x + k) mod n

где:

xномер буквы открытого текста
yномер буквы шифртекста
kключ — величина сдвига
nчисло символов в алфавите (26, 32 или 10)
mod nостаток от деления на n: алфавит «замыкается в круг»

Шифрование: на k позиций вправо.

x = (y − k) mod n

Расшифрование: на k позиций влево. Если получилось отрицательное число, прибавьте n: например, (1 − 3) mod 26 = −2 + 26 = 24.

k = (y − x) mod n; k = (k₁ + k₂) mod n

где:

x, yномера соответствующих букв открытого текста и шифртекста
k₁, k₂ключи двух шифрований подряд

Чтобы найти ключ, достаточно одной буквы; два сдвига складываются. Сдвиг на k влево — это сдвиг на n − k вправо.

10Веб-программированиеПродвинутый

Веб-программирование: создание сайта, теги HTML и списки

К уроку

Таблицы, цветовая схема, изображения и ссылки в HTML

К уроку

N = 256 · 256 · 256 = 2²⁴ = 16 777 216

где:

#RRGGBBкод цвета: три шестнадцатеричные пары — красный, зелёный, синий
256число значений одной пары: 00…FF = 0…255
Nчисло цветов, которые можно записать

Каждый цвет кодируется 3 байтами = 24 битами — как True Color в растровой графике.

h₂ = h₁ · w₂ / w₁h₂ = h₁ · w₂ / w₁

где:

w₁, h₁собственные ширина и высота изображения (пиксели)
w₂ширина, заданная в атрибуте width
h₂высота, которую покажет браузер

Если задана только width (или только height), браузер сохраняет пропорции.

11Алгоритмы и структуры данныхУниверситет

Сложность алгоритмов и О-нотация

К уроку

1 + 2 + … + (n − 1) = n(n − 1) / 21 + 2 + … + (n − 1) = n(n − 1) / 2

где:

nразмер входных данных (число элементов)

Сумма Гаусса: число операций во вложенных циклах вида «каждый элемент с каждым по одному разу».

f(n) = O(g(n)) ⇔ ∃ c > 0, ∃ n₀: 0 ≤ f(n) ≤ c · g(n) ∀ n ≥ n₀

где:

f(n)число операций алгоритма
g(n)функция сравнения (n, n², n log n …)
cположительная константа
n₀размер, начиная с которого выполняется неравенство

f(n) = Ω(g(n)) ⇔ ∃ c > 0, n₀: f(n) ≥ c · g(n) ∀ n ≥ n₀; f(n) = Θ(g(n)) ⇔ f = O(g) и f = Ω(g)

Ω — нижняя оценка, Θ — одновременно верхняя и нижняя («зажата» между двумя константами).

T(n) = 2T(n/2) + cn ⇒ T(n) = cn · log₂ n + n · T(1) = Θ(n log n)T(n) = 2T(n/2) + cn ⇒ T(n) = cn · log₂ n + n · T(1) = Θ(n log n)

где:

T(n)время работы на входе из n элементов
2T(n/2)2T(n/2)рекурсивная обработка двух половин
cnработа по разбиению и слиянию (линейная)

Дерево рекурсии: на уровне k находится 2ᵏ подзадач размера n/2ᵏ, общая работа уровня 2ᵏ · c · n/2ᵏ = cn. Уровней log₂ n, поэтому всего cn · log₂ n.

T(n) = a · T(n/b) + Θ(nᵈ)T(n) = a · T(n/b) + Θ(nᵈ)

где:

aчисло рекурсивных вызовов (a ≥ 1)
bво сколько раз уменьшается размер (b > 1)
dпоказатель степени работы по разбиению и объединению (d ≥ 0)

Основная теорема (упрощённая форма): сравни a с bᵈ. a < bᵈ → Θ(nᵈ); a = bᵈ → Θ(nᵈ · log n); a > bᵈ → Θ(nᵖ), где p = log a / log b.

Массивы, связные списки, стеки и очереди

К уроку

addr(A[i]) = base + i · s

где:

baseначальный адрес массива (адрес A[0])
iиндекс элемента (начиная с 0)
sразмер одного элемента, байт

Именно поэтому индексы начинаются с 0: i показывает, на сколько шагов элемент удалён от начала.

(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 3, 2ᵏ < n(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 3, 2ᵏ < n

где:

nчисло добавленных элементов
1 + 2 + … + 2ᵏсумма копирований при всех расширениях (< 2n)

Амортизированная стоимость: общая работа n добавлений меньше 3n, значит, одно добавление в среднем стоит O(1) — несмотря на редкие «дорогие» расширения.

tail = (head + size) mod m, next(i) = (i + 1) mod m

где:

headиндекс первого элемента очереди
sizeчисло элементов в очереди
mёмкость массива
tailиндекс, куда запишется следующий элемент

Хеш-таблицы

К уроку

h(s) = (s₀ · pᵏ⁻¹ + s₁ · pᵏ⁻² + … + sₖ₋₁ · p⁰) mod m

где:

s₀ … sₖ₋₁числовые коды символов строки
pоснование (обычно небольшое простое число, например 31)
kдлина строки
mчисло корзин

Полиномиальный хеш зависит и от символов, и от их порядка: «ab» и «ba» получают разные хеши.

P(нет коллизий) ≈ e^(−k(k − 1) / (2m))

где:

kчисло вставленных ключей
mчисло корзин

m = 365, k = 23: k(k − 1)/2 = 253, 253/365 ≈ 0,693, e^(−0,693) ≈ 0,5. Чтобы начались коллизии, достаточно примерно √m ключей.

α = n / mα = n / m

где:

αкоэффициент заполнения (load factor)
nчисло ключей в таблице
mчисло корзин

При методе цепочек α — средняя длина цепочки, она может быть больше 1; при открытой адресации всегда α < 1.

E(цепочки) = 1 + α; E(линейное пробирование) ≈ ½ · (1 + 1 / (1 − α)²)E(цепочки) = 1 + α; E(линейное пробирование) ≈ ½ · (1 + 1 / (1 − α)²)

где:

Eожидаемое число проб при неудачном поиске (ключа нет)

В предположении равномерного хеширования. Формула для линейного пробирования — из анализа Кнута; при α → 1 число проб резко растёт.

Деревья и кучи

К уроку

n ≤ 2ʰ⁺¹ − 1 ⇒ h ≥ ⌈log₂(n + 1)⌉ − 1 ≈ log₂ n

где:

nчисло узлов
hвысота дерева (в рёбрах)

На глубине d помещается не более 2ᵈ узлов: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Значит, высота двоичного дерева из n узлов не может быть меньше примерно log₂ n, но может достигать n − 1.

left(i) = 2i + 1, right(i) = 2i + 2, parent(i) = ⌊(i − 1) / 2⌋left(i) = 2i + 1, right(i) = 2i + 2, parent(i) = ⌊(i − 1) / 2⌋

где:

iиндекс узла в массиве (с 0)

Дерево записывается в массив по уровням; так как оно полное, пропусков нет, а высота равна ⌊log₂ n⌋.

T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)T(build-heap) ≤ ∑ₕ (n / 2ʰ⁺¹) · h = (n/2) · ∑ₕ h / 2ʰ ≤ (n/2) · 2 = n = O(n)

где:

hвысота узла над листьями
n / 2ʰ⁺¹n / 2ʰ⁺¹число узлов высоты h (примерно)

heapify превращает массив в кучу снизу вверх: половина узлов — листья (0 работы), четверть погружается на 1 шаг и т. д. Поскольку ∑ h/2ʰ = 2, всего получается O(n), а не O(n log n). Пирамидальная сортировка затем делает n извлечений — O(n log n).

Графы и алгоритмы на графах

К уроку

∑ deg(v) = 2|E|, |E| ≤ |V| · (|V| − 1) / 2∑ deg(v) = 2|E|, |E| ≤ |V| · (|V| − 1) / 2

где:

deg(v)степень вершины v
|V|, |E|число вершин и рёбер

«Лемма о рукопожатиях»: каждое неориентированное ребро добавляет к сумме степеней 2 — по одному на каждом конце. Второе неравенство — максимальное число рёбер в простом неориентированном графе.

dist[v] ← min(dist[v], dist[u] + w(u, v)); T = O((V + E) · log V)

где:

dist[v]найденное на данный момент кратчайшее расстояние от источника до v
w(u, v)вес ребра u–v (≥ 0)
Tвремя работы с двоичной кучей

Рекурсия и динамическое программирование

К уроку

n! = n · (n − 1)!, 0! = 1

где:

n · (n − 1)!рекурсивный шаг
0! = 1базовый случай

T(n) = T(n − 1) + T(n − 2) + O(1) = Θ(φⁿ), φ = (1 + √5) / 2 ≈ 1,618T(n) = T(n − 1) + T(n − 2) + O(1) = Θ(φⁿ), φ = (1 + √5) / 2 ≈ 1,618

где:

T(n)время работы простой рекурсивной fib(n)
φзолотое сечение

С мемоизацией каждое fib(k) вычисляется один раз: n + 1 подзадача × O(1) работы = O(n). От экспоненты к линии!

dp[i][c] = max(dp[i − 1][c], dp[i − 1][c − wᵢ] + vᵢ), dp[0][c] = 0

где:

dp[i][c]наибольшая стоимость из первых i предметов при вместимости c
wᵢ, vᵢвес и стоимость i-го предмета (второй вариант только при wᵢ ≤ c)

Время и память O(n · W). Это псевдополиномиальная сложность: она экспоненциальна по числу битов W.

L[i][j] = L[i − 1][j − 1] + 1, если aᵢ = bⱼ; иначе L[i][j] = max(L[i − 1][j], L[i][j − 1])

где:

L[i][j]длина НОП первых i символов a и первых j символов b
L[0][j] = L[i][0]0 (с пустой строкой ничего общего нет)

Время O(m · n): для двух строк длины 1000 нужно всего 10⁶ ячеек, а перебор всех подпоследовательностей означал бы 2¹⁰⁰⁰ вариантов.

coins[x] = 1 + min { coins[x − c] : c ≤ x }, coins[0] = 0

где:

coins[x]наименьшее число монет для суммы x
cдоступный номинал монеты

Эффективные алгоритмы сортировки

К уроку

T(n) = 2T(n/2) + cn = Θ(n log n)T(n) = 2T(n/2) + cn = Θ(n log n)

где:

2T(n/2)2T(n/2)рекурсивная сортировка двух половин
cnслияние (не более n − 1 сравнений)

На каждом из log₂ n уровней слияния в сумме дают ≤ n сравнений → ≤ n log₂ n. Так в худшем, среднем и лучшем случаях. Дополнительная память O(n); алгоритм устойчив (равные элементы сохраняют порядок).

худший случай: T(n) = T(n − 1) + (n − 1) = n(n − 1)/2; в среднем: ≈ 2n ln n ≈ 1,39 n log₂ nхудший случай: T(n) = T(n − 1) + (n − 1) = n(n − 1)/2; в среднем: ≈ 2n ln n ≈ 1,39 n log₂ n

где:

T(n − 1)оставшаяся часть, когда опорный всегда минимум или максимум
n − 1число сравнений одного разбиения

При сбалансированных разбиениях быстрая сортировка ведёт себя как слияние: T(n) = 2T(n/2) + n → Θ(n log n); при худшем разбиении каждый раз — Θ(n²).

h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) · log₂(n/2) = Ω(n log n)h ≥ log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) · log₂(n/2) = Ω(n log n)

где:

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

Каждый из n/2 множителей n!, больших n/2, не меньше n/2, поэтому n! ≥ (n/2)^(n/2). Точнее, по формуле Стирлинга, log₂(n!) ≈ n log₂ n − 1,44n.

12Компьютерные системы и теорияУниверситет

Архитектура компьютера

К уроку

t = N · CPI / ft = N · CPI / f

где:

tпроцессорное время программы, с
Nчисло выполненных команд
CPIсреднее число тактов на команду
fтактовая частота, Гц

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

AMAT = t_hit + m · t_miss

где:

AMATсреднее время доступа к памяти
t_hitвремя доступа при попадании в кэш
mдоля промахов
t_missштраф за промах (обращение к следующему уровню)

−x = (NOT x) + 1; n bit: −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1

где:

NOT xинверсия всех битов x
nчисло битов (8 бит: −128 … 127)

x = (−1)ˢ · 1,m₂ · 2^(e − 127)

где:

sбит знака (1 бит)
eсмещённый порядок (8 бит, смещение 127)
mдробная часть мантиссы (23 бита; ведущая 1 не хранится)

32-битный формат (single). 64-битный double: 1 + 11 + 52 бита, смещение 1023, точность около 15–16 десятичных цифр. float в Python — это double.

Операционные системы

К уроку

W = (1 / n) · ∑ (Cᵢ − Aᵢ − Bᵢ)W = (1 / n) · ∑ (Cᵢ − Aᵢ − Bᵢ)

где:

Wсреднее время ожидания
Cᵢмомент завершения процесса i
Aᵢмомент поступления
Bᵢдлительность работы на процессоре (burst)

p = ⌊VA / P⌋, d = VA mod P, PA = frame(p) · P + dp = ⌊VA / P⌋, d = VA mod P, PA = frame(p) · P + d

где:

VA, PAвиртуальный и физический адрес
Pразмер страницы, байт
p, dномер страницы и смещение внутри неё

При P = 2ᵏ деление — это просто разделение битов: для страниц 4 КБ = 2¹² младшие 12 бит — смещение, остальные — номер страницы.

Компьютерные сети: углублённо

К уроку

N_host = 2^(32 − n) − 2, network = IP AND mask, broadcast = network OR (NOT mask)

где:

nдлина префикса (/n)
N_hostчисло адресов, доступных устройствам
maskn единиц и 32 − n нулей (например, /26 → 255.255.255.192)

d = L / R + D / s; throughput_TCP ≤ W / RTTd = L / R + D / s; throughput_TCP ≤ W / RTT

где:

L / RL / Rзадержка передачи: размер пакета L (бит) / скорость канала R (бит/с)
D / sD / sзадержка распространения: расстояние D / скорость сигнала s (≈ 2 · 10⁸ м/с в оптоволокне)
W, RTTразмер окна TCP и время кругового обхода

Теория баз данных

К уроку

π[first_name](σ[city = 'Bakı'](students)) ≡ SELECT first_name FROM students WHERE city = 'Bakı'

где:

σвыборка (selection): строки, удовлетворяющие условию, — WHERE
πпроекция: нужные столбцы — список SELECT
⋈соединение (join): объединение двух отношений по общему атрибуту — JOIN

h = ⌈log N / log f⌉h = ⌈log N / log f⌉

где:

hвысота индекса B-дерева (число читаемых страниц при поиске)
Nчисло строк в таблице
fветвление: сколько ключей помещается на странице

Теория вычислений

К уроку

M = (Q, Σ, δ, q₀, F), δ: Q × Σ → Q

где:

Qконечное множество состояний
Σвходной алфавит (например, {0, 1})
δфункция переходов
q₀, Fначальное состояние и множество допускающих состояний

L регулярен ⇒ ∃ p: ∀ w ∈ L, |w| ≥ p: w = xyz, |xy| ≤ p, |y| ≥ 1, xyⁱz ∈ L ∀ i ≥ 0

где:

pдлина накачки (число состояний автомата)
yнепустая часть, которую можно повторять или удалять сколько угодно

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

Программная инженерия

К уроку

C = n(n − 1) / 2C = n(n − 1) / 2

где:

Cчисло парных каналов общения в команде
nчисло участников команды

5 человек → 10 каналов, 10 человек → 45 каналов. Этим объясняется закон Брукса: добавление людей в опаздывающий проект часто задерживает его ещё сильнее. Поэтому Scrum-команды держат небольшими (обычно до 10 человек).

M = E − N + 2P (= число решений + 1)

где:

Mцикломатическая сложность Маккейба: число независимых путей
E, Nрёбра и узлы графа потока управления
Pчисло связных компонент (1 для одной функции)

M — хорошая оценка минимального числа тестов, нужных для покрытия всех ветвей. Функции с M > 10 обычно разбивают на меньшие.

Криптография и информационная безопасность

К уроку

C = E(K, M), M = D(K, C)

где:

M, Cоткрытый текст и шифртекст
Kодин и тот же секретный ключ у обеих сторон
E, Dалгоритмы шифрования и расшифрования (например, AES)

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

A = gᵃ mod p, B = gᵇ mod p, s = Bᵃ mod p = Aᵇ mod p = gᵃᵇ mod p

где:

p, gобщеизвестные простое число и основание
a, bсекретные числа сторон
sобщий секрет — никогда не передаётся по сети

Обмен ключами Диффи — Хеллмана: подслушивающий видит p, g, A и B, но чтобы получить s, ему нужно решить задачу дискретного логарифма.

n = p · q, φ(n) = (p − 1)(q − 1), e · d ≡ 1 (mod φ(n)), c = mᵉ mod n, m = cᵈ mod n

где:

p, qдва больших секретных простых числа (на практике ≈ 1024 бита каждое)
(n, e)открытый ключ
dзакрытый ключ: обратный к e по модулю φ(n)
m, cсообщение (0 ≤ m < n) и шифртекст

RSA (Ривест, Шамир, Адлеман, 1977). Чтобы найти d, нужно φ(n), а для него — множители n: безопасность держится на трудности разложения на множители.

H = L · log₂ N

где:

Hэнтропия случайного пароля, бит
Lдлина пароля
Nразмер алфавита (26 строчных букв, 94 печатных символа)

Каждый дополнительный бит вдвое удлиняет перебор. Формула верна только для действительно случайных паролей: пароли вроде «Baku2026!» быстро находятся атаками по словарю.

1Компьютер: информация, аппаратное и программное обеспечениеНачальный

Информация, её виды и информационные процессы

Устройство компьютера: процессор, память и материнская плата

Устройства ввода и вывода

Файловые системы и место на диске

2Текстовые и табличные процессорыНачальный

Текстовые процессоры: редактирование, форматирование и клавиши

Электронная таблица: адреса, диапазоны и формулы

Функции в электронной таблице

Диаграммы в электронной таблице и их элементы

3Кодирование и измерение информацииСредний

Измерение информации: бит, байт и единицы измерения

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

Компьютерная графика: кодирование растровых и векторных изображений

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

4Системы счисления и логикаСредний

Системы счисления: позиционные системы и двоичная система

Восьмеричная и шестнадцатеричная системы счисления

Арифметические действия в различных системах счисления

Системы счисления: задачи с неизвестным основанием

5МоделированиеСредний

Модели и моделирование

Табличные информационные модели: решение логических задач с помощью таблиц

Древовидные информационные модели

Графы как информационные модели: матрица смежности и число путей

6АлгоритмыСредний

Алгоритм, его свойства и способы описания

Разветвляющиеся алгоритмы

Циклические алгоритмы и таблица трассировки

Построение блок-схем: письменные задания

Алгоритмы сортировки

7Программирование на Python (школьный курс)Средний

Языки программирования и Python: переменные, ввод и вывод

Условный оператор: if, elif, else и составные условия

Операторы цикла: for, while, шаг цикла, break, continue и вложенные циклы

Операции над числами: цифры, делители и простые числа

Анализ программы: от результата к входным данным

Строки и операции над ними

Списки и операции над ними

Функция: def, параметры и return

Написание программ: письменные задания

8Базы данныхПродвинутый

Базы данных: модели, СУБД и связанные таблицы

Запросы, поиск и сортировка в базе данных

9Сети, интернет и информационная безопасностьПродвинутый

Поиск в интернете: поисковые системы и запросы

Кибербезопасность: пароли, фишинг и конфиденциальность

Защита информации и криптография

10Веб-программированиеПродвинутый

Веб-программирование: создание сайта, теги HTML и списки

Таблицы, цветовая схема, изображения и ссылки в HTML

11Алгоритмы и структуры данныхУниверситет

Сложность алгоритмов и О-нотация

Массивы, связные списки, стеки и очереди

Хеш-таблицы

Деревья и кучи

Графы и алгоритмы на графах

Рекурсия и динамическое программирование

Эффективные алгоритмы сортировки

12Компьютерные системы и теорияУниверситет

Архитектура компьютера

Операционные системы

Компьютерные сети: углублённо

Теория баз данных

Теория вычислений

Программная инженерия

Криптография и информационная безопасность