Методические указанияКМРИЗ. Методические указания к лабораторным работам первого цикла по компьютерным методам решения инженерных задач Волгоград 2006
 Скачать 1.74 Mb.
|
|
Министерство сельского хозяйства РФ Департамент научно-технолгической политики и образования Федеральное государственное образовательное учреждение Высшего профессионального образования «Волгоградская государственная сельскохозяйственная академия» Кафедра: “Электротехнологии в сельском хозяйстве” Методические указания к лабораторным работам первого цикла по компьютерным методам решения инженерных задач  Волгоград 2006 Методические указания к лабораторным работам по дисциплине “Компьютерные методы решения инженерных задач” / Сост. Елисеев Д.С.; Волгоградская государственная с.х. академия. Волгорад 2009.28 с. Рассматриваются общие вопросы о составлении и анализе алгоритмов решения инженерных задач, методах расчёта линейных и нелинейных разветвлённых электрических цепей, компьютерной обработке электронных сигналов, расчёте освещённости рабочих поверхностей и распознавания формы физических объектов. Предназначаются для студентов факультета электрификации сельского хозяйства, обучающихся по специальности 110302. Общие указания Для выполнения лабораторной работы студент должен заранее ознакомиться с содержанием и методикой её выполнения, получить общее представление об ожидаемых результатах опытов. Для этого следует изучить теоретический материал по лекциям и рекомендуемой литературе. К лабораторному занятию нужно подготовить таблицы для записи результатов измерений и расчётов, вычертить необходимые схемы. Непосредственно перед решением задач преподаватель проверяет готовность каждого студента к работе. Во время выполнения лабораторных работ каждый студент должен соблюдать правила техники безопасности. По полученным результатам работы студент должен аккуратно оформить отчёт в соответствии требованиям ГОСТ 2.105-96. Отчёт, оформленный с нарушениями предъявляемых требований, к защите не допускается. При защите отчёта студент должен решить поставленную перед ним задачу любыми методами с использованием ЭВМ и дать исчерпывающие пояснения по выполненной работе. Лабораторная работа №1 Исследование сложности алгоритмов инженерных расчётов Цель работы: 1) исследовать зависимости времени выполнения предложенного алгоритма от размера задачи при различных типах исходных данных; 2) оценить временную сложность алгоритма. Краткие теоретические сведения С увеличением размера задачи (количества обрабатываемых элементов) возрастает время на её решение. Это связано с тем, что выполнение какого-либо действия над одним элементом происходит в течение конечного времени. Следовательно, чем больше размер задачи, тем больше таких операций и тем дольше будет время вычислений. Очевидно, что чем меньше время вычислений, тем меньше операций выполняется исследуемым алгоритмом, т.е. тем проще сам алгоритм. Так, например, для человека сложить в уме несколько чисела проще, чем десяток или сотню. Условно принято оценивать сложность алгоритмов решения инженерных задач по двум показателям – времени их выполнения и объёму занимаемой памяти. В используемой программе для измерения времени выполнения алгоритма целочисленные и вещественные типы данных подобраны так, что они содержат одинаковое количество информации – по 48 бит на один элемент вектора данных, поэтому сравнивать объёмы занимаемой памяти для этих типов нет смысла – они одинаковы. При определении сложности необходимо учитывать размер задачи. Поэтому для математического описания сложности алгоритмов используется функциональная зависимость времени выполнения от размера вектора данных. В этом случае инженеру предоставляется возможность сравнивать и определять наиболее эффективный алгоритм из множества предлагаемых. Наибольшее распространение получила полиномиальная оценка сложности алгоритмов:  (1.1)где M(N) – сложность алгоритма; N – размер задачи (мощность вектора данных). ak – постоянные положительные коэффициенты, зависящие от производительности ЭВМ; n – порядок оценки; В представленной формуле порядок оценки n является старшей степенью полинома  . В связи с тем, что разница в производительности различных ЭВМ существенна, на практике принято не учитывать в представленной математической записи все члены с младшими степенями, а коэффициент при старшей степени принимают равным единице. В этом случае зависимость (1.1) принимает асимптотический вид: (1.2)В этой зависимости показатель степени n определяет сложность алгоритма. Такой способ оценки значительно проще и не связан с производительностью ЭВМ. Результат, найденный по формуле (1.2) называется асимптотической оценкой сложности. А сама оценка записывается как  (читается – сложность порядка n). Так, например, в случае линейной зависимости времени вычисления от размера задачи показатель степени  – сложность  .При оценке временной сложности удобно использовать аппаратные средства самого компьютера, а именно – счётчик прерываний таймера, которые обрабатываются микропроцессором в обычном режиме работы 91 раз за 5 секунд. Переменная, хранящая текущее значение счётчика таймера располагается в оперативной памяти компьютера по адресу h0040:h006C и занимает ровно 4 байта. Значение этой переменной увеличивается на единицу примерно через каждые 55 мс автоматически с момента включения компьютера, независимо от количества выполняемых процессором задач. Поэтому для оценки времени выполнения того или иного алгоритма достаточно прочитать и запомнить показания счётчика до его запуска и после выполнения. Разницу в показаниях следует умножить на 55, получив тем самым значение затраченного времени, выраженного в миллисекундах. Отчёт должен содержать:
Программа работы
Варианты заданий Вариант задания выдаётся преподавателем каждой бригаде студентов из таблицы 1.1: Таблица 1.1 – Варианты заданий для оценки временной сложности алгоритмов
|