Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум»




Скачать 379.62 Kb.
НазваниеМетодические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум»
страница1/4
Дата публикации03.02.2014
Размер379.62 Kb.
ТипМетодические указания
uchebilka.ru > Информатика > Методические указания
  1   2   3   4


Министерство образования и науки,

молодежи и спорта Украины
Севастопольский национальный технический

университет


Методические указания

к выполнению курсовой работы

по дисциплине «Вычислительный практикум»

для студентов заочной формы обучения

специальности 6.05010201

Севастополь

2012

УДК 519.688 (07)
Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» для студентов заочной формы обучения специальности 6.05010201, Сост. А.В. Скатков, Г.Г. Сергеев, Л.П. Луговская. – Севастополь: Изд-во СевНТУ, 2012. – 23 с.

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


Методические указания рассмотрены и утверждены на заседании кафедры кибернетики и вычислительной техники (протокол № ____ от «____»____________2012 г.)
Допущено учебно-методическим центром СевНТУ в качестве методических указаний.
Рецензент – к.т.н., доцент Фисун С.Н.

Введение
Курсовая работа предназначена для практического усвоения студентами основных разделов дисциплины «Программирование», а также раздела «Комбинаторика» дисциплины «Высшая математика». Студентам предлагается разработать и реализовать на ЭВМ программную систему планирования работы вычислительного комплекса.

В задачи курсовой работы по дисциплине «Вычислительный практикум» входит:

  • развитие у студентов навыка научно-исследовательской работы в области разработки сложных программных систем;

  • умение составлять многошаговые итерационные алгоритмы;

  • навык анализа научно-технической литературы в области программирования и прикладной математики;

  • использование стандартов, справочников, технической документации по математическому и программному обеспечению ЭВМ и др.

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

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

^ 1. Основные этапы выполнения курсовой работы
Подготовительный этап (1-3 неделя). Уточнение постановки задачи. Анализ научно-технической литературы с целью обоснования выбора метода решения. Разработка спецификации на программную систему.

^ Проектный этап.(4-8 недели). На этом этапе рассматриваются различные пути реализации поставленной задачи, предлагаются критерии оценки эффективности алгоритма и оценка с их помощью различных вариантов решения. На этом этапе разрабатывается алгоритмическое и программное обеспечение моделирования.

^ Реализационный этап (9-12 недели). В начале этого этапа вырабатывается наиболее рациональное решение по машинной реализации модели системы и составляется график дальнейшей работы, в ходе которой необходимо реализовать алгоритм средствами выбранного языка программирования, выполнить окончательную отладку, получить результаты и проанализировать их.

^ Оформительский этап (13-14 недели). На данном этапе выполняется оформление пояснительной записки в соответствии с требованиями к оформлению технической документации, регламентируемыми стандартом Украины.

^ Заключительный этап (15-16 недели). На этом этапе проводится защита курсовых работ. Студент обязан представить окончательно оформленную пояснительную записку к курсовой работе не позже чем за два дня до защиты. На заключительном этапе проводится подготовка доклада и защита курсовой работы перед комиссией. Доклад должен сопровождаться демонстрацией работы программы. В докладе в сжатой форме следует представить поставленную задачу, основное содержание курсовой работы, краткий анализ состояния изучаемого вопроса, обоснование и принятие решения, анализ полученных результатов.

^ 2. Методы решения задачи планирования работы вычислительных систем.
2.1 Задача планирования работы вычислительных систем. В настоящем разделе рассматриваются основные методы решения задач, связанных с планированием работы вычислительных систем. Круг вопросов, связанных с построением наилучших планов работ (расписаний), особенно с разработкой математических методов получения решений с использованием соответствующих моделей, изучается в рамках теории расписаний [1]. Наиболее известной в теории расписаний задачей является задача построения оптимального (в том или ином смысле) расписания процесса решения задач (выполнения программ) некоторой совокупностью «машин». При решении данной задачи в рассматриваемой системе необходимо закрепить решаемые задачи за ЭВМ, согласовать длительности решения задач и установить порядок их выполнения во времени.

