Разработан новый высокопроизводительный метод проверки графа на планарность: простое решение с огромной производительностью

Два специалиста по информатике нашли в весьма неожиданном месте идею, которая как раз пригодилась им для прорыва в теории графов.  октябре 2019 Якоб Хольм и Ева Ротенберг пролистывали новую работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное. Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад. Хольм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму», — сказал Хольм, специалист по информатике из Копенгагенского университета. «Возможно, мы полностью раскрыли этот вопрос». Парочка поспешила приступить к работе над новой статьёй. Они представили её в июне на симпозиуме по вычислительной теории, проводимом Ассоциацией вычислительной техники, где подробно описали метод проверки графа на планарность, превосходящий предыдущий вариант экспоненциально.

Читать далее

Из истории теоретической физики или как нам удалось анализировать макрообъекты без погружения на молекулярный уровень их строения

Перенормировка, возможно, оказалась самым важным прорывом в теоретической физике за последние 50 лет. Не нужно анализировать поведение отдельных молекул воды, чтобы понять поведение капель, или анализировать капли, чтобы понять волны. Возможность переключать фокус между разными масштабами – это и есть суть перенормировки. В 1940-х годах физики-первопроходцы наткнулись на новый слой реальности. Место частиц заняли поля – всеобъемлющие и волнующиеся сущности, заполнявшие всё пространство на манер океана. Одна небольшая рябь в таком поле могла обозначать электрон, другая – фотон, а их взаимодействия, судя по всему, могли объяснить все электромагнитные явления. Была только одна проблема – вся эта теория держалась на надеждах и молитвах. Только при помощи такой техники, как “перенормировка“, позволявшей тщательно скрывать бесконечные величины, исследователи могли обойти бессмысленные предсказания этой теории. Схема работала, но даже те, кто разрабатывал эту теорию, подозревали, что она может оказаться карточным домиком, держащимся за счёт извращённого математического трюка.

Читать далее

Невозможные события и их математическая интерпретация: иллюзия возможностей и реальность

Математики давно пытаются привыкнуть к тому, что некоторые задачи в принципе невозможно решить. Мы любим повторять, что всё возможно. В книге Джастера Нортона «Мило и волшебная будка» король отказывается сообщить Мило, что его цель недостижима, поскольку «многое становится возможным, если не знаешь, что оно невозможно» [правда, это слова других персонажей книги / прим. перев.]. Но в реальном мире некоторые вещи и вправду невозможны, и мы можем доказать это при помощи математики. Люди используют термин «невозможно» разными способами. Он может описывать просто маловероятные вещи – такие, как найти две одинаковых колоды перемешанных карт. Он может описывать задачи, практически невозможные по причине отсутствия времени, места или ресурсов – такие, как переписать всю Библиотеку Конгресса от руки. Устройства типа вечного двигателя невозможны физически, поскольку их существование противоречило бы нашему пониманию физики. Математическая невозможность – это другое. Мы начинаем с недвусмысленных предположений, и, используя математические рассуждения и логику, заключаем, что некоторые исходы событий невозможны.

Читать далее

Научные версии возникновения сверхпроводимости в теории и эксперименте: кратко о главном

Есть такое природное явление, которое ученые называют сверхпроводимостью, а инженеры — «будущим энергетики, медицины, скоростного транспорта и военного дела». Несмотря на то, что первые сверхпроводящие материалы были открыты более ста лет назад, применять их научились сравнительно недавно и лишь в нескольких довольно специфических приборах вроде Большого адронного коллайдера или в магнитно-резонансной томографии. Почему? Потому что мы до сих пор не до конца понимаем, как это явление работает. В новом материале мы постарались максимально коротко и просто рассказать о нескольких научных версиях возникновения сверхпроводимости, разобравшись с которыми вы поймете, над чем вот уже столетие ломают голову физики всего мира. Так что же такое сверхпроводимость? Это свойство некоторых веществ обладать строго нулевым сопротивлением ниже определенной температуры — ее называют критической.

Читать далее

Разработан кольцевой метаматериал, поглощающий за счет своей структуры более 90% акустических волн

«Современные звукоизоляторы – в буквальном смысле толстые стенки», – говорят исследователи из команды профессора Бостонского университета Синь Чжана (Xin Zhang). Их проект на традиционные подходы совсем не похож: в нем используется метаматериал, уникальные свойства которого определяются не его составом, а деталями формы и структуры. В статье, опубликованной в журнале Physical Review B, ученые описывают и демонстрируют такую структуру – открытую, похожую на серию колец, сквозь которые может течь свободный поток воздуха, но при этом почти ни один звук не вырывается наружу. Физики начали с математического моделирования такой формы и размеров метаматериала, которые смогут эффективно перенаправлять акустические волны обратно к своему источнику. Произведя такую структуру с помощью 3D-принтера, ученые закрепили ее на конце пластиковой трубы, у противоположного конца которой был размещен динамик.

Читать далее

Обнаружена сверхпроводимость у углеродсодержащего сероводорода при комнатной температуре

