Теория чисел. Общие вопросы

Настоящее пособие составлено на основе олимпиадных задач по математике преподавателями факультета ВМК МГУ имени М. В. Ломоносова. Пособие содержит теоретический материал, подборку задач, а также указания и решения к большинству задач.

В этой основательной и вместе с тем доступной книге авторы объясняют принципы обобщенного программирования и стоящее за ними понятие математической абстракции. Любой достаточно квалифицированный программист, умеющий логически мыслить, уже обладает достаточными знаниями для прочтения этой книги. Авторы на удивление доходчиво сообщают необходимые сведения из общей алгебры и теории чисел. Они объясняют, какие проблемы должны были разрешить математики, и показывают, как найденные ими решения переводятся на язык обобщенного программирования и позволяют создать эффективный и элегантный код. Читая эту книгу, вы освоите мыслительный процесс, необходимый для правильного программирования, и научитесь обобщать найденные для частного алгоритмы с целью расширить область их полезного применения без потери эффективности. Вы также постигнете, в чем состоит ценность математики для программирования, — и это понимание пригодится вне зависимости от того, на каком языке вы пишете и какую парадигму применяете.

Настоящее пособие составлено на основе олимпиадных задач по математике преподавателями факультета ВМК МГУ имени М.В. Ломоносова. Пособие содержит теоретический материал, подборку задач, а также указания и решения к большинству задач.

Настоящее пособие составлено преподавателями факультета ВМК МГУ имени М.В. Ломоносова на основе олимпиадных задач по математике. Пособие содержит теоретический материал, подборку задач, а также идеи, указания (подсказки) и решения.

Настоящее пособие составлено преподавателями факультета ВМК МГУ имени М.В. Ломоносова на основе олимпиадных задач по математике. Пособие содержит теоретический материал, подборку задач, а также идеи, указания (подсказки) и решения.

Рассматривается модель работы страховой компании в дискретном времени при наличии непропорционального договора перестрахования. Совокупные требования, ежегодно поступающие в компанию, образуют последовательность неотрицательных независимых одинаково распределенных случайных величин с конечным математическим ожиданием. Предполагается, что при падении капитала страховой компании ниже заданного уровня производятся дополнительные денежные вливания. Исследуется устойчивость оптимальных вливаний капитала к изменению в распределении страховых требований. Под оптимальными подразумеваются минимальные ожидаемые капиталовложения, которые находятся из соответствующего уравнения Беллмана

Найдена асимптотика числа решений системы трех диофантовых уравнений аддитивного типа при числе переменных, равном 6. Каждое аддитивное слагаемое в этих уравнениях представляет собой простейшую форму, степень которой по каждой переменной не превосходит 1

В работе получена теорема об одном выборе приближения числа элементов в конечной последовательности специального вида. Рассмотрена конечная последовательность значений неприводимого полинома от простого аргумента. Значения не обязательно различны. Они делятся на некоторое натуральное число, свободное от квадратов. Для последовательности выполнены условия, накладываемые в случае одномерного решета. Доказано, что существует мультипликативная функция, такая, что некоторая величина является достаточно точным приближением для числа элементов в последовательности. При этом остаточный член мал "в среднем" в смысле теоремы Бомбьери–Виноградова. Для оценки одной из возникающих сумм применяется результат А. И. Виноградова.

Дается описание орбит группы автоморфизмов конечно-порожденного модуля над кольцом главных идеалов в терминах канонических представителей и с помощью полной системы инвариантов. Для примарного модуля устанавливается естественная биекция между орбитами и разбиениями диаграммы Юнга, задающей модуль, в сумму двух диаграмм Юнга, что позволяет найти число орбит

Рассматривается конечная система A функций многозначной логики, принимающих значения 0 и 1, причем проекция системы A порождает класс всех монотонных булевых функций. Показано, что найдутся константы c и d, такие, что для любой функции f из [A] глубина D(f) и сложность L(f) функции f в классе формул над A связаны соотношением D(f) □ c log2 L(f)+d.

Рассматривается система M|GI|1|∞ с ненадежным прибором и временем обслуживания, зависящим от состояния системы. Находятся условие эргодичности системы и производящая функция для числа требований в системе в стационарном режиме.

В работе рассматриваются классы ограниченно детерминированных функций, в каждом состоянии которых реализуется функция из некоторого замкнутого класса Dk-значной логики (P-множества). Показано, что существует континуум предполных классов, содержащих произвольное P-множество. Также рассматривается задача о существовании критерия распознавания полноты систем, содержащих P-множества.

