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

174 ГЛОССАРИЙ
Строка
Последовательность символов. Традиционно символами считали буквы ал- фавита, но в настоящее время содержимое строки зависит от контекста; это могут быть цифры, буквы, знаки препинания или даже недавно изобретен- ные символы, такие как эмодзи.
Структура данных
Способ организации данных таким образом, чтобы их можно было обрабаты- вать с помощью набора определенных готовых операций.
Табулятор
Электромеханическое устройство, которое могло считывать перфокарты и использовать эту информацию для выдачи числовых значений.
Тезис Черча — Тьюринга
Гипотеза о том, что любые вычисления, которые можно описать с помощью алгоритма, могут быть выполнены машиной Тьюринга.
Тестовый набор данных
Данные, которые откладываются в сторону во время обучения. С их помощью мы проверяем, насколько хорошо конкретный метод машинного обучения проявляет себя при работе с реальным вводом.
Узел
Элемент в различных структурах данных. Элементы списка называют уз- лами.
Указатель
Участок компьютерной памяти, хранящий адрес другого участка компьютер- ной памяти. Таким образом первый ссылается на второй.
Унарная система счисления
Система счисления, в которой числа представлены одним символом; напри- мер, один штрих обозначает единицу, а III — число 3.
Управляющая структура
Три возможных способа комбинирования шагов алгоритма или программы: последовательность, выбор и итерация.

ГЛОССАРИЙ 175
Учебный набор данных
Данные, которые мы предоставляем алгоритмам машинного обучения, чтобы научить их решать задачи.
Факториал
Факториал натурального числа n является произведением всех чисел от 1 до n включительно. Мы используем обозначение n!, поэтому n! = 1 × 2 × … × n.
Это определение можно расширить до всех вещественных чисел, но здесь нас это не интересует.
Факториальная сложность
Вычислительная сложность, которая соответствует факториальному росту.
В обозначении больше «О» это выглядит как O(n!).
Функция активации
Функция, которая определяет вывод нейрона на основе его ввода.
Хроматический индекс
Минимальное количество цветов, которые нужны, чтобы раскрасить все ребра графа (задача раскраски графа).
Центральное процессорное устройство
Чип, который выполняет инструкции программы внутри компьютера.
Цикл
Путь, который начинается и заканчивается в одном и том же узле графа.
А также повторяющаяся последовательность инструкций в компьютерной программе. Цикл завершается при выполнении условия. Цикл, который ни- когда не заканчивается, называется бесконечным и обычно является резуль- татом ошибки, не давая программе остановиться. См. итерация.
Частная производная
Производная функции для одной из множества переменных, в то время как остальные переменные принимаются за константы.
Число Эйлера
Математическая константа e, приблизительно равная 2,71828. Это предел
(1 + 1/n)
n
, где n стремится к бесконечности.

Эвристика
Стратегия выбора между альтернативными решениями в алгоритме. Жадная эвристика склоняет нас к выбору, который выглядит лучше всего прямо сей- час (без учета того, что может произойти в будущем).
Эйлеров путь
Маршрут, проходящий по каждому ребру графа ровно один раз. Его еще на- зывают «эйлерова цепь».
Эйлеров цикл
Эйлеров путь, который начинается и заканчивается в одном и том же узле.
Экспоненциальный рост
Модель роста, в которой количество элементов последовательно умножается само на себя. Например, мы начинаем с a элементов, затем получаем a × a, за- тем a × a × a; в целом это Формула. При экспоненциальном росте числа бы- стро увеличиваются.
Эпоха
Этап в процессе машинного обучения, охватывающий весь набор учебных данных.
Эффект Матфея
Явление, состоящее в том, что богатые становятся богаче, а бедные беднеют.
Названо в честь стиха из Евангелия от Матфея (25:29) и, как показывает прак- тика, применимо ко многим сферам, а не только к материальному богатству.
Язык программирования
Искусственный язык, с помощью которого можно описывать этапы вы- числений. Язык программирования может быть выполнен на компьютере.
У языков программирования, как и у естественных языков, есть синтаксис и грамматика, которые определяют, что на них можно писать. Их существует большое количество, и постоянно появляются новые языки, призванные сде- лать программирование более продуктивным (или просто потому, что мно- гие не могут удержаться от создания собственного языка в надежде на то, что он получит широкое распространение). Языки программирования бывают высокоуровневыми и низкоуровневыми; первые похожи на естественный язык, а последние состоят из элементарных конструкций, отражающих соот- ветствующее аппаратное обеспечение.

ПРИМЕЧАНИЯ 177
ПРИМЕЧАНИЯ
Предисловие
1. Если вам интересны эти и другие индикаторы глобального успеха, достиг- нутого благодаря идеям Просвещения, ищите «Pinker 2018».

