关键词： quasi-metric   complexity space   fixed point   improver   worsener   complexity class   Quicksort   Hanoi   Largetwo  

摘要： Schellekens [The Smyth completion: A common foundation for denotational semantics and complexity analysis, Electron. Notes Theor. Comput. Sci. 1 (1995), pp. 211-232.] introduced the theory of complexity (quasi-metric) spaces as a part of the development of a topological foundation for the asymptotic complexity analysis of programs and algorithms in 1995. The applicability of this theory to the asymptotic complexity analysis of divide and conquer algorithms was also illustrated by Schellekens in the same paper. In particular, he gave a new formal proof, based on the use of the Banach fixed-point theorem, of the well-known fact that the asymptotic upper bound of the average running time of computing of Mergesort belongs to the asymptotic complexity class of n log(2) n. Recently, Schellekens' method has been shown to be useful in yielding asymptotic upper bounds for a class of algorithms whose running time of computing leads to recurrence equations different from the divide and conquer ones reported in Cerda-Uguet et al. [The Baire partial quasi-metric space: A mathematical tool for the asymptotic complexity analysis in Computer Science, Theory Comput. Syst. 50 (2012), pp. 387-399.]. However, the variety of algorithms whose complexity can be analysed with this approach is not much larger than that of algorithms that can be analysed with the original Schellekens method. In this paper, on the one hand, we extend Schellekens' method in order to yield asymptotic upper bounds for a certain class of recursive algorithms whose running time of computing cannot be discussed following the techniques given by Cerda-Uguet et al. and, on the other hand, we improve the original Schellekens method by introducing a new fixed-point technique for providing, contrary to the case of the method introduced by Cerda-Uguet et al., lower asymptotic bounds of the running time of computing of the aforementioned algorithms and those studied by Cerda-Uguet et al. We illustrate and validate the dev

关键词： probit-based stochastic user equilibrium   elastic demand   asymmetric link travel time functions   variational inequality   computational algorithm  

摘要： This article addresses model development and computational algorithm design for the probit-based asymmetric stochastic user equilibrium (SUE) problem with elastic demand. Two variational inequality (VI) models are first proposed for the SUE problem and then existence and uniqueness of their solutions are examined. These two VI models are, in reality, built by means of a probit-based stochastic network loading (SNL) map. Since there is no computational procedure available for calculating the SNL map, we thus propose a two-stage Monte Carlo simulation-based method to estimate the SNL map. To compromise computational time with accuracy in the estimation, a lower bound of sample size required by the Monte Carlo simulation is also investigated. Based on these two VI models and Monte Carlo simulation-based method, we design two hybrid predictioncorrection (PC) cost averaging (CA) algorithms for solving the SUE problem. Finally, two numerical examples are carried out to assess performance of the proposed algorithms.

关键词： Buckyball   Graph algorithms   Dynamic programming   Greedy algorithm   Nanocomputational calculations  

摘要： Purpose - One of the significant underlying principles of nanorobotic systems deals with the understanding and conceptualization of their respective complex nanocomponents. This paper introduces a new methodology to compute a set of optimal electronic and mathematical properties of Buckyball nanoparticle using graph algorithms based on dynamic programming and greedy algorithm. Design/methodology/approach - Buckyball, C-60, is composed of sixty equivalent carbon atoms arranged as a highly symmetric hollow spherical cage in the form of a soccer ball. At first, Wiener, hyper-Wiener, Harary and reciprocal Wiener indices were computed using dynamic programming and presented them as: W(Buckyball) = 11870.4, WW(Buckyball) = 52570.9, Ha(Buckyball) = 1022 and RW(Buckyball) = 346.9. The polynomials of Buckyball, Hosoya and hyper-Hosoya, which are in relationship with Buckyball's indices, have also been computed. The relationships between Buckyball's indices and polynomials were then computed and demonstrated a good agreement with their mathematical equations. Also, a graph algorithm based on greedy algorithms was used to find some optimal electronic aspects of Buckyball's structure by computing the Minimum Weight Spanning Tree (MWST) of Buckyball. Findings - The computed MWST was indicated that for connecting sixty carbon atoms of Buckyball together: the minimum numbers of double bonds were 30;the minimum numbers of single bonds were 29;and the minimum numbers of electrons were 178. These results also had good agreement with the principles of the authors' used greedy algorithm. Originality/value - This paper has used the graph algorithms for computing the optimal electronic and mathematical properties of BB. It has focused on mathematical properties of BB including Wiener, hyper-Wiener, Harary and reciprocal Wiener indices as well as Hosoya and Hyper-Hosoya polynomials and computerized them with dynamic programming graph algorithms.

关键词： matrix bound   unified coupled algebraic Riccati equation   eigenvalue  

