Российская Информационная Сеть
English   Контакты
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ
ТОП-дайджест  Хроника  Эксклюзив  Фоторепортажи  Личное мнение  Погода  Комментарии  Поиск  RSS  Интернет-радио  
 Топ 20 сегодня Топ 20 сегодня 
Почему Лукашенко скоро исправит свою ошибку
В России расширили перечень стратегически значимых лекарств
В МИД заявили, что не дадут в обиду задержанных в Белоруссии россиян
Лукашенко прокомментировал задержание россиян
Лукашенко прокомментировал задержание россиян под Минском
Дания разрешила "Газпрому" возобновить прокладку "Северного потока - 2"...
Черногория разрешила въезд россиянам
Новым зампредом хабаровского правительства станет начальник управления...
Счетная палата указала на проблемы с содержанием автодорог
Суд арестовал жену рэпера Картрайта
далее топ дня...
 Фотожурнал: фото-топ за месяц, галерея всех фото Фотожурнал 
 Новости партнеров
 Топ новости разделов сегодня Топ новости разделов 
Почему Лукашенко скоро исправит свою ошибку Почему Лукашенко скоро исправит свою ошибку
Помощник Путина назвал три рецепта экономического роста в России Помощник Путина назвал три рецепта экономического роста в России
В Кремле прокомментировали опубликованное в СМИ видео убийства сирийца В Кремле прокомментировали опубликованное в СМИ видео убийства сирийца...
Британский самолет провел разведку у границ Калининградской области Британский самолет провел разведку у границ Калининградской области
Kaspersky раскрыл кампанию политического кибершпионажа на Ближнем ВостокеKaspersky раскрыл кампанию политического кибершпионажа на Ближнем Востоке...
Почти 16 тысяч жителей Курска остались без отопления и горячей воды Почти 16 тысяч жителей Курска остались без отопления и горячей воды
Суд в США приговорил россиянина Лисова к четырем годам тюрьмы Суд в США приговорил россиянина Лисова к четырем годам тюрьмы
Призывная комиссия знала о склонности стрелка в Благовещенске к суициду Призывная комиссия знала о склонности стрелка в Благовещенске к суициду...
На Украине предложили ввести уголовную ответственность за торговлю с РоссиейНа Украине предложили ввести уголовную ответственность за торговлю с Россией...
Юлию Началову похоронят во вторник на Троекуровском кладбищеЮлию Началову похоронят во вторник на Троекуровском кладбище
далее...
 Личное мнение Личное мнение 

 Новости о знаменитостях Знаменитости 
Звездная Coca-Cola - самый яркий летний хит на Europa Plus Live

Слухи о закрытии передачи «Давай поженимся»




 Новости науки и техники Новости науки и техники 
12 декабря, 16:55

Математики преодолели барьер Копперсмита-Винограда

Новости по теме:
Вирджиния Уильямс из Стэнфордского университета предложила алгоритм умножения квадратных матриц с самой лучшей на данный момент асимптотикой сложности. Прежний рекордсмен, алгоритм Копперсмита-Винограда, был предложен в 1987 году, а оценка его сложности получила прозвище одноименного барьера.

Традиционно для анализа сложности используются асимптотические оценки. Фактически, они говорят о том, с какой скоростью растет количество вычислительных операций при росте параметров алгоритма (в данном случае параметр один - размер квадратной матрицы n). Алгоритм умножения "по определению", то есть по строкам и столбцам, имеет сложность O(n3) то есть его сложность растет примерно как константа, помноженная на степенную функцию с показателем 3.

В 80-х годах прошлого века Дон Копперсмит и Шнуэль Виноград предложили алгоритм вычисления умножения матриц со сложностью O(n2,39). Затем они заметили, что разбиение матрицы перед умножением на подматрицы и применение алгоритма к ним позволяет довести сложность до рекордных O(n2,376). Этот результат был получен разбиением n на два. Дальнейшие разбиения, однако (на три, четыре и так далее) не принесли улучшения.

