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

знаний в форме сыгранных ранее партий, описывается в [Сильвер и др.,
2017].
9. Литература, посвященная глубокому обучению, является довольно обшир- ной. Если вас интересует комплексное введение в эту область, см. [Гуд- феллоу, Бенджио и Курвилль, 2016]. Краткий обзор можно найти в [Лекун,
Бенджио и Хинтон, 2015]. Темы глубокого и машинного обучения осве- щаются в [Алпайдин, 2016]. Исследование на тему автоматических поис- ковых методов в нейронной архитектуре можно почитать в [Елскен, Хен- дрик Метзен и Хаттер, 2018].
Послесловие
1. Помимо Тьюринга, другими известными исследователями в этой обла- сти были Мэри Эннинг, Пол Дирак, Розалинд Фрэнклин, Уильям и Кэро- лин Хершел, Дороти Ходжкин, Ада Лавлейс и Чарльз Бэббидж, Стивен Хо- кинг, Джеймс Клерк Максвелл, Сриниваса Рамануджан, Эрнест Резерфорд и Фредерик Сэнгер. Бэббидж, Лавлейс и Тьюринг были пионерами в сфере компьютеров. Бэббидж (1791–1871) изобрел первую вычислительную ма- шину и выработал фундаментальные принципы, на которых основаны со- временные компьютеры. Лавлейс (1815–1852), дочь лорда Байрона, рабо- тала вместе с Бэббиджем, осознала потенциал его изобретения и создала первый алгоритм, который можно было выполнить на таком устройстве.
В наши дни она считается первым компьютерным программистом. Ди- зайн купюры номиналом £50 можно посмотреть в официальном объ- явлении по адресу: https://www.bankofengland.co.uk/news/2019/july/
50-pound-banknote-character-announcement.
2. См. замечательную биографию, составленную Эндрю Ходжесом (1983).
Роль Тьюринга во взломе немецкой шифровальной машины Энигма осве- щена в фильме «Игра в имитацию», вышедшем в 2014 году.
3. Описание машины доступно в [Тьюринг, 1937, 1938].
4. Пример машины Тьюринга позаимствован из [Джон Хопкрофт, Раджив
Мотвани и Джефри Уллман, 2001, глава 8]. Рисунок основан на примере
Себастьяна Сардины, доступном по адресу: http://www.texample.net/tikz/
examples/turing-machine-2/.
5. Подробности о тезисе Черча — Тьюринга см. [Льюис и Пападимитрио,
1998, глава 5]. Обсуждение истории тезиса Черча — Тьюринга и его раз- личных вариантов можно найти в [Копленд и Шагрир, 2019].

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 183
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Algorismus 15
directed acyclic graph 43
IBM 75
NASA 100
O большое 32
PageRank 11
Pink Floyd 19
автоматическое дифференцирование
149
Алан Тьюринг 150
алгоритм PageRank 97
алгоритм Евклида 22
алгоритмическая эра 13
алгоритм обратного распространения потери 137
алгоритмы линейного времени 35
Атомарный ключ 77
Ациклический граф 43
Вероятностные алгоритмы 91
Вычислительная сложность 31
Герман Холлерит 74
гиперболический тангенс 124
гиперплоскость 132
гипертекст 98
глубокое обучение 120
Гордон Мур 34
градиент 131
граница решений 125
графы 39
Двоичный поиск 70
ДНК 44
жадные алгоритмы 49
задача коммивояжера 37
Задача о секретаре 67
задача о семи кёнигсбергских мостах
38
Закон Мура 34
Иоганн Кеплер 66
Карл Хирхольцер 45
категорийная перекрестная энтропия 144
Квантовые компьютеры 157
Ларри Пейдж 97
Линейный поиск 62
Логлинейное время 36
Локальный оптимум 49
матрица Google 116
матрица гиперссылок 108
Матрица смежности 107
машина Тьюринга 152
машинное обучение 127
Метод перегруппировки 65
метод сортировки строк 84
Мультиграф 41
мультимножество 41
Мухаммад ибн Муса аль-Хорезми 15

