Математические проблемы реализации алгоритмов на ЭВМ

Обработка информации

Для решения системной задачи данные о системе объекта необходимо физически закодировать. Общим способом кодирования данных является их представление в виде энергетических уровней величиной ΔЕ. Число энергетических уровней равно N = E/ΔE, где Е — энергия системы, которой мы располагаем. Максимальное число физически разрешимых уровней для заданного количества энергии определяется принципом неопределенности Гейзенберга, согласно которому величина уровня должна удовлетворять условию

ΔE•Δt h, где Δt — длительность интервала наблюдения h = 6,63•10^-27 эрг*c — постоянная Планка.

Из этого следует:

N E•Δt/h

Тогда с учетом формулы Энштейна Е = mc^2 получим:

N mc^2•Δt/h

Отсюда следует, что измеритель массой 1 г за время 1 с может обработать не более N = 1,36•10^47 бит данных.

Представим гипотетический измеритель массой, равной массе Земли m = 6•10^27 г. Этот измеритель за время, равное примерно времени существования Земли q =10^10 лет смог бы обработать порядка 10^93 бит данных. Это число обычно называют пределом Бреммермана.

Задачи, требующие обработки более чем 10^93 бит информации называются трансвычислительными задачами. К сожалению, комбинаторика говорит нам, что такой предел может быть достигнут для задач даже относительно небольшого размера.

Например, в распознавании образов: пусть есть массив q*q, каждый элемент которого может быть раскрашен одним из k цветов, тогда всего вариантов раскраски может быть k^(q*q). Если массив 18×18, то задача трансверсальна при двух цветах. Так же 67! > 10^94.

Реальные вычислительные мощности

Процессоры персональных компьютеров

AMD AMD ATHLON II X4 645 3.1 ГГц (2010) — 38.44 Гфлопс

Мощнейший компьютер на 2011 K computer 10,51 * 10^15 FLOPS

В одних сутках 86400 секунд ~ 10^5

За сутки вычислений персональный 10^15, суперкомпьютер 10^20

Год работы +2 порядка

Закон Мура: число транзисторов на кристалле будет удваиваться каждые 24 месяца.

Дата добавления: 2014-01-07