摘要： In this paper, combining the equivalent form of the unified coupled algebraic Riccati equation (UCARE) with the eigenvalue inequalities of a matrix's sum and product, using the properties of an M-matrix and its inverse matrix, we offer new lower and upper matrix bounds for the solution of the UCARE. Furthermore, applying the derived lower and upper matrix bounds and a fixed-point theorem, an existence uniqueness condition of the solution of the UCARE is proposed. Then, we propose a new fixed-point iterative algorithm for the solution of the UCARE. Finally, we present a corresponding numerical example to demonstrate the effectiveness of our results.

关键词： 算法初步   高中数学   算法教学  

摘要： 第八次课程改革实施已接近十年，课程设置发生了很多变化。其中数学由阶段性学习变为模块式学习，即分为必修和选修两部分。《普通高中课程标准（实验）》（以下简称《标准》）把“算法初步”作为一个新的内容列入了必修课程五个模块中的数学3。然而，通过查阅相关文献，调卷问卷分析发现目前高中在职数学教师对算法及算法教学的相关内容准备和掌握不是十分充分理想，学生接受程度并未达到标准要求，具体有体现如下： 1、吉林省实施新课改近5年,目前中学教师的算法教学素养总体不高，需要进一步加强和学习； 2、对于进行的算法教学，多数一线教师并未接触过，系统学过，准备尚不充分，需要时间对《标准》进行钻研，学习中国传统数学中的算法教学案例； 3、学生只是为了应付考试而单纯的学习算法内容，程序设计，编写框图只有少数人掌握； 4、教师在此方面的教学内容缺少与学生的系统交流分析，没有形成规范教学模式。 因此，可以看出算法教学作为新课程改革中新出现的内容，在现行的教学中并没有成熟的教学经验可以用来借鉴。为此，本文通过对一线教师及学生的调查和数据分析来探讨算法教学内容及教师的算法知识，希望对教师，学生都能够提供相应的帮助。 本文将从以下方面研究中学数学算法的教学及教师的算法知识： 1、以高中课程标准为依据研究人教A版数学必修3中的算法内容，与不同国家不同地区的算法内容作比较；通过阅读相关文献，并进行分析，借鉴其中算法教学先进的理念，探讨高中数学算法教学的方法、思想、内容及价值。 2、通过调查问卷的形式了解在职教师与学生对算法知识的理解程度，通过分析问卷和访谈内容，提出研究建议。 最后，提出本文的不足之处和对研究的展望。

关键词： abelian Lie subalgebra   abelian ideal   alpha invariant   beta invariant   algorithm  

摘要： In this paper, we show an algorithmic procedure to compute abelian subalgebras and ideals of finite-dimensional Lie algebras, starting from the non-zero brackets in its law. In order to implement this method, we use the symbolic computation package MAPLE 12. Moreover, we also give a brief computational study considering both the computing time and the memory used in the two main routines of the implementation. Finally, we determine the maximal dimension of abelian subalgebras and ideals for non-decomposable solvable non-nilpotent Lie algebras of dimension 6 over both the fields R and C, showing the differences between these fields.

关键词： 算法初步   高中数学新课程   算法思想   教学实践  

摘要： 算法是计算科学的重要基础,算法思想已经成为现代人应该具备的一种数学素养[1].众所周知,计算机在现代科技和社会生活中发挥着越来越大的作用,而算法恰恰是计算机得以运行的前提,所以算法的科学价值自然不言而喻.为了体现高中数学内容的与时俱进,"算法初步"被编进高中数学新课程,并被编写

关键词： 子公式权重   公式相关度   计算机代数系统(CAS)   排序算法  

摘要： 目前,Web中的数学信息量逐渐增加,数学搜索成为人们关注的焦点。近几年,浏览器对数学公式的显示和存储问题己得到逐步解决,为面向数学公式的搜索引擎的研究和开发提供了良好的基础。 尽管数学公式可以存储在web文档中,在网络中搜索数学公式仍具有局限性。数学公式具有复杂的二维结构以及蕴涵有复杂的数学表达意义,不同描述的数学公式可能具有相同的意义,同一数学公式的表示形式可能有多种,另外用户查询公式可能为某一公式的子公式,因此用传统的文本检索系统搜索数学公式显得力所不足。国际上现有的或者正在研究的数学公式检索系统,在建立索引方面已取得逐步发展,在返回结果集的排序算法方面大部分仍应用文本搜索引擎的排序算法,未深入研究面向数学公式搜索结果排序的算法。因此,本文将在深入研究现有的基于文本搜索引擎排序算法的原理和基础上,结合数学公式的特点以及数学公式间的关系(等价、代数相关、子公式等)尝试提出面向数学公式搜索排序的算法。本文将计算机代数系统(CAS)和数学公式搜索引擎相结合去挖掘公式与公式之间的关系,不但为查询公式和网页之间相关度的计算方面提供更加合理可靠的相关度量方法,还将促进系统对数学公式语义检索的能力。

