Кому нужна математика? Понятная книга о том, как устроен цифровой мир - [9]
В 2007 году Биксби провел впечатляющий эксперимент. Он взял все версии пакета CPLEX, начиная с его первого появления в 1991 году, и опробовал их на большом количестве известных практических задач целочисленного линейного программирования. Ученые собрали внушительные коллекции таких задач. Биксби выбрал из них 1892, а затем сравнил скорость их решения, от версии к версии, на одном и том же компьютере.
Оказалось, что за 15 лет скорость решения увеличилась в 29 000 раз! Интересно, что самое большое ускорение, почти десятикратное, произошло в 1998 году, причем не случайно. До этого математики в течение 30 лет разрабатывали новые теории и методы, из которых очень мало было внедрено в практику. В 1998 году в версии CPLEX6.5 была поставлена задача реализовать по максимуму все эти идеи. В результате наши возможности в линейном программировании вышли на качественно новый уровень.
Процесс продолжается. Gurobi появился в 2009 году и к 2012-му ускорился в 16,2 раза. А общий эффект в 1991–2012 годах – в 29000×16,2 раз! Повторим, что это произошло независимо от скорости компьютера, иными словами, исключительно благодаря развитию математических идей.
Если верить закону Мура, то за 1992–2012 годы компьютеры ускорились примерно в 8000 раз. Сравните с почти полумиллионным ускорением алгоритмов! Получается, что если вам нужно решить задачу линейного программирования, то лучше использовать старый компьютер и современные методы, чем наоборот, новейший компьютер и методы начала 1990-х.
Мы не устаем восхищаться прогрессом компьютерных технологий. При этом математика достигла гораздо большего прогресса, и никто даже не заметил! Многогранники, плоскости, двойственные задачи и разветвления зашиты в программных пакетах и решают задачи планирования, как будто так было всегда и в этом нет ничего особенного.
Конечно, самое поразительное – совместный эффект математики и компьютеров. Ускорение в 4 миллиарда раз. Задачи, на которые требовалось 126 лет в 1991 году, в 2012-м мы научились решать за одну секунду! И это не предел. В статье 2015 года Димитрис Бертсимас и Анжела Кинг из Массачусетского технологического института приводят новую цифру – 450 миллиардов – и предлагают новые приложения линейного программирования в статистике.
При столь невероятной эффективности для линейного программирования открываются новые горизонты, немыслимые ранее, но вполне реальные сегодня.
Расписание движения поездов на голландских железных дорогах
Самая престижная награда в исследовании операций – премия Франца Эдельмана за выдающиеся успехи науки в приложениях. В 2008 году ее получили Железные дороги Нидерландов за новое железнодорожное расписание, которое начало действовать в 2006 году.
Нидерланды – маленькая, но густонаселенная страна. На территории размером примерно с Нижегородскую область проживает около 17 миллионов человек. Железные дороги – основа всей голландской логистики. Многие каждый день ездят на поезде на работу. Совещание в другом конце страны – обычное дело. Голландцы – чемпионы Европы по пассажирским железнодорожным перевозкам. В 2006 году Железные дороги Нидерландов перевезли 15,8 миллиарда пассажиров.
До 2006 года действовало расписание, составленное в 1970 году. Перевозки увеличивались, составы постепенно удлинялись, а где возможно, добавлялись новые поезда. Пока наконец к началу 2000-х увеличивать перевозки в рамках старого расписания стало невозможно. Прокладывать новые пути фактически тоже невозможно из-за их безумной дороговизны, да и просто нехватки земли. Железнодорожные пути в Нидерландах строились и расширялись очень мало еще со времен Второй мировой войны. Задача, которая встала перед менеджментом железных дорог, – обеспечить требуемый объем перевозок при имеющейся инфраструктуре. Как это сделать? В 2002 году было решено составить новое расписание.
Расписание железных дорог – дело очень сложное. Нужно, чтобы два поезда одновременно не претендовали на один и тот же участок рельсов. Маршруты с пересадками тоже должны быть удобными, без получасового ожидания на платформе. Кроме того, нужно распределить пути прибытия и отправления на каждой станции, определить количество и тип вагонов для каждого состава, составить расписание кондукторов и машинистов. И все это для 5500 поездов в день!
Над задачей работала целая команда математиков. Основные сложности и идеи они описали в статье{4}, за которую им была присуждена премия Эдельмана.
Каждый этап составления расписания требовал новой модели и новых подходов. Некоторые задачи, например распределение путей прибытия и отправления, после нескольких шагов предварительной подготовки удалось решить с помощью пакета CPLEX. Задача расписания движения поездов упрощалась благодаря цикличности: поезда отправляются в одно и то же время каждый час. Но даже в этом случае коммерческие пакеты оказались бессильны. Справиться с задачей помогли новые математические идеи. Внедрение не сразу прошло гладко. И все же теперь больше поездов перевозит больше людей по тем же рельсам. Пассажиропоток увеличивается, но расписание по-прежнему справляется. В рамках старого расписания это было бы невозможно.
Эта книга — уникальный путеводитель в мире высшего образования для абитуриентов и их родителей. Автор — математик и увлеченный, талантливый педагог — знает изнутри систему высшего образования в России и Голландии, имеет богатый опыт работы со студентами разных специальностей из разных стран. Нелли Литвак нашла понятную формулу «попадания в призвание» и предлагает семь правил, которые помогут любому старшекласснику сделать обоснованный индивидуальный выбор. Как понять, какая профессия подходит именно вам? Что необходимо знать о вузе и учебной программе и как извлечь максимальную пользу за предстоящие годы инвестиций в самого себя? Абитуриентам книга даст отправные точки для поиска и выбора специальности, а родителям подскажет, как избежать конфликтов с детьми и поддержать их в принятии одного из главных решений в жизни.
По статистике, голландские дети – самые счастливые в мире. Именно в этой стране живет и растит двух девочек автор книги Нелли Литвак. Будучи успешным профессионалом, она тем не менее одним из главных своих достижений считает хорошие отношения со старшей дочерью. А доверительные отношения в семье психологи рассматривают как отправную точку благоприятного становления личности. Наблюдая педагогические успехи и провалы родителей и учителей, семейный и школьный уклад нескольких поколений в России и в Голландии, сравнивая традиции образования и воспитания, Нелли Литвак решила систематизировать собственные методы и накопленный опыт и поделиться ими с другими.
Перед вами первое подробное исследование норм жизни населения России после Второй мировой войны. Рассматриваются условия жизни в городе в период сталинского режима. Основное внимание уделяется таким ключевым вопросам, как санитария, доступ к безопасному водоснабжению, личная гигиена и эпидемический контроль, рацион, питание и детская смертность. Автор сравнивает условия жизни в пяти ключевых промышленных районах и показывает, что СССР отставал от существующих на тот момент норм в западно-европейских странах на 30-50 лет.
В книге воспоминаний заслуженного деятеля науки РФ, почетного профессора СПбГУ Л. И. Селезнева рассказывается о его довоенном и блокадном детстве, первой любви, дипломатической работе и службе в университете. За кратким повествованием, в котором отражены наиболее яркие страницы личной жизни, ощутимо дыхание целой страны, ее забот при Сталине, Хрущеве, Брежневе… Книга адресована широкому кругу читателей.
Содержание антологии составляют переводы автобиографических текстов, снабженные комментариями об их авторах. Некоторые из этих авторов хорошо известны читателям (Аврелий Августин, Мишель Монтень, Жан-Жак Руссо), но с большинством из них читатели встретятся впервые. Книга включает также введение, анализирующее «автобиографический поворот» в истории детства, вводные статьи к каждой из частей, рассматривающие особенности рассказов о детстве в разные эпохи, и краткое заключение, в котором отмечается появление принципиально новых представлений о детстве в начале XIX века.
Монография впервые в отечественной и зарубежной историографии представляет в системном и обобщенном виде историю изучения восточных языков в русской императорской армии. В работе на основе широкого круга архивных документов, многие из которых впервые вводятся в научный оборот, рассматриваются вопросы эволюции системы военно-востоковедного образования в России, реконструируется история военно-учебных заведений лингвистического профиля, их учебная и научная деятельность. Значительное место в работе отводится деятельности выпускников военно-востоковедных учебных заведений, их вкладу в развитие в России общего и военного востоковедения.
Как цикады выживают при температуре до +46 °С? Знают ли колибри, пускаясь в путь через воды Мексиканского залива, что им предстоит провести в полете без посадки около 17 часов? Почему ветви некоторых деревьев перестают удлиняться к середине июня, хотя впереди еще почти три месяца лета, но лозы и побеги на пнях продолжают интенсивно расти? Известный американский натуралист Бернд Хайнрих описывает сложные механизмы взаимодействия животных и растений с окружающей средой и различные стратегии их поведения в летний период.
Немногие культуры древности вызывают столько же интереса, как культура викингов. Всего за три столетия, примерно с 750 по 1050 год, народы Скандинавии преобразили северный мир, и последствия этого ощущаются до сих пор. Викинги изменили политическую и культурную карту Европы, придали новую форму торговле, экономике, поселениям и конфликтам, распространив их от Восточного побережья Америки до азиатских степей. Кроме агрессии, набегов и грабежей скандинавы приносили землям, которые открывали, и народам, с которыми сталкивались, новые идеи, технологии, убеждения и обычаи.