Простейшим и наиболее изученным классом задач теории расписаний являются задачи упорядочения. В этих задачах распределений задач по ЭВМ и длительности их выполнения предполагаются заданными. Необходимо указать наиболее эффективную стратегию управления очередями задач на выполнение каждой ЭВМ.

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

Наконец, в задачах распределения предполагается, что один и тот же блок может выполнять различные работы или наборы работ. Необходимо указать в некотором смысле наилучшее распределение работ по блокам.

На практике предложены и используются различные способы представления расписаний. Наиболее наглядны из них графические представления - графики Ганта, ленточные графики, планировочные графики, циклограммы и т.п. Во многих случаях общепринятым является табличное представление, в достаточной степени наглядное и не требующее дополнительных пояснений. Для представления в ЭВМ широко используется специфическая форма представления расписаний посредством задания вектор-функции времени. Компоненты вектор-функции s(t)={s1(t),s2(t),...sn(t)} описывают загрузку обслуживающих приборов 1,2,3,...,n во времени. Если si(t’)=0, то в момент времени t=t’ обслуживающий прибор свободен. Если si(t’)=k, то в момент времени t=t’ прибор обслуживает требование с номером k. Выбор той или иной формы представления расписаний определяется конкретными условиями, в которых возникает необходимость в их составлении и рассмотрении.


  1. ^ Комбинаторные методы решения задач теории расписаний

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

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

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

Понятие перестановки хорошо рассматривается в [1] — расположение элементов некоторого множества в любом порядке (без повторений) представляет собой перестановку элементов этого множества. Перестановка обычно представляется последовательностью элементов (чисел) из N == {1,2,...,n}. Символической записью этой конструкции является  = (i1,i2,i3,..., in).

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

Пусть Р — некоторое множество (не обязательно всех) перестановок =(i1, i2,i3 . . ., in) элементов множества N = {1, 2, ..., n}.

Под st-окрестностью k-то по порядку элемента в перестановке  (обозначение Qst (, k)) будем понимать упорядоченный набор s,t >, где s== (imax(1,k-s+i), ... , ik-1,ik) и t== (ik+1,i k+2 ... , imin(n,k+\t))— перестановки длины min(k, s) и min (n-k,t) соответственно и Q— множество (неупорядоченное) элементов { i1, i2,i3 . . ., ik-s }. Если k  s, то Q = . Предполагается, что sO и t0.

Требуется найти перестановку * Р, которой соответствует наименьшее значение функции F (, n), заданной на Р рекуррентным соотношением

F (, k) = Ф [F(, k - 1), Qst (, k)]

где F (, 0)— известная не зависящая от  величина, а функция, стоящая в правой части этого соотношения, неубывающая по F (, k—1).

Практически все задачи упорядочения, предлагаемые для решения в данном курсовом проекте могут быть решены реализацией следующего простого алгоритма:

  1. Инициализация. Выбор начальной расстановки . Определение функции F(,n). Запомнить расстановку * как оптимальную.

  2. Пока существуют нерассмотренные варианты перестановки выполнять п.3-4.

  3. Генерировать следующую расстановку *. Вычислить F*(*,n).

  4. Если F*(*,n)> F(,n) запомнить расстановку * как оптимальную.

Задача о следующей перестановке (алгоритм Дейкстры) рассмотрена в [3].

Пусть требуется написать внутренний блок, выполняющий действие над глобальной целой векторной переменной, именуемой с, при

с_ниж=1 и с_вер=n

для некоторого постоянного значения n(n>1). Кроме того известно, что упорядоченная последовательность значений с(1),с(2),...,с(n) является некоторой перестановкой значений от 1 до n, но не последней в алфавитном порядке: n, n-1, ...1. Внутренний блок должен преобразовать последовательность c(l), с (2), ..., с(n) в последовательность, являющуюся ее посредственным следующим по алфавиту преемником. Например, при n=9 последовательность

1 4 6 2 9 5 8 7 3

