Словарь

# A B C D E F H I J L M N P S T U А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

$\Theta$

f(n) = Θ(g(n)): f растёт так же, как g, с точностью до постоянных множителей: и O(g), и Ω(g). Глава 13 · Сколько стоит программа

$O$

f(n) = O(g(n)): начиная с некоторого n, f(n) не больше c·g(n) для какого-то постоянного c. Оценка роста сверху. Глава 13 · Сколько стоит программа

, , , которые говорят, где абзац, заголовок, ссылка. Браузер превращает его в дерево DOM.">HTML

Глава 43 · Анатомия этой страницы

, у переменной после двоеточия. Сам Python их не проверяет, их читают mypy и редакторы.">аннотациями типов

Глава 53 · Суд над null

0. Оценка роста снизу.">$\Omega$

Глава 13 · Сколько стоит программа

::= вариант | вариант. Появилась в описании ALGOL 60 (1960); ею и её расширениями описывают синтаксис большинства языков программирования.">формой Бэкуса — Наура

Глава 50 · Лингвист в экспедиции

= 7.">предикатами

Глава 10 · Функции как значения

>> в Python, консоль браузера и Jupyter.">REPL

Глава 51 · Матрёшка

ACID

Четыре свойства транзакций: атомарность (всё или ничего), согласованность (правила базы соблюдены до и после), изоляция (одновременные транзакции не видят половин друг друга), долговечность (подтверждённое переживёт сбой). Глава 46 · Библиотека и банк

AES

Advanced Encryption Standard — блочный шифр, стандарт США с 2001 года (шифр Rijndael Даймена и Рэймена). Шифрует блоки по 128 бит ключом в 128, 192 или 256 бит за 10, 12 или 14 раундов. Глава 59 · Шифровальный отдел

AIMD

Additive increase, multiplicative decrease — правило управления перегрузкой: без потерь окно растёт на постоянную величину за круг туда и обратно, при потере уменьшается в постоянное число раз (в TCP — вдвое). Делит канал между потоками поровну. Глава 42 · Изобрести протокол

API

Application Programming Interface — договор, по которому одна программа пользуется другой. В вебе — набор адресов и правил: какой запрос послать и какой ответ, обычно в JSON, придёт. Глава 43 · Анатомия этой страницы

B-дерево

Сбалансированное дерево поиска с широкими узлами: в каждом узле до сотен ключей по порядку и на одного ребёнка больше. Все листья на одной глубине, высота растёт как логарифм по основанию ширины узла. Так хранят индексы баз данных и файловых систем. Глава 46 · Библиотека и банк

BM25

Формула ранжирования (Робертсон, Спарк Джонс и др., система Okapi, 1990-е): как TF-IDF, но вклад частоты слова насыщается (параметр k₁ ≈ 1,2) и учитывается длина документа относительно средней (b ≈ 0,75). Глава 48 · Поисковик по нашим учебникам

BQP

Bounded-error Quantum Polynomial time: задачи, которые квантовый компьютер решает за полиномиальное время с вероятностью ошибки не больше 1/3. Содержит P, лежит внутри PSPACE; разложение на множители лежит в BQP. Как BQP соотносится с NP, неизвестно. Глава 64 · Лаборатория кубитов

co-NP

Задачи, у которых ответ «нет» подтверждается коротким быстро проверяемым сертификатом: дополнения задач из NP. Невыполнимость формулы, отсутствие гамильтонова цикла, тождественная истинность формулы лежат в co-NP. Глава 57 · Письмо Гёделя

CSS

Cascading Style Sheets — язык стилей веба: правила вида «селектор { свойство: значение }» задают цвета, шрифты, отступы и раскладку элементов дерева DOM. Глава 43 · Анатомия этой страницы

D-триггером

Ячейка памяти на один бит, которая принимает значение входа D только в момент фронта тактового сигнала, а всё остальное время хранит его. Собирается из двух D-защёлок, открываемых по очереди. Глава 31 · Память и такт

DEFLATE

Формат сжатия без потерь: сначала LZ77 заменяет повторы ссылками (окно 32 КиБ), потом код Хаффмана кодирует знаки, длины и расстояния. Используется в ZIP, gzip, PNG, zlib и HTTP. Глава 47 · Конкурс упаковки

DNS

Domain Name System — распределённая иерархическая система, которая превращает имена вроде legost.in в IP-адреса. Каждый уровень дерева имён обслуживают свои серверы, и никто не хранит всё. Глава 43 · Анатомия этой страницы

DOM

Document Object Model — дерево, которое браузер строит из HTML: узлы — элементы и куски текста. Скрипты страницы читают и меняют его, а браузер перерисовывает то, что изменилось. Глава 43 · Анатомия этой страницы

EDF

Earliest deadline first: правило планирования, при котором ядро получает задача с самым ранним сроком. На одном ядре успевает всё, что вообще можно успеть, но при перегрузке опаздывают все подряд. Глава 37 · Центр управления полётом

f-строка

Строка с буквой f перед кавычкой: f"…{выражение}…". Python вычисляет выражения в фигурных скобках и подставляет их значения в текст. Глава 2 · Имена и значения

HTTP

HyperText Transfer Protocol — протокол веба: клиент посылает запрос (метод, путь, заголовки, иногда тело), сервер отвечает кодом состояния, заголовками и телом. В версии 1.1 это обычный текст. Глава 43 · Анатомия этой страницы

HTTPS

HTTP внутри зашифрованного соединения TLS: посторонний на пути видит, с каким сервером вы говорите, но не видит ни адресов страниц, ни их содержимого, и не может незаметно их подменить. Глава 43 · Анатомия этой страницы

IP-адрес

Адрес машины в интернете. В версии IPv4 — 32 бита, записанные четырьмя числами от 0 до 255 через точку: 192.168.1.23. Первые биты обозначают сеть, остальные — машину в ней. Глава 41 · Один день из жизни пакета

JIT-компиляция

Компиляция во время работы программы: исполнитель замечает часто выполняемые куски и переводит их в машинный код, подстроенный под встреченные типы. Глава 33 · Рентген Python

JSON

JavaScript Object Notation — текстовый формат данных из словарей (в фигурных скобках), списков, строк, чисел, true/false и null; на нём обмениваются данными сайты и программы. Глава 8 · Словарь и телеграф

LRU

Least Recently Used, «дольше всех не использованный»: правило вытеснения, при котором из полного кэша выбрасывают элемент, к которому дольше всех не обращались. Глава 34 · Близко и далеко

LZ77

Алгоритм сжатия Лемпеля и Зива (1977): повтор заменяется ссылкой «вернись на столько-то знаков назад и скопируй столько-то». Ссылки ищут в скользящем окне из последних нескольких тысяч знаков. Глава 47 · Конкурс упаковки

LZW

Алгоритм сжатия Лемпеля — Зива — Уэлча (1984): упаковщик и распаковщик одинаково строят словарь фраз по ходу работы, и в выход идут номера фраз. Использовался в compress и GIF. Глава 47 · Конкурс упаковки

MAC-адрес

Адрес сетевой карты на канальном уровне (Ethernet, Wi-Fi): 48 бит, обычно записываются как шесть пар шестнадцатеричных цифр. Имеет смысл только в пределах одной локальной сети. Глава 41 · Один день из жизни пакета

MMU

Memory management unit, блок управления памятью: часть процессора, которая при каждом обращении к памяти переводит виртуальный адрес в физический и проверяет права доступа. Глава 38 · Гостиница с номерами

MTU

Maximum Transmission Unit — наибольший размер пакета, который канал может передать за один раз. У Ethernet это 1500 байт; пакет больше приходится резать. Глава 41 · Один день из жизни пакета

NAND

Вентиль «и-не»: выдаёт 0, только когда на обоих входах 1; в остальных случаях выдаёт 1. Из одних таких вентилей можно собрать любую логическую схему. Глава 29 · Логика из выключателей

NAT

Network Address Translation — подмена адресов: роутер на границе домашней сети заменяет в исходящих пакетах частный адрес и порт на свой внешний адрес и свободный порт, запоминает пару и по ней возвращает ответы. Глава 42 · Изобрести протокол

NP

Задачи распознавания, у которых ответ «да» подтверждается сертификатом полиномиальной длины, а проверка сертификата идёт за полиномиальное время. Рассадка гостей, судоку, выполнимость формулы лежат в NP. Глава 57 · Письмо Гёделя

NP-полной

Задача из NP, к которой за полиномиальное время сводится любая задача из NP. Быстрый алгоритм для одной NP-полной задачи дал бы быстрые алгоритмы для всех задач NP. Примеры: SAT, 3-SAT, клика, гамильтонов цикл, судоку n²×n². Глава 57 · Письмо Гёделя

NP-трудной

Задача, к которой за полиномиальное время сводится любая задача из NP. Она не легче NP-полных, но сама не обязана лежать в NP: это может быть задача оптимизации (кратчайший тур коммивояжёра) или даже неразрешимая задача. Глава 57 · Письмо Гёделя

NULL

Отметка в клетке таблицы: значения нет или оно неизвестно. NULL не равен ничему, даже другому NULL; сравнение с ним даёт «неизвестно». Проверяют его через IS NULL. Глава 45 · Архивариус

P

Задачи распознавания, которые решаются алгоритмом за полиномиальное время. Кратчайший путь, сортировка, паросочетание, проверка простоты числа лежат в P. Глава 57 · Письмо Гёделя

PageRank

Оценка важности страницы по ссылкам на неё (Брин и Пейдж, 1998): доля времени, которую случайный читатель проводит на странице, если с вероятностью d идёт по случайной ссылке, а иначе открывает случайную страницу. Считается степенным методом. Глава 48 · Поисковик по нашим учебникам

PID

Process ID — номер процесса, под которым его знает ядро. В Unix у каждого процесса, кроме первого, есть родитель со своим PID. Глава 36 · Экскурсия по живой системе

PSPACE

Задачи, которые решаются с полиномиальной памятью, сколько бы времени ни ушло. Содержит P, NP и co-NP. Типичные PSPACE-полные задачи — игры двух игроков на доске произвольного размера и формулы с кванторами «существует» и «для любого» вперемежку. Глава 57 · Письмо Гёделя

S-выражением

Запись данных и программ в Лиспе: либо атом (число, имя), либо список других S-выражений в скобках. Программа на Лиспе состоит из S-выражений, поэтому её дерево видно прямо в тексте. Глава 51 · Матрёшка

segmentation fault

Segmentation fault: аварийное завершение программы, которая обратилась к памяти, которую ей не выдавали, или так, как нельзя (запись в страницу только для чтения). MMU замечает нарушение, ядро посылает сигнал SIGSEGV. Глава 38 · Гостиница с номерами

SQL-инъекция

SQL-инъекция: атака, при которой данные от пользователя, вклеенные в текст SQL-запроса, разбираются базой как часть команды. Позволяет обойти проверки, прочитать или стереть чужие данные. Защита — параметры запроса (?), а не склейка строк. Глава 61 · Учебный полигон

TCP

Transmission Control Protocol — транспортный протокол интернета, который поверх ненадёжного IP даёт надёжный поток байтов: номера, подтверждения, повторы, окно, управление потоком и перегрузкой. На нём работают веб, почта, ssh. Глава 42 · Изобрести протокол

TF-IDF

Вес слова в документе: частота слова в документе (tf), умноженная на log(N / df), где df — в скольких из N документов слово встречается. Частые в документе и редкие в коллекции слова весят больше всего. Глава 48 · Поисковик по нашим учебникам

TLB

Translation lookaside buffer: маленький быстрый кэш внутри процессора, где хранятся недавние переводы «страница → кадр». Если перевод там есть, таблицу страниц читать не нужно. Глава 38 · Гостиница с номерами

TTL

Time To Live, «время жизни» — поле IP-заголовка: каждый маршрутизатор уменьшает его на единицу и выбрасывает пакет, когда оно доходит до нуля. Защищает сеть от пакетов, которые ходят по кругу. Глава 41 · Один день из жизни пакета

UDP

User Datagram Protocol — транспортный протокол без гарантий: отдельные датаграммы с номерами портов и контрольной суммой, без соединения, подтверждений и повторов. На нём работают DNS, видеозвонки, игры. Глава 42 · Изобрести протокол

URL

Uniform Resource Locator — адрес документа в сети: схема (протокол), имя сервера, необязательный порт, путь на сервере, необязательные параметры после ? и фрагмент после #. Глава 43 · Анатомия этой страницы

UTF-8

Кодировка Юникода, в которой символ занимает от 1 до 4 байтов: ASCII — один байт, кириллица — два, большинство иероглифов — три, эмодзи — четыре. Первые биты байта говорят, сколько байтов в символе. Ей записано почти всё в интернете. Глава 28 · Всё есть биты

«пометить и вымести»

Способ сборки мусора в два прохода: пометить все объекты, достижимые по ссылкам из корней (переменных и стека программы), а потом пройти всю память и освободить непомеченные. Собирает и петли, которые счётчик ссылок пропускает. Глава 51 · Матрёшка

«разделяй и властвуй»

Метод построения алгоритмов: задачу делят на подзадачи того же вида, решают их рекурсивно и собирают ответ из их ответов. Глава 21 · Разделяй и властвуй

абстрактным синтаксическим деревом

Абстрактное синтаксическое дерево: строение программы без подробностей записи — без скобок, разделителей и промежуточных правил грамматики. Узлы — операции, вызовы, присваивания, циклы; так программу видят интерпретатор и компилятор. Глава 50 · Лингвист в экспедиции

абстрактным типом данных

Описание структуры данных через её операции и их смысл, без указания устройства. Стек — это push, pop и peek; на массиве он сделан или на связном списке — дело реализации. Глава 15 · Стек, очередь и калькулятор

АВЛ-деревом

Двоичное дерево поиска, в котором у каждого узла высоты левого и правого поддеревьев различаются не больше чем на единицу. После вставки и удаления оно восстанавливает это правило поворотами; высота всегда O(log n). Придумано Адельсон-Вельским и Ландисом в 1962 году. Глава 17 · Сад деревьев поиска

автоматом с магазинной памятью

Конечный автомат со стеком неограниченной глубины: на каждом шаге может положить символ на стек или снять верхний. Его языки — контекстно-свободные: сбалансированные скобки, синтаксис языков программирования. Глава 54 · Автоматы и регулярки

агрегатные функции

Функция, которая сворачивает много строк в одно значение: count, sum, avg, min, max. С GROUP BY она считается отдельно для каждой группы строк. Глава 45 · Архивариус

адрес возврата

Адрес команды, с которой нужно продолжить после возврата из функции. Команда call кладёт его на стек, команда ret снимает и прыгает по нему. Глава 33 · Рентген Python

адресация по содержимому

Способ хранения, при котором адрес объекта — хеш его содержимого. Одинаковые данные получают один адрес и хранятся один раз, а изменённые получают новый адрес; испорченный объект выдаёт себя несовпадением хеша. Глава 40 · Спасательная операция

адресное пространство

Все виртуальные адреса, которые доступны процессу. У каждого процесса оно своё: один и тот же адрес в двух процессах означает разные ячейки. Глава 38 · Гостиница с номерами

адресом

Номер байта в памяти компьютера. Зная адрес, процессор читает или пишет нужное место памяти за одно обращение, где бы оно ни было. Глава 14 · Как список лежит в памяти

алгебраическими

Тип данных, собранный из произведений (запись: и то, и другое) и сумм (вариант: или то, или другое). Maybe в Haskell, enum в Rust, объединение dataclass-классов через | в Python. Глава 53 · Суд над null

алгоритм Кнута — Морриса — Пратта

Алгоритм поиска подстроки Кнута, Морриса и Пратта (1977): идёт по тексту без возвратов и после несовпадения сдвигает образец по префикс-функции. Время O(n + m). Глава 27 · Иголка в стоге

Алгоритм Лас-Вегаса

Рандомизированный алгоритм, который всегда отвечает правильно, а случайно только время его работы. Глава 26 · Подбросим монетку

Алгоритм Монте-Карло

Рандомизированный алгоритм, время работы которого ограничено, а ответ может быть неверным с малой вероятностью; повторением её делают сколь угодно малой. Глава 26 · Подбросим монетку

алгоритмом сортировочной станции

Алгоритм Дейкстры (1961), который переводит инфиксное выражение в обратную польскую запись, держа знаки операций и скобки на стеке. Глава 15 · Стек, очередь и калькулятор

альфа-бета отсечение

Альфа-бета отсечение: ускорение минимакса. Запоминаем α — лучшее, что уже гарантировано игроку на максимуме, и β — лучшее для соперника. Как только ветка не может улучшить результат (значение вышло за α…β), её перестают просматривать. Ответ тот же, что у минимакса. Глава 62 · Турнир ботов

амортизированной

Стоимость операции в среднем по длинной последовательности операций: редкие дорогие шаги раскладываются на множество дешёвых. Append у списка Python стоит O(1) амортизированно. Глава 14 · Как список лежит в памяти

