Реферат: Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ
к курсовой работе на тему
: “Разработка
алгоритмов и
программ выполнения операций над последовательными
и связанными представлениями структур данных
”
по курсу
“
Теория алгоритмов и вычислительных
Два орграфа
X
и
Y
с
N
вершинами (
X
в последовательном представлении
, Y
в связанном представлении) без кратностей. Дуги орграфов образуют неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин
,
в которые ведут ребра из каждой вершины графа.
Выполнить над ребрами орграфов операцию разности
( X/Y
).
В результате выполнения этой операции новый орграф
Z
определяется в связанном представлении
,
а старый орграф
X
исправляется в последовательном представлении.
Особенности представления данных
:
Последовательное представление данных
:
одномерный массив
Array
,
содержащую два целочисленных поля
I
(
содержит номер вершины, из которой исходит дуга) и
J
(
содержит номер вершины, в которую входит дуга).
Связанное представление данных
:
одномерный массив
Spisok
указателей на структуру
index
,
представляющую собой элемент списка
и содержащий поле
:
целочисленное
i ndex
(
содержит номер вершины, в которую входит дуга) и
Next
-
указатель на структуру
Spisok
,
указывающее на следующий элемент списка
N - количество вершин в графе
Y,Z.
Ввод информации
об неориентированных графах происходит из файла, формат которого должен быть нижеследующим
:
Xij - номер очередной вершины смежной
i в графе
X
(i = 1..N, j=1..ki)
Yij - номер очередной вершины смежной
i в графе
Y
(i = 1..N, j=1..ki)
Если из какой-то вершины не выходит ни одного ребра
,
то для нее в исходных данных задаем только ноль (например
‘0’ -
вершина 2 изолирована). Таким образом, для каждого графа должно вводится в общей сложности
N нолей.
Формат печати результатов
работы программы представлен в следующем формате
:
Даны неориентированные графы X и Y без кратностей.
Для каждого графа задаем номера вершины смежности с данной.
Граф X (в ЭВМ в последовательном представлении):
Граф Y (в ЭВМ в связанном представлении):
Над графами выполняется операция разности двумя способами
с получением нового графа Z (в связанном представлении):
И исправлением старого графа X (в последовательном представлении):
Кол-во вершин, кол-во дуг графа X, кол-во дуг графа Y
и кол-во времени, затраченного на вычисление разности X и Y:
где
T - кол-во времени, затраченного на вычисление разности X и Y
Zij - номер очередной вершины смежной
i в графе
Z
(i = 1..N, j=1..ki)
Принцип решения основан на методе полного перебора, что конечно не лучший вариант, но все-таки лучше, чем ничего.
Аномалии исходных данных
и реакция программы на них:
1.
нехватка памяти при распределение
: вывод сообщения на экран и завершение работы программы;
2.
неверный формат файла
: вывод сообщения на экран и завершение работы программы;
Входными данными для моей работы является начальное число вершин графа, которое по мере работы программы увеличиться на 30 верши. Это число не может превосходить значения 80 вершин, так как в процессе работы программы число увеличивается на 30 и становиться 110 – это «критическое» число получается из расчета 110
»
2 16
/3
. Это происходит потому, что стандартный тип
int
не может вместить в себя более чем
2 16
. Мне же требуется для нормально работы программы, чтобы тип вмещал в себя утроенное количество вершин неориентированного графа. Конечно, это всего лишь приближение, но с учётом того, что графы генерируются случайно возможность набора 33000 невелико и, следовательно, допустимо.
Входной файл генерируется каждый раз новый.
Графы для расчета мультипликативных констант генерируются случайным образом, используя датчик случайных чисел, это-то и накладывает ограничения на количество вершин. Дело в том, что при работе с генератором случайных чисел предпостительно иоспользовать целый тип данных – так говорил товарищ Подбельский В.В.
Каткие сведения о временной сложности.
Качество алгоритма оценивается как точность решения и эффективность алгоритма, которая определяется тем временем, которое затрачивается для решения задачи и необходимым объёмом памяти машины.
Временная сложность алгоритма есть зависимость от количества выполняемых элементарных операций как функция размерности задачи. Временная сложность алгоритма А обозначается .
Размерность задачи – это совокупность параметров, определяющих меру исходных данных. Временная оценка алгоритма бывает двух типов:
1.
априорная – асимптотическая оценка сложности
2.
апосториорная – оценка сложности алгоритма с точностью до мультипликативных констант, сделанных для конкретной машины.
Именно асимптотическая оценка алгоритма определяет в итоге размерность задачи, которую можно решить с помощью ЭВМ. Если алгоритм обрабатывает входные данные размера
N
за время
CN
2
, где С
– некая постоянная, то говорят, что временная сложность этого алгоритма есть . Вернее говорить, что положительная и нулевая функция
есть , если существует такая постоянная С
, что для всех отрицательных значений
N
.
Для того, чтобы проверить правильность временной оценки алгоритма, надо знать априорную оценку сложности.
Проверка вычислительной сложности алгоритма сводиться к экспериментальному сравнению двух или более алгоритмов, решающих одну и ту же задачу. При этом возникают две главные проблемы: выбор входных данных и перевода результатов эксперимента в графики кривых сложности.
При прогоне программы мы получаем значения функции, которые можно изобразить на графике как функцию
f
(
NX,NY,NZ
)
. Данные точки показывают характер кривой. Для аппроксимации этого облака точек в своей курсовой работе я использовал метод наименьших квадратов.
Анализ по методу наименьших квадратов заключается в определении параметров кривой, описывающих связь между некоторым числом
N
пар значений
Xi, Yi
(
в данном случае
n
и
t
соответственно), обеспечивая при этом наименьшую среднеквадратичную погрешность. Графически эту задачу можно представить следующим образом – в облаке точек
Xi, Yi
плоскости
XY
(
смотри рисунок) требуется провести прямую так, чтобы величина всех отклонений отвечала условию:
В моём случае
T(NX,NY,NZ)=O(NX*(NY+NZ) =>
T(NX,NY,NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ)
Следовательно для моего примера мы получим:
Для того чтобы получить значение функции на
K-
том эксперименте, мы засекаем значение времени перед вызовом функции, которая реализует алгоритм, вставим оператор вида:
Где функция
clock()
даёт время с точностью до нескольких миллисекунд (в языке С++ она описана в заголовочном файле
time.h)
. После выполнения процедуры, реализует алгоритм, мы находим разность времени
После всех проделанных манипуляций нужно прировнять к нулю все частные производные. Это будет выглядеть, в общем виде, примерно так:
После раскрытия скобок и замены T(n)=
T(n)=(c,
t
(n))=
получим
Положим А
ij=(ti, tj)
и
B=(ti,TikTak)
=
>
мы получили систему уравнений
AX=B
, где Х=С. Формирование в матрице столбцов А и столбцов В записывается очень легко используя любой алгоритмический язык. После заполнения матрицы её остаётся решить и вывести решения этой задачи. Решение производиться методом Жордана.
Априорная временная оценка процедур.
Процедура вывода графа на экран в последовательном представлении:
Void prin3(Array *X, int N1, int N)
Процедура вывода графа на экран в связаном представлении:
Процедура вычисления разности графов
с возвращающим значением последовательного графа:
Array * RaznostZ(int n, int &n1, Array *X, Spisok **Y,Array *Z)
X – грав в последовательном представлении
Z – грав в последовательном представлении
Процедура
вычисления разности графов
с возвращающим значением последовательного графа:
Spisok * RaznostY(int n, int &n1, Array *X, Spisok **Y)
X – грав в последовательном представлении
N3 – количество вершин в графе Z – возвращаемом.
Процедура
ввода графов
в последовательном представлении:
Spisok **ReadFileY( Spisok **Y, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
Процедура
ввода графов
в последовательном представлении:
Array *ReadFileY( Array *X, char *st)
St – указатель на строку с именем файла из которого будет происходить ввод
X – грав в последовательном представлении
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Spisok //Связанное представление графа
{ int index; //Содержвтельная "ячейка"
///////////////////////////////////////////////////////////////////////////////////////////////////////
struct Array //Последовательное представление графа
///////////////////////////////////////////////////////////////////////////////////////////////////////
inline double fun1(double N_X,double N_Y,double N_Z){ return N_X*(N_Y+N_Z);}
inline double fun2(double N_X,double N_Y,double N_Z){ return N_X+N_Y;}
inline double fun3(double N_X,double N_Y,double N_Z){ return N_X;}
inline double fun4(double N_X,double N_Y,double N_Z){ return N_Y;}
inline double fun5(double N_X,double N_Y,double N_Z){ return N_Z;}
inline double fun6(double N_X,double N_Y,double N_Z){ return 1;}
///////////////////////////////////////////////////////////////////////////////////////////////////////
typedef double(*MENU1)(double,double,double);
MENU1 MyMenu[6] = { fun1,fun2,fun3,fun4, fun5,fun6 };
////////////////////////////////////////////////////////////////////////////////
for (s = 0, i = 0; i < (n - j); i++)if (fabs(A[i][j]) > fabs(s)) s = A[ir = i][j];
for (i = 0; i < ir; i++)A[i][k] -= c * A[i][j];
for (i = ir + 1; i < n; i++)A[i - 1][k] = A[i][k] - c * A[i][j];
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////
Spisok **GenSeY(int Mas_y,int & Counter)
for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;
if (end == NULL) {cout << "Lack of memory";exit (1);}
if (end==NULL) {cout <<"L a c k of m e m o r y !"; exit (1);}
////////////////////////////////////////////////////////////////////////////////
Array *GenSeX(int Mas_y,int & Counter)
if(X==NULL){cout<<"\n net u mena stolko pamaty!!!\n";exit(1);}
for (int j = 0; j< m; j++)if (k==Pro[j]) flag = 1;
////////////////////////////////////////////////////////////////////////////
if (!file) cerr <<"Can not open file!!!!!";
for( int j = 0; string[j] != '0' ; j++ )
// {cout <<"error in file "<index){Flag=1;break;}//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
if(Flag==0){ //если не было совпадений вершин, то... всё понятно:
////////////////////////////////////////////////////////////////////////
while(rex!=NULL){Z[i]=rex->next;delete rex;rex=Z[i];}
////////////////////////////////////////////////////////////////////////////////
Spisok** RaznostY(int n,int n1,Array *X, Spisok **Y)
Z,Y - связанном представлении, X - в последовательном.
n - кол-во вершин графа, n1 - кол-во дуг графа*/
Spisok **Z = new Spisok *[n];//выделение памяти для графа в связанном представлении
for (i=0;iindex)Flag=1;//если нашли повторение, то выход
max=max->next; //передвигаемся на следующий элемент списка
if(Flag==0){ //если небыло совпадений вершин, то... всё понятно:
Spisok *end=Z[j], *beg=Z[j], *pred=Z[j];
while (end !=NULL) {pred = end ;end = end ->next;}
if((beg==NULL)&&(end==NULL))Z[j]=beg=end=new(Spisok);
else end = end -> next = new (Spisok);
DeleteY(Y,n); //Убийство связанного графа Игрыка!
///////////////////////////////////////////////////////////////////////////////////////////////////////
/* Х - в последовательном представлении
cout<<"\t\tДемонстрация работоспособности программы."<Реферат: Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных
Отношения Базарова И Одинцовой Сочинение
Реферат по теме Фашистское государство Япония
Дипломная работа по теме Разработка бизнес-плана снижения себестоимости продукции на металлургических предприятиях (на материалах ОАО 'Мценский литейный завод')
Реферат: Проблемы происхождения и развития земли 2
Курсовая работа: Податкова система України, її становлення та розвиток
Дипломная работа: Особенности социального обеспечения
Отчет по практике по теме Особливості психокорекційної роботи із надання психологічної допомоги в дитячому садку
Курсовая работа по теме Учетная политика ОАО 'Ростелеком'
Курсовая работа по теме Анализ системы управления "Общежитие"
Входная Контрольная Работа По Истории 8 Класс
Курсовая На Тему Организация Целевого Кредитования
Курсовая работа по теме Составление бизнес-плана торгового предприятия
Реферат: История танцевальной культуры Карелии
Контрольная работа: Педагогическая мысль в Древней Греции и Древнем Риме
Реферат по теме Партиципаторная демократия
Как Избавиться От Скуки 10 Предложений Сочинение
Реферат На Тему Парезы Ног
Курсовые Разницы 2022 Рб
Дипломная работа по теме Совершенствование системы оценки и стимулирования персонала гостиницы 'Русь'
Дипломная Работа Мчс
Реферат: Методы снижения помех в RadioEthernet-сетях
Доклад: Джобс Стивен (Jobs Steven)
Реферат: Герцен и Достоевский