Программа курса «Основы комбинаторики и теории чисел»



Скачать 45.81 Kb.
Дата01.11.2016
Размер45.81 Kb.
ТипПрограмма курса
Программа курса

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

  1. Понятия множества и подмножества, простейшие операции над множествами. Упорядоченные пары и кортежи, декартово произведение.

  2. Отображения и соответствия. Понятия образа и прообраза. Свойства отображений. Композиция и обратное отображение. Возведение множества в степень.

  3. Сравнение мощностей и понятие равномощности. Теорема
    Кантора-Бернштейна. Счётные и несчётные множества. Теорема Кантора.

  4. Отношения на множествах. Свойства бинарных отношений. Отношения
    эквивалентности, теорема о классах эквивалентности. Отношения
    частичного и линейного порядка. Минимальные/максимальные и
    наименьшие/наибольшие элементы.

  5. Свойства упорядоченных множеств. Операции над упорядоченными множествами. Изоморфизмы упорядоченных множеств.

  6. Основные правила комбинаторики: правило сложения, правило умножения, принцип Дирихле. Теорема о раскраске множества в два цвета.

  7. Размещения, перестановки и сочетания. Формулы для чисел размещения и сочетания с повторениями и без повторений. Бином Ньютона, полиномиальная формула. Простейшие тождества (6 штук). Формулы для сумм степеней натуральных чисел.

  8. Формула включения и исключения. Знакопеременные тождества (2 штуки).

  9. Простые числа. Бесконечность множества простых. Основная теорема арифметики с доказательством.

  10. Суммы, распространенные на делители числа. Функция Мёбиуса.

  11. Формула обращения Мёбиуса.

  12. Применение формулы обращения Мёбиуса для подсчета числа циклических последовательностей. Циклические последовательности с фиксированным количеством символов каждого типа (обязательное упражнение).

  13. Общая формула обращения Мёбиуса для частично упорядоченных множеств (б/д). Суммы по делителям и формула включений и исключений как частные случаи.

  14. Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные формулы. Количество всех упорядоченных разбиений на произвольные слагаемые. Диаграммы Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений. Теорема о бесконечном произведении (б/д). Формула Харди – Рамануджана (б/д).

  15. Формальные степенные ряды, операции над ними, деление в столбик. Пример тождества, доказываемого с помощью формальных степенных рядов. Производящие функции. Теоремы о сходимости степенных рядов (б/д). Примеры, иллюстрирующие теоремы. Сходимость на границе интервала. Числа Фибоначчи и их производящая функция. Суммы чисел Фибоначчи, чисел сочетания и пр. Числа Каталана. Извлечение корней из степенных рядов. Формула для числа Каталана: д-во через производящие функции и комбинаторное д-во.

  16. Линейные рекуррентные соотношения с постоянными коэффициентами. Соотношения 1ого порядка, в том числе неоднородные. Соотношения 2ого порядка – с доказательством, соотношения большего порядка – только формулировка.

  17. Основы теории делимости: наибольший общий делитель, наименьшее общее кратное, алгоритм Евклида.

  18. Функция Эйлера. Формула с произведением по простым числам.

  19. Основы теории сравнений. Системы вычетов. Теоремы Эйлера и Ферма (Ферма с двумя доказательствами).

  20. Значения некоторых биномиальных коэффициентов по данному модулю.

  21. Теорема Шевалле.

  22. Проблема Эрдеша – Гинзбурга – Зива. Решение проблемы при d=1 и n=p (нижняя и верхняя оценки). «Почти решение» проблемы при d=2 и n=p (нижняя и верхняя оценки).

  23. Теорема Лагранжа о числе корней многочлена по простому модулю. Теорема Вильсона. Китайская теорема об остатках.

  24. Сравнения второй степени. Квадратичные вычеты и невычеты. Теорема о том, что если a – квадратичный вычет по простому
    нечётному модулю p, то a и квадратичный вычет по модулю p^k.
    Аналогичная теорема для двойки в качестве задачи (если a сравнимо с 1 по модулю 8, то a – квадратичный вычет по модулю 2^k). Теорема о том, что если m – произведение степеней простых и a – квадратичный вычет по модулю каждой из этих степеней, то a – квадратичный вычет по модулю m.

  25. Символы Лежандра. Определение, простейшие свойства, формула для (2/p). Квадратичный закон взаимности.

  26. Показатели. Первообразные корни. Существование по модулю 2, 4, p, p^a, 2p^a. Несуществование по другим модулям. Индексы и системы индексов. Несколько слов об алгоритмических проблемах дискретного логарифмирования.

  27. Распределение простых чисел в натуральном ряде. Функции \pi(x), \theta(x), \psi(x). Теорема о равенстве нижних и верхних пределов. Теорема Чебышёва.

  28. Асимптотический закон распределения простых (б/д). «Дырки» между соседними простыми числами (б/д).

  29. Теорема Дирихле о диофантовых приближениях: общий случай; случай рациональных чисел; случай иррациональных чисел. Двумерная теорема Минковского. Ее уточнение для замкнутых множеств (б/д). Применение теоремы Минковского для передоказательства теоремы Дирихле.

  30. Конечные цепные дроби. Каноническая запись. Подходящие дроби. Рекуррентные соотношения для числителей и знаменателей подходящих дробей. Следствия: несократимость подходящих дробей, возрастание подходящих дробей с четными номерами и убывание подходящих дробей с нечетными номерами. Бесконечные цепные дроби. Процедура разложения данного числа в цепную дробь. Теорема о сходимости полученной дроби к данному числу (б/д). Передоказательство теоремы Дирихле. Уточнение теоремы Дирихле (б/д). Зависимость качества аппроксимации от скорости роста неполных частных: существование чисел с заданным наперед качеством аппроксимации; золотое сечение как самое плохо приближаемое число (б/д). Теорема о периодичности дроби для квадратичной иррациональности (доказательство в одну сторону). Проблема для кубических иррациональностей.

  31. Понятие о спектре Лагранжа (последовательность констант, сходящаяся к 1/3). Гипотеза Коробова – Бахвалова – Зарембы.

  32. Алгебраические и трансцендентные числа. Существование трансцендентных чисел (из соображения мощности). Теорема Лиувилля (б/д). Конструкция трансцендентного числа с помощью цепной дроби и теоремы Лиувилля. Сводка результатов о трансцендентности: е, пи, е+пи, пи+е^{пи}, alpha^{beta} (теорема Гельфонда), вывод про e^{пи} из теоремы Гельфонда.

  33. Решетки в пространствах. Базис и определитель. Многомерная теорема Минковского (для произвольной решетки). Критический определитель. Теорема Минковского – Главки и история ее улучшений. Доказательство теоремы Минковского – Главки в случае многомерного октаэдра.

  34. (Для интересующихся) Детерминированный алгоритм проверки числа на простоту.

