Учебная работа № /7375. «Диплом Разработка алгоритма программного обеспечения

Выдержка из похожей работы

X1k1

2 :
X21 X22 ..,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»216/3,Это происходит потому, что стандартный тип int
не может вместить в себя более чем 216,Мне же требуется для нормально работы
программы, чтобы тип вмещал в себя утроенное количество вершин
неориентированного графа,Конечно, это всего лишь приближение, но с учётом
того, что графы генерируются случайно возможность набора 33000 невелико и,
следовательно, допустимо.

Входной файл генерируется каждый раз новый,

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

Оценка временной сложности.

Каткие сведения о временной сложности.

            Качество
алгоритма оценивается как точность решения и эффективность алгоритма, которая
определяется тем временем, которое затрачивается для решения задачи и
необходимым объёмом памяти машины.

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

            Размерность
задачи – это совокупность параметров, определяющих меру исходных данных.
Временная оценка алгоритма бывает двух типов:

1,  
априорная –
асимптотическая оценка сложности

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

Именно
асимптотическая оценка алгоритма определяет в итоге размерность  задачи,
которую можно решить с помощью ЭВМ,Если алгоритм обрабатывает входные данные
размера N за
время CN2, где С – некая постоянная, то говорят, что временная сложность
этого алгоритма есть .
Вернее говорить, что положительная и нулевая функция  есть , если существует такая постоянная С,
что  для всех
отрицательных значений N.

Вычисление
временной сложности.

            Для
того, чтобы проверить правильность временной оценки алгоритма, надо знать
априорную оценку сложности»