наибольший общий делитель 22
нейронные сети 133
обратные ссылки 103
обучение без учителя 127
обучение с учителем 127
организация турнира 46
ориентированный граф 41
переполнение 72
перестановка данных 77
перфокарты 74
перцептрон 124
Поиск восхождением к вершине 49
поразрядная сортировка 81
приблизительный поиск 59
разреженная матрица 118
распознавание образов 138
рейтинговый вектор графа 107
Роберт К. Мертон 64
самоорганизующийся поиск 66
Сантьяго Рамон-и-Кахаль 121
Связный список 61
Сергей Брин 97
сигмоида 124
синапсы 121
скорость изменения функции 130
сортировка вставками 81
сортировка выбором 79
Сортировка данных 75
сортировка слиянием 91
Составной ключ 77
социальная сеть 41
степенной метод 111
степень узла графа 49
тестовый набор данных 127
Управляющие структуры 23
учебный набор данных 127
Факториальная сложность 36
функция softmax 141
Функция активации 123
функция выпрямитель 124
Хроматический индекс 49
частная производная потери 131
число Эйлера 35
эвристики 49
Эдсгер Дейкстра 52
Эйлеров цикл 40
экспоненциальная сложность 36
Экспоненциальный рост 34
эффект Матфея 64
язык программирования 25

БИБЛИОГРАФИЯ 185
БИБЛИОГРАФИЯ
• Alpaydin, Ethem. 2016. Machine Learning. Cambridge, MA: MIT Press.
• Bachrach, Ran, Ran El-Yaniv, and Martin Reinstädtler. 2002. “On the Com- petitive Theory and Practice of Online List Accessing Algorithms.” Algorith-
mica 32 (2): 201–245.
• Barabási, Albert-László, and Pósfai Márton. 2016. Network Science. Cam- bridge: Cambridge University Press.
• Bar-Noy, Amotz, Rajeev Motwani, and Joseph Naor. 1992. “The Greedy Al- gorithm Is Optimal for Online Edge Coloring.” Information Processing Let-
ters 44 (5): 251–253.
• Bearden, J. Neil. 2006. “A New Secretary Problem with Rank-Based Selec- tion and Cardinal Payoff s.” Journal of Mathematical Psychology 50:58–59.
• Benjamin, Arthur, Gary Chartrand, and Ping Zhang. 2015. The Fascinating
World of Graph Theory. Princeton, NJ: Princeton University Press.
• Bentley, Jon. 2000. Programming Pearls. 2nd ed. Boston: Addison-Wesley.
• Berry, Michael W., and Murray Browne. 2005. Understanding Text Engines:
Mathematical Modeling and Text Retrieval. 2nd ed. Philadelphia: Society for
Industrial and Applied Mathematics.
• Biggs, Norman L., E. Keith Lloyd, and Robin J. Wilson. 1986. Graph Theory,
1736–1936. Oxford: Clarendon Press.
• Bjorklund, Eric. 1999. “The Theory of Rep-Rate Pattern Generation in the
SNS Timing System.” SNS-NOTE-CNTRL-99. Spallation Neutron Source.
ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf.
• Bloch, Joshua. 2006. “Extra, Extra — Read All about It: Nearly All Binary
Searches and Mergesorts Are Broken.” Google AI Blog, June 2. googlere-
search.blogspot.it/2006/06/extra-extra-read-all-about-it-nearly.html.
• Brin, Sergey, and Lawrence Page. 1998. “The Anatomy of a Large-Scale Hyper- textual Web Search Engine.” Computer Networks and ISDN Systems 30 (1–7):
107–117.
• Bryan, Kurt, and Tanya Leise. 2006. “The $25,000,000,000 Eigenvector:
The Linear Algebra behind Google.” SIAM Review 48 (3): 569–581.
• Charniak, Eugene. 2018. Introduction to Deep Learning. Cambridge, MA:
MIT Press.

