Hardprob/Minimum Tree Compact Packing — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
  
* Дерево <m>T=\left(V,E\right)</m>, нормализованный вес на вершинах <m>w: V → Q^{+}</m>, <m>\sum_{v \in V}w(v)=1</m>, нормализованный → <m>\sum_{v \in V}w(v)=1</m> и некоторая страничная емкость <em>p</em>.
+
* Дерево <m>T=\left(V,E\right)</m>,  
 +
** нормализованный вес на вершинах <m>w: V → Q^{+}</m>, <m>\sum_{v \in V}w(v)=1</m>,  
 +
** некоторая страничная емкость <em>p</em>.
 
* Найти компактную упаковку <em>T</em> на страницах емкости <em>p</em>, т.е. функция <m>\tau : V \rightarrow Z^{+}</m>, такая, что <m>|\tau^{-1}(i)| = p</m>
 
* Найти компактную упаковку <em>T</em> на страницах емкости <em>p</em>, т.е. функция <m>\tau : V \rightarrow Z^{+}</m>, такая, что <m>|\tau^{-1}(i)| = p</m>
 
* Минимизировать страничные сбои этой упаковки, т.е.  
 
* Минимизировать страничные сбои этой упаковки, т.е.  

Версия 17:58, 11 апреля 2023


  • Дерево ,
    • нормализованный вес на вершинах , ,
    • некоторая страничная емкость p.
  • Найти компактную упаковку T на страницах емкости p, т.е. функция , такая, что
  • Минимизировать страничные сбои этой упаковки, т.е.

, где



Задача в лаб22 (рид-онли просмотр)