"Русский переплет" зарегистрирован как СМИ.
Свидетельство о регистрации в Министерстве печати РФ: Эл. #77-4362 от
5 февраля 2001 года. При полном или частичном использовании
материалов ссылка на www.pereplet.ru обязательна.
|
|
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 . . . |
|
11.12.2011
23:36 |
Первооткрывателям связи посвящается
видеоролик Cisco В середине 19-го столетия по дну Атлантического океана был проложен кабель, позволивший наладить телеграфную связь между Новым и Старым светом . . . |
|
11.12.2011
16:29 |
В Стокгольме и Осло вручили Нобелевские премии
Нобелевскую премию по литературе дали Тумасу Транстремеру В Стокгольме в субботу, 10 декабря, прошла церемония награждения Нобелевскими премиями 2011 года в . . . |
|
11.12.2011
16:00 |
Система ГЛОНАСС теперь обеспечивает 100% покрытие Земли
Пресс-служба Роскосмоса объявила, что 8 декабря был введен в эксплуатацию 24-й космический аппарат системы ГЛОНАСС - один из трех космических аппаратов, запущенных 4 . . . |
|
11.12.2011
15:52 |
В России будут построены новые центры исследований Intel и IBM
Недавно было заключено соглашение о сотрудничестве между фондом Сколково и американскими компаниями Intel и IBM, по которому последние разместят свои центры . . . |
|
11.12.2011
15:49 |
Многооблачный мир
Первый отчет по результатам исследования тенденций развития облачных вычислений, опубликованный недавно компанией Cisco под названием "Глобальный индекс развития . . . |
|
10.12.2011
20:59 |
Фермеры в странах с развивающейся экономикой берут на вооружение мобильные технологии
Мобильное сельское хозяйство обеспечивает сельским жителям и владельцам мелких фермерских хозяйств мобильный доступ к информации. До конца концепция мобильного . . . |
|
10.12.2011
19:15 |
HP в России продолжает стремительно развиваться
Компания HP подвела итоги деятельности в России за 2011 финансовый год. Бизнес компании в этот период сохранил устойчивые позиции на рынке и, несмотря на ряд внешних . . . |
|
10.12.2011
15:33 |
Обнаружена звезда со скоростью вращения 2 млн км/ч
Как сообщает 3DNews, астрономы Европейской южной обсерватории (ESO) записали в свой актив очередной космический объект, обладающий некими <самыми-самыми> . . . |
|
10.12.2011
08:19 |
На базе суперкомпьютера <Т-Платформы> тюменские ученые создадут искусственный интеллект
Компания <Т-Платформы>, международный разработчик суперкомпьютеров и поставщик полного спектра решений и услуг для высокопроизводительных вычислений, сообщила о . . . |
|
10.12.2011
07:43 |
Россия - лидер по количеству пользователей Интернет в Европе
Россия стала крупнейшим рынком Европы по количеству пользователей Интернет, обогнав ведущие экономики региона - Францию и Германию и став лакомым куском для . . . |
|
10.12.2011
07:35 |
Ультрабуки будут оснащаться сенсорными экранами
Производители ноутбуков планируют оснащать ультрабуки сенсорными панелями, чтобы использовать новые возможности Windows 8 и вернуть часть доли рынка, которую заняли . . . |
|
10.12.2011
07:04 |
Игорь Щёголев: российский рынок мобильной связи - один из самых быстрорастущих в мире
Как сообщает 3DNews, рынок мобильной индустрии в России демонстрирует высокие темпы развития и является одним из самых быстрорастущих в мире. С таким заявлением на . . . |
|
10.12.2011
00:14 |
ASUS нацелена стать третьим в мире поставщиком ПК
Как сообщает 3DNews, во время мероприятия, посвящённого мировым продажам, Asustek Computer объявила о своих целях на следующий год по поставкам продуктов четырёх главных . . . |