186 БИБЛИОГРАФИЯ
• Compeau, Phillip E. C., Pavel A. Pevzner, and Glenn Tesler. 2011. “How to
Apply de Bruijn Graphs to Genome Assembly.” Nature Biotechnology 29
(11): 987–991.
• Copeland, B. Jack, and Oron Shagrir. 2019. “The Church-Turing Thesis:
Logical Limit or Breachable Barrier?” Communications of the ACM 62 (1):
66–74.
• Demaine, Erik D., Francisco Gomez-Martin, Henk Meijer, David Rappa- port, Perouz Taslakian, Godfried T. Toussaint, Terry Winograd, and David
R. Wood. 2009. “The Distance Geometry of Music.” Computational Geome-
try: Theory and Applications 42 (5): 429–454.
• Dyson, George. 2012. Turing’s Cathedral: The Origins of the Digital Universe.
New York: Vintage Books.
• Elsken, Thomas, Jan Hendrik Metzen, and Frank Hutter. 2018. “Neural Ar- chitecture Search: A Survey.” ArXiv, Cornell University. August 16.

arxiv.org/abs/1808.05377.
• Eulerho, Leonhardo. 1736. “Solutio Problematis Ad Geometrian Situs Per- tinentis.” Commetarii Academiae Scientiarum Imperialis Petropolitanae
8:128–140.
• Ferguson, Thomas S. 1989. “Who Solved the Secretary Problem?” Statisti-
cal Science 4 (3): 282–289.
• Fleischner, Herbert, ed. 1991. “Chapter X Algorithms for Eulerian Trails and
Cycle Decompositions, Maze Search Algorithms.” In Eulerian Graphs and
Related Topics, 50: X.1– X.34. Amsterdam: Elsevier.
• Franceschet, Massimo. 2011. “PageRank: Standing on the Shoulders of Gi- ants.” Communications of the ACM 54 (6): 92–101.
• Friend, Edward H. 1956. “Sorting on Electronic Computer Systems.” Jour-
nal of the ACM 3 (3): 134–168.
• Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning.
Cambridge, MA: MIT Press.
• Hand, David J. 2014. The Improbability Principle: Why Coincidences, Mira-
cles, and Rare Events Happen Every Day. New York: Farrar, Straus and Gir- oux.
• Hawking, Stephen. 1988. A Brief History of Time. New York: Bantam Books.
• Hierholzer, Carl. 1873. “Ueber die Möglichkeit, einen Linienzug ohne Wie- derholung und ohne Unterbrechung zu Umfahren.” Mathematische Annalen
6 (1): 30–32.
• Hoare, C. A. R. 1961a. “Algorithm 63: Partition.” Communications of the
ACM 4 (7): 321.

БИБЛИОГРАФИЯ 187
• Hoare, C. A. R. 1961b. “Algorithm 64: Quicksort.” Communications of the
ACM 4 (7): 321.
• Hoare, C. A. R. 1961c. “Algorithm 65: Find.” Communications of the ACM 4
(7): 321–322.
• Hodges, Andrew. 1983. Alan Turing: The Enigma. New York: Simon and
Schuster.
• Hollerith, Herman. 1894. “The Electrical Tabulating Machine.” Journal of
the Royal Statistical Society 57 (4): 678–689.
• Hopcroft, John E., Rajeev Motwani, and Jeff rey D. Ullman. 2001. Introduc-
tion to Automata Theory, Languages, and Computation. 2nd ed. Boston: Ad- dison-Wesley.
• Iwashita, Hiroaki, Yoshio Nakazawa, Jun Kawahara, Takeaki Uno, and
Shinichi Minato. 2013. “Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions.” Technical Report TCS-
TR-A-13-64. Division of Computer Science, Graduate School of Information
Science, Technology, Hokkaido University.
• Kekulé, August. 1872. “Ueber Einige Condensationsprodukte Des Alde- hyds.” Annalen der Chemie und Pharmacie 162 (1): 77–124.
• Kleinberg, Jon M. 1998. “Authoritative Sources in a Hyperlinked Environ- ment.” In Proceedings of the Ninth Annual ACM-SIAM Symposium on Dis-
crete Algorithms, 668–677. Philadelphia: Society for Industrial and Applied
Mathematics.
• Kleinberg, Jon M. 1999. “Authoritative Sources in a Hyperlinked Environ- ment.” Journal of the ACM 46 (5): 604–632.
• Knuth, Donald E. 1970. “Von Neumann’s First Computer Program.” Com-
puting Surveys 2 (4): 247–261.
• Knuth, Donald E. 1972. “Ancient Babylonian Algorithms.” Communications
of the ACM 15 (7): 671–677.
• Knuth, Donald E. 1997. The Art of Computer Programming, Volume 1: Fun-
damental Algorithms. 3rd ed. Reading, MA: Addison-Wesley.
• Knuth, Donald E. 1998. The Art of Computer Programming, Volume 3: Sort-
ing and Searching. 2nd ed. Reading, MA: Addison-Wesley.
• Knuth, Donald E. 2011. The Art of Computer Programming, Volume 4A:
Combinatorial Algorithms, Part 1. Upper Saddle River, NJ: Addison-Wesley.
• Langville, Amy N., and Carl D. Meyer. 2006. Google’s PageRank and Beyond:
The Science of Search Engine Rankings. Princeton, NJ: Princeton University Press.
• LeCun, Yann, Yoshua Bengio, and Geoff rey Hinton. 2015. “Deep Learning.”
Nature 521 (7553): 436–444.

