检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

算法复杂性平滑分析的研究进展与展望

计算机研究与发展 2005年第2期42卷 286-293页

作者：杨智应朱洪雷向欣上海海事大学计算机科学与技术系上海200135 复旦大学计算机科学与工程系上海200433 复旦大学计算机与信息技术系上海200433

有很多算法其最坏情况复杂性很坏 (甚至是指数阶的 ) ,但在实际应用中却很有效其中一个典型代表就是求解线性规划问题的单纯形算法最近 ,Spielman和Teng提出了算法的平滑复杂性概念及算法复杂性平滑分析方法 ,对上述矛盾给出了合理... 详细信息

有很多算法其最坏情况复杂性很坏 (甚至是指数阶的 ) ,但在实际应用中却很有效其中一个典型代表就是求解线性规划问题的单纯形算法最近 ,Spielman和Teng提出了算法的平滑复杂性概念及算法复杂性平滑分析方法 ,对上述矛盾给出了合理的解释 ,在理论计算机科学界引起了极大的关注为此 ,做了以下工作 :介绍算法复杂性平滑分析的基本概念 ;介绍两年多来算法复杂性平滑分析主要的研究进展 ;从实际应用出发提出一个更合乎算法复杂性平滑分析思想的随机扰动模型 (简称TSSP模型 ) ,克服“PartialPermutation”随机扰动模型的不足 ,并证明在TSSP模型下快速排序算法的时间平滑复杂性为O(2λn×log2 (n) ) ,其中λ是随机扰动幅度大小最后。

关键词：平滑分析平滑复杂性 TSSP模型 k-邻域

在线全文

学校读者我要写书评

暂无评论

基于0-保留扰动的高斯算法平滑复杂度分析

软件学报 2006年第10期17卷 2057-2062页

作者：杨智应雷向欣朱洪上海海事大学计算机科学与工程系上海200135 华东理工大学计算机科学与工程系上海200237 复旦大学计算机科学与工程系上海200433

算法的平滑复杂度能够更合理地反映算法的实际性能.在运行高斯算法求解线性系统过程中,矩阵条件数是导致求解误差偏大的一个因素.Sankar等人用0-保留高斯扰动进行对称矩阵条件数平滑分析.然而,Sankar等人给出的平滑复杂度过高而且复杂.... 详细信息

算法的平滑复杂度能够更合理地反映算法的实际性能.在运行高斯算法求解线性系统过程中,矩阵条件数是导致求解误差偏大的一个因素.Sankar等人用0-保留高斯扰动进行对称矩阵条件数平滑分析.然而,Sankar等人给出的平滑复杂度过高而且复杂.为了解决这个问题,首先提出了两个关键的不等式;然后将这两个不等式用于对称矩阵条件数的平滑分析,得到更简单、更低的平滑复杂度;并利用该结果对高斯算法求解精度进行平滑分析,从而得到更低的平滑复杂度.

关键词：平滑复杂度 0-保留扰动矩阵条件数对称矩阵

在线全文

学校读者我要写书评

暂无评论

统计分析在系统级故障诊断中的应用

计算机应用与软件 2001年第10期18卷 58-60页

作者：杨智应广东嘉应教育学院计算机教育系梅州514071

本文探讨统计分析在系统级故障诊断中的应用,提出两个概率诊断模型,讨论了给出的两个模型的测试算法及有关测试数据的统计推断。

关键词：概率诊断序贯分析统计分析系统级故障诊断计算机

在线全文

学校读者我要写书评

暂无评论

一种基于速度的移动对象轨迹简化算法

计算机应用研究 2018年第9期35卷 2666-2670页

作者：杨彪杨智应上海海事大学信息工程学院上海201306

目前对移动对象轨迹简化问题分为离线简化和在线简化。以往的简化方法中许多依赖轨迹的几何特性,而针对移动对象的速度这一重要特征没有足够关注。基于速度研究移动对象轨迹的离线简化新方法,提出了移动对象轨迹离线简化的动态规划算法... 详细信息

目前对移动对象轨迹简化问题分为离线简化和在线简化。以往的简化方法中许多依赖轨迹的几何特性,而针对移动对象的速度这一重要特征没有足够关注。基于速度研究移动对象轨迹的离线简化新方法,提出了移动对象轨迹离线简化的动态规划算法、基于广度优先搜索的轨迹简化算法及其优化算法、时间复杂度更低的近似算法。通过大量实验验证所提出的算法比基于方向的简化算法和基于位置的简化算法具有更好的简化效率。

关键词：移动对象离线轨迹简化速度阈值近似算法

在线全文

学校读者我要写书评

暂无评论

基于PLAZA的移动对象轨迹实时化简方法

计算机应用研究 2014年第5期31卷 1316-1319,1348页

作者：王欣然杨智应上海海事大学信息工程学院计算机系上海201306

为了设计更为简洁高效的实时轨迹化简算法,在PLAZA算法的基础上,给出适合移动对象轨迹化简的分区角度概念,并利用移动对象的瞬时速度等实时位置信息,在距离和方向两个层面上对误差进行控制。通过融合区域过滤的思想,构造限制插值点误差... 详细信息