амплитуды

Число (вообще говоря, комплексное), которое квантовое состояние приписывает каждому возможному исходу измерения. Вероятность исхода — квадрат модуля его амплитуды. Глава 64 · Лаборатория кубитов

аномалией Белади

Свойство некоторых правил вытеснения, например FIFO: на некоторых последовательностях обращений с бо́льшим числом кадров получается больше страничных прерываний. LRU и OPT ей не подвержены. Глава 38 · Гостиница с номерами

арбитраж

Сделка, которая приносит прибыль без риска за счёт разницы цен, например обмен валют по кругу, после которого денег становится больше. Глава 24 · Навигатор

аргументом

Значение, которое передают функции при вызове: в draw_square(40) это 40. Глава 5 · Свои слова

аргументом обмена

Способ доказать жадный алгоритм: берут любое оптимальное решение и показывают, что его можно переделать, заменив часть на жадный выбор, и не ухудшить. Глава 23 · Жадность и электричество

арифметико-логическим устройством

Арифметико-логическое устройство: часть процессора, которая по коду операции складывает, вычитает, сравнивает, сдвигает или выполняет побитовые операции над числами из регистров и выставляет флаги. Глава 30 · Машина считает

архитектурой с хранимой программой

Устройство компьютера, при котором программа хранится в той же памяти, что и данные, и состоит из таких же чисел. Её можно загрузить, прочитать и изменить как данные. Глава 32 · Ты — процессор

ассемблер

Программа, которая переводит текст на языке ассемблера (мнемоники команд и метки) в машинный код. Сам такой язык тоже называют ассемблером. Глава 32 · Ты — процессор

ассоциативностью

Правило, как группируются одинаковые операции без скобок: левая ассоциативность — слева направо, 8 − 3 − 2 = (8 − 3) − 2; правая — справа налево, 2 ** 3 ** 2 = 2 ** (3 ** 2). В грамматике задаётся тем, в какую сторону растёт рекурсия. Глава 50 · Лингвист в экспедиции

Атака на цепочку поставок

Атака на цепочку поставок (supply-chain attack): внедрение вредоносного кода в зависимость системы — библиотеку, пакет, инструмент сборки, — откуда он попадает во всё, что этим собрано или с этим слинковано. Глава 61 · Учебный полигон

атака посредника

Атака, при которой противник встаёт между двумя сторонами связи, выдаёт себя каждой за другую и пересылает сообщения, читая или меняя их. Против неё нужна проверка подлинности — подпись. Глава 60 · Секрет на виду у всех

атакой по побочному каналу

Способ узнать секрет не из того, что программа выдаёт, а по побочным признакам её работы: по времени, расходу энергии, состоянию кэша, звуку. Глава 35 · Конвейер и предсказатель

атомарно

Переименование файла, которое происходит целиком или не происходит вовсе: любой, кто откроет файл по этому имени, увидит либо старую версию, либо новую. На нём строят безопасное сохранение: записать во временный файл, fsync, переименовать. Глава 40 · Спасательная операция

атомарностью

Свойство операции выполняться целиком, как один неделимый шаг: другие потоки видят либо состояние до неё, либо состояние после, но никогда не середину. Глава 39 · Гонки

атрибутами

Имя, привязанное к объекту: bunny.energy, point.x. Читается и меняется через точку. Глава 12 · Остров кроликов и лис

базовый случай

Самый простой случай рекурсивной задачи, который решается сразу, без новых рекурсивных вызовов; на нём рекурсия останавливается. Глава 9 · Задача внутри задачи

базой данных

Собрание данных, которое хранит и выдаёт по запросам отдельная программа — система управления базами данных (СУБД): SQLite, PostgreSQL, Oracle. В реляционной базе данные лежат в таблицах. Глава 45 · Архивариус

байт

Восемь битов. Наименьшая порция памяти, у которой есть свой адрес; хранит число от 0 до 255. Глава 28 · Всё есть биты

байт-кодом

Программа для виртуальной машины: последовательность простых команд, в которую интерпретатор переводит исходный текст перед выполнением. В CPython каждая команда — два байта: код операции и аргумент. Глава 33 · Рентген Python

бесконечным циклом

Цикл, условие продолжения которого никогда не становится ложным, поэтому сам он не заканчивается. Глава 4 · Снова и снова

библиотекой времени выполнения

Подпрограммы, которые компилятор добавляет к каждой программе, чтобы выполнить то, чего нет в командах процессора: умножение на машине без умножения, вывод на экран, выделение памяти, сборку мусора. Глава 52 · Замкнуть круг

бит чётности

Дополнительный бит, который делает число единиц в слове чётным (или нечётным). Если при чтении чётность не та, значит, какой-то бит испорчен. Глава 31 · Память и такт

биты

Двоичная цифра: 0 или 1. Наименьшая порция информации; всё, что хранит и передаёт компьютер, записано битами. Глава 28 · Всё есть биты

блок

Несколько строк, сдвинутых вправо на одинаковый отступ под строкой с двоеточием (if, else, while, def…): они выполняются вместе, как одно целое. Глава 3 · Развилки

блокировкой

Объект синхронизации (мьютекс, от mutual exclusion — взаимное исключение): взять его может только один поток, остальные ждут, пока хозяин не отпустит. В Python — threading.Lock. Глава 39 · Гонки

блокирующей

Студент и вуз (или двое из разных долей), которые не вместе, но оба предпочли бы друг друга своим нынешним партнёрам. Глава 25 · Потоки и пары

блоков

Наименьшая порция, которой диск и файловая система читают и пишут данные; обычно 4096 байт. Файл занимает целое число блоков. Глава 40 · Спасательная операция

блочный шифр

Шифр, который превращает блок фиксированной длины (у AES — 128 бит) в блок той же длины под управлением ключа. Длинные сообщения шифруют блок за блоком по особым правилам (режимам). Глава 59 · Шифровальный отдел

бором

Дерево для набора строк: каждая стрелка подписана буквой, путь от корня до узла читается как начало строки, а строки с общим началом делят общий путь. Ищет строку или все строки с данным началом за время, пропорциональное длине запроса. Глава 27 · Иголка в стоге

булевой алгеброй

Алгебра над значениями 0 и 1 с операциями «и» (умножение), «или» (сложение) и «не» (черта сверху); на ней основано проектирование цифровых схем. Глава 29 · Логика из выключателей

вводом-выводом через память

Способ связи процессора с устройствами, при котором устройство отвечает на определённые адреса памяти: запись по такому адресу передаёт байт устройству, чтение — берёт байт у него. Глава 32 · Ты — процессор

векторизацией

Переписывание вычисления так, чтобы оно делалось над целыми массивами сразу (в numpy — операциями над массивами вместо цикла Python); тогда работу выполняет цикл на C, часто с векторными командами процессора. Глава 35 · Конвейер и предсказатель

Векторная команда

Single Instruction, Multiple Data: команда процессора, которая выполняет одну и ту же операцию сразу над несколькими числами, лежащими рядом в широком регистре (128, 256 или 512 бит). Глава 35 · Конвейер и предсказатель

векторные часы

Логические часы, в которых каждый узел хранит вектор счётчиков — по одному на каждый узел системы. a → b тогда и только тогда, когда вектор a не больше вектора b покомпонентно и не равен ему. Глава 44 · Парламент острова Паксос

вершинами

Объект графа: человек, станция, клетка лабиринта. Вершины соединяются рёбрами. Глава 19 · Шесть рукопожатий

весами

Настраиваемые числа модели машинного обучения; их подбирает обучение. У прямой два веса, у сетей — от тысяч до сотен миллиардов. Глава 63 · Машина учится

взаимной блокировкой

Взаимная блокировка: несколько потоков ждут друг друга по кругу — каждый держит то, что нужно следующему, и ждёт того, что держит предыдущий, — и ни один не может продолжить. Глава 39 · Гонки

взвешенным

Граф, у каждого ребра которого есть число — вес: длина, время, цена. Длина пути во взвешенном графе — сумма весов его рёбер. Глава 24 · Навигатор

видеокарту

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

византийским

Самый тяжёлый вид отказа: узел ведёт себя произвольно — отвечает неверно, разным узлам по-разному, словно намеренно. Чтобы пережить f таких узлов при обычных сообщениях, нужно не меньше 3f + 1 узлов. Глава 44 · Парламент острова Паксос

виртуальная машина

Программа, которая изображает процессор: у неё свой набор команд, свой счётчик команд и своя память, а исполняет её настоящий процессор. Внутри CPython работает стековая виртуальная машина. Глава 33 · Рентген Python

виртуальной памятью

Способ, которым процессор и операционная система дают каждому процессу собственное адресное пространство: виртуальные адреса переводятся в физические по таблице страниц, а страницы, которым не хватило места, лежат на диске. Глава 38 · Гостиница с номерами

виртуальные адреса

Адрес, которым пользуется программа. Процессор по таблице страниц переводит его в физический адрес — номер настоящей ячейки в микросхемах памяти; у разных процессов один и тот же виртуальный адрес обычно ведёт в разные ячейки. Глава 38 · Гостиница с номерами

включение

Запись [выражение for x in данные if условие] — новый список (словарь, множество) из элементов данных, прошедших условие и преобразованных выражением. Глава 10 · Функции как значения

вложенный цикл

Цикл, который стоит в теле другого цикла и на каждой итерации внешнего проходит целиком. Глава 4 · Снова и снова

внешним ключом

Столбец таблицы, значения которого — первичные ключи другой таблицы. Так в реляционной базе записывают связь: аэропорт ссылается на свою страну её кодом. Глава 45 · Архивариус

возвращаемым значением

Значение, которое функция отдаёт месту вызова командой return; вызов в выражении заменяется этим значением. Глава 5 · Свои слова

временной диаграммой

Рисунок сигналов цифровой схемы во времени: каждый провод — дорожка, высокий уровень — 1, низкий — 0, время у всех дорожек общее. Глава 31 · Память и такт

время оборота

Время от прихода задачи до её завершения: f − a. Глава 37 · Центр управления полётом

время ожидания

Сколько задача простояла в очереди готовых: время оборота минус время её собственной работы, f − a − b. Глава 37 · Центр управления полётом

время отклика

Время от прихода задачи до момента, когда она впервые получила процессор: s − a. Главная мерка для интерактивных программ. Глава 37 · Центр управления полётом

выборка резервуаром

Способ выбрать k случайных элементов из потока неизвестной длины за один проход, храня только k элементов: i-й элемент с вероятностью k/i заменяет случайный из хранимых. Глава 26 · Подбросим монетку

выборы председателя

Процедура, которой узлы распределённой системы выбирают одного координатора. В Raft кандидат получает голоса большинства; каждый узел голосует в каждом сроке не больше одного раза. Глава 44 · Парламент острова Паксос

выводом

Цепочка замен по правилам грамматики от стартового нетерминала до фразы из одних терминалов. Фраза принадлежит языку, если у неё есть вывод. Глава 50 · Лингвист в экспедиции

выводом типов

Нахождение типов выражений по тому, как они используются, без аннотаций. Алгоритм Хиндли — Милнера находит самый общий тип, решая систему уравнений на типы унификацией. Глава 53 · Суд над null

высотой дерева

Число узлов на самом длинном пути от корня дерева вниз до листа: у пустого дерева высота 0, у одного узла — 1. Поиск в дереве поиска делает не больше сравнений, чем высота. Глава 17 · Сад деревьев поиска

вытеснением

Отнятие процессора у работающей программы без её согласия — по прерыванию таймера или потому, что появилась задача важнее. Глава 37 · Центр управления полётом

галактическими

Алгоритм с лучшей асимптотической оценкой, чем у известных, но с такими постоянными множителями, что выигрыш проявился бы только на входах, которых на Земле не бывает. Ценен тем, что двигает границу известного. Глава 65 · Белые пятна

генераторы

Функция с yield. Её вызов лишь создаёт объект, который выдаёт значения по одному, каждый раз продолжая с того места, где остановился. Глава 10 · Функции как значения

генерация кода

Этап компилятора, который переводит промежуточное представление в команды конкретного процессора: выбирает команды, раскладывает значения по регистрам и памяти. Глава 52 · Замкнуть круг

глобальный замок интерпретатора

Global Interpreter Lock — замок, который в обычной сборке CPython разрешает выполнять байт-код Python только одному потоку процесса в каждый момент. Поток отпускает его, когда ждёт ввода-вывода, и по просьбе интерпретатора каждые несколько миллисекунд. Глава 39 · Гонки

голоданием

Ситуация, когда элемент с низким приоритетом бесконечно долго ждёт обслуживания, потому что всё время находятся более приоритетные. Глава 18 · Кто следующий

гонкой

Ошибка, при которой результат программы зависит от того, в каком порядке и как вперемешку несколько потоков выполнили свои шаги над общими данными. Глава 39 · Гонки

градиентный спуск

Способ искать минимум функции многих переменных: из текущей точки делают шаг против градиента, w ← w − η·∂L/∂w, и повторяют. Им обучают почти все модели машинного обучения. Глава 63 · Машина учится

грамматика

Конечный набор правил, по которым из символов складываются все правильные фразы языка, и только они. Правило говорит, на что можно заменить нетерминал: S → ка | ка ло S. Глава 50 · Лингвист в экспедиции

гранью

Грань строки — её начало, которое одновременно её конец, но не вся строка. У «абракадабра» две грани: «абра» и «а». Глава 27 · Иголка в стоге

графом

Набор вершин и рёбер, каждое из которых соединяет две вершины. Граф помнит только, что с чем связано; расстояния, форма и расположение в нём не записаны. Глава 19 · Шесть рукопожатий

грязное чтение

Аномалия: транзакция читает изменения другой транзакции, которые ещё не зафиксированы и могут быть отменены. Глава 46 · Библиотека и банк

Двоичное дерево поиска

Двоичное дерево, в котором для каждого узла все ключи левого поддерева меньше его ключа, а все ключи правого — больше. Поиск, вставка и удаление идут одним путём от корня вниз. Глава 17 · Сад деревьев поиска

двоичный поиск

Поиск в отсортированном списке: сравнить искомое с серединой отрезка и отбросить половину, где его быть не может. Около log₂ n сравнений. Глава 20 · Турнир сортировок

двудольный

Граф, вершины которого делятся на две доли так, что каждое ребро соединяет вершины из разных долей. Глава 25 · Потоки и пары

двусвязным списком

Связный список, в котором каждый узел хранит ссылки и на следующий, и на предыдущий узел; по нему можно идти в обе стороны. Глава 14 · Как список лежит в памяти

двухбитный насыщающийся счётчик

Двухбитный счётчик предсказателя переходов: от 0 до 3, прыжок прибавляет единицу, не-прыжок вычитает, за края счётчик не выходит. 2 и 3 — прогноз «прыгнет», 0 и 1 — «не прыгнет»: чтобы сменить прогноз, нужны две ошибки подряд. Глава 35 · Конвейер и предсказатель

дек

Двусторонняя очередь: добавлять и забирать можно с обоих концов за O(1). Умеет быть и стеком, и очередью. В Python — collections.deque. Глава 15 · Стек, очередь и калькулятор

декларативными

Способ программирования, при котором описывают, каким должен быть результат, а не последовательность шагов. SQL и регулярные выражения декларативны; Python в основном императивен. Глава 45 · Архивариус

декогеренцией

Порча квантового состояния из-за взаимодействия с окружением: амплитуды теряют согласованные фазы, и кубит постепенно ведёт себя как обычный случайный бит. Глава 64 · Лаборатория кубитов

декомпозицией

Разбиение задачи на подзадачи, каждую из которых решает своя функция; сверху вниз — сначала главная функция, потом те, на которые она опирается. Глава 5 · Свои слова

декоратором

Функция, которая принимает функцию и возвращает новую, обёрнутую: с замером времени, подсчётом вызовов, запоминанием ответов. Записывается строкой @имя над def. Глава 10 · Функции как значения

дерево

Структура из узлов, где у каждого узла, кроме одного — корня, ровно один родитель, а детей может быть сколько угодно; путей по кругу нет. Двоичное дерево — дерево, где у узла не больше двух детей: левый и правый. Глава 17 · Сад деревьев поиска

дерево игры

Дерево игры: корень — текущая позиция, ветви из каждого узла — все допустимые ходы, листья — закончившиеся партии (выигрыш, проигрыш, ничья). Уровни чередуются: ход одного игрока, ход другого. Глава 62 · Турнир ботов

дерево разбора

Дерево вывода фразы по грамматике: в корне стартовый нетерминал, у каждого нетерминала дети — правая часть применённого к нему правила, в листьях по порядку стоят слова фразы. Глава 50 · Лингвист в экспедиции

дерево решений

Дерево всех возможных ходов алгоритма: во внутренних узлах — вопросы-сравнения, ветки — ответы, в листьях — результаты. Число сравнений на входе — длина пути от корня до листа. Глава 20 · Турнир сортировок

