спасибо за помощь!
Информация о работе
Подробнее о работе
Задача о сумме подмножеств
- 27 страниц
- 2013 год
- 792 просмотра
- 2 покупки
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
В теории сложности алгоритмов и криптографии выделяют несколько важнейших задач. Каждая из этих задач имеет свои особенности, совокупность всех таких задач называют задачами NP-класса. К данному классу задач также относится задача о сумме подмножеств.
Смысл данной задачи заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел, входящих в это подмножество, равнялась заданному числу.
Классическим примером данной задачи является задача о наборе необходимой суммы монетами (или купюрами) заданного номинала.
Также разновидностью данной задачи является задача о сумма подмножеств с повторяющимися элементами: Каждое a[i] может использоваться в сумме несколько раз, можно ли составить сумму K?
В информационных технологиях данная задача имеет немаловажное значение при обработках больших массивов данных (базы данных и банки данных).
В данном курсовом проекте будут рассмотрены основные алгоритмы нахождения решения задачи: простой алгоритм перебора, алгоритм Горовица-Сани, алгоритм с использованием динамического программирования, приближенный алгоритм. Будет проверена работоспособность алгоритмов с помощью примеров, а также проведен их сравнительный анализ.
Оглавление
Введение 5
1. Теоретическая часть 6
1.1 Постановка задачи 6
1.2 Алгоритмы решения 7
2. Практическая часть 9
2.1 Алгоритм перебора 9
2.2 Алгоритм динамического программирования 14
2.3 Приближенный алгоритм 18
2.4 Сравнение алгоритмов 25
Заключение 26
Список использованной литературы 27
Цель курсового проекта – изучить особенности задачи о сумме подмножеств, различные алгоритмы её решения. Объем – 27 с., 4 ил. 5 таблиц, 3 источника.
Ключевые слова
Сумма, множество, подмножество, алгоритм, Горовиц и Сани, динамическое программирование.
1. Скиена С. Алгоритмы. Руководство по разработке. - 2-е изд.: Пер. с англ. - СПб.: БХВ-Петербург, 2011. - 720 с.: ил.
2. Чеботарев С.В. Элементы теории множеств.: Учебно-методическое пособие. – Барнаул: Изд-во БГПУ, 2005. – 74 с.
3. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.; ИНФРА-М, Новосибирск: Изд-о НГТУ, 2002.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
