Основы комбинаторики и теории чисел

Паспорт

• Где и когда. I–II семестры программы 01.03.02 «Прикладная математика и информатика», профиль «Математика», в плане набора 2025.
• Объём. 270 часов, 6 з.е.: по 135 часов и 3 з.е. в каждом семестре. Всего 120 аудиторных часов (60 лекций, 60 семинаров), 90 часов самостоятельной работы и 60 часов на подготовку к экзаменам.
• Кафедра. Кафедра дискретной математики.
• Преподаватель. В открытых вариантах программы указан поток, но не единый лектор для всех потоков ФПМИ; имя преподавателя нужно брать из расписания конкретного семестра.
• Итоговый контроль. Учебный план предусматривает аттестацию в обоих семестрах; точную форму для своей группы следует сверять с актуальным планом.

Содержание опубликованных программ

Ниже опубликованы полные списки тем общего курса кафедры: осень 2022 года и весна 2023 года. Это наиболее подробные доступные документы, но не обещание идентичности программы набора 2025.

I семестр: осенняя программа 2022

1. Множества, подмножества, операции, кортежи и декартово произведение.
2. Отображения, образы и прообразы, композиция, обратное отображение и декартова степень множества.
3. Равномощность, теорема Кантора—Бернштейна, счётные и несчётные множества, теорема Кантора.
4. Бинарные отношения, эквивалентность, частичный и линейный порядок, экстремальные элементы.
5. Операции, свойства и изоморфизмы упорядоченных множеств.
6. Предпорядки, полные предпорядки, квазитранзитивность, ацикличность и решётки.
7. Правила сложения и умножения, принцип Дирихле, двухцветная раскраска и задача о попарно неортогональных \((-1,0,1)\)-векторах.
8. Размещения, перестановки, сочетания с повторениями и без них; биномиальная и полиномиальная формулы, тождества и суммы степеней.
9. Формула включений и исключений и знакопеременные тождества.
10. Простые числа, бесконечность множества простых и основная теорема арифметики.
11. Суммы по делителям и функция Мёбиуса.
12. Формула обращения Мёбиуса.
13. Подсчёт циклических последовательностей с помощью обращения Мёбиуса.
14. Общее обращение Мёбиуса для частично упорядоченных множеств.
15. Линейные рекуррентные соотношения с постоянными коэффициентами.
16. Разбиения чисел, диаграммы Юнга, теоремы Эйлера, формула Харди—Рамануджана.
17. Формальные степенные ряды и производящие функции; Фибоначчи, Каталан и извлечение корней из рядов.
18. Теория сравнений и системы вычетов.
19. Биномиальные коэффициенты по модулю.
20. Теорема Шевалле.
21. Проблема Эрдёша—Гинзбурга—Зива.

II семестр: весенняя программа 2023

1. Алгоритм Евклида, основная теорема арифметики и лемма Евклида.
2. Сравнения, системы вычетов, теоремы Эйлера и Ферма.
3. Линейные сравнения, китайская теорема об остатках и функция Эйлера.
4. Число корней многочлена по простому модулю и теорема Вильсона.
5. Квадратичные сравнения, вычеты и невычеты.
6. Символ Лежандра и квадратичный закон взаимности.
7. Матрицы Адамара, их конструкции и гипотеза Адамара.
8. Двоичные коды, расстояние Хэмминга, границы Хэмминга и Плоткина, коды из матриц Адамара.
9. Задачи о раскрасках в терминах уклонения и матрицы Адамара.
10. Распределение простых: функции \(\pi(x)\), \(\theta(x)\), \(\psi(x)\) и теорема Чебышёва.
11. Асимптотический закон распределения простых и промежутки между соседними простыми.
12. Первообразные корни, индексы и алгоритмические задачи дискретного логарифмирования.
13. Теорема Дирихле о диофантовых приближениях и теорема Минковского.
14. Конечные цепные дроби и подходящие дроби.
15. Бесконечные цепные дроби, качество приближения и периодичность для квадратичных иррациональностей.
16. Алгебраические и трансцендентные числа, теорема Лиувилля и теорема Гельфонда.
17. Иррациональность и трансцендентность \(e\).
18. Решётки, определитель, многомерная теорема Минковского и теорема Минковского—Главки.
19. Равномерно распределённые последовательности по модулю 1.
20. Тригонометрические суммы, критерий Вейля, суммы Гаусса.
21. Алгоритм Агравала—Каяла—Саксены проверки простоты и его полиномиальность.

Литература, указанная кафедрой

Н. Я. Виленкин, Комбинаторика; Н. Б. Алфутова и А. В. Устинов, Алгебра и теория чисел (сборник задач); М. Холл, Комбинаторика; А. М. Райгородский, Линейно-алгебраический метод в комбинаторике и Задачи о раскрасках; А. И. Галочкин, Ю. В. Нестеренко, А. Б. Шидловский, Введение в теорию чисел; И. М. Виноградов, Основы теории чисел; К. Чандрасекхаран, Арифметические функции; Дж. В. Касселс, Введение в геометрию чисел; А. Я. Хинчин, Цепные дроби; А. А. Глибичук и др., Основы комбинаторики и теории чисел. Сборник задач; Л. Кейперс и Г. Нидеррейтер, Равномерные распределения последовательностей; M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P.

Оценивание

Открытой БРС или единого листа с порогами для этого курса кафедры дискретной математики не найдено.

Источники и актуальность

Страница осеннего варианта, вариант для программистов, программа весны 2023 и учебный план 01.03.02, набор 2025.