Детерминированный конечный автомат

Детерминированный конечный автомат: конечное множество состояний, алфавит, таблица переходов (состояние, символ) → состояние, начальное состояние и множество принимающих. Читает строку по символу и принимает её, если закончил в принимающем состоянии. Глава 54 · Автоматы и регулярки

дешифратор

Схема, которая по n-битному номеру зажигает ровно одну из 2ⁿ выходных линий; в памяти выбирает ячейку по адресу. Глава 31 · Память и такт

дизъюнктивной нормальной формой

Запись логической функции как «или» нескольких произведений («и») входов и их отрицаний; например, ab + āc. Глава 29 · Логика из выключателей

динамическим массивом

Массив, который растёт сам: держит запас мест, а когда запас кончается, переезжает в больший блок памяти. Так устроен список Python. Глава 14 · Как список лежит в памяти

Динамическое программирование

Метод решения задач, в которых подзадачи повторяются: ответ на каждую подзадачу вычисляется один раз и запоминается — рекурсией с памятью или таблицей снизу вверх. Глава 22 · Запомнить, чтобы не считать

динамической

Проверка типов во время работы программы: тип есть у значения, а не у переменной, и ошибка обнаруживается, только когда до неё дошло выполнение. Python, JavaScript, Лисп. Глава 49 · Музей языков

динамической

Правило, по которому функция ищет незнакомые имена в кадре того, кто её вызвал, и дальше по цепочке вызовов. Было в ранних Лиспах; живёт в переменных local командной оболочки. Глава 51 · Матрёшка

дискретное косинусное преобразование

Дискретное косинусное преобразование: запись блока чисел (например, 8 × 8 точек картинки) как суммы косинусных волн разных частот. В JPEG и MP3 после него мелкие высокочастотные детали можно хранить грубо. Глава 47 · Конкурс упаковки

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

Задача: по числам g, p и A = g^x mod p найти показатель x. Для больших p быстрых способов её решения не известно; на этом держится обмен ключами Диффи — Хеллмана. Глава 60 · Секрет на виду у всех

дополнительный код

Способ хранить целые со знаком в n битах: отрицательное число −x записывается как 2ⁿ − x. Старший бит — знак, нуль один, а сложение и вычитание делаются той же схемой, что и для чисел без знака. Глава 28 · Всё есть биты

допустимой

Эвристика в поиске пути, которая никогда не превышает истинного расстояния до цели. С ней A* находит кратчайший путь. Глава 24 · Навигатор

доставкой по возможности

Best effort, «как получится»: сеть старается доставить пакет, но ничего не обещает — он может потеряться, задублироваться или прийти позже следующего. Так работает IP. Глава 41 · Один день из жизни пакета

ёмкость

Сколько мест отведено под элементы динамического массива; длина — сколько из них занято. Ёмкость не меньше длины. Глава 14 · Как список лежит в памяти

Ёмкость разреза

Сумма пропускных способностей рёбер, которые идут из части разреза с истоком в часть со стоком. Глава 25 · Потоки и пары

жадный алгоритм

Алгоритм, который строит ответ по шагам и на каждом шаге делает выбор, лучший по простому местному правилу, никогда его не отменяя. Глава 23 · Жадность и электричество

журнал

Отдельная область диска, куда файловая система (или база данных) сначала записывает все задуманные изменения с отметкой «готово» и только потом вносит их на место. После сбоя завершённые записи журнала повторяют, незавершённые отбрасывают. Глава 40 · Спасательная операция

журнал упреждающей записи

Журнал упреждающей записи (write-ahead log): база сначала дописывает изменения в конец отдельного файла-журнала и только потом, при контрольной точке, переносит их в сам файл базы. Подтверждённой считается транзакция, чья запись «готово» дошла до журнала. Глава 46 · Библиотека и банк

заголовки

Строка «Имя: значение» в запросе или ответе HTTP. Заголовки несут всё, кроме самого содержимого: имя сайта, тип и длину данных, правила кэширования, куки. Глава 43 · Анатомия этой страницы

Задача выполнимости

Задача выполнимости: можно ли так выбрать значения переменных, чтобы формула в КНФ стала истинной. Первая задача, у которой доказали NP-полноту (Кук, 1971; Левин, 1973). 3-SAT — то же для условий из трёх литералов. Глава 57 · Письмо Гёделя

задачей коммивояжёра

Задача коммивояжёра: найти кратчайший замкнутый маршрут, проходящий через каждый город ровно один раз. Её вариант «есть ли маршрут не длиннее L» NP-полон. Глава 58 · Экспедиция коммивояжёра

задачей распознавания

Задача, ответ на которую — «да» или «нет»: есть ли рассадка, можно ли дописать судоку, выполнима ли формула. На них строится теория сложности: P, NP и NP-полнота говорят именно о таких задачах. Глава 57 · Письмо Гёделя

задержкой

Время, за которое выход логического вентиля успевает отозваться на изменение входов; у современных вентилей — порядка пикосекунд, но в длинной цепочке задержки складываются. Глава 30 · Машина считает

задержкой

Время от запроса до ответа: сколько ждать одного обращения к памяти, диску или серверу. Не путать с пропускной способностью — сколько данных проходит за секунду. Глава 34 · Близко и далеко

Закладка

Закладка (backdoor): намеренно скрытый способ обойти защиту — тайный пароль, встроенный в программу, или код, добавленный в инструмент сборки. В отличие от уязвимости, закладку оставляют нарочно. Глава 61 · Учебный полигон

закон Амдала

Если доля p работы программы делится между N ядрами, а остальное последовательно, ускорение равно 1 / ((1 − p) + p/N) и никогда не превышает 1 / (1 − p). Глава 35 · Конвейер и предсказатель

законом Мура

Наблюдение Гордона Мура (1965, уточнено в 1975): число транзисторов на микросхеме удваивается примерно каждые два года. Это наблюдение за промышленностью, а не закон природы. Глава 35 · Конвейер и предсказатель

законом Ципфа

Наблюдение о текстах: слово на r-м месте по частоте встречается примерно в r раз реже самого частого. Глава 8 · Словарь и телеграф

законы де Моргана

Правила переворота отрицания: «не (a и b)» равно «не a или не b», а «не (a или b)» равно «не a и не b». Глава 29 · Логика из выключателей

закрытый ключ

Половина пары ключей, которую владелец никому не показывает: ею расшифровывают и подписывают. Вычислить её по открытому ключу практически невозможно. Глава 60 · Секрет на виду у всех

замыканием

Функция вместе с переменными того места, где её создали: она помнит их и после того, как создавшая её функция закончила работу. Глава 10 · Функции как значения

запутанным

Свойство состояния нескольких кубитов, которое нельзя записать как произведение состояний каждого: результаты их измерений связаны сильнее, чем при любой классической договорённости. Глава 64 · Лаборатория кубитов

защёлка

Простейшая ячейка памяти на один бит: петля из двух вентилей с входами для записи. RS-защёлка ставится в 1 или в 0 отдельными входами, D-защёлка пока открыта, повторяет вход D, а закрывшись, хранит последнее значение. Глава 31 · Память и такт

защитой в несколько слоёв

Защита в несколько слоёв (defense in depth): несколько независимых мер, каждая из которых останавливает атаку сама по себе. Если один слой пробит или забыт, следующий ещё держит. Противоположность единственной стене. Глава 61 · Учебный полигон

иерархией памяти

Устройство памяти компьютера ступеньками: регистры, кэши L1–L3, оперативная память, диск. Каждая ступень больше и медленнее предыдущей; часто нужные данные держат на верхних. Глава 34 · Близко и далеко

иерархией Хомского

Классификация языков (и грамматик) по силе машины, которая их распознаёт: регулярные — конечный автомат, контекстно-свободные — автомат со стеком, контекстно-зависимые — машина с лентой длиной во вход, рекурсивно перечислимые — машина Тьюринга. Хомский, 1956. Глава 54 · Автоматы и регулярки

избыточностью

Предсказуемая часть данных — то, что можно не хранить: разница между длиной записи и количеством информации в ней. Сжатие без потерь удаляет избыточность. Глава 47 · Конкурс упаковки

изменяемыми

Изменяемый объект можно поменять на месте, не создавая нового: список, словарь, множество. Неизменяемые — числа, строки, кортежи: их можно только заменить другими. Глава 6 · Списки

измерение

Операция, которая даёт классический результат: базисное состояние |k⟩ с вероятностью |амплитуда k|². После измерения система оказывается в этом базисном состоянии, а прежние амплитуды теряются. Глава 64 · Лаборатория кубитов

имитацией отжига

Локальный поиск, который иногда принимает ухудшения: ход, удлиняющий решение на Δ, принимается с вероятностью e^(−Δ/T), а «температура» T постепенно снижается. Так поиск выбирается из локальных оптимумов. Глава 58 · Экспедиция коммивояжёра

императивное программирование

Парадигма программирования, в которой программа — последовательность команд, меняющих состояние памяти: присваивания, циклы, переходы. FORTRAN, C, Pascal, большая часть кода на Python. Глава 49 · Музей языков

инвариант цикла

Утверждение о переменных цикла, которое верно перед первой итерацией и остаётся верным после каждой. Вместе с условием выхода оно доказывает, что цикл делает то, что нужно. Глава 20 · Турнир сортировок

инверсией

Пара позиций i < j, где a[i] > a[j]: два элемента, стоящие не по порядку. В отсортированном списке инверсий нет, в развёрнутом их n(n − 1)/2. Глава 20 · Турнир сортировок

инверсией приоритетов

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

индекс

Отдельная структура рядом с таблицей: значения выбранных столбцов, упорядоченные для быстрого поиска, и при каждом — адрес строки (в SQLite rowid). Ускоряет поиск и сортировку, но замедляет запись и занимает место. Глава 46 · Библиотека и банк

индексный узел

Индексный узел (inode): запись файловой системы Unix о файле — размер, владелец, права, время изменения и список блоков с содержимым. Имени файла в нём нет: имена хранятся в каталогах. Глава 40 · Спасательная операция

индексом

Номер элемента в списке или строке, считая с нуля: a[0] — первый элемент, a[-1] — последний. Глава 6 · Списки

индексом совпадений

Вероятность того, что две буквы, выбранные из текста наугад, совпадут. У русского текста около 0,056, у равномерной случайной смеси 32 букв — 1/32 ≈ 0,031. Не меняется при шифре замены. Глава 59 · Шифровальный отдел

инкапсуляцией

Принцип: объект прячет своё устройство и меняет своё состояние только через свои методы, которые следят за его правилами. Снаружи видно, что объект умеет, но не как он это делает. Глава 12 · Остров кроликов и лис

интерпретатором

Программа, которая исполняет другую программу команда за командой, на ходу: читает команду, выполняет, переходит к следующей. Глава 33 · Рентген Python

интерференцией

Сложение амплитуд разных путей вычисления, ведущих к одному исходу: одинаковые знаки усиливают исход, противоположные гасят его. Источник выигрыша квантовых алгоритмов. Глава 64 · Лаборатория кубитов

инфиксной

Привычная запись выражения, где знак операции стоит между операндами: 3 + 4 · 5. Ей нужны скобки и правила старшинства операций. Глава 15 · Стек, очередь и калькулятор

исключающее или

Исключающее или: логическая операция, равная 1, когда ровно один из двух битов равен 1. В Python — оператор ^, который применяет её к каждой паре битов чисел. Повторный XOR с тем же ключом возвращает исходное: (m ^ k) ^ k == m. Глава 59 · Шифровальный отдел

исключение

Сигнал об ошибке, который прерывает обычное выполнение: вместо значения функция «бросает» объект-исключение, и он летит к вызвавшим её функциям, пока кто-нибудь его не поймает. Глава 11 · Отчёт комиссии

итерацией

Один проход по телу цикла. Глава 4 · Снова и снова

кадром стека

Участок стека, принадлежащий одному вызову функции: адрес возврата, сохранённые регистры и локальные переменные. Появляется при вызове, освобождается при возврате. Глава 33 · Рентген Python

кадры

Кусок физической памяти размером со страницу. Каждая страница процесса, которая сейчас в памяти, лежит в каком-то кадре. Глава 38 · Гостиница с номерами

Канал

Канал (pipe) — буфер в ядре с двумя концами: что один процесс пишет в один конец, другой читает из другого в том же порядке. Писатель ждёт, когда буфер полон, читатель — когда пуст. Глава 36 · Экскурсия по живой системе

карты Карно

Таблица истинности, разложенная прямоугольником так, что соседние клетки различаются значением одного входа; группы соседних единиц дают упрощённую формулу. Глава 29 · Логика из выключателей

катастрофическим перебором

Экспоненциальный (или высокий полиномиальный) рост времени поиска по регулярному выражению у движков с перебором с возвратом: если совпадения нет, движок перебирает все способы разрезать строку между частями выражения. Атака на это — ReDoS. Глава 54 · Автоматы и регулярки

квадратичное

Время, которое растёт как квадрат размера входа: вдвое больше данных — вчетверо дольше. Типичный признак — каждый элемент сравнивается с каждым. Глава 13 · Сколько стоит программа

квантование

Округление значений до ступенек заданного размера: вместо точного числа хранится номер ступеньки. Главный источник потерь в JPEG и MP3; чем крупнее ступеньки, тем меньше файл и хуже качество. Глава 47 · Конкурс упаковки

квантовые гейты

Операция над кубитами: унитарная матрица, на которую умножается вектор состояния. Унитарные матрицы сохраняют длину вектора, а значит, сумму вероятностей, и всегда обратимы. Глава 64 · Лаборатория кубитов

квантом

Отрезок времени, на который планировщик отдаёт ядро процессу; когда он истекает, прерывание от таймера возвращает управление планировщику. Глава 37 · Центр управления полётом

кворумом

Набор узлов, согласия которых достаточно для решения. Обычно — любое большинство: любые два большинства пересекаются, поэтому два решения не могут пройти незаметно друг для друга. Глава 44 · Парламент острова Паксос

класса

Описание вида объектов: какие у них атрибуты и что они умеют (методы). По классу, как по чертежу, создают сколько угодно объектов. Глава 12 · Остров кроликов и лис

клеточным автоматом

Сетка клеток, каждая в одном из конечного числа состояний; на каждом шаге все клетки одновременно меняют состояние по одному и тому же правилу, которое смотрит на клетку и её соседей. Пример — игра «Жизнь» Конвея. Глава 55 · Машина Тьюринга

ключ

Секретный параметр шифра: число, слово, таблица или случайные байты. Кто знает шифр и ключ, читает шифровку; кто знает только шифр, читать не должен. Глава 59 · Шифровальный отдел

ключом

То, по чему в словаре ищут значение: слово, буква, число или кортеж. Ключи в словаре не повторяются. Глава 8 · Словарь и телеграф

код возврата

Число, с которым процесс заканчивает работу и которое получает его родитель: 0 — всё в порядке, любое другое — что-то пошло не так. Глава 36 · Экскурсия по живой системе

код операции

Число в команде процессора, которое говорит, какую операцию выполнить: например, в «Искре-8» 5 означает сложение, 6 — вычитание. Глава 30 · Машина считает

код состояния

Трёхзначное число в первой строке ответа HTTP. Первая цифра — класс: 2 — успех, 3 — иди в другое место, 4 — ошибка клиента, 5 — ошибка сервера. 200 OK, 301 переехал, 404 не найдено, 500 сервер упал. Глава 43 · Анатомия этой страницы

код Хаффмана

Префиксный код наименьшей цены для данных частот букв; строится повторным слиянием двух самых редких букв (поддеревьев) в одно. Глава 23 · Жадность и электричество

кодирование длин серий

Кодирование длин серий (run-length encoding): идущие подряд одинаковые значения заменяются парой «сколько раз, какое значение». Хорошо сжимает картинки с большими однотонными областями и ничего не даёт на тексте. Глава 47 · Конкурс упаковки

кодировкой

Договорённость, каким числом (или какими байтами) записывается каждый символ: ASCII, КОИ-8, CP1251, UTF-8. Прочитать байты можно только той же кодировкой, какой их записали. Глава 28 · Всё есть биты

кодовой точкой

Номер символа в Юникоде, от 0 до 0x10FFFF; записывается как U+0416 («Ж»). В Python его возвращает ord, а строка — это последовательность кодовых точек. Глава 28 · Всё есть биты

коллапс перегрузки

Состояние сети, в котором каналы заняты почти целиком, а полезных данных доходит в сотни раз меньше: очереди переполнены, и сеть передаёт в основном повторы потерянных пакетов. Глава 42 · Изобрести протокол

коллизия

Ситуация, когда у двух разных ключей хеш-таблица выбирает одну корзину (или у них совпали сами хеши). Коллизии неизбежны; таблица должна уметь с ними жить. Глава 16 · Хеш-таблица: атака и защита

