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

 Новости о знаменитостях Знаменитости 
Лимузин Ельцина выставлен на продажу

Новость: 17 августа 14:48: Певица Рианна создала коллекцию носков со своим изображениемПевица Рианна создала коллекцию носков со своим изображением


 Заплатим за ваше мнение!
Получайте до 1,5 долларов за каждую заполненную анкету!



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

Комментариев к этой новости пока нет. Добавьте первым свой комментарий!
[Добавить комментарий]
 Хроника новостей: Новости науки и техники Хроника новостей 
Корабль "Союз" с экипажем пристыковался к МКС

19 декабря 12:04
На Дальнем Востоке появится новая армия, сообщили СМИ

18 декабря 09:04
От МКС отстыковался "Союз МС-05" с тремя космонавтами

14 декабря 09:04
В Стокгольме наградили лауреатов Нобелевской премии

10 декабря 22:04
Спутник "Метеор-М" не вышел на целевую орбиту

28 ноября 13:04
На Восточном прошел второй пуск в истории космодрома

28 ноября 10:04
РН "Союз" со спутником взлетела с космодрома Восточный

28 ноября 09:04
Госкомиссия разрешила второй запуск РН с космодрома Восточный

28 ноября 08:04
Российские специалисты отправились в район поисков аргентинской подлодки

28 ноября 06:04
Пентагон заявил об "опасном" перехвате Су-30 самолета США

28 ноября 04:04
Вошедший в Черное море американский эсминец направляется в Одессу

28 ноября 01:04
Турция успокоила, что С-400 не опасны для НАТО

27 ноября 20:04
Как быстро похудеть: 3 важных фактора

10 ноября 09:25
МВД планирует ввести новые экзамены для водителей.

7 ноября 09:23
Россия ближайшем будущем будет развивать ядерные силы и высокоточное оружие.

31 октября 10:34
Российская армия получила ещё один полк С-400

26 октября 12:44
Российские школьники собрали все золотые медали чемпионата JuniorSkills

19 октября 16:40
Россия празднует День Ксмических войск

4 октября 08:38
Крымский мост защитят от диверсантов

3 октября 08:07
Новое российское оружие способно выключать электронику НАТО на расстоянии

2 октября 10:52
Россия лишилась опасного оружия

28 сентября 08:41
Виктория Дайнеко пожаловалась на бывшего мужа

27 сентября 10:51
Современный автомобиль необходимо защищать антивирусом

26 сентября 11:43
Сотовые операторы отказываются от GSM сетей

20 сентября 10:02
Космонавт рассказал необычных эмоциях при выходе в открытый космос

20 сентября 09:46
Стали известны цена на Lada Vest SW Cross

19 сентября 17:24
Пилотируемый космический корабль Союз МС-06 успешно произвел стыковку с МКС.

14 сентября 10:08
Chery планирует захватить рынок Европы своими электромобилями

13 сентября 20:20
Франкфуртский автосалон: электромобили, автопилоты и конкуренты из Китая

12 сентября 09:55
Ракета-носитель Протон доставил на орбиту Земли новый спутник

12 сентября 09:14
 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 >> 938
 Главная новость дня Главная новость дня 
Источник сообщил о планируемой утилизации двух крупнейших в мире подлодок
 
 Эксклюзив Эксклюзив 
Пора ли продавать акции Apple? Пора ли продавать акции Apple?
 
  Топ новостей Опросы 
 Фоторепортажи: новости с подборкой фотографий Фоторепортажи 
Канье Уэст принял на себя роль визуального художника
В Кёльне около 100 человек застряли на канатной дороге (фото)
Николай Носков впервые рассказал о тяжелой болезни
68-летняя Пугачева показала свои морщины (фото)
Актера Шайа ЛаБаф арестовали за драку с полицейским
 Новости партнеров
 Новости дня Новости дня 
 
  Copyright © RIN 2000-
* Обратная связь
Контактная информация  
Политика  Общество  Экономика  Деловые  Наука  Hi-Tech  Культура  Шоу-бизнес  Спорт  Происшествия  Криминал  Скандалы  Пикантные  Зарубежные  ИноСМИ