188 БИБЛИОГРАФИЯ
• Lewis, Harry R., and Christos H. Papadimitriou. 1998. Elements of the The-
ory of Computation. 2nd ed. Upper Saddle River, NJ: Prentice Hall.
• McCabe, John. 1965. “On Serial Files with Relocatable Records.” Opera-
tions Research 13 (4): 609–618.
• McCulloch, Warren S., and Walter Pitts. 1943. “A Logical Calculus of the
Ideas Immanent in Nervous Activity.” Bulletin of Mathematical Biophysics 5
(4): 115–133.
• Merton, Robert K. 1968. “The Matthew Effect in Science.” Science 159
(3810): 56–63.
• Minsky, Marvin, and Seymour Papert. 1969. Perceptrons: An Introduction to
Computational Geometry. Cambridge, MA: MIT Press.
• Misa, Thomas J., and Philip L. Frana. 2010. “An Interview with Edsger
W. Dijkstra.” Communications of the ACM 53 (8): 41–47.
• Mitzenmacher, Michael, and Eli Upfal. 2017. Probability and Computing:
Randomization and Probabilistic Techniques in Algorithms and Data Analysis.
2nd ed. Cambridge: Cambridge University Press.
• Parker, Matt. 2014. Things to Make and Do in the Fourth Dimension: A Math-
ematician’s Journey through Narcissistic Numbers, Optimal Dating Algo-
rithms, at Least Two Kinds of Infinity, and More. London: Penguin Books.
• Pattis, Richard E. 1988. “Textbook Errors in Binary Searching.” SIGCSE Bul-
letin 20 (1): 190–194.
• Pevzner, Pavel A., Haixu Tang, and Michael S. Waterman. 2001. “An Eu- lerian Path Approach to DNA Fragment Assembly.” Proceedings of the Na-
tional Academy of Sciences 98 (17): 9748–9753.
• Pinker, Steven. 2018. Enlightenment Now: The Case for Reason, Science, Hu-
manism, and Progress. New York: Viking Press.
• Rivest, Ronald. 1976. “On Self-Organizing Sequential Search Heuristics.”
Communications of the ACM 19 (2): 63–67.
• Rosenblatt, Frank. 1957. “The Perceptron: A Perceiving and Recognizing
Automaton.” Report 85–460–1. Cornell Aeronautical Laboratory.
• Rumelhart, David E., Geoff rey E. Hinton, and Ronald J. Williams. 1986.
“Learning Representations by Back-Propagating Errors.” Nature 323 (6088):
533–536.
• Silver, David, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre,
George van den Driessche, Julian Schrittwieser, et al. 2016. “Mastering the Game of Go with Deep Neural Networks and Tree Search.” Nature 529
(7587): 484–489.

