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

156 ПОСЛЕСЛОВИЕ
Эта машина Тьюринга выполняет алгоритм для вычисления операции собственного вычитания на основе предоставленного ввода, следуя ин- струкциям, описанным в соответствующей таблице. Ее шаги настолько эле- ментарны, что для выполнения операции головке приходится активно пе- ремещаться туда-сюда. Чтобы найти 2 ׹ 4 = 0 и 4 ׹ 2 = 2 потребуется 21 и, соответственно, 34 действия. Действий много, но насколько же они про- сты! Для их выполнения требуется минимальный интеллект. Именно в про- стоте итераций весь смысл. Для выполнения действий машины Тьюринга не требуется особых умений; вам лишь нужно сверяться с таблицей, пере- мещаться по ленте, считывать и записывать по одному символу за раз и сле- дить за своим состоянием. Вот и все. Нетривиальным этот подход делает то, что действия, которые способна выполнять машина Тьюринга, определяют, из каких шагов может состоять алгоритм.
В этой книге алгоритмы описывались на более высоком уровне с помо- щью более сложных шагов. Это делалось для удобства, так как машина Тью- ринга работает на таком низком уровне, что описывать с ее помощью наши алгоритмы было бы слишком громоздким процессом. Но все шаги в любом рассмотренном нами алгоритме можно представить в виде действий кор- ректно составленной машины Тьюринга. Мы продемонстрировали простую машину для реализации собственного вычитания. Для более сложных алго- ритмов нам понадобилась бы машина Тьюринга с большим количеством дей- ствий, с более объемным алфавитом и более богатой таблицей инструкций.
Но это была бы вполне выполнимая задача.
Несмотря на свою простоту, машина Тьюринга имеет широчайшую сферу применения; с ее помощью можно реализовать любой алгоритм. Машина
Тьюринга способна выполнить любой алгоритм, который можно вычислить на компьютере. Иными словами, с ее помощью можно делать все, на что спосо-
бен алгоритм. Это свободная трактовка тезиса Черча — Тьюринга, названного в честь Тьюринга и американского математика Алонсо Черча (1903–1995), од- ного из основателей теоретических компьютерных наук. Это тезис, поскольку у него нет доказательства, и мы не знаем, можно ли его доказать математиче- ски. Теоретически он может быть опровергнут, если кто-то разработает аль- тернативный вид вычислений, способный решать задачи, которые не под силу машине Тьюринга. Но вряд ли это когда-либо произойдет. Поэтому машина
Тьюринга считается формальным описанием понятия алгоритм.
Представьте себе компьютер — настолько мощный, насколько хотите. Он будет куда быстрее описанной нами машины Тьюринга, которая работает с лен- той символов. Но все, что он вычисляет алгоритмическим путем, может быть

вычислено машиной Тьюринга. Это касается даже тех компьютеров, которые мы еще не умеем производить. Наши устройства работают с битами, которые принимают лишь одно из двух состояний: 0 или 1. Квантовые компьютеры ра- ботают с кубитами. Если проверить состояние кубита, оно точно так же будет равно либо 0, либо 1. Но между проверками кубит может находиться в комбини- рованном состоянии, известном как суперпозиция. То есть он одновременно мо- жет быть равен 0 и 1, пока мы не решим его прочитать; только тогда он примет одно из этих двух значений. Это позволяет квантовым компьютерам представ- лять сразу несколько состояний вычисления. Они способны быстро решать слож- ные задачи, с которыми плохо справляются классические компьютеры. К сожа- лению, на текущем уровне технологического прогресса производство квантовых компьютеров сопряжено с большими трудностями. Тем не менее даже они не мо- гут делать что-то такое, что не под силу машине Тьюринга. Они более эффек- тивны в решении некоторых задач, чем классические ЭВМ или любые машины
Тьюринга, если уж на то пошло. Но если машина Тьюринга не может решить какую-то задачу, квантовый компьютер тоже окажется бессильным.
Рамки, в которых проводятся вычисления, определяются машинами Тью- ринга. Все, что делает компьютер, можно сделать с помощью ручки и листа бумаги, работая с лентой символов. Все, что выполняется на любом цифро- вом устройстве, в сущности, является последовательностью элементарных манипуляций с символами. В естественных науках мы наблюдаем окружаю- щий мир и пытаемся объяснить его с помощью фундаментальных принци- пов. В вычислениях все наоборот: мы пытаемся найти для фундаментальных принципов различные практические применения.
Тьюринг предложил свою машину в качестве модели вычислений еще до появления первых цифровых компьютеров. Это не мешало ему исследо- вать возможности будущих вычислительных устройств. Говоря об ограниче- ниях, свойственных компьютерам, следует помнить, что в их рамках челове- ческий интеллект способен творить чудеса. Эти ограничения не мешают нам создавать алгоритмы на все случаи жизни. Когда в Месопотамии была изо- бретена письменность, она предназначалась для учета, а не для литератур- ных текстов. Первыми писателями, вероятно, стали бухгалтеры, но в итоге, несмотря на такое скромное начало, мы получили Уильяма Шекспира. Кто знает, что нам со временем принесут алгоритмы.
Рамки, в которых проводятся вычисления, определяются машинами Тью- ринга. Все, что делает компьютер, можно сделать с помощью ручки и листа бумаги… Все, что выполняется на любом цифровом устройстве, является по- следовательностью элементарных манипуляций с символами.

