У нас можно недорого заказать курсовую, контрольную, реферат или диплом

«Методы решения задачи о рюкзаке» - Курсовая работа
- 31 страниц(ы)
Содержание
Введение
Заключение
Список литературы
Примечания

Автор: navip
Содержание
Введение
Глава 1 Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи
1.1 Постановка задачи о рюкзаке
1.2 NP – полнота задачи
Глава 2 Методы решения задачи о рюкзаке
2.1 Классификация методов
2.2 Динамическое программирование
2.3 Полный перебор
2.4 Метод ветвей и границ
2.5 Жадный алгоритм
2.6 Сравнительный анализ методов
2.7 Модификации задачи
Заключение
Литература
Введение
Задача о загрузке (задача о рюкзаке) и различные её модификации широко применяются на практике в прикладной математике, криптографии, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: самолетов, кораблей, железнодорожных вагонов и т.д.
Рассматриваемая нами задача является NP – полной, то есть для нее не существует полиномиального алгоритма , решающего её за разумное время, в этом и есть проблема. Либо мы выбираем быстрый алгоритм, но он как известно не всегда решает задачу наилучшим образом, либо выбираем точный, который опять же не является работоспособным для больших значений. Существует несколько модификаций задачи.
1. Каждый предмет можно брать только один раз.
2. Каждый предмет можно брать сколько угодно раз.
3. Каждый предмет можно брать определенное количество раз
4. На размер рюкзака имеется несколько ограничений.
5. Некоторые вещи имею больший приоритет, чем другие
Цель данной работы – выделить основные методы решения задачи о загрузке, классифицировать и сравнить эти методы.
Реализовать алгоритмы решения классической задачи о рюкзаке. Протестировать их и разбить их на две группы: точные и приближенные, сравнить по скорости решения, по точности. Определить в каких случаях следует использовать тот или иной подход к решению задачи.
Алгоритмы решения можно разделить на два типа: точные и приближенные. Точные: применение динамического программирования, полный перебор, метод ветвей и границ (сокращение полного перебора). Приближенные алгоритмы: Жадный алгоритм.
Заключение
В ходе исследования задачи о рюкзаке были выявлены три основных алгоритма решения. Полный перебор, ДП – программирование, жадный алгоритм. Так же был рассмотрен Метод ветвей и границ, но как сокращение полного перебора. Все методы разделены на две группы. Первая группа – точные методы, сюда входят ДП – алгоритмы, Полный перебор и Метод ветвей и границ. Вторая группа – приближенные методы, к таким методам относится Жадный алгоритм. Выбор использования того или иного метода спорный вопрос, все зависит от постановки задачи, а так же от того, какие цели поставлены. Если требуется найти точное решение, то конечно нужно использовать точные методы, при небольшом наборе входных данных (предметов до 10-20), подойдет перебор или метод ветвей и границ в силу простоты реализации, при больших, следует использовать ДП – алгоритм. Если же точность решения не так важна, или входные данные таковы, что ни один из точных методов не работоспособен, остается применять только приближенные алгоритмы. Но остается возможность комбинирования различных методов для ускорения, или даже применение каких либо “уловок” для конкретного примера. Надеяться же на построение полиномиального алгоритма нет смысла, так как данная задача NP-полна. Безусловно, данная задача очень важна с точки зрения ее приложения в реальной жизни. Не смотря на свою “древность”, рюкзак не только не забывается, наоборот, интерес к нему задаче растет. Оптимальная загрузка транспорта помогает сокращать расходы, получать большую прибыль. Также задача применяется в криптографии и прикладной математике.
Список литературы
1. Вирт, Н. Алгоритмы и структуры данных [Текст] / Н. Вирт. – Пер. с англ.-М.Мир, 1989.-360 с., ил.
2. Визгунов, Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. – Н.Новгород.: ННГУ, 2006. – 48 с.
3. Кузюрин, Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. – 2005. – 79 с.
4. Гери, М. Вычислительные машины и труднорешаемые задачи [Текст] / М. Гери, Д. Джонсон. – М.: Мир, 1982 – 416 с.
5. Окулов, С. М - Программирование в алгоритмах [Текст] / С.М. Окулов. – М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.: ил.
6. Окулов, С.М. Информатика в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. – Киров: Изд-во ВГПУ, 1998. — 343с.
7. Царев, В.А. Проектирование, анализ и программная реализация структур данных и алгоритмов: Учебное пособие [Текст] / В.А. Царев, А.Ф. Дробанов. – Череповец., 2007. – 169 с.
8. Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов [Текст] / И.Л. Акулич. – М.: Высш. шк., 1986. – 319 с., ил.
9. Хаггари, Р. Дискретная математика для программистов [Текст] / Р. Хаггари. – М.: Техносфера, 2003. – 320с.
10. Кормен, Т. Алгоритмы: построение и анализ [Текст] / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с.
Примечания
К работе прилагается программа с исходным кодом.
Тема: | «Методы решения задачи о рюкзаке» | |
Раздел: | Информатика | |
Тип: | Курсовая работа | |
Страниц: | 31 | |
Цена: | 890 руб. |
Закажите авторскую работу по вашему заданию.
- Цены ниже рыночных
- Удобный личный кабинет
- Необходимый уровень антиплагиата
- Прямое общение с исполнителем вашей работы
- Бесплатные доработки и консультации
- Минимальные сроки выполнения
Мы уже помогли 24535 студентам
Средний балл наших работ
- 4.89 из 5
написания вашей работы
-
Курсовая работа:
37 страниц(ы)
Глава 1. Математическая формулировка
задачи о коммивояжере…. стр. 3
§1. Постановка вопроса…. стр. 3
§2. Некоторые примеры…. стр. 6§3. Необходимые сведения из теории графов…. стр. 14РазвернутьСвернуть
§4. Построение полного графа задачи о коммивоя-
жере на основе анализа графа коммуникаций…. стр. 17
Глава 2. Методы решения задачи о коммивояжере… стр. 19
§1. Эвристические методы и методы Монте-Карло. стр. 19
§2. Сведение задачи о коммивояжере к задачам це-
лочисленного линейного программирования … стр. 21
§3.Решение задачи о коммивояжере методами дина-
мического программирования…. стр. 25
§4.Метод ветвей и границ…. стр. 27
Заключение …. стр. 36
Литература …. стр. 37
-
Курсовая работа:
16 страниц(ы)
Введение 3
1 Аналитическая часть 5
1.1 Постановка задачи оптимизации 5
1.2 Построение математической модели оптимизационной задачи 61.3 Обоснование и описание вычислительной процедуры решения задачи 7РазвернутьСвернуть
1.4 Решение задачи оптимизации аналитически 7
2 Технологическая часть 13
Заключение 14
-
Дипломная работа:
Программный модуль для предоптимизационного анализа информации в задаче двумерного размещения
53 страниц(ы)
Введение 4
Глава 1. Обзор и анализ задач геометрического размещения и методов их решения 6
1.1 Многообразие задач геометрического размещения 61.2 Содержательная постановка задачи двумерного размещения 7РазвернутьСвернуть
1.3 Методы решения задач геометрического размещения 8
1.4 Оптимизационный процесс раскроя-упаковки 10
Выводы по 1 главе 13
Глава 2. Проектирование программного модуля для предоптимизационного анализа информации в задаче двумерного размещения 14
2.1 Процесс предоптимизационного анализа 14
2.2 Разработка программного модуля 18
2.3 Тестирование и анализ результатов генетических алгоритмов 24
2.3.2 Поиск лучших решений для разных классов задач 28
2.3.3 Поиск лучших решений для классов задач с большим количеством заготовок 32
Выводы по 2 главе 33
Глава 3. Разработка и тестирование программного модуля для предоптимизационного анализа информации в задаче двумерного размещения 34
3.1 Выбор языка программирования 34
3.2 Техническое задание 36
3.3 Тестирование программного модуля 38
3.4 Эффективность внедрения программного модуля предоптимизационного анализа информации в задаче двумерного размещения 40
3.4.1 Экономический эффект от внедрения программного модуля 40
3.4.2 Время разработки программы 42
Выводы по 3 главе 44
Заключение 45
Список литературы 46
Приложение 48 -
Дипломная работа:
Приложения координатно-векторного метода к решению школьных задач
80 страниц(ы)
Введение….….3
Глава I. Координатный метод решение задач….5
§ 1.1. Ортонормированный репер на плоскости. Простейшие задачи в координатах….….6§ 1.2. Общее уравнение прямой. Уравнение окружности….12РазвернутьСвернуть
§ 1.3. Примеры решения задач координатным методом….….…19
Глава II. Векторный метод решения задач….….25
§ 2.1. Координаты вектора на плоскости….25
§ 2.2. Координаты вектора в пространстве….26
§ 2.3. Примеры решения задач векторным методом….31
Глава III. Координатно-векторный метод решения задач….42
§ 3.1. Нахождение угла между прямыми в пространстве….42
§ 3.2. Нахождение угла между плоскостями….….51
§ 3.3. Нахождение угла между прямой и плоскостью….57
§ 3.4. Нахождение расстояния от точки до плоскости….72
§ 3.5. Нахождение расстояния между скрещивающимися прямыми.….75
Заключение….….79
Литература….….….80
-
ВКР:
Управление учебной деятельностью обучаящихся по овладению методами решения геометрических задач
69 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ДЛЯ РЕШЕНИЯ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ В РАМКАХ ЕГЭ ПО МАТЕМАТИКЕ 5
1.1. Методы и приёмы обучения решению геометрических задач 51.2. Анализ и спецификация ЕГЭ по математике 12РазвернутьСвернуть
1.3. Методы решения задач на квадратной решетке и координатной плоскости 16
1.4. Теоретические основы для решения задач по планиметрии 21
1.5. Теоретические основы для решения задач по стереометрии 32
ГЛАВА 2. МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ПОДГОТОВКИ УЧАЩИХСЯ К РЕШЕНИЮ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ В РАМКАХ ЕГЭ ПО МАТЕМАТИКЕ ПРОФИЛЬНОГО УРОВНЯ 41
2.1 Анализ школьных учебников 41
2.2 Разработка элективного курса «Практикум решения задач по геометрии» 45
2.3 Апробация 59
Заключение 62
Список литературы 63
Приложение 1. Контрольно-измерительные материалы 67 -
Дипломная работа:
Программный модуль формирования маршрутов транспортных средств на базе эволюционного алгоритма
68 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА 1. ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ И МЕТОДЫ ИХ РЕШЕНИЯ 5
1.1 Обзор и анализ существующих задач маршрутизации 51.2 Методы решения задач маршрутизации 6РазвернутьСвернуть
1.3 Основные понятия эволюционного алгоритма 12
ГЛАВА 2. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО МОДУЛЯ 15
2.1 Постановка задачи маршрутизации 15
2.2 Применение операторов и процедур для эволюционного алгоритма 17
2.3 Проектирование программного модуля в программе BPwin 19
ГЛАВА 3. РАЗРАБОТКА ПРОГРАМНОГО МОДУЛЯ 23
3.1 Обзор и анализ существующих языков программирования 23
3.2 Техническое задание к программному модулю 26
3.3 Программная реализация разработанного эволюционного алгоритма 31
3.4 Вычислительный эксперимент 45
3.5 Анализ экономической эффективности 50
ЗАКЛЮЧЕНИЕ 66
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 67
Не нашли, что искали?
Воспользуйтесь поиском по базе из более чем 40000 работ
Следующая работа
Сравнение методов трапеций и прямоугольников (на Visual Basic)




