может я чего не понимаю, но по-моему это нужно для хороших псевдо-случайных генераторов

и в криптографии

Именно.

очень часто и много слышал от знакомых физиков, что математики-теоретики на передовой современной науки зашли в такие глубокие и специализированые дебри, что:
1) не понимают даже друг друга зачастую
2) не несут никакой прикладной пользы

Забавно, слышал то же самое про физиков-теоретиков из разных областей, в особенности в отношении квантовой и астрофизики :)

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

Pattern avoidance naturally appears in Schubert calculus and Kazhdan-Lusztig theory, see for example works of Sara Billey. For example smoothness of Schubert varieties can be characterized by avoidance of certain patterns. Results of this flavor in my opinion are often deep and beautiful.

You are right however that most of pattern avoidance questions studied do not come from any question in other area of mathematics. Such study is indeed not very well motivated.

In general with combinatorics one should distinguish two almost unrelated kinds: algebraic, that studies enumerative questions coming from from other areas, and non-algebraic, often called Erdos-style. The first type of combinatorics is intimately related with many other areas and does not suffer from lack of motivation. The second kind very often is locked in itself. There are notable exceptions however, for example many things Terry Tao does can be viewed (I think) as very high level Erdos-style combinatorics.

Спасибо, это очень интересно (хоть мне и не хватает алгебраических знаний, чтобы даже приблизительно оценить работы Sara Billey, увы).

распознавание образов

Я имею некое отношение к науке распознавания образов. Но что-то вот так сходу не могу придумать/вспомнить задачу где такая комбинаторика была бы полезна.
Не могли бы вы привести более конкретный пример? Действительно очень интересно.

Ну, комплексные числа тоже долгое время считались не имеющими применения в хозяйстве, а прошло 300 лет, начали самолёты и подводные лодки строить - оказалось, что гидро- и аэродинамика на языке этих странных чисел описывается проще...

Много лет считали, что теория чисел не имеет и никогда не будет иметь приложений. Кому какое дело до того, как данное большое число разлагается на простые множители? Ан нет, изобрели односторонние функции и стали в криптографии использовать...

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

Может быть, и до узоров в подпоследовательностях дойдёт...

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

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

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

Теоретическая математика всегда опережала прикладные нужды на несколько сот лет. Удивительно, что вы раньше с этим не столкнулись..

Это не совсем тот случай; речь идет о влиянии и связях внутри самой математики.

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

1. Проще всего спросить самого Ногу. Он точно знает где все это применяется.

2. На конгрессе в Мадриде, 2006, Ричард Стенли делал пленарный доклад про это. Доклад должен быть в сети. Правда, мне он не показался очень интересным, как раз из-за отсутсвия мотивации. Хотя связи с алгоримом RSK там обсуждались.

3. Основные работы Окунькова тоже связаны с перестановками, у него (с Некрасовым) есть применения к физике. Он за это получил премию Филдса (тоже в Мадриде). Есть еще связи со случайными матрицами (а значит - со всей остальной математикой, включая теорию чисел).

1. Не уверен, что его это интересует, хотя в любом случае наверняка знает, вы правы. Я спрошу у него.

2. Нашел эту статью, спасибо; http://www-math.mit.edu/~rstan/papers.html , сделать поиск на Madrid. Она почти вся о частном случае строго возрастающих/убывающих паттернов, который, понятно, пользуется независимым интересом, и тесно связан с RSK, как вы отметили (я на самом деле не знаю ничего про Young tableux и RSK, хотя давно хочу прочитать; может, соберусь как раз ввиду этого). Об общем случае pattern avoidance - меня именно это больше всего занимает, т.к. тяжелее представить связь с другой математикой, чем в частном случае возрастающей подпоследовательности - Стенли говорит, и упоминает, что о нем существует огромная литература и он бурно растет, но ничего не говорит о приложениях.

Спасибо!

Применяется в поточной криптографии и в связи. Например, некоторые паттерны непригодны для кодирования сигнала, если после них идёт что-то типа NRZ.

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

Эх, вот так просто ходить на курс Алона. Здорово!

Географическое удобство :)

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

То, что Вы заметили - это отличительное свойство "венгерской", или Erdos-style математики, которая представляет собой огромный аморфный набор плохо мотивированных проблем. Не так давно в ЖЖ в разных журналах была разветвленная дискуссия на тему о том, хорошо это или плохо; см. ссылки в одном из моих последних постов.

Сейчас популярность этого предмета растет. Деньги, получаемые под предлогом приложений к computer science, играют немалую роль.

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

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

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

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

12 лет назад, когда мы ваяли один квест, я, к своему жуткому удивлению, обнаружил, что даже матёрые мехматовцы решают подобные задачи тупым перебором...
Если б не моя старая нелюбовь к математике, может быть и заинтересовался бы. А так, конечно, тема для журнала "Квант". Он жив ещё, интересно?

Это действительно интересно только потому, что это кому-то интересно. Математика с большой буквы не требует никаких мотиваций, кроме чисто научного интереса. А если для какого результата вдруг найдется прикладное применение - так это приятный, но побочный "выхлоп" :)

Готвальд Харди, вами бы гордился. Только применение это всё-таки неприятный и нежелательный побочный эффект.

Это последствия кризиса - от всего начинают ждать применимости в народном хозяйстве.