Материалы портала «Научная Россия»

0 комментариев 802

Квантовый алгоритм поможет распознать язык Дика

Квантовый алгоритм поможет распознать язык Дика
Ученый КФУ вместе с зарубежными коллегами разработал квантовый алгоритм для распознавания языка Дика

Учёными Казанского федерального университета (КФУ), Квантового центра университета Латвии и университета Парижа был разработан алгоритм для квантовых компьютеров, который распознает язык Дика. Научные результаты представлены в  журнале  Leibniz International Proceedings in Informatics – сообщает пресс-служба КФУ.

Язык Дика — множество правильных скобочных структур вместе с пустой структурой над алфавитом {a, b}. Он назван в честь немецкого алгебраиста Вальтера фон Дика и известен среди информатиков и математиков. Решить задачу Дика, или распознать этот язык значит – осуществить проверку правильности расстановки скобок в тексте – поясняет пресс-служба. Учёные предложили решить эту задачу при помощи квантового компьютера. Несмотря на то, что квантовые компьютеры ещё не созданы, учёные уверены в необходимости создания эффективных квантовых алгоритмов, что будет дополнительно стимулировать физиков к скорейшему созданию квантовых компьютеров и сделает их существование более осмысленным.

Как указывает один из исследователей, старший научный сотрудник НИЛ «Квантовые методы обработки данных» ИВМиИТ КФУ Камиль Хадиев, классическое решение задачи известно уже давно, однако о квантовом алгоритме для задачи до 2018 года никто не задумывался. Известный учёный в мире квантовой информатики Скот Ааронсон и соавторы в тот год привлекли внимание исследователей своей работой, где отметили, что задачу Дика программа для обычного компьютера решала бы год, а на квантовом компьютере ее можно решить за несколько секунд.

Спустя два года международной группой учёных был предложен алгоритм, который для решения этой задачи тратит примерно 40 секунд, и было сделано уточнение, что быстрее, чем за 10 секунд, задача на квантовом компьютере решаться не сможет. 

«Задача Дика предназначена для проверки кода программы и позволяет выяснить, удовлетворяет ли она правилам или нет. Задача Дика, с одной стороны, является важной подзадачей синтаксических анализаторов и компиляторов, а с другой стороны, интересна с теоретической точки зрения», – рассказал Камиль Хадиев.

 

Источник: media.kpfu.ru

квантовый алгоритм язык дика

Назад

Социальные сети

Комментарии

Авторизуйтесь, чтобы оставить комментарий

Информация предоставлена Информационным агентством "Научная Россия". Свидетельство о регистрации СМИ: ИА № ФС77-62580, выдано Федеральной службой по надзору в сфере связи, информационных технологий и массовых коммуникаций 31 июля 2015 года.