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

Только начинаю изучать комбинаторику. В чем состоит применение комбинаторики в информатике
  • Вопрос задан
  • 9680 просмотров
Решения вопроса 2
@saphire13
Системный администратор
На самом деле довольно много где. К примеру, комбинаторика, по сути впервые упомянутая Лейбницем, вышла в так называемую задачу о семи мостах, которая дала начало теории графов, и уже на основе которой разработаны, например, сетевые протоколы динамической маршрутизации. Из той же оперы - решение задачи о кратчайшем пути в графе, которая сейчас, вроде бы, решается полным или частичным перебором, что тоже является комбинаторикой, а уже само решение такой задачи ложится в основу маршрутизации в сетях. Так же она является неотъемлемой частью создания искусственных нейронных сетей, что является частью развития отрасли искусственного интеллекта. Так же применяется в криптографии.
Ответ написан
@vilgeforce
Раздолбай и программист
Перебор паролей, например.
UPD. Расчеты всевозможные, например каково количество возможных битовых строк длиной N бит, если известно что в них ровно X бит выставлено в 1.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Mrrl
@Mrrl
Заводчик кардиганов
Мало применяется. В информатике она, скорее всего, понадобится в анализе сложности различных алгоритмов, выборе оптимальной стратегии перебора. В олимпиадном программировании встречается постоянно. В реальной жизни - в основном, когда комбинаторные формулы требуются для расчётов вероятностей, а те, в свою очередь, для проверки статистических гипотез.
Ещё комбинаторика может пригодиться в задачах, связанных со статистической физикой, когда через число состояний оценивается энтропия системы, а через неё - дальнейшее поведение или устойчивость. Возможно, она нужна для алгоритмов вроде сверхбыстрого умножения чисел. Но всё это очень далёкий уровень, при взгляде с которого элементарная комбинаторика уже неотличима от таблицы умножения.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы