Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

164 ГЛОССАРИЙ
Интернет
Глобальная сеть компьютеров и цифровых устройств, взаимосвязанных по- средством общего набора коммуникационных протоколов.
Итерация
См. цикл.
Категорийная перекрестная энтропия
Функция потери, которая вычисляет разницу между двумя распределениями вероятностей.
Квантовый компьютер
Компьютер, который использует квантовые явления для выполнения вычис- лений. Квантовые компьютеры работают с кубитами вместо битов и могут решать некоторые задачи намного быстрее, чем классические ЭВМ. Изготов- ление квантовых компьютеров сопряжено с определенными физическими трудностями.
Класс сложности
Набор задач, для решения которых требуется один и тот же объем ресурсов
(таких как время или память).
Классификатор
Программа, которая относит наблюдение к одному из нескольких классов.
Ключ
Элемент записи, который мы используем для ее сортировки или поиска. Ключ может быть атомарным, если его нельзя разбить на отдельные части (напри- мер, идентификационный номер), или составным, если он состоит из более мелких фрагментов данных (как полное имя, состоящее из фамилии, имени и отчества).
Кратчайший путь
Кратчайший путь между двумя узлами графа.
Кубит
Элементарная единица квантовой информации. Кубит может существовать в суперпозиции двух состояний, 0 и 1. Но, если его измерять, он схлопывается

ГЛОССАРИЙ 165
в одном из двух двоичных значений. Кубит может быть реализован с помо- щью таких квантовых свойств, как спин электрона.
Линейно разделяемый
Набор данных, наблюдения в котором можно разделить на две категории с помощью прямой линии (в двумерном пространстве), плоскости (в трех- мерном пространстве) или гиперплоскостью (если измерений больше трех).
Линейное время
Время, пропорциональное вводу алгоритма. Записывается как O(n).
Линейный поиск
Поисковый алгоритм, в котором каждый элемент анализируется по очереди, пока не будет найдено то, что мы ищем. Его еще называют последователь- ным поиском.
Логарифм
Операция, противоположная возведению в степень. Логарифм отвечает на следующий вопрос: «В какую степень нужно возвести число, чтобы полу- чить нужное значение?» Если спросить, «в какую степень нужно возвести 10, чтобы получить 1000?», ответом будет 3, поскольку 10 3
= 1000. Число, возво- димое в степень, называется основанием. Если a
x
= b, мы записываем log
a
x.
Если a = 2, мы записываем lgx.
Логарифмическое время
Время, пропорциональное логарифму ввода алгоритма, например O(lgn).
Присуще хорошим поисковым алгоритмам.
Логлинейное время
Время, пропорциональное произведению размера ввода алгоритма и лога- рифма этого ввода, например O(nlgn). Присуще хорошим алгоритмам сор- тировки.
Локальный оптимум
Решение, которое превосходит все другие решения, находящиеся по сосед- ству, но не является лучшим в целом. Соседним называется решение, которое находится в одном шаге от текущего.

166 ГЛОССАРИЙ
Матрица
Прямоугольный массив, который, как правило, состоит из чисел или, в более общем виде, математических выражений. Содержимое матрицы организо- вано в виде горизонтальных строк и вертикальных столбцов.
Матрица Google
Специального рода матрица (модификация матрицы гиперссылок), которая используется в степенном методе в алгоритме PageRank.
Матрица гиперссылок
Матрица, представляющая структуру графа; похожа на матрицу смежности, но каждый элемент в ней делится на количество ненулевых элементов в со- ответствующем ряду.
Матрица смежности
Матрица, представляющая граф. Для каждой вершины графа предусмотрены строка и столбец. Каждая запись, строка и столбец которой соответствуют двум вершинам, соединенным ребром графа, содержит 1; все остальные за- писи равны 0.
Машина Тьюринга
Идеализированная (абстрактная) машина, описанная Аланом Тьюрингом.
Состоит из бесконечной ленты и подвижной головки, которая считывает и за- писывает символы на этой ленте, руководствуясь набором заданных правил.
Машина Тьюринга может реализовать любой алгоритм, поэтому ее можно использовать в качестве модели возможных вычислений.
Машинное обучение
Применение алгоритмов, которые решают задачи путем автоматического об- учения на примерах.
Метка
В машинном обучении это значение, представляющее категорию, к кото- рой принадлежит наблюдение. В ходе обучения компьютеру предоставля- ются задачи вместе с решениями; если задача состоит в классификации, решение представляет собой метку, соответствующую определенному классу.

