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