检索结果-内蒙古大学图书馆

10th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Chen, Wei Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

ISBN: (纸本)9783642133206

Puzzles and games have been used for centuries to nurture problem-solving skills. Although often presented as isolated brain-teasers, the desire to know how to win makes games ideal examples for teaching algorithmic problem solving. With this in mind, this paper explores one-person solitaire-like games. The key to understanding solutions to solitaire-like games is the identification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a collection of novel one-person games. The known classification of states of the game of (peg) solitaire into 16 equivalence classes is used to introduce the relevance of polynomial arithmetic. Then we give a novel algebraic formulation of the solution to a class of tiling problems. Finally, we introduce an infinite class of challenging one-person games inspired by earlier work by Chen and Backhouse on the relation between cyclotomic polynomials and generalisations of the seven-trees-in-one type isomorphism. We show how to derive algorithms to solve these games.

关键词： Solitaire invariants tiling problems polynomials games on cyclotomic polynomials seven-trees-in-one nuclear pennies algorithm derivation

来源：评论

学校读者我要写书评

暂无评论

On Euclid's algorithm and elementary number theory

On Euclid's algorithm and elementary number theory

引用

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

algorithms can be used to prove and to discover new theorems. This paper shows how algorithmic skills in general, and the notion of invariance in particular, can be used to derive many results from Euclid's algorithm. We illustrate how to use the algorithm as a verification interface (i.e., how to verify theorems) and as a construction interface (i.e., how to investigate and derive new theorems). The theorems that we verify are well-known and most of them are included in standard number-theory books. The new results concern distributivity properties of the greatest common divisor and a new algorithm for efficiently enumerating the positive rationals in two different ways. One way is known and is due to Moshe Newman. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm. A short review of the original papers by Stern and Brocot is also included. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.

关键词： Number theory Calculational method Greatest common divisor Euclid's algorithm Invariant Eisenstein array Eisenstein-Stern tree (aka Calkin-Wilf tree) Stern-Brocot tree algorithm derivation Enumeration algorithm Rational number

来源：评论

学校读者我要写书评

暂无评论

Designing an algorithmic Proof of the Two-Squares Theorem

Designing an Algorithmic Proof of the Two-Squares Theorem

引用

10th International Conference on Mathematics of Program Construction

作者： Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

ISBN: (纸本)9783642133206

We show a new and constructive proof of the two-squares theorem, based on a somewhat unusual, but very effective, way of rewriting the so-called extended Euclid's algorithm. Rather than simply verifying the result as it is usually done in the mathematical community we use Euclid's algorithm as an interface to investigate which numbers can be written as sums of two positive squares. The precise formulation of the problem as an algorithmic problem is the key, since it allows us to use algorithmic techniques and to avoid guessing. The notion of invariance, in particular, plays a central role in our development: it is used initially to observe that Euclid's algorithm can actually be used to represent a given number as a sum of two positive squares, and then it is used throughout the argument to prove other relevant properties. We also show how the use of program inversion techniques can make mathematical arguments more precise.

关键词： algorithm derivation sum of two squares Euclid's algorithm invariant program inversion

来源：评论

学校读者我要写书评

暂无评论

The capacity-C torch problem

The capacity-<i>C</i> torch problem

引用

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

ISBN: (纸本)9783540705932

The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four people and the capacity of the bridge is two is a well-known puzzle, widely publicised on the internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present an algorithm that determines the shortest total crossing time;the number of primitive computations executed by the algorithm (i.e. the worst-case time complexity of the algorithm) is proportional to the square of the number of people.

关键词： algorithm derivation shortest path dynamic programming algorithmic problem solving

来源：评论

学校读者我要写书评

暂无评论

The algorithmics of solitaire-like games

The algorithmics of solitaire-like games

引用

10th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Chen, Wei Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

One-person solitaire-like games are explored with a view to using them in teaching algorithmic problem solving. The key to understanding solutions to such games is the identification of invariant properties of polynomial arithmetic. We demonstrate this via three case studies: solitaire itself, tiling problems and a novel class of one-person games. The known classification of states of the game of (peg) solitaire into 16 equivalence classes is used to introduce the relevance of polynomial arithmetic. Then we give a novel algebraic formulation of the solution to a class of tiling problems. Finally, we introduce an infinite class of challenging one-person games, which we call "replacement-set games", inspired by earlier work by Chen and Backhouse on the relation between cyclotomic polynomials and generalisations of the seven-trees-in-one type isomorphism. We present an algorithm to solve arbitrary instances of replacement-set games and we show various ways of constructing infinite (solvable) classes of replacement-set games. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Solitaire Tiling problems Cyclotomic polynomials Cyclotomic game Replacement-set game Seven-trees-in-one algorithm derivation Invariants Type isomorphism