ГЛОССАРИЙ 167
Метод перегруппировки
Самоорганизующийся поисковый алгоритм. Найденный элемент меняется местами с предыдущим. Таким образом популярные элементы перемеща- ются ближе к началу.
Метод строковой сортировки
Метод сортировки, который работает со своими ключами как с последова- тельностью символов. Например, ключ 1234 воспринимается как строка сим- волов 1, 2, 3, 4, а не как число 1234.
Мультиграф
Граф, в котором одно и то же ребро может повторяться.
Мультимножество
Множество, в котором элемент может встречаться в нескольких экземпля- рах; в математике элемент не может входить в обычное множество больше одного раза.
Мусор на входе — мусор на выходе
Если программе предоставлены неверные данные вместо ожидаемого ввода, не стоит ждать чудес: программа выдаст неверный результат вместо ожидае- мого вывода.
Наибольший общий делитель
Наибольшее целое число, на которое делятся два других целых числа.
Направленный граф
Граф, в котором ребра направлены. Направленный граф также называют ори- ентированным (или орграфом, если коротко).
Нейрон
Клетка, которая является элементарным составным элементом нервной си- стемы. Она принимает сигналы от одних нейронов и передает их другим.
Ненаправленный граф
Граф с ненаправленными ребрами.

168 ГЛОССАРИЙ
Нерешаемая задача
Задача, решение которой с использованием лучшего известного нам алго- ритма заняла бы слишком много времени для того, чтобы рассматривать что-то кроме тривиальных случаев.
Обратная ссылка
Ссылка, которая указывает на просматриваемую нами веб-страницу (или же веб-страница с этой ссылкой).
Обучение
Процесс предоставления алгоритму машинного обучения демонстрационного ввода, на основе которого он может научиться выдавать правильный вывод.
Обучение без учителя
Подход к машинному обучению, в котором алгоритму предоставляются за- дачи без решений. Таким образом алгоритм должен определить, каким дол- жен быть ввод для получения нужных решений.
Обучение с учителем
Подход к машинному обучению, в котором алгоритму предоставляются как сами задачи, так и их решения.
Онлайн-алгоритм
Алгоритм, которому не нужен полный ввод для решения задачи. Онлайн-ал- горитм получает ввод постепенно, по мере его появления, и на каждом этапе генерирует решение на основе уже принятого ввода.
Оптимизаторы
Алгоритмы, которые оптимизируют значение функции. В машинном обуче- нии оптимизаторы обычно минимизируют значение функции потерь.
Перемещение к началу
Самоорганизующийся поисковый алгоритм. При нахождении искомого эле- мента мы перемещаем его в начало.
Переподгонка (переобучение)
Эквивалент зубрежки в машинном обучении. Модель, которую мы пытаемся обучить, слишком хорошо адаптируется к учебным данным. В результате она

ГЛОССАРИЙ 169
неспособна предсказывать правильные значения для других, неизвестных данных.
Переполнение
Выход за пределы диапазона допустимых значений на компьютере.
Перестановка
Изменение порядка размещения каких-то данных.
Перфокарты
Кусок тонкого картона с дырами, размещение которых обозначает какую-то информацию. Эти карты использовались в старых компьютерах и даже раньше, в устройствах вроде жаккардового ткацкого станка, в котором они описывали тканые узоры.
Перцептрон
Искусственный нейрон, для активации которого используется ступенчатая функция.
Плотное соединение
Слои в нейронной сети организованы так, что все нейроны одного слоя соеди- няются со всеми нейронами следующего.
Подгонка
Процесс машинного обучения на основе данных. В этом процессе создается модель, которая соответствует наблюдениям.
Полиномиальное время
Время, пропорциональное вводу алгоритма, возведенному в фиксированную степень. Например, O(n
2
).
Поразрядная сортировка
Метод сортировки, который работает путем разбиения ключей на состав- ные части (например, на отдельные цифры, если это цифровой ключ) и рас- пределения по группам в зависимости от значений этих составных частей
(десять групп, по одной для каждой цифры). Вначале группы формируются на основе последней цифры, затем мы складываем их вместе и распределяем в зависимости от предпоследнего разряда и т. д. Дойдя до первого разряда,

170 ГЛОССАРИЙ
мы получаем отсортированную группу. Это метод строковой сортировки, по- скольку он работает с числовыми ключами как со строками цифр.
Последовательность
Последовательность шагов, выполняемых один за другим в алгоритмах и про- граммировании.
Потеря
Разница между фактическим и желаемым выводом алгоритма машинного об- учения. Обычно вычисляется функцией потерь.
Приближение
Решение задачи с помощью алгоритма, который может дать не оптимальный, но достаточно близкий к нему результат.
Программа
Набор инструкций, написанных на языке программирования, которые опи- сывают вычислительный процесс.
Программирование
Искусство написания компьютерных программ.
Программная ошибка (
англ. bug)
Ошибка в программе. С помощью этого термина Томас Эдисон описывал тех- ническую неисправность. На ранних этапах развития компьютерной техники в оборудование пробирались настоящие насекомые (bugs) и выводили его из строя. Например, в 1947 году в компьютер Harvard Mark II залетел моты- лек и отпечатался в его журнале, который впоследствии вошел в коллекцию
Национального музея американской истории при Смитсоновском институте.
Программное обеспечение (software)
Набор программ, выполняющихся на компьютере или цифровом устройстве.
Этот термин дополняет аппаратное обеспечение. Он использовался в разных областях еще до появления компьютеров. В 1850-х годах сборщики мусора называли разлагающиеся материалы soft-ware («мягкие изделия»), а осталь- ные — hard-ware («твердые изделия»). Эта терминология может поднять на- строение тем, кому никак не удается заставить компьютер делать то, что от него требуется.

