一种抗高阶旁路攻击的LED密码算法

LED密码算法是2011年提出的超轻量级密码算法,主要是为资源受限下物联网加密应用研发的.轻量级密码算法结构相对简单,更容易被旁路攻击成功.随机掩码是一种有效抗旁路攻击的方法,在深入LED密码算法结构研究的基础上,提出一种全随机掩码的LED密码算法CMLED.论述了CMLED算法的设计方法,从形式化方面给出了抗高阶旁路攻击选择掩码的原则.同时,对全随机掩码的CMLED与原始算法进行了硬件资源占用与加密效率对比,实验表明CMLED仍然可以高效地在智能卡上实现.     

模糊推理反向三Ⅰ问题的真度形式解

在n值命题逻辑系统Ln,L*n中提出了模糊推理的反向三Ⅰ问题,并给出了反向三Ⅰ问题的真度形式解,从而在系统Ln与L*n中建立了反向三Ⅰ问题的形式化推理机制,为模糊推理的反向三Ⅰ算法奠定了逻辑基础.     

等谱流的有限积分法(英文)

本文我们考虑基于径向基函数插值的有限积分法来近似求解等谱流问题,并提出了一种新的算法.我们的方法很好地保证了该问题解的对称性.此外,数值实验也证明了我们的新算法比二阶龙格库塔更精确.     

基于松弛策略解半无限规划模型的显式修正算法

讨论了一类线性半无限最优规划模型的求解算法.采用松弛方法解其系列子问题LP(T_k)及DLP(T_k),基于松弛策略和在适当的假设条件下,提出了一个我们称之为显式算法的新型算法.新算法的主要改进之处是算法在每一步迭代计算时,允许丢弃一些不必要的约束.在这种方式下,算法避免了求解系列太大规模的子问题.最后,基于提出的显式修正算法,并与传统割平面方法和已有文献中的松弛修正算法、对同一问题作了初步的数值比较实验.     

现代逻辑的一个规范化理论——一阶时态逻辑

一阶时态逻辑与程序语言理论中另外两门非常有用的逻辑——动态逻辑和Hoare逻辑它们之间到底有什么关系呢?本文的目的就是要解决这个问题.为此,我们首先拓广了时态算子的概念.与此同时,我们又提出了一种关于约束变元组的定义.这种关于约束变元的新的定义,使得某些现代逻辑学家心中的,关于变元组受约束的非形式化的约定,能够形式化地表达出来.随后,我们证实了:一阶时态逻辑具有一阶动态逻辑和Hoare逻辑的演算功能.再结合已知的事实:一阶时态逻辑具有一阶谓词逻辑、模态逻辑和(通常的)时态逻辑的演算功能.我们可以认为:一阶时态逻辑是这些现代逻辑的一个统一理论.由于我们能在一阶时态逻辑的一个形式系统里,同时进行上述的各种逻辑演算,因而一阶时态逻辑能成为一门很有前途的公理语义学.     

非精确信赖域类型算法及收敛性分析

在求解大规模数据的优化问题时,由于数据规模和维数较大,传统的算法效率较低.本文通过采用非精确梯度和非精确Hessian矩阵来降低计算成本,提出了非精确信赖域算法和非精确自适应三次正则化算法.在一定条件下,证明了算法有限步停止,并估计了算法迭代的复杂度.特别地,我们分析了采用随机抽样时算法在给定概率下的复杂度.最后,通过二分类问题的数值求解,比较了本文提出的随机信赖域算法,随机自适应三次正则化算法和已有算法收敛效率.数值结果表明在相同精度下,本文提出的算法效率更高,并且随机自适应三次正则化算法的效率优于随机信赖域算法.     

求解均衡问题的内部束方法

结合logarithmic二次函数和Lemar6chal和Wolfe(1975)提出的束方法,本文提出了一个求解非光滑均衡问题的束方法.一方面,我们算法推广了Nguyen等在文[1]中的束方法,并且保证了算法生成的序列在集合的内部.另一方面,将内部束方法应用到求解均衡问题.     

隐互补约束优化问题的磨光SQP算法

本文提出了一类隐互补约束优化问题的磨光SQP算法.首先,我们给出了这类优化问题的最优性和约束规范性条件.然后,在适当假设条件下,我们证明了算法具有全局收敛性.     

面向应急对地观测任务的多平台资源部署优化研究

提出了一种基于遗传算法的面向应急对地观测任务的多平台资源部署优化方法。该方法通过把观测区域离散化为网格点的集合,将多平台资源部署问题形式化为一个组合优化问题,其目标是在一定响应时间约束下最大化观测区域覆盖率。设计的求解算法采用整数编码表示各平台资源的部署位置,使用精英保留策略加快算法收敛速度。仿真结果表明,该方法能够快速获得满意的卫星、飞艇、无人机多平台资源部署方案。     

约束优化问题的一类光滑罚算法的全局收敛特性

对约束优化问题给出了一类光滑罚算法.它是基于一类光滑逼近精确罚函数 l_p(p\in(0,1]) 的光滑函数 L_p 而提出的.在非常弱的条件下, 建立了算法的一个摄动定理, 导出了算法的全局收敛性.特别地, 在广义Mangasarian-Fromovitz约束规范假设下, 证明了当 p=1 时, 算法经过有限步迭代后, 所有迭代点都是原问题的可行解; p\in(0,1) 时,算法经过有限迭代后, 所有迭代点都是原问题可行解集的内点.     

Lex M versus MCS-M

