没有合适的资源?快使用搜索试试~ 我知道了~
--可在www.sciencedirect.com在线获取理论计算机科学电子笔记282(2012)35-45www.elsevier.com/locate/entcs一种集成图纸约束求解的工具AnaMar'ıaFernanumber-Soriano1JulioMarinumbero1A'ngelHerranz1amfernandez,jmarino,fi.upm.es巴别塔研究小组马德里理工大学西班牙马德里摘要电子表格已成为广泛使用的工具,但它们被应用于越来越复杂的问题,远远超出了它们最初设想的任务类型。 这往往会导致大, 很难维护表单,几乎不能保证它们的正确性。 潜在的错误是由于 部分原因是由于不熟练的用户以及电子表格系统自身的局限性。这一贡献提出了一个工具,旨在改善通常的工作流程时,填写电子表格。 的该工具集成了一个约束求解器,它基于单元格内容到有理数上的等式和不等式系统的变换。然后使用约束逻辑程序求解转换后的系统,并以可理解的方式将所获得的解决方案呈现给用户。这种基于约束逻辑编程的解决方案的实际好处之一是向后执行:我们的工具能够根据写在单元格中的聚合公式找到所需的输入值以达到所需的输出。同时,该约束模型也为单元公式中的循环引用问题关键词:电子表格,约束逻辑编程,约束求解,线性约束,编程环境,最终用户开发1引言最终用户开发(EUD)[5]这个术语是指那些允许非专业开发人员在没有编程语言知识的情况下创建或修改软件的环境Mash-up、Programming byExample(PbE)或图形化脚本语言1由马德里地区政府提供的MICINN赠款TIN 2009 -14599-C 03 -03(DESAFIOS10)和赠款S 2009 TIC-1465(PROMETIDOS-CM)部分支持的工作1571-0661 © 2011 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2011.12.00436上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)35≤≤这些工具中最古老的例子,当然也是最成功的是电子表格。其成功的一些原因是典型的:1。可用性:它们存在于大多数计算机的办公室套件2. ─ 即时反馈:在电子表格的一部分中所做的更改会立即反映在结果中,而无需传统软件系统所需的任何重组,重新编译或测试,以及3. 廉价的重用:电子表格中的片段可以很容易地与其他片段组合在一起,用户可以将在一个应用程序中学到的技能应用到另一个应用程序中,通常只是扩展一些电子表格。当然,EUD模式并非没有批评。重复合成、剪切粘贴和类比的结果可能是不可预测的,特别是考虑到以前很少有必须解决的问题的具体说明,并且不存在测试在电子表格的情况下,这导致了巨大的,难以维护和理解的工作表,但这些工作表通常负责组织某些部分的业务逻辑的关键功能事实上,普华永道(PWC)和毕马威(KPMG)等咨询公司的研究表明,某些领域95%的电子表格可能包含某种错误。错误的典型来源包括不相容数据之间的算术运算(例如,将码加到磅),用未定义单元格(错误地取为零)或单元格集合中的循环引用2(其由不同的电子表格系统以各种方式处理)操作虽然这些问题中的一些可以使用传统的编程技术来解决类型系统我们正在介绍的工具扩展了传统的电子表格模型,其中单元格内容要么是常数,要么是与其他单元格内容一起操作的结果,并有可能说明单元格内容之间的关系。这可以缓解上面的一些问题。例如,如果我们想添加一系列数量,并且有一个我们还不知道,那么我们很可能最终忘记它并最终将其视为零(即使它代表法拉利的价格)。与我们的建议,细胞可以被分配一个范围(例如150000A 5 240000),将被反映在求和与相应的范围。在许多系统中经常导致意外结果的细胞之间的相互关系想象一下,现在我们想添加几个项目的价格,但有些是美元,有些是欧元。我们可以将每一项放在不同的行中,并保留一列用于美元价格,下一列用于欧元价格。这意味着,最初,2细胞中直接或间接引用自身的表达。上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)3537Fig. 1. 发票的典型电子表格,包括金额、采购价格和折扣率几个项目。这些单元格中的唯一信息反映货币汇率。如果我们收到欧元的价格,那么我们可以更新右列中的单元格,并重新计算左列中的数量,从而减少无意中混合货币的可能性。图1显示了一个更详细的示例。所有产品的折扣率为10%发票的总价格为143,94e。想象一下,我们有一个总价格的约束140,00e,例如,由于营销原因。问题是重新计算适用于每种产品的折扣率。更重要的是,想象一下,我们不能将超过10%的产品应用于其中一种产品。如何重新计算剩余项目的折扣率?在传统的电子表格系统中,我们只能迭代地改变发票的不同值,以近似解决方案,但我们不能我们的工具在这个例子中的应用将在第5节中展示。我们的系统的工作原理是将单元格的内容翻译成一个逻辑程序编写的Prolog方言能够推理线性不等式的rational。第3节给出了细胞语言及其翻译的正式描述。约束逻辑编程(CLP)方法的一个优点是它允许对多个应用领域进行统一处理,因此这里为有理数提出的解决方案可以适用于解决组合问题。第2节讨论了允许这种通用性的框架。第4节概述了该工具以前曾有人提议扩展具有演绎能力的电子表格由于篇幅有限,读者可参考[4],以便对该领域进行快速调查。虽然构建我们自己的系统意味着要重新实现早期工具中的一些功能,但我们认为这一任务是值得的,因为它为我们提供了一个可扩展的平台,可以将这些想法应用于38上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)35LDD LDLD|↔ ∃JJD|∃∀→纸到更复杂的领域。2约束与逻辑编程有关参数约束逻辑编程框架(CLP(X))的正式、详细介绍,请参阅[3在下文中,CLP(X)代表逻辑编程的扩展,其中原子公式可以是用户定义的谓词对项元组的应用,也可以是以单独的一阶签名形式编写的新类别的公式(约束),并提供一阶结构作为标准解释。在合取和存在量化下是封闭的。对(,)被称为约束域,用于丰富主机逻辑编程语言,使其具有某些特定于域的智能,这些智能使用主机的标准演绎机制来实现是不够的。CLP()表示给定约束域传统的Prolog可以看作是一个实例CLP(Herbrand),其中的约束只是语法等式的条款。我们的原型中使用的实例称为CLP(Q),其中约束语言允许在有理域上解释线性不等式该框架的另一个成功实例是CLP(FD),其中的约束包括在整数的有限子集上解释的算术不等式为了在CLP语言中使用,约束域需要提供以下操作和约束检查i)一致性测试,D |ii)检查一个约束对另一个约束的含义,|= c→cJ; iii)将约束c投影到变量x的集合上,以便获得更简单的等价ntc:=cx100。c;以及iv)检测约束c强制其自由变量之一的单个值:为z.x,y= 0。c(x,y)x=z。在我们的电子表格模型中使用这些操作的可用性,以确保单元格集合的一致性,并且还计算向用户显示的单元格的可视化。3翻译函数的形式化描述翻译过程的主要特点是单元格引用在CLP程序中表示为逻辑变量,单元格内容在CLP程序中表示为约束。图2说明了转换的本质:我们展示了一对电子表格,它们被转换成CLP程序,以及它们的执行结果第一个例子ssA是一个标准的电子表格,每个单元格生成一个上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)3539电子表格CLP方案和解决方案?- { A1 = 14,B1 = 25,C1 = A1+ B1}。A1 = 14,B1 = 25,C1 = 39。?-?- { D3 = 100,D3 = 1.45* E3 }。D3 = 100.0,E3 = 68.9655?-∗SSA一BC11425A1+ B1SSBDE3100|D 3 = 1。45岁E3E3图二. 将电子表格转换为CLP程序等式约束,CLP求解器找到解。在第二个示例ssB中,单元格D 3包含表达式(100),但也对单元格E 3建立了约束:D 3 = 1。45 E3(完全可能是欧元兑美元的汇率单元格E3的值直接是E3,这是一种不建立其他约束的方法。在本例中,像元生成两个约束:D3 = 100和D3 = 1.45*E3,求解器找到E3的值我们将翻译过程正式描述为一个数学函数。在正式定义之前,我们需要一个带有约束的电子表格的正式模型,翻译函数的域,以及CLP程序的正式模型,它的共域。3.1约束条件下的图纸抽象图从概念上讲,电子表格是从单元格引用(表示行和列的自然数对)到单元格内容(涉及数字和单元格操作的有效表达式)的部分函数我们在图2中的例子ssA可以用一个类似的数学对象来表示:ssA={(1, 1)<$→14,(1, 2)<$→25,(1, 3)<$→(1, 1)+(1, 2)}其中(1,1)+(1,2)是单元格内容A1+B1的非正式表示我们对电子表格的正式表示是Address中的一个部分函数,自然数的笛卡尔积,转化为单元格内容:电子邮件地址地址=N×N细胞单元格内容有两个组件:表达式和约束。例如ssB遵循以下语法:单元格::= Expr [|Constr]其中方括号表示约束的可选性。没有任何40上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)35不单元格=Expr×ConstrExpr::=ExprQConstr::= T|ConstrConstr|ConstrQExprQ::=地址|Q|UnaexprQ|BinexprQUnaexprQ::= UnaopQ ExprQUnaopQ::= + |−BinexprQ::=ExprQBinopQExprQBinopQ::= + | − | ∗ |//下一页ConstrQ::=ExprQRelopQExprQ返回Q::==|<|>> |≤| ≥图三. 带约束的失去一般性,约束省略等价于一个平凡的约束(),所以我们假设约束总是存在的。图3显示了单元格内容的完整抽象语法3由于我们将重点关注有理数上的线性约束,因此图3中的约束的正式模型定义为Expr::=ExprQConstr::=. | ConstrQ其中,ExprQ是有理数的算术表达式,Constr是通过原子约束、将预定义约束应用于CLP(Q)项(ExprQ)或结合其他约束来构建的。然而,我们的形式化使人们能够轻松地扩展域的集合,例如,在有限域上添加约束:Expr::= ExprQ|快速ZConstr::=. |FDConstrZ|FDConstrZ本节开始时呈现的电子表格ssB将由以下数学对象表示:ssB={(3,4)<$→(100,(3,4)= 1. 45(3, 5)),(3, 5)<$→((3, 5),T)}3.2翻译功能我们将在本节中解释如何将电子表格转换为CLP程序。CLP程序的抽象语法,我们的工具,[3]出于可读性的考虑,我们以歧义语法的形式呈现这些成分上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)3541Prog=PClauseClause::=Atom:-Goal。目标::=点亮,...,Lit Lit::=原子|原子原子::= PS(术语,.,任期)PS::= globalcon|为|<|>>|......这是什么?术语:=变量|FS(术语,.,期限)变量::= A1|A2|B1|......这是什么?FS::= Q| +/1|-/1| +/2|-/2|*/2|//两个见图4。 CLP程序图五. 工具架构生成的定义见图4。生成的CLP程序只有一个子句,并同时在所有单元格上建立全局约束我们生成了一个名为globalcon的谓词,它将非空单元格与一个与该单元格的解相对应的唯一变量相关联,同时考虑到全局所有单元格中包含的信息翻译功能的完整定义可以在[1]中找到让我们展示一下前面例子的CLP程序:例如自动生成CLP程序SSAglobalcon([(1,1,A1),(1,2,B1),(1,3,C1)]):-{ A1 = 14,B1 = 25,C1 = A1 + B1}。SSBglobalcon([(3,4,D3),(3,5,E3)]):-{ D3 = 100,D3 = 1.45* E3}。42上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)35见图6。 AST UML类图。4工具架构在图5中,我们可以看到我们的应用程序有五个主要组件。让我们简单地描述一下每一个的功能。图形用户界面(GUI),一种电子表格外观,单元格以行和列的矩阵形式排列要填充一个单元格,用户只需点击它,然后按照扩展了约束的电子表格单元格内容的标准具体语法一旦用户填写单元格,“前端”组件就会处理电子表格中的“后端”组件生成CLP程序,该程序它遵循访问者模式的布局[2]。 最后,解决方案由“Presenter”组件解析该应用程序是用Java编写的,GUI使用Java Swing组件,前端已实现使用 JavaCC 和 Prolog 引 擎 使 用 Ciao Prolog 。 4 原 型 可 以 免 费 下 载(babel.ls.fi.upm.es/software/anatomicsolver)并进行测试。55使用该工具我们通过解决第1节中提到的两个例子来说明与我们的工具的交互。在发票的例子(图。(1)使用者应遵循4可查阅http://www.ciaohome.org。5其他示例可以在scenarios/目录下找到。上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)3543这些步骤:(i)而 不 是 迭 代 地 改 变 贴 现 率 直 到140。00e时,用户在E27:(ii)然后,用户从单元格B29中删除10%的折扣率,或者在其中键入以下内容:(iii)求解器计算出约束系统(单位折扣)D20 =B 20<$C 20<$B 29/ 100,(数量)E20 =B 20<$C 20−D 20,.E 27 = E 10 +. +E26,E27 = 140,B29 =B 29“欧元(i) 用户只要说明每种货币如何依赖于另一种货币的价值就足够了(允许循环引用,前提是不引入不一致):美元欧元3=1。小行星4501= D 3/1。4501(ii) 现在可以更改一列中的值,并在另一列中获得适当的货币,只需添加建立它的约束美元欧元3=1。小行星4501= D 3/1。4501 |E 3 = 2(iii) 得到以下答案:美元欧元3二、900226结论和今后的工作在本文中,我们提出了一个工具,探讨了约束求解器在电子表格应用程序的集成。对标准的微小扩展E27E 10 +... +E 26|东27 == 140B29乙二十九|真正B2912个。44上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)35电子表格语言以及与现有CLP环境的协调使我们的工具能够在存在不完整信息的情况下有效地进行计算我们已经应用这种能力,以克服现有的电子表格系统中的三个限制一方面,我们提出了一个简单而可靠的解决方案,如第5节所示的单元公式中的循环引用问题。此外,约束可以用来减轻空值带来的一些不便。最后,我们的方法允许在电子表格中解决目标优化问题,而不需要像图1中的例子那样通常采用试错法。我们可以提到为我们的原型计划的一些扩展• 其他约束域及其集成。这种改进一方面要求扩充抽象语法和具体语法;例如,为了引入有限域(CLP(FD)),我们需要扩展语法来表达区间和成员关系。这样的扩展将是有用的,例如,解决调度问题,尽管用户交互将稍微复杂一些,因为需要某种机制来遍历不同的解决方案此外,在同一表达式语法下混合不同域的情况下,类型系统将是强制性的,至少可以确保约束不会以潜在不一致的方式使用。• 提高可用性。为了简单起见,我们的原型允许编写一个约束,该约束在任何其他单元格的内容中约束任何单元格,并且我们还没有回答关于可用性的一些重要问题:我们应该允许每个单元格都有一组约束吗我们是否应该只允许一套全球性的约束?系统是否应该在单元格的结果内容中选择该单元格的任何约束来回答应用程序是否应该为用户输入保留一个单独的内容,为求解器的答案保留另一个内容?正确回答这些问题对于最终用户采用我们的建议至关重要。引用[1] Fern'anaen-Soriano,A. M.,“Una propuesta para la i n tegraci 'on de restriccionesen h o jas d e c' alculo,”Master's thesis,Uni v ersidad P oli t 'ecnica deMadrid(2010).[2] 伽马,E.,R.赫尔姆河Johnson和J. Vlissides,[3] Ja Zahar,J.和M. J. Maher,约束逻辑编程:一个调查,逻辑编程杂志19/20(1994年),pp。503-581[4] Kasso,M.和A. Valente,An Introduction to Logic Spreads。,Knowledge Eng. Review(2007),pp. 213-219上午Fernán-Soriano等人/理论计算机科学电子笔记282(2012)3545[5] Lie Berman,H.,F. 帕滕奥和W。Volker,编辑,“终端用户开发”,人机交互9,SpringerVerlag,2006年[6] Powell,S. G.,K. R. Baker和B. Lawson,对电子表格错误文献的批判性评论,Decis。支持系统46(2008),pp.128比138
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 电力电子系统建模与控制入门
- SQL数据库基础入门:发展历程与关键概念
- DC/DC变换器动态建模与控制方法解析
- 市***专有云IaaS服务:云主机与数据库解决方案
- 紫鸟数据魔方:跨境电商选品神器,助力爆款打造
- 电力电子技术:DC-DC变换器动态模型与控制
- 视觉与实用并重:跨境电商产品开发的六重价值策略
- VB.NET三层架构下的数据库应用程序开发
- 跨境电商产品开发:关键词策略与用户痛点挖掘
- VC-MFC数据库编程技巧与实现
- 亚马逊新品开发策略:选品与市场研究
- 数据库基础知识:从数据到Visual FoxPro应用
- 计算机专业实习经验与项目总结
- Sparkle家族轻量级加密与哈希:提升IoT设备数据安全性
- SQL数据库期末考试精选题与答案解析
- H3C规模数据融合:技术探讨与应用案例解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)