Алгоритм решения задачи о рюкзаке, основанный на обходе дерева вариантов укладки
Аннотация
Задача о рюкзаке лежит в основе целого ряда асимметричных криптосистем, в частности одной из первых асимметричных криптосистем – криптосистемы Меркля–Хеллмана. Было доказано, что многие из этих систем являются нестойкими либо непригодны к применению на практике из-за больших объемов необходимых вычислений. Тем не менее в настоящий момент задача о рюкзаке – одна из актуальных задач в области криптографии. В статье впервые описывается алгоритм решения задачи о рюкзаке, основанный на методе обхода дерева укладки рюкзака.
Ключевые слова
задача о рюкзаке; алгоритм; дерево укладки
Литература
1. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Триумф, 2003. – 816 с.
2. Мурин Д. М. Компьютерно-аналитическое исследование задач рюкзачного типа как средство анализа и совершенствования систем защиты информации. АКД. Томск: НИТГУ, 2013. – 22 с.
3. Борзунов Г. И., Войнов А. Е., Сучкова Е. А. Выбор базового алгоритма для расчета минимального количества процессоров, обеспечивающего достижение заданного значения коэффициента ускорения // Безопасность информационных технологий. 2010. № 1. С. 45–46.
Ссылки
- На текущий момент ссылки отсутствуют.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.