узоры в перестановках (математическое)

[avva]

Я не понимаю комбинаторику.

В этом семестре я хожу вольнослушателем на курс "вероятностные методы в комбинаторике" в Тель-Авивском университете (ведет Нога Алон). Просто так, интереса ради; вообще-то я не учусь, а работаю на полную ставку. После первых четырех лекций у меня складывается смешанное отношение к предмету. Методы, которые мы изучаем, очень интересны и красивы; но вопросы, на которые они помогают ответить, кажутся очень слабо мотивированными, и в большинстве случаев не связанными друг с другом и чем-либо еще. Есть исключения - напр. интересные фундаментальные вопросы о графах, числа Ramsey итп. - но это именно исключения.

Пару недель назад у меня никак не получалось решить задачу из домашнего задания, связанную с перестановками строк матрицы (вот условие задачки, вдруг кому интересно: доказать, что существует постоянная c > 0, так что для любого N и любой действительной матрицы NxN, в которой все числа разные, есть перестановка строк, после которой ни в одном столбце нет возрастающей подпоследовательности длиной c*sqrt(N)).

Я стал искать в сети статьи и материалы, связанные с подпоследовательностями в перестановках. И обнаружил, к своему удивлению, что есть целое отдельное поле исследований, называется pattern avoidance in permutations, которое занимается следующим вопросом. Пусть задана перестановка над (1...k) (узор, "паттерн"). Сколько есть перестановок над (1...n), n > k, в которых нет подпоследовательности, повторяющей порядок узора, и что можно о них сказать?

Оказывается, этим вопросом занимается куча людей. В нем есть сложные результаты, гипотезы, нерешенные проблемы, гора статей, ежегодные конференции. Вместе с тем мне не удалось обнаружить ни одного серьезного применения этих результатов или идей из этой области где-либо еще - я не говорю о "реальном мире", конечно - где-либо еще в математике или компьютерных науках. Может, я неправ, и такие серьезные и важные применения есть? Или их нет, и действительно, как это видится мне, это совершенно изолированное поле деятельности, sui generis, интересное лишь постольку, поскольку кому-то интересно знать, сколько перестановок избегают данный узор?

Меня это удивляет. Я не понимаю.

Comments

[neatfires.livejournal.com]

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

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

[silly_sad.livejournal.com]

я готов спорить что именно факультет экономики даст вам самый ложный ответ, или не даст вовсе :-)

на самом деле, програмист - НЕ рабочий. и тем более не конвейерный.
а в остальном, да, конечно тупая рутина тоже нужна.