Рубрика «Новости»

Об изоморфизме графов (P vs. NP)

László Babai

Кажется, есть некоторое, довольно серьезное, продвижение в задаче об изоморфизме графов. 10 ноября математик Ласло Бабаи (László (Laci) Babai) расскажет о новом алгоритме, который позволяет решить задачу об изоморфизме графов за квазиполиномиальное время. Объявление об этом имеется на сайте Чикагского университета.

Задача об изоморфизме графов является одной из “математических болезней”. Самый быстрый известный алгоритм, позволяющий определить, изоморфны ли два данные графа, принадлежит Бабаи и Лаксу. Этот алгоритм был предложен в 1983 году. Время его работы — e^{\sqrt{n\log n}}. Если верить объявлению, Бабаи уменьшил это время до e^{{\rm polylog}(n)} ({\rm polylog}(n) — некоторый полином от \log\, n). Таким образом, одна из важнейших задач оказывается чуть-чуть более, чем P.

А теперь немного о самом Ласло Бабаи. Он родился в 1950 году в Будапеште. Работает профессором математики и информатики в Чикагском университете. Главным образом занимается комбинаторикой, теорией сложности вычислений, алгоритмами и конечными группами, особенно интересуется связями между этими областями математики. Наиболее значительные его достижения — это введение интерактивной системы доказательств, введение термина “алгоритм Лас-Вегас” и использование теоретико-групповых методов в проверке графов на изоморфизм. Читать полностью ‘Об изоморфизме графов (P vs. NP)’ »

Новый алгоритм Facebook позволяет узнать вас, даже если ваше лицо скрыто

Глава научно-исследовательской лаборатории искусственного интеллекта Facebook говорит, что новое программное обеспечение может определить пользователей в 83% случаев, даже если их лица не видно.

Мы только начинаем понимать, что компьютеры и алгоритмы могут распознавать наши лица, и осознавать последствия, которые это может иметь для частной жизни. Глава научно-исследовательской лаборатории искусственного интеллекта Facebook говорит, что экспериментальная алгоритм, который он помог разработать для гигантской социальной сети, может узнать вас с высокой долей вероятности, даже если ваше лицо скрыто от камеры.

Янн Леган, эксперт в области компьютерного зрения и распознавания образов, работающий в Facebook с 2013 года, рассказал о своих исследованиях на недавней конференции в Бостоне. Он сказал, что хотел выяснить, могут ли быть изменены алгоритмы, используемые для распознавания лиц, так, чтобы распознавать людей по другим физическим характеристикам: типу телосложения, жестам и т.д. Читать полностью ‘Новый алгоритм Facebook позволяет узнать вас, даже если ваше лицо скрыто’ »

Кризис математики в Америке?

НЬЮ-ЙОРК

Часто говорят, что математика в обучении является краеугольным камнем. Связь, информатика, искусство, Интернет, космические исследования — все это основано на базовых математических понятиях. В последнем международном исследовании Международной программы по оценке образовательных достижений учащихся (PISA) Соединенные Штаты оказались на 27-м месте по успеваемости школьников по математике. Каковы причины этого, и что делается в связи с этим? Читать полностью ‘Кризис математики в Америке?’ »

Впервые женщина получила самую престижную награду в математике

Впервые в истории женщина получила высшую награду в области математики, часто называемую также Нобелевской премией по математике.

За все время своего существования (с 1936 года), филдсовская медаль вручалась только мужчинам. Первой женщиной, получившей ее от Международного математического союза в Сеуле (Южная Корея), стала в этом году Мариам Мирзахани. Читать полностью ‘Впервые женщина получила самую престижную награду в математике’ »

Боязнь математики и понимание информации о генетически модифицированных продуктах

Согласно исследователям, люди, которые боятся математики, возможно, хуже понимают информацию о генетически модифицированных продуктах питания и другую информацию, связанную со здоровьем.

“Боязнь математики, которая проявляется, когда люди обеспокоены использованием математики или статистики, приводит к уменьшению усилий, и уменьшается способность заниматься математикой’’, — сказала Роксана Пэррот, заслуженный профессор. — “Боязнь математики также, как было установлено, ухудшает работу памяти.’’

Исследователи обнаружили, что боязнь математики привела людей к худшему пониманию статистики в информации о генетически модифицированных продуктах питания, в то время как бóльшие математические знания и бóльшая уверенность в их использовании давали лучшее понимание.

“Это первое известное нам исследование, в котором изучалась боязнь математики применительно к здоровью и оценке риска’’, — сказала Пэррот. — “Математика стала обычным элементом во многих сообщениях об исследованиях, связанных со здоровьем и рисками, обращающихся к математической компетенции и игнорирующих познавательные и эмоциональные компоненты.‘’ Читать полностью ‘Боязнь математики и понимание информации о генетически модифицированных продуктах’ »

Математическое доказательство размером с Википедию слишком большое, чтобы люди могли его проверить

Борис Конев и Алексей Лисица

Если ни один человек не может проверить доказательство теоремы, действительно ли это может считаться математикой? Этот интересный вопрос возник в связи с недавним доказательством, полученным с помощью компьютера. Оно столь же велико, как все содержание Википедии, поэтому маловероятно, что его когда-нибудь сможет проверить человек. Читать полностью ‘Математическое доказательство размером с Википедию слишком большое, чтобы люди могли его проверить’ »