xozzslip
@xozzslip
Чекни мой канал о кодинге https://bit.ly/2LNBAL8

Дискретная математика в непрерывной жизни?

Задался вопросом непосредственного использования дискретной математики.

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

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

PS Обращу еще раз внимание, я спрашиваю не о применимости дискретной математики в целом, её необходимость очевидна. Так же я не спрашиваю об использовании графов (древовидных структурах, алгоритмах обхода, поиска путей, паросочетаниях). Я спрашиваю об использовании конкретных разделов: реккурентные соотношения, неэлементарные комбинаторные объекты и любые другие advanced комбинаторные понятия , до которых я еще не добрался, которые интересным образом встречаются в исследованиях и разработке. Опишите (!), как и когда эти вещи встречались в вашей практике.
  • Вопрос задан
  • 3175 просмотров
Решения вопроса 1
Mrrl
@Mrrl
Заводчик кардиганов
Такие задачи чаще встречаются на этапе разработки алгоритма. Когда нужно понять эффективность алгоритма, уложить структуру в память, сравнить разные структуры или подходы и выбрать более подходящую. Не всегда удаётся сразу получить оценку O(N^k), бывают и более сложные ситуации. Или такая задача, как организовать перебор с наименьшим числом возвратов, как-то закодировать найденный вариант... тут и число отображений может пригодиться.
Проблема в этом вопросе - что когда надо применить какое-нибудь комбинаторное понятие, то применяешь его и идёшь дальше. В памяти этот факт не откладывается, в программе иногда тоже. Зато если в программе такие вычисления остаются - это гарантированная невозможность поддержки кода кем-либо ещё :) Даже при наличии комментариев.
Ответ написан
Пригласить эксперта
Ответы на вопрос 5
Deerenaros
@Deerenaros
Программист, математик, задрот и даже чуть инженер
UPD.
Покуда ответ был слишком большой, позволю себе обновление вставить в начало. В общем, поконкретнее надо? Ну ладно, рекуррентные соотношения - любые серьёзные алгоритмы, точнее - анализ их производительности. Комбинаторика очень часто применяется в чистом виде в решении каких либо задач - посчитать число объектов, связей, соотношений и прочего. В каком-либо порядке их перебрать, учитывая, что их количество слишком велико для расположения их всех в памяти. Все выкладки в области теории информации используют аппарат дискретной математики и теории вероятностей (вероятностные ансамбли, вероятность ошибки, алфавит сообщений, множества кодовых слов и так далее). Криптография так же любит использовать различные разделы, но в основном более простые. Хотя сегодня, с ростом сложности криптографии, растёт и сложность анализа её алгоритмов. Особенно это касается пост квантовой криптографии. Ну и хочу заметить, что advanced комбинаторные понятия нередко используются в физике элементарных частиц при описании их состояний. А, что забавно, только это и является основной информацией, что можно получить в квантовой механике - остальное лишь вероятностями.

На старт, внимание, и... Поехали!

Прежде чем пытаться осудить математиков в бесполезности их работы, стоит заметить, что среди тех самых математиков открыта специальная олимпиада на тему "самое бесполезное исследование в жизни", которое не только конкурирует с шнобелевской премией, но и зачастую весьма и весьма её превосходит (в плане слогана самих игнобелевских премий - "заставляют сначала засмеяться, а потом — задуматься", правда тут не смех порой, а банальное надругательство над понятийным аппаратом).

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

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

Годами математики сочиняли бесполезные работы по теории чисел, считая себя победителями в их собственной специальной олимпиаде. Годами они сочиняли n-мерные пространства. Но пришёл фон Нейман и создал компьютер. Пришёл Клод Шеннон и постулировал конфиденциальный канал со сколь угодно малой вероятностью успешной передачи информации. Набежала ещё туева хуча физиков-теоретиков и создали M-теорию струн.

А вы говорите... Непрерывная жизнь. А что если она очень даже прерывная?
Ответ написан
@nano_e_t_4
Что то подсказывает, что любая, более или менее серьезная разработка (будь то it сфера, физика (тем более!), и пр.)) требует серьезного математического аппарата. А там уже все это разворачивается в полном виде. Иначе это было бы никому не нужно, и никем не использовалось.
Ответ написан
@mamkaololosha
Для начала погугли что такое middleware. Как его пишут и кто. Когда автотесты работают часами. Когда ты думаешь 3 часа, а потом пишешь 15 строчек кода и всё сразу работает, т.к. запустить и проверить "как у всех" тупа нету времени. Любая компания, которая пишет своё-чужое-поисковое-иное хайлоад-middleware всё это использует. Amazon, Google, Facebook, Twitter, Mailru, Yandex, Rumbler, Bing. Все-все-все.
Ответ написан
@deleted2-brainick
Конечно, же в реальной жизни используется дискретная математика. Просто зачастую она скрыта глубоко в недрах вещей которыми мы пользуемся каждый день. Простой пример: в протоколе The Border Gateway Protocol (BGP) используется алгоритм Дейстры.
UPD. Не BGP, а OSPF. - благодарю throughtheether за исправление неточности.
Ответ написан
kloppspb
@kloppspb
решать рекуррентное соотношение через производящие функции в какой-то реально полезной задаче?
...
теорией графов
...


Подобные (гусары, молчать!) вопросы снимаются сразу же после запуска профайлера на коде с тупой сортировкой пузырьком. Во вполне реальных задачах, когда данных станет чуть больше, чем "тестовый пример из ста значений" :)
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
IVARIANT Санкт-Петербург
от 180 000 до 250 000 руб.
CORE Москва
До 110 000 руб.
27 июн. 2019, в 01:26
50000 руб./за проект
27 июн. 2019, в 00:27
250000 руб./за проект