Введение
1. О порядке роста числа сверхрастущих и инъективных векторов и некоторых особенностях сильного модульного умножения 13
1.1. Задача о рюкзаке 14
1.2. Подсчет инъективных и сверхрастущих векторов
1.2.1. Математические основы проведенных компьютерных экспериментов по подсчету инъективных и сверхрастущих векторов с заданными размерностью и максимальным элементом 16
1.2.2. Алгоритм подсчета возрастающих инъективных векторов 17
1.2.3. Результаты компьютерных экспериментов 21
1.3. Оценки для функций F\ (г, М) и F-2(г. М) 22
1.3.1. Оценка сверху для функции F\ (г, М) 22
1.3.2. Оценка снизу для функции Fi(г, М) 25
1.3.3. Результаты компьютерных экспериментов
1.4. Алгоритм перечисления всех сверхрастущих векторов заданной размерности с фиксированным максимальным элементом 32
1.5. Некоторые особенности сильного модульного умножения 33
1.6. О монотонности функции F\ (г, М) 39
1.7. Выводы 44
2. Модификация метода Лагариаса-Одлыжко решения Задачи о рюкзаке для случая Обобщенной Задачи о рюкзаке и случаев систем задач о рюкзаках 47
2.1. LLL-приведенпые базисы решетки 47
2.2. Алгоритм построения LLL-приведенного базиса решетки 51
2.3. Об оценке числа точек целочисленной решетки, попадающих в сферу малого радиуса в г-мерном пространстве 55
2.4. Метод Лагариаса-Одлыжко решения Задачи о рюкзаке 56
2.5. Метод решения Обобщенной Задачи о рюкзаке, основанный
на методе Лагариаса-Одлыжко 62
2.6. Метод решения систем обобщенных задач о рюкзаках 67
2.7. Метод решения систем задач о рюкзаках 70
2.8. Выводы 74
3. О некоторых свойствах образов трансформированных Задач. LLL-решатель 75
3.1. О верхней границе плотности инъективных векторов 76
3.1.1. О последовательности Штерна и результатах компьютерных экспериментов 76
3.1.2. О плотности инъективных векторов 79
3.2. Некоторые свойства образов трансформированных Задач 86
3.2.1. Задача о точном покрытии ос Задача о рюкзаке 87
3.2.2. Задача о раскрашиваемое ос Задача о рюкзаке 93
3.2.3. Задача 3-ВЫП ос Задача о рюкзаке 95
3.2.4. О коротком сведении Задачи 3-ВЫП к Задаче о рюкзаке 97
3.3. LLL-решатель 101
3.3.1. Конструкция LLL-решателя 101
3.3.2. Результаты компьютерных экспериментов 102
3.4. Выводы 106
Заключение 107
Список использованной литературы
