Вопросы

Основы комбинаторики. Основные определения и понятия

Теория делимости

Теория сравнений

Тема 1. Элементы комбинаторики. разбиения множеств и чисел, размещения и сочетания, перестановки, Перебор элементов прямого произведения множеств. Примеры комбинаторных задач, анализ способов их решения. Разбиения множеств и чисел, размещения и сочетания, перестановки, Декартовы произведения множеств, способы перебора. Биномиальные коэффициенты, переборные задачи с использованием бинома Ньютона. Задачи на разбиения. Решение комбинаторных задач методом математической индукции.

Тема 2. биномиальные коэффициенты, Бином Ньютона Коды Грея алгоритмы генерации комбинаторных объектов. Решения комбинаторных задач с использованием биномиальных коэффициентов, бинома Ньютона и кодов Грея. Разработка алгоритмов генерации комбинаторных объектов. Оценка сложности таких алгоритмов. Разработка частотных методов приближенного решения ряда комбинаторных задач, разработка алгоритмов решения такого рода задач. .

Тема 3. Комбинаторные задачи с ограничениями Ограничения на Порядок выбора Задачи о смещениях. Решение методом включения-исключения Смещение пар. Задачи с ограничениями, с ограничениями на порядок выбора. Классификация таких ограничений, разработка алгоритмов их решения. Верхние оценки сложности этих алгоритмов. Комбинаторные задачи, допускающие решение методами ветвей и границ, алгоритмы их решения, верхняя оценка сложности этих алгоритмов.

Тема 4. Генеральная совокупность без повторений и выборки без повторений. Примеры задач на смещение пар. Задачи на смещение пар, допускающие решение методами ветвей и границ, алгоритмы их решения, верхняя оценка сложности этих алгоритмов. Решения задач на смещения пар методами включения-исключения. Примеры транспортных задач, которые допускают применение метода смещения пар.

Тема 5. Применение графов (схем) при решении комбинаторных задач. Графы, ориентированные и неориентированные графы. Полные графы. Деревья. Теорема о существовании бесконечной ветви у бесконечных деревьев с конечным числом ветвлений. Комбинаторные задачи на графах. Теоремы о разбиениях. Теорема Харрингтона-Париса о разбиении. Связь с теоремами Геделя о неполноте.

Литература

1. Алфутова Н.Б., Устинов А.В. Алгебра и теория чисел. Сборник задач для математических школ.  М.: МЦНМО, 2002.  264 с.
2. Банникова Т.М., Баранова Н.А. Основы теории чисел: учебнометодическое пособие.  Ижевск, 2009.  95 с.
3. Бухштаб А.А. Теория чисел.  М.: Просвещение, 1966.  384 с.
4. Василенко О.Н., Галочкин А.И. Сборник задач по теории чисел.  М.: Изд-во Моск. ун-та, 1995.  128 с.
5. Виленкин Н.Я. Комбинаторика.  М.: Наука, 1969.  328 с.
6. Виноградов И.М. Основы теории чисел.  СПб-М.: Лань, 2004.  167 с.
7. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Наука, 1977.  80 с.
8. Кофман А. Введение в прикладную комбинаторику.  М.: Наука, 1975.  480 с.
9. Крупинин В.Г., Павлов А.Л., Попов Л.Г. Высшая математика. Теория вероятностей, математическая статистика, случайные процессы. Сборник задач с решениями: Учебное пособие.  М.: Издательский дом МЭИ, 2013.  386 с.
10.Кудреватов Г.А. Сборник задач по теории чисел.  М.: Просвещение, 1970.  128 с.
11.Ландо С.К. Лекции о производящих функциях.  М.: МЦНМО, 2004.  144 с.
12.Прасолов В.В. Задачи по алгебре, арифметике и анализу: Учебное пособие.  М.: МЦНМО, 2007. 608 с.
13.Серпинский В. О решении уравнений в целых числах.  М.: Изд-во физ.-мат. лит., 1961.  90 с.
14. Серпинский В. 250 задач по элементарной теории чисел.  М.: Просвещение, 1968.  160 с.