Hardprob/Minimum Tree Compact Packing — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Дерево <m>T=\left(V,E\right)</m>, нормализованный вес на верш…») |
StasFomin (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
* Минимизировать страничные сбои этой упаковки, т.е. | * Минимизировать страничные сбои этой упаковки, т.е. | ||
<m>\sum_{v ∈ V}c_{\tau}(v)w(v)</m>, где | <m>\sum_{v ∈ V}c_{\tau}(v)w(v)</m>, где | ||
| − | <m> | + | <m> |
| − | \begin{displaymath} | + | \begin{displaymath} |
| − | c_{\tau}(v)=\sum_{i=0}^{l(v)-1}\Delta_{\tau}(v_{i}), | + | c_{\tau}(v)=\sum_{i=0}^{l(v)-1}\Delta_{\tau}(v_{i}), |
| − | \end{displaymath} | + | \end{displaymath} |
| − | </m> | + | </m> |
---- | ---- | ||
Версия 17:57, 11 апреля 2023
- Дерево , нормализованный вес на вершинах , , нормализованный → и некоторая страничная емкость p.
- Найти компактную упаковку T на страницах емкости p, т.е. функция , такая, что
- Минимизировать страничные сбои этой упаковки, т.е.
, где
Задача в лаб17 (рид-онли просмотр)