должна быть преобразована в последовательность

1 4 6 2 9 7 3 5 8

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

с (k) сохраняется для 1 k < i

с (k) изменяется для k=i

Значение i определяется как максимальное значение i(
После того как i найдено, необходимо отыскать в «хвосте», т. е. среди значений с(j) при i+ljn, новое значение с(i). Т.е. требуется найти такое значение j в интервале i+ljn, что с(j) есть наименьшее значение, удовлетворяющее условию

c(j)>c(i)

После того как j найдено, с(i) должно получить свое новое значение, для чего используется операция «с: переставить(i, j)». Дополнительным преимуществом этой операции является то, что после ее выполнения вся последовательность продолжает оставаться перестановкой чисел от 1 до n; заключает всю цепочку действий переупорядочивание значений в хвосте последовательности, чтобы монотонно возрастали. Общая структура программы представляется в виде:

  1. определение i;

  2. определение j;

  3. c: переставить (i, j);

  4. сортировка хвоста

Операция «с: переставить (i, j)» не нарушает монотонности значений функции в хвосте, и поэтому «сортировка хвоста» сводится к расположению значений в обратном порядке.

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

Переменные:

c : вектор;

i,j : целое;

Начало:

i:=n-1;

Пока (c[i]>=c[i+1]) i:=i-1;

j:=n;

Пока (c[j]<=c[i]) j:=j-1;

c:переставить(i,j);

i:=i+1; j:=n;

Пока (i

н.ц.

c:переставить(i,j);

i:=i+1;

j:=j-1;

к.ц.

Конец.


  1. Методы планирования работы систем с одним обслуживающим прибором

Пусть конечный поток требований N={1,2,3,...,n}, поступающих на обслуживание в заданные моменты времени, обслуживается одним прибором. В каждый момент времени прибор обслуживает не более одного требования. Требование k, поступает на обслуживание в момент времени dk>=0 и для обслуживания требует tk единиц времени. Порядок обслуживания может быть произвольным, либо регламентироваться заданными отношениями частичного порядка. При некоторых постановках задачи могут допускаться прерывания в обслуживании каждого отдельного требования. Необходимо так организовать процесс обслуживания, чтобы он в том или ином смысле был наилучшим.

Процесс обслуживания может быть описан заданием кусочно-постоянной, непрерывной слева функции s =s (t), принимающей при 0 t одно из значений 0, 1, 2,..., n. Если s(t)=k0, то в момент времени t прибор обслуживает требование k; если s (t) = 0, то в момент времени t ни одно из требований не обслуживается. Эта функция называется расписанием.

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

  • условие полноты: для любого 1 k n существует 0 < t < , такое, что s (t)=k; суммарная длина промежутков, на которых s (t) = k, равна tk;

  • условие готовности к обслуживанию: s(t) k для всех tk;

  • условие упорядоченности: если по условию задачи требование i необходимо обслужить раньше требования j и s (t') == i, то s (t)  j для всех t < t';

  • условие непрерывности: если по условию задачи прерывания в обслуживании требований не допускаются и s {t') == s (t") = k  0, то s (t) == k для всех t' < t < t".

Расписания s =s (t), которые удовлетворяют перечисленным условиям, называются допустимыми.

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

При рассмотрении задач такого рода под допустимым расписанием будем понимать такое расписание s=s(t), которое удовлетворяет всем требованиям, вытекающим из постановки конкретно рассматриваемой задачи.

Каждому допустимому расписанию s = s (t) соответствует вектор времен завершения обслуживания требований при этом расписании. Значение , , таковы что и s(t)k для всех t>.

Предполагается, что качество расписания s определяется вектором , т.е. каждому расписанию s ставится в соответствие значение некоторой скалярной функции F() вектора , определяемого расписанием s. Наиболее распространенным является следующий способ задания F(). Для каждого требования задается неубывающая кусочно-непрерывная функция k(x), выражающая в количественном отношении «штраф», который необходимо «заплатить», если обслуживание этого требования завершится в момент времени х. В качестве F() выбирается одна из функций или . Функции k(x) называются функциями штрафа. Расписание, которое удовлетворяет всем условиям рассматриваемой задачи, называется оптимальным, если ему соответствует наименьшее значение F().

Если прерывания обслуживания каждого отдельного требования запрещены, то активное расписание однозначно определяется заданием последовательности =(i1, i2,i3 . . ., in), в которой эти требования обслуживаются. Таким образом, решение задачи может быть получено в результате рассмотрения конечного числа расписаний, определяемых возможными последовательностями обслуживания требований. Такие расписания называются перестановочными. Если множество N не упорядочено, то число перестановочных расписаний n!.

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

Рассмотрим весьма простые методы решения задачи оптимального упорядочения требований для некоторых частных случаев функций штрафа. Пред­полагается, что множество N требований не упорядочено, критерий опти­мальности расписания — суммарный штраф.

Пусть требования i и j обслуживаются непосред­ственно друг за другом и их обслуживание начинается в момент времени t  0. Если при этом первым обслужи­вается требование i, то суммарный штраф за обслужива­ние этих требований



Если первым обслуживается требование j, то суммарный штраф за обслуживание этих двух требований



Определим



Величина Rij (t) показывает, насколько изменяется суммарный штраф при переходе от последовательности, при которой требование i начинало обслуживаться в мо­мент времени t непосредственно перед требованием j, к последовательности, отличающейся от исходной транс­позицией элементов i и j.

Если Rij(t)<0, то при решении вопроса, какое именно из двух последовательно обслуживаемых требова­ний i и j необходимо начать обслуживать в момент вре­мени t, предпочтение следует отдать требованию i. Ана­логично, если Rij {t)>0, то первым в момент времени t следует обслуживать требование j. Наконец, если Rij {t)=0, то порядок обслуживания этих требований безразличен.

Поскольку функции i(x) и j(x) предполагаются кусочно-непрерывными в интервале (0, ), то этот интервал может быть разбит на конечное число интерва­лов, в каждом из которых величина Rij(t) положительна. отрицательна или равна нулю.

Интервал (1, 2) называется интервалом очередности типа i  j, если Rij(t)<0 для всех t(1, 2). Eсли Rij(t)>0 для всех t(1, 2) интервал (1, 2) называется интервалом очередности типа j  i. При Rij(t)=0 для всех t(1, 2) порядок обслуживания требований безразличен.

Величина Rij(t) по определению зависит от значений t, ti, tj и функций штрафа i(x) и j(x). В каждом конкретном случае в результате несложных преобразований могут быть выделены интервалы очередности.

Задание интервалов очередности оказывается весьма полезным при поиске оптимальных расписаний методом последовательного конструирования вариантов.

Директивным сроком называется момент времени Dk>0, к которому необходимо или, во всяком случае, желательно завершить обслуживание требования . В общем случае не удастся построить такого расписания, при котором обслуживание каждого требования k завершается не позднее заданного директивного срока Dk. Появляется объективная необходимость в нарушении от­дельных директивных сроков, что сопряжено с определенными потерями. Эти потери, как правило, зависят от того, какие именно требования и на сколько задерживаются с обслуживанием. Иными словами, каждому требованию отнесена неубывающая кусочно-непрерывная функция штрафа k(x)=0 при х  Dk и k(x)>0 при х > Dk. Требуется определить расписание обслужива­ния п требований, при котором суммарный штраф наи­меньший.

В [1] предлагается алгоритм конструирования оптимальной относительно F() последовательности обслуживания требований, когда k(x)=max(x-Dk,0), :

  1. Упорядочим множество N всех требований по не­убыванию значений Dk. Обозначим полученную последовательность D=(i1, i2,i3 . . ., in). Если при этом все требования обслуживаются в срок, то D - оптимальная последовательность.

  2. Упорядочим множество N всех требований по не­убыванию значений tk. Обозначим полученную последо­вательность t=(j1, j2,j3 . . .,jn).Если при этом Dik<Dij. или , то t - оптимальная последовательность.

  3. Из множества N выберем требование Ln с tLn = max (tk). Если Dk(
    tLn,DLn) для всех kN, то в оптимальной последовательности это требование мож­но обслуживать последним .

  4. Среди требований множества Np выберем требова­ние Ln-р с DLn-р= mах Dk. Если tLn-р+ Dk>tl для всех kNp, то в оптимальной последовательности требования множества Np будут обслуживаться первыми в порядке неубывания значений Dk. В про­тивном случае обозначим Np через М.

  5. Разобьем множество М на два подмножества М1 и М2 по следующему принципу: если для jM существует iM такое, что интервал (1=0, 2=tk) является интервалом очередности типа i  j , to jM2, остальные требования принадле­жат множеству М1. Иными словами, множество M1 со­стоит из конкурентноспособных претендентов на первооче­редное обслуживание в оптимальной последовательности среди всех требований множества М.

  6. Выберем произвольное требование L1M1 и пред­положим, что в оптимальной последовательности это тре­бование обслуживается первым среди всех требований множества М. Уменьшим значение Dk для всех kM, kL1 на величину tL1 и перейдем к выполнению пп. 3—4, полагая N = М \ L1. Таким образом, в результате при­нятия гипотезы, что первым в оптимальной последователь­ности обслуживается требование L1, получаем множество М (L1)M все еще неупорядоченных требований. Аналогичные рассуждения проводим относительно ос­тальных требований множества М1.

  7. Перейдем к последовательному рассмотрению ситуа­ций вида: требование L1 обслуживается первым и М (L1) — множество все еще неупорядоченных требований. Повто­ряем пп. 5, 6, полагая М =- М (L1) и принимая в качестве Dk значения исходных директивных сроков, уменьшенных на величину tL1. Затем перейдем к последовательному рассмотрению ситуаций вида: требования L1, L2, обслуживаются первыми в последовательности (L1, L2) и M(L1, L2) - множество все еще неупорядоченных требований и т.д.

В результате получаем конечное множество последовательностей, среди которых выбираем последовательность *, которой соответствует наименьшее значение F(). Эта последовательность является искомой.
  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению курсовой работы по дисциплине «Основы маркетинга»
Бобрушева В. В. Методические указания к выполнению курсовой работы по дисциплине «Основы маркетинга» для студентов 2 курса дневной...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению курсовой работы по дисциплине...
Методические указания к выполнению курсовой работы по дисциплине «Техническая термодинамика»/ Составители

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению курсовой работы «Гребные электрические...
Методические указания к выполнению курсовой работы «гребные электрические установки» по дисциплине «электрические системы и комплексы...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания и задания к выполнению курсовой работы по дисциплине...
Методические указания и задания к выполнению курсовой работы по дисциплине „Планирование деятельности предприятия” / составители:...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению курсовой работы по дисциплине...
Методические указания к выполнению курсовой работы по дисциплине «Планирование деятельности предприятия» / И. С. Грабовский, С. А....

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению курсовой работы “управление вспомогательными...
Методические указания к выполнению курсовой работы “Управление вспомогательными механизмами и общесудовыми системами судна” по дисциплине...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к курсовой работе по курсу "Разведка месторождений полезных ископаемых"
Методические указания к выполнению курсовой работы по дисциплине «Разведка месторождений полезных ископаемых» (для студентов очной...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания и исходные данные к выполнению курсовой работы...
Методические указания и исходные данные к выполнению курсовой работы (ргз) по дисциплине “Механика грунтов, основания и фундаменты”(для...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению контрольной работы по дисциплине...
Методические указания к выполнению контрольной работы по дисциплине «Локальные информационные сети» для студентов специальности 090803...

Методические указания к выполнению курсовой работы по дисциплине «Вычислительный практикум» iconМетодические указания к выполнению расчетно-графической работы по...
Методические указания к выполнению расчетно-графической работы по дисциплине: «Гражданская оборона» (для студентов всех специальностей...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<