Примечания книги Кому нужна математика? Понятная книга о том, как устроен цифровой мир. Автор книги Нелли Литвак, Андрей Райгородский

1

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

2

Отсылка к знаменитому одноименному роману лауреата Нобелевской премии Германа Гессе. Прим. ред.

3

В приложении 2 к главе 2 для подготовленного читателя мы более подробно рассматриваем еще один маленький пример составления расписаний.

4

В приложении 3 к главе 2 мы объясняем для заинтересованного читателя основные идеи этого метода более подробно. Заметим, что это объяснение не требует математической подготовки.

5

Для интересующихся читателей в приложении 1 к главе 3 мы приводим вычисления числа последовательностей из нулей и единиц заданной длины.

6

Для подготовленного читателя в приложении 2 к главе 3 приведена точная формула границы Хэмминга и ее доказательство в общем случае.

7

Такой остров действительно есть, его население составляет 4,5 тысяч человек; кенгуру там гораздо больше!

8

В приложении 1 к главе 4 для подготовленного читателя приведены формулы, которыми мы воспользовались при подготовке в табл. 4.1, в общем виде.

9

В приложениях для подготовленного читателя мы будем придерживаться математической терминологии: «вершины» и «ребра».

10

В приложении 2 к главе 4 мы приводим математическую формулировку теоремы Эрдеша – Реньи о фазовом переходе.

11

В приложении 3 к главе 4 мы приводим идею доказательства результата Эрдеша – Реньи в более точной математической формулировке. Подробно это доказательство рассматривается в книге Андрея «Модели случайных графов» (Райгородский A. M. Модели случайных графов. 2-е изд. М.: МЦНМО, 2016.).

12

В приложении к главе 5 мы приводим более формальное математическое объяснение и формулы для подсчета данных, приведенных в табл. 5.1.

13

Заметим, что не нужно путать шифрование и кодирование. Как мы уже рассказывали в главе 3, задачи теории кодирования состоят вовсе не в том, чтобы скрыть от кого-либо информацию. Коды строятся прежде всего для того, чтобы обеспечить бесперебойную передачу данных, в том числе и тех, которые подвержены помехам и искажениям. А вот шифрование – это как раз «сокрытие информации от посторонних». Этим и занимается криптография.

14

См. https://www.youtube.com/watch?v=G2_Q9FoD-oQ; https://www.youtube.com/watch?v=V4V2bpZlqx8.

15

Источник: Prime Pages https://primes.utm.edu/howmany.html.

16

В приложении 2 к главе 6 мы более подробно рассказываем о выборе р и g.

17

В приложении 1 к главе 6 мы приводим простое доказательство, что по схеме Диффи – Хеллмана Боб и Алиса получат одно и то же число.

18

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/.

19

http://www.cnet.com/news/crypto-class-bans-foreign-students/.

20

https://www.eff.org/fr/cases/bernstein-v-us-dept-justice.

21

https://www.schneier.com/blog/archives/2015/05/the_logjam_and_.html.

22

В приложении 1 к главе 7 объясняется, откуда возникает двойной логарифм.

23

Помимо поисковых систем аукционами второй цены пользуется корпорация электронной торговли eBay.

24

В приложении к главе 8 приведено более формальное доказательство совместимости по стимулам в аукционе второй цены.

25

