Содержание
Оглавление
Введение 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
Выдержка из текста
В теории сложности алгоритмов и криптографии выделяют несколько важнейших задач. Каждая из этих задач имеет свои особенности, совокупность всех таких задач называют задачами NP-класса. К данному классу задач также относится задача о сумме подмножеств.
Смысл данной задачи заключается в нахождении (хотя бы одного) непустого подмножества некоторого набора чисел, чтобы сумма чисел, входящих в это подмножество, равнялась заданному числу.
Классическим примером данной задачи является задача о наборе необходимой суммы монетами (или купюрами) заданного номинала.
Также разновидностью данной задачи является задача о сумма подмножеств с повторяющимися элементами: Каждое a[i] может использоваться в сумме несколько раз, можно ли составить сумму K?
В информационных технологиях данная задача имеет немаловажное значение при обработках больших массивов данных (базы данных и банки данных).
В данном курсовом проекте будут рассмотрены основные алгоритмы нахождения решения задачи: простой алгоритм перебора, алгоритм Горовица-Сани, алгоритм с использованием динамического программирования, приближенный алгоритм. Будет проверена работоспособность алгоритмов с помощью примеров, а также проведен их сравнительный анализ.
Список использованной литературы
1. Скиена С. Алгоритмы. Руководство по разработке. — 2-е изд.: Пер. с англ. — СПб.: БХВ-Петербург, 2011. — 720 с.: ил.
2. Чеботарев С.В. Элементы теории множеств.: Учебно-методическое пособие. – Барнаул: Изд-во БГПУ, 2005. – 74 с.
3. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.; ИНФРА-М, Новосибирск: Изд-о НГТУ, 2002.