В рамках новой работы Уильямс удалось усовершенствовать оригинальную оценку Копперсмита и Винограда. В результате ей удалось показать, что при разбиении n на 8 частей, асимптотика сложности оказывается равной O(n2,3727). Несмотря на то, что улучшение получено только в третьем знаке, по словам специалистов, работа представляет интерес, поскольку барьер Копперсмита-Винограда продержался 24 года. Многие ученые полагают, что существует алгоритм с асимптотической оценкой O(n2), то есть сложность растет как количество элементов в квадратной матрице.

В работе подчеркивается, что данный алгоритм не найдет применения в существующих вычислительных системах по той же причине, по которой не используется алгоритм Копперсмита-Винограда - уменьшение сложности приводит к увеличению необходимой для работы памяти. При этом памяти современных компьютеров не хватит для применения таких алгоритмов в реальных задачах. Вместо них часто применяется алгоритм Штрассена.
[Читать все комментарии] [Напечатать новость]
Источник: LENTA.RU
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости науки и техники Хроника новостей 
Британский самолет провел разведку у границ Калининградской области

23 октября 01:04
На бывшей американской базе в Сирии приземлились вертолеты ВКС

22 октября 05:04
НАСА хочет купить еще одно место в "Союзе", сообщил источник

22 октября 04:04
НАСА хочет купить очередное место в российском "Союзе", сообщил источник

22 октября 03:04
Российские военные выполнят наблюдательный полет над территорией США

21 октября 01:04
Новейший российский беспилотник "Охотник" совершил первый полет

3 августа 18:04
Российские военные сняли на видео уничтожение артиллерии боевиков в Сирии

3 августа 05:04
Стали известны характеристики баллистической ракеты "Сармат"

27 июня 18:04
"Не нужно прятать камеры": Госсовет обсудил безопасность на дорогах

26 июня 15:04
В Центральном военном округе началась внезапная проверка боеготовности

24 июня 11:04
ВКС получили два новейших вертолета Ми-28НМ

23 июня 10:04
Российские Су-27 дважды сопроводили бомбардировщики США над Балтикой

23 марта 13:04
Су-27 дважды за сутки сопровождали американские B-52 над Балтикой

23 марта 12:04
В России успешно запустили реактор нового энергоблока АЭС

23 марта 08:04
Запуск спутника "Глонасс" с Плесецка планируется в середине мая

23 марта 02:04
Производитель сорвал поставку трех Ил-476 для Минобороны

21 марта 18:04
Модуль "Наука" для МКС потеряет ключевую функцию после ремонта

20 марта 02:04
Открыта трасса для запуска кораблей к МКС с космодрома "Восточный"

17 марта 02:04
Названа причина смерти Юлии Началовой

16 марта 20:04
"Роскосмос" предложил проводить на МКС военные эксперименты

14 марта 20:04
В ракете "Союз-ФГ" был неисправен украинский прибор, сообщил источник

13 марта 15:04
S7 приостановила полеты Boeing 737 Max

12 марта 20:04
Ученые рассказали, действительно ли в Хабаровском крае упал метеорит

24 декабря 18:04
Российский спецназ вооружили автоматом, который NI назвал "супероружием"

13 декабря 03:04
Источник рассказал, когда с палубы "Адмирала Кузнецова" уберут упавший кран

6 декабря 02:04
Появилось видео пролета Су-25 над Крымским мостом

25 ноября 21:04
Российские военные химики прибыли в обстрелянный боевиками Алеппо

25 ноября 03:04
Завершились учения "Восток-2018"

17 сентября 10:04
Крупные военные учения в России станут регулярными

16 сентября 15:04
Американский беспилотник заметили у Черноморского побережья России

16 сентября 09:04
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 >> 884
 Главная новость дня Главная новость дня 
Почему Лукашенко скоро исправит свою ошибку
 
 Эксклюзив Эксклюзив 
Как дела, S&P 500?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
В Кёльне около 100 человек застряли на канатной дороге (фото)
Пугачева затмила невесту Никиты Преснякова (фото, видео)
Ким Кардашян рассказала об ограблении в Париже
Новые маленькие кроссоверы известных марок выходят на рынок.
Анджелина Джоли с детьми переехала в новый дом
 Новости партнеров
 Новости дня Новости дня 
 
   RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