178 ПРИМЕЧАНИЯ
здесь используется число π. Эти формулы в 2002 году предложила Бритни
Кристал Галливан, которая в то время была старшеклассницей. Она ре- шила продемонстрировать, что рулон туалетной бумаги длиной 365 ме- тров можно сложить пополам всего 12 раз. Хорошее введение в степени степеней (включая этот пример) можно найти в [Строгаз, 2012, глава 11].
8. См. Transistor count, «Википедия», https://en.wikipedia.org/wiki/Transistor_
count.
9. Это вызвано тем, что для сравнения n элементов друг с другом вам нужно взять один элемент и сравнить его с остальными n — 1 элементами, затем взять еще один и сравнить его с n — 2 элементами (с первым вы его уже срав- нили) и т. д. Таким образом получается 1 + 2 + … + (n – 1) = n(n – 1) / 2 срав- нений. Затем вы получаете O(n(n – 1) / 2) = О(n
2
— n / 2) = O(n
2
), потому что, согласно определению большого «O», алгоритм, время работы которого не превышает O(n
2
), точно успеет выполниться за время О(n
2
— n / 2).
Глава 2
1. Изображение находится в общественном состоянии и взято из Wikipedia
Commons по адресу: https://commons.wikimedia.org/wiki/File: Konigsberg_
Bridge.png.
2. Документ (Eulerho, 1736) доступен на сайте Euler Archive (http://eulerarchive.
maa.org), который находится в ведении Математической ассоциации США.
Английский перевод находится в [Биггз, Ллойд и Уилсон, 1986].
3. Графам посвящен обширный раздел научной литературы. Хорошей от- правной точкой будет [Бенджамин, Чартранд и Чанг, 2015].
4. Изображение, опубликованное в оригинальном издании (Eulerho, 1736), взято из Wikipedia Commons по адресу: https://commons.wikimedia.org/
wiki/File:Solutio_problematis_ad_geometriam_situs_pertinentis,_Fig._1.png.
Находится в общественном доступе.
5. Изображение из [Кекуле, 1872], взятое из «Википедии» по адресу: https://
en.wikipedia.org/wiki/Benzene#/media/File: Historic_Benzene_Formulae_
Kekul%C3%A9_(original).png. Находится в общественном достоянии.
6. Оригинальное издание на немецком языке ищите в [Хирхольцер, 1873].
7. Если вам интересны подробности об алгоритме Хирхольцера и других ал- горитмах для эйлерового пути, см. [Флейшнер, 1991]. Использование гра- фов в процессе составления генома описывается в [Певзнер, Танг и Уотер- ман, 2001; Компю, Певзнер и Теслер, 2001].

ПРИМЕЧАНИЯ 179 8. Анализ оптимальности жадного онлайн-алгоритма для раскрашивания ребер, а также пример звездообразного графа, иллюстрирующего худший случай, можно найти в [Бар-Ной, Мотвани и Наор, 1992].
9. В оригинальной басне двумя персонажами были муравей и цикада. Они также встречаются в латинских переводах с древнегреческого и пересказе
Жана де Лафонтена на французском языке.
10. История об изобретении алгоритма изложена Дейкстрой в интервью Misa and Frana в 2010 году.
Глава 3
1. Первое описание эффекта Матфея встречается в [Мертон, 1968]. Обзоры ряда явлений с неравномерными распределениями ищите в [Барабаси и Мартон, 2016; Уест, 2017]. Если вас интересует несоответствие распре- делений роста и богатства среди посетителей стадиона, см. [Талеб, 2007].
2. Самоорганизующийся поиск представлен Джоном Маккейбом в 1965 году.
Анализ производительности методов перемещения в начало и перегруппи- ровки можно найти в [Ривест ,1976; Бахраш, Эль-Янив и Рейнштедтлер, 2002].
3. Задача о секретарях опубликована в колонке Мартина Гарднера в февраль- ском выпуске журнала Scientific American 1960 года. Решение дано в мар- товском выпуске. Об истории этой задачи можно почитать в [Фергюсон,
1989]. В 2006 году Д. Нил Бирден предложил решение для варианта, со- ставленного без использования принципа «все или ничего». В [Мэтт Пар- кер, 2014, 11 глава] находится описание этой задачи вместе с несколькими другими математическими идеями и введением в компьютеры.
4. Двоичный поиск появился на заре компьютерной эпохи [Кнут 1998]. Джон
Мокли, один из архитекторов ENIAC, первого цифрового компьютера об- щего назначения, описал его в 1946 году. Если вас интересует богатая ис- тория двоичного поиска, см. [Бентли, 2000; Пэттис, 1988; Блох, 2006].
Глава 4
1. Холлерит, 1894.
2. Сортировки выбором и вставками существуют с момента появления пер- вых компьютеров; они включены в исследование методов сортировки в 1950-х годах [Friend, 1956].

