Гдe пpимeняетcя кoмбинатoрика?

[Евгений Б.]

Как именно комбинаторика используется в практических целях?

У Виленкина написано:

Цитата:

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

Ещё Я нашёл:

Цитата:

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

[Архипов]

Еще в кулинарии. Миллион рецептов - результат комбинаторики.
Еще в астрологии (комбинации планет и судеб), медицине (миллион рецептов для миллиона болезней), В быту (куда - шкаф, куда - кровать, куда - телевизор?). Самая распространенная и актуальная проблема человечества - чем еше бы себя развлечь?

[Евгений Б.]

Архипов писал(а):

в кулинарии

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

Архипов писал(а):

в астрологии

а при составлении гороскопа тоже используется?(помимо статистики, конечно)

Архипов писал(а):

в медицине

а здесь наверное анализируют совместимость веществ, входящих в препараты?

[bubu gaga]

Я комбинаторику так и понимаю, есть какое-то словесное описание множества (или способа его построения) и надо с помощью аналогий найти ему эквивалентное множество, для которого у нас уже есть способ подсёта элементов. Всюду где такая задача стоит и нужна комбинаторика.

[Парджеттер]

Евгений Б. в сообщении #138120 писал(а):

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

Евгений Б. в сообщении #138120 писал(а):

а при составлении гороскопа тоже используется?(помимо статистики, конечно)

Евгений Б. в сообщении #138120 писал(а):

а здесь наверное анализируют совместимость веществ, входящих в препараты?

Ага... а еще в конструировании... сколько можно редукторов собрать из заданного комплекта валов, шестерен, подшипников и корпусов, если учесть, что не все совместимы...

Шутки, конечно, это замечательно. Ну а если серьезно - где?

[Really]

Евгений Б. писал(а):

Как именно комбинаторика используется в практических целях?

Цитата:

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

Вот в азартных играх я видел как используется. Когда по покеру соревнования показывают
в углу экрана высвечиваются шансы каждого игрока на победу в данном розыгрыше.
Вот вам и комбинаторная задача. Хотя может быть это использование комбинаторики
в телевидении?

[Архипов]

Really в сообщении #138207 писал(а):

Вот в азартных играх я видел как используется. Когда по покеру соревнования показывают
в углу экрана высвечиваются шансы каждого игрока на победу в данном розыгрыше.
Вот вам и комбинаторная задача. Хотя может быть это использование комбинаторики
в телевидении?

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

[Парджеттер]

Архипов в сообщении #138225 писал(а):

Вопрос задан о применении комбинаторики в практике.

Правда непонятно - имеется в виду, где можно применить или где она реально применяется? Вот с последним, по-моему, ситуация сложнее.

Архипов в сообщении #138225 писал(а):

Комбинирование - творческий акт

По-видимому, особенно превзошел в этом деле тов. О.Бендер.

[Really]

Архипов писал(а):

"Шансы" - это из теории вероятностей.

Шансы, безусловно из теории вероятностей. А вот подсчет количества всех возможных
вариантов расклада карт - задача комбинаторная.

[маткиб]

Комбинаторика активно применяется в теории синтеза цифровых электронных схем и в теории сложности алгоритмов.

[Евгений Б.]

Парджеттер писал(а):

Правда непонятно - имеется в виду, где можно применить или где она реально применяется? Вот с последним, по-моему, ситуация сложнее.

Я имел в виду, где она реально на практике применяется.

Парджеттер писал(а):

Ага... а еще в конструировании...

Мне где-то попадалась инфа, что и там тоже применяется, только не знаю для чего именно.

bubu gaga писал(а):

Я комбинаторику так и понимаю, есть какое-то словесное описание множества (или способа его построения) и надо с помощью аналогий найти ему эквивалентное множество, для которого у нас уже есть способ подсёта элементов. Всюду где такая задача стоит и нужна комбинаторика.

Нужна - это в смысле используется на самом деле или это теоретически только? (по-моему теоретически )

маткиб писал(а):

Комбинаторика активно применяется в теории синтеза цифровых электронных схем и в теории сложности алгоритмов.

А на практике? Или приведённые выше теории и есть "практика".
А какой-нибудь пример использования можно?

[маткиб]

Евгений Б. писал(а):

А на практике? Или приведённые выше теории и есть "практика".
А какой-нибудь пример использования можно?

Примеров, где она УЖЕ ПРИМЕНЯЕТСЯ, я не знаю. Зато знаю примеры, где она может применяться. Например, смотри статью
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose D. P. Rolim
"Parallel Read Operations Without Memory Contention"
по ссылке
http://eccc.hpi-web.de/eccc-reports/200 ... 3/Paper.ps

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

Ещё на меня в своё время произвели впечатление теоретические результаты из теории сложности алгоритмов, которые опираются на хитрые комбинаторные утверждения:
1) теорема Вэлианта-Вазирани
http://en.wikipedia.org/wiki/Valiant-Vazirani_theorem
2) теорема Тода
http://logic.pdmi.ras.ru/~hirsch/studen ... cture8.pdf
http://logic.pdmi.ras.ru/~hirsch/studen ... cture9.pdf
До применения этих результатов на практике ещё очень далеко, но оно не исключается.