• Silver, David, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou,
Aja Huang, Arthur Guez, Thomas Hubert, et al. 2017. “Mastering the Game of Go without Human Knowledge.” Nature 550 (7676): 354–359.
• Strogatz, Steven. 2012. The Joy of x: A Guided Tour of Math, from One to In-
finity. New York: Houghton Miffl in Harcourt.
• Taleb, Nassim Nicholas. 2007. The Black Swan: The Impact of the Highly Im-
probable. New York: Random House.
• Toussaint, Godfried T. 2005. “The Euclidean Algorithm Generates Tradi- tional Musical Rhythms.” In Renaissance Banff: Mathematics, Music, Art,
Culture, edited by Reza Sarhangi and Robert V. Moody, 47–56. Winfield, KS:
Bridges Conference, Southwestern College.
• Toussaint, Godfried T. 2013. The Geometry of Musical Rhythm: What Makes
a “Good” Rhythm Good? Boca Raton, FL: CRC Press.
• Turing, Alan M. 1937. “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Soci-
ety S2–42:230–265.
• Turing, Alan M. 1938. “On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction.” Proceedings of the London Math-
ematical Society S2–43:544–546.
• Tyson, Neil deGrasse, Michael Abram Strauss, and Richard J. Gott. 2016.
Welcome to the Universe: An Astrophysical Tour. Princeton, NJ: Princeton
University Press.
• West, Geoffrey. 2017. Scale: The Universal Laws of Life, Growth, and Death in
Organisms, Cities, and Companies. London: Weidenfeld and Nicholson.
• Xiao, Han, Kashif Rasul, and Roland Vollgraf. 2017. “Fashion-MNIST:
A Novel Image Dataset for Benchmarking Machine Learning Algorithms.”
August 28. arxiv.org/abs/1708.07747.

ДЛЯ ДАЛЬНЕЙШЕГО ЧТЕНИЯ
• Broussard, Meredith. 2018. Artificial Unintelligence: How Computers
Misunderstand the World. Cambridge, MA: MIT Press.
• Christian, Brian, and Tom Griffiths. 2016. Algorithms to Live By: The
Computer Science of Human Decisions. New York: Henry Holt and Company.
• Cormen, Thomas H. 2013. Algorithms Unlocked. Cambridge, MA: MIT Press.
• Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford
Stein. 2009. Introduction to Algorithms. 3rd ed. Cambridge, MA: MIT Press.
• Denning, Peter J., and Matti Tedre. 2019. Computational Thinking.
Cambridge, MA: MIT Press.
• Dewdney, A. K. 1993. The (New) Turing Omnibus: 66 Excursions in
Computer Science. New York: W. H. Freeman and Company.
• Dyson, George. 2012. Turing’s Cathedral: The Origins of the Digital Universe.
New York: Vintage Books.
• Erwig, Martin. 2017. Once upon an Algorithm: How Stories Explain
Computing. Cambridge, MA: MIT Press.
• Fry, Hannah. 2018. Hello World: How to Be Human in the Age of the Machine.
London: Doubleday.
• Harel, David, and Yishai Feldman. 2004. Algorithmics: The Spirit of
Computing. 3rd ed. Harlow, UK: Addison-Wesley.
• Louridas, Panos. 2017. Real-World Algorithms: A Beginner’s Guide.
Cambridge, MA: MIT Press.
• MacCormick, John. 2013. Nine Algorithms That Changed the Future: The
Ingenious Ideas That Drive Today’s Computers. Princeton, NJ: Princeton
University Press.
• O’Neil, Cathy. 2016. Weapons of Math Destruction: How Big Data Increases
Inequality and Threatens Democracy. New York: Crown Publishing Group.
• Petzold, Charles. 2008. The Annotated Turing: A Guided Tour through
Alan Turing’s Historic Paper on Computability and the Turing Machine.
Indianapolis: Wiley Publishing.
• Sedgewick, Robert, and Kevin Wayne. 2017. Computer Science: An
Interdisciplinary Approach. Boston: Addison-Wesley.