колмогоровской сложностью

Длина кратчайшей программы, которая печатает данную строку и останавливается. Предел сжатия отдельной строки; вычислить её никаким алгоритмом нельзя. Глава 47 · Конкурс упаковки

кольцевой буфер

Очередь на массиве постоянной длины, свёрнутом в кольцо: голова и хвост движутся вперёд и по модулю длины возвращаются к началу. Ничего не сдвигается, память не растёт. Глава 15 · Стек, очередь и калькулятор

Коммит

Снимок проекта в системе контроля версий: адрес дерева файлов, адреса родительских коммитов, автор и сообщение. В git адрес коммита — хеш всего этого, поэтому он заверяет и содержимое, и всю историю до него. Глава 40 · Спасательная операция

коммутацией пакетов

Способ строить сеть, при котором данные режут на пакеты с адресами, а узлы передают каждый пакет дальше по отдельности. Каналы делят все, кто сейчас передаёт; выделенной линии ни у кого нет. Глава 41 · Один день из жизни пакета

коммутация каналов

Способ строить сеть, при котором на время разговора между двумя абонентами выделяется сквозной канал, принадлежащий только им, даже когда они молчат. Так работала телефонная сеть. Глава 41 · Один день из жизни пакета

компилятор

Программа, которая заранее переводит всю программу с одного языка на другой, обычно на машинный код процессора; перевод потом исполняется без неё. Глава 33 · Рентген Python

композиция

Соединение функций, при котором результат одной становится аргументом другой: f(g(x)). Глава 5 · Свои слова

композиция объектов

Способ строить объект из других объектов: остров хранит в атрибутах луг и список зверей и поручает им работу. Отношение «у острова есть луг», в отличие от наследования, где «лиса — это зверь». Глава 12 · Остров кроликов и лис

компонентами связности

Наибольший кусок графа без направлений, внутри которого из любой вершины можно дойти до любой другой. Граф, у которого компонента одна, называют связным. Глава 19 · Шесть рукопожатий

конвейером

Устройство процессора, при котором команда проходит несколько этапов (выборка, декодирование, исполнение, запись), и разные этапы разных команд выполняются одновременно: в каждый такт на конвейер входит новая команда. Глава 35 · Конвейер и предсказатель

конвейером команд

Цепочка программ, соединённых каналами: стандартный вывод каждой подключён к стандартному вводу следующей. В оболочке пишется через вертикальную черту: sort | uniq -c. Глава 36 · Экскурсия по живой системе

конечным автоматом

Устройство или программа с конечным числом состояний: на каждом шаге по текущему состоянию и очередному входу выбирается следующее состояние. Глава 31 · Память и такт

консенсус

Задача о согласии: несколько узлов предлагают значения, и все исправные узлы должны выбрать одно и то же значение из предложенных. Решение должно оставаться верным при отказах узлов и потерях сообщений. Глава 44 · Парламент острова Паксос

контекстно-свободными

Грамматика, у которой в левой части каждого правила стоит один нетерминал, и его можно заменить по правилу независимо от окружения. Синтаксис почти всех языков программирования описывают такими грамматиками. Глава 50 · Лингвист в экспедиции

контрольная сумма

Короткое число, вычисленное по данным при записи и проверяемое при чтении: если данные изменились, число почти наверняка не совпадёт. Примеры — бит чётности, Adler-32, CRC-32, SHA-256. Глава 40 · Спасательная операция

контрольная цифра

Цифра, которую дописывают к номеру так, чтобы по остальным цифрам можно было проверить, не ошиблись ли в номере. Глава 5 · Свои слова

конфигурацией

Полное мгновенное описание машины Тьюринга: содержимое ленты, положение головки и состояние. По конфигурации и таблице однозначно определяется следующая конфигурация. Глава 55 · Машина Тьюринга

конфликтами конвейера

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

конъюнктивной нормальной форме

Конъюнктивная нормальная форма: формула вида «условие и условие и …», где каждое условие — «или» нескольких литералов (переменных и их отрицаний). Например, (x₁ ∨ ¬x₂) ∧ (x₂ ∨ x₃). В таком виде формулы получают SAT-решатели. Глава 57 · Письмо Гёделя

кооперативная многозадачность

Многозадачность, при которой задачи сами отдают процессор — в удобных им местах, — а планировщик никого не прерывает. Дёшево и предсказуемо, но одна задача, которая не уступает, останавливает все остальные. Глава 37 · Центр управления полётом

копирование при записи

Приём, при котором копия данных сначала разделяет память с оригиналом, а настоящее копирование страницы происходит только при первой записи в неё. Так fork создаёт процесс, не копируя всю его память. Глава 38 · Гостиница с номерами

корень

Самый верхний узел дерева, единственный, у которого нет родителя. От него начинаются все пути и поиски. Глава 17 · Сад деревьев поиска

корзинами

Ячейка хеш-таблицы: место для записей, хеш ключа которых по модулю размера таблицы равен её номеру. Глава 16 · Хеш-таблица: атака и защита

корнями

Места, с которых сборщик мусора начинает искать живые объекты: глобальные переменные, локальные переменные в кадрах стека, регистры. Всё, до чего от них нельзя дойти по ссылкам, — мусор. Глава 51 · Матрёшка

корректной

Свойство системы типов: если программа прошла проверку, при выполнении в ней не случится ошибок типов. Цена корректности — проверка иногда отвергает правильные программы. Глава 53 · Суд над null

кортеж

Неизменяемая последовательность значений в круглых скобках: (время, широта, долгота). Удобна для записей с постоянным набором полей. Глава 6 · Списки

коэффициентом Жаккара

Мера сходства двух множеств: размер пересечения, делённый на размер объединения. 1 — множества совпадают, 0 — общих элементов нет. Глава 27 · Иголка в стоге

коэффициентом заполнения

Отношение числа записей хеш-таблицы к числу её корзин, α = n/m. От него зависит средняя длина цепочки, а значит, и время поиска. Глава 16 · Хеш-таблица: атака и защита

кратчайшим путём

Путь между двумя вершинами графа с наименьшим числом рёбер, а если у рёбер есть длины — с наименьшей суммой длин. Число рёбер на кратчайшем пути — расстояние между вершинами. Глава 19 · Шесть рукопожатий

криптоанализом

Искусство и наука вскрывать шифры: читать шифровки без ключа или находить сам ключ. Глава 59 · Шифровальный отдел

криптографической

Хеш-функция, у которой практически невозможно найти вход по значению, второй вход с тем же значением или вообще два входа с одинаковым значением. Примеры — SHA-256, SHA-3; MD5 и SHA-1 этим требованиям больше не отвечают. Глава 60 · Секрет на виду у всех

критической секцией

Участок программы, где поток работает с общими данными и где одновременно может находиться только один поток. Глава 39 · Гонки

куайнами

Программа, которая печатает собственный исходный текст, не читая его из файла. Глава 0 · Что умеет программа

Кубит

Квантовый бит: система с двумя базисными состояниями |0⟩ и |1⟩, состояние которой — единичный вектор α|0⟩ + β|1⟩ с комплексными амплитудами, |α|² + |β|² = 1. Глава 64 · Лаборатория кубитов

куки

Маленький кусок данных, который сервер передаёт браузеру заголовком Set-Cookie, а браузер возвращает с каждым следующим запросом на тот же сайт. Так сервер, который не помнит клиентов, узнаёт своих: по номеру сессии. Глава 43 · Анатомия этой страницы

куча

Двоичное дерево, в котором ключ каждого узла не больше ключей его детей (свойство кучи); самый маленький ключ — в корне. Обычно хранится в массиве: дети ячейки i — в ячейках 2i+1 и 2i+2. Глава 18 · Кто следующий

кэши

Небольшая быстрая память, где хранятся копии данных из большой медленной, чтобы при повторном обращении не ходить далеко. Глава 34 · Близко и далеко

лавинный эффект

Свойство хорошей хеш-функции или шифра: изменение одного бита входа меняет в среднем половину битов результата, причём непредсказуемо какие. Глава 60 · Секрет на виду у всех

лексер

Первая ступень разбора программы: проходит текст слева направо и режет его на токены — числа, имена, знаки, строки, — выбрасывая пробелы и комментарии. Иначе лексический анализатор, токенизатор. Глава 50 · Лингвист в экспедиции

лексической областью видимости

Правило, по которому функция ищет незнакомые имена там, где она написана в тексте программы (в кадре, где её создали), а не там, откуда её вызвали. Так устроены Python, Scheme, JavaScript и почти все современные языки. Глава 51 · Матрёшка

леммой о накачке

Свойство регулярных языков: любую достаточно длинную строку языка можно разрезать на xyz с непустым y так, что xy…yz (y повторён любое число раз, в том числе ноль) тоже в языке. Нарушение леммы доказывает, что язык не регулярен. Глава 54 · Автоматы и регулярки

ленивые вычисления

Способ вычислять значения только тогда, когда их запрашивают, и не больше, чем запрошено: так работают генераторы, map и filter. Глава 10 · Функции как значения

линейное

Время, пропорциональное размеру входа n: вдвое больше данных — вдвое дольше. Так работают сумма списка и поиск перебором. Глава 13 · Сколько стоит программа

линейный поиск

Поиск перебором: просмотреть элементы по очереди, пока не найдётся нужный. В худшем случае n сравнений; работает на любом списке. Глава 20 · Турнир сортировок

листья

Узел дерева без детей: на нём ветка кончается. Глава 17 · Сад деревьев поиска

логарифмическое

Время, которое растёт как log n: при удвоении входа добавляется один шаг. Так работает двоичный поиск. Глава 13 · Сколько стоит программа

логическим

Кубит, закодированный кодом коррекции ошибок во многих физических кубитах. Если физические ошибки реже порога, с ростом кода ошибки логического кубита падают экспоненциально. Глава 64 · Лаборатория кубитов

логическим вентилем

Электронная схема с несколькими входами и одним выходом, вычисляющая логическую функцию: «и», «или», «не», «и-не» и другие. Глава 29 · Логика из выключателей

логическое значение

Логический тип bool: всего два значения, True (истина) и False (ложь). Их дают сравнения, на них держатся условия. Глава 2 · Имена и значения

логическое программирование

Парадигма программирования, в которой программа — набор фактов и правил, а вычисление — поиск ответа на запрос: система сама перебирает правила, подставляет значения переменных и возвращается из тупиков. Пролог, Datalog. Глава 49 · Музей языков

ложное срабатывание

Ответ «да» там, где правильный ответ «нет»: например, фильтр Блума считает элемент добавленным, хотя его не добавляли. Глава 26 · Подбросим монетку

локальностью

Свойство программ обращаться к данным неслучайно: к недавно тронутым — снова (во времени) и к соседям недавно тронутых (в пространстве). На нём держатся все кэши. Глава 34 · Близко и далеко

локальные переменные

Переменная, созданная внутри функции (в том числе параметр); существует только во время вызова и не видна снаружи. Глава 5 · Свои слова

локальный оптимум

Решение, которое нельзя улучшить ни одним ходом локального поиска. Оно может быть намного хуже лучшего — глобального оптимума. Глава 58 · Экспедиция коммивояжёра

локальным поиском

Способ решать задачи оптимизации: взять какое-нибудь решение и улучшать его маленькими изменениями (ходами), пока улучшения находятся. Пример — 2-opt для коммивояжёра. Глава 58 · Экспедиция коммивояжёра

маршрутизатором

Устройство на стыке нескольких сетей: принимает пакет, читает адрес назначения в его IP-заголовке и по таблице маршрутизации решает, в какую сторону его отправить. Глава 41 · Один день из жизни пакета

массивом

Блок памяти из одинаковых ячеек, лежащих подряд. Адрес ячейки i — начало блока плюс i, умноженное на размер ячейки, поэтому любая ячейка доступна за одно действие. Глава 14 · Как список лежит в памяти

матрицей смежности

Способ хранить граф таблицей n × n: в клетке (a, b) единица, если ребро из a в b есть, и ноль, если нет. Проверка ребра — O(1), но памяти нужно n² клеток при любом числе рёбер. Глава 19 · Шесть рукопожатий

Машина Тьюринга

Воображаемая вычислительная машина: бесконечная лента из клеток с символами, головка над одной клеткой и конечная таблица правил «в состоянии q читаю символ a — пишу b, сдвигаюсь влево или вправо, перехожу в состояние r». Нет подходящего правила — машина останавливается. Глава 55 · Машина Тьюринга

машинное обучение

Способ строить программы по примерам с ответами: правило подбирают, меняя настраиваемые числа модели, пока она не начнёт отвечать на примерах правильно. Глава 63 · Машина учится

машинным кодом

Программа в том виде, в каком её исполняет процессор: последовательность чисел-команд в памяти. Глава 32 · Ты — процессор

медленными хешами паролей

Хеш-функция для хранения паролей: с солью и нарочно медленная (много повторов или много памяти), чтобы перебор словаря стоил атакующему дорого. Примеры — Argon2, scrypt, bcrypt, PBKDF2. Глава 60 · Секрет на виду у всех

межсайтовый скриптинг

Межсайтовый скриптинг (XSS): атака, при которой данные от пользователя попадают на страницу без экранирования и браузер исполняет их как скрипт в контексте сайта. Защита — экранирование вывода (html.escape) и флаг HttpOnly у важных куки. Глава 61 · Учебный полигон

мемоизацией

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

мёртвым

Часть программы, которая никогда не выполняется (после безусловного прыжка, в ветке if с всегда ложным условием) или результат которой никому не нужен. Оптимизатор её удаляет. Глава 52 · Замкнуть круг

метастабильностью

Состояние ячейки памяти, при котором выход какое-то время висит между 0 и 1, а потом непредсказуемо сваливается в одно из значений. Возникает, если вход меняется в момент записи. Глава 31 · Память и такт

метациклическим

Интерпретатор языка, написанный на этом же языке, где каждое свойство языка определено через то же свойство языка-хозяина: if — через if, вызов — через вызов. Классический пример — eval Лиспа на Лиспе. Глава 51 · Матрёшка

Метод

Первое слово запроса HTTP: что клиент хочет сделать. GET — получить, HEAD — только заголовки, POST — отправить данные, PUT — положить по адресу, DELETE — удалить. Глава 43 · Анатомия этой страницы

метод Монте-Карло

Способ найти число — вероятность, площадь, среднее, — устроив случайный опыт, где это число — доля удач или среднее, и повторив опыт много раз. Глава 26 · Подбросим монетку

методами

Функция, описанная внутри класса. Вызывается через точку: bunny.hop(1, 0); объект перед точкой попадает в параметр self. Глава 12 · Остров кроликов и лис

методом цепочек

Способ разрешать коллизии: в каждой корзине хеш-таблицы хранится цепочка (список) всех записей, попавших в неё. Глава 16 · Хеш-таблица: атака и защита

минимакс

Минимакс: способ оценить позицию в игре двух соперников. Значение узла — максимум по детям на ходу игрока, который хочет больше, и минимум на ходу того, кто хочет меньше. Так выбирают ход, считая, что соперник отвечает наилучшим образом. Глава 62 · Турнир ботов

минимальным остовным деревом

Остовное дерево взвешенного графа с наименьшей суммой весов рёбер. Глава 23 · Жадность и электричество

многоуровневая очередь с обратной связью

Многоуровневая очередь с обратной связью: несколько очередей с разными приоритетами; новая задача начинает с верхней, а задача, истратившая свой квант целиком, опускается ниже, где кванты длиннее. Придумана в CTSS (1962). Глава 37 · Центр управления полётом

множество

Набор различных значений без порядка и повторов; проверка «есть ли x» в нём такая же быстрая, как поиск ключа в словаре. Глава 8 · Словарь и телеграф

моделью

В машинном обучении — функция с настраиваемыми числами (весами): по входу она выдаёт ответ, а обучение подбирает веса по примерам. Глава 63 · Машина учится

моделью угроз

Модель угроз: явный список того, что система защищает (данные, деньги, доступность), от какого нарушителя (случайный посетитель, сосед по серверу, государство) и какой ценой. Защиту строят под конкретную модель угроз. Глава 61 · Учебный полигон

Модульный тест

Маленькая функция, которая вызывает проверяемый код на известном входе и сравнивает результат с ожидаемым; если он не совпал, тест падает. Глава 11 · Отчёт комиссии

Мультиплексор

Схема-переключатель: по управляющему сигналу (адресу) пропускает на выход один из нескольких входов. Глава 29 · Логика из выключателей

мутантов

Копия программы с одной маленькой нарочно внесённой ошибкой: другим знаком сравнения, сдвинутой границей, пропущенной проверкой. Хорошие тесты должны её заметить. Глава 11 · Отчёт комиссии

наибольшая общая подпоследовательность

Самая длинная последовательность, которую можно получить вычёркиванием и из одной данной, и из другой. Основа программ сравнения текстов: всё, что в неё не вошло, удалено или добавлено. Глава 22 · Запомнить, чтобы не считать

