Саймон Сингх - Симпсоны и их математические секреты

Здесь есть возможность читать онлайн «Саймон Сингх - Симпсоны и их математические секреты» — ознакомительный отрывок электронной книги совершенно бесплатно, а после прочтения отрывка купить полную версию. В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. Город: Москва, Год выпуска: 2016, ISBN: 2016, Издательство: Манн, Иванов и Фербер, Жанр: Математика, foreign_edu, Прочая научная литература, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Симпсоны и их математические секреты: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Симпсоны и их математические секреты»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

Саймон Сингх рассказывает о самых интересных эпизодах мультсериала, в которых фигурируют важнейшие математические идеи – от числа π и бесконечности до происхождения чисел и самых сложных проблем, над которыми работают современные математики.
Книга будет интересна поклонникам сериала «Симпсоны» и всем, кто увлекается математикой.
На русском языке публикуется впервые.

Симпсоны и их математические секреты — читать онлайн ознакомительный отрывок

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Симпсоны и их математические секреты», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Другими словами, если Гомер отправится в Спрингфилдский муниципальный дом блинов, как показано в эпизоде «Запутанный мир Мардж Симпсон» (The Twisted World of Marge Simpson, сезон 8, эпизод 11; 1997 год), и официант принесет ему n блинов разных размеров, уложенных в случайном порядке, то сколько переворотов ему потребуется сделать в самом худшем случае, для того чтобы расположить блины правильно? Число переворотов блинов обозначается как P n . Задача состоит в том, чтобы найти формулу определения числа P n .

Задача блинной сортировки сразу же привлекла внимание математиков по двум причинам. Во-первых, было похоже, что она позволит лучше понять способы решения задач по информатике, поскольку перегруппировка блинов имеет много общего с перегруппировкой данных. Во-вторых, эта головоломка казалась достаточно трудной, а математики просто обожают задачи, граничащие с невозможным.

Несколько простых примеров могут пролить свет на эту задачу. Во-первых, чему равно число переворотов, если в наличии всего один блин? Ответ: нулю, поскольку этот блин не может лежать неправильно. Следовательно, P 1= 0.

Чему равно число переворотов в случае двух блинов? Тут может быть только два варианта: либо их уложили правильно, либо в обратном порядке. Определить худший случай не составит труда, причем потребуется всего один переворот, для того чтобы обеспечить правильное расположение блинов. Следовательно, P 2= 1.

Далее, чему равно число переворотов в случае трех блинов? Вычислить это немного труднее, так как существует шесть вариантов их исходного порядка. И в зависимости от него число переворотов, необходимое для расположения блинов в правильном порядке, составляет от ноля до трех в самом худшем случае. Следовательно, P 3= 3.

В большинстве случаев вы сами можете уложить блины в нужном порядке с помощью - фото 29

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

По мере увеличения стопки блинов задача усложняется в связи с ростом количества - фото 30

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

Изза сложности выполнения всех перестановок и возможных стратегий - фото 31

Из-за сложности выполнения всех перестановок и возможных стратегий переворачивания блинов даже очень мощным компьютерам до сих пор не удалось рассчитать число переворотов в случае двадцати блинов. Кроме того, даже три десятилетия спустя никто не смог отказаться от метода решения «в лоб» с помощью компьютера и найти красивое уравнение для определения числа переворотов блинов. На данный момент единственным достижением в решении этой задачи стало выведение формулы определения границ для числа переворотов блинов. В 1979 году было доказано, что верхняя граница для числа переворотов составляет (5 n + 5)/3 переворотов. Это значит, что мы можем взять бессмысленно огромное количество блинов (скажем, тысячу) и точно знать, что число переворотов, необходимых для их укладки в порядке возрастания (или убывания) размера, будет меньше, чем:

Таким образом учитывая что выполнить треть переворота невозможно меньше или - фото 32

Таким образом, учитывая, что выполнить треть переворота невозможно, меньше или равно 1668. Этот знаменитый результат, поскольку он был опубликован в работе Христоса Пападимитриу и Уильяма Гейтса, который нам больше известен как Билл Гейтс, основатель компании Microsoft, а эта работа считается его единственной научной публикацией.

В работе Гейтса, написанной им в период учебы в Гарвардском университете, упоминается также более сложный вариант этой задачи. В задаче о подгоревших блинах фигурируют блины, подгоревшие с одной стороны, которые необходимо уложить в правильном порядке, переворачивая так, чтобы подгоревшая сторона оказывалась внизу. Именно эту задачу решил Дэвид Коэн во время учебы в Беркли.

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Симпсоны и их математические секреты»

Представляем Вашему вниманию похожие книги на «Симпсоны и их математические секреты» списком для выбора. Мы отобрали схожую по названию и смыслу литературу в надежде предоставить читателям больше вариантов отыскать новые, интересные, ещё непрочитанные произведения.


Отзывы о книге «Симпсоны и их математические секреты»

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

x