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



Скачать 52.07 Kb.
Дата09.06.2016
Размер52.07 Kb.
Вопросы к курсу

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

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

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

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

  4. Счётные и несчётные множества. Теорема Кантора.

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

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

  7. Плотно упорядоченные множества. Изоморфизм двух счётных плотных линейно упорядоченных множеств без наибольших и наименьших элементов.

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

  9. Размещения, перестановки и сочетания. Формулы для чисел размещения и сочетания с повторениями и без повторений. Бином Ньютона, полиномиальная формула.

  10. Простейшие комбинаторные тождества (6 штук). Формулы для сумм степеней натуральных чисел.

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

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

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

  14. Применение формулы обращения Мёбиуса для подсчета числа циклических последовательностей.

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

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

  17. Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные формулы. Количество всех упорядоченных разбиений на произвольные слагаемые.

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

  19. Формальные степенные ряды, операции над ними, деление в столбик. Пример тождества, доказываемого с помощью формальных степенных рядов.

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

  21. Числа Каталана. Извлечение корней из степенных рядов.

  22. Формула для чисел Каталана : д-во через производящие функции и комбинаторное док-во.

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

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

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

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

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

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

  29. Проблема Эрдеша – Гинзбурга – Зива. «Почти решение» проблемы при d=2 и n=p: нижняя оценка, формулировка верхней оценки и доказательство основной леммы с помощью теоремы Шевалле.

  30. Проблема Эрдеша – Гинзбурга – Зива. «Почти решение» проблемы при d=2 и n=p: нижняя оценка, формулировка основной леммы и доказательство верхней оценки.

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

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

  33. Сравнения второй степени. Квадратичные вычеты и невычеты. Теорема о том, что если m – произведение степеней простых и a – квадратичный вычет по модулю каждой из этих степеней, то a – квадратичный вычет по модулю m.

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

  35. Символы Лежандра. Квадратичный закон взаимности.

  36. Показатели. Первообразные корни. Существование по модулю 2, 4, p. Несуществование по другим модулям.

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

  38. Показатели. Первообразные корни. Индексы и системы индексов. Несколько слов об алгоритмических проблемах дискретного логарифмирования.

  39. Распределение простых чисел в натуральном ряде. Функции \pi(x), \theta(x), \psi(x). Теорема о равенстве нижних и верхних пределов. Асимптотический закон распределения простых (б/д). «Дырки» между соседними простыми числами (б/д).

  40. Распределение простых чисел в натуральном ряде. Теорема Чебышёва. Асимптотический закон распределения простых (б/д). «Дырки» между соседними простыми числами (б/д).

  41. Теорема Дирихле о диофантовых приближениях: общий случай; случай рациональных чисел; случай иррациональных чисел.

  42. Двумерная теорема Минковского. Ее уточнение для замкнутых множеств (б/д). Применение теоремы Минковского для передоказательства теоремы Дирихле.

  43. Конечные цепные дроби. Каноническая запись. Подходящие дроби. Рекуррентные соотношения для числителей и знаменателей подходящих дробей. Следствия: несократимость подходящих дробей, возрастание подходящих дробей с четными номерами и убывание подходящих дробей с нечетными номерами.

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

  45. Бесконечные цепные дроби. Процедура разложения данного числа в цепную дробь. Теорема о периодичности дроби для квадратичной иррациональности (доказательство в одну сторону). Проблема для кубических иррациональностей.

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

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

  48. Решетки в пространствах. Базис и определитель. Многомерная теорема Минковского (для произвольной решетки). Критический определитель.

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

Литература:

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

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

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

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

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

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

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

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

Каталог: upload
upload -> Предоставление максимально широкого поля возможностей учащимся, ориентированным на высокий уровень образования и воспитания, с учетом их индивидуальных потребностей
upload -> Методические рекомендации по организации исследовательской и проектной деятельности младших школьников
upload -> «Организация исследовательской деятельности в процессе обучения биологии»
upload -> Государственный образовательный
upload -> Одобрено на заседании каф. Философии и гуманитарных дисциплин Пушкина Н. М
upload -> Сборник тезисов докладов и методических материалов круглого стола психологов (11-12 ноября 2015 года) Екатеринбург 2015
upload -> Название кафедры
upload -> Мультикультурное образование в сша, канаде и австралии
upload -> Департамент образования и молодежной политики


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


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

    Главная страница