We study the problem of minimal triangulation of graphs. One of the first algorithms to solve this problem was Lex M, which was presented in 1976. A new algorithm, and a simplification of Lex M called MCS-M, was presented in 2002. In this paper we compare these two algorithms and show that they produce the same set of triangulations, answering an open question mentioned by the authors of MCS-M.     

Fixed-point algorithms for frequency estimation and structured low rank approximation

We develop fixed-point algorithms for the approximation of structured matrices with rank penalties. In particular we use these fixed-point algorithms for making approximations by sums of exponentials, i.e., frequency estimation. For the basic formulation of the fixed-point algorithm we show that it converges to the solution of a related minimization problem, namely the one obtained by replacing the original objective function with its convex envelope and keeping the structured matrix constraint unchanged.It often happens that this solution agrees with the solution to the original minimization problem, and we provide a simple criterion for when this is true. We also provide more general fixed-point algorithms that can be used to treat the problems of making weighted approximations by sums of exponentials given equally or unequally spaced sampling. We apply the method to the case of missing data, although the above mentioned convergence results do not hold in this case. However, it turns out that the method often gives perfect reconstruction (up to machine precision) in such cases. We also discuss multidimensional extensions, and illustrate how the proposed algorithms can be used to recover sums of exponentials in several variables, but when samples are available only along a curve.     

Polynomial Time Approximation Scheme for Two Parallel Machines Scheduling with a Common Due Date to Maximize Early Work

We study the scheduling problem with a common due date on two parallel identical machines and the total early work criterion. The problem is known to be NP-hard. We prove a few dominance properties of optimal solutions of this problem. Their proposal was inspired by the results of some auxiliary computational experiments. Test were performed with the dynamic programming algorithm and list algorithms. Then, we propose the polynomial time approximation scheme, based on structuring problem input. Moreover, we discuss the relationship between the early work criterion and the related late work criterion. We compare the computational complexity and approximability of scheduling problems with both mentioned objective functions.     

Heuristic algorithms for a complex parallel machine scheduling problem

In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows. This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given feasible solution of the problem. This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405.     

On a stopping rule for iterative orthogonalization of symmetric matrices

In this paper we consider three versions of Kovarik's iterative orthogonalization algorithms, for approximating the minimal norm solution of symmetric least squares problems. Although the convergence of these algorithms is linear, in practical applications we observed that a too big number of iterations can dramatically deteriorate the already obtained approximation. In this respect we analyse the above mentioned Kovarik–like methods according to the modifications they make on the “machine zero” eigenvalues of the problem (symmetric) matrix. We establish a theoretical almost optimal formula for the number of iterations necessary to obtain an enough accurate approximation, as well as to avoid the above mentioned troubles. Experiments on collocation discretization of a Fredholm first kind integral equation ilustrate the efficiency of our considerations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The min-Knapsack problem with compactness constraints and applications in statistics

In the min-Knapsack problem, one is given a set of items, each having a certain cost and weight. The objective is to select a subset with minimum cost, such that the sum of the weights is not smaller than a given constant. In this paper, we introduce an extension of the min-Knapsack problem with additional “compactness constraints” (mKPC), stating that selected items cannot lie too far apart. This extension has applications in statistics, including in algorithms for change-point detection in time series. We propose three solution methods for the mKPC. The first two methods use the same Mixed-Integer Programming (MIP) formulation but with two different approaches: passing the complete model with a quadratic number of constraints to a black-box MIP solver or dynamically separating the constraints using a branch-and-cut algorithm. Numerical experiments highlight the advantages of this dynamic separation. The third approach is a dynamic programming labelling algorithm. Finally, we focus on the particular case of the unit-cost mKPC (1c-mKPC), which has a specific interpretation in the context of the statistical applications mentioned above. We prove that the 1c-mKPC is solvable in polynomial time with a different ad-hoc dynamic programming algorithm. Experimental results show that this algorithm vastly outperforms both generic approaches for the mKPC and a simple greedy heuristic from the literature.     

Online time-constrained scheduling in linear and ring networks

We consider the problem of scheduling a sequence of packets over a linear network, where every packet has a source and a target, as well as a release time and a deadline by which it must arrive at its target. The model we consider is bufferless, where packets are not allowed to be buffered in nodes along their paths other than at their source. This model applies to optical networks where opto-electronic conversion is costly, and packets mostly travel through bufferless hops. The offline version of this problem was previously studied in M. Adler et al. (2002) [3]. In this paper we study the online version of the problem, where we are required to schedule the packets without knowledge of future packet arrivals. We use competitive analysis to evaluate the performance of our algorithms. We present the first online algorithms for several versions of the problem. For the problem of throughput maximization, where all packets have uniform weights, we give an algorithm with a logarithmic competitive ratio, and present some lower bounds. For other weight functions, we show algorithms that achieve optimal competitive ratios.     

Approximated algorithms for the minimum dilation triangulation problem

The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the sequential parameter optimization toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.     

Algorithms for nonexpansive self-mappings with application to the constrained multiple-set split convex feasibility fixed point problem in Hilbert spaces

In this article we devise two iteration schemes for approximating common fixed points of a finite family of nonexpansive mappings and establish the corresponding strong convergence theorem for the sequence generated by any one of our algorithms. Then we apply our results to approximate a solution of the so-called constrained multiple-set convex feasibility fixed point problem for firmly nonexpansive mappings which covers the multiple-set convex feasibility problem in the literature. In particular, our algorithms can be used to approximate the zero point problem of maximal monotone operators, and the equilibrium problem. Furthermore, the unique minimum norm solution can be obtained through our algorithms for each mentioned problem.