Где применяется комбинаторика в информатике?

Question

[Никита]

Только начинаю изучать комбинаторику. В чем состоит применение комбинаторики в информатике

Answer 1

[Александр]

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

Comments

[mayorovp]

> Из той же оперы - решение задачи о кратчайшем пути в графе, которая сейчас, вроде бы, решается полным или частичным перебором,
Эй, что это за новости?! Эта задача решается куда быстрее, чем полным перебором. Обход в ширину (для невзвешенного графа) и алгоритм Дейкстры (для взвешенного)

[Александр]

mayorovp: Поэтому и вроде бы :)

[Владислав]

Александр Горбунов: уже больше полувека как не вроде бы.)

[Александр]

>А как комбинаторика может куда-то входить или выходить?

brainick: если вкратце, то сам термин комбинаторика ввел в употребление Лейбниц (математик был такой), на основе его (и не только) работ, Эйлер сформулировал "Задачу о семи мостах", давшую начало развитию теории графов, и окончательно вывел комбинаторику в самостоятельный раздел математики.

[Александр]

brainick: правда-правда

Answer 2

[Владимир Мартьянов]

Перебор паролей, например.
UPD. Расчеты всевозможные, например каково количество возможных битовых строк длиной N бит, если известно что в них ровно X бит выставлено в 1.

Answer 3

[Mrrl]

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

UPD. Можно вспомнить одно место, где комбинаторика требуется в обычных задачах. Это когда у нас есть множество каких-нибудь подмножеств, перестановок, слов над алфавитом, или ещё чего-нибудь, что обычно считает комбинаторика. И мы хотим по элементу этого множества найти его индекс. И наоборот.
Задача возникает не часто, но если возникла, то без комбинаторных формул не обойтись никак.