A quantitative analysis of parametric CAD model complexity and its relationship to perceived modeling complexity

Digital product data quality and reusability has been proven a critical aspect of the Model-Based Enterprise to enable the efficient design and redesign of products. The extent to which a history-based parametric CAD model can be edited or reused depends on the geometric complexity of the part and the procedure employed to build it. As a prerequisite for defining metrics that can quantify the quality of the modeling process, it is necessary to have CAD datasets that are sorted and ranked according to the complexity of the modeling process. In this paper, we examine the concept of perceived CAD modeling complexity, defined as the degree to which a parametric CAD model is perceived as difficult to create, use, and/or modify by expert CAD designers. We present a novel method to integrate pair-wise comparisons of CAD modeling complexity made by experts into a single metric that can be used as ground truth. Next, we discuss a comprehensive study of quantitative metrics which are derived primarily from the geometric characteristics of the models and the graph structure that represents the parent/child relationships between features. Our results show that the perceived CAD modeling complexity metric derived from experts’ assessment correlates particularly strongly with graph-based metrics. The Spearman coefficients for five of these metrics suggest that they can be effectively used to study the parameters that influence the reusability of models and as a basis to implement effective personalized learning strategies in online CAD training scenarios.     

Kempe链的研究与民航空域频率覆盖重构

本文给出了构建Kempe链的算法,用Kempe链方法证明了Heawood反例是四色的,探讨了基于Kempe链模型的民航空域频率覆盖重构的可能性。     

用例驱动的软件复杂性度量及应用

在用例驱动的软件开发过程中,研究软件复杂性,对于项目规模估算、进度控制及度量、评估都具有积极的意义.从需求获取、分析、设计、测试等阶段详细讨论了整个软件开发过程中如何获取、量化用例层次上的软件复杂度的方法,概括了研究的意义并通过实践进一步验证.根据它对软件可靠性相关指标参数的影响,探讨基于用例的软件可靠性度量分析方法的改进.     

Kolmogorov complexity and combinatorial methods in communication complexity

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods.We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify hard inputs.We show that our method implies the rectangle and corruption bounds, known to be closely related to the subdistribution bound. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication. We then show that our method generalizes the VC dimension and shatter coefficient lower bounds. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result.     

Aesthetics and complexity in digital layout systems

Abstract

The layout of pages which carry information is the bread and butter of the graphic design profession. The rationale of what elements are chosen and where they are placed is based on tacit knowledge gained over a number of years of experience. The aesthetics associated with the overall finished design are often based on a style. Important elements of style are complexity and aesthetic value. In this paper I explore how various mathematical aesthetic functions can use complexity as an arousal enhancing or limiting mechanism in the application of layout designs.     

A spaceflight operation complexity measure and its experimental validation

A measure of operation complexity in spaceflight is proposed using a weighted Euclidean norm based on four factors: complexity of operation step size (COSS), complexity of operation logic structure (COLS), complexity of operation instrument information (COII), and complexity of space mission information (CSMI). The development of the operation complexity measure followed four steps. First, four factors were identified to be reflected in the operation complexity measure for spaceflight. Second, the entropy theory was adopted to measure the four factors. Then, the weights of the four factors were determined based on a questionnaire survey of 10 astronauts. Finally, the operation complexity values of spaceflight operations were determined by the weighted Euclidean norm of the four factors. To verify the validity of this complexity measure, a one-factor experiment was designed to test the proposed hypotheses. Ten subjects participated in the experiment and performed 179 trials. Both objective indexes (operation time and error rate) and subjective indexes (workload evaluated by NASA Task Load Index questionnaire and subjective complexity rating) were used in the experiment. The data analysis showed that the average operation time, subjective complexity rating, and subjective workload could be predicted well from the operation complexity value (R = 0.876, 0.802, and 0.698, respectively); and the error rate could only be partly explained by the operation complexity value (R = 0.343).

Relevance to industry

The proposed operation complexity measure can be used for ergonomics evaluation of spaceflight operation design. It can also be used for astronaut training planning. Training resources can be allocated to spaceflight tasks according to their operation complexity.     

基于参数化零部件的自动装配设计

介绍在参数化零部件库的基础上实施装配设计的参数化。在设计者对装配尺寸或零部件的参数作出个性后,可自动进行装配图调整,达到零部件参数化和装配设计参数化的统一,实现自动设计。     

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。     

面向任务的重叠联盟结构生成计算复杂性