-
Дипломная работа:
Электронный документооборот в библиотеке
67 страниц(ы)
ВВЕДЕНИЕ
ГЛАВА I Создание и внедрение систем электронного документооборота в Российской Федерации…
1.1. Этапы внедрения электронного документооборота в России.1.2. Нормативная база работы с электронными документами в Российской Федерации.РазвернутьСвернуть
ГЛАВА II Внедрение электронного документооборота в деятельность Национальной библиотеки им. А.З. Валиди РБ….
2.1.Значение электронного документооборота в организации работы библиотек….
2.2 История создания электронной библиотеки в Национальной библиотеке им. А.З. Валиди…
2.3 Характеристика современного программного обеспечения Национальной библиотеки им. А.З. Валиди РБ…
ГЛАВА III Пути внедрения системы электронного документооборота в библиотеках г. Уфы (на примере Муниципального бюджетного учреждения Центральная система детских библиотек им. Ш. А. Худайбердина ГО г. Уфа)…
3.1 Общая характеристика деятельности МБУ ЦСДБ им. Ш.А. Худайбердина ГО г. Уфы…
3.2. Нормативное регулирование работы библиотек с электрон-ным каталогом в Административном регламенте по предоставлению муниципальной услуги…
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
-
Дипломная работа:
83 страниц(ы)
ВВЕДЕНИЕ. 3
ГЛАВА 1. Педагогические основы формирования эстетической культуры детей младшего школьного возраста на основе занятий спортивными бальными танцами1.1. Особенности формирования эстетической культуры детей младшего школьного возраста как психолого-педагогическая проблема . 7РазвернутьСвернуть
1.2. Специфика спортивных бальных танцев как вида искусства. 22
Выводы по первой главе….…. 31
ГЛАВА 2. Экспериментальная работа по формированию эстетической культуры детей младшего школьного возраста на основе изучения спортивных бальных танцев
2. 1. Содержание, формы и методы формирования эстетической культуры младшего школьного возраста на занятиях спортивными бальными танцами …33
2. 2. Педагогический эксперимент и его результаты…. 40
Выводы по второй главе….…. 51
ЗАКЛЮЧЕНИЕ….…54
Список использованной литературы…. 57
Приложение….…. 65
-
Дипломная работа:
Перфекционизм и прокрастинация как личностные факторы депрессивных и тревожных состояний
128 страниц(ы)
ВВЕДЕНИЕ 3
ГЛАВА I. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИССЛЕДОВАНИЯ ЛИЧНОСТНЫХ ФАКТОРОВ ТРЕВОЖНЫХ И ДЕПРЕССИВНЫХ СОСТОЯНИЙ 91.1 Тревожные состояния и тревожные расстройства личности 9РазвернутьСвернуть
1.2 Депрессивные расстройства, их виды и особенности 16
1.3 Перфекционизм как личностная черта, теоретические модели и методики исследования 22
1.4 Феномен прокрастинации и его связь с аффективными состояниями личности 32
Выводы по первой главе 47
ГЛАВА II. ЭМПИРИЧЕСКОЕ ИССЛЕДОВАНИЕ ПЕРФЕКЦИОНИЗМА И ПРОКРАСТИНАЦИИ КАК ЛИЧНОСТНЫХ ФАКТОРОВ ДЕПРЕССИВНЫХ И ТРЕВОЖНЫХ СОСТОЯНИЙ 48
2.1. Организация и методы исследования 48
2.2. Анализ результатов исследования 52
2.3. Программа профилактики перфекционизма и прокрастинации у студентов 68
Выводы по второй главе 71
ЗАКЛЮЧЕНИЕ 73
СПИСОК ЛИТЕРАТУРЫ 75
ПРИЛОЖЕНИЕ 83
-
Дипломная работа:
Методика исследования параболического уравнения второго порядка
22 страниц(ы)
Введение 3
1. Вспомогательные утверждения 6
2. Доказательство теоремы 1 14
3. Оценки характеристик N (r) и p∗ 20
Список литературы 22
-
Дипломная работа:
Место флейтового искусства в казахской традиционной музыкальной культуре
78 страниц(ы)
ВВЕДЕНИЕ ….
ГЛАВА I. Место флейтового искусства в казахской традиционной культуре….
1.1. Функциональные характеристики флейты ….1.2. Распространенные регионы флейты…РазвернутьСвернуть
ГЛАВА II. Великие исполнители великого искусства …
2.1.Устройство и возникновение Сыбызғы флейты. …
2.2.Апликатура и приемы звукоизвлечения…
2.3. Сыбызғы флейта в практике оркестров и ансамблей …
ЗАКЛЮЧЕНИЕ…
ЛИТЕРАТУРА….
ПРИЛОЖЕНИЕ…
-
Дипломная работа:
Программный модуль для мониторинга и оценки типа мышления сотрудников государственных органов
76 страниц(ы)
Введение 3
Глава I. Анализ предметной области 6
1.1. Мышление - объект психологической диагностики 6
1.2. Типы мышления и способы его исследования 81.3. Классификационный анализ психодиагностических методик 11РазвернутьСвернуть
1.4. Анализ тестовых технологий 15
1.5. Психологические аспекты профессиональной деятельности государственных служащих 17
1.6. Государственный служащий - субъект профессиональной деятельности 19
1.7. Описание используемой диагностической методики 23
Выводы по первой главе 27
Глава II. Процесс проектирования программного модуля 30
2.1. Основные подходы к моделированию программного модуля для мониторинга и оценки типа мышления сотрудников государственных органов 30
2.2. Структурный подход моделирования программного модуля 35
2.3. Объектный подход моделирования программного модуля 41
Выводы по второй главе 43
Глава III. Реализация и аппробация программного модуля 46
3.1. Техническое задание на разработку программного модуля 46
3.2. Алгоритм реализации программного модуля 49
3.3. Апробация программного модуля 60
Выводы по третьей главе 61
Заключение 63
Список литературы 67
Приложение 72
-
Контрольная работа:
32 страниц(ы)
Элементы векторной алгебры и аналитической геометрии
Элементы линейной алгебры
Введение в математический анализПроизводная и её приложенияРазвернутьСвернуть
Приложения дифференциального исчисления
Дифференциальное исчисление функций нескольких переменных
Неопределённый и определённый интегралы
Теория вероятностей и математическая статистика
-
Дипломная работа:
Развитие мотивации младших школьников к изучению иностранного языка
75 страниц(ы)
ВВЕДЕНИЕ….… .3
Глава 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАЗВИТИЯ МОТИВАЦИИ МЛАДШИХ ШКОЛЬНИКОВ К ИЗУЧЕНИЮ ИНОСТРАННОГО ЯЗЫКА1.1. Мотивация учебной деятельности: сущность, типы….….….….9РазвернутьСвернуть
1.2.Педагогические условия формирования мотивации учения….28
Выводы по главе 1….….48
Глава 2. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ РАБОТА ПО РАЗВИТИЮ МОТИВАЦИИ МЛАДШИХ ШКОЛЬНИКОВ К ИЗУЧЕНИЮ ИНОСТРАННОГО ЯЗЫКА
2.1. Диагностика учебной мотивации младших школьников к изучению английского языка….….51
2.2. Система работы по развития мотивации к изучению иностранного языка в начальной школе ….54
2.3. Анализ результатов опытно-экспериментальной работы … 61
Выводы по главе 2….… ….66
ЗАКЛЮЧЕНИЕ….…68
ЛИТЕРАТУРА….….70
Приложения
-
Дипломная работа:
71 страниц(ы)
ВВЕДЕНИЕ 4
ГЛАВА 1. ЛИТЕРАТУРНЫЙ ОБЗОР 6
1.1. Понятие экологического воспитания 6
1.2. Проблема экологического воспитания в современном мире 71.3. Формирование экологической культуры детей дошкольного возраста 12РазвернутьСвернуть
1.4. Формирование экологической культуры детей младшего школьного возраста 17
1.5. Формирование экологической культуры школьников 5-11 классов 21
ГЛАВА 2. МАТЕРИАЛЫ И МЕТОДЫ 24
2.1. Природно-климатические условия г. Мелеуз 24
2.1.1. Географическое месторасположение 24
2.1.2. Климатические условия 25
2.1.3. Почва 25
2.1.4. Экологические условия 26
2.2. Программа и методика исследования 28
2.2.1. Выбор и обоснование ландшафтного стиля реконструкции объекта 29
2.2.2. Составление генерального плана, разбивочной и посадочной схемы 29
2.3. Описание объекта исследования 31
2.3.1. Предпроектный анализ территории 32
2.3.2. Описание существующих насаждений 32
2.3.3. Дорожки, площадки 33
2.3.4. МАФ, архитектурные сооружения 34
2.3.5. Существующий баланс территории сквера 34
ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ 35
3.1. Поиск и обоснование основной концепции реконструкции парка 35
3.2. Функциональное зонирование территории. Поставленные задачи и их решение 36
3.3. Проектирование дорожно-тропиночной сети 36
3.4. Посадка деревьев и кустарников 37
3.4.1. Планируемые мероприятия по уходу за существующими и проектируемыми насаждениями 37
3.4.2. Проектирование ландшафтных групп 38
3.5. Проектирование цветников 38
3.6. Реконструкция травяного покрова 38
3.7. Безопасность и экологичность проекта 39
3.7.1. Мероприятия по охране окружающей среды 39
3.7.2. Мероприятия по защите населения и материальных ценностей в чрезвычайных ситуациях 41
ГЛАВА 4. МЕТОДИКА ФОРМИРОВАНИЯ ЭКОЛОГИЧЕСКОЙ КУЛЬТУРЫ СРЕДСТВАМИ ЛАНДШАФТНОЙ АРХИТЕКТУРЫ 46
4.1. Разработка плана внеурочных занятий с интерактивным методом 49
4.1.1. Разработка плана внеурочного занятия № 1 49
4.1.2. Разработка плана внеурочного занятия № 2 53
4.1.3. Разработка плана внеурочного занятия № 3 59
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
-
Реферат:
Открытия Луи Пастера и Роберта Коха и их значение в развитии медицины
23 страниц(ы)
Введение….…3
Биография Луи Пастера….4
Работы в области химии….5
Брожение по Пастеру….6
Изучение инфекционных заболеваний … ….7Биография Роберта Коха ….…10РазвернутьСвернуть
Основные достижения и научные труды….11
Заключение….19
Приложение…21
Список используемой литературы…23