накопителями

Переменная, которая получает начальное значение до цикла и обновляется на каждой его итерации: сумма, счётчик, наибольшее значение. Глава 4 · Снова и снова

наследование

Способ описать класс через другой: class Fox(Animal) получает все атрибуты и методы Animal и может добавить свои или заменить унаследованные. Глава 12 · Остров кроликов и лис

наследование приоритетов

Правило для мьютексов: пока задачу, держащую мьютекс, ждёт задача более высокого приоритета, держащая временно получает этот приоритет; отпустив мьютекс, она возвращается к своему. Глава 39 · Гонки

недетерминированным

Недетерминированный конечный автомат: из одного состояния по одному символу может вести несколько переходов или ни одного, бывают ε-переходы без чтения символа. Принимает строку, если хотя бы один путь по ней ведёт в принимающее состояние. Глава 54 · Автоматы и регулярки

нейронная сеть

Модель из слоёв «нейронов»: каждый нейрон считает взвешенную сумму выходов предыдущего слоя и пропускает её через нелинейную функцию активации. Слои между входом и выходом называют скрытыми. Веса всех слоёв подбирают градиентным спуском. Глава 63 · Машина учится

необязательными

Тип «значение или ничего»: str | None (Optional[str]) в Python, String? в Kotlin, Option в Rust, Maybe в Haskell. Проверка типов не даёт обратиться к значению, пока не доказано, что оно есть. Глава 53 · Суд над null

неоднозначной

Грамматика, по которой у какой-нибудь фразы больше одного дерева разбора. Для языка программирования это ошибка описания: у программы должен быть один смысл. Глава 50 · Лингвист в экспедиции

неопределённое поведение

Действие, о результате которого стандарт языка ничего не обещает (в C — запись за край массива, переполнение знакового целого). Программа может упасть, тихо испортить данные или работать как ни в чём не бывало. Глава 33 · Рентген Python

нетерминалами

Имя части фразы в грамматике (выражение, слагаемое, оператор), которое правила заменяют на последовательности других нетерминалов и терминалов — слов самого языка. Глава 50 · Лингвист в экспедиции

номером последовательности

Номер последовательности — номер, который отправитель пишет в каждый пакет, чтобы получатель мог расставить данные по местам, выбросить повторы и заметить пропуски. В TCP нумеруются не пакеты, а байты. Глава 42 · Изобрести протокол

нормализация

Перестройка схемы базы данных так, чтобы каждый факт хранился в одном месте: повторяющиеся сведения выносят в отдельную таблицу и ссылаются на неё ключом. Защищает от расхождений при правках. Глава 45 · Архивариус

область подкачки

Место на диске, куда операционная система выносит страницы, которым не хватило физической памяти, чтобы вернуть их обратно при следующем обращении. Подкачка — сам этот обмен. Глава 38 · Гостиница с номерами

областью видимости

Часть программы, в которой имя переменной что-то значит: локальные имена функции видны только внутри неё. Глава 5 · Свои слова

обмен ключами Диффи — Хеллмана

Протокол, по которому двое получают общий секретный ключ, обмениваясь только открытыми сообщениями: A = g^a mod p и B = g^b mod p; общий ключ g^ab mod p. Подслушивающему нужен дискретный логарифм. Глава 60 · Секрет на виду у всех

обобщёнными

Тип с параметром-типом: list[T], dict[K, V], Option<T>. Одна обобщённая функция работает с любым T, а проверка типов при каждом вызове подставляет вместо T конкретный тип. Глава 53 · Суд над null

оболочки

Командный интерпретатор (sh, bash, zsh): обычная программа, которая читает команды, запускает их через fork и exec, соединяет трубами и перенаправляет их ввод и вывод. Глава 36 · Экскурсия по живой системе

обратная связь

Соединение, при котором выход схемы подаётся обратно на её вход. Нечётное число инверсий в петле даёт колебания, чётное — устойчивое состояние, то есть память. Глава 31 · Память и такт

обратное распространение ошибки

Способ за один проход от выхода сети к входу вычислить градиент функции потерь по всем её весам: производные по цепному правилу, слой за слоем. Глава 63 · Машина учится

обратной польской

Запись выражения, в которой знак операции стоит после операндов: 3 4 + вместо 3 + 4. Не нуждается в скобках и правилах старшинства и вычисляется одним проходом со стеком. Глава 15 · Стек, очередь и калькулятор

обратным индексом

Словарь «слово → список документов, где оно встречается» (обычно с числом вхождений и позициями). Его строят заранее, и запрос сводится к нескольким обращениям к словарю и пересечению списков. Глава 48 · Поисковик по нашим учебникам

обучающей выборкой

Примеры с правильными ответами, по которым подбирают веса модели. Глава 63 · Машина учится

обход в глубину

Обход графа, который идёт вперёд, пока может, а в тупике возвращается к последней развилке с неосмотренными рёбрами. Пишется рекурсией или своим стеком (LIFO); время O(V + E). Кратчайших путей не ищет. Глава 19 · Шесть рукопожатий

обход в ширину

Обход графа кругами: сначала соседи начальной вершины, потом их соседи, и так далее. Вершины ждут своей очереди в очереди FIFO. В графе без весов находит пути с наименьшим числом рёбер; время O(V + E). Глава 19 · Шесть рукопожатий

обходы

Способ посетить каждый узел дерева ровно один раз. Прямой обход: узел, потом левое и правое поддеревья; симметричный: левое, узел, правое; обратный: левое, правое, узел; в ширину — по этажам. Глава 17 · Сад деревьев поиска

объект

Значение в памяти машины: у него есть тип, содержимое и своя «личность» (номер id). Имена в Python указывают на объекты. Глава 2 · Имена и значения

объектно-ориентированное программирование

Объектно-ориентированное программирование — парадигма, в которой программа — множество объектов: каждый хранит своё состояние и отвечает на сообщения (вызовы методов). Simula, Smalltalk, Java; в Python это классы. Глава 49 · Музей языков

одноразовым блокнотом

Шифр, в котором ключ — случайная последовательность длиной с сообщение, используемая один раз; каждый символ шифруется своим символом ключа (сдвигом или XOR). При соблюдении условий невзламываем. Глава 59 · Шифровальный отдел

односторонней

Функция, значение которой вычисляется быстро, а найти по значению аргумент практически невозможно: например, перемножить два больших простых числа и разложить произведение. Существование таких функций не доказано. Глава 60 · Секрет на виду у всех

окружением

Цепочка кадров, в которой интерпретатор ищет значения имён: сначала в текущем кадре, потом во внешнем, и так до глобального. У каждого вызова функции — новый кадр, а внешний для него — кадр, где функцию создали (при лексической области видимости). Глава 51 · Матрёшка

оперативной

Оперативная память, ОЗУ (RAM, random access memory): память, где любую ячейку можно прочитать или записать по адресу за одно обращение. Теряет содержимое без питания. Глава 31 · Память и такт

операционная система

Программа, которая распоряжается железом компьютера и делит его между другими программами: даёт им процессорное время, память, доступ к файлам и устройствам — и защищает программы друг от друга. Глава 36 · Экскурсия по живой системе

опорным

Элемент, относительно которого быстрая сортировка делит список: меньшие налево, большие направо. Глава 21 · Разделяй и властвуй

оптимальной подструктурой

Свойство задачи на оптимум: лучшее решение целой задачи составлено из лучших решений её подзадач. Без него таблица лучших ответов не помогает. Глава 22 · Запомнить, чтобы не считать

оптимизацией глазком

Оптимизация, которая просматривает готовый код через узкое «окошко» в несколько соседних команд и заменяет расточительные сочетания экономными: PUSH и сразу POP — ничем, прыжок на следующую строку — ничем. Глава 52 · Замкнуть круг

ориентированным

Граф, у рёбер которого есть направление: стрелка от одной вершины к другой. Пример: «эту главу читать перед той», «эта страница ссылается на ту». Глава 19 · Шесть рукопожатий

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

Ориентированный ациклический граф (DAG): граф со стрелками, в котором нельзя вернуться в вершину, идя по стрелкам. Зависимости задач, пакетов и глав курса — такие графы. Глава 19 · Шесть рукопожатий

особыми формами

Выражение языка, которое вычисляется по собственному правилу, а не по общему «вычислить все аргументы и вызвать функцию»: if, define, quote, lambda в Лиспе; if, def, and, or в Python. Глава 51 · Матрёшка

Остаточная сеть

Для сети и потока в ней — граф, где ребро u→v с числом r означает: из u в v можно дополнительно отправить r, либо по свободному месту ребра u→v, либо отменив часть потока по встречному ребру v→u. Глава 25 · Потоки и пары

остовным деревом

Дерево из рёбер графа, которое проходит через все его вершины: по нему можно добраться от любой вершины до любой, и циклов в нём нет. Глава 23 · Жадность и электричество

ответственное раскрытие

Ответственное (согласованное) раскрытие: порядок, при котором нашедший уязвимость сначала тайно сообщает владельцу и даёт время на починку (обычно до 90 дней), и только потом обнародует. Защищает пользователей, пока заплатки нет. Глава 61 · Учебный полигон

отказ-остановка

Отказ, при котором узел перестаёт работать: не отвечает и не шлёт сообщений, но и не врёт. После восстановления он может вернуться со своими сохранёнными данными. Глава 44 · Парламент острова Паксос

открытой адресацией

Способ разрешать коллизии без цепочек: в каждой ячейке хеш-таблицы не больше одной записи, а если ячейка занята, запись ищет свободную по заранее известному маршруту. Так устроены dict и set в CPython. Глава 16 · Хеш-таблица: атака и защита

открытый ключ

Половина пары ключей, которую публикуют: ею зашифровывают сообщения владельцу или проверяют его подписи. Для RSA это пара (n, e). Глава 60 · Секрет на виду у всех

открытым текстом

Сообщение в том виде, в каком его можно прочесть, — до шифрования или после расшифровки. Глава 59 · Шифровальный отдел

отложенная выборка

Примеры, которые не показывают модели при обучении и по которым один раз, в конце, проверяют её точность. Только она показывает, как модель будет работать на новых данных. Глава 63 · Машина учится

отложенным согласием

Алгоритм Гейла — Шепли: свободные участники одной стороны подают заявления по своим спискам, другая сторона держит лучшее из полученных и отказывает остальным, пока все не пристроены. Глава 25 · Потоки и пары

отпечатки

Малая выборка хешей шинглов документа, по которой можно найти общие куски с другими документами. Просеивание (winnowing) выбирает отпечатки так, что любой достаточно длинный общий кусок даёт хотя бы один общий отпечаток. Глава 27 · Иголка в стоге

отрицательным

Цикл во взвешенном графе с отрицательной суммой весов; если он достижим, кратчайших путей через него не существует. Глава 24 · Навигатор

оценочная функция

Оценочная функция: приближённая оценка незаконченной позиции числом (кто ближе к победе), когда досчитать до конца игры нельзя. Поиск останавливается на заданной глубине и берёт её значение вместо точного. Глава 62 · Турнир ботов

очередь

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

очередь сообщений

Способ связи потоков или процессов: отправитель кладёт сообщения в очередь, получатель забирает их в том же порядке; ожидание и блокировки спрятаны внутри очереди. Глава 39 · Гонки

очередью с приоритетом

Абстрактный тип данных: элементы с приоритетами; операции — добавить элемент и достать элемент с наивысшим приоритетом (обычно — с наименьшим ключом). Глава 18 · Кто следующий

пакетом

Порция данных с заголовком, в котором записано, куда и откуда она идёт. Сеть передаёт пакеты по отдельности: каждый узел принимает пакет целиком и отправляет дальше. Глава 41 · Один день из жизни пакета

Палиндром

Слово или фраза, которые читаются одинаково слева направо и справа налево, если не обращать внимания на пробелы, знаки и регистр. Глава 7 · Собеседник из строк

парадигмами

Общий взгляд на то, что такое программа и из чего она складывается: из команд, функций, фактов и правил, объектов или операций над массивами. Парадигма определяет почерк кода сильнее, чем синтаксис. Глава 49 · Музей языков

параметр

Имя в заголовке функции, под которым она получает входное значение: в def draw_square(size) это size. Глава 5 · Свои слова

паросочетании

Набор рёбер графа, у которых нет общих концов: каждая вершина входит не больше чем в одну пару. Глава 25 · Потоки и пары

паук

Программа поисковика, которая обходит веб: скачивает страницу, вынимает из неё ссылки и ставит их в очередь на скачивание. Так поисковик узнаёт о страницах. Глава 48 · Поисковик по нашим учебникам

первичный ключ

Столбец (или несколько столбцов), значение которого однозначно называет строку таблицы: двух строк с одинаковым первичным ключом база не допустит. Глава 45 · Архивариус

переключение контекста

Смена программы на ядре процессора: ядро ОС сохраняет регистры, счётчик команд и прочее состояние прерванного процесса и загружает сохранённое состояние следующего. Глава 37 · Центр управления полётом

перекос записи

Аномалия: две транзакции читают одни и те же данные, проверяют по ним общее правило и меняют разные записи; каждая по отдельности правило соблюдает, а вместе нарушают. Глава 46 · Библиотека и банк

переменной

Имя, привязанное к значению. В Python переменная — ярлык на объекте: одно и то же имя можно перевесить на другой объект. Глава 2 · Имена и значения

переменные окружения

Пара «имя = значение», которую процесс получает от родителя вместе с остальным окружением: PATH, HOME, LANG и другие. Дети получают копию; изменения в ребёнке родителя не касаются. Глава 36 · Экскурсия по живой системе

переобучение

Ситуация, когда модель хорошо отвечает на обучающих примерах и заметно хуже — на новых: она запомнила особенности примеров вместо закономерности. Глава 63 · Машина учится

переполнение

Ситуация, когда результат вычисления не помещается в отведённое ему число бит: машина либо заворачивает его по кругу, либо сообщает об ошибке. Глава 11 · Отчёт комиссии

Переполнение буфера

Переполнение буфера: запись за границу массива (буфера) в языке без проверки границ, из-за которой данные затирают соседнюю память — другие переменные, служебные поля, адрес возврата. Если данные приходят извне, их автор может выбирать, что именно затереть. Глава 61 · Учебный полигон

перестановки

Расстановка элементов в каком-то порядке; у n различных элементов n! перестановок. Глава 9 · Задача внутри задачи

перестановкой Барроуза — Уилера

Преобразование Барроуза — Уилера (1994): выписать все циклические сдвиги строки, отсортировать их и взять последние знаки. Получается перестановка той же строки, где одинаковые знаки стоят сериями; её можно обратить. На нём стоит bzip2. Глава 47 · Конкурс упаковки

Перцептрон

Простейшая обучаемая модель: взвешенная сумма входов плюс сдвиг, ответ — знак суммы. Учится правилом Розенблатта (1958): на каждой ошибке прибавляет к весам пример со знаком правильного ответа. Глава 63 · Машина учится

песочницей

Песочница (sandbox): ограниченное окружение, в котором чужой код выполняется без доступа к остальной системе — к сети, чужим файлам, лишним правам. Нарушение любой границы безопасно останавливается. Глава 61 · Учебный полигон

Пирамидальная сортировка

Сортировка: построить из массива кучу, затем n − 1 раз переставлять корень в конец и просеивать вниз. Время O(n log n) в худшем случае, дополнительная память O(1), неустойчива. Глава 18 · Кто следующий

планировщик

Часть операционной системы, которая решает, какой из готовых к работе процессов (или потоков) получит ядро процессора следующим и надолго ли. Глава 37 · Центр управления полётом

планировщиком

Часть базы данных, которая для каждого запроса перебирает способы его выполнить — полный просмотр, разные индексы, порядок соединений — оценивает их стоимость и выбирает самый дешёвый. Глава 46 · Библиотека и банк

планом запроса

Описание того, как база данных собирается выполнить запрос: какие таблицы читать целиком, где искать по индексу, в каком порядке соединять. В SQLite его показывает EXPLAIN QUERY PLAN. Глава 46 · Библиотека и банк

поворот

Перестройка трёх связей в дереве поиска: ребёнок узла поднимается на его место, а узел становится ребёнком; средняя ветка переходит от одного к другому. Порядок ключей сохраняется, высоты веток меняются на единицу. Глава 17 · Сад деревьев поиска

подклассы

Класс, унаследованный от другого: в записи class Fox(Animal) Fox — подкласс Animal. Экземпляр подкласса считается и экземпляром родителя: isinstance(fox, Animal) истинно. Глава 12 · Остров кроликов и лис

подпоследовательностью

Последовательность, которая получается из данной вычёркиванием элементов: порядок оставшихся сохраняется, но они не обязаны стоять подряд. В отличие от подстроки. Глава 22 · Запомнить, чтобы не считать

подстроку