传统的重叠联盟形成问题大都聚焦智能体, 鲜有从任务视角出发. 为此, 本文首先构建了一种面向任务的 重叠联盟结构生成模型, 并分析了其解空间和相关决策问题的计算复杂性. 此外, 基于流网络分别设计了相应的孤 立联盟、重叠联盟、重叠联盟结构成功性判别算法和最优重叠联盟结构生成算法. 分析结果表明, 判别孤立联 盟、重叠联盟、重叠联盟结构的成功性的时间复杂度均与智能体数和任务数呈多项式关系, 而搜索最优重叠联盟结 构的时间复杂度与智能体数和任务数呈指数关系. 最后, 通过仿真实验验证了上述结果.     

The complexity of achievement and maintenance problems in agent-based systems

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).     

Reducing the effect of complexity on volume model evaluation

A major problem with volume modelling systems is that processing times may increase with model complexity in a worse than linear fashion. The authors have addressed this problem, for picture generation, by repeatedly dividing the space occupied by a model, and evaluating the sub-models created only when they meet a criterion of simplicity. Hidden surface elimination has been integrated with evaluation, in such a way that major portions of the model which are not visible are never evaluated. An example demonstrates a better than linear relationship between model complexity and computation time, and also shows the effect of picture complexity on the performance of the process.     

软件产品族构件演化及其复杂度评价

基于现有构件以演化方式产生出新的构件是提高软件复用水平和满足用户不断变化需求的关键技术。首先,给出了一种基于多个代理的构件演化交互模型,该模型能够以自治方式实现演化一致性数据处理;其次,利用方面织入机制将新的功能代码准确织入现有构件内部,降低了构件不同功能代码的耦合度;然后,对构件演化的复杂度进行了讨论,给出了四项演化复杂度评价指标和一个复杂度计算模型,以对构件演化成本进行量化估算;最后,以数字化校园中各应用系统间数据交换构件演化为例,证明了方法的可行性和有效性。     

Classifier performance as a function of distributional complexity

When choosing a classification rule, it is important to take into account the amount of sample data available. This paper examines the performances of classifiers of differing complexities in relation to the complexity of feature-label distributions in the case of small samples. We define the distributional complexity of a feature-label distribution to be the minimal number of hyperplanes necessary to achieve the Bayes classifier if the Bayes classifier is achievable by a finite number of hyperplanes, and infinity otherwise. Our approach is to choose a model and compare classifier efficiencies for various sample sizes and distributional complexities. Simulation results are obtained by generating data based on the model and the distributional complexities. A linear support vector machine (SVM) is considered, along with several nonlinear classifiers. For the most part, we see that there is little improvement when one uses a complex classifier instead of a linear SVM. For higher levels of distributional complexity, the linear classifier degrades, but so do the more complex classifiers owing to insufficient training data. Hence, if one were to obtain a good result with a more complex classifier, it is most likely that the distributional complexity is low and there is no gain over using a linear classifier. Hence, under the model, it is generally impossible to claim that use of the nonlinear classifier is beneficial. In essence, the sample sizes are too small to take advantage of the added complexity. An exception to this observation is the behavior of the three-nearest-neighbor (3NN) classifier in the case of two variables (but not three) when there is very little overlap between the label distributions and the sample size is not too small. With a sample size of 60, the 3NN classifier performs close to the Bayes classifier, even for high levels of distributional complexity. Consequently, if one uses the 3NN classifier with two variables and obtains a low error, then the distributional complexity might be large and, if such is the case, there is a significant gain over using a linear classifier.     

F2上周期多序列及其广义对偶多序列的复杂性分析*

联合线性复杂度是度量周期多序列强度的一个重要指标。将二元周期多序列按位取反后得到的周期多序列,与原序列有着密切的联系。 针对这类特殊的周期多序列,提出了二元周期多序列的广义对偶多序列定义,讨论了它们联合线性复杂度之间的关系。同时,定义了二元周期多序列的联合重量复杂度,并给出了它们联合重量复杂度之间的关系。     

On complexity of single-minded auction

We consider complexity issues for a special type of combinatorial auctions, the single-minded auction, where every agent is interested in only one subset of the commodities.First, we present a matching bound on the communication complexity for the single-minded auction under a general communication model. Next, we prove that it is NP-hard to decide whether Walrasian equilibrium exists in a single-minded auction. Finally, we establish a polynomial size duality theorem for the existence of Walrasian equilibrium for the single-minded auction.     

A characterization of average case communication complexity

It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.     

The parameterized complexity of probability amplification

In this paper we study the parameterized complexity of probability amplification for some parameterized probabilistic classes. We prove that it is very unlikely that W[P] has the probability amplification property.