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

 Новости о знаменитостях Знаменитости 
Муз-ТВ спровоцировало флэшмоб среди популярных поп-исполнителей и актёров

Айза Долматова рассказала правду о своем бойбфренде




 Новости науки и техники Новости науки и техники 
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
  Комментарии к новости 
[Добавить комментарий]

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости науки и техники Хроника новостей 
Новейший российский беспилотник "Охотник" совершил первый полет

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
Найдены последние фотографии "Союза" до появления в нем отверстия, сообщил источник

16 сентября 04:04
В США без объяснения причин закрыли солнечную обсерваторию

16 сентября 00:04
Россия полностью заменила украинские комплектующие для военной техники

14 сентября 08:04
На корабле "Союз" не нашли новых следов от сверла, заявил источник

14 сентября 07:04
Россия прекратит возить астронавтов на МКС с апреля

31 августа 14: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
 Главная новость дня Главная новость дня 
СК проводит обыски в 30 регионах по делу об отмывании денег ФБК
 
 Эксклюзив Эксклюзив 
Как дела, S&P 500?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Натали рассекретила внешность младшего сына (фото)
Игру престолов ждет захватывающий финал
Наталья Штурм разделась на море (фото)
Восьмой сезон сериала Игра престолов будет последним
Ким Кардашян рассказала об ограблении в Париже
 Новости партнеров
 Новости дня Новости дня 
 
   RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