 |
Математическое обеспечение и оценка трудоемкости алгоритма
|
|
|
|
Объектно-ориентированные языки и системы программирования
Вариативная часть Б1. Б.6
Прикладная математика и информатика
Ханты-Мансийск
2016 год
Оглавление
Оглавление. 2
Общие положения. 3
Цель курсового проектирования. 3
Тематика курсового проектирования. 3
Оформление курсового проекта. 3
Содержание курсового проекта. 4
Основная часть. 4
Постановка задачи. 4
Математическое обеспечение и оценка трудоемкости алгоритма. 5
Язык разработки. 5
Реализация системы.. 6
Аналитическая часть. 8
Порядок защиты курсового проекта. 9
Список использованных источников. 12
Приложение А. 13
Приложение Б. 16
Приложение В. 17
Общие положения
Настоящие методические указания предназначены для обеспечения курсового проектирования дисциплины «Объектно-ориентированные языки и системы программирования» для студентов направления подготовки 01.04.02 «Прикладная математика и информатика»
Цель курсового проектирования
Целью курсового проектирования является изучение технологий объектно-ориентированного программирования на современных языках программирования.
В ходе выполнения курсового проекта решаются следующие основные задачи:
- Освоить новый объектно-ориентированный язык программирования и приобрести навыки разработки приложений на нем.
- Закрепить навыки поиска научно - технической литературы и её анализа.
- Освоить правила оформления проектной и эксплуатационной документации.
Тематика курсового проектирования
Выполнение проекта осуществляется студентом на основе выданного ему индивидуального задания на курсовой проект.
Типовая тема курсового проекта: Реализация алгоритма (указывается название алгоритма, например, Дейкстры) на языке (указывается язык разработки, например, Pithon).
|
|
|
Список базовых алгоритмов и языков приведен в Приложениях Б и В соответственно.
Студентам, по согласованию, могут быть предложены индивидуальные, нестандартные задания по теме данной дисциплины, связанные с выполнением госбюджетных и хоздоговорных НИР и ОКР, проводимых на кафедре. В свою очередь, студент может самостоятельно предложить тему КП, отличающуюся повышенной актуальностью, связанную с выполнением НИРС или предстоящей выпускной квалификационной работы. Тема КП утверждается в установленные кафедрой сроки. Основные руководящие данные для выполнения проекта оформляются студентом совместно с преподавателем в заданиях по курсовому проектированию.
Выполнение курсового проекта предусматривает работу по созданию новой или развитию существующей программной системы.
По согласованию с преподавателем, возможна работа над одной темой группой студентов (2-3 человека). При этом каждый участник группы отвечает за выполнение своей части общего проекта. Зона ответственности каждого участника коллективного проекта явно прописывается в его задании на курсовой проект.
Оформление курсового проекта
Оформление пояснительной записки курсового проекта должно соответствовать «Общим правилам оформления студенческих работ» [1].
Содержание курсового проекта
Курсовой проект состоит из пояснительной записки и приложений. Основными требованиями к пояснительной записке являются: четкость и логическая последовательность изложения материала, убедительность аргументации, краткость и ясность формулировок. В тексте записки не должно быть общих фраз, очевидных выводов и т. п. Рекомендуемый объем пояснительной записки – 30-40 страниц текста.
Выбор каждого проектно-технологического решения должен проводиться из нескольких альтернатив и быть тщательно обоснован. При этом рекомендуется на страницах пояснительной записки проводить анализ альтернативных вариантов архитектуры системы, программно-технологических платформ и подходов, а результаты проведенного анализа помещать в тот или иной раздел соответствующего приложения.
|
|
|
Общая структура пояснительной записки должна соответствовать «Общим правилам оформления студенческих работ» [1].
Основная часть
Основная часть пояснительной записки к курсовому проекту должна включать в себя следующие разделы:
- Постановка задачи;
- Математическое обеспечение и оценка трудоемкости алгоритма;
- Язык разработки;
- Реализация системы;
- Аналитическая часть.
Постановка задачи
Основным документом, в соответствии с которым выполняется разработка некоторого проекта в любой отрасли, включая проекты по разработке программного обеспечения (ПО), является техническое задание (ТЗ).
ТЗ может содержать системные требования, требования к тестированию и др. Техническое задание позволяет обеим сторонам (заказчику и исполнителю) согласовать все необходимые детали реализации ПО, спланировать сроки и этапы выполнения проекта. Кроме того, ТЗ позволяет заказчику требовать от исполнителя соответствия продукта всем без исключения условиям, оговорённым в ТЗ, а исполнителю на законных основаниях отказаться от выполнения работ, не указанных в ТЗ.
Возможны различные варианты подготовки ТЗ:
- в соответствии с государственным стандартом ГОСТ 34.602-89 [2], предполагающим детальное описание всех возможных аспектов разработки ПО и требующим подготовку значительного по объему документа;
- в соответствии со стандартом IEEE Std 830, предполагающим различные способы структурирования детальных требований для различных классов систем и позволяющим детализацию, достаточную для понимания;
- в соответствии с некоторым упрощенным корпоративным шаблоном оформления.
При разработке ТЗ в рамках выполнения курсовой работы предлагается использовать третий вариант подготовки ТЗ, предполагающего следующую структуру.
1. Введение
1.1. Наименование продукта
|
|
|
1.2. Краткая характеристика области применения
2. Основание для разработки
2.1. Документ, на основании которого ведется разработка
2.2. Организация, утвердившая документ
3. Назначение разработки
4. Требования к разработке
4.1. Требования к функциональным характеристикам
4.2. Требования к надежности
4.3. Требования к составу и параметрам технических средств
4.4. Требования к информационной и программной совместимости
5. Требования к программной документации
6. Технико-экономические показатели
7. Этапы разработки
8. Порядок контроля и приемки.
При подготовке ТЗ особое внимание следует уделить п.4.1. В нем необходимо детально указать перечень требований к разрабатываемому ПО так, чтобы не только полностью соответствовать заданию, но и по возможности расширить его за счет дополнительных функциональных характеристик.
При коллективном выполнении задания особое значение приобретает планирование работы и определение зоны ответственности каждого члена группы разработчиков. Соответствующая информация об этапах и сферах ответственности указывается в п.7. При этом следует избегать групповой ответственности за выполнение того или иного этапа, оставляя такую возможность только для исключительных случаев.
Математическое обеспечение и оценка трудоемкости алгоритма
Перед реализацией ПО необходимо подробно описать и проанализировать с теоретической точки зрения алгоритм работы программы. В этом разделе также приводятся данные о временной сложности алгоритма. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Временная сложность зачастую оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом, где элементарная операция занимает для выполнения фиксированное время.
По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объёме используемой памяти.
|
|
|
Язык разработки
Одной из задач курсового проектирования является изучение нового объектно-ориентированного языка программирования и реализация на нем информационной системы. Поэтому в курсовом проекте следует уделить внимание основным особенностям и характеристикам выбранного языка с точки зрения объектно-ориентированной парадигмы и использованным в работе его функциональным возможностям.
При описании выбранного языка желательно проводить сравнение его с другими современными языками программирования.
Типовая структура раздела следующая:
1. Общие сведения о языке (класс, автор, краткая история, среды разработки).
2. Поддерживаемые парадигмы программирования.
3. Типизация.
4. Особенности компилятора/интерпретатора.
5. Реализованные типы и структуры данных.
6. Объектно-ориентированные возможности.
7. Функциональные возможности.
8. Дополнительные сведения (управление памятью, исключения, расширения языка и т.п.).
Реализация системы
В разделе реализации системы необходимо описать три основные этапа: проектирование, кодирование и тестирование.
При проектировании необходимо указать ключевые проектные решения относительно внутреннего устройства программной системы и её технических интерфейсов. Проектные решения описываются в виде комплекта взаимосвязанных диаграмм. Для этого рекомендуется использовать нотации UML или IDEF. На диаграммах должны быть отображены:
- общая архитектура системы (представление о компонентах системы, взаимосвязях между компонентами, а также правилах, регламентирующих эти взаимосвязи) и её связи с внешней средой;
- устройство (структура и алгоритм работы) ключевых компонентов;
- объектно-ориентированная структура (иерархия классов с основными методами и полями);
- пользовательский интерфейс.
Описание этапа кодирования предполагает раскрытие основных технологических приемов программирования, характерных для выбранного языка и использованных при разработке системы.
Не рекомендуется включать в пояснительную записку весь исходный код системы. В пояснительной записки упор делается на ключевых методах использованных объектов и написанном коде, реализующем основной алгоритм, соответствующий теме курсового проекта.
При написании кода следует придерживаться типового для языка стандарта кодирования. Такой стандарт сильно зависит от используемого языка программирования, но в рамках всей работы он должен быть строго выдержан.
Например, для языка Java [3], [4] можно придерживаться следующего стандарта оформления кода:
- в качестве способа выбора названий и используемый регистр символов для имён переменных и других идентификаторов (стиль именования переменных, констант и функций; запись типа переменной в её идентификаторе) следует использовать венгерскую нотацию;
|
|
|
- количество операторов на строчке должно быть равно 1.
- все операторы, входящие в составной оператор (все, что находится между { } в языке Java) должны быть сдвинуты вправо на 5 (пять) символов (используйте табуляцию, настройте редактор, если он меньше);
- открывающая скобочка должна находиться на той же строчке, что и следующий до блока оператор, а закрывающая должна находиться строго на одной линии по вертикали с началом оператора, предшествующем данному составному.
- обязательны пустые строки перед и после определений функций. Логические части функции тоже нужно отделять друг от друга пустой строкой, например, цикл от предшествующих или последующих операторов.
- тип переменной необходимо указывать для КАЖДОЙ из них. На одной строчке - одна переменная. Идентификаторы (названия переменных, типов, подпрограмм) должны быть значимыми настолько, чтобы читающий текст программы мог понимать смысл всех переменных и т.д. без присутствия рядом автора.
- использовать пробелы при оформлении арифметических выражений.
В исходном коде обязательно наличие комментариев.
Однако надо помнить, что комментарии должны объяснять намерения программиста, а не код; то, что можно выразить на языке программирования, не должно выноситься в комментарии – в частности, надо использовать говорящие названия (название объекта определяется его смысловым содержанием) переменных, функций, классов, методов и пр., разбивать программу на лёгкие для понимания части, стремиться к тому, чтобы структура классов и структура данных были максимально понятными и прозрачными и т. д.
Комментировать необходимо:
- заголовок файла, пакета и класса описывающий их содержимое;
- заголовок функции, поясняя назначение ее аргументов и смысл самой функции;
- ключевые для алгоритма переменные и структуры данных;
- наиболее важные основные этапы и особенности реализуемых алгоритмов.
Недопустимо комментировать каждую строку кода. При защите работы это рассматривается как незнание языка программирования.
Тестирование – один из основных инструментов обеспечения безотказной корректной работы ПО, в конечном итоге влияющим на общее качество и коммерческую конкурентоспособность программного продукта. Поэтому в курсовом проекте необходимо уделить достаточное внимание этому важному этапу.
Как минимум, тестирование должно предусматривать последовательное выполнение следующих этапов:
- разработку плана тестирования и тестовых заданий;
- выполнение тестовых процедур функционального модульного и системного тестирования;
- выполнение тестовых процедур нагрузочного тестирования;
- формирование заключения по результатам.
Заключение о результатах тестирования должно содержать вывод об устойчивости и корректности работы при различных условиях (видах тестирования, тестовых заданиях) отдельных модулей и подсистем, а также системы в целом.
Основным требованием к такому заключению является то, что при внешней оценке оно должно позволить сделать вывод либо об успешном завершении этапа тестирования и возможности передачи разработанной системы в опытную эксплуатации, либо о необходимости ее доработки (с указанием – в какой части: подсистема, возможные причины и пути устранения).
Разрабатываемое ПО должно содержать минимальный комплект эксплуатационной документации, включающий в себя эскизный проект системы, который создается на этапе проектирования и руководство пользователя.
Руководство пользователя (руководство по эксплуатации, руководство оператора) – документ, назначение которого – предоставить людям помощь в использовании некоторой системы. Документ входит в состав технической документации на систему и, как правило, подготавливается техническим писателем.
Большинство руководств пользователя помимо текстовых описаний содержит изображения. В случае программного обеспечения, в руководство обычно включаются снимки экрана.
Типичное руководство пользователя содержит:
- Аннотацию, в которой приводится краткое изложение содержимого документа и его назначение
- Введение, содержащее ссылки на связанные документы и информацию о том, как лучше всего использовать данное руководство
- Страницу содержания
- Главы, описывающие, как использовать, по крайней мере, наиболее важные функции системы
- Глава, описывающая возможные проблемы и пути их решения
- Часто задаваемые вопросы и ответы на них
- Где ещё найти информацию по предмету, контактная информация
- Глоссарий и, в больших документах, предметный указатель
Руководство пользователя разрабатывается на основе стандарта РД 50-34.698-90 АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ. ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ДОКУМЕНТОВ.
Аналитическая часть
Созданное и протестированное ПО предполагает использование для решения практических задач. В аналитической части работы необходимо спланировать и провести вычислительный эксперимент для различных начальных данных этих задач. После проведения эксперимента необходимо провести анализ решений и характеристик разработанного ПО. Желательно сравнить полученные результаты с результатами работы аналогичных систем.
Основными характеристиками для анализа является время работы программы и точность решения.
При планировании эксперимента необходимо учитывать те характеристики предметной области задачи, которые могут существенно повлиять на работу программы и полученные результаты. Например, для алгоритма Дейкстры в качестве предметной области можно взять транспортную задачу и в этом случае изменять количество вершин графа и его связность.
|
|
|