来源：评论

学校读者我要写书评

暂无评论

Recounting the rationals: Twice!

Recounting the rationals: Twice!

引用

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

ISBN: (纸本)9783540705932

We derive an algorithm that enables the rationals to be efficiently enumerated in two different ways. One way is known and is credited to Moshe Newman;it corresponds to a deforestation of the so-called Calkin-Wilf tree of rationals. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm.

关键词： Calkin-Wilf tree Stern-Brocot tree algorithm derivation enumeration algorithm rational numbers

来源：评论

学校读者我要写书评

暂无评论

Parallelization with tree skeletons

Parallelization with tree skeletons

引用

9th International Euro-Par Conference on Parallel Processing

作者： Matsuzaki, K Hu, ZJ Takeichi, M Univ Tokyo Grad Sch Informat Sci & Technol Tokyo Japan

ISBN: (纸本)354040788X

Trees are useful data structures, but to design efficient parallel programs over trees is known to be more difficult than to do over lists. Although several important tree skeletons have been proposed to simplify parallel programming on trees, few studies have been reported on how to systematically use them in solving practical problems;it is neither clear how to make a good combination of skeletons to solve a given problem, nor obvious even how to find suitable operators used in a single skeleton. In this paper, we report our first attempt to resolve these problems, proposing. two important transformations, the tree diffusion transformation and the tree context preservation transformation. The tree diffusion transformation allows one to use familiar recursive definitions to develop his parallel programs, while the tree context preservation transformation shows how to derive associative operators that are required when using tree skeletons. We illustrate our approach by deriving an efficient parallel program for solving a nontrivial problem called the party planning problem, the tree version of the famous maximum-weight-sum problem.

关键词： parallel skeletons tree algorithms parallelization program transformation algorithm derivation

来源：评论

学校读者我要写书评

暂无评论

Toward interactive statistical modeling

引用

Procedia Computer Science 2010年第1期1卷 1835-1844页

作者： Sooraj Bhat Ashish Agarwal Alexander Gray Richard Vuduc College of Computing Georgia Institute of Technology Atlanta GA Department of Computer Science Yale University New Haven CT

When solving machine learning problems, there is currently little automated support for easily experimenting with alternative statistical models or solution strategies. This is because this activity often requires expertise from several different fields (e.g., statistics, optimization, linear algebra), and the level of formalism required for automation is much higher than for a human solving problems on paper. We present a system toward addressing these issues, which we achieve by (1) formalizing a type theory for probability and optimization, and (2) providing an interactive rewrite system for applying problem reformulation theorems. Automating solution strategies this way enables not only manual experimentation but also higher-level, automated activities, such as autotuning.

关键词： Machine learning algorithm derivation Interactive modeling Type theory

来源：评论

学校读者我要写书评

暂无评论

Problem Reduction Graph Model for Discrete Optimization Problems

Problem Reduction Graph Model for Discrete Optimization Prob...

引用

The Third International Joint Conference on Computational Science and Optimization(第三届计算科学与优化国际大会 CSO 2010)

作者： Yujun Zheng Jinyun Xue State Key Lab of Computer Science Institute of SoftwareChinese Academy of SciencesBeijingChina Pr State Key Lab of Computer Science Institute of SoftwareChinese Academy of SciencesBeijingChina Pr

The paper proposes the problem reduction graph (PRG), an abstract model for discrete optimization problems which uses structural decomposition to reduce problem complexity and constructs the recurrence relations between the problem and its subproblems. We develop several important algorithm patterns for PRG construction, each leading to a special class of concrete problem-solving algorithms in a systematic way. The model supports logical transformation from specifications to algorithmic programs by deductive inference, and thus significantly promotes the automation and reusability of algorithm design.

关键词： combinatorial optimization problem reduction graph (PRG) algorithm derivation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：