 |
решения комбинаторных задач
|
|
|
|
Введение
Настоящее техническое задание распространяется на разработку системы решения комбинаторно-оптимизационных задач, предназначенной для ввода и хранения данных указанных задач, а также для их решения, хранения полученных результатов и использования разработчиками программных и аппаратных средств вычислительной техники.
Широкий круг задач проектирования различного рода технических объектов, в том числе компьютеров, относится к классу комбинаторно-оптимизационных задач, точные методы решения которых, как правило, имеют экспоненциальную вычислительную сложность и нереализуемы даже на современных компьютерах. В настоящее время для решения таких задач широко используются приближенные методы и алгоритмы, требующие различных вычислительных ресурсов и дающие неодинаковую точность решения.
При этом данные методы и алгоритмы не систематизированы, оценки их вычислительной и емкостной сложности и сведения о возможной точности получаемых решений не полны и разбросаны по многим источникам. В рамках единой системы не существует программной реализации даже для ограниченного круга алгоритмов решения основных комбинаторно-оптимизационных задач проектирования.
Создание системы, в рамках которой были бы реализованы наиболее часто упоминаемые методы и алгоритмы решения указанных задач, позволит как оценивать и исследовать отдельные методы и алгоритмы, так и сравнивать их с точки зрения затрат вычислительных ресурсов и точности получаемых решений.
1. Основание для разработки
Система разрабатывается на основании приказа заместителя директора по учебной работе... №... от.... и в соответствии с учебным планом на 20___ — 20___ г.
|
|
|
2. Назначение разработки
Система призвана решить небольшой круг комбинаторно-оптимизационных задач на графах:
поиск цикла минимальной длины (задача коммивояжера);
поиск кратчайшего пути;
поиск минимального связывающего дерева.
Пользователями могут выступать научные работники и инженеры, занимающиеся проектированием компьютеров, студенты соответствующих специальностей, а также специалисты других предметных областей, которым приходится решать подобные задачи.
3. Требования к программе или программному изделию
3.1. Требования к функциональным характеристикам
Система должна представлять совокупность методических и программных средств решения следующих задач:
■ построение минимального покрывающего дерева;
■ поиск покрывающего цикла минимальной длины (задача коммивояжера);
■ поиск кратчайшего пути.
Для этих задач должны быть реализованы:
■ алгоритм, обеспечивающий получение точного решения;
■ в случае если точное решение дает алгоритм, имеющий не полиномиальную вычислительную сложность, то необходимо дополнительно разработать алгоритм, обеспечивающий получение приближенных решений с полиномиальной вычислительной сложностью.
Методическое обеспечение должно быть реализовано в пользовательском интерфейсе системы, который должен предполагать:
■ выбор задачи, метода и алгоритма ее решения;
■ ввод данных;
■ решение проектной задачи и сохранение исходных данных, промежуточных и окончательных результатов во встроенной базе данных для последующего анализа.
3.2. Требования к надежности
Программный продукт должен соответствовать современному уровню требований к надежности программного обеспечения:
■ предусматривать контроль вводимой информации и блокировку некорректных действий пользователя при работе с системой;
■ обеспечивать корректное завершение вычислений с соответствующей диагностикой при превышении имеющихся вычислительных ресурсов;
|
|
|
■ обеспечивать целостность информации, хранящейся в базе данных.
3.3. Требования к составу и параметрам технических средств
Системные требования для работы программного продукта должны быть следующими: тактовая частота процессора ~ 1 000 Гц; объем оперативной памяти 64 Мб; объем свободного дискового пространства 20 Мб; разрешение монитора 1024x768; наличие устройства чтения компакт-дисков; принтер.
3.4. Требования к информационной и программной совместимости
Программа должна работать в операционных системах Windows 2000/XP.
4. Требования к программной документации
Разрабатываемая система должна включать справочную информацию о работе системы и подсказки пользователю. В состав сопровождающей документации должны входить: расчетно-пояснительная записка, содержащая описание системы; руководство пользователя; руководство системного программиста.
5. Этапы разработки (табл. 1.1)
Таблица 1.1
Этапы разработки
| Номер этапа | Название этапа | Срок | Отчетность |
| Разработка ядра системы | 01.01.2011-31.03.2011 | Описание внутренних форматов, интерфейса и форматов данных базы. Реализация системы на уровне интерфейса | |
| Разработка методов и алгоритмов и их реализация для задачи коммивояжера | 01.04.2011-30.06.2011 | Описание методов и алгоритмов. Программные модули, реализующие методы. | |
| Разработка методов и алгоритмов и их реализация для задачи построения минимального связывающего дерева и задачи поиска кратчайшего пути в графе | 01.07.2011-30.09.2011 | Описание методов и алгоритмов. Программные модули, реализующие методы. | |
| Тестирование программного продукта и составление программной документации | 01.10.2011-31.12.2011 | Тесты. Документация. Программный продукт. |
После утверждения технического задания организация-разработчик непосредственно приступает к созданию программного обеспечения.
Задание
Разработать документ «Техническое задание» на программный продукт в соответствии с одним из вариантов, представленных в приложении. Оформить работу в соответствии с ГОСТ 19.106—78.
Варианты заданий для выполнения на практических занятиях
|
|
|
1.Разработать программное обеспечение автоматизированной информационной системы «Книжный магазин». База данных должна содержать сведения о поступлении книг, включая дату поступления, номер документа и сведения о поставщике; сведения о книгах — жанр, название, автор(ы), год издания, издательство, место издания, количество страниц, цена; сведения о реализации книг (дата продажи, количество экземпляров, сумма). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
2.Разработать программу для построения графика функции, заданной параметрическим уравнением. При выполнении этого проекта предполагается развитый интерфейс, позволяющий изменять масштаб, менять цвета фона и линий. Предусмотреть возможность вывода координат курсора мыши и параметра t при нажатии на правую кнопку.
3.Разработать программное обеспечение автоматизированной информационной системы «Студенческая библиотека». База данных должна содержать сведения о книгах — жанр, название, инвентарный номер, автор(ы), год издания, издательство, место издания, количество страниц, цена; сведения о выдаче и возврате книг студентам (формуляр); данные о списании книг. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
4.Разработать программное обеспечение автоматизированной информационной системы «Городская библиотека». База данных должна содержать сведения о книгах — жанр, название, инвентарный номер, автор(ы), год издания, издательство, место издания, количество страниц, цена; сведения о выдаче и возврате книг читателям (формуляр); сведения о читателях (ФИО, адрес, паспортные данные). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
5.Разработать простейший графический редактор, обладающий функциональными возможностями редактора Paint.
6.Разработать программное обеспечение автоматизированной информационной системы «Школьная библиотека». База данных должна содержать сведения о поступлении книг, включая дату поступления и поставщиков, номер документа; сведения о книгах — жанр, название, инвентарный номер, автор(ы), год издания, издательство, место издания, количество страниц, цена; сведения о выдаче и возврате книг учащимся (формуляр); данные о списании книг. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
|
|
|
7.Разработать программное обеспечение автоматизированной информационной системы «Отдел кадров предприятия». База данных должна содержать сведения о работниках предприятия, включая ФИО, пол, дату рождения, образование, должность, профессию, подразделение, дату поступления на работу, оклад, паспортные данные, адрес. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
8.Разработать программное обеспечение автоматизированной информационной системы «Студенческий отдел кадров». База данных должна содержать сведения о студентах техникума, включая ФИО, пол, дату рождения, адрес проживания, телефон, сведения о родителях, рабочие телефоны родителей, курс, группу, специальность, отделение, вид финансирования, год поступления, год окончания, номер студенческого билета. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
9.Разработать программное обеспечение автоматизированной информационной системы «Магазин музыкальных инструментов». База данных должна содержать сведения о поступлении музыкальных инструментов в магазин (включая дату поступления, номер документа, сведения о поставщике, количество, сумму), сведения об инструментах (название, вид инструмента, цена); сведения о продажах музыкальных инструментов покупателям (дата продажи, количество, сумма). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
10.Разработать программное обеспечение автоматизированной информационной системы «Музыкальный салон». База данных должна содержать все сведения о кассетах и CD-дисках, поступающих для продажи. В ней должны быть данные о музыкальных произведениях (жанр, название, исполнитель, год выпуска), сведения о поступлении музыкальных кассет и дисков (включая дату поступления, номер документа, сведения о поставщике, количество поставляемых дисков (кассет), сумму поступления), а также сведения о продажах музыкальных дисков (дата продажи, количество проданных дисков, сумма продажи). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
|
|
|
11.Разработать программное обеспечение автоматизированной информационной системы «Склад оптовой торговли». База данных должна содержать сведения о поступлении товаров на склад (включая дату поступления, номер документа, сведения о поставщике, количество товара, сумму), сведения о товаре (название, вид товара, цена); сведения о продажах (дата продажи, количество проданного товара, сумма продажи, сведения о покупателе). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
12.Разработать программное обеспечение автоматизированной инормационной системы «Салон сотовой связи». База данных должна содержать сведения о сотовых телефонах и аксессуарах, имеющихся в салоне. Необходимо указывать модель телефона, фирму-производителя, цену, краткую характеристику, гарантийный срок использования. Нужно вводить сведения о поступлении телефонов и аксессуаров (включая дату поступления, номер документа, сведения о поставщике, количество поставляемого товара, сумму), а также сведения о продажах (дата продажи, количество проданного товара, сумму продажи). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
13.Разработать программу проектирования плана города. Необходимо поддерживать библиотеку условных обозначений и элементов. В проекте должны быть реализованы функции масштабирования, рисования и удаления элементов.
14.Разработать программное обеспечение автоматизированной информационной системы «Материальный склад». База данных должна содержать:
■ сведения о поступлении материалов на склад (включая дату поступления, номер документа, сведения о поставщике, количество материала, сумму);
■ сведения о материалах (название, вид материала, цена);
■ сведения о списании материалов (дата списания, номер документа, количество, сумма);
■ сведения о передачи материала в производство (дата передачи, номер документа, количество, сумма).
Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
15. Разработать программное обеспечение автоматизированной информационной системы «Учет и выдача спецодежды на предприятии». База данных должна содержать:
■ сведения о поступлении спецодежды на склад (включая дату поступления, номер документа, данные о поставщике, количество поставляемой спецодежды);
■ сведения о спецодежде (название, вид спецодежды (обувь, халат и т.д.), цена);
■ сведения о выдаче спецодежды сотрудникам — дата выдачи, данные о сотруднике, получившем спецодежду (ФИО, профессия, должность), срок использования спецодежды.
Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
16.Разработать программное обеспечение автоматизированной информационной системы «Учебная часть». База данных должна содержать все сведения, которые заносятся в зачетную книжку студента (номер группы, специальность, отделение, ФИО студента, семестры, дисциплины, дата сдачи экзамена или зачета, преподаватели, оценки). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
17. Разработать программное обеспечение автоматизированной информационной системы «Абитуриент». База данных должна содержать анкетные данные, которые указывает при подаче заявления поступающий. ФИО, дата рождения, гражданство, пол, домашний адрес, выбранная специальность, телефон, законченное образовательное учреждение и год его окончания, данные о родителях, дополнительные сведения (инвалид, сирота, нуждается в общежитии), изучаемый иностранный язык, средний балл аттестата. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
18.Разработать программное обеспечение автоматизированной информационной системы, предназначенной для контроля поступления оплаты за обучение студентов («Поступление оплаты»), В базе данных хранятся сведения о студентах (ФИО, группа, курс, специальность), сведения о родителях, сведения о поступлении денег в кассу (дата поступления и сумма). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
19.Разработать программу для администрирования локальной сети. Программа должна устанавливаться на компьютерах-клиентах и компьютере-сервере, с которого будет производиться опрос устройств компьютеров-клиентов. Пользователь на сервере может в любое время управлять компьютером-клиентом.
20.Разработать программное обеспечение автоматизированной тестовой системы, в которой хранятся название тестов, вопросы, иллюстрации к вопросам, варианты ответов, ограничение времени на ответ, номер правильного ответа, количество баллов за правильный ответ. Кроме того, должны сохраняться сведения о тестируемых студентах (ФИО, группа), дата тестирования и результаты тестирования (номер вопроса, номер выбранного ответа, верный или неверный был дан ответ), количество баллов, набранное студентом. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
21.Разработать программное обеспечение для ведения электронного классного журнала. В базе данных хранятся номер группы, списки студентов в каждой группе. По каждой дисциплине указываются дата заполнения журнала, преподаватель, тема дисциплины, заносятся оценки и отметки о пропуске занятия. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
22.Разработать программу для администрирования локальной сети. Программа должна устанавливаться на компьютерах-клиентах и компьютере-сервере, с которого будет производиться опрос устройств компьютеров-клиентов. Пользователь может в любое время получить список устройств и системного программного обеспечения, имеющихся на компьютерах в локальной сети.
23.Разработать программное обеспечение для автоматизированной информационной системы «Учебная группа». База данных должна содержать сведения о студентах одной студенческой группы техникума, включая ФИО, пол, дату рождения, адрес проживания, телефон, сведения о родителях, рабочие телефоны родителей, номер студенческого билета, а также сведения об успеваемости студентов (данные зачетной книжки). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
24.Разработать программное обеспечение автоматизированной информационной системы «Электронный каталог CD-дисков».
25.Разработать программное обеспечение автоматизированной информационной системы «Компьютерный салон». База данных должна содержать сведения о поступлении и реализации компьютеров и их комплектующих: дата поступления, номер документа, поставщик, тип комплектующего устройства, его модель и производитель. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
26.Разработать программу проектирования схем локальных вычислительных сетей (ЛВС). Проект должен поддерживать возможность создания плана отдельного этажа здания, создания и редактирования элементов ЛВС, инструментарий для расстановки этих элементов по плану здания.
27.Разработать программное обеспечение автоматизированной информационной системы учета компьютеров и комплектующих, имеющихся в учебном заведении. База данных должна содержать сведения о наличии и перемещении компьютеров и их комплектующих внутри учебного заведения: номер компьютера, место нахождения (номер кабинета и материально ответственное лицо), состав компьютера — перечень комплектующих устройств (тип комплектующего устройства, его модель и производитель). Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
28.Разработать программное обеспечение автоматизированной информационной системы «Городской телефонный справочник». База данных должна содержать фамилию имя и отчество абонента, домашний адрес и номер телефона. Должны учитываться городские поселки и села. Кроме того, в базе данных должны учитываться служебные телефоны (наименование предприятия, адрес, отдел, номер телефона).
29.Разработать программное обеспечение автоматизированной информационной системы «Банк данных жителей города». База данных должна содержать анкетные данные: ФИО, дата рождения, гражданство, пол, домашний адрес, место рождения, ИНН, страховой номер, телефон, семейное положение, дополнительные сведения (инвалид, сирота), место работы, номер избирательного участка. Создать экранные формы для ввода и редактирования данных в таблицах и все необходимые выходные отчеты.
30.Разработать программу, которая наглядно иллюстрирует работу методов сортировки: выборкой и вставкой.
Провести сравнение этих сортировок по количеству сравнений, по количеству обменов. Для этого нужно построить графики зависимостей данных величин от количества элементов массива.
31. Разработать программу, которая наглядно иллюстрирует работу методов сортировки: простой вставкой и бинарной вставкой.
Провести сравнение этих сортировок по количеству сравнений, по количеству обменов. Для этого нужно построить графики зависимостей данных величин от количества элементов массива.
32. Разработать программу, которая наглядно иллюстрирует работу методов сортировки: выборкой, простой вставкой и бинарной вставкой.
Провести сравнение этих сортировок по количеству сравнений, по количеству обменов. Для этого нужно построить графики зависимостей данных величин от количества элементов массива.
|
|
|