Литература:

  1. Н.Я. Виленкин. Комбинаторика. – М.: Наука, 1969.

  2. Н.Б. Алфутова, А.В. Устинов. Алгебра и теория чисел (сборник задач). – М.: МЦНМО, 2002.

  3. М. Холл. Комбинаторика. – М.: Мир, 1970.

  4. А.М. Райгородский. Линейно-алгебраический метод в комбинаторике. – М.: МЦНМО, 2007.

  5. А.И. Галочкин, Ю.В. Нестеренко, А.Б. Шидловский. Введение в теорию чисел. – Изд-во Московского Университета, 1995.

  6. И.М. Виноградов. Основы теории чисел. – Москва–Ижевск: НИЦ "Регулярная и хаотическая динамика", 2003.

  7. К. Чандрасекхаран. Арифметические функции. – М.: Наука, 1975.

  8. Дж.В. Касселс. Введение в геометрию чисел. – М.: Мир, 1965.

Каталог: materials
materials -> Вопрос Периодизация и хронология каменного века
materials -> Информация о морских и речных портах
materials -> Вопросы радиоэлектроники серия техника телевидения 2015 вып. 6 Аннотации
materials -> Мониторинг и оценка программ
materials -> Вопросы по курсу «Вакуумная электроника»
materials -> Программа государственного экзамена по направлению 220200 «Автоматизация и управление»
materials -> Информация о программе Забайкальский край
materials -> Географические представления сторон в процессе урегулирования этнополитических конфликтов в СНГ с. В. Рассказов
materials -> Всероссийская научно-практическая конференция «Международный опыт как ресурс повышения качества российского образования». Хотелось бы рассказать о секции №9, которая была посвящена
materials -> 2017 году – 689,2 млрд руб и в 2018 году – 738,1 млрд рублей. Среднегодовой темп роста за эти годы составит 1,5%. В 2016 году


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал