Вычислительная практика

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

Севастопольский национальный технический  университет

 

 

 

 

 

 

Кафедра кибернетики и вычислительной техники

 

 

 

Пояснительная записка

к курсовому проекту

по дисциплине:

«Вычислительная практика»

 

 

 

 

 

 

Выполнил:

ст. гр. М-24д

Перевёртов М.А.

Проверила:

Окорокова Е.С.

 

 

 

 

 

Севастополь

2003

 

Содержание 

 

 

Введение……………………………………………………………………………………………3

1.Постановка задачи………………………………………………………………4

2.Описание алгоритма……………………………………………………………5

3.Описание программы……………………………………………………………7

4.Тестовые примеры…………………………………………………………………9

5.Анализ результат………………………………………………………………12

Заключение……………………………………………………………………………………13

Литература……………………………………………………………………………………14

Приложение …………………………………………………………………………………15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

 

 

 

 

 

 

 

 

 

 

 

1. Постановка  задачи

Пусть ЭВМ необходимо обслужить множество N={1,2,...,n}требований. Требование k, поступает на обслуживание в момент времени d_k>=0 и для обслуживания требует t_k единиц времени. Обслуживание требования k желательно завершить к директивному сроку D_k>=0. Функция штрафа j_k(x)=c_k*max(x-D_k,0)², где c_k>0-некоторый коэффициент, характеризующий степень важности выполнения программы в срок. Определить такой порядок выполнения программ, при котором суммарный штраф будет минимален. -фактическое время завершения обслуживания требования k.

 

 

 

Входные данные:

1. Количество заданий, которые необходимо обслужить(к=1..10).
2. Начальный момент времени, в который должно начаться выполнение требования.
3. Количество времени необходимое для выполнения ЭВМ каждого требования.
4. Директивный срок, к которому желательно завершить обслуживание требования.
5. Некоторый коэффициент, характеризующий степень важности выполнения программы в срок.

2. Описание  алгоритма

По заданию  мне необходимо по входным данным составить такую  последовательность требований, при которой суммарный штраф будет минимален, т.е. решение данной задачи сводится к полному перебору всех возможных последовательностей и вычислению штрафа с запоминанием последовательности с минимальным штрафом. Полный перебор заключается в том, что мы переставляем элементы множества N = {1,2,...,n}. Символической записью этой конструкции является p = (i₁,i₂,i_3,..., i_n).Под задачей упорядочения понимается, как правило, задача построения одной или нескольких перестановок, удовлетворяющих определенным ограничениям и доставляющих экстремум некоторой функции или функциям, определенным на рассматриваемом множестве перестановок.

Пусть Р — некоторое множество (не обязательно всех) перестановок p=(i₁, i₂,i₃ . . ., i_n) элементов множества N = {1, 2, ..., n}.

Под st-окрестностью k-то по порядку элемента в перестановке  p (обозначение Q_st (p, k)) будем понимать упорядоченный набор <Q,s_s,s_t >, где s_s== (i_max(1,k-s+i), ... , i_k-1,i_k) и s_t== (i_k+1,i _k+2 ... , i_min(n,k+\t))— перестановки длины min(k, s) и min (n-k,t) соответственно и Q— множество (неупорядоченное) элементов {i₁, i₂,i₃..., i_k-s}. Если k £ s, то Q = Æ. Предполагается, что s³O и t³0.

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

F (p, k) = Ф [F(p, k - 1), Q_st (p, k)]

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

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

1. Инициализация. Выбор начальной расстановки p. Определение функции F(p,n). Запомнить расстановку p^* как оптимальную.
2. Пока  существуют нерассмотренные варианты перестановки выполнять п.3-4.
3. Генерировать следующую расстановку p^*. Вычислить F^*(p^*,n).

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

 

 

 

 

 

 

 

 

 

 

 

3. Описание программы

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

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

2.Считанные данные помещаются в массив требований.

3.В цикле  обрабатываем данные с первой  до последней последовательности.

4.Определяем штраф последовательности.

5.Полученный  штраф сравниваем с оптимальным,  если он меньше, то запоминаем штраф и последовательность.

6.Определяем  следующую последовательность.

7.Выводим результат  в компонент TEdit.

 

Объявленные типы данных в программе:

Type Demand = array[1..10] of integer

iCountNumber:Integer – содержит количество требований

DK,D,TK,C,Current,Best:Demand;

DK - вектор, содержит моменты времени поступления требований;

D – вектор, содержит директивные сроки требований;

TK – вектор, содержит времена выполнения требований;

C – вектор, содержит степень важности требований;

 

 

 

 

 

Процедуры и функции:

function Current_Penalty(New:Demand):integer;

Функция расчета  суммарно штрафа последовательности по формуле  , возвращает число целого типа.

function Fact(n_fact:integer):integer;

Функция, которая  возвращает факториал числа n_fact.

procedure TMain.GoProcessClick(Sender: TObject);

процедура начала процесса обработки и вычисления.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Тестовые примеры.

Пример 1: Без штрафа

Входные данные:

