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




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

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

Кафедра кибернетики и

вычислительной техники


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

к курсовой работе

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

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


Выполнил:

cт. гр. М-22д

Сивков С.А.

Вариант задания: 11

Проверил:

ст.пр. Воронин Д.Ю.

Севастополь

2012

Содержание

Введение...................................................................................................................4

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

2. Анализ задачи……………………………………………………………...….–

2.1. Основные положения теории расписаний………………….…...….7

2.2. Выбор и обоснование методов решения……………………………8

2.2.1. Метод полного перебора……………………………………..–

2.2.2. Генетический алгоритм…………………….………………..9

3. Алгоритм решения задачи………………………………………………..…12

3.1. Метод полного перебора…………………………………………....–

3.2. Генетический перебор ……………………..…………………….....14

4. Описание программы……………………………………………….…….....16

4.1. Описание структуры данных………………………………………..–

4.2. Описание программы…………………………………………......….–

5. Методика тестирования программы……………………………………......18

5.1. Проверка ветви метода прямого перебора………………………....–

5.2. Проверка ветви метода изолированных мутаций………………….–

5.3. Тестирование………………………………………………………..19

6. Анализ результатов работы…………………………………………….…....–

Заключение…………………………………………………………….……......21

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

Приложение А………………………………………………………….………..23

Приложение Б…………………………………………………………….……..35

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

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

Теория расписаний — раздел дискретной математики, занимающийся проблемами упорядочения. Задачи теории расписаний можно разделить на 2 группы:

  • задачи с прерываниями (когда в момент поступления нового требования старое требование (задача) может быть прервана, т.е. отложена, с возможностью завершения позже)

  • задачи без прерываний (то есть каждое требование выполняется до конца без прерываний).

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

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

В курсовой работе рассмотрены 2 метода: 1 – метод полного перебора, наиболее точный, 2 – метод – генетический – быстрый.

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

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

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

Пусть ЭВМ необходимо обслужить множество N={1,2,...,n}требований. Требование k, поступает на обслуживание в момент времени dk>=0 и для обслуживания требует tk единиц времени. Обслуживание требования k желательно завершить к директивному сроку Dk>=0. Функция штрафа k(x)=max(x-Dk,0). Процесс обслуживания требования k допускает прерывание, во время которого может быть обслужено требование k’. Прерывание обслуживания более чем одного требования не допускается. Определить такой порядок выполнения программ, при котором суммарный штраф будет минимален. -фактическое время завершения обслуживания требования k.

  1. Анализ задачи

Данная задача относится к классу задач упорядочения.

Задано некоторое множество требований N={1,2,3,…,n} поступающих на обслуживание в ЭВМ. Требуется составить расписание так, чтобы все требования были выполнены, при условии что время на выполнение всех требований будет минимальным, т.е. результат зависит от порядка выполнения требований. При построении порядка выполнения требований нужно учитывать такие параметры как время для подготовки каждого требования и время перехода от одного требования к другому, прерывание требования, именно эти параметры влияют на конечное затраченное время и соответственно на функцию штрафа .

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

^ Входные данные: количество требований представлено как int переменная n; длительности обслуживания для каждого требования представлено одномерным массивом длины n;прерывание представлено переменной типа int pr; директивные сроки представлены в виде одномерного массива типа int (Обслуживание требования k желательно завершить к директивному сроку Dk>=0 ). Функция штрафа представляет собой критерий, по которому можно определить какая из последовательностей требований занимает меньшее время при обработке.

^ Выходные данные: оптимальный порядок требований, суммарный штраф и критерий — минимальное время обслуживания всех требований системой.

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

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

^ 2.1.Основные положения теории расписаний

Расписанием s =s (t)={s1(t),s2(t),...,sM(t)} называется совокупность M кусочно-постоянных, непрерывных слева функций sL=sL(t), каждая из которых задана на промежутке 0 t< и принимает значения 0, 1, 2,..., n, причем если sL(t)=k0 при некотором t=t’, то sH(t’)k для любых 1LHM. Выражение sL(t)=k0 означает, что в момент времени t=t’ прибор L обслуживает требование k. Ecли sL (t’) = 0, то в момент времени t=t’ прибор L свободен.

Расписание должно удовлетворять:

  • условию полноты: суммарная длина промежутков, на которых функции sL(t) принимают значения sL(t)0, равна tk.

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