180 ПРИМЕЧАНИЯ
3. Согласно [Кнуту, 1998, 170], идея, стоящая за поразрядной сортировкой в том виде, в котором мы ее видели здесь, существует как минимум с 1920-х годов.
4. Подбрасывание монеты следует из 1 / 52! ≈ (1 / 2)
226
. Пример с выбором случайного атома позаимствован у Дэвида Хэнда (2014), согласно кото- рому, вероятность меньше одного из 10 50
является пренебрежительно низ- кой в космических масштабах.
5. См. [Хоар, 1961a, 1961b, 1961c].
6. Больше о рандомизированных алгоритмах можно найти в [Митценмахер и Апфол, 2017].
7. О жизни фон Неймана и атмосферы, царившей в эпоху появления первых цифровых компьютеров, можно почитать в [Дайсон, 2012]. Презентацию программы для сортировки слиянием фон Неймана см. [Кнут, 1970].
Глава 5
1. Оригинальная версия алгоритма PageRank опубликована Брином и Пэй- джем в 1998 году. Мы лишь поверхностно затронули ее математические аспекты. Более глубокий обзор ищите в [Брайан и Лейсе, 2006]. Введение в поисковые системы и PageRank представлено в [Лэнгвил и Мейер, 2006;
Берри и Браун, 2005]. Еще одним важным алгоритмом ранжирования явля- ется Hypertext Induced Topic Search или HITS [Клейнберг, 1998, 1999], раз- работанный раньше, чем PageRank. Задолго до этого, еще в 1940-х годах, похожие идеи возникали в других областях, например в социометрии, на- уке об измерении социальных отношений, и эконометрике, науке о коли- чественных аспектах экономических принципов [Францешет, 2011].
Глава 6
1. Современные технологии позволяют рассматривать нейроны гораздо более детально, но Рамон-и-Кахаль был пионером в этой области, и его рисунки считаются одними из самых элегантных иллюстраций в истории науки.
В Интернете можно найти множество изображений нейронов, но этого ри- сунка нам достаточно; вы можете сами убедиться в красоте и неувядающей силе иллюстраций Рамон-и-Кахаля, выполнив простой поисковый запрос.
Приведенный здесь рисунок находится в общественном достоянии и досту- пен по адресу: https://commons.wikimedia.org/wiki/File:PurkinjeCell.jpg.

ПРИМЕЧАНИЯ 181 2. Если быть точным, название «сигмоида» происходит от греческой буквы сигма,
Σ, но по своему внешнему виду эта функция больше напоминает ла- тинскую букву S.
3. Касательная угла определяется как отношение противоположной стороны прямоугольного треугольника к смежной или как синус угла, поделенный на косинус угла в единичной окружности. Гиперболический тангенс опре- деляется как отношение между гиперболическим синусом и гиперболиче- ским косинусом угла на гиперболе.
4. В 1943 году Уоррен Маккаллок и Уолтер Питтс предложили первый искус- ственный нейрон. В 1957 году Фрэнк Розенблатт описал перцептрон. Этим изобретениям уже больше полувека. Как же так получилось, что нейрон- ные сети набрали популярность лишь недавно? В 1969 году Марвин Мин- ски и Сеймур Пейперт в своей знаменитой одноименной книге нанесли сильный удар по идее перцептрона, указав на то, что ему свойственны фундаментальные вычислительные ограничения. Это в сочетании с несо- вершенным оборудованием тех дней привело к так называемой зимней спячке в нейронных вычислениях, которая длилась вплоть до 1980-х, пока исследователи не научились создавать и обучать сложные нейронные сети.
Это возродило интерес к данной области, но, чтобы довести нейронные сети до уровня популярности, который наблюдается в последние пять лет, пришлось проделать много работы.
5. Одна из трудностей при изучении нейронных сетей связана с запутан- ными обозначениями, которые, как может показаться, понятны только избранным. Но на самом деле они не такие уж и сложные, если понимать, о чем идет речь. Мы часто можем встретить производные; производная функции f(x) по x записывается как
df x
dx
( )
. Частная производная функции f со многими переменными, такими как x
1
, x
2
, … x
n
, записывается как
∂
∂
f
x
i
Градиент обозначает как
∇ = ∂
∂
… ∂
∂
f
f
x
f
x
n
(
, ,
)
1 6. Алгоритм обратного распространения появился на свет в середине 1980-х
[Румельхарт, Хинтон и Уильямс, 1986], хотя различные его вариации встречались еще в 1960-х годах.
7. Это изображение взято из набора данных Fashion-MNIST [Сяо, Расул и Вольграф, 2017[, разработанного для измерения производительности машинного обучения. Раздел вдохновлен учебным руководством по ос- новам классификации в TensorFlow, доступным по адресу: https://www.
tensorflow.org/tutorials/keras/basic_classification.
8. Описание первой системы, победившей чемпиона по го, можно найти в [Сильвер и др., 2016]. Ее улучшенная версия, не требующая человеческих