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

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

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

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

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