Федеральное агентство по образованию
Бийский технологический институт (филиал)
государственного образовательного учреждения
высшего профессионального образования
«Алтайский государственный технический университет
им. И.И. Ползунова»
В.Д. Лисица, В.В. Царегородцева
РАСЧЕТ ПЛОЩАДЕЙ ФИГУР И ИХ ПЕРЕСЕЧЕНИЯ МЕТОДОМ МОНТЕ-КАРЛО
Методические рекомендации по выполнению курсовых работ
по дисциплине «Информатика»
для студентов инженерных специальностей
Бийск
Издательство Алтайского государственного технического
университета им. И.И. Ползунова
2008
УДК 681.3.06
ББК 32.973-01
Рецензент доцент кафедры МРСиИ, к.т.н. Смирнов В.В.
Работа подготовлена на кафедре информатики и вычислительной математики
Лисица, В.Д.
Расчет площадей фигур и их пересечения методом Монте-Карло: методические рекомендации по выполнению курсовых работ по дисциплине «Информатика» для студентов инженерных специальностей / В.Д. Лисица, В.В. Царегородцева; Алт. гос. техн. ун-т, БТИ. – Бийск: Изд-во Алт. гос. техн. ун-та, 2008. – 18 с.
В методических рекомендациях излагаются основные требования, предъявляемые к курсовым работам, приводится последовательность этапов решения задач и перечень программных средств, необходимых для получения результатов и их последующего оформления в виде законченной печатной работы, предъявляемой на защиту.
УДК 681.3.06
ББК 32.973-01
Рассмотрены и одобрены на заседании кафедры
информатики и вычислительной математики
Бийского технологического института
Протокол № 57 от 02 апреля 2008 г.
© В.Д. Лисица, В.В. Царегородцева, 2008
© БТИ АлтГТУ, 2008
СОДЕРЖАНИЕ
ВВЕДЕНИЕ……………………………………………………………………………………..4
1 СТРУКТУРА РАБОТЫ…………………………………………………………………..5
1.1 Титульный лист…………………………………………………………………………………………..5
1.2 Задание на курсовую работу…………………………………………………………………………….5
1.3 Содержание………………………………………………………………………………………………..5
1.4 Введение……………………………………………………………………………………………………5
1.5 Основные главы…………………………………………………………………………………………..6
1.6 Заключение………………………………………………………………………………………………...6
1.7 Список использованных источников…………………………………………………………………..6
2 РАБОТА НАД ПЕРВОЙ ГЛАВОЙ……………………………………………………..7
2.1 Постановка задачи………………………………………………………………………………………..7
2.2 Метод решения……………………………………………………………………………………………7
3 РАБОТА НАД ВТОРОЙ ГЛАВОЙ……………………………………………………..9
3.1 Генератор случайных точек (раздел 2.1 курсовой работы)………………………………………....9
3.2 Алгоритм решения (раздел 2.2 курсовой работы)……………………………………………………9
3.3 Решение задачи на языке Pascal (раздел 2.3 курсовой работы)…………………………………...10
3.4 Решение задачи в системе MathCAD (раздел 2.4 курсовой работы)……………………………...10
4 ОФОРМЛЕНИЕ РАБОТЫ……………………………………………………………..12
ПРИЛОЖЕНИЕ А. Образец титульного листа……………………………………………………………….13
ПРИЛОЖЕНИЕ Б. Образец Задания…………………………………………………………………………...14
ПРИЛОЖЕНИЕ В. Метод проверки решения задачи в системе MathCAD………………………………15
ПРИЛОЖЕНИЕ Г. Варианты фигур для заданий 2006-2007 учебного года……………………………....17
ВВЕДЕНИЕ
Компьютерные технологии решения самых разнообразных задач и последующее документальное оформление полученных результатов повсеместно используются в инженерной, педагогической и научной деятельности. При этом от специалиста требуется комплексное владение современными программными средствами, знание основ программирования и численных методов, а также подготовка научно-технической документации с помощью соответствующих текстовых и графических редакторов. Поэтому на заключительной стадии общеобразовательного курса «Информатика» для студентов инженерных специальностей предусмотрена специальная курсовая работа, направленная на формирование указанных знаний и навыков.
Выполнение предлагаемой курсовой работы включает в себя следующие основные этапы:
1) постановка задачи;
2) изучение численного метода решения;
3) изучение и практическое применение основных элементов системы MathCAD;
4) разработка эффективного алгоритма решения;
5) написание и отладка компьютерных программ;
6) расчеты и анализ результатов;
7) оформление работы в виде печатного варианта;
8) защита работы.
Учебным планом предусматривается, что ко времени выполнения курсовой работы студенты изучили в достаточной степени основы программирования на универсальных языках программирования типа Pascal (Delphi), а также дополнительно ознакомились с возможностями специализированной системы математических вычислений MathCAD. Оформление печатного варианта курсовой работы рекомендуется проводить с помощью текстового редактора Word, необходимые графические элементы выполняются с использованием любого из графических редакторов по усмотрению исполнителя (Paint, Corel Draw, AutoCAD и т.п.). Дополнительно рекомендуется использовать компьютерные сети Интернет для получения соответствующей справочной и учебной информации по заданной теме.
1 СТРУКТУРА РАБОТЫ
Курсовая работа должна содержать следующие основные разделы:
o Титульный лист
o Задание на курсовую работу
o Содержание
o Введение
o Глава 1. Описание метода решения
1.1. Постановка задачи
1.2. Метод решения
o Глава 2. Решение задачи
2.1. Генератор случайных чисел
2.2. Алгоритм решения
2.3. Решение на языке Pascal
2.4. Решение в системе MathCAD
o Заключение
o Список использованных источников
При необходимости количество разделов можно расширить, например, добавить приложения.
1.1. Титульный лист
Титульный лист оформляется в соответствии с образцом, приведенным в Приложении А.
1.2. Задание на курсовую работу
Задание на проведение курсовой работы оформляется в соответствии с образцом, приведенным в Приложении Б. При оформлении печатного варианта Задание помещается после титульного листа и включается в общую нумерацию страниц.
1.3. Содержание
В Содержании приводятся названия заголовков основных разделов работы (см. выше), начиная с Введения с указанием номеров соответствующих страниц.
1.4. Введение
Во Введении кратко излагаются роль и значение численных методов решения математических задач и их отличия от классических методов. Приводятся исторические сведения о методе Монте-Карло, объясняется смысл его названия и указываются области его практического применения.
Далее раскрываются цели и задачи курсовой работы, перечисляются программные средства, используемые при решении задачи и оформлении полученных результатов.
1.5. Основные главы
Основными являются Глава 1 и Глава 2. Каждая из них начинается с новой страницы. Содержание этих глав рассматривается ниже.
1.6. Заключение
В этом разделе кратко излагаются основные результаты, полученные в работе, и приводятся числовые значения искомых величин.
1.7. Список использованных источников
Все сведения и утверждения (кроме общеизвестных), не являющиеся авторскими, должны снабжаться ссылками на источник информации. В качестве таких источников можно использовать печатные издания, а также электронные материалы с указанием соответствующих сайтов (и соответствующей даты).
2 РАБОТА НАД ПЕРВОЙ ГЛАВОЙ
В первой главе делается постановка задачи, описывается метод решения, приводятся варианты заданий.
1.8. Постановка задачи
Каждому варианту курсовой работы соответствует свой уникальный набор двух фигур. В Приложении Г в качестве примера приводится полный набор фигур, использованный при задании в 2007 г. Все фигуры построены с использованием только двух элементов – прямых и окружностей, поэтому от исполнителя требуется составлять и понимать их уравнения. Рисунки фигур, а также все поясняющие схемы выполняются с помощью любого графического редактора по усмотрению исполнителя.
Ниже в качестве образца оформления дается постановка задачи для некоторого условного варианта (рисунок 2.1).
1.9. Метод решения
Для решения данной задачи будем использовать метод Монте-Карло. Для нашей простой задачи суть его состоит в следующем. Пусть дана некоторая плоская фигура (рисунок 2.2), требуется рассчитать ее площадь.
Опишем вокруг заданной фигуры другую фигуру простой формы (круг, прямоугольник и т.п.), площадь которой легко можно рассчитать. Мы будем здесь использовать прямоугольник (рисунок 2.2) с соответствующими координатами вершин (x1, y1) и (x2, y2).
В полученный прямоугольник будем случайным образом (по возможности равномерно) помещать точки с координатами (x, y), удовлетворяющими условию , . Часть таких точек попадет вовнутрь исследуемой фигуры, другая часть окажется за ее пределами. Обозначим через NN общее количество точек, N – количество точек, попавших в фигуру. Тогда можно записать приближенное равенство
, (1)
где S – искомая площадь, SS – площадь прямоугольника.
Из формулы (1) получим итоговое расчетное соотношение
. (2)
Таким образом, используемый метод является приближенным. Точность расчета по (2) существенно зависит от количества заданных случайных точек и качества генератора случайных чисел. Для нашей задачи рекомендуется задавать NN>10000.
Расчет площади пересечения двух фигур проводится аналогично. Допустим, исследуемые фигуры имеют вид, показанный на рисунке 2.3.
Вокруг них опять описываем прямоугольник так, чтобы обе фигуры целиком помещались в нем. В полученный прямоугольник случайным образом «бросаем» точки и подсчитываем, какое их количество попадет в область пересечения фигур (на рисунке 2.3 заштриховано). Напомним, что точка считается попавшей в область пересечения, если она одновременно принадлежит обеим фигурам. Далее расчет проводим по формуле (2).
Отметим, что использованный метод легко распространяется и на большее число фигур.
3 РАБОТА НАД ВТОРОЙ ГЛАВОЙ
В данной главе описывается алгоритм решения данной задачи, приводится тек
1.10. Генератор случайных
точек (раздел 2.1 курсовой работы)
В разделе 2.1 курсовой работы описываются программные средства создания случайных чисел в заданном диапазоне (генератор случайных чисел). Поскольку каждая точка на плоскости определяется двумя числами – координатами x и y, то нам нужны соответственно два таких генератора. Мы их построим на основе стандартных функций:
random – для языка Pascal, которая возвращает случайные числа в диапазоне [0,1];
rnd(1) – для системы MathCAD с аналогичным действием.
Для того чтобы координаты случайной точки подчинялись условию
в языке Pascal можно использовать следующие линейные преобразования:
В системе MathCAD используются аналогичные соотношения, только вместо функции random применяется функция rnd(1).
Примечание –
В языке Pascal перед первым оператором, использующим функцию random, рекомендуется обратиться к стандартной процедуре Randomize, которая будет каждый раз менять генерируемую последовательность случайных чисел.
1.11. Алгоритм решения (раздел 2.2 курсовой работы)
В данном разделе дается понятие алгоритма и способы его создания. Для исполнителя предлагается два варианта создания алгоритма программ:
° в виде графической блок-схемы;
° словесное описание с нумерацией пунктов.
В первом случае используются стандартные графические обозначения ключевых элементов программы, во втором – их словесный аналог, например:
1) Задаем прямоугольник: x1=…; y1=…; x2=…; y2=…;
2) Рассчитываем площадь прямоугольника Spr=(x2-x1)(y2=y1);
3) …
4) …
5) …
1.12. Решение задачи на языке
Pascal (раздел 2.3 курсовой работы)
В разделе 2.3 курсовой работы приводится текст программы, написанной на языке Pascal, и результаты соответствующих расчетов. Программа должна быть отлажена и обязательно снабжена необходимыми комментариями. В качестве примера ниже приведем небольшой фрагмент такой программы.
Program FigSurface;
Const
x1=-2; y1=-2; x2=2; y2=2; {координаты вершин прямоугольника}
ss = (x2-x1)*(y2-y1); {площадь прямоугольника}
NN=10000; {количество случайных точек}
. . .
{Расчет первой фигуры}
. . .
{Расчет второй фигуры}
. . .
Рекомендуется при написании программы определить несколько вспомогательных функций. Например, написать две функции логического типа F1(x, y) и F2(x, y), которые для заданных значений координат некоторой точки (x, y) возвращают значения true или false в зависимости от того, находится точка внутри фигуры или вне ее.
Поскольку программа на языке Pascal хранится на диске в виде текстового файла, то при оформлении курсовой работы текст программы легко вставляется в документ редактора Word.
1.13. Решение задачи в системе
MathCAD (раздел 2.4 курсовой работы)
В данном разделе приводится текст соответствующей программы в системе MathCAD. Кроме решения основной задачи здесь рекомендуется провести графическую проверку правильности составления логических выражений, необходимых для решения данной задачи. Как показывает опыт проведения курсовых работ, именно в этих разделах допускается наибольшее количество ошибок. Покажем это на следующем примере.
Допустим, исследуемая фигура имеет вид, показанный на рисунке 3.1.
Опишем вокруг этой фигуры прямоугольник (т.е. зададим значения (x1, y1) и (x2, y2)).
В полученный прямоугольник будем случайным образом помещать точки (x, y). Требуется определить, какие из этих точек попадут вовнутрь заданной фигуры и количество таких точек.
Решение этой задачи, выполненное в системе MathCAD, приведено в Приложении В.
В этом решении вначале специально допущена ошибка в логическом выражении, определяющем попадание точек в верхнюю часть фигуры, что сразу видно из соответствующего графика. Ниже приводится исправленный вариант.
В курсовой работе целесообразно провести такую проверку для каждой фигуры, а также можно вывести профиль области их пересечения.
Отметим, что решение данной задачи в системе MathCAD можно провести более эффективно, используя встроенный язык программирования (так называемые программные модули). Однако в рамках обычного курса «Информатики» этот раздел, как правило, не изучается. Предлагается для инициативных студентов, желающих повысить свой творческий потенциал и (само)оценку, самостоятельно освоить эти возможности (что совсем не трудно при умении программировать на языке Pascal) – такие инициативы, безусловно, поощряются!
4
ОФОРМЛЕНИЕ РАБОТЫ
Законченная работа должна быть отпечатана, скреплена (сброшюрована) и подписана исполнителем на титульном листе. После этого она сдается преподавателю на проверку. Основные требования к оформлению работы:
1. Формат страницы: А4, портрет.
2. Поля: верхнее, нижнее, левое –2,5 см, правое – 2 см.
3. Основной текст: Times New Roman, кегль 10 или 12 пт., отступ первой строки – 1 см,
выравнивание по ширине.
4. Междустрочный интервал: одинарный, полуторный или двойной.
5. Рисунки: выполняются в черно-белом цвете в формате *.jpg или *.gif и вставляются
непосредственно в текст. Подписи под рисунками – Times New Roman, кегль 9 пт., выравнивание по центру. Нумерация рисунков сквозная, следует после слова "Рис.". Далее после знака "–" с прописной буквы следует подпись.
6. Математические символы и обозначения в тексте: Times New Roman, кегль 11 пт., курсив.
Формулы набираются в редакторе MathType. Нумерация формул сплошная, выравнивание нумерации по правому краю.
Таблицы могут вставляться на ширину рабочего поля страницы. Заголовок таблицы: "Табл. 1" – Times New Roman, кегль 11 пт., выравнивание по левому краю. Текст внутри таблицы – Times New Roman, кегль 10 пт.
7. Список использованных источников: Times New Roman, кегль 10 пт. Список источников
выполняется в виде нумерованного списка, выравнивание номера по левому краю, выступ – 0,7 см, без табуляции.
ПРИЛОЖЕНИЕ А
ОБРАЗЕЦ ТИТУЛЬНОГО ЛИСТА
|
ПРИЛОЖЕНИЕ Б
ОБРАЗЕЦ ЗАДАНИЯ
Федеральное агентство Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
«Алтайский государственный технический университет
им. И.И. Ползунова»
Бийский технологический институт (филиал)
Кафедра информатики и вычислительной математики
УТВЕРЖДАЮ
Зав. кафедрой ИВМ
__________ Г.И. Севодина
«25
» февраля 2008 г.
ЗАДАНИЕ
На курсовую работу по дисциплине «Информатика»
студенту_____________________________________________________
группа________УК-71
___________ факультет Механический
Тема проекта: Численные методы расчета площадей сложных фигур
Срок сдачи студентом законченного проекта _____1.06.08
Исходные данные к проекту: (Текст задания) Вариант 1А-2Б
Для двух заданных фигур с помощью метода Монте-Карло рассчитать их площади и площадь их пересечения. Изучить численный метод, составить алгоритм расчета, написать и отладить программы на языке
Pascal 7.0 и в системе
MathCAD. Оформить результаты расчетов в соответствии с методическими рекомендациями.
Дата выдачи задания:____19.02.08
_____________________ (Ф.И.О.) ________________ (подпись студента)
ПРИЛОЖЕНИЕ В
МЕТОД ПРОВЕРКИ РЕШЕНИЯ В СИСТЕМЕ
MathCAD
ПРИЛОЖЕНИЕ Г
ВАРИАНТЫ ФИГУР ДЛЯ ЗАДАНИЙ
2006-2007 УЧЕБНОГО ГОДА
Лисица Владимир Дмитриевич
Царегородцева Валентина Всеволодовна
РАСЧЕТ ПЛОЩАДЕЙ ФИГУР И ИХ ПЕРЕСЕЧЕНИЯ МЕТОДОМ МОНТЕ-КАРЛО
Редактор Соловьева С.В.
Технический редактор Сазонова В.П.
Подписано в печать 15.04.08. Формат 61х 86/8
Усл. п. л. – 2,09. Уч.-изд. л. – 2,25.
Печать – ризография, множительно–копировальный
Аппарат «RISO TR 1510»
Тираж 100 экз. Заказ 2008-30.
Издательство Алтайского государственного
технического университета им. И.И. Ползунова
656099, г. Барнаул, пр. Ленина, 46.
Оригинал-макет подготовлен ИИО БТИ АлтГТУ.
Отпечатано в ИИО БТИ АлтГТУ.
659305, г. Бийск, ул. Трофимова, 29.