Номер требований    1  2   3

                 tk 2  8   13

                 dk 1  5   4

                 Dk 3  13  17

                 Ck 2  2   2

Число всевозможный комбинаций равняется 3!=6

Номер требований    1  2   3

tk(нач.)            2  8   13

tk(заверш.)         3  13  17

j_k(x)              0   0   0

Так как все требования выполняются в директивный срок, суммарный штраф равен нулю.

Так как степень важности одинакова для каждого требования и требование 1 начинается в ранний момент времени, то обработка требования начинается с него.

Пример 2:

Входные данные: С штрафом

Номер требований    1  2   3

                 tk 8  2   5

                 dk 3  5   7

                 Dk 14 4  13

                 Ck 3  3   3

Так как степень  важности одинакова для каждого  требования и требование 2 начинается в ранний момент времени, затем обрабатывается 1 требование, потом 3.

Номер требований    2  1   3

tk(нач.)            2  8   11

tk(заверш.)         7  11  18

j_k(x)              3   0   5

Вычислим штраф: =57

Пример 3:с разным коэффициентом важности.

Входные данные: С штрафом

Номер требований    1  2   3

                 tk 5  3   1

                 dk 4  8   2

                 Dk 10 7  6

                 Ck 2  1   4

Так как степень  важности одинакова для каждого  требования и требование 3 начинается в ранний момент времени, затем обрабатывается 1 требование, потом 2.

 

Номер требований    3  1   2

tk(нач.)            1  5   9

tk(заверш.)        3  9  16

j_k(x)              0   0  9

Вычислим штраф: =64

 

 

 

 

 

 

 

 

Построим график зависимости времени от количества требований, для этого вычислим время  которое необходимо для вычисления от 3 до 10 требований.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5.Анализ работы программы

Для выполнения программа использует компонент StringGrid, что позволяет быстро и легко изменять данные для требования, а также наглядно показывает всю информацию о каждом требовании. При помощью кнопки  ADD можно добавить требование, а спомощью кнопки Delete удалить. Результат работы программы записывается в поле ввода в таком виде:

Оптимальная последовательность и минимальный штраф.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

В курсовой работе рассмотрены  методы реализации программного комплекса  оптимизации работы программ-требований, при заданных критериях времени и оценки штрафа.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список  литературы

1. Методические указания по курсовому проектированию по дисциплине «Вычислительный практикум» для студентов дневной и заочной формы обучения специальности 7.091501 / Сост. проф. Скатков А.В., Сергеев Г. Г. – Севастополь: Изд-во СевГТУ, 1997. – 23 с.
2. Гофман В. Э., Хомоненко А. Д., Delphi 5. – СПб.: БХВ – Санкт-Петербург, 2000. – 800 с.: ил.
3. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. - М.: «Наука».1976 г. - 256 с.
4. Португал В.М., Семенов А.И. Теория расписаний. -М.: «Знание».-1972 г. - 61 с.
5. Дейкстра Э. Дисциплина программирования. -М.: «Мир».1978 г. - 275с.
6. Советов Б.Я., Яковлев С.А. Моделирование систем: Курсовое проектирование. -М.: ВШ., 1988 г. - 135 с.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Приложение .

 

Текст программы.

 

unit MainForm;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids, Buttons, ComCtrls,math, ExtCtrls;

 

 

type

  TMain = class(TForm)

    GoProcess: TButton;

    StringGrid1: TStringGrid;

    Result: TEdit;

    Indicator: TLabel;

    Panel1: TPanel;

    Add: TBitBtn;

    Delete: TBitBtn;

    procedure GoProcessClick(Sender: TObject);

    procedure FormActivate(Sender: TObject);

    procedure AddClick(Sender: TObject);

    procedure DeleteClick(Sender: TObject);

  private

    { Private declarations }

  public

 

    { Public declarations }

  end;

type Demand = array[1..10] of integer;

var

  Main: TMain;

  iCountNumber:integer;

  DK,D,TK,C,Current,Best:Demand;

implementation

 

{$R *.dfm}

 

 

procedure Follow_Sequence;

var

i,j,k:integer;

begin

j:=iCountNumber;

i:=j-1;

while (Current[i]>Current[i+1]) do Dec(i);

while (Current[i]>=Current[j]) do Dec(j);

k:=Current[i];

Current[i]:=Current[j];

Current[j]:=k;

Inc(i);

j:=iCountNumber;

while (i<j) do

        begin

        k:=Current[i];

        Current[i]:=Current[j];

        Current[j]:=k;

        Inc(i);

        Dec(j);

        end;

end;

 

 

function Current_Penalty(New:Demand):integer;

var

full_time,summ_penalty,index:integer;

begin

full_time:=0;

summ_penalty:=0;

for index:=1 to iCountNumber do

        begin

        full_time:=full_time+TK[ New[index] ]+Max(DK[ New[1] ]-full_time,0);

        summ_penalty:=summ_penalty+C[ New[index] ] * Max(full_time - D[ New[index] ],0)* Max(full_time - D[ New[index] ],0);

        end;

Current_Penalty:=summ_penalty;

end;

 

function Fact(n_fact:integer):integer;