关键词： 算法初步   高中数学   教科书使用  

摘要： 教科书作为教学活动的主要资源,直接影响师生的教学活动。普通高中新课程教科书从2004年投入使用以来,一直备受各界关注,为了了解高中新课程教科书的使用情况,发现其优缺点,2010年,受教育部委托,北京师范大学和西南大学“普通高中数学新课程数学教科书使用调研”课题组组织了国内近十所高校对北京市、重庆市、浙江省等十一个省(市)进行调研,在调研活动中发现新增内容“算法初步”的教学受到广泛关注,备受争议,为了进一步了解师生对算法初步内容的使用情况,笔者抽取了重庆市五所中学的36名教师和451名学生作为实验样本,对人教A版中算法初步内容的使用情况进行了调查,调查结论如下： 1.对于算法初步的内容编排,大多数的教师和学生对算法的编排感到满意； 2.教科书“算法初步”内容使用的具体情况及师生的建议：(1)大多数师生能够充分利用教科书中的教学资源进行日常的教学,使用最多的是教科书上的例题和习题；(2)大部分学生认为教科书上的内容偏难(如编程),相应的例题不够典型、比较难而不易理解,不能满足学生学习的需求；(3)使用较少的是阅读性材料,且师生之间存在差异,教师更注重旁注的使用,对于章末的阅读与思考栏目内容师生都不重视。对于“思考与讨论”和“探索与研究”栏目学生更喜欢后者；(4)师生建议：降低对编程的要求；增加一些典型的例题；尤其是实践操作题; 3.师生对算法知识的认识不够。 有相当一部分师生认为算法知识跟高中数学中其他知识点没有直接的联系,高考也只考一个知识点(程序框图),在生活中也用不到等,因此觉得算法知识对于高中的数学学习不太重要,有些甚至要求删除这部分内容。部分教师对算法的知识储备不足,以至这部分内容的教学成为教师教学的一大难点。 根据上述调查结论,笔者认为尽快修改算法章节的部分内容,加强教师培训,改善教学设备条件成为新课程改革的紧迫任务。

关键词： 算法   六模块教学法   Scilab   算法教学   教学设计   案例分析  

摘要： 算法初步是随着2009年课程改革在普通高中数学新课程必修教材《数学必修3》（人教B版）新增的一章内容，新课标要求本章内容要重视信息技术与算法课程内容的有机整合，利用程序Scilab通过模仿、操作、探索，经历通过设计程序框图、语句表达、上机操作解决问题的过程。对于笔者所在学校呼和浩特市回民中学，从2009年至今，面对生源处于本市中等偏差的水平以及教材的更新，传统的教学方式、方法难以适应现在的教育教学，也无法完全体现新课程的教育理念。为了改变这种状况，笔者所在学校通过与国内一些教学情况较好的学校的交流、学习，制定了校本研究课题——六模块教学法，并且由笔者承担了六模块教学法在高中数学学科的研究任务。由于算法内容是普通高中数学中出现的最新内容且对教师的要求较高，所以进行算法初步这章内容的六模块教学法研究更显得尤为迫切和必要。 本文从普通高中数学算法这一模块的课堂教学中结合Scilab程序应用对本人所在单位针对本校学生提出的六模块教学法作了理论与实践的研究与探索，充分证实了在课改背景下普通高中数学课堂运用六模块教学模式的可行性，对培养学生由被动厌学变为主动愿学有一定参考价值。全文共分四个部分。 第一部分绪论介绍了选题的背景、本研究的理论价值和实践意义及论文的总体设计。以及国内外算法相关课题的研究概况和文献综述，六模块教学法的综述。 第二部分对当前算法教与学情况的访谈调查及分析，包括研究的方法、对学生的访谈、对老师的访谈、访谈分析及对算法教学的启示。 第三部分利用六模块教学法对算法教学进行案例设计。通过对访谈中发现的算法教学问题进行分析，利用六模块教学法并借助Scilab对算法内容进行新的教学设计，以期对当下的算法教学有一定的借鉴意义。主要就三个方面进行具体的设计及分析，分别是:通过实例提高“循环结构”的教学有效性，从数学史的角度对古今中外一些算法间进行比较以及算法思想在其它模块教学中的体现。并通过访谈、调查、分析等方法对学生学习算法内容后的知识与技能掌握情况、情感态度与创新思维能力，以及六模块教学法的有效性加以总结。 第四部分小结，针对六模块教学法在实施过程中有待进一步思考、解决的问题以及发展趋势的估计作了简要的阐述。