|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Формальная постановка задачиСтр 1 из 3Следующая ⇒
ЗАДАНИЕ ДЛЯ КУРСОВОГО ПРОЕКТА (2-3 КУРС) Задачи студента по курсовому проекту 1. Каждый студент получает свою общую задачу дискретной оптимизации (перечень задач и их словесные формулировки даны в приложении 5), для которой необходимо построить математическую модель. 2. Каждый студент получает индивидуальную задачу (с конкретными значениями исходных параметров), соответствующую общей задаче из п.1 (данные частных задач приведены в приложении 6). Для нее необходимо построить два допустимых решения. 3. Студент должен выбрать алгоритм решения задачи, обосновать его выбор и программно реализовать его с использованием ООП – должны быть представлены класс задачи (class Problem), класс решения (class Solution) и класс алгоритма (class Algorithm). Создать консольное приложение, которое должно находить по 2 локальных оптимума индивидуальных задач. 4. Студент должен подготовить текст курсового проекта (его детальная структура приведена в приложении 2). 5. Студент должен подготовить доклад и выступить с ним по курсовому проекту (3 минуты на выступление).
Работа каждого студента оценивается согласно методике оценки (указана в приложении 3).
Оглавление ПРИЛОЖЕНИЕ 1. Перечень задач и литература. 2 ПРИЛОЖЕНИЕ 2. Структура курсового проекта. 3 ПРИЛОЖЕНИЕ 3. Методика оценки курсового проекта. 4 ПРИЛОЖЕНИЕ 4. Титульный лист отчета по типовому проекту. 5 ПРИЛОЖЕНИЕ 5. Словесные формулировки задач. 6 ПРИЛОЖЕНИЕ 6. Данные частных задач. 8
ПРИЛОЖЕНИЕ 1. Перечень задач и литература 1. Найти в графе вершинное покрытие минимальной мощности. 2. Найти в графе независимое множество максимальной мощности. 3. Найти в графе доминирующее множество минимальной мощности. 4. Найти в графе максимальное паросочетание. 5. Найти в графе минимальное реберное покрытие. 6. Найти в графе простой путь максимальной длины. 7. Найти в полном взвешенном графе гамильтонов цикл минимальной длины. 8. Найти в графе двудольный подграф с максимальным числом вершин. 9. Найти в графе двудольный подграф с максимальным числом ребер. 10. Найти во взвешенном графе остов минимального веса. 11. Найти во взвешенном графе остов максимального веса. 12. Найти равномерное разбиение графа на 2 подграфа с минимальным сечением.
Рекомендуемая литература: 1. Асанов М.О., Баранов В.А., Расин В.В. Дискретная математика: Графы, Матроиды, Алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 288 с. 2. Емеличев В.А. и др. Лекции по теории графов М.: Наука, гл. ред. Физ.-мат. Лит., 1990.- 384с. 3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, .- 416с. 4. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. 5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985 6. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980.
ПРИЛОЖЕНИЕ 2. Структура курсового проекта Титульный лист (см. приложение 4) Содержание Введение 1. Отметить актуальность задачи с примерами её практического применения. 2. Привести обзор и классифицировать известные подходы к решению рассматриваемой задачи (точные/приближенные/эвристические, детерминированные/рандомизированные, конструктивные/итерационные). 3. Привести обоснование выбора конкретного алгоритма для решения задачи, обозначить его место в классификации. 4. Сформулировать цель курсового проекта и его задачи. Формальная постановка задачи 1. Описать исходные данные задачи. 2. Построить математическую модель задачи, для чего формализовать понятие " решения задачи" и привести ограничения задачи. 3. Сформулировать критерий задачи. 4. Отметить математическую сложность задачи. Алгоритм решения задачи 1. Детально описать выбранный алгоритм. 2. Представить реализацию алгоритма для выбранной задачи. Программная реализация и эксперимент 1. Представить программную реализацию алгоритма (в приложении) 2. Привести результаты эксперимента и сформулировать выводы. 3. Показать допустимость найденных решений привести значения критериев. Заключение 1. Указать что нужно было сделать в рамках курсового проекта. 2. Перечислить, что удалось сделать, что сделать не получилось и в чем причина неудачи. Литература должны быть перечислины 5-10 источников: методы решения задачи, доказательство NP-трудности, практические приложения задачи, программные средства. (ссылки указываются в тексте работы)
Приложение (код программы)
ПРИЛОЖЕНИЕ 3. Методика оценки курсового проекта Результатами курсового проекта являются: текст курсового проекта, код программы с реализацией алгоритма и доклад. По каждому результату определен перечень оценочных позиций. Каждая позиция оценивается по 3 бальной шкале: 0 – результат по этой позиции отсутствует, 1 – результат неполный и/или имеются ошибки, 2 – результат получен. По интегральному показателю рассчитывается оценка студента.
Перечень оцениваемых позиций по тексту курсового проекта 1. Раскрыта актуальность задачи с практическими примерами. 2. Приведён обзор и классификация подходов. 3. Обозначено место рассматриваемого алгоритма в классификации подходов. 4. Приведено обоснование выбора алгоритма 5. Сформулированы цель и задачи курсового проекта. 6. Описаны исходные данные задачи. 7. Построена математическая модель задачи и сформулирован критерий задачи. 8. Отмечена математическая сложность задачи. 9. Представлена реализация алгоритма для выбранной задачи. 10. Приведены результаты эксперимента и сформулированы выводы. 11. Приведена проверка полученных решений на допустимость. 12. В работе (в тексте) имеют место ссылки на источники по тематике курсового проекта.
ПРИЛОЖЕНИЕ 4. Титульный лист отчета по типовому проекту МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «Нижегородский государственный университет им. Н.И. Лобачевского» Институт информационных технологий, математики и механики Кафедра информатики и автоматизации научных исследований
Направление подготовки: «Прикладная информатика»
ОТЧЕТ ПО ТИПОВОМУ КУРСОВОМУ ПРОЕКТУ ТЕМА РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМА ……. ДЛЯ ЗАДАЧИ …
Выполнил: студент группы ____________ __________________________ __________________________ подпись Научный руководитель: __________________________ __________________________ подпись
Нижний Новгород ХХХХ(год) ПРИЛОЖЕНИЕ 5. Словесные формулировки задач Примем обозначения: · · Множество T – множество связных графов без циклов (деревьев) · w(e) – вес ребра e
ПРИЛОЖЕНИЕ 6. Данные частных задач Данные частных задач заданы при помощи матрицы смежности или матрицы весовых коэффициентов (в случае задачи коммивояжера и поиска островного дерева). Если ребро из вершины с номером i в вершину с номером j существует, то на пресечении строки с номером i со столбцом с номером j стоит 1, иначе 0. ЗАДАНИЕ ДЛЯ КУРСОВОГО ПРОЕКТА (2-3 КУРС) Задачи студента по курсовому проекту 1. Каждый студент получает свою общую задачу дискретной оптимизации (перечень задач и их словесные формулировки даны в приложении 5), для которой необходимо построить математическую модель. 2. Каждый студент получает индивидуальную задачу (с конкретными значениями исходных параметров), соответствующую общей задаче из п.1 (данные частных задач приведены в приложении 6). Для нее необходимо построить два допустимых решения. 3. Студент должен выбрать алгоритм решения задачи, обосновать его выбор и программно реализовать его с использованием ООП – должны быть представлены класс задачи (class Problem), класс решения (class Solution) и класс алгоритма (class Algorithm). Создать консольное приложение, которое должно находить по 2 локальных оптимума индивидуальных задач. 4. Студент должен подготовить текст курсового проекта (его детальная структура приведена в приложении 2). 5. Студент должен подготовить доклад и выступить с ним по курсовому проекту (3 минуты на выступление).
Работа каждого студента оценивается согласно методике оценки (указана в приложении 3).
Оглавление ПРИЛОЖЕНИЕ 1. Перечень задач и литература. 2 ПРИЛОЖЕНИЕ 2. Структура курсового проекта. 3 ПРИЛОЖЕНИЕ 3. Методика оценки курсового проекта. 4 ПРИЛОЖЕНИЕ 4. Титульный лист отчета по типовому проекту. 5 ПРИЛОЖЕНИЕ 5. Словесные формулировки задач. 6 ПРИЛОЖЕНИЕ 6. Данные частных задач. 8
ПРИЛОЖЕНИЕ 1. Перечень задач и литература 1. Найти в графе вершинное покрытие минимальной мощности. 2. Найти в графе независимое множество максимальной мощности. 3. Найти в графе доминирующее множество минимальной мощности. 4. Найти в графе максимальное паросочетание. 5. Найти в графе минимальное реберное покрытие. 6. Найти в графе простой путь максимальной длины. 7. Найти в полном взвешенном графе гамильтонов цикл минимальной длины. 8. Найти в графе двудольный подграф с максимальным числом вершин. 9. Найти в графе двудольный подграф с максимальным числом ребер. 10. Найти во взвешенном графе остов минимального веса. 11. Найти во взвешенном графе остов максимального веса. 12. Найти равномерное разбиение графа на 2 подграфа с минимальным сечением.
Рекомендуемая литература: 1. Асанов М.О., Баранов В.А., Расин В.В. Дискретная математика: Графы, Матроиды, Алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 288 с. 2. Емеличев В.А. и др. Лекции по теории графов М.: Наука, гл. ред. Физ.-мат. Лит., 1990.- 384с. 3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982, .- 416с. 4. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. 5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985 6. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980.
ПРИЛОЖЕНИЕ 2. Структура курсового проекта Титульный лист (см. приложение 4) Содержание Введение 1. Отметить актуальность задачи с примерами её практического применения. 2. Привести обзор и классифицировать известные подходы к решению рассматриваемой задачи (точные/приближенные/эвристические, детерминированные/рандомизированные, конструктивные/итерационные). 3. Привести обоснование выбора конкретного алгоритма для решения задачи, обозначить его место в классификации. 4. Сформулировать цель курсового проекта и его задачи. Формальная постановка задачи 1. Описать исходные данные задачи. 2. Построить математическую модель задачи, для чего формализовать понятие " решения задачи" и привести ограничения задачи. 3. Сформулировать критерий задачи. 4. Отметить математическую сложность задачи. Алгоритм решения задачи 1. Детально описать выбранный алгоритм. 2. Представить реализацию алгоритма для выбранной задачи. Популярное:
|
Последнее изменение этой страницы: 2016-06-05; Просмотров: 566; Нарушение авторского права страницы
ребро e инцидентно вершине v (ребро e проходит через вершину v ) или вершина v принадлежит ребру e.