[Парджеттер]

Евгений Б. в сообщении #138330 писал(а):

Я имел в виду, где она реально на практике применяется.

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

Евгений Б. в сообщении #138330 писал(а):

Мне где-то попадалась инфа, что и там тоже применяется, только не знаю для чего именно.

Я Вам так скажу. Работая инженером-конструктором, я никогда не сталкивался с применением комбинаторики - ни на практике, ни в каких-либо специализированных книгах.

Евгений Б. в сообщении #138330 писал(а):

А какой-нибудь пример использования можно?

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

Ну а вообще, в computer science комбинаторика применяется более, так сказать, "напрямую".

[bubu gaga]

Евгений Б. писал(а):

Нужна - это в смысле используется на самом деле или это теоретически только? (по-моему теоретически )

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

Вот здесь длиннющий список, для "впечатлиться" (я лично даже сам не ожидал)
http://en.wikipedia.org/wiki/List_of_co ... ics_topics

[Архипов]

Парджеттер в сообщении #138377 писал(а):

Я Вам так скажу. Работая инженером-конструктором, я никогда не сталкивался с применением комбинаторики - ни на практике, ни в каких-либо специализированных книгах.

Я уже приводил более широкую трактовку понятия "комбинаторика" - творческий труд - комбинирование свойств, форм, функций, объектов. Как раз то, чем Вы занимались, будучи инженером-конструктором. Дается задание: сконструировать механизм (или агрегат, или систему) с определенными свойствами и функциями. Ваша задача - найти оптимальный вариант сочетания данных требований. Придется перебирать варианты (отбрасывая негодные, пробуя годные). Рубик придумал кубик (скомбинировал 26 кубиков). А потом другие конструкторы-комбинаторы придумали еще десяток фигур. Дизайнеры, декораторы, модельеры тоже только тем и занимаются, что комбинируют формы, цвета, фигуры...
Композиторы, писатели, художники тоже комбинируют (перебирают варианты, оставляя наиболее удачные и отбрасывая негодные).
Один японец запрограммировал звуковой синтезатор для автоматического перебора различных комбинаций нот и тембров, потом сидел и слушал. Более удачные варианты "композиций", на свой вкус, записывал на диск. Автомат "творил", а человек оценивал.
Шахматы - результат творческого поиска сочетания (комбинации) фигур. Всякие игры - комбинация правил, объектов, субъектов, случайных и закономерных ситуаций.
В агротехнике - в сотни горшочков сажают различные сорта одной культуры, помещают их в различные условия группами (температура, влажность, освещенность, химический состав удобрений,...) . Таким образом, за один вегитативный цикл делаются десятки и сотни экспериментов, для реализации которых без комбинаторного приема понадобилось бы десятки, сотни лет.
Задача математики - подсчет вариантов, а вот способ комбинирования (манипулирования, сочетания, перебора, набора,.перестановки, отражения. переноса. поворота...) -творческая задача. Придумать удачные, интересные, полезные способы комбинирования труднее, чем сосчитать возможное их количество.
Еще пример: компьютерная игра "Тетрис" - из мизерного количества простейших фигур комбинаторным приемом получается большое количество увлекательных ситуаций. Изобретение.
Или: запрограммировать звуковой синтезатор азбуки Морзе. Программа в машинных кодах занимает где-то около 60 байтов памяти. Благодаря комбинаторному принципу самой азбуки.
А мобильные телефоны? Это же комбайны (комбинация функций)! Но функции-то надо было придумать, внедрить в электронную схему, упорядочить.
Автоматические переводчики с одного языка на другой, смвольные вычисления физических, математических, химических, семантических, логических структур. Необъятное поле для творчества, изобретений, сортировки и отбора наиболее удачных вариантов.
А кодирование номерных знаков, аэропортов, городов и стран, миллионов видов товаров, химикатов, материалов, статистических данных, доменов, сайтов и серверов, пользователей и прочего, прочего, прочего...
А логистика? Тоже основана на комбинаторике, топологии и последующей автоматизации перебора, сортировки, оптимизации, резервирования.
Зайдем в супермаркет. В нем почта, интернет, аптека, банкомат, фотоателье, широчайший ассортимент товаров и услуг. Комплекс, комбинат, комбайн.
Кстати, отечественное изобретение - сельпо. В нем продавались: продукты, инструменты, гвозди, электротовары, химтовары, мебель, патроны, автомобили, керосин, одежда, обувь, канцтовары, велосипеды, и прочее. Покупалась тара, яйца, овощи, сало, утильсырье и прочее..
Предприниматель - комбинатор по сути. Ежедневно что-то придумывает, пробует, ошибается, находит удачнную комбинацию, вновь что-то затевает. А мы спрашиваем: "где применить комбинаторику?"