ОБ АВТОРЕ
Панос Луридас — доцент на кафедре Научных и технических методов управле- ния Афинского университета экономики и бизнеса. Он работает над алгорит- мическими приложениями, проектированием программного обеспечения, безопасностью, практической криптографией и прикладным машинным об- учением. Он автор книги Real-World Algorithms: A Beginner’s Guide, опубли- кованной издательством MIT Press, и уже больше четверти века активно за- нимается программированием.

Все права защищены. Книга или любая ее часть не может быть скопирована, воспроизведена в
электронной или механической форме, в виде фотокопии, записи в память ЭВМ, репродукции или
каким-либо иным способом, а также использована в любой информационной системе без получения
разрешения от издателя. Копирование, воспроизведение и иное использование книги или ее части
без согласия издателя является незаконным и влечет уголовную, административную и гражданскую
ответственность.
Научно-популярное издание
БИБЛИОТЕКА MIT
Луридас Панос
АЛГОРИТМЫ
САМЫЙ КРАТКИЙ И ПОНЯТНЫЙ КУРС
Главный редактор Р. Фасхутдинов
Руководитель направления В. Обручев
Ответственный редактор Е. Истомина
Литературный редактор Р. Болдинова
Младший редактор А. Захарова
Художественный редактор К. Доброслов
Компьютерная верстка Э. Брегис
Корректоры А. Баскакова, Л. Макарова
Страна происхождения: Российская Федерация
Шы.арыл.ан елі: Ресей Федерациясы
Дата изготовления / Подписано в печать 17.02.2022.
Формат 70x100 1
/
16
. Печать офсетная. Усл. печ. л. 15,56.
Тираж экз. Заказ
12+
ООО «Издательство «Эксмо»
123308, Россия, город Москва, улица Зорге, дом 1, строение 1, этаж 20, каб. 2013.
Тел.: 8 (495) 411-68-86.
Home page: www.eksmo.ru E-mail: info@eksmo.ru
ндіруші: «ЭКСМО» А#Б Баспасы,
123308, Ресей, *ала М+скеу, Зорге к/шесі, 1 7й, 1 ;имарат, 20 *абат, офис 2013 ж.
Тел.: 8 (495) 411-68-86.
Home page: www.eksmo.ru E-mail: info@eksmo.ru.
Тауар белгісі: «Эксмо»
Интернет-магазин : www.book24.ru
Интернет-магазин : www.book24.kz
Интернет-дкен : www.book24.kz
Импортёр в Республику Казахстан ТОО «РДЦ-Алматы».
#аза*стан Республикасында;ы импорттаушы «РДЦ-Алматы» ЖШС.
Дистрибьютор и представитель по приему претензий на продукцию, в Республике Казахстан: ТОО «РДЦ-Алматы»
#аза*стан Республикасында дистрибьютор ж+не /нім бойынша арыз-талаптарды
*абылдаушыныJ /кілі «РДЦ-Алматы» ЖШС,
Алматы *., Домбровский к/ш., 3«а», литер Б, офис 1.
Тел.: 8 (727) 251-59-90/91/92; E-mail: RDC-Almaty@eksmo.kz
німніJ жарамдылы* мерзімі шектелмеген.
Сертификация туралы а*парат сайтта: www.eksmo.ru/certifi cation
Сведения о подтверждении соответствия издания согласно законодательству РФ о техническом регулировании можно получить на сайте Издательства «Эксмо»
www.eksmo.ru/certifi cation
ндірген мемлекет: Ресей. Сертификация *арастырылма;ан
ПРИСОЕДИНЯЙТЕСЬ К НАМ! bomborabooks bombora bombora.ru
МЫ В СОЦСЕТЯХ:
БОМБОРА – лидер на рынке полезных и вдохновляющих книг. Мы любим книги и создаем их, чтобы вы могли творить, открывать мир, пробовать новое, расти.
Быть счастливыми. Быть на волне.