论文部分内容阅读
分析了组合两种算法所需的空间复杂度在何种情况下为原算法的空间复杂度之和的问题,即空间复杂度的保持问题。通过形式化oracle查询方式,证明了在后续oracle查询和前面所有的oracle回复都不相关,即非适应性查询情况下,算法组合将保持空间复杂性,但在适应性查询情况时不一定成立。
保持空间复杂性的算法组合
【摘 要】
：
分析了组合两种算法所需的空间复杂度在何种情况下为原算法的空间复杂度之和的问题,即空间复杂度的保持问题。通过形式化oracle查询方式,证明了在后续oracle查询和前面所有的oracle回复都不相关,即非适应性查询情况下,算法组合将保持空间复杂性,但在适应性查询情况时不一定成立。
【机 构】
：
电子科技大学计算机科学与工程学院
【出 处】
：
计算机应用研究
【发表日期】
：
2010年06期
【基金项目】
：
国家“863”计划资助项目（2006AA01Z428）, 国家自然科学基金资助项目（60673075）
其他文献
引入移动sinks节点是解决网络连通性、能耗平衡、提高网络生命周期和网络容量的有效方法。针对移动sinks节点的移动机制直接与网络性能相关,结合mWSNs体系结构,分析了基于随机移动模型的网络性能,提出了零数据包分片率的随机移动模型。理论分析与仿真结果表明,该模型能够保证数据零分片,提高了网络的时延性能和数据包传输成功率。
为实现囊胚自动注射过程中的囊胚位姿信息获取,研究了一种基于视觉的囊胚检测及其内部结构识别的方法。首先用Hough变换和聚类方法检测圆,实现囊胚的位置定位;然后等扇区划分囊胚区域,统计各扇区灰度特征,判断发育成熟度;最后根据发育成熟囊胚中内细胞团区域平均灰度偏差最大的特点予以识别。实验结果显示,该方法对囊胚的检测和结构识别的正确率分别大于90%和80%,表明其在囊胚检测和内部特征结构识别中的有效性。
提出一种新的第三方双重图像水印算法。该算法依赖于可信任第三方提供的时间戳以及用户的私钥和授权码生成双重水印信息,然后将其嵌入在图像分块除直流分量外的DCT系数上。水印检测时可分别对水印作品时间戳和隶属关系的合法性进行检测。仿真实例和安全分析表明,该算法对嵌入参数敏感,对图像的常规操作具有较好的鲁棒性。在没有第三方的参与下,任何用户都不能构造和检测出合法的水印信息,这限制了恶意盗版者进行分析和攻击的
消化性溃疡(PU)是在消化内科比较常见的且发病率较高的疾病,主要发生在胃和十二指肠的慢性溃疡。秋冬和冬春之交为高发季节,男性患病率高于女性,多发于中老年。PU发病机理比
将Tian差值扩展技术应用于彩色图像中,提出一种利用预测误差差值进行扩展嵌入的彩色图像可逆数据隐藏算法。针对传统差值扩展技术存在过分修改像素灰度值、须嵌入定位图等缺点,首先利用色彩分量间的相关性减小差值,并将差值扩展量分散到两个色彩分量中;其次,对直方图平移技术进行改进,使得同等嵌入率下图像质量达到最佳;最后由两个色彩分量中像素的预测值之和决定可用于扩展嵌入的像素,无须保存溢出定位图,提取端在提取
慢性肾衰竭(CRF)是由于多种原因引起肾脏损害,表现为水电解质失衡、尿潴留等,严重者将会引起全身各系统受损,数据显示我国中老年人群慢性肾脏病患病率高达9.4%,影响患者生活
针对已有基于hash运算的RFID认证协议所面临的安全问题,提出了一种新的适合低成本RFID的双向认证协议,并与已有的协议进行安全性分析和性能比较。结果表明该协议仅使用hash函数和异或操作,就达到机密性、完整性和防追踪性的安全目标,并运用时间戳作为标签查询标志,提高认证过程的执行性能。因此该协议与先前工作相比,更适合低成本的RFID系统。
为了在降低计算复杂度的同时获得良好的性能,给出了一种基于离散粒子群优化的多用户MIMO用户选择方法。该方法基于sum-MSE预编码,所支持的用户数目取决于接收方的子流数之和,改变了传统的用户选择方法支持的用户接收天线数之和不大于发送天线数的限制。当移动台子流个数小于接收天线数时,所研究的用户选择方法可以增加同时服务的用户个数,获得更高的系统和容量。仿真结果表明,该方法能够在系统性能和复杂度之间进行
提出了一种量子代理签名方案,利用量子力学中Einstein-Podolsky-Rosen(EPR)的纠缠特性并结合经典编码方法来实现对量子比特串的签名和验证。在本方案中,原始签名人可以将自己的签名权委托给代理签名人,而量子密钥分配和一次一密保证了新方案的无条件安全性。研究表明新方案满足不可伪造性、不可否认性和可追踪性。