Кусок строки, идущий подряд: «Kamchatsky» — подстрока строки «Petropavlovsk-Kamchatsky». Глава 7 · Собеседник из строк

подтверждением

Подтверждение (ACK, от acknowledgement) — ответ получателя: такой-то пакет или такие-то байты дошли. Нет подтверждения — отправитель повторяет. Глава 42 · Изобрести протокол

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

Поиск по дереву Монте-Карло (MCTS): вместо оценочной функции позицию оценивают множеством случайных доигрываний до конца (доля побед). Дерево растят в сторону многообещающих ходов, но пробуют и остальные. Основа силы AlphaGo в го. Глава 62 · Турнир ботов

поиском подстроки

Задача: найти все места, где короткая строка — образец — входит в длинную строку — текст. Наивное решение прикладывает образец к каждой позиции и тратит до n·m сравнений; КМП и Рабин — Карп укладываются в линейное время. Глава 27 · Иголка в стоге

показателем умножения матриц

Число ω: точная нижняя грань показателей a, при которых матрицы n×n можно перемножить за O(nᵃ) арифметических действий. Известно, что 2 ≤ ω < 2,371177 (2026); точное значение неизвестно. Глава 65 · Белые пятна

покрывающим

Индекс, в котором есть все столбцы, нужные запросу, так что базе не приходится обращаться к самой таблице. В плане SQLite — USING COVERING INDEX. Глава 46 · Библиотека и банк

покрытие множествами

Задача: дано множество элементов и набор его подмножеств; выбрать как можно меньше подмножеств, чтобы они вместе содержали все элементы. NP-трудна; жадный алгоритм ошибается не больше чем примерно в ln n раз. Глава 58 · Экспедиция коммивояжёра

полиморфизмом

Свойство кода работать с объектами разных классов одинаково: animal.step(island) у кролика и у лисы вызывает разные методы, а вызывающему всё равно, кто перед ним. Глава 12 · Остров кроликов и лис

полиномиальное время

Число шагов алгоритма на входе длины n не больше C·nᵏ для каких-то постоянных C и k: n, n log n, n², n³… Экспонента 2ⁿ и факториал n! — не полиномы. Глава 57 · Письмо Гёделя

полиномиальное сведение

Переделка входов задачи A во входы задачи B за полиномиальное время, при которой ответ «да» переходит в «да», а «нет» — в «нет». Если A сводится к B и B решается быстро, то и A решается быстро. Глава 57 · Письмо Гёделя

полной по Тьюрингу

Свойство языка, машины или системы правил: на ней можно выполнить любую машину Тьюринга, а значит, по тезису Чёрча — Тьюринга, любое вычисление, если хватит памяти и времени. Python, C, Brainfuck, λ-исчисление и игра «Жизнь» полны по Тьюрингу, конечные автоматы и регулярные выражения — нет. Глава 55 · Машина Тьюринга

полным

Двоичное дерево, все этажи которого заполнены, кроме, может быть, последнего, а последний заполнен слева направо без пропусков. Его удобно хранить в массиве. Глава 18 · Кто следующий

полным перебором

Атака на шифр, при которой пробуют все возможные ключи подряд. Защита от неё — такое количество ключей, что перебор не закончится за разумное время. Глава 59 · Шифровальный отдел

полным просмотром

Способ выполнить запрос, при котором база читает все строки таблицы подряд и проверяет условие для каждой. Стоит O(n); в плане SQLite называется SCAN. Глава 46 · Библиотека и банк

полным сумматором

Схема, складывающая три бита — два разряда чисел и перенос из младшего разряда — и выдающая бит суммы и бит переноса в старший разряд. Глава 29 · Логика из выключателей

полусумматором

Схема, складывающая два бита: выдаёт бит суммы (a XOR b) и бит переноса (a И b). Глава 29 · Логика из выключателей

полуходом

Полуход (ply): один ход одного игрока. Глубина поиска в играх меряется в полуходах: «на четыре полухода вперёд» — я, соперник, я, соперник. Глава 62 · Турнир ботов

пользовательском режиме

Режим процессора, в котором работают обычные программы: им запрещены команды, управляющие железом, и доступна только своя память. Всё остальное программа просит у ядра. Глава 36 · Экскурсия по живой системе

поразрядная сортировка

Сортировка чисел (или строк) по цифрам: несколько проходов устойчивой раскладки по карманам, от младшей цифры к старшей. Время — число цифр × (n + основание), без единого сравнения. Глава 20 · Турнир сортировок

порт

Номер от 0 до 65535 в транспортном заголовке (UDP, TCP): по нему ядро решает, какой программе на машине отдать пакет. Программа «слушает» порт, привязав к нему сокет. Глава 41 · Один день из жизни пакета

постепенной типизацией

Типизация, при которой статические типы можно добавлять в программу постепенно: размеченные части проверяются до запуска, неразмеченные — только во время выполнения. Так устроены Python с mypy и TypeScript. Глава 53 · Суд над null

Постквантовая криптография

Криптография на задачах, для которых не известно быстрых алгоритмов и на квантовом компьютере: решётки, хеш-функции, коды. Первые стандарты NIST — 2024 год. Глава 60 · Секрет на виду у всех

постоянная память

Постоянная память, ПЗУ (ROM, read-only memory): содержимое задаётся при изготовлении и только читается; не стирается без питания. Глава 31 · Память и такт

построением подмножеств

Построение ДКА по НКА (Рабин и Скотт, 1959): состояние ДКА — множество состояний, в которых может быть НКА; переходы вычисляются обходом в ширину от начального множества. В худшем случае состояний 2 в степени n. Глава 54 · Автоматы и регулярки

потерянное обновление

Аномалия одновременной работы: две транзакции читают одно значение, каждая записывает своё, и изменение той, что записала раньше, пропадает. Глава 46 · Библиотека и банк

Поток

Числа f(u, v) на рёбрах сети, которые не больше пропускных способностей и для каждой вершины, кроме истока и стока, сколько втекает, столько и вытекает. Глава 25 · Потоки и пары

потоком

Нить исполнения внутри процесса: свой счётчик команд, свои регистры и свой стек вызовов, а память, глобальные переменные и открытые файлы — общие со всеми потоками того же процесса. Глава 39 · Гонки

прав доступа

Девять битов у каждого файла в Unix: чтение (r), запись (w) и исполнение (x) — для хозяина, для группы и для всех остальных. Ядро сверяет их с пользователем процесса при каждом открытии файла. Глава 36 · Экскурсия по живой системе

предподсчёт

Работа, которую алгоритм делает один раз заранее, чтобы потом быстро отвечать на много запросов: таблицы, индексы, сокращения в графе. Глава 24 · Навигатор

предсказателем переходов

Часть процессора, которая до того, как условный переход исполнен, угадывает, прыгнет ли он, — чтобы конвейер не простаивал. Угадывает по тому, как этот и соседние переходы вели себя раньше. Глава 35 · Конвейер и предсказатель

Представление

Запись значения так, как его пишут в коде Python: repr('a\nb') — это строка 'a\\nb' вместе с кавычками. Глава 7 · Собеседник из строк

прерывание

Сигнал процессору от таймера или устройства: процессор откладывает текущую программу, запоминает, где остановился, и выполняет обработчик в ядре операционной системы. Глава 37 · Центр управления полётом

префикс-функцию

Для строки p — список π, где π[i] — длина самой длинной грани начала p[:i + 1]. Считается за линейное время и подсказывает алгоритму КМП, куда сдвигать образец после несовпадения. Глава 27 · Иголка в стоге

префиксным

Код, в котором ни одно кодовое слово не служит началом другого; поэтому сообщение читается однозначно без разделителей. Глава 23 · Жадность и электричество

приближённый алгоритм

Алгоритм для трудной задачи оптимизации, который работает за полиномиальное время и гарантирует, что ответ хуже оптимума не больше чем в заданное число раз — коэффициент приближения. Глава 58 · Экспедиция коммивояжёра

Принцип Керкгоффса

Правило Огюста Керкгоффса (1883): стойкость шифра не должна зависеть от секретности его устройства. Противник знает систему; тайной остаётся только ключ. Глава 59 · Шифровальный отдел

принцип наименьших привилегий

Принцип наименьших привилегий: каждая часть системы работает с минимальными правами, нужными для её задачи, и не больше. Тогда ошибка или взлом одной части наносит минимальный урон. Глава 61 · Учебный полигон

приоритет

Правило, какая операция в выражении без скобок выполняется раньше: умножение старше сложения, поэтому 2 + 3 * 4 = 14. В грамматике задаётся уровнями: каждая ступень старшинства — свой нетерминал. Глава 50 · Лингвист в экспедиции

присваиванием

Команда «имя = выражение»: вычислить выражение справа и привязать к результату имя слева. Знак = в Python — не равенство. Глава 2 · Имена и значения

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

Вопрос: по тексту программы P и её входу x определить, закончит ли P работу на x за конечное число шагов. Тьюринг (1936) доказал, что никакой алгоритм не решает его для всех P и x. Глава 56 · Разговор с Оракулом

проброс

Приём против конфликтов по данным: результат, только что вычисленный АЛУ, подаётся прямо на вход следующей команды, не дожидаясь, пока его запишут в регистр. Глава 35 · Конвейер и предсказатель

пробуксовка

Состояние, когда процессам не хватает памяти на их рабочие наборы и система почти всё время переносит страницы между памятью и диском, почти не делая полезной работы. Глава 38 · Гостиница с номерами

проверкой типов

Программа, которая по тексту другой программы, не запуская её, проверяет, что ни одна операция не получит значение неподходящего типа. Встроена в компиляторы C, Java, Rust; для Python это отдельная программа, например mypy. Глава 53 · Суд над null

программирование массивами

Парадигма программирования, в которой операции применяются сразу к целым массивам, без явных циклов: x + 1 прибавляет единицу к каждому элементу. APL, J, MATLAB, numpy. Глава 49 · Музей языков

произведением пропускной способности на задержку

Произведение пропускной способности канала на время туда и обратно: сколько данных должно быть в пути одновременно, чтобы канал не простаивал. Такое окно нужно отправителю. Глава 42 · Изобрести протокол

промах

Обращение к памяти, которое не нашло данных в кэше: их приходится везти с более медленной ступеньки. Обратный случай — попадание. Глава 34 · Близко и далеко

промежуточное представление

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

пропускная способность

Пропускная способность ребра в сети потоков — число c(u, v): больше этого по ребру провезти нельзя. Глава 25 · Потоки и пары

пропускная способность

Пропускная способность канала — сколько данных он передаёт за секунду, обычно в битах в секунду (бит/с, Мбит/с, Гбит/с). Не путать с задержкой — временем, за которое доходит первый бит. Глава 41 · Один день из жизни пакета

просеивание

Восстановление свойства кучи после изменения одного элемента: элемент меняется местами с родителем (просеивание вверх) или с меньшим из детей (просеивание вниз), пока не встанет на место. Глава 18 · Кто следующий

просеиванием

Способ выбрать отпечатки документа: в каждом окне из w подряд идущих хешей шинглов оставить наименьший. Любой общий кусок из w + k − 1 слов гарантированно даёт общий отпечаток. На нём работает MOSS. Глава 27 · Иголка в стоге

протоколом

Договор о формате и порядке сообщений между участниками обмена: какие поля в каком порядке, что отвечать и что делать, если что-то пошло не так. Глава 41 · Один день из жизни пакета

профилировщик

Программа, которая следит за работой другой программы и показывает, сколько времени ушло на каждую функцию: где «горит». Глава 13 · Сколько стоит программа

процесс

Программа во время работы: её код, своя память, регистры, открытые файлы и номер (PID). Одну программу можно запустить несколькими процессами сразу. Глава 36 · Экскурсия по живой системе

процессором

Устройство, которое по кругу выбирает из памяти команды и исполняет их. Состоит из блока управления, АЛУ и регистров. Глава 32 · Ты — процессор

рабочим набором

Страницы, к которым процесс обращался за последнее время. Если рабочие наборы всех процессов помещаются в память, промахов мало; если нет — начинается пробуксовка. Глава 38 · Гостиница с номерами

разбиение

Шаг быстрой сортировки: переставить элементы так, чтобы меньшие опорного оказались слева, а большие — справа. Глава 21 · Разделяй и властвуй

разделение времени

Способ работы компьютера, при котором процессор быстро переключается между программами многих пользователей, отдавая каждой короткие кванты времени, так что каждый видит машину, отвечающую ему одному. Глава 37 · Центр управления полётом

разделение сети

Разрыв сети, после которого узлы делятся на группы: внутри группы сообщения ходят, между группами — нет. Каждая группа видит другую как отказавшую. Глава 44 · Парламент острова Паксос

разрезом

Разбиение вершин графа на две непустые группы; рёбра разреза — те, что соединяют вершины из разных групп. Глава 23 · Жадность и электричество

разрешимой

Задача с ответом «да» или «нет» разрешима, если существует программа, которая на любом входе останавливается и выдаёт правильный ответ. Если такой программы нет, задача неразрешима. Глава 56 · Разговор с Оракулом

распределение регистров

Этап компилятора, который решает, какие значения держать в регистрах процессора, а какие — в памяти. Регистров мало, поэтому значения, нужные в одно и то же время, должны получить разные регистры; задачу часто сводят к раскраске графа. Глава 52 · Замкнуть круг

распределённая система

Несколько компьютеров, которые общаются только сообщениями по сети и вместе делают одно дело. У них нет общей памяти и общих часов, и каждый может отказать отдельно от других. Глава 44 · Парламент острова Паксос

Расстояние редактирования

Наименьшее число вставок, удалений и замен символов, которыми одна строка превращается в другую. Расстояние Левенштейна; считается таблицей за время, пропорциональное произведению длин строк. Глава 22 · Запомнить, чтобы не считать

рёбрами

Связь двух вершин графа. Ребро без направления идёт в обе стороны; ориентированное ребро (дуга) — только от одной вершины к другой. Глава 19 · Шесть рукопожатий

регистр

Несколько триггеров с общим тактовым сигналом, хранящих одно число. В процессоре регистры — самая быстрая память, из них АЛУ берёт операнды и в них пишет результат. Глава 31 · Память и такт

регулярными

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

регулярными выражениями

Формула, описывающая множество строк: символы, «или» (|), повторение (*) и группировка; в практических языках к ним добавлены классы [a-z], повторы {n,m}, якоря и многое другое. Модуль re в Python. Глава 54 · Автоматы и регулярки

резолвером

Сервер (или программа), который находит адрес по имени: спрашивает корень DNS, затем серверы доменов всё ниже по дереву и запоминает ответы на срок их жизни. Глава 43 · Анатомия этой страницы

рекуррентному соотношению

Уравнение, которое выражает значение функции через её значения на меньших аргументах, например T(n) = 2T(n/2) + n. Глава 21 · Разделяй и властвуй

рекурсивный спуск

Способ разбора, при котором каждому нетерминалу грамматики соответствует функция: она смотрит на очередной токен, выбирает правило и вызывает функции для его частей. Дерево строится сверху вниз, а вложенность скобок — это глубина рекурсии. Глава 50 · Лингвист в экспедиции

рекурсией

Приём, при котором функция решает задачу, вызывая саму себя на задаче того же вида, но меньшего размера. Глава 9 · Задача внутри задачи

релаксацией

Проверка ребра u → v в поиске кратчайших путей: если dist[u] + w(u, v) меньше dist[v], оценка dist[v] уменьшается до этой суммы. Глава 24 · Навигатор

реле

Выключатель, которым управляет электромагнит: ток в катушке притягивает железный якорь, и тот замыкает или размыкает контакты другой цепи. Глава 29 · Логика из выключателей

реплика

Копия данных на одном из серверов распределённой системы. Копии хранят, чтобы данные пережили отказ любой машины; трудность — держать их одинаковыми. Глава 44 · Парламент острова Паксос

репликация конечного автомата

Способ сделать надёжный сервис из ненадёжных машин: каждая реплика выполняет одни и те же команды в одном и том же порядке, записанном в общем журнале, и потому приходит в одно и то же состояние. Глава 44 · Парламент острова Паксос

решёнными

Решённая игра: для неё известен исход при идеальной игре обеих сторон (выигрыш первого, второго или ничья), а часто и сама идеальная стратегия. Крестики-нолики — ничья; шашки — ничья; «Четыре в ряд» — выигрыш первого. Глава 62 · Турнир ботов

самокомпилирующимся

Компилятор, написанный на том самом языке, который он компилирует: компилятор C на C, Go на Go. Первую версию приходится собирать другим компилятором или интерпретатором — это называют раскруткой (bootstrapping). Глава 52 · Замкнуть круг

сборщик мусора

Часть языка, которая сама находит и освобождает объекты, недостижимые из программы. В CPython он дополняет счётчик ссылок и ищет петли объектов, которые держат друг друга. Глава 38 · Гостиница с номерами

сведением