158 ГЛОССАРИЙ
ГЛОССАРИЙ
Null
Ничто в компьютере.
PageRank
Алгоритм, который используется для ранжирования веб-страниц в зависимо- сти от их значимости. Разработан основателями Google и стал фундаментом одноименной поисковой системы.
ReLU
Нейрон, который использует выпрямитель в качестве функции активации.
ReLU расшифровывается как rectified linear unit (выпрямленная линейная единица).
Tanh (гиперболический тангенс)
Функция активации, похожая на сигмоиду, но со значениями в диапазоне от –1 до 1.
Softmax
Функция активации, которая принимает на вход вектор вещественных чи- сел и превращает его в другой вектор, описывающий распределение вероят- ностей.
«О» большое
Обозначение сложности вычислений. Имея алгоритм и ввод, превышающий какой-то пороговый показатель, оно дает нам максимальное ожидаемое ко- личество шагов, необходимых для выполнения алгоритма. Ввод должен пре- вышать какое-то пороговое значение, поскольку нас интересует поведение алгоритма в контексте больших наборов данных. Вычислительная сложность алгоритма «О» большое гарантирует, что при достаточно большом вводе ал- горитму не потребуется больше определенного количества шагов. Например, сложность O(n
2
) означает, что, имея ввод размером n, превышающий опреде- ленную пороговую величину, мы можем выполнить алгоритм за количество шагов, не превышающее фиксированный множитель n
2

ГЛОССАРИЙ 159
Автоматическое дифференцирование
Набор методик для получения производной функции численным, а не анали- тическим путем, который потребовал бы использования правил исчисления для дифференцирования функций.
Активация
Генерация вывода нейроном.
Акцентированный отрезок
Часть ритма, на которую делается акцент.
Алгоритм
1. Вернитесь к первой странице этой книги.
2. Прочитайте текущую страницу.
3. Если непонятно, вернитесь к пункту 2. В противном случае переходите к пункту 4.
4. Если следующая страница существует, сделайте ее текущей и перейдите к пункту 2. В противном случае остановитесь.
Алгоритм Дейкстры
Алгоритм для поиска кратчайшего расстояния между двумя узлами в графе, изобретенный в 1956 году молодым голландским ученым Эдсгером Дейк- строй. Он работает с графами, содержащими положительные веса.
Алгоритм Евклида
Алгоритм для поиска наибольшего общего делителя двух целых чисел, пред- ставленный в 13-томном сборнике «Начала», который написал древнегрече- ский математик Евклид (около 300 г. до н. э.). Этот труд посвящен геометрии и теории чисел, начиная с аксиом и заканчивая доказательством теорем, ос- нованных на этих аксиомах. Это древнейшая дошедшая до нас работа в обла- сти математики, в которой используется этот дедуктивный подход, что делает ее одной из наиболее влиятельных книг в истории науки.
Алгоритм обратного распространения
Фундаментальный алгоритм обучения нейронных сетей. Сеть корректирует свою конфигурацию (веса и сдвиги) путем передачи обновленных значений от конечного слоя к первому.

160 ГЛОССАРИЙ
Алгоритм Хирхольцера
Алгоритм поиска в графах циклов Эйлера. Опубликован в 1873 немецким ма- тематиком Карлом Хирхольцером.
Аппаратное обеспечение
Физические компоненты, из которых состоит компьютер или цифровое устройство. Этот термин дополняет программное обеспечение.
Ациклический граф
Граф, у которого нет циклов.
Бит
Основная единица информации, хранящаяся в компьютере. Бит может при- нимать одно из двух значений: 0 или 1. Слово «бит» (англ. bit) происходит от словосочетания binary digit (двоичная цифра).
Блуждающий пользователь
Человек, который переходит с одной веб-страницы на другую в соответствии с вероятностью, заданной в матрице Google.
Быстрая сортировка
Метод сортировки, который работает путем многократного перемещения значений относительно выбранного элемента так, чтобы те, которые меньше его, оказались по левую сторону, а остальные — по правую.
Вектор
Горизонтальная строка или вертикальный столбец чисел (или, в более общем смысле, математических выражений). Векторы обычно встречаются в геоме- трии, где они имеют длину и направление и представлены в виде строки или столбца с их числовыми координатами; но в действительности понятие век- тора носит более общий характер — возьмите, к примеру, рейтинговый век- тор. Вектор является частным случаем матрицы.
Вес (граф)
Число, назначенное ребру графа. Такое число, к примеру, может представ- лять награду или наказание, связанные со ссылкой между двумя узлами, со- единенными ребром.

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

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

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