Для читателей с математической подготовкой, которых заинтересовала теория аукционов и три Нобелевские премии, рекомендуем видеолекцию Алексея Савватеева (Савватеев А. Теория аукционов. Наиболее значимые достижения [Электронный ресурс]. – Режим доступа: https://www.youtube.com/watch?v=fCIU07zg9HQ&feature=youtu.be.), где он подробно и очень доходчиво объясняет математическую сторону вопроса.

26

На самом деле, если нужно выбрать два разных сервера, эта вероятность равна

но это значение очень близко к u²_k, когда n достаточно велико.

1

Holt Charles С. Learning how to plan production, inventories, and work force // Operations Research, 50(l):96–99, 2002.

2

Канторович Л. В. Об одном эффективном методе решения некоторых классов экстремальных проблем // Докл. АН СССР. 1940. Том 28. С. 212–215.

3

Bixby E. Robert. A brief history of linear and mixed-integer programming computation. Documenta Mathematica, p. 107–121, 2012.

4

Kroon Leo, Huisman Dennis, Abbink Erwin, Fioole Pieter-Jan, Fischetti Matteo, Maroti Gabor, Schrijver Alexander, Steenbeek Adri and Ybema Roelof. The new dutch timetable: The or revolution // Interfaces, 39(1):6–17, 2009.

5

Shannon Claude Elwood. A mathematical theory of communication // The Bell System technical Journal, 27:379–423, 623–656, 1949.

6

Слоэн Н. Дж. А., Мак-Вильямс Ф. Дж. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.

7

Спенсер Дж., Алон Н. Вероятностный метод. М.: Бином. Лаборатория знаний, 2007.

8

Keevash Peter. The existence of designs // arXiv preprint arXiv.H01.3665, 2014.

9

Renyi A. and Erdos P. On random graphs // Publicationes Mathematicae, 6(290–297):5, 1959.

10

Erdos Paul and Renyi Alfred. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5:17–61, 1960.

11

Albert Reka, Jeong Hawoong and Barabasi Albert-Laszlo. Error and attack tolerance of complex networks // Nature, 406(6794):378–382, 2000.

12

Doyle J. C., Alderson D. L., Li L., Low S., Roughan M., Shalunov S., Tanaka R. and Willinger W. The «robust yet fragile» nature of the Internet. PNAS, 102(41): 14497–14502, 2005.

13

Mahadevan P., Krioukov D., Fall K. and Vahdat A. Systematic topology analysis and generation using degree correlations // ACM SIGCOMM Computer Communication Review, 36(4):135–146, 2006.

14

Eager Derek L., Lazowska Edward D. and Zahorjan John. Adaptive load sharing in homogeneous distributed systems. Software Engineering, IEEE Transactions on, (5): 662–675, 1986.

15

Введенская Н. Д. Система обслуживания с выбором наименьшей из двух очередей – асимптотический подход / Н. Д. Введенская, Р. Л. Добрушин, Ф. И. Карпелевич // Проблемы передачи информации. – 1996. – № 32 (1). – С. 20–34.

16

Richa Andrea W., Mitzenmacher M. and Sitaraman R. The power of two random choices: A survey of techniques and results // Combinatorial Optimization, 9:255–304, 2001.

17

Richa Andrea W., Mitzenmacher M. and Sitaraman R. The power of two random choices: A survey of techniques and results // Combinatorial Optimization, 9:255–304, 2001.

18

Adrian David, Bhargavan Karthikeyan, Durumeric Zakir, Gaudry Pierrick, Green Matthew, et al. Imperfect forward secrecy: How diffie-hellman fails in practice // Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, p. 5–17. ACM, 2015.

19

Adrian David, Bhargavan Karthikeyan, Durumeric Zakir, Gaudry Pierrick, Green Matthew, et al. Imperfect forward secrecy: How diffie-hellman fails in practice // Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, p. 5–17. ACM, 2015.

20

Heule Stefan, Nunkesser Marc and Hall Alexander. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm // Proceedings of the 16th International Conference on Extending Database Technology, pp. 683–692. ACM, 2013.

21

Sketch of the day: Hyperloglog – cornerstone of a big data infrastructure. http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/. Accessed: 2015-11-22.

22

Flajolet Philippe, Fusy Eric, Olivier G. and Meunier Frederic. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm // Philippe Jacquet, editor, Analysis of Algorithms 2007 (AofA07), volume AH of Discrete Mathematics and Theoretical Computer Science Proceedings, p. 127–146, 2007.

23

Sketch of the day: Hyperloglog – cornerstone of a big data infrastructure. http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/. Accessed: 2015-11-22.

24

Heule Stefan, Nunkesser Marc and Hall Alexander. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm // Proceedings of the 16th International Conference on Extending Database Technology, pp. 683–692. ACM, 2013.

25

Backstrom Lars, Boldi Paolo, Rosa Marco, Ugander Johan and Vigna Sebastiano. Four degrees of separation // Proceedings of the 4th Annual ACM Web Science Conference, p. 33–42. ACM, 2012.

26

Sketch of the day: Hyperloglog – cornerstone of a big data infrastructure. http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/. Accessed: 2015-11-22.

27

Backstrom Lars, Boldi Paolo, Rosa Marco, Ugander Johan and Vigna Sebastiano. Four degrees of separation // Proceedings of the 4th Annual ACM Web Science Conference, p. 33–42. ACM, 2012.

28

Heule Stefan, Nunkesser Marc and Hall Alexander. Hyperloglog in practice: Algorithmic engineering of a state of the art cardinality estimation algorithm // Proceedings of the 16th International Conference on Extending Database Technology, pp. 683–692. ACM, 2013.

29

Sketch of the day: Hyperloglog – cornerstone of a big data infrastructure. http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/. Accessed: 2015-11-22.

30

Vickrey William. Counterspeculation, auctions, and competitive sealed tenders // The Journal of finance, 16(l):8–37, 1961.

31

Easley David and Kleinberg Jon. Networks, crowds, and markets: Reasoning about a highly connected world. Cambridge University Press, 2010.

32

Stokes Donald E. Pasteur’s quadrant: Basic science and technological innovation. Brookings Institution Press, 2011.

33

Райгородский A. M. Модели случайных графов. 2-е изд. М.: МЦНМО, 2016.

34

Введенская Н. Д. Система обслуживания с выбором наименьшей из двух очередей – асимптотический подход / Н. Д. Введенская, Р. Л. Добрушин, Ф. И. Карпелевич // Проблемы передачи информации. – 1996. – № 32 (1). – С. 20–34.

35

Виноградов И. М. Основы теории чисел. М. – Ижевск: НИЦ «Регулярная и хаотическая динамика, 2003.

36

Flajolet Philippe, Fusy Eric, Olivier G. and Meunier Frederic. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm // Philippe Jacquet, editor, Analysis of Algorithms 2007 (AofA07), volume AH of Discrete Mathematics and Theoretical Computer Science Proceedings, p. 127–146, 2007.