ГЛОССАРИЙ 171
Производная
Наклон функции в заданной точке или скорость ее изменения. Например, ускорение — это производная скорости (быстрота изменения скорости по времени).
Пространство поиска
Область значений, по которым мы ищем.
Путь
Последовательность ребер графа, которые соединяют последовательность узлов.
Путь выполнения
Последовательность шагов, которые алгоритм выполняет в ходе своей ра- боты.
Разделяй и властвуй
Метод решения задач, в котором задача разбивается на более мелкие подза- дачи (обычно две) снова и снова, пока они не становятся настолько простыми, что их решение становится тривиальным.
Разреженная матрица
Матрица, большинство элементов которой равны нулю.
Рандомизация
Использование в алгоритмах элемента случайности. Это дает алгоритму возмож- ность находить хорошие решения в большинстве случаев, даже если поиск оп- тимального решения является невыполнимым с вычислительной точки зрения.
Раскрашивание вершин
Назначение цветов вершинам графа таким образом, чтобы никакие две смеж- ные вершины не были одного цвета.
Раскрашивание графа
Раскрашивание ребер или вершин графа.
Раскрашивание ребер
Назначение цветов ребрам графа таким образом, чтобы никакие два смеж- ных ребра не были одного цвета.

172 ГЛОССАРИЙ
Распознавание изображений
Вычислительная задача по распознаванию образов в изображениях.
Расщепление
Разбиение материала на более мелкие части. В ядерной физике роль такого материала играет тяжелое ядро, излучающее большое количество протонов и нейтронов в результате столкновения с высокоэнергетической частицей.
Рейтинговый вектор
Вектор, содержащий рейтинги страниц графа.
Релаксация
Метод, который используется в алгоритмах для работы с графами. Искомым элементам назначаются худшие значения из возможных, и затем алгоритм их постепенно корректирует. Таким образом мы начинаем с самых крайних зна- чений и плавно их смягчаем, приближая их к конечному результату.
Самоорганизующийся поиск
Поисковый алгоритм, который учитывает популярность элементов, переме- щая их туда, где их можно будет быстрее найти.
Сдвиг
Числовое значение, присвоенное нейрону, которое определяет его склон- ность к активации.
Сигмоида
Функция в форме буквы S, чьи значения находятся в диапазоне от 0 до 1.
Синапс
Соединение между нейронами.
Скрытый слой
Слой нейронной сети, не связанный напрямую с ее вводом или выводом.
Сложность (вычислительная сложность)
Время, необходимое для выполнения алгоритма. Время выражается в после- довательности элементарных вычислительных шагов, которые нужно выпол- нить.

ГЛОССАРИЙ 173
Собственный вектор
В линейной алгебре это вектор, дающий при умножении на определенную ма- трицу тот же вектор, умноженный на число (которое называют собственным).
PageRank находит первый собственный вектор матрицы Google, то есть соб- ственный вектор матрицы Google с наибольшим собственным значением (1).
Сортировка слиянием
Метод сортировки, который работает путем многократного слияния все боль- ших наборов отсортированных элементов.
Сортировка вставками
Метод сортировки, в котором каждый элемент вставляется в подходящую по- зицию среди уже отсортированных элементов.
Сортировка выбором
Метод сортировки, в котором мы раз за разом находим наименьший из неупо- рядоченных элементов и помещаем его в правильную позицию.
Социальная сеть
Граф, в котором роль узлов играют люди, а связи между ними являются ребрами.
Список
Структура данных, содержащая элементы. Каждый элемент указывает на сле- дующий; исключение составляет последний элемент, который указывает в никуда или, как еще говорят, на null. Таким образом элементы связаны ме- жду собой, поэтому подобные списки также называют связными.
Срабатывание (нейрон)
См. активация (нейрон).
Степенной метод
Алгоритм, который берет вектор, умножает его на матрицу и затем умножает результат на ту же матрицу снова и снова, пока он не придет к стабильному значению. Степенной метод — ключевой элемент PageRank; вектор, в кото- ром он сходится, является первым собственным вектором матрицы Google.
Степень (узел)
Количество ребер узла.