Способ решить задачу A с помощью решателя задачи B: каждый вход A переводится в вход B с тем же ответом. Если A сводится к B и A неразрешима, то неразрешима и B. Глава 56 · Разговор с Оракулом

свёртка констант

Оптимизация: выражения, все операнды которых известны при компиляции (2 * 4, 8 - 1), компилятор вычисляет сам и подставляет результат, чтобы программа не считала их при каждом выполнении. Глава 52 · Замкнуть круг

свёрткой

Сведение последовательности к одному значению: функция двух аргументов по очереди подмешивает каждый элемент к накопителю; в Python — functools.reduce. Глава 10 · Функции как значения

свидетелем

Число a, по которому быстро проверяется, что n составное (в тесте Ферма или Миллера — Рабина). Глава 26 · Подбросим монетку

связным списком

Цепочка узлов, в которой каждый узел хранит значение и ссылку на следующий. Вставка и удаление рядом с известным узлом стоят O(1), доступ по номеру — O(n). Глава 14 · Как список лежит в памяти

Сдвиг

Операция, которая переносит все биты числа на одну или несколько позиций влево или вправо; сдвиг влево на один разряд умножает число на 2, вправо — делит нацело на 2. Глава 30 · Машина считает

Семантика

Смысл правильно записанной программы: что она делает при выполнении. Одинаковый по виду текст в разных языках может иметь разную семантику, а разный — одинаковую. Глава 49 · Музей языков

Семафор

Счётчик с двумя неделимыми операциями: P (acquire) уменьшает его на единицу, а если он равен нулю — ждёт; V (release) увеличивает и будит ждущего. Семафор на n пропускает в участок кода не больше n потоков сразу. Глава 39 · Гонки

сертификатом

Короткая подсказка, которая подтверждает ответ «да» в задаче распознавания: рассадка, заполненная доска, выполняющий набор, делитель числа. Её длина полиномиальна от входа, а проверка полиномиальна по времени. Глава 57 · Письмо Гёделя

сертификатом

Документ, в котором удостоверяющий центр своей подписью связывает имя (например, адрес сайта) с открытым ключом. Браузер проверяет цепочку подписей до корневого центра, ключ которого встроен в систему. Глава 60 · Секрет на виду у всех

Сеть

Ориентированный граф с двумя выделенными вершинами — истоком s и стоком t, — у каждого ребра которого есть пропускная способность: сколько по нему можно провезти. Глава 25 · Потоки и пары

сеть доставки содержимого

Content Delivery Network, сеть доставки содержимого: серверы по всему миру хранят копии файлов сайта и отдают их тем, кто рядом, чтобы запросу не нужно было идти до исходного сервера. Глава 34 · Близко и далеко

Сжатие

Запись данных меньшим числом битов. После сжатия без потерь исходные данные восстанавливаются в точности (ZIP, PNG), после сжатия с потерями — только приблизительно (JPEG, MP3). Глава 47 · Конкурс упаковки

сжатие с потерями

Сжатие, после которого распаковка возвращает данные лишь приблизительно: выбрасывается то, чего не заметит глаз или ухо. JPEG, MP3, видео. Глава 47 · Конкурс упаковки

сжатия без потерь

Сжатие, после которого распаковка возвращает исходные данные бит в бит. Так сжимают тексты, программы, таблицы: ZIP, gzip, PNG, bzip2. Глава 47 · Конкурс упаковки

симметричными

Шифр, в котором отправитель и получатель пользуются одним и тем же секретным ключом. Все шифры от Цезаря до AES — симметричные. Глава 59 · Шифровальный отдел

Синтаксис

Правила, по которым из символов складываются правильные программы языка: какие слова и знаки где могут стоять. Нарушение синтаксиса обнаруживается до запуска: в Python это SyntaxError. Глава 49 · Музей языков

система непересекающихся множеств

Структура данных для разбиения элементов на группы: find(x) находит представителя группы x, union(a, b) сливает две группы. С подвешиванием меньшей группы к большей и сжатием путей обе операции почти константны. Глава 23 · Жадность и электричество

системами реального времени

Система, в которой результат должен быть получен к заданному сроку: опоздавший результат считается ошибкой. Жёсткое реальное время — опоздание недопустимо никогда, мягкое — изредка допустимо. Глава 37 · Центр управления полётом

системным вызовом

Просьба программы к ядру операционной системы: открыть файл, прочитать байты, создать процесс, выделить память. Выполняется особой командой процессора, которая переключает его в режим ядра. Глава 36 · Экскурсия по живой системе

системой команд

Полный список команд, которые понимает процессор, вместе с правилами их записи в байтах. Глава 32 · Ты — процессор

системой типов

Правила, по которым каждому выражению программы приписывается тип и проверяется, что типы сходятся. Система типов определяет, какие ошибки язык обещает найти до запуска. Глава 53 · Суд над null

скользящее окно

Скользящее окно: отправитель держит в пути до W неподтверждённых пакетов; подтверждение первого из них сдвигает окно вперёд и разрешает отправить следующий. Так канал не простаивает, пока идут подтверждения. Глава 42 · Изобрести протокол

скользящим

Хеш окна фиксированной длины, который при сдвиге окна на один символ пересчитывается за O(1): вычесть вклад ушедшего символа, умножить на основание, прибавить пришедший. Основа алгоритма Рабина — Карпа и отпечатков документов. Глава 27 · Иголка в стоге

слабой типизацией

Свойство языка молча преобразовывать значения неподходящего типа вместо ошибки: в JavaScript "5" * 3 даёт 15, в C дробь, переданная туда, где ждут целое, обрезается. Противоположность — строгая типизация; граница между ними размыта. Глава 49 · Музей языков

словарём

Структура данных из пар «ключ — значение»: по ключу сразу находится значение, например code["о"] → "---". Глава 8 · Словарь и телеграф

сложностью

Как растёт работа алгоритма — число шагов или время — с размером входа n: линейно, квадратично, экспоненциально. Глава 13 · Сколько стоит программа

случилось раньше

Отношение между событиями распределённой системы: a → b, если a и b произошли на одном узле и a раньше, или a — отправка сообщения, а b — его получение, или есть цепочка таких шагов. Если ни a → b, ни b → a, события параллельны. Глава 44 · Парламент острова Паксос

событийное моделирование

Способ моделировать систему, перескакивая от события к событию: будущие события лежат в очереди с приоритетом по времени, программа достаёт ближайшее, обрабатывает его и добавляет новые. Глава 18 · Кто следующий

совершенной секретностью

Свойство шифра: шифровка не несёт никакой информации о сообщении, кроме длины; вероятность каждого сообщения после перехвата та же, что до него. Доказано Шенноном для одноразового блокнота. Глава 59 · Шифровальный отдел

согласованностью в конечном счёте

Гарантия, что если новых изменений больше нет, то все копии данных со временем станут одинаковыми. В любой момент разные копии могут отвечать по-разному. Глава 44 · Парламент острова Паксос

соглашение о вызовах

Договор о том, как функции передают друг другу аргументы и ответ: в каких регистрах и в каком порядке, что лежит на стеке, какие регистры вызванная функция обязана сохранить. Глава 33 · Рентген Python

соединение

Операция над двумя таблицами: каждая строка первой склеивается с теми строками второй, для которых выполняется условие ON. LEFT JOIN оставляет и строки первой таблицы без пары, заполняя недостающее значениями NULL. Глава 45 · Архивариус

сокет

Сокет — точка, через которую программа обменивается данными по сети: ядро выдаёт его как файловый дескриптор, а программа пишет в него и читает из него. У сокета есть адрес машины и номер порта. Глава 41 · Один день из жизни пакета

солью

Случайное секретное значение, от которого зависит хеш-функция. Его выбирают заново, например, при каждом запуске программы, чтобы противник не мог заранее подобрать ключи с одинаковым хешем. Глава 16 · Хеш-таблица: атака и защита

сопоставлением с образцом

Разбор значения по образцам: оператор проверяет, какому из вариантов значение соответствует, и сразу связывает его части с именами. match в Python, case в Haskell и OCaml, match в Rust. Глава 53 · Суд над null

сопрограммой

Функция, которая может приостановиться посередине, отдать управление и потом продолжить с того же места. В Python — генераторы и функции async def. Глава 37 · Центр управления полётом

сортировка вставками

Сортировка: элементы берут по одному и вставляют на место в уже упорядоченную левую часть, сдвигая большие вправо. От n − 1 до n(n − 1)/2 сравнений — смотря насколько перемешаны данные. Глава 20 · Турнир сортировок

сортировка выбором

Сортировка: найти наименьший элемент и поставить его первым, затем наименьший из оставшихся — вторым, и так далее. Всегда n(n − 1)/2 сравнений и не больше n − 1 обменов. Глава 20 · Турнир сортировок

сортировка подсчётом

Сортировка без сравнений для небольшого набора возможных значений: посчитать, сколько раз встретилось каждое, и выписать их по порядку. Время n + k, где k — число возможных значений. Глава 20 · Турнир сортировок

сортировками сравнениями

Сортировка, которая узнаёт о данных только из сравнений пар элементов. Выбор, вставки, пузырёк, слияние, быстрая, пирамидальная, Timsort — сортировки сравнениями. Глава 20 · Турнир сортировок

состояний Белла

Четыре максимально запутанных состояния двух кубитов: (|00⟩ ± |11⟩)/√2 и (|01⟩ ± |10⟩)/√2. Первое получается из |00⟩ гейтом H на первый кубит и CNOT. Глава 64 · Лаборатория кубитов

социальной инженерией

Социальная инженерия: получение доступа обманом человека, а не взломом техники, — поддельное письмо, звонок от «службы поддержки», просьба «срочно» сообщить код. Защищают от неё правила и привычка проверять. Глава 61 · Учебный полигон

спекулятивным исполнением

Исполнение команд до того, как стало известно, нужны ли они: процессор идёт по угаданной ветке, а результаты держит начерно и отменяет, если догадка не подтвердилась. Глава 35 · Конвейер и предсказатель

специальные

Метод с именем вида __имя__, который Python вызывает сам: __init__ при создании объекта, __repr__ и __str__ при показе, __eq__ при сравнении ==, __add__ при сложении +. Глава 12 · Остров кроликов и лис

списками смежности

Способ хранить граф: для каждой вершины — список её соседей. На Python — словарь, где ключ — вершина, значение — список. Занимает память, пропорциональную числу вершин и рёбер. Глава 19 · Шесть рукопожатий

списком вхождений

Список документов (номеров страниц), в которых встречается слово, — одна строка обратного индекса. Хранится отсортированным, чтобы списки быстро пересекались. Глава 48 · Поисковик по нашим учебникам

список

Упорядоченный набор значений под одним именем: [5.4, 5.1, 6.6]. Элементы нумеруются с нуля, список можно менять: добавлять, удалять, переставлять. Глава 6 · Списки

Средний случай

Время работы алгоритма, усреднённое по входам размера n при каком-то предположении о том, как эти входы распределены, например «все перестановки равновероятны». Глава 13 · Сколько стоит программа

срез

Кусок списка или строки: a[начало:конец:шаг]. Конец не включается; результат — новый список. Глава 6 · Списки

сроки

В Raft — пронумерованный отрезок времени, в начале которого проходят выборы. В каждом сроке не больше одного председателя; узел, увидевший больший номер срока, сразу признаёт его и становится рядовым. Глава 44 · Парламент острова Паксос

ссылка

Значение, которое указывает на объект, — в CPython это адрес объекта в памяти. Список хранит ссылки на элементы, а не сами элементы. Глава 14 · Как список лежит в памяти

стандартный ввод

Три файловых дескриптора, открытые у каждого процесса с рождения: 0 — стандартный ввод (stdin), 1 — стандартный вывод (stdout), 2 — вывод ошибок (stderr). Программа читает и пишет в них, не зная, куда они подключены. Глава 36 · Экскурсия по живой системе

старением

Способ бороться с голоданием: приоритет задачи постепенно растёт, пока она ждёт, так что любая задача рано или поздно получит процессор. Глава 37 · Центр управления полётом

статистику

Сведения о данных, по которым планировщик оценивает стоимость способов выполнить запрос: сколько строк в таблице, сколько в среднем строк на одно значение столбца индекса. В SQLite их собирает ANALYZE в таблицу sqlite_stat1. Глава 46 · Библиотека и банк

статической типизации

Проверка типов до запуска программы, по её тексту: у каждой переменной и функции известен тип, и программа с несовпадением типов не собирается. C, Java, Haskell, Rust. Глава 49 · Музей языков

стеком

Структура данных, в которой добавляют и забирают с одного конца — вершины: последним положили, первым забрали (LIFO). Операции push, pop и peek стоят O(1). Глава 15 · Стек, очередь и калькулятор

стеком вызовов

Стопка кадров вызовов, которые начались и ещё не закончились: новый вызов кладёт кадр сверху, возврат его снимает. Глава 5 · Свои слова

стеком протоколов

Набор протоколов, сложенных уровнями: каждый уровень решает одну задачу, пользуется услугами нижнего и служит верхнему. В интернете уровней пять: физический, канальный, сетевой, транспортный и прикладной. Глава 41 · Один день из жизни пакета

стеммером

Программа, которая приводит слово к основе, отрезая окончания по правилам: «сортировкой» → «сортировк». Быстро и без словаря, но ошибается на беглых гласных, чередованиях и омонимах. Глава 48 · Поисковик по нашим учебникам

степенной метод

Способ найти главный собственный вектор матрицы: много раз умножать на неё вектор и смотреть, к чему он сходится. Так считают PageRank. Глава 48 · Поисковик по нашим учебникам

сторожевым таймером

Сторожевой таймер: механизм, который ждёт от программы регулярного знака «я жива» и, не дождавшись к сроку, перезапускает её или весь компьютер. Глава 39 · Гонки

страницы

Кусок адресного пространства фиксированного размера (обычно 4 КиБ); единица, которой виртуальная память переводит адреса, защищает и переселяет данные. Глава 38 · Гостиница с номерами

страничное прерывание

Прерывание, которое процессор поднимает, когда страницы, к которой обратилась программа, нет в памяти (или к ней нельзя так обращаться). Ядро ОС приносит страницу — с диска или выдаёт новую, — правит таблицу и повторяет команду. Глава 38 · Гостиница с номерами

строка документации

Строка в тройных кавычках сразу под заголовком функции: что функция делает, что принимает и что возвращает; её показывает help(). Глава 5 · Свои слова

строкой

Значение-текст: последовательность символов в кавычках, например "Привет". Глава 1 · Первая программа и первая ошибка

строкой кэша

Порция, которой данные переезжают между памятью и кэшем: обычно 64 байта подряд (у процессоров Apple — 128). Прочитав один байт, процессор получает в кэш всю его строку. Глава 34 · Близко и далеко

сужением типа

Уточнение типа переменной после проверки в самой программе: после if x is None: return проверка типов считает переменную типа str | None строкой, str. Так же сужают isinstance, сравнения и match. Глава 53 · Суд над null

сумматором с последовательным переносом

Многоразрядный сумматор из цепочки полных сумматоров, где перенос из каждого разряда идёт на вход следующего; прост, но медленен: перенос может пробежать через все разряды. Глава 30 · Машина считает

суперпозиции

Состояние квантовой системы, в котором ненулевые амплитуды есть у нескольких базисных состояний сразу, например (|0⟩ + |1⟩)/√2. Глава 64 · Лаборатория кубитов

суффиксный массив

Список начальных позиций всех суффиксов строки, упорядоченный по алфавиту суффиксов. Позволяет найти любой образец двоичным поиском за O(m log n) и находить повторы по общим началам соседей. Глава 27 · Иголка в стоге

сферой Блоха

Изображение состояний одного кубита точками единичной сферы: cos(θ/2)|0⟩ + e^{iφ} sin(θ/2)|1⟩ — точка с широтой θ от северного полюса и долготой φ. Гейты поворачивают сферу. Глава 64 · Лаборатория кубитов

схемой

Описание базы данных: какие в ней таблицы, какие у них столбцы и типы, какие ключи и как таблицы ссылаются друг на друга. Глава 45 · Архивариус

счётчик

Регистр, который на каждом такте прибавляет к своему значению единицу (или вычитает её); по кругу: после наибольшего числа снова 0. Глава 31 · Память и такт

счётчик команд

Регистр процессора, в котором лежит адрес следующей команды. После выборки команды увеличивается на её длину; команда перехода записывает в него новый адрес. Глава 32 · Ты — процессор

счётчик ссылок

Способ освобождать память: у каждого объекта хранится число ссылок на него; новая ссылка прибавляет единицу, исчезнувшая — отнимает, и объект освобождается, как только счётчик падает до нуля. Так работает CPython. Глава 38 · Гостиница с номерами

таблица маршрутизации

Таблица маршрутизатора: строки вида «префикс адреса → куда отправить». Для каждого пакета выбирается строка с самым длинным подходящим префиксом. Глава 41 · Один день из жизни пакета