Будем говорить, что расписание s=s(t) допускает прерывания в процессе обслуживания требований, если существуют такие 1 kn, 1LHM и 0t’

  1. sL(t’)= sL(t’’)=k, но sL(t) k

  2. sL(t’)= sH(t’’)=k

Содержательно, процесс обслуживания требований без прерываний удовлетворяет следующему условию. Каждое требование обслуживается только одним прибором. Если процесс некоторого требования k начинается в момент времени tk, то оно протекает непрерывно и завершается в момент времени tk+ tk.

Предполагается, что число разрывов каждой из функций sL(t) конечно.

Каждому расписанию s соответствует вектор времен завершения обслуживания требований при этом расписании. Значение , - наибольшее значение t, при котором .

Качество расписания s характеризуется значением действительной кусочно-непрерывной монотонно возрастающей функции F()=F(x1,x2,...,xn) при x=.

^ 2.2.Выбор и обоснование методов перебора

Задача построения оптимального расписания однопроцессорной ЭВМ является NP-сложной.

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

Генетический метод более быстрый, чем полный перебор.

^ 2.2.1.Метод полного перебора

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

^ Метод полного перебора даёт однозначно точное решение поставленной задачи без каких-либо погрешностей и неточностей. Однако это достигается путём сложных и многочисленных вычислений. Например, для задачи всего с 4-мя программами будет построено 4! (24) расписаний, для которых будет вычислена функция штрафа и после этого среди всех расписаний осуществляется поиск минимального элемента. Для пяти программ число построенных расписаний возрастёт до 120, а всего при 8-ми программах метод будет вынужден построить 40320 расписаний. Таким образом, при увеличении числа программ n на 1, сложность вычислений увеличивается в n+1 раз.

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

2.2.2. Генетический перебор.

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

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

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

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

Кроссовер - обмен частями генетической цепи между лучшими представителями поколения.

Мутация - изменение случайного гена в цепи.

В рамках данной задачи генетической цепью (представителем, особью) можно называть конкретное расписание. Геном будет являться конкретная программа, стоящая в генетической цепи на определённом месте. Так же следует подчеркнуть, что в получении потомства участвует одна единственная (лучшая) особь поколения, поскольку при совершении операции кроссовера возможна ситуация, когда одна особь (расписание) будет содержать два одинаковых гена (программы), или не содержать какой-либо ген, что противоречит постановке задачи.

Для данной задачи необходимо переопределить метод получения нового поколения - операцию мутации. Пусть дана особь (расписание), со следующим генотипом: 01234. Это означает, что ген (программа) 0 будет стоять на первом месте (выполняться первой), ген (программа) 1 на втором месте и будет выполняться после программы 0, и т.д. Допустим этот представитель выбран для дальнейшей эволюции как лучший представитель поколения. Тогда для него применяется операция мутации: случайным образом выбирается место мутации, например 2 (это означает, что место мутации (разрыва) будет после элемента 2, перед 3), и элементы, стоящие в плотную к разрыву переставляются местами. В данном случае, после операции мутации получится особь 01324.

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

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

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

Пусть n - длина генотипа вида. Тогда пусть k = n-1; l=2*n. Такое значение означает, что будут выполнены все возможные единичные мутации родительского генотипа. l, равное 2*n даёт достаточную длительность эволюции для достаточной точности ответа. Таким образом, суммарное число итераций (построенных расписаний) получим равное (n-1)*2n. Т.е., допустим для n=7 генов (программ) число итераций будет равно (7-1)*2*7 = 6*14 = 84+1. В результат приписан +1, поскольку родитель участвует в выборе лучшего представителя в следующем поколении и формула не учитывает добавление самого первого родителя. 85 это намного меньше, чем 7! (5040).
  1   2   3

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

Похожие:

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

Пояснительная записка к курсовой работе по дисциплине «Вычислительный практикум» iconПояснительная записка к курсовому проекту по дисциплине "Вычислительный...
Анализ поставленной задачи

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

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

Пояснительная записка к курсовой работе по дисциплине «Вычислительный практикум» iconПояснительная Записка к Курсовой Работе по Дисциплине «Информатика. Основы Программирования»

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

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

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

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

Пояснительная записка к курсовой работе по дисциплине «Вычислительный практикум» iconПояснительная записка к курсовой работе по дисциплине системное программное обеспечение
Тема: Разработка программы на языке c для ос linux с использованием системного api

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


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


<