На фото: Установка для исследования сверхпроводящих материалов при высоких давлениях (Adam Fenster). Американские физики обнаружили сверхпроводимость у углеродсодержащего сероводорода при комнатной температуре. Сверхпроводимость твердого материала на основе сероводорода H3S и метана CH4 сохраняется до 15 градусов Цельсия, однако эффект наблюдается при давлении больше 1,4 миллиона атмосфер. Сверхпроводник представляет собой твердую фазу включения с максимальной критической температурой при давлении 2,67 миллиона атмосфер, пишут ученые в Nature. Традиционно сверхпроводимость — возможность проводить электрический ток с нулевым сопротивлением — считалась свойством материала, которое можно наблюдать только при совсем низких температурах. Первое поколение сверхпроводников теряло сверхпроводимость при температурах лишь на 30 градусов выше абсолютного нуля (это не больше −240 градусов Цельсия). В 80-е годы XX века были обнаружены первые «высокотемпературные сверхпроводники» — керамические материалы на основе смешанного оксида меди. Они теряют сверхпроводимость уже при значительно более высоких температурах, но все еще заметно ниже комнатной: так, в течение двух десятилетий рекордсменом высокотемпературной сверхпроводимости был купрат состава HgBa2Ca2Cu3O8+x, с температурой перехода −109 градусов Цельсия.

Читать далее

Создана суперхиральная метаповерхность отражающая свет с нарушением геометрической симметрии

Фото: Hend Sroor, et al. / Nature Photonics, 2020. Физикам впервые удалось создать хиральный свет с произвольным угловым моментом при помощи метаповерхности. Ученые показали, что построенная система позволяет создавать свет с рекордно высоким угловым моментом. Работа опубликована в журнале Nature PhotonicsХиральность — термин, который используют для систем, в которых отсутствует зеркальная симметрия. Часто его применяют в химии для характеристики соединений. Например, химические соединения ароматов лимона и апельсина отличаются только хиральностью, то есть они идентичные с точностью до зеркального отображения. Физические объекты, такие как свет, тоже обладают хиральностью. В общем случае хиральный свет несет спиновый и орбитальный угловые моменты. Теоретически, эти угловые моменты можно контролировать, что ведет к созданию структурированного света, однако на практике контроль хиральности — сложная, но весьма актуальная задача. Структурированный свет можно использовать для оптического контроля молекул, метрологии и коммуникации.

Читать далее

Разработана сверхбыстрая видеосъемка со скоростью полтриллиона кадров в секунду для работы в ультрафиолетовом диапазоне

Ученые адаптировали метод сжатой сверхбыстрой фотографии для съемки в ультрафиолетовом диапазоне и предложили алгоритм, который эффективнее справился с восстановлением изображения. Комбинация двух этих разработок позволила ученым фиксировать единичные или очень редкие события со скоростью полтриллиона кадров в секунду. Работа опубликована в журнале Laser & Photonics Reviews. Сжатую сверхбыструю фотографию в 2014 году впервые продемонстрировала группа ученых из Университета Вашингтона в Сент-Луисе. Им удалось создать сверхбыструю камеру, которая позволяла делать до ста миллионов кадров в секунду. За шесть лет подобные камеры совершенствовались не только с точки зрения самого устройства, но и алгоритмов обработки изображений. Дело в том, что информация об объекте, которую получается компьютер непосредственно с камеры требует дополнительной обработки, поэтому скорость метода и его качество зависит и от алгоритма обработки. Несмотря на то, что появилось множество новых улучшенных скоростных камер, они все еще могут регистрировать свет только в видимом и инфракрасном диапазоне, но не в ультрафиолетовом (УФ).

Читать далее

Исследования столкновения ультрарелятивистских ядер свинца на БАК показали следы рождения топ-кварков

Иллюстрация: CMS / CERN. Эксперимент CMS увидел следы рождения топ-кварков в столкновениях ультрарелятивистских ядер свинца на Большом адронном коллайдере со статистической точностью в 4 σ. Ранее рождение этой самой тяжелой элементарной частицы наблюдали только в протон-протонных и протон-ядерных столкновениях. Ожидается, что рождающиеся в столкновениях ядро-ядро топ-кварки помогут физикам пронаблюдать эволюцию кварк-глюонной плазмы с течением времени и лучше изучить ее свойства. О полученных результатах сообщается в препринте статьи, а недавно она была принята к публикации в журнале Physical Review Letters. Топ-кварк — кварк третьего поколения, самый тяжелый из шести кварков, а также в принципе самая тяжелая из известных элементарных частиц. Впервые он был обнаружен 25 лет назад на Тэватроне в Фермилабе в столкновениях пар протон-антипротон, где в дальнейшем и были изучены ее основные свойства. Согласно предсказаниям Стандартной модели время жизни топ-кварка составляет всего 5 × 10-25 секунды, что на порядок меньше характерного времени сильного взаимодействия. Благодаря этой особенности он не адронизируется (в отличие от всех остальных кварков), что делает его идеальной частицей для изучения материи, в которой он образуется.

Читать далее