Большие задачи

Все задачи принципиально можно разделить на две группы: P (Polinomial) и NP (Non Polinomial) задачи. P задачи характеризуются объемом вычислений , где a – объем входных данных, p – полином невысокой степени. Такие задачи под силу современным многопроцессорным ЭВМ и называются «большими». NP задачи характеризуются выражением и современным машинам «не по зубам». Для решения таких задач могут использоваться квантовые ЭВМ,

скорость вычислений которых пропорциональна объему данных.

Время решения «больших» задач определяется количеством вычислитель

ных операций в задаче и быстродействием вычислительных машин. Естествен-

но, с ростом быстродействия вычислительных машин растет и размер решаемых задач. Для сегодняшних суперЭВМ доступными являются задачи с числом

операций с плавающей точкой.

Большое количество вычислительных моделей строится на базе решения

СЛАУ, при этом размеры решетки (число уравнений) может достигать многих

тысяч. Например, при моделировании полупроводниковых приборов число

уравнений может быть равно . Известно, что решение такой системы требует порядка вычислений по плавающих операций для каждого вычисления. Тогда общее время расчета одного варианта моделирования будет порядка операций.