В работе формулируется гипотеза о квантовой пропускной способности для каналов с бесконечномерными входным и выходным пространствами. Дается доказательство обращения этой гипотезы, использующее определения и свойства когерентной информации для бесконечномерных каналов.

Рассматривается обобщение квадратично-вычетных кодов на случай вычетов высших степеней. Исследуются свойства h-вычетных кодов. В некоторых случаях указывается вид и способ построения порождающего многочлена. С помощью полученных результатов выписываются порождающие многочлены кодов с вычетами 5–8-й степени.

Предлагается развитие метода осреднения для решения физически нелинейных задач о равновесии слоистых пластин или пластин из функционально-градиентных материалов. Согласно методу осреднения, решением задачи является суперпозиция решения глобальной задачи во всей области и решения локальной задачи для представительной области, например ячейки периодичности. Для нелинейной задачи суперпозиция неверна, что осложняет применение метода в случае нелинейности. Выходом может служить процедура объединения метода осреднения и метода линеаризации при решении краевой (или вариационной) задачи. Определяющие соотношения в механике деформируемого твердого тела можно рассматривать как уравнения относительно скоростей или дифференциалов напряжений и деформаций по времени или параметру нагружения. В том случае, если они линейны относительно скоростей, можно применить процедуру метода осреднения. В статье такой подход демонстрируется на примере симметричной слоистой пластины, изгибающейся под воздействием равномерно распределенной нагрузки, изменяющейся во времени.

Доказывается существование такой метрики на канторовом множестве, что в него изометрически вкладываются все конечные метрические пространства, ограниченные по диаметру числом 1 и по количеству точек числом п. Также доказывается, что для любых т, п существует канторово множество в Rm, изометрически содержащее все конечные метрические пространства, которые вкладываются в Rm, ограничены по диаметру числом 1 и по количеству точек числом п. Последний результат доказывается для широкого класса метрик на Rm, в том числе для евклидовой метрики.

В работе получены верхние оценки полных рациональных тригонометрических сумм специального вида с простым знаменателем.

В статье рассматривается задача об устойчивости относительного равновесия системы на орбите. Система состоит из двух твердых тел, соединенных тонким нерастяжимым упругим стержнем. Задача об устойчивости установившихся движений сводится к задаче минимума измененной потенциальной энергии системы, состоящей из потенциальной энергии упругих, гравитационных и центробежных сил.

Задача представления натуральных чисел в виде сумм слагаемых определенного вида актуальна в теории чисел и ее приложениях. Интерес представляет среднее значение длины таких разложений и необходимое количество вспомогательных вычислений. В статье рассмотрены разложения с двойной базой, цепи с двойной базой, полиадическое (факториальное) разложение натуральных чисел.

Изучаются свойства функций k-значной логики. На основе кодирования функций многозначной логики в двоичной системе счисления определяется специальная операция суперпозиции. Показывается, что семейство классов, содержащих только функции, принимающие не более двух значений, и замкнутых относительно рассматриваемой операции и операции введения несущественной переменной, является счетным.

Исследуется задача о поиске явного вида метрики вращения на римановых многообразиях Бертрана в координатах определенного вида.

Для произвольной конечной системы A функций k-значной логики, принимающих значения из множества E_s= 0,..., s-1, k\geq s\geq 2, такой, что замкнутый класс, порожденный ограничением функций из A на множество E_s, содержит мажоритарную функцию, доказано существование констант c и d, таких, что для любой функции f\in [A] глубина D_A (f) и сложность L_A (f) функции f в классе формул над A связаны соотношением D_A (f) \leq c\log_2L_A (f) +d.

Доказана теорема о распределении значений аналогов сумм Клостермана. Получены асимптотические формулы для дробных моментов этих сумм.

Приводятся оценки сверху квадратичных показателей иррациональности чисел вида \sqrt 2k+1 \ln ( (k+1-\sqrt 2k+1 ) /k) и \sqrt 2k-1 \arctg (\sqrt 2k-1 / (k-1) ), где k\in N. В частности, улучшена оценка квадратичного показателя иррациональности \ln2.

В статье выведены асимптотические формулы.

Рассматривается конечная система A функций многозначной логики, принимающих значения 0 и 1, причем проекция A порождает класс всех монотонных булевых функций.

Рассматривается система M|GI|1| бесконечность с ненадежным прибором и временем обслуживания, зависящим от состояния системы. Находятся условие эргодичности системы и производящая функции для числа требований в системе в стационарном режиме.

Рассматриваются классы ограниченно детерминированных функций, в каждом состоянии которых реализуется функция из некоторого замкнутого класса D k-значной логики (P-множества). Показано, что существует континуум предполных классов, содержащих произвольное P-множество. Также рассматривается задача о существовании критерия распознавания полноты систем, содержащих P-множества.

