"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
13.12.2011 22:08 |
Бозон Хиггса снова избежал регистрации
Физики, работающие с детекторами CMS и Atlas Большого адронного коллайдера, объявили, что им удалось не только сузить границы вероятной массы бозона Хиггса, но и . . . |
13.12.2011 22:01 |
10 самых важных мобильных событий года
Масштабные партнерские сервисы на основе геолокации Foursquare сотрудничает с AmEx, а Shopkick с CW. Геолокационные компании добились огромного роста капитала, но этого . . . |
13.12.2011 21:52 |
Электроника перейдет на молибден
Швейцарцы создали прототип микрочипа из совершенно нового материала. Дисульфид молибдена по многим параметрам превосходит традиционный кремний, а его . . . |
13.12.2011 18:15 |
Физики провели самое масштабное моделирование эволюции Вселенной
Физики провели самое масштабное на сегодняшний день моделирование процессов формирования Вселенной. Статья ученых появится в журнале Journal of the Korean Astronomical Society, а . . . |
13.12.2011 18:13 |
Истоки ходьбы нашли под водой
Ученые обнаружили, что умение ходить у живых организмов появилось задолго до того, как они вышли на сушу. Статья исследователей появилась в журнале Proceedings of the National . . . |
13.12.2011 18:11 |
Dawn вышел на самую низкую орбиту вокруг Весты
Космический аппарат Dawn спустился на самую низкую из предусмотренных в рамках его миссии орбит вокруг Весты. Об этом сообщается на официальном сайте космической . . . |
13.12.2011 18:10 |
В космических лучах нашли сверхтяжелые элементы
Российские ученые обнаружили присутствие в космических лучах ядер сверхтяжелых элементов. Об этом сообщает агентство ФИАН-инфо. В рамках работы исследователи из . . . |
13.12.2011 18:04 |
НПО имени Лавочкина признало провал миссии "Фобос-Грунта"
Генеральный директор и генеральный конструктор НПО имени Лавочкина Виктор Хартов признал провал миссии "Фобос-Грунт". Об этом он 13 декабря рассказал РИА Новости . . . |
13.12.2011 18:02 |
Найдены самые маленькие в мире лягушки
Исследователь Фред Краусс из Музея Бишоп в Гонолулу обнаружил самых маленьких из известных на настоящий момент лягушек. Статья ученого появилась в журнале ZooKeys . . . |
13.12.2011 17:46 |
52% пользователей услуг связи в России недовольны качеством обслуживания
Согласно исследованию Global Telecom Consumer Survey 2011, проведенному исследовательским институтом IBM Institute for Business Value, в ближайшие 2-3 года российский потребитель намерен . . . |
12.12.2011 20:45 |
6 российских школ и центров сети ОРТ начнут работать по программе Академий Cisco
В течение 2011/2012 учебного года в 6 российских учебных заведениях, действующих под патронатом ОРТ, начнут работать Академии Cisco. Преподавание будет вестись по . . . |
12.12.2011 20:26 |
Индиана Джонс может снова вернуться
Несмотря на то, что в ходе создания последнего фильма об отважном археологе Индиане Джонсе <Индиана Джонс и Королевство хрустального черепа> у Стивена Спилберга и . . . |
12.12.2011 20:13 |
Назначена дата первого полета к МКС частного космического корабля Dragon
Американское космическое агентство назвало дату и основные цели второго старта корабля Dragon компании SpaceX. В частности, в программу полета включена стыковка с МКС, . . . |
12.12.2011 20:12 |
Математики преодолели барьер Копперсмита-Винограда Вирджиния Уильямс из Стэнфордского университета предложила алгоритм умножения квадратных матриц с самой лучшей на данный момент асимптотикой сложности (pdf). Прежний рекордсмен, алгоритм Копперсмита-Винограда, был предложен в 1987 году, а оценка его сложности получила прозвище одноименного барьера.
Традиционно для анализа сложности используются асимптотические оценки. Фактически, они говорят о том, с какой скоростью растет количество вычислительных операций при росте параметров алгоритма (в данном случае параметр один - размер квадратной матрицы n). Алгоритм умножения "по определению", то есть по строкам и столбцам, имеет сложность O(n3) то есть его сложность растет примерно как константа, помноженная на степенную функцию с показателем 3.
В 80-х годах прошлого века Дон Копперсмит и Шнуэль Виноград предложили алгоритм вычисления умножения матриц со сложностью O(n2,39). Затем они заметили, что разбиение матрицы перед умножением на подматрицы и применение алгоритма к ним позволяет довести сложность до рекордных O(n2,376). Этот результат был получен разбиением n на два. Дальнейшие разбиения, однако (на три, четыре и так далее) не принесли улучшения.
В рамках новой работы Уильямс удалось усовершенствовать оригинальную оценку Копперсмита и Винограда. В результате ей удалось показать, что при разбиении n на 8 частей, асимптотика сложности оказывается равной O(n2,3727). Несмотря на то, что улучшение получено только в третьем знаке, по словам специалистов, работа представляет интерес, поскольку барьер Копперсмита-Винограда продержался 24 года. Многие ученые полагают, что существует алгоритм с асимптотической оценкой O(n2), то есть сложность растет как количество элементов в квадратной матрице.
В работе подчеркивается, что данный алгоритм не найдет применения в существующих вычислительных системах по той же причине, по которой не используется алгоритм Копперсмита-Винограда - уменьшение сложности приводит к увеличению необходимой для работы памяти. При этом памяти современных компьютеров не хватит для применения таких алгоритмов в реальных задачах. Вместо них часто применяется алгоритм Штрассена.
|
12.12.2011 20:09 |
Создан переключатель из одной молекулы
Немецкие физики создали выключатель из одной молекулы. Статья исследователей появилась в журнале Nature Nanotechnology. В рамках работы ученые исследовали . . . |
12.12.2011 20:07 |
Eвропа одобрила строительство исключительно большого телескопа
Южная европейская обсерватория (ESO) одобрила строительство E-ELT (European Extremely Large Telescope - Европейского исключительно большого телескопа). Об этом сообщается на сайте . . . |
12.12.2011 18:11 |
Intel на выставке CES 2012
КОГДА: 10-13 января 2012 г. (встреча с журналистами на CES 2012 будет проведена 9 января). ГДЕ: Международная выставка потребительской электроники CES 2012, Las Vegas Convention Center, Central . . . |
12.12.2011 17:07 |
Астрофизики объяснили необычную орбиту Меркурия
Астрофизики объяснили необычную орбиту Меркурия столкновением с астероидом. Статья ученых появилась в Nature Geoscience. До середины прошлого века ученые полагали, что . . . |
12.12.2011 16:43 |
Выпускники Академий Cisco на московской Cisco Expo: любое дело по плечу
22-24 ноября в Москве проходила ежегодная конференция Cisco Expo. Третий год подряд к ее подготовке и проведению были привлечены студенты Академий Cisco. По рекомендациям . . . |
12.12.2011 08:09 |
Samsung поставил рекорд по продажам мобильных телефонов
Компания Samsung поставила рекорд по годовым продажам мобильных телефонов - к концу ноября в магазины было отгружено более 300 миллионов мобильников, сообщает Reuters . . . |