8. Понятие массовой и индивидуальной задачи.

Под массовой задачей мы будем понимать некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит несколько параметров или несколько переменных значений, которые неопределены. Массовая задача П определяется информацией:

1. Общим списком всех её параметров

2. Формулировкой некоторых свойств, которым должен удовлетворять ответ.

Индивидуальная задача I получается из массовой задачи П, если всем параметрам задачи П присвоить конкретное значение.

Рассмотрим массовую задачу О КОММИВОЯЖЁРЕ. Параметрами в данной задаче являются конечный набор городов C = {c₁,c₂,…,c_n} и расстояние d(c_i,c_j) между парой городов c_i,c_j. Решением является упорядоченный набор <C_k1,C_k2,…,C_kn> заданных городов, в котором каждый C_ki не совпадает ни с каким другим, и величина принимает минимальное значение. Индивидуальная задача о коммивояжёре задаётся следующим образом:

C={c₁, c₂, c₃, c₄}

d(c₁, c₂) = 10,

d(c₁, c₃) = 5,

d(c₁, c₄) = 9,

d(c₂, c₃) = 6,

d(c₂, c₄) = 9,

d(c₃,c₄) = 3

< C₁, C₂, C₄, C₃>

Под алгоритмом будем понимать общее выполнение, шаг за шагом, процедуры решения задачи. Для определённости, мы будем считать её программой для компьютерного написания на формальном машинном языке. Будем говорить, решая массовую задачу П, если П применимо к любой индивидуальной задаче I, то и решение П даёт решение задачи I.

Нам необходим наиболее “эффективный” алгоритм решения задачи. Под самым эффективным алгоритмом понимается самый быстрый алгоритм решения. Время работы алгоритма удобно выразить в виде функции одной переменной. Эта переменная характеризует “размер” индивидуальной задачи, т.е. объём входных данных, требуемых при её описании. В дальнейшем, сравнительную сложность задач будем описывать через их размеры. Описание индивидуальной задачи можно рассматривать как одну конечную цепочку, состоящую из символов конечного входного алфавита.

Предположим, что заранее выбран такой способ, что с каждой массовой задачей связана некоторая фиксированная система кодирования. Она отображает индивидуальность задачи в цепочки символов. Входная длина индивидуальной задачи I из П определяется как число символов в цепочке, полученной применением к задаче I схемы кодирования для массовой задачи П. Эта входная длина используется в качестве формальной характеристики размера индивидуальной задачи.

Временная сложность алгоритма отображается функцией затраты времени, требующегося для его работы.

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

9. Понятие полиномиального алгоритма и труднорешаемой задачи

Для сравнения эффективности алгоритмов предлагается подход, основанный на различных полиномиальных и экспоненциальных алгоритмах. Будем говорить, что функция f(n) есть O(g(n)), если существует константа c такая, что |f(n)|≤c·|g(n)|, n≥0.

Полиномиальными алгоритмами называют алгоритмы, у которых временная сложность равна O(p(n)), где p(n) – некоторая полиномиальная функция, n – длина входной цепочки алгоритма.

Алгоритмы, временная сложность которых не поддаётся подобной оценке, называются экспоненциальными.

Временная сложность	Современные ЭВМ	*100	*1000
N	N1	100N1	1000N1
N^2	N2	10N2	31.6N2
N^3	N3	4.64N3	10N3
N^4	N4	2.5N4	3.98N4
2^N	N5	N5+6.64	N5+9.97

Большинство экспоненциальных алгоритмов представляет собой варианты полного перебора.

Полиномиальный алгоритм можно построить лишь тогда, когда удаётся проникнуть в суть решения задачи. Обычно считается, что задача не является хорошо решаемой, если для неё не получен полиномиальный алгоритм. Подобного рода задачи будем считать труднорешаемыми.

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