为了设计更为简洁高效的实时轨迹化简算法,在PLAZA算法的基础上,给出适合移动对象轨迹化简的分区角度概念,并利用移动对象的瞬时速度等实时位置信息,在距离和方向两个层面上对误差进行控制。通过融合区域过滤的思想,构造限制插值点误差范围的安全区域,设计出了针对移动对象实时位置信息进行化简的新算法NPLAZA。实验结果证明,算法NPLAZA误差小,轨迹化简高效、稳定。

关键词：移动对象轨迹化简 PLAZA算法区域过滤实时化简

在线全文

学校读者我要写书评

暂无评论

基于分段的移动对象轨迹简化算法

计算机应用研究 2019年第7期36卷 2044-2048页

作者：张甜杨智应上海海事大学信息工程学院

GPS的高采样率使轨迹的数据规模巨大,在实际应用中难以处理,需要依赖轨迹简化算法对原始数据进行压缩。针对此问题,提出了一种新的基于速度分段的轨迹简化算法,即STS算法,在保留速度特征的同时保留了给定轨迹的时空特征。STS算法将速度... 详细信息

GPS的高采样率使轨迹的数据规模巨大,在实际应用中难以处理,需要依赖轨迹简化算法对原始数据进行压缩。针对此问题,提出了一种新的基于速度分段的轨迹简化算法,即STS算法,在保留速度特征的同时保留了给定轨迹的时空特征。STS算法将速度值分组成若干间隔,将轨迹分割成速度保留段,计算各轨迹段的SED阈值,通过在每个子轨迹段上应用TD-TR算法导出简化的轨迹。通过真实的数据集进行广泛实验,验证所提出的算法比ATS算法具有更好的性能。

关键词：移动对象轮廓系数 TD-TR算法分类回归决策树轨迹简化

在线全文

学校读者我要写书评

暂无评论

在线调度算法的延迟竞争比分析

广西师范大学学报（自然科学版） 2008年第2期26卷 93-96页

作者：杨智应上海海事大学信息工程学院上海200135

讨论了在无抢占无迁移的在线环境下算法AAIMD的性能。采用平均延迟作为度量调度策略优劣的标准,并证实了在允许最优离线对手有作业抢占和迁移的环境下,算法AAIMD仍具有常数竞争比。

关键词：流动时间延迟平均延迟在线调度算法AAIMD

在线全文

学校读者我要写书评

暂无评论

矩阵条件数及高斯算法平滑分析的进一步研究

软件学报 2004年第5期15卷 650-659页

作者：杨智应朱洪宋建涛复旦大学计算机科学与工程系上海200433 复旦大学智能信息处理实验室上海200433

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算... 详细信息

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n3).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设A为任意矩阵,A是A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差12s.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了()saanAK)log(413.64])(Pr[+.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为7.loglog)(1/3log)(7log2222++++nnms在上述结果的证明过程中存在错误,将其纠正后得到以下结果:7.367.)/1(loglog24)(1/3log7log2222++++++ssnnm通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到saa226])(Pr[nAK.部分地解决了Sankar等人提出?

关键词：平滑复杂度矩阵条件数矩阵增长因子平滑精度

在线全文

学校读者我要写书评

暂无评论

XML数据流分页频繁子树挖掘研究

计算机研究与发展 2012年第9期49卷 1926-1936页

作者：雷向欣杨智应黄少寅胡运发华东理工大学计算机科学与工程系上海200237 上海海事大学计算机科学与技术系上海200135 北京大学光华管理学院北京100871 复旦大学计算机科学技术学院上海200433

随着XML数据流的广泛应用,从挖掘XML数据流中发现知识具有重要的理论与应用价值.相比其他频繁模式挖掘,大型XML文档与数据流的频繁子树挖掘面临困难:XML数据流不可能整体在内存解析;对XML数据流分段挖掘必须考虑XML数据的半结构化特征等... 详细信息

随着XML数据流的广泛应用,从挖掘XML数据流中发现知识具有重要的理论与应用价值.相比其他频繁模式挖掘,大型XML文档与数据流的频繁子树挖掘面临困难:XML数据流不可能整体在内存解析;对XML数据流分段挖掘必须考虑XML数据的半结构化特征等.针对上述问题,提出数据流分页频繁子树挖掘模型Tmlist.Tmlist对XML数据流进行分页,管理跨页节点及频繁候选子树的跨页增长,逐页挖掘频繁子树;频繁候选子树的增长根据根节点层次由浅至深地在最右路径加入频繁候选节点,避免以低层次为根子树的重复性递归增长;对频繁候选子树采用子树拓扑序列和最右路径共同标识,子树的增长不需要对子树前缀进行匹配,省去前缀节点存储与匹配开销;以页面最小支持度对频繁候选子树按页筛选,子树按页面衰减度衰减支持度、剪枝.Tmlist在可控误差范围内降低频繁子树挖掘的空间消耗,提高内存利用率和挖掘效率.

关键词： XML 数据流分页频繁子树数据挖掘