Опубликовано в рубрике Исследователи из Копенгагенского университета и Технического университета Дании (DTU) думали, что им осталось пять лет до решения математической загадки 1980-х годов. На самом деле, сами того не зная, они почти решили проблему и только что раскрыли большую часть решения в исследовательской статье. Решение может быть использовано для улучшения телефонов и компьютеров завтрашнего дня.
Якоб Холм и Ева Ротенберг
Двое ученых-информатиков, доцент Джейкоб Холм из UCPH и доцент Ева Ротенберг из DTU чуть не выдали свое решение летом 2019 года, после того как отправили исследовательскую статью, которая стала предшественником статьи, в которой они наконец решили математическую загадку.
Настоящая головоломка. Вот как можно смело описывать эту математическую проблему в дисциплине теории графов. Два математика из Департамента компьютерных наук Копенгагенского университета и DTU решили задачу, над которой самые быстрые и умные люди в мире бились с 1980-х годов.
Двое ученых-информатиков, доцент Джейкоб Холм из UCPH и доцент Ева Ротенберг из DTU чуть не выдали свое решение летом 2019 года, после того как отправили исследовательскую статью, которая стала предшественником статьи, в которой они наконец решили математическую загадку.
«Мы почти отказались от того, чтобы получить последний кусок и разгадать загадку. Мы думали, что получили незначительный результат, интересный, но никоим образом не решили проблему. Мы предполагали, что нам предстоит еще пять лет работы над Лучше всего, прежде чем мы сможем решить загадку », — объясняет Джейкоб Холм, который является частью BARC, отдела алгоритмов Департамента компьютерных наук UCPH.
Читайте также: если вам понравилась новость, и вы хотите получать новости на подобную тематику, переходите на сайт yobit. Там вы сможете найти свежие новости о технологиях, например криптовалюты, искусственный интеллект и многое другое.
Проблема трех коммунальных служб
В 1913 году предшественник решенной математической головоломки был опубликован в «The Strand Magazine» как «Проблема трех служебных программ». Это заставило читателей журнала почесать в затылках и задуматься. В задаче в каждом из трех коттеджей должны быть вода, газ и электричество, а «линии» между домами и водой, электричеством и газом не могут пересекать друг друга, что невозможно.
Решение между строк
Проще говоря, головоломка состоит в том, как соединить несколько точек на графике, не позволяя соединяющим их линиям пересекаться. И как с помощью математического вычисления — алгоритма — вы можете внести изменения в обширную «сеть графов», чтобы гарантировать, что никакие линии не пересекаются, без необходимости начинать все заново. Свойства, которые можно использовать, среди прочего, для строительства огромных дорожных сетей или крошечных внутренностей компьютеров, где электрические схемы на печатных платах не могут пересекаться.
Джейкоб Холм интересовался математической головоломкой с 1998 года, но ответ был обнаружен только тогда, когда два исследователя читали уже присланную исследовательскую статью. Тем временем исследователи узнали о новом математическом методе, который, как они поняли, может быть применен к этой проблеме.
«Читая нашу исследовательскую статью, мы внезапно осознали, что решение было прямо перед нашими глазами. Наша следующая реакция была:« О нет, мы прострелили себе ногу и отдали раствор », — говорит доцент Ева Ротенберг из DTU.
О теории графов
ГРАФИК — это очень простая конструкция, используемая для моделирования вещей, которые можно описать как объекты, и связей между ними. Теория графов — это одновременно область математики и важный инструмент информатики.
В этом контексте граф можно проиллюстрировать диаграммой, состоящей из ряда точек (узлов, вершин), связанных с рядом линий (ребер). Каждое ребро изображено в виде линии (или изогнутой части) с узлами в качестве двух конечных точек.
О решении
В динамических графах есть два типа обновлений: можно удалить ребро и можно вставить новое ребро. Эти две операции должны выполняться пользователем, в то время как алгоритм постоянно отслеживает прорисовку сети. Это алгоритм, рецепт которого нашли исследователи.
Может использоваться для компьютерной электроники
Это было тогда, когда два исследователя занялись написанием исследовательской работы и выяснением деталей, чтобы решить загадку, над которой Холм периодически работал с 1998 года.
«Мы работали над статьей без перерыва, от пяти до шести недель. И в итоге она заняла более 80 страниц», — говорит Ева Ротенберг.
К счастью, никто не смог победить их в решении проблемы, и два исследователя смогли представить свои результаты на основных конференциях по теоретической информатике, которые планировалось провести в Чикаго, но в итоге оказались виртуальными.
Итак, для чего можно использовать решение этой математической головоломки? Двое исследователей не знают наверняка, но у них есть несколько предложений.
«Наше исследование является фундаментальным, поэтому мы редко знаем, для чего оно в конечном итоге будет использоваться. Даже с самого начала нам трудно представить себе приложения», — говорит Джейкоб Холм, добавляя:
«Конструкция микрочипов и печатных плат, присутствующих во всей электронике, может быть областью, в которой наш результат будет использоваться. При рисовании проводов на печатной плате они никогда не должны пересекаться. В противном случае могут возникнуть короткие замыкания. То же самое относится к микрочипы, которые содержат миллионы транзисторов и для которых необходимо иметь графическое изображение ».
