2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Формула включений-исключений
Сообщение08.08.2023, 15:33 
Что сейчас sota в приближении формулы включений-исключений? Т.е. мне нужно посчитать $p(\cup _{i=1}^n A_i)$ как можно быстрее, жертвуя точностью. Также, в моей задаче $p(\cap _{i \in S}A_i)$ считаются за время, не зависящее от $|S|$, а $n\sim50-200$.

 
 
 
 Re: Формула включений-исключений
Сообщение08.08.2023, 17:36 
Аватара пользователя

(sota)

vlad_light в сообщении #1604426 писал(а):
sota
Изображение

 
 
 
 Re: Формула включений-исключений
Сообщение08.08.2023, 21:15 

(state of the art)

svv

Аааааа, вон оно что Михайлович! :D :D А Вам встречалась где-то такая аббревиатура - sota?

P.S. State of the art программных пакетов, считающих формулу включений-исключений - это романтично, с моей точки зрения )

 
 
 
 Re: Формула включений-исключений
Сообщение08.08.2023, 21:43 
Не помогут ли тут приближенные алгоритмы для подсчета уникальных элементов типа HyperLogLog?

 
 
 
 Re: Формула включений-исключений
Сообщение08.08.2023, 22:50 
tolstopuz в сообщении #1604480 писал(а):
Не помогут ли тут приближенные алгоритмы для подсчета уникальных элементов типа HyperLogLog?

Самих множеств у меня нет, я могу только считать $p(\cap _{i \in S}A_i)$ для произвольного $S$.

(Оффтоп)

Я не про программные пакеты, а скорее алгоритм. Но будет полезно, если есть что-то на python.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group