Формулируется гипотеза о квантовой пропускной способности для каналов с бесконечномерными входным и выходным пространствами. Дается доказательство обращения этой гипотезы, использующее определения и свойства когерентной информации для бесконечномерных каналов.

Рассматривается обобщение квадратично-вычетных кодов на случай вычетов высших степеней. Исследуются свойства h-вычетных кодов. В некоторых случаях указывается вид и способ построения порождающего многочлена. С помощью полученных результатов выписываются порождающие многочлены кодов с вычетами 5-8-й степени.

Предлагается развитие метода осреднения для решения физически нелинейных задач о равновесии слоистых пластин или пластин из функционально-градиентных материалов. Согласно методу осреднения, решением задачи является суперпозиция решения глобальной задачи во всей области и решения локальной задачи для представительной области, например ячейки периодичности. Для нелинейной задачи суперпозиция неверна, что осложняет применение метода в случае нелинейности. Выходом может служить процедура объединения метода осреднения и метода линеаризации при решении краевой (или вариационной) задачи. Определяющие соотношения в механике деформируемого твердого тела можно рассматривать как уравнения относительно скоростей или дифференциалов напряжений и деформаций по времени или параметру нагружения. В том случае, если они линейны относительно скоростей, можно применить процедуру метода осреднения. В статье такой подход демонстрируется на примере симметричной слоистой пластины, изгибающейся под воздействием равномерно распределенной нагрузки, изменяющейся во времени.

В статье рассматриваются вероятностные характеристики методов технического анализа Каги и Ренко. Для линейной модели Л. Башелье дается выражение ожидаемой прибыли инвестора, использующего стратегию Каги. Также в работе получены некоторые свойства, связанные с величинами “падения” и “размаха” броуновского движения.

В статье приводится новое доказательство теоремы о квадратичном показателе иррациональности ln 2.

Рассматриваются виртуальные квандлы с двумя операциями и связанные с ними инварианты длинных виртуальных узлов. Выполняется построение одного из инвариантов и приводится пример доказательства неэквивалентности двух узлов при помощи этого инварианта.

Получена оценка для модуля тригонометрической суммы с простыми числами.

В статье получен аналог формулы суммирования Эйлера по целым точкам произвольного промежутка.

Получена верхняя оценка меры множества значений t ∈ (T,T + H ] при H = T^27/82+ε, для которых |S(t)| >= λ.

В работе рассмотрено некоторое множество одноместных функций многозначной логики, монотонных относительно частичного порядка специального вида. Введены операции композиции и свертки. Получен критерий полноты для рассматриваемой функциональной системы.

В статье рассматривается задача об оценке суммы значений функции делителей. Улучшена известная оценка, и этот результат обобщен для суммы возведенных в данную степень значений функции делителей.

В работе доказывается следующий результат: если при некотором вещественном A>0 для некоторого натурального n>1 и для всех x ∈ [0,1] имеет место неравенство |f^n| >A, то справедлива оценка где ρ(t)= 0.5-{t}.

Получена оценка снизу для многочленов от некоторых p-адических чисел.

В работе исследуется задача реализуемости двумерных римановых многообразий Бертрана, являющихся конфигурационным пространством обратной задачи динамики, как поверхностей вращения, вложенных в R3. Решается также задача локальной реализуемости (вблизи параллели) изучаемых римановых многообразий.

В работе рассматривается класс, состоящий из всех мультипликативных функций f , таких, что для некоторой постоянFй A>1 выполняется неравенство |f(p)|

Дано новое доказательство теоремы Дирихле о том, что в случае простого модуля q = 3 (mod 4) L -ряд Дирихле с вещественным характером не обращается в нуль.

В статье даются оценки QC-нормы, введенной Б. С. Кашиным и В. Н. Темляковым, тригонометрических полиномов специального вида. Полученный результат обобщает пример К. И. Осколкова.

Рассматриваются комплексные гамильтоновы системы на С× (С\{0}) со стандартной симплектической структурой ωc = dz ∧dw и функцией Гамильтона f = az2 +b/w+Pn(w) , где Pn(w) — многочлен степени n, числа a, Ь (Е С и ab= 0 . Изучается гамильтонова эквивалентность для некоторых естественных кла∈ов таких С-гамильтоновых систем. Устанавливается, как топологически устроены факторпространства, полученные отождествлением эквивалентных систем, в каждом из рассмотренных классов. Также доказывается, что бифуркационный комплекс для случая систем с гамильтонианом f = az + b/w + Pn(w) , где ab = 0, n ^ 0 , гомеоморфен двумерной плоскости.