таблица страниц

Таблица, которую ядро ОС ведёт для каждого процесса: для каждой страницы — в каком кадре она лежит (или что её нет в памяти) и что с ней можно делать. MMU читает её при переводе адресов. Глава 38 · Гостиница с номерами

таблицах

Основная единица хранения в реляционной базе данных: набор строк с одинаковыми именованными столбцами. У каждого столбца свой тип. Порядок строк в таблице не определён. Глава 45 · Архивариус

таблицей истинности

Таблица, в которой для каждого сочетания значений True и False у переменных записано значение логического выражения. Глава 3 · Развилки

таймаутом повтора

Таймаут повтора: сколько отправитель ждёт подтверждения, прежде чем решить, что пакет или подтверждение потерялись, и отправить пакет снова. Глава 42 · Изобрести протокол

тактовым

Сигнал-метроном, который равномерно перескакивает между 0 и 1; по его фронтам все триггеры машины одновременно принимают новые значения. Один его период — такт. Глава 31 · Память и такт

тезисом Чёрча — Тьюринга

Утверждение: всякая функция, которую можно вычислить механической процедурой (алгоритмом), вычислима машиной Тьюринга. Это не теорема, а соглашение о смысле слова «алгоритм», подтверждённое тем, что все предложенные модели вычислений оказались равносильны. Глава 55 · Машина Тьюринга

теоремой CAP

Теорема Брюера (доказана Гилбертом и Линч в 2002 году): при разделении сети распределённая система должна выбрать — отвечать на запросы (доступность) или гарантировать, что ответы согласованы (согласованность); получить оба свойства нельзя. Глава 44 · Парламент острова Паксос

типов

Вид значения, от которого зависит, что с ним можно делать: int — целое число, float — дробное, str — строка, bool — истина или ложь. Узнать тип можно функцией type(). Глава 2 · Имена и значения

токены

Неделимое «слово» программы для разборщика: число, имя, знак операции, скобка, строка. У токена есть вид (NUM, NAME, OP…) и значение. Глава 50 · Лингвист в экспедиции

топологической сортировкой

Расстановка вершин ориентированного графа в ряд так, что каждая стрелка ведёт слева направо: всё, от чего вершина зависит, стоит раньше неё. Существует тогда и только тогда, когда в графе нет циклов. Глава 19 · Шесть рукопожатий

транзакцией

Группа операций с базой данных, которая выполняется как одно целое: либо все её изменения вступают в силу (COMMIT), либо ни одно (ROLLBACK). Другие пользователи базы не видят её промежуточных состояний. Глава 46 · Библиотека и банк

транзистор

Полупроводниковый выключатель без движущихся частей: напряжение на управляющем выводе (затворе) открывает или закрывает путь току между двумя другими выводами. Глава 29 · Логика из выключателей

трейсбек

Отчёт об ошибке, который Python печатает, когда программа падает: где она остановилась и почему. Глава 1 · Первая программа и первая ошибка

трёхзначной логики

Логика с тремя значениями: истина, ложь и неизвестно. В SQL любое сравнение с NULL даёт «неизвестно», а WHERE пропускает только истинные строки. Глава 45 · Архивариус

тройное рукопожатие

Тройное рукопожатие — начало соединения TCP: клиент отправляет SYN, сервер отвечает SYN-ACK, клиент — ACK. Стороны договариваются о начальных номерах и убеждаются, что связь работает в обе стороны. Глава 42 · Изобрести протокол

Увеличивающий путь

Путь из истока в сток в остаточной сети. Если пустить по нему столько, сколько пропускает его самое узкое ребро, поток вырастет. Глава 25 · Потоки и пары

узел

Элемент связной структуры данных: объект, который хранит значение и ссылки на соседние узлы. Глава 14 · Как список лежит в памяти

указателем

Переменная, значение которой — адрес другого значения в памяти. В C: &x — адрес x, *p — то, что лежит по адресу p, p + 1 — адрес следующего элемента того же типа. Глава 33 · Рентген Python

универсальной машиной

Машина Тьюринга, которая получает на ленте описание любой другой машины и её вход и выполняет эту машину. Описал Тьюринг в 1936 году; это идея программы, хранимой вместе с данными. Глава 55 · Машина Тьюринга

унификацией

Решение системы уравнений на типы (или на выражения с неизвестными): найти подстановку, после которой обе части каждого уравнения совпадают. Основа вывода типов Хиндли — Милнера и языка Пролог. Глава 53 · Суд над null

управление потоком

Управление потоком: получатель сообщает отправителю, сколько свободного места у него в буфере, и отправитель не отправляет больше. Защищает медленного получателя от быстрого отправителя. Глава 42 · Изобрести протокол

уровнем изоляции

Настройка базы данных: от каких аномалий одновременной работы защищены транзакции. Стандарт SQL называет четыре уровня: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ, SERIALIZABLE. Глава 46 · Библиотека и банк

усердного бобра

BB(n) — наибольшее число шагов, которое делает перед остановкой машина Тьюринга с n состояниями и символами 0 и 1, запущенная на пустой ленте. Функцию ввёл Тибор Радо (1962); она невычислима и растёт быстрее любой вычислимой функции. Глава 56 · Разговор с Оракулом

условие

Выражение, которое программа проверяет перед тем, как выбрать путь: его значение — True (истина) или False (ложь). Глава 3 · Развилки

устойчивое

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

устойчивой

Сортировка, которая не меняет взаимный порядок элементов с равными ключами. Устойчивы вставки, пузырёк, слияние и sorted в Python; выбор и пирамидальная — нет. Глава 20 · Турнир сортировок

утечка

Память, которую программа занимает, хотя больше ею не пользуется. В языках со сборкой мусора это обычно объекты, до которых ещё можно добраться по забытой ссылке, — растущий список, кэш без предела. Глава 38 · Гостиница с номерами

утиная типизация

Принцип Python: годится любой объект, у которого есть нужные методы, независимо от его класса. Остров вызывает step у всего, что лежит в списке зверей. Глава 12 · Остров кроликов и лис

уязвимостью

Уязвимость: ошибка или особенность системы, через которую можно добиться того, чего её создатель не предполагал, — прочитать чужие данные, получить лишние права, обрушить сервер. Чаще всего это обычная ошибка в коде, а не слабость математики. Глава 61 · Учебный полигон

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

Часть операционной системы, которая превращает массив блоков диска в дерево каталогов и файлов с именами: хранит, какие блоки принадлежат какому файлу, и обновляет эти записи при каждом изменении. Глава 40 · Спасательная операция

файловым дескриптором

Небольшое целое число, под которым процесс знает открытый файл, канал или устройство: номер в таблице открытых файлов процесса. 0, 1 и 2 — стандартные ввод, вывод и вывод ошибок. Глава 36 · Экскурсия по живой системе

ферму ссылок

Множество страниц, созданных только для того, чтобы ссылаться на продвигаемую страницу и поднимать её PageRank. Один из видов поискового спама. Глава 48 · Поисковик по нашим учебникам

Фильтр Блума

Массив из m битов и k хеш-функций: добавляя элемент, ставят k битов в единицу; элемент «возможно, есть», если все его k битов — единицы, и «точно нет», если хоть один — ноль. Глава 26 · Подбросим монетку

фильтрами

Программа, которая читает данные со стандартного ввода, преобразует их и пишет результат в стандартный вывод, — звено конвейера команд: grep, sort, uniq, cut, tr, head. Глава 36 · Экскурсия по живой системе

фишингом

Фишинг: подделка письма, сайта или звонка под доверенный источник, чтобы человек сам ввёл пароль или код. Проверяется адресом отправителя и тем, что настоящая служба никогда не просит пароль. Глава 61 · Учебный полигон

флагов

Отдельный бит в процессоре, который сообщает что-то о результате последней операции: ноль ли он, был ли перенос, отрицателен ли он. Глава 30 · Машина считает

фронтом

Момент, когда цифровой сигнал меняет уровень: передний фронт — из 0 в 1, задний (спад) — из 1 в 0. Глава 31 · Память и такт

функцией

Именованный кусок программы, который можно вызывать много раз с разными аргументами; может вернуть результат через return. Глава 5 · Свои слова

функцией высшего порядка

Функция, которая принимает другие функции как аргументы или возвращает функцию как результат: map, filter, sorted с key, декораторы. Глава 10 · Функции как значения

функцией потерь

Число, которое показывает, насколько модель ошибается на примерах обучающей выборки. Обучение — поиск весов, при которых оно наименьшее. Глава 63 · Машина учится

функциональное программирование

Парадигма программирования, в которой программа — композиция функций, а не последовательность команд: вместо присваиваний — новые значения, вместо циклов — рекурсия и функции высшего порядка. Лисп, ML, Haskell. Глава 49 · Музей языков

хвостовым

Вызов функции, который стоит последним действием другой функции: его результат сразу становится её результатом. Кадр вызывающей функции после такого вызова не нужен, поэтому интерпретатор или компилятор может его не хранить. Глава 51 · Матрёшка

хеш-таблица

Структура данных: массив корзин, и запись с ключом k лежит в корзине номер hash(k) mod m. Поиск, вставка и удаление в среднем занимают O(1). Так устроены dict и set в Python. Глава 16 · Хеш-таблица: атака и защита

хеш-функцией

Функция, которая превращает ключ — строку, число, кортеж — в целое число. Равные ключи она обязана превращать в равные числа; разные желательно — в разные и вразброс. Глава 16 · Хеш-таблица: атака и защита

хешируемыми

Объект, у которого есть хеш (hash(x) работает) и он не меняется за время жизни объекта. Хешируемые объекты могут быть ключами словаря и элементами множества: числа, строки, кортежи из хешируемых. Глава 16 · Хеш-таблица: атака и защита

Худший случай

Самое большое время работы алгоритма среди всех входов размера n. Оценка по худшему случаю — гарантия: быстрее не обещаем, медленнее не будет. Глава 13 · Сколько стоит программа

целочисленное программирование

Задача: минимизировать линейную функцию от переменных при линейных ограничениях, когда переменные обязаны быть целыми (часто 0 или 1). NP-трудна, но решатели справляются с огромными практическими задачами ветвлением и отсечениями. Глава 58 · Экспедиция коммивояжёра

цикл событий

Диспетчер кооперативных сопрограмм: держит очередь готовых и список ждущих (таймера, сети, файла), по очереди продолжает готовые, а когда готовых нет — засыпает до ближайшего события. Глава 37 · Центр управления полётом

циклом

Конструкция, которая повторяет блок команд — заданное число раз или пока выполняется условие. Глава 4 · Снова и снова

циклом

Путь по рёбрам графа, который возвращается в свою начальную вершину, не проходя ни одного ребра дважды. В ориентированном графе — путь по стрелкам. Граф без циклов в зависимостях можно упорядочить топологически. Глава 19 · Шесть рукопожатий

циклом «выборка — декодирование — исполнение»

Работа процессора по кругу: выборка команды из памяти по адресу из счётчика команд, декодирование и исполнение, затем следующая команда. Глава 32 · Ты — процессор

цифровая подпись

Число, которое владелец закрытого ключа вычисляет по сообщению; любой может проверить его открытым ключом, но никто другой не может его подделать, а при малейшем изменении сообщения проверка не проходит. Глава 60 · Секрет на виду у всех

часов

Правило вытеснения страниц, приближающее LRU одним битом на страницу: стрелка обходит кадры по кругу; у страницы с поднятым флагом обращения флаг опускают и идут дальше (второй шанс), страницу с опущенным флагом выселяют. Глава 38 · Гостиница с номерами

частные адреса

Адрес из диапазонов, отведённых для внутренних сетей (10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16): их может использовать кто угодно у себя, но в интернете они не маршрутизируются. Глава 42 · Изобрести протокол

часы Лэмпорта

Логические часы Лэмпорта: у каждого узла счётчик. Перед каждым событием он увеличивается на 1; сообщение несёт значение счётчика отправителя, а получатель ставит себе максимум из своего и пришедшего плюс 1. Если a → b, то отметка a меньше отметки b. Глава 44 · Парламент острова Паксос

чередованием

Один из возможных порядков, в котором перемешаны шаги нескольких потоков; шаги каждого потока при этом идут в своём порядке. Глава 39 · Гонки

числами с плавающей запятой

Дробное число в формате IEEE 754: знак, порядок (степень двойки) и мантисса (значащие двоичные цифры). В 64-битном float — 1, 11 и 52 бита; точность около 16 десятичных знаков. Глава 28 · Всё есть биты

чистыми

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

чтение за краем буфера

Чтение за границей буфера (buffer over-read): программа отдаёт больше данных, чем в буфере есть, прихватывая соседнюю память. Так устроен Heartbleed: сервер возвращал столько байтов, сколько просил клиент, не проверяя, сколько прислал. Глава 61 · Учебный полигон

шаг обучения

Множитель η в градиентном спуске: какую долю градиента вычитают из весов за один шаг. Слишком маленький — обучение тянется, слишком большой — потери растут и веса разлетаются. Глава 63 · Машина учится

шестнадцатеричной

Запись чисел по основанию 16 цифрами 0–9 и буквами a–f. Одна шестнадцатеричная цифра — ровно четыре бита, байт — две цифры: 0xFF = 255. Глава 28 · Всё есть биты

шинглы

Кусок из k идущих подряд слов (или символов) текста. Множество шинглов — «отпечаток» текста, которому безразличен порядок абзацев; общие шинглы двух текстов — общие куски. Глава 27 · Иголка в стоге

Шифр

Правило, по которому открытый текст превращают в шифровку и шифровку обратно в текст. Правило общее, а конкретное превращение выбирает ключ. Глава 59 · Шифровальный отдел

шифр Виженера

Шифр, в котором буквы сдвигаются по очереди на номера букв ключевого слова, повторяемого по кругу: несколько шифров Цезаря вперемешку. Описан Беллазо в 1553 году, назван в честь Виженера. Глава 59 · Шифровальный отдел

шифр простой замены

Шифр, в котором каждая буква алфавита всегда заменяется одной и той же другой буквой по секретной таблице. Ключ — перестановка алфавита. Глава 59 · Шифровальный отдел

шифрованием с открытым ключом

Шифрование, в котором ключи парные: зашифровывают открытым ключом, известным всем, расшифровывают закрытым, который знает только владелец. Пример — RSA. Глава 60 · Секрет на виду у всех

шифровкой

Результат шифрования: текст или байты, из которых без ключа смысл не извлечь. Глава 59 · Шифровальный отдел

шпаргалка

Угаданный кусок открытого текста, который, по-видимому, есть в шифровке: стандартное приветствие, сводка погоды, подпись. Атака по известному открытому тексту начинается со шпаргалки. Глава 59 · Шифровальный отдел

эвристикой

Быстро вычисляемая оценка, которая направляет поиск, например, расстояние до цели по прямой. Сама по себе она не гарантирует правильного ответа. Глава 24 · Навигатор

экземпляром

Объект, созданный по классу: bunny = Rabbit(3, 5) — экземпляр класса Rabbit. У каждого экземпляра свои атрибуты. Глава 12 · Остров кроликов и лис

эксплойтом

Эксплойт: конкретный приём или программа, которая использует уязвимость, чтобы добиться цели нарушителя. Знать уязвимость и иметь работающий эксплойт — разные вещи. Глава 61 · Учебный полигон

экспоненциальное

Время, которое растёт как 2ⁿ (или другое число в степени n): каждый новый элемент входа умножает работу. Перебор всех подмножеств, наивный рекурсивный fib. Глава 13 · Сколько стоит программа

энтропией

Среднее количество информации в одном знаке источника: H = −Σ p(x) log₂ p(x) бит. По теореме Шеннона это нижняя граница среднего числа битов на знак для любого сжатия без потерь. Глава 47 · Конкурс упаковки

эффектом ELIZA

Склонность людей приписывать программе понимание и чувства, которых в ней нет, — по имени бота ELIZA (1966). Глава 7 · Собеседник из строк

Юникод

Единая таблица символов всех письменностей мира: у каждого символа свой номер — кодовая точка от U+0000 до U+10FFFF. Как эти номера лежат в байтах, определяют кодировки UTF-8, UTF-16 и UTF-32. Глава 28 · Всё есть биты

ядро

Самостоятельный исполнитель команд внутри процессора: свои регистры, свой конвейер, свой поток команд. В многоядерном процессоре на одном кристалле несколько ядер, а общими у них бывают кэш последнего уровня и путь к памяти. Глава 35 · Конвейер и предсказатель

ядро

Главная часть операционной системы: работает в привилегированном режиме процессора, управляет памятью, процессами, файлами и устройствами и выполняет просьбы программ — системные вызовы. Глава 36 · Экскурсия по живой системе

языковая модель

Модель, которая по началу текста оценивает вероятности следующего символа, слова или кусочка слова. Выбирая продолжения одно за другим, она пишет текст. Глава 63 · Машина учится