Курсовая: Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

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

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 511 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО О БРАЗОВАНИЯ РОССИЙСКО Й ФЕДЕРАЦИИ. МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИО ННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им . К.Э . ЦИОЛКОВКОГО КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИ Й ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовой работе на тему : “Разработка алгоритмов и программ выполнения операций над по следовательными и связанными представлениями структур дан ных” по курсу “Теория алгоритмов и вычислительных методы” Руководитель : Авдошин С.М. Дата сдачи : _____________ Подпись : _____________ Студент : Лицентов Д.Б. Группа : 3ИТ -2-26 М осква 1998 1. Постановка задачи. Дано : Два орграфа X и Y с N вершинами ( X в по следовательном представлении , Y в связанном представле нии ) без кратностей . Дуги орграфов образуют неупорядоченные списки . Орграфы задаются неупорядо ченными списками смежных вершин - номеров вершин , в которые ведут ребра из каждой вершины графа. Требуется : Выполнить над ребрами орграф ов операцию разности ( X / Y ). В результате выполнения этой операции новый орграф Z опреде ляется в связанном представлении, а стар ый орграф X исправляется в пос ледовательном представлении. Особенности представления данны х : Последовательное представление данных : одномерный массив Array , содержащую два целочисленных поля I (соде ржит номер вершины , из которой исходит дуг а ) и J (содержит номер вершины , в которую в ходит дуга ). Array[_] I J Array[ 1 ] From To Array[ 2 ] From To … From To Array[ N ] From To N – количество ду г в орграфе X . Связанное представление данных : одномерный массив Spisok указателей на с труктуру index , представляющую собой элемент списка и содержащий поле : целочисленное i ndex (содержит номер вершины , в кото рую входит дуга ) и Next - указатель на структуру Spisok , указывающее на следующий элем ент списка Spisok[ _ ] NEXT index next index n ext Index Next Spisok[ 1 ] To … To NULL … To … To NULL Spisok[ N ] To … To NULL N - коли чество вершин в графе Y , Z . 2. Внешнее опи сание программы. Ввод информации об неориентированных графах происходит из файла , формат которого должен быть нижеследующим : N X1 1 X1 2 ... X1k1 0 X2 1 X2 2 ... X2k2 0 ... XN 1 XN 2 ... XNkN 0 Y1 1 Y1 2 ... Y1k1 0 Y2 1 Y2 2 ... Y 2 k 2 0 ... YN 1 YN 2 ... YNkN 0 где N - число верш ин в графах Xij - номер очередной вершины смежной i в графе X ( i = 1.. N , j =1.. ki ) Yij - номер очеред ной вершины смежной i в графе Y ( i = 1.. N , j =1.. ki ) Если из какой-то вершины не выходит ни одного ребра , то для нее в исх одных данных задаем только ноль (например ‘ 0’ - верши на 2 изолирована ). Таким образом , для каж дого графа должно вводится в общей сложно сти N нолей. Формат печати результатов работы програм мы представлен в следующем формате : Даны неориентированные графы X и Y без кратностей. Для каждого графа задаем номера верши ны смежности с данной. Граф X (в ЭВМ в последовательном представлении ): 1 : X1 1 X1 2 ... X1k1 2 : X2 1 X2 2 ... X2k2 ... N : XN 1 XN 2 ... XNkN Граф Y (в ЭВМ в связанном представ лении ): 1 : Y1 1 Y1 2 ... Y1k1 2 : Y2 1 Y2 2 ... Y2k2 ... N : YN 1 YN 2 ... YNkN Над графами выполняется операция раз ности двумя способами с получением нового графа Z (в связанно м представлении ): 1 : Z 1 1 1, Z 1 2 ... Z 1 k 1 2 : Z 2 1 Z 2 2 ... Z 2 k 2 ... N : ZN 1 ZN 2 ... ZNkN И исправлени ем старого графа X (в последовательном представ лении ): 1 : X1 1 X1 2 ... X1k1 2 : X2 1 X2 2 ... X2k2 ... N : XN1 XN2 ... XNkN Кол-во вер шин , кол-во дуг графа X, кол-во дуг графа Y и кол-во времени , затраченного на в ычисление разности X и Y: N MX MY T где T - кол-во времени , затраченного на вычисление разности X и Y Zij - номер оче редной вершины смежной i в графе Z ( i = 1.. N , j =1.. ki ) MX - кол-во дуг в графе X MY - кол-во дуг в графе Y Метод решени я : Принцип реш ения основан на методе полного перебора , ч то конечно не лучший вариант , но все-таки лучше , чем ничего . Аномал ии исходных данн ых и реакция программы на них : 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 ( смотри рисунок ) требуется провести прямую так , что бы величина всех отклонений отвечала условию : N F = K=1 Где В моём случае T(NX,NY,NZ)=O(NX*(NY+NZ) => T(NX,NY,NZ)=C1*NX*(NY+NZ)+C2*(NY+NZ)+C3*(NY)+C4*(NZ) Следовательно для моего примера мы получим : Для того чтобы получить значение функции на K- том экспери менте , мы засекаем значение времени перед вызовом функции , которая реализует алгоритм , в ставим оператор вида : TikTak=clock(); Где функция clock () даёт время с точностью до нескольких миллисекун д (в языке С ++ она описана в заголовочн ом файле time.h) . После выполнения процедуры , реализует а лгоритм , мы находим разность времени TikTak=cloc() - TikTak; После всех проделанных манип уляций нужно приров нять к нулю все частные производные . Это будет выглядеть , в общем виде , примерно так : После раскрытия скобок и замены T(n)= T(n)=(c, (n))= получим Положим А 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 – количество дуг в графе. O(N)=N Процедура вычисления разности гр афов с возвращающим значен ием последовательного гр афа : Array * RaznostZ(int n, int &n1, Array *X, Spisok **Y,Array *Z) N - количество дуг графа N1 – количество вершин в графе Х X – грав в последовательном представлен ии Y - грав в связаном представлении Z – грав в последовательном представлен ии O(N,N1)=N 1*N*k=N1*N2 N2 – количество вершин в графе Y Процедура вычисления разности графов с возвращающим значением последовательного графа : Spisok * RaznostY(int n, int &n1, Array *X, Spisok **Y) N - количество дуг графа N1 – количество вершин в графе Х X – грав в последовательном предс тавлении Y - грав в связаном представлении O(N,N1)=N1*N*(k+l)=N1*(N3+N2) N2 – количество вершин в графе Y N3 – количество вершин в графе Z – возвращаемом. Процедура ввода графов в последовательном представлении : Spisok **ReadFileY( Spisok **Y, char *st) St – указатель на строку с именем файла из которого будет происходить ввод Y - грав в связаном предс тавлении O(N,N1)=N+N2 N2 – количество вершин в графе Y Процедура ввода графов в последовательном представлении : Array *ReadFileY( Array *X, char *st) St – указатель на строку с именем файла из которого будет происходить ввод X – грав в последовател ьном представлении O(N,N1)=N2 N2 – количество вершин в графе X Текст про граммы. # include # include

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по программированию "Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru