Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: акт, решебники за 8 класс
| Добавил(а) на сайт: Bezrukov.

При прогоне программы мы получаем значения функции, которые можно изобразить на графике как функцию f(NX,NY,NZ). Данные точки показывают характер кривой. Для аппроксимации этого облака точек в своей курсовой работе я использовал метод наименьших квадратов.

Анализ по методу наименьших квадратов заключается в определении параметров кривой, описывающих связь между некоторым числом N пар значений
Xi, Yi (в данном случае n и t соответственно), обеспечивая при этом наименьшую среднеквадратичную погрешность. Графически эту задачу можно представить следующим образом – в облаке точек Xi, Yi плоскости XY (смотри рисунок) требуется провести прямую так, чтобы величина всех отклонений отвечала условию:

[pic]

N

F =[pic]

K=1

Где

[pic]
В моём случае T(NX,NY,NZ)=O(NX*(NY+NZ) =>

T(NX,NY,NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ)

Следовательно для моего примера мы получим:

[pic]
Для того чтобы получить значение функции на K-том эксперименте, мы засекаем значение времени перед вызовом функции, которая реализует алгоритм, вставим оператор вида:

TikTak=clock();
Где функция clock() даёт время с точностью до нескольких миллисекунд (в языке С++ она описана в заголовочном файле time.h). После выполнения процедуры, реализует алгоритм, мы находим разность времени

TikTak=cloc() - TikTak;
После всех проделанных манипуляций нужно прировнять к нулю все частные производные. Это будет выглядеть, в общем виде, примерно так:

[pic]

После раскрытия скобок и замены T(n)= T(n)=(c,((n))= [pic]получим

[pic]
Положим Аij=(ti, tj) и B=(ti,TikTak) => мы получили систему уравнений AX=B, где Х=С. Формирование в матрице столбцов А и столбцов В записывается очень легко используя любой алгоритмический язык. После заполнения матрицы её остаётся решить и вывести решения этой задачи. Решение производиться методом Жордана.

Априорная временная оценка процедур.

Процедура вывода графа на экран в последовательном представлении:
Void prin3(Array *X, int N1, int N)

X – граф в связаном представлении

N – количество вершин графа.

N1 – количество дуг в графе Х

O(N,N1)=N*N1

Процедура вывода графа на экран в связаном представлении:
Void print3(Spisok **X, int N)

X – граф в связаном представлении

N – количество дуг в графе.