Темы (задачи) для научных исследований по математике (стр. 5 )

Отрезки на прямой можно трактовать как фиксированные временные интервалы некоторых работ (требований). Тогда хроматическое число соответствующего графа пересечений можно рассматривать как наименьшее число приборов, необходимое для того, чтобы обслужить данный набор требований (каждый прибор в каждый момент времени может обслуживать не более одного требования). В этом контексте большой интерес представляет взаимосвязь χ(G) и ω(G) для графов пересечений различных геометрических объектов. Для графов пересечений отрезков интервальных графов, interval graphs известна точная оценка: χ(G) = ω(G) для любого интервального графа G (докажите – это очень просто). С другой стороны, очевидно, что

ω(G) ≤ χ(G) вообще для любого графа G.

Далеко не всегда требования занимают непрерывный промежуток времени. Например, некоторые требования могут иметь перерывы в обработке, в течение которых могут выполняться другие требования. В этом случае элементами I являются мультиотрезки, конечные объединения попарно непересекающихся отрезков. Назовём k-отрезком конечное объединение не более чем k отрезков. Для графа G пересечений k-отрезков известно, что χ(G) ≤ 2k (ω(G) - 1). Предлагается изучить соотношения между χ(G) и ω(G) для небольших значений k (2, 3, …) и выяснить, какие значения может принимать один из параметров при фиксированном втором.

Параметр ω(G) можно заменить на наибольшее число мультиотрезков, пересекающихся в одной точке (это не то же самое, но для 1-отрезков эти параметры совпадают).

Интересным случаем также является рассмотрение мультиотрезков, у которых пересекаются только компоненты (отрезки) с одинаковыми номерами.

3. On-line обработка интервальных заданий

На завод «Свобода» поступают по одному задания, которые надо бы выполнять. Каждое задание имеет фиксированные начало и окончание, то есть представляет из себя отрезок на оси времени. Из-за кризиса на заводе остался только один рабочий, так что не все задания получится выполнить. Это не страшно, потому что цель – выполнить как можно больше заданий. Каждое задание поступает в момент своего начала, и требуется немедленно решить, выполнять его или отклонить. Никакой информации про будущее нет. Если задание принято, рабочий занят до момента его окончания, и все поступающие за это время задания автоматически отклоняются. Если задание отклонено, оно пропадает навсегда.

Эффективность алгоритмов обработки заданий измеряется по сравнению со случаем, когда все задания известны заранее. Пусть OPT – наибольшее количество заданий, которые можно выполнить, имея полную информацию, а N – количество заданий, которое выполняется, используя ваш алгоритм. Хочется, разумеется, чтобы отношение N/OPT было как можно ближе к единице.

1. Найдите верхние и нижние оценки на возможную величину N/OPT, когда задания представляют собой а) произвольные отрезки; б) отрезки равной длины.

2. То же самое для случая, когда задания являются объединениями двух отрезков; двух отрезков равной длины; всё прочее в том же духе.

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

4. Кузнечиковая избегаемость слов

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

Конечное слово w над Σ (то есть конечная последовательность букв из алфавита Σ) назвается k-ой степенью слова u, если w получается из u выписыванием подряд слова u ровно k раз. Слово (конечное или бесконечное) W называется свободным от k-ых степеней (или избегающим k-ых степеней), если оно не содержит в качестве подслова никакого слова, являющегося k-ой степенью некоторого слова. Под подсловом здесь мы понимаем некоторую последовательность идущих подряд букв слова.

Докажите, что над алфавитом из двух букв не существует слова из хотя бы четырёх букв, избегающего квадратов. Докажите, что существует бесконечное слово над алфавитом из трёх букв, избегающее квадратов (слово Туэ), и бесконечное слово над алфавитом из двух букв, избегающее кубов (слово Туэ-Морса).

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

Задача 1. Симметрические многочлены

1)  Многочлен от переменных является симметрическим многочленом, поэтому его можно представить в виде многочлена с целыми коэффициентами от основных симметрических многочленов.

Пусть и его корни, тогда .

Элемент D(f) называют дискриминантом многочлена f. Какое свойство многочлена выражает условие: D(f) = 0?

2)  Найдите дискриминанты следующих многочленов:

а) квадратного трехчлена ;

б) кубического многочлена ;

в) приведенного кубического многочлена .

3)  Вспомните (изучите), как вычисляется определитель Вандермонда

4)  Из предыдущего задания следует, что .

Воспользуйтесь этим утверждением, свойством неизменности определителя при транспонировании матрицы и постарайтесь выразить многочлен через степенные суммы

5)  Докажите, что

Задача 2. Кососимметрические многочлены

  I.  Многочлен называется кососимметрическим тогда и только тогда, когда он меняет знак при перестановке любых двух переменных, т. е. для любых . Приведите примеры кососимметрических многочленов.

  II.  Существуют ли такие перестановки переменных, которые не меняют кососимметрический многочлен?

  III.  Пусть - произвольная перестановка переменных. Как связаны и , где - кососимметрический многочлен?

  IV.  Убедитесь, что если – кососимметрический многочлен над числовым полем, то .

  V.  Выведите следствие из утверждения IV.

  VI.  Докажите, что если – кососимметрический многочлен над числовым полем, то он делится на .

  VII.  Обобщите утверждение, полученное в V.

  VIII.  Докажите, что если – кососимметрический многочлен над числовым полем, то он делится на .

  IX.  Если и – два кососимметрический многочлен над числовым полем, причем частное f и g является многочленом, то что будет происходить с этим частным при произвольной перестановке двух переменных (произвольной перестановке переменных).

  X.  Докажите, что если частное двух кососимметрических многочленов является многочленом, то этот многочлен симметрический.

  XI.  Выведите следствие из утверждений, полученных в заданиях VII и X.

  XII.  Если , то из утверждения XI следует, что любой кососимметрический многочлен над числовым полем можно представить в виде , где – симметрический многочлен.