算法基础（精选6篇）
算法基础 篇1
随着多媒体技术和网络技术的迅猛发展及广泛应用, 对数字媒体的保护已经成为一个迫在眉睫的问题, 尤其是对数字图像的保护。由于传统加密方法对多媒体内容保护能力有限, 因此一种新的保护途径应运而生, 即数字水印技术。虽然已经出现了许多对常见的信号处理稳健的数字水印算法, 但是非常微小的几何攻击都能够使这些水印失效。奇异值分解 (SVD) 的图像数字水印算法对放大、旋转等几何攻击以及对剪切攻击是稳健的是稳健的。
数字图像的奇异值分解。数值分析中的奇异值分解 (SVD) 是一种将矩阵对角化的数值算法。在图像处理中应用的主要理论背景是: (1) 图像奇异值的稳定性非常好, 当图像被施加小的扰动时, 图像的奇异值不会有大的变化; (2) 奇异值所表现的是图像的代数特性。
从线性代数的角度看, 一幅数字图像可以看成是一个非负矩阵。用A∈Rm×n来表示这样一个图像矩阵, 其中R表示实数域。矩阵A的奇异值分解如下:A=UDVT
其中都是正交矩阵, 是A或AT的奇异值, 其中R是A的秩, 是AAT或ATA特征值的平方根。U、V分别是A的左奇异向量和右奇异向量。因为
所以U的列向量是AAT的特征向量, V的列向量是ATA的列向量, 并且它们所对应的特征值都是A的奇异值的平方。
基于HVS的图像块分类。根据HVS的特性, 人眼对不同类型图像区域的敏感程度依次为:对图像平滑区域的噪声最敏感;对图像的边缘信息较为敏感;对纹理区域的噪声不敏感。根据这个特性, 我们希望在图像的纹理区域进行水印的嵌入。文献基于图像块的灰度均值、熵和方差等统计特性将图像块进行划分。
图像处理与信息论的相关理论表明, 方差反应各像素灰度值与图像平均灰度值的总的离散程度, 而熵则表征图像所含信息的多少, 图像纹理区域熵值较大而方差较小。在这里, 我们引入, 其中H表示熵, 为标准差, 显然熵值越大, 方差越小, T值越大。通过引入T值, 我们在对图像的各分块进行比较时, 就不必对方差和熵值分别进行比较, 而统一对T值大小比较即可, 这样对于各分块的比较变得简单明了, 同时也利于程序的编写。
水印的嵌入与提取。算法步骤如下:水印嵌入:首先将图像进行分块, 计算每块图像的T值, 选取T值最大的块, 进行奇异值分解, 将水印嵌入到进行奇异值分解的图像块中。方法如下:水印是由服从高斯分布的实数序列组成, 其中Wi相互独立, n为水印的长度。挑选出除了d1以外的n个数值最大的奇异值组成的单调递减序列, 之所以排除d1是因为d1远远大于其它的奇异值。对d1的改变会导致图像质量的下降。根据将水印w嵌入到S中, 得到一个嵌入后的奇异值序列。其中
a是一个比例参数, 用来调节w改变S的程度, 从而控制嵌入水印后的图像质量。将S'回代入D中, 生成D', 然后再UD'VT就得到嵌入水印后的图像块A'。由于调整后的奇异值序列可能不符合单调递减的顺序, 而在奇异值分解后奇异值总是递减排列的, 所以根据d'i的递减顺序对S中对应的di排序, 生成序列。用它来标明A的奇异值及其原始顺序。用它来标明A的奇异值及其原始顺序。
提取水印时需要:嵌入水印的图像 (可能已经遭受到攻击) 、参考水印w、奇异值序列和比例参数a。
将进行分块, 确定原先嵌入水印的图像块, 设为A*, 并从中提取出可能已遭到破坏的水印w*并进行检测:
(1) A*进行奇异值分解, 得到按递减顺序排列的奇异值向量D*。
(2) 将按单调递减顺序排列, 还原成。
(3) 根据S和, 使D*中的奇异值与S的相应元素对齐, 并从中D*提取出奇异值序列。
(4) 提取水印。
(5) 计算标准相关系数:
利用corr2 (w, w*) 来测量w与w*相似程度。
实验结果:我们使用256级灰度图像Lena.bmp为例, 来测试本水印算法对各种几何攻击的稳健程度。Lena.bmp的大小为256×256, 先将图像进行64×64分块, 再嵌入水印。本文只给出算法对放大、旋转等几何攻击以及对剪切攻击的结果。
分块的大小为64×64, 取水印长度N=50。实验结果如下:原图像 (图1) 。
未攻击时, 在原图像的下半部分加入水印, a=0.3, 图像为 (图2) 。
当a=0.3时, 峰值信噪比psnr=46.9693;
从上面各幅图像中提取的水印并给出相关系数r=0.9991
下面我们对嵌入水印的图像施加各种攻击
旋转90度, a=0.3, 相关系数r=0.9991
横向拉伸2倍, a=0.3, 相关系数r=0.9991
纵向拉伸2倍, a=0.3, 相关系数r=0.9991
可见本文的算法对常见的几何攻击是非常稳健的。经过几何攻击后的图像可以非常稳健的提取水印。
现在我们施加其他攻击:
裁减左半幅图像, a=0.3, 从中提取的水印与原始水印的相关系数r=0.9991
裁减下半幅图像, a=0.3, 从中提取的水印与原始水印的相关系数r=0
实验结果表明, 本文算法对剪切有一定的抵抗性, 关键是剪切的位置, 若把嵌入水印的图像块剪切掉, 那不能提取出水印;若没有剪切掉嵌入水印的块, 则可以非常稳定的提取出水印。
本文提出了一种能够抵抗一般几何攻击的数字水印算法, 由服从高斯分布的随机数组成的水印被嵌入到数字图像的奇异值之上, 并考虑到人类视觉系统特性的影响, 引入了基于统计量熵值和方差的参数T, 作为我们划分不同种类块的标准。实验结果表明本水印算法对这些几何攻击具有很好的稳定性。
摘要：本文提出了一种利用奇异值分解的图像数字水印算法, 针对的是在水印提取之前遭受了未知几何攻击的图像。实验结果表明, 本文的算法对放大、旋转等几何攻击以及对剪切, 噪声攻击是稳健的, 而且此水印在受到了上述的几何攻击后仍能够被有效的提取。
关键词：奇异值分解,数字水印,几何攻击
参考文献
[1]刘瑞祯, 谭铁牛.基于奇异值分解的数字图像水印方法[J].电子学报, 2001, 29 (2) :pp.168~171.
[2][美]G..H.戈卢布C.F范洛恩[J]《.矩阵计算》, 8.1&8.6.
[3]阮秋奇.数字图像处理学[M].电子工业出版社.
算法基础 篇2
关键词：计算机软件,基础数据结构,算法分析,复杂度
1 算法的概述
1.1 算法两要素
算法主要包括两部分:信息的处理操作和信息处理方式的操作结构, 对信息的处理操作一般包括逻辑符号、数学计算、信息传递和信息对比, 操作结构可以指引指令有序进行, 通常用流程图来描述。
1.2 算法的主要特征
有限指令的主要部分就是算法, 有限指令能够明确处理问题的步骤。面对问题, 算法能够对各种定值指令进行预算处理, 通过运算传达最后的计算结果。算法的特点主要为:指令的数量必须有限;指令不能超出计算机的能力范围;被处理的对象不受指令影响, 对象数量不影响指令, 必须要有至少一个传递末端。
1.3 算法表示方法
目前编译算法一般都用符号和文字来进行, 主要包括程序图、C语言、PAD图, 一般性文字等。C语言和一般性文字能够具体详细的描述算法, 其他方法描述算法是大致内容并进行作图, 更加直观的表达, 便于学习理解。
1.4 常用的算法
常用的算法主要包括枚举法、迭代法、递推和递归法。枚举法内容是指通过信息特点对运行结果的可能区域进行估计, 然后利用一些方法手段检查各个结果, 直到所有结果都符合。在验证过程中, 验证对象如果满足算法要求, 这个验证对象就是最终计算机传递的结果, 如果没有达到要求的对象, 那么算法就无解。迭代法是一种较为粗略的方法, 可以把麻烦复杂的问题转化为较为简单的迭代式子, 通过循环这个步骤, 达到由繁化简并最终得出答案的目的, 该法适合非数值类问题的计算。递推法和递归法是主要的算法制定编写法, 都通过运用特殊公式逐项推导而来的。
2 算法设计要求
算法像语言一样, 是计算机和人类沟通时的语言, 通过算法, 人们不仅可以跟计算机进行交流, 还可以按照指令执行任务。因此所有的指令必须要符合一定的行为准则, 算法的设计要求主要包括以下几点:
2.1 具有正确性
设计者编译指令时必须要按照算法的规则来进行, 从而保证人和计算机正确的交流, 保证计算机执行好任务。正确性中最重要的就是避免语法错误的出现, 从而能够为正确答案的得出做好准备。
2.2 具有可读性
算法具有可持续性, 是指算法总体思路容易让人理解, 是想一下, 一个非常混乱的算法, 即使再聪明的人也很难明白算法原理的, 更不用说得出计算机答案。
2.3 具有稳定性
就像机械设备似的, 如果工作状态不稳定, 那么就会很容易出现难懂奇怪的问题, 算法如果不够稳定, 计算机在正常运行的时候, 也会很容易出现错误。经常出现的错误就是乱码, 就会让人感觉像是算法存在严重问题。
2.4 具有高效低耗的性能
计算机性能的好坏取决于内部的器件好坏, 算法也是这样的。好算法可以用最低能耗最短时间来得出答案, 计算机内部的工作原理可以决定这些因素, 其中最主要的就是存储大小和运算速度的联系。
3 算法复杂度的分析
算法复杂度决定了一个算法执行并得出结果需要的总时间, 设计者通常是根据算法复杂度来判断对算法的总效率来进行判断的, 这是因为时间的消耗和算法需要的内存情况是直接联系挂钩的。评判者主要是依据运行的时长以及内存的消耗来进行判断的。下面就简要介绍一下运行时长以及内存消耗:
3.1 运行的时长
通常来讲设计者不是依据算法的总运行时间来衡量时间长短的, 这是因为计算机仍然是算法正常运行的载体, 计算机的运行速度跟许多因素有关, 例如计算机的运行环境、计算机内部使用损耗等。因此, 同一种算法在不同的计算机运行载体上运行的效果也是有很大差别的。一般来说, 计算机运行时长的大小不是衡量算法效率的一种标准, 而是判断算法运行时间损耗的一项指标, 能够在一定程度上评判算法运行的好坏。
3.2 内存的消耗
计算机运行算法, 会暂时占用相关的空间, 被占用的空间大小尺度就是常说的内存消耗, 内存消耗与相关的函数紧密联系。内存消耗主要内容是传入和传出信息占用的内存、算法在运行过程中暂时占用的内存等。传入和传出信息占用的内存跟需要解决处理的问题是相关的, 不会因算法变化而变化;算法运行中暂时占用的内存大小是由算法来决定的, 不同的算法需要不同的内存, 因此, 比较好的算法需要的内存也比较少, 这也是内存消耗成为评判算法好坏的又一个非常重要的标准。
参考文献
[1]邓龙.计算机软件基础数据结构算法[J].信息与电脑 (理论版) , 2012 (6) .
[2]李毅波.数据结构与算法学习系统的设计与实现[D].中南大学, 2012.
[3]曹林, 缪旻, 樊文波.计算机软件基础课程设计的探索与实践[J].中国科教创新导刊, 2013 (4) .
算法基础 篇3
随着计算机技术与数据库技术的不断发展, 数据与信息的在生产生活中的重要性日益凸显, 信息获得与存储成本不断下降, 数据库的规模与范围、深度等都不但的增加, 为人们提供着海量的信息与数据资源。在上世纪中期出现的数据库管理技术也成为了一个重要的计算机技术分支, 并且从原始的文件处理演变到功能强大的数据库, 同时数据库系统的开发和研究也早已从浅层的网状数据库到开发关系的数据库系统, 数据建模工具和索引存取等方法;同时联机处理也的到了更加广泛的应用。但是数据库的发展速度仍然不能满足人们对信息处理的需求, 因为智能化的数据整合与处理分析才是人们需要数据库重要功能, 即可以对数据进行深层次的高级分析, 此时就提出了数据挖掘这个概念。
数据挖掘的基本概念提出与1995年, 数据挖掘是一种较为直接而形象的翻译方式, 体现的是技术的基本思路, 即从海量、存在干扰的数据中获得某种规律的的过程, 并使之成为重要的决策支持。当然也可称之为数据开采或者数据采矿。究其定义而言不同的研究者对其解释也不尽相同, 多数人认同的是将数据挖掘看做是知识发现的过程, 也有人认为是知识发现的一个基本步骤, 但不是全部。
不论是合作理解, 数据挖掘作为知识发现的重要过程是不可否认的, 其具体的实施步骤如下:数据降噪, 即在海量数据中存在一些与知识无关的数据, 就是噪声, 因此需要进行清理;数据的集成, 海量数据往往来自多个数据源, 因此需要进行集成;数据甄选, 即从数据库中获得与知识获取相关的数据信息;数据转化, 即利用算法改变数据模式, 使其适应数据挖掘的基本需求, 如汇总、聚集等;数据挖掘, 即根据数据挖掘的算法提取数据的基本模式;模式评价, 即对某种兴趣度进行衡量, 由此识别对知识获取有用的模式;知识解答与表达, 完成数据挖掘后利用相应的表达方式将挖掘结果呈现出来。
在挖掘步骤中第一到第四步骤其实都是一种预先处理的过程, 为数据挖掘做前期的准备;而后面的第五到第六个步骤则是根据不同的知识获取目标而设定不同的算法, 以此获得有价值的知识;最后一步则是规则解释的过程, 并使其结果可视化;所有的步骤其实都是一个知识学习的全过程。而所有的数据挖掘其核心的技术措施就是对算法的设计, 即利用何种方式对数据进行筛选, 从而消除那些对知识获取无关的数据噪声, 并在最终获得所需的有价值的信息, 这就意味着同样的数据经过不同的算法获得的知识是不同的。这既是数据挖掘中挖掘算法的重要作用, 同时其基本原理也将影响其结果, 本文将利用信息统计为基础提出一种挖掘算法。
二、基于信息统计的数据挖掘算法
数据挖掘是一种提出与上世纪末期的新技术形式, 其主要的提出目的就是要在海量的数据中获得某些有价值的信息, 其本身就已经超出了单纯的计算机技术范畴, 是多学科结合的产物。所以不同的数据挖掘任务所采用的数据挖掘方法也不同;对于同一任务可以选择的不同科学领域的算法也是多元的;预测性挖掘任务因为目标变量的属性不同, 其分类与预测的方法也就存在差异。一般而言数挖掘的任务可以分为两种, 一种描述;一种预测。描述是对数据库的数据进行一般特征与性质的总结。预测则是对数据进行分析与判断, 作出一种发展的假设。具体而言描述性挖掘的任务主要用在对数据分布特征和数据的总结与分析;而预测性挖掘则是在数据描述的基础上对数据的某一个特征进行判断, 推出其发展的趋势。具体的挖掘案例如:对城市的人均收入进行分析, 此时就需要采集资料在资料搜集的过程中必须遵循随机性、独立性等原则。针对于此按照统计学的基本原理本文提出基于此的数据挖掘的算法如下:
(一) 基本定义
无效数据定义:在某个数据的采集中如果某个数据的值≤0, 则这个数据在数据集合中是无效的。
有效数据定义:在采集与归纳的数据中与无效数据相反, 其值>0则该数据即为有效数据, 也就是数据符合数据采集的实际情况, 不是噪音数据。
均值定义:所有数据的平均值即为均值, 如有n个数a, 则所有a1…an的平均值就为均值:
与之相应的有方差:
样本比例方差定义:假设在样本均值中的数据样本为a1…an, 则在数据挖掘中形成的样本比例方差为:
备注的定义:样本方差在应用中仅仅表达了数据的离散特征, 但是在研究信息统计为基础的数据挖掘中, 其不能代表数据的数据源的差异, 如前面提及的影响城市收入因素的地区性差异, 所以引入比例方差来消除其负面印象。
3σ原则的定义:在数据中存在一个随机变量, 因此在挖掘中必须设定一个随机变量的范围, 也即是为随机变量设计一个区间, 而使得区间以外的数据比例降低至最低, 也可是允许范围, 通常在设定中需要保证其范围在均值所能控制的范围内, 即:
满足其在上面的区间范围内的原则就是所谓的3σ原则。
计算定理1:对于原始数据n和无效的数据n1、有效数据n2可以得出一个固定的等式, 即n=n1+n2是表示所有数据的集合, 其条件成立。
则证明:对于任何一个原始数据而言, 其必须满足的条件是Xi≤0;否则其满足的条件是Xi>0, 则必然会存在一个且仅有一个关系成立。即任何一个原始数据的Xi要么是有效的要么则是无效的, 其其属性是唯一的。则所有都满足等式n=n1+n2成立。
计算定理2:样本的方差与样本的比例方差之间应存在一个数学关系:
则证明样本比例方差的公式可以转化为:
基于此, 本文中提出的算法对原始的统计信息进行多次处理, 有效的利用原始数据中所包含的基本信息, 不会对统计信息产生负面影响。
(二) 统计信息的数据挖掘算法
此算法步骤:1) 输入没有经过处理的原始数据, 形成其数据的为以a为数据单元的多个数据集合。2) 检查并消除数据集合中存在的无效数据, 保留每一组中的有效数据;3) 计算每一组中有效数据的样本均值, 并求出其方差值;4) 按照前面的步骤3) 计算结果建立一个对应每组数据的模型;5) 利用Si近似替代, 然后根据前面提出的3原则设计出一个适应数据挖掘的每组的数据区间;6) 计算出每一个组的有效数据的样本比例方差值;7) 按照第三与第六步的分析结果, 分别对样本的均值和样本的比例方差进行排序。仍以收入比较为例, 样本的均值大的经济水平相比之下就发展水平高而均值小则低, 样本比例方差大的贫富差距就大而小的则差距小。
三、结束语
在以信息统计为基础的数据挖掘算法设计中, 突出的特征就是利用统计信息对有效数据和无效数据进行区分, 借此消除多余的噪声干扰, 即无效数据。因此这个算法的优势就是可以出去噪声数据对有效信息的影响;在数据分析中仍可保留原始数据的有效信息, 即有效降噪并充分挖掘。
摘要：信息高度发达的时代要求对信息的处理具备有效而高效的技术, 数据挖掘正是为此而产生并发展的, 在数据挖掘中不同的任务所利用采用的计算方式也不同, 本文就针对一种基于信息统计的数据挖掘算法进行了简要的介绍。
关键词：数据挖掘,挖掘过程,信息统计,挖掘算法
参考文献
[1]陈文锋.基于统计信息的数据挖掘算法[J].统计与决策, 2008 (15) .
[2]王振华, 柴玉梅.基于决策树的分布式数据挖掘算法研究[J].河南科技, 2005 (02) .
[3]田飞.简谈数据挖掘算法[J].科技咨询导报, 2007 (29) .
[4]胡桔州, 侯木舟, 欧阳资生.数据挖掘的统计方法及其软件实现[J].统计与决策, 2007 (05) .
算法基础 篇4
关键词：算法设计,立体教学模式,任务驱动,多元化
1、引言
计算机算法基础是计算机科学中一门处于核心地位的教育课程, 算法的研究已经被公认为是计算机科学的一块基石。该课程具有知识点多, 内容涉及面广, 学习量大, 对学生的抽象思维和逻辑思维能力要求高, 同时实践性强等特点, 使得许多学生学习该课程感到相当困难。然而, 对于信息与计算科学这个数学与计算机交叉的学科而言, 学生的数学基础相对于计算机专业而言普遍较好。这使得他们在逻辑思维和数学抽象思维能力上具有一定的优势, 但是, 实践能力相对更差。
目前, 在本科阶段的教学中, 该课程以单一的讲授教学为主, 教学方法呆板, 教学枯燥难懂, 学生的学习动力不足, 其优势未能得到发挥, 弱势也没能得到提高。学生最后只是机械地记住几种算法, 没有真正消化。然而, 本人通过几届ACM程序设计大赛的培训工作发现, 信息专业的参赛学生通过这种特殊的培训之后能够表现出高于其他专业的解题能力。事实上, 这一套方法应用于对信息专业的其他学生教学中也取得了很好的效果。
本文针对计算机算法基础课程教学实践中存在的问题和不足进行了研究, 对现有的课程教学进行了改进, 旨在更全面地实现该课程的教学目标, 有利于培养学生发现问题、分析问题和解决问题的能力, 也有利于提高学生的创新能力。
2、教学内容的分析
本课程主要介绍算法的基础知识, 包括抽象计算模型、算法基本概念、算法复杂性分析基础、算法设计的基本方法 (包括递归与分治法、贪心法、动态规划方法、回溯法、分支限界法以及高级图论算法等) 、以及算法复杂性理论基础。在内容上以这几大算法为主线, 注入新的前沿内容, 同时可以串上历年的竞赛试题。
计算机算法基础课程主要介绍各种数据结构的特点和运算, 上接数据结构、高等数学、离散数学、程序设计语言等专业基础课, 下启软件开发, 人工智能等高级课程, 在计算机课程中起到一个承上启下的作用, 它与其它课程的关系如图1所示。在教学内容处理还要注意启后, 与其它后续课程挂起钩来, 用它去解决课程中出现的问题。如解决软件开发中一些实际问题, 人工智能的算法等。
在教学中主要是依据四段模式来讲解:分析问题、数学建模、算法设计、程序实现, 做到理论和实践并重, 抽象和具体结合。所以在内容讲述中, 一方面, 要注意渗透数学思维, 让学生学会充分利用数学工具来分析问题和解决问题, 要引导学生在数学建模和算法设计的过程中体会数学的严谨和魅力, 以及各种求解策略的适用范围。另一方面, 要注重算法的程序实现, 只有真正实现了, 才能更加深对算法的理解, 否则算法的讲述只不过是纸上谈兵, 只有空洞的理论。
3、教学模式的改革
为了适应该课程的特点, 我们改单一的教学模式为立体化的教学模式。其总体架构可用图2表示。
3.1 教学目标的多元化
算法课程的主要目标不是死记硬背一些知识性的东西, 而在于能力的培养。学生不仅要了解计算领域中的一系列标准算法, 还要具备设计新算法和分析其效率的能力。此门课程的教学目的是使学生掌握一些常用的计算机算法和使学生具有独立地完成计算机软件设计的基本能力;从而在今后的工作中能够独立地分析和解决各类实际问题。教学目标是理论和实践并重, 理论结合实践。既要培养学生的抽象思维能力, 又要注重培养实际解决问题的应用能力。
3.2 教学方式的多元化
算法这门课程既有深度又有广度, 光靠课堂四十五分钟的讲解很难达到理想的教学效果。为此我们采用以传统的集中式课堂教学为主, 开放式的网络课堂教学为辅的多元教学方式。
(1) 可以充分利用先进的网络技术, 开设网络教学平台, 便于共享资源, 课后交流, 并布置各种难易程度的在线作业, 这样便于因材施教, 培养个性化人才。
(2) 特别重视课程实验教学环节, 目前实验课程的内容大多是课堂教学内容的验证性实验, 学生照着书上写好的源程序依葫芦画瓢, 知其然不知其所以然, 结果出来后就万事大吉。这种实验课的质量是不好的, 学生的应用能力, 解决问题的能力还是没有提高。我们应该精心选择和设计与理论授课内容相关的问题, 让学生自行找到解决问题的算法并实现。
(3) 重视作业练习环节, 除了精心选择与课堂讲授内容相辅的基础练习外, 应重视布置综合的课程设计作业, 这种作业更能培养学生的综合应用能力和合作精神。
(4) 赛课结合, 以ACM程序设计大赛的习题库为平台, 通过定期组织程序设计竞赛, 可以有效地促进学生的学习, 形成相互竞争共同进步的局面, 以及提高学习兴趣。
3.3 教学方法的多元化
要达到课程的多元化目标, 教学方法不能采用单一的讲述, 而应采取各种教学方法结合的以学生为主体的启发式教学法。传统的课堂教学往往采用这种方式:提出任务→内容讲授→练习→总结, 这种模式学生没有思考和探索的空间。对这种教学方法按如后的模式进行改进:提出任务→设计并提出问题→讨论→讲授→练习。这种模式归结为以下几点:任务驱动、问题引导、讲授与讨论结合。
(1) 任务驱动:算法要解决的实际问题就是教学中的"任务"。在课程教学中, 要将具体的算法思维融入到"任务"中, 以任务为主导, 引导学生用算法设计策略自行探究解决方案, 另一方面, 在实验环节中, 将由教师布置结合课堂讲授内容且融入了知识点的任务, 让学生根据任务描述, 自主探索问题解决方案, 并提交程序代码。通过课堂教学和实验课程两个环节的任务驱动, 让学生自主探索地掌握算法分析方法和常见的算法设计策略, 并应用到实际问题中, 训练学生实践能力, 以达到教学目标。
(2) 问题引导:在授课过程中, 切忌简单地将备课内容流水式的讲解完, 一定要在每一个思考点为学生设置相应的问题, 引导他们朝着解决整个问题的方向思考, 让学生感觉到一种有自身参与的动态的学习过程充满了兴奋和乐趣。改革课堂问答方式, 在单向的老师向学生提问的方式基础上增加学生向老师提问和学生间互相提问的方式。
(3) 讲解与讨论结合:学生根据教师提出的问题展开讨论, 自主地找到解决问题的方法, 在讨论完了这后再由教师讲授和点拨要点。
3.4 教学评价的多元化
传统的课程考核方式采取的是平时成绩与期末考试成绩按一定权重求和的评价方式, 在考试内容上重记忆, 轻创新;重知识, 轻能力;过分注重书本知识, 且往往只对部分知识点进行考查, 无法反映学生综合知识的学习情况, 忽视学生应用知识分析、解决问题的能力的考核。
我们的教学评价方式是改单一的知识性考核为立体化考核方式, 要考查的因素包括平时成绩、理论考试、编程考试和课程设计考核, 各因素所占比例如下表1所示:
理论考试沿用传统的笔试试卷的方式, 重在基本知识的考核。编程考试是根据课程要达到的基本能力目标进行考核, 要求学生在事先设计好的一组上机题目随机抽取2道, 在计算机上完成。课程设计则是由多个学生组成一个组, 分工设计一个综合性的程序, 如设计五子棋程序。这种设计式的考核可以考察学生的综合应用能力, 可以更全面地涉及所学的知识, 并能使学生在课程设计过程中培养分工合作的能力。
4、教学效果调查
根据以上模式进行教学改革后, 笔者在最近一次的教学检查中对92名学生作了问卷调查, 统计了学生对教学改革的满意程度, 结果如下表2, 同时调查并统计了教学改革能更好地促进哪些方面能力的培养, 结果如下表3。
从表2和表3的调查数据来看, 立体化教学模式在实践中收到了较好的效果。
5、结束语
本文根据计算机算法基础课程的特点以及目前教学中存在的不足, 研究并提出了一种立体化教学模式, 分别对教学目标、教学方式、教学方法和教学评价作出了多元化处理, 在教学改革实践后在所教的班级作了问卷调查, 结果表明这种教学模式取得较为满意的效果, 在学生的能力培养和兴趣培养方面均有较大的提高。但是对学生创新思维能力的培养还需要我们进一步研究。
参考文献
[1]王晓东.算法设计与分析[M].清华大学出版社2006
[2]王素立, 白首华.算法分析与设计教学方法[J].湘潭师范学院学报 (自然科学版) , 2005, 27 (3) :124-127.
[3]孙红丽, 叶斌.浅谈算法设计与分析课程的教学改革[J].太原教育学院学报, 2005 (12) :45-47
算法基础 篇5
计算机基础课程是大学的必修课程,计算机基础考试逐渐由传统笔试向机试转变,这种转变既能考查学生基础知识的掌握程度,又能考查学生的实际操作能力,减轻了教师负担,保证考试的公平、公正。组卷技术是在线考试系统实现的核心,目前组卷算法很多,常见的类型主要有简单随机抽取算法、回溯试探算法、遗传算法。
(1)简单随机抽取算法是从题库中随机抽取一定数量的满足预先设定条件的试题组成试卷。这种方法实现简单、容易理解、组卷速度较快,但是抽取的试题重复率高,尤其是题库小的系统[1]。
(2)回溯试探法是随机抽取算法的改进,它采用随机抽取算法从题库中抽取试题,如果满足条件就将试题标记放入预先建立的栈中,如果抽取的试题不满足条件,就返回到上一个成功状态,继续随机搜索。它有效地解决了简单随机算法的试题重复抽取问题,实现简单,但只适用于小型题库系统。对于大型题库来说,需要占用很大的内存空间,且组卷时间长、效率低。
(3)遗传算法是模仿生物界中遗传、变异、交叉等过程,依照基因组合原理对染色体进行编码,按照优胜劣汰的原则得到最优解。这种算法具有全局寻优、智能搜索和收敛速度快等优点,但是实现困难[2]。
柳浪涛、谷林[3]提出了一种“卷内分块、组块分层”的组卷机制,按照题目类型分为若干块,按块分别抽题。按照题型分块,即为题库分类;块内分组,即为不同类型试题分组。分类算法是指按照题型设计将题库分类,解决知识点覆盖面的问题,而分段算法是将各类题型试题按照“知识点”、“难度系数”字段分组,从每组试题中按照试题数量比例抽取相应的试题,以解决试题重复抽取问题。题量越大,抽取效果越好。
综合考虑算法难易、组卷速度、知识点覆盖率、试题重复率等问题,本文采用分类分段回溯试探算法。分类分段算法结合回溯试探算法,综合利用了两者的优点,弥补了两者的不足。首先将题库按照不同题型分类,然后再对不同类别的试题按照知识点、难度系数字段分段,最后对每类题库根据预先设定条件随机抽取试题。回溯试探算法是对简单随机算法的改进,随机抽取一道题加入试卷,系统将记录下这道题的知识点、试题序号放入预先建立的栈中,再根据约束条件随机抽取下一道题,将这道题的知识点、试题编号与上一道题记录下的知识点、试题序号相比较,如果不同,则将试题加入试卷并释放上一个记录,并写入这道题的属性,如果相同则重新抽取试题,以此类推。回溯试探法结合分类分段抽取法,有效缩小了回溯搜索的范围,提高了组卷速度,解决了试题知识点覆盖面、试题重复抽取以及知识点覆盖面问题。
1 数据库设计
题库设计质量的好坏对组卷成败至关重要。本文采用分类分段回溯试探算法,在试题库中按“难度系数”排序,再按“知识点”排序。排序后,同一个知识点的同一难度系数试题放在一起,组卷就是从同一知识点同一难度系数的题目中随机抽取指定数量的题目[4]。
计算机基础在线考试一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题几类。为了提高组卷效率,需要预先确定试卷为百分制,然后确定题型题量、小题分值、知识点分布等属性,这些设置好的试卷属性字段都统一存放在PaperSet数据表中。按照试卷属性设置表中数据,每种题型分别从相应的题库中抽取。题库表分为选择题及操作题。
选择题题库表结构如表1所示,操作题题库表结构如表2所示。其中“questType”字段表示为题型设置编号,“1”代表选择题,“2”代表填空题,“3”代表Excel操作题,“4”代表Word操作题,“5”代表Windows操作题。表2中的“OperateType”字段指每种操作题的操作类型,用数字代表不同的操作类型,例如Word操作题中“1”、“2”、“3”数字分别代表“表格操作”、“文本替换”、“段落缩进”操作类型,Excel题型主要设计有“单元格样式”、“行列样式”、“工作表操作”、“生成图表”等操作类型,Windows操作题主要设计有“文件夹删除”、“文件夹创建”、“文件夹重命名”、“文件复制”等操作类型。此外,题库中的“Chapter”字段,用数字代表不同的知识点分布,用“Degree”难度系数划分“简单”、“中等”、“较难”、“困难”,分别用数字“1”、“2”、“3”、“4”来存储。
2 组卷
将在线考试系统设计的5种题型分为5个模块,在页面设置5个事件按钮,考生点击一个按钮将随机从相应题库抽取确定数量的试题,如图1所示。按照题型不同将题库分为5类,在这5大题库中又采用章节、难度系数的设定对每种题型进一步分组。题库中的每道题至少有如下4个属性,定义如下:
(1)分值:每道试题的分值,小题设置的分值与该题型的题量乘积即是该大题总分。设计试卷满分为100分,根据题型设置,单选题30分,15题,每题2分;填空题20分,10题,每题2分;Word题20分,5题,每题4分;Excel题20分,5题,每题4分,Window题10分,4题,每题2.5分。
(2)题型:试题的类型一般分为选择题、填空题、Excel操作题、Word操作题、Windows操作题等。给出试题类型,自动组卷将在给定的数据库表中搜索,缩小了搜索范围,加快了组卷速度。
(3)知识点:又称为考核点,它涉及具体考核内容,知识点按章节从前往后划分。每种题型预先设计一定数量的知识点,每道试题考查内容对应不同的知识点,每个考查的知识点录入一定数量的试题。
(4)难度系数:指测试试题的难易程度。它的定义是qi=1-Ri/n,qi表示第i题的难度系数,Ri表示此题平均得分值,n是该题的满分值[5]。试卷难度控制将容易、中等、困难试题所占比例进行设置。一般试卷的难度系数在中等才能使考试成绩成正态分布。题目区分度与它的难度相关,通常过高或过低题目的区分度都较小,中等难度的区分度最优[6]。
根据分类分段算法,按照题型设置,每种题型设置相应题库,分5次随机抽题。对于每类题库,再按照知识点、难度系数字段属性分配集合。根据回溯试探算法执行抽题,每种题型抽题的组卷事件触发按钮点击后,按照设定的难度系数、题型、题量等约束条件分别从相应的题库中随机抽取一道试题加入试卷中,将此试题的知识点、试题序号记录下来,再抽取下一道题,将这道题的知识点与上一题相比较,如果相同就放弃加入试卷并继续抽题,如果不一样即释放上一条记录,更新为当前记录。以此类推,直到完成组卷,算法描述如下:
这样的设计解决了试题知识覆盖面、试题重复率等问题。部分抽取试题代码如下(采用C#语言结合SQL语言的代码):
对于不同的题型调用不同的抽题函数随机抽取试题。
3 实验结果
分类分段回溯试探组卷算法相较于随机抽取算法而言,解决了试题重复率高、知识点覆盖率小的问题,相较于回溯试探法而言解决了搜索速度慢、组卷效率低等问题。本文算法综合利用了分类分段随机算法以及回溯试探算法的优点,摒弃了它们的不足,代码实现较为简单,能够生成需要的试卷。
4 结语
本文采用的分类分段回溯试探算法,结合了简单随机抽取算法和回溯试探算法的优点,实现简单,大大缩小了搜索范围,组卷速度快且避免了试题重复率问题。在线考试组卷系统兼顾了题型、题量、分值、知识点分布、难度系数等试卷参数,能快速得到一份满意的计算机基础在线考试试卷。
参考文献
[1]王琦.智能组卷算法研究比较[J].科技信息,2008(29):403-418.
[2]高兴媛,古辉.在线考试系统自动组卷技术的研究与实现[J].计算机与现代化,2011(3):155-157.
[3]柳浪涛,谷林.自动组卷系统试题难度和知识点覆盖控制算法[J].西安工程大学学报,2015,29(3):321-324.
[4]雷勇.分类分段算法在组卷中的应用研究[J].实践与经验,2014(19):41-44.
[5]桂阳,王修信,农京辉,等.大学物理试题库智能组卷随机抽取法的改进[J].广西物理,2008,29(2):23-25.
算法基础 篇6
证券公司作为一个特许行业, 面临着来自股东、客户及监管部门等方面的盈利压力, 上市证券公司还面临着再融资规则、退市规则的盈利压力。会计年度的人为划分, 还使证券公司面临着年度盈利目标和长期盈利目标的平衡问题。财务预算作为一种管理工具, 具有控制企业财务收支、评价经营绩效的作用, 但实务中证券公司一年一定、最多年中调整一次的财务收支预算 (以下简称财务预算或预算) , 与现实相差甚多, 常流于形式, 财务预算往往蜕化为20%左右的营业费用预算, 大大弱化了预算功能。本文在总结证券公司预算编制、执行中普遍性问题的基础上, 结合我国证券公司的业务和营业收支特点及部分证券公司经营战略的转变, 提出一种用于财务控制的财务预算方法——“以市场交易量为基础的滚动目标利润预算法” (以下简称“交易量预算法”) 。
现阶段证券公司的主要业务收入中, 自营投资业务收入波动性最大, 客户资产管理和投资银行业务收入占比相对较小, 经纪业务收入及与之相关的客户保证金利差收入占比最大且相较于自营收入而言波动性相对较小。交易量预算法根据证券公司收入结构的这一特点, 以经纪业务收入及与之相关的客户保证金利差收入的预测为核心, 在预计利润的基础上确定目标利润, 从而确定自营业务的亏损容忍上限, 并结合设定的止损率据以计算自营业务投资规模, 即锁定自营投资风险, 以确保最低盈利目标的实现。根据交易量预算法建立的预算模型还可以用于盈亏平衡分析和利润敏感性分析。
二、交易量预算法的主要内容与核心思想
在我国现阶段, 证券公司盈利模式同质化状态尚未根本改观, 证券公司“靠天吃饭”的行业特征明显, 股票指数和交易量的跌宕起伏使得证券公司的收入及与收入相关的支出具有极大的波动性, 特别是以股票投资为主的自营业务收入, 且其占营业收入的比重较高, 如全行业06、07年平均分别为36.45%和31.82%, 08年因大部分公司自营业务亏损而使这一比重骤降至很低的水平。因而财务预算很难编制, 预算与实际往往相差甚远。基于我国证券公司现阶段的业务特点和收入结构, 传统的预算方法对证券公司并不适用。
随着我国证券公司的发展及稳健经营的需要, 借鉴海外券商的收入结构, 特别是在我国证券市场目前没有风险对冲机制的情况下, 部分公司已开始逐步减少对股票自营投资的过度依赖, 以减少经营风险和经营业绩的波动性。这是在总结历史经验和教训基础上调整收入结构的必然趋势。全行业06-08年度经纪业务佣金收入占营业收入的比重分别为44.57%、56.56%、65.6% (自营亏损抬高了08年经纪业务佣金收入占比) , 呈逐年上升趋势。经纪业务收入目前是多数证券公司的主要收入来源。相较于股票投资业务, 经纪业务收入相对易于预测。正是在这样的背景下, 我们提出交易量预算法这一适合于证券公司的财务预算方法。
从财务角度看, 证券公司的主要营业收入可划分为卖方业务收入和买方业务收入。卖方业务收入包括经纪业务收入及衍生的客户保证金利差收入、资产管理业务收入、投资银行业务收入、融资融券业务利息收入等, 即除了自营业务收入外, 证券公司的其他业务收入基本都可归类为卖方业务收入。
交易量预算法的核心是首先预测预算年度的以经纪业务收入为主的卖方业务收入和主要营业支出, 并据以计算预计利润, 然后将一定比例的预计利润作为预算年度的目标利润, 预计利润与目标利润的差额作为公司可以承受的自营业务损失上限, 以此结合止损率来确定自营业务规模, 在预算年度根据预算执行情况及假设条件的变化按月或随时调整预计利润、目标利润和自营业务规模。为了确保目标利润的完成, 自营业务的规模可以因为看空而不断减少, 但不能因为看多而无限度增加, 自营业务的风险敞口应以预计利润与目标利润的差额为限。举例来说, 不含自营业务利润的预计利润假定为10亿元, 确定目标利润为8亿元, 则自营业务的风险敞口上限为2亿元;再假设自营业务的整体止损率为20%, 则自营业务的上限规模为10亿元 (2/20%) 。那么即使再看多, 自营业务规模也不能超过10亿元, 除非调整止损率, 比如将止损率调整为15%, 则规模可扩大至13.33亿元 (2/15%) 。
这一预算方法不将自营业务收入作为预算收入的组成部分, 而是在编制预算时, 根据利润预测结果确定一个自营业务的亏损上限, 并在预算年度内根据预算执行情况按月或随时予以调整。这是一种进可攻退可守的利润控制方法, 在市场繁荣、业绩好的情况下自营规模可随预计利润的增加而增加, 反之亦然。这样既能在股市上涨时增加利润, 又能在下跌时控制风险, 是一种稳健的经营策略。回顾我国股票市场的历史, 几乎是“一轮牛市消灭一批证券公司”。之所以如此, 是因为这些公司在牛市时不能根据自己的损失承担能力控制自营规模, 当熊市来临时又不能及时止损。2000年的牛市, 很多证券公司通过保本保底的资产管理业务的无限度扩张变相扩大了自营规模, 结果导致损失惨重, 相当一部分公司因此陷入困境或破产, 很多公司为了做到当年帐面盈利而不惜出售基金公司股权、上市公司法人股等优质资产。综合治理完成后, 证券公司合规经营日益走上正轨, 未来证券公司最大的经营风险将是来自于投资规模的失控。08年以来股市的大幅下跌又使个别未能根据自身盈利承受能力控制自营规模的公司发生年度亏损。《证券公司风险控制指标管理办法》中以净资本规模约束自营规模的规定是一种侧重于资产负债表风险控制的监管要求, 它与公司自身更侧重于利润表风险控制的目标不完全一致, 所以不能以此作为证券公司从盈利角度控制自营规模的依据。交易量预算法提出的以预计利润与目标利润的差额即预计利润的一定比例作为自营业务亏损上限从而决定自营业务规模这一思路是控制自营业务风险和公司业绩风险的有效方法。
三、交易量预算法的主要步骤
第一, 主要业务收入的预测。
(1) 经纪业务佣金净收入预测。经纪业务佣金净收入取决于三个因素, 即:市场交易量、市场份额、平均净佣金费率。佣金净收入=市场交易量×市场份额×平均净佣金费率。股票交易量取决于换手率和流通市值两个因素, 即:股票交易量=换手率×流通市值。对股票交易量的预测应综合主要研究机构对市场的预测, 建议取主要证券公司研究机构对交易量预测的平均值。基金、权证等其他品种的交易量或佣金净收入, 可根据前一年其占股票交易量或佣金净收入的比例并结合可能的变化进行估算。
在确定用于预测的市场份额和净佣金费率时需考虑以下因素:经纪业务代理买卖的证券品种包括A股、B股、基金、权证、国债现券、企业债及可转债、国债回购等, 每一品种交易量占交易总量的比重不同, 不同品种的市场份额和佣金费率也不同。各公司应根据自身市场份额和净佣金费率的品种结构, 以及预算年度交易品种结构的可能变化等因素, 确定是使用综合还是分品种的市场份额和净佣金费率。佣金净收入是佣金收入减去经手费、证管费、银行第三方存管费等手续费支出后的差额。经手费和证管费与佣金收入的比例关系不同, 银行第三方存管费与佣金收入没有直接关系, 而与客户保证金规模相关。公司应根据重要性原则确定直接使用净佣金费率单一指标, 还是在分别预测佣金收入、经手费、证管费、银行第三方存管费的基础上计算佣金净收入。市场份额应结合公司市场份额的变化趋势、市场竞争形势、公司应对竞争的策略等因素进行预测。另外, 预测时应充分考虑佣金费率逐年下降的现实, 结合公司的竞争策略确定预算时采用的佣金费率。
(2) 客户保证金利差收入。首先预测客户保证金规模。统计研究表明, 客户保证金规模与股票指数、交易量及市场份额呈正相关, 可以根据统计规律预测客户保证金的平均规模。预测时应剔除新股申购前后保证金的波动。客户保证金利差收入=客户保证金预计平均规模×利差率。
(3) 资产管理业务收入。主要指集合理财产品收入, 包括管理费收入、交易佣金收入和自有资金分红收入。如有其他资产管理业务, 可根据实际情况预测。分产品按预计平均规模和管理费率预计管理费收入。交易佣金收入按预计平均规模、换手率和佣金费率计算。自有资金分红收入按各产品的净值、自有资金参与规模、预计分红比例计算。
(4) 投资银行业务收入。投资银行业务收入可以根据证券发行和并购市场情况及公司的项目贮备情况预测。
(5) 自有资金利息收入。首先根据公司目前的自有资金规模、预算年度内重大投资和筹资项目情况等预测自有资金平均流入流出情况, 预计自有资金平均规模, 然后乘以预计的存款利率。
(6) 长期股权投资收入。为预测方便起见, 纳入合并的子公司可仅预测其净利润, 按控股比例计算投资收入。未纳入合并范围的长期股权投资根据历史数据预计分红收入。
第二, 营业费用分类及与营业税金的预测。
在参考管理会计对费用分类的基础上, 结合证券公司营业费用的特点我们将证券公司的营业费用根据性质划分为固定性费用、可预算控制性费用、变动性费用三大类。具体如下:
(1) 固定性费用。是指发生额相对稳定或标准确定后发生额可较为准确预计的费用。包括:固定性工资及与之有固定比例关系的工会经费、职工教育经费;房屋租赁费及与房屋拥有或使用相关的房产税、物业管理费、水电费;固定资产折旧及房屋装修、交易席位等摊销费用;社会保险费用及住房公积金;审计费等。固定性费用主要根据上年度实际发生情况及基础数据或标准的预计变动情况进行预测。
(2) 可预算控制性费用。是指发生额具有较大弹性但可通过预算的形式加以控制的费用。包括:差旅费、业务招待费、广告及宣传费、办公费、会议费等。可预算控制性费用是各相关部门费用控制的重点, 以公司核定的预算作为预测值。
(3) 变动性费用。是指发生额与相关业务指标或其他财务指标之间存在固定或相对固定的比例, 随相关业务指标或其他财务指标的变动而变动的费用。包括:与经营业绩相关的奖金及与之相关的工会经费和职工教育经费、与经纪业务佣金收入相关的经纪人佣金和交易单元流量费、与营业收入相关的投资者保护基金。变动性费用预测的基础是寻找各项变动性费用与相关业务指标或其他财务指标的函数关系, 通过建立模型来预测。
营业税金及附加的预测较为简单, 根据收入的预测结果, 剔除非营业税应税收入 (如金融同业利息收入、长期股权投资分红收入、公允价值变动收入等) 和营业费用中的投资者保护基金等营业税应税收入抵减项目, 然后乘以营业税税率及附加费率。
第三, 根据以上结果预测税前利润, 进而确定目标税前利润, 目标税前利润可按预测税前利润的一定比例来确定, 比如75-90%。不考虑汇兑损益、其他业务收支、营业外收支、资产减值损失等不重要或无法预测项目对利润的影响, 除非影响较大且易于预计。
第四, 将自营业务收入作为确保目标税前利润完成前提下的调节性收入, 即将预测利润超过目标利润的部分 (预测利润-目标利润) 作为公司可承受的自营业务损失上限, 设定止损率, 并据以计算自营业务的最大规模。
第五, 预算年度内, 每月根据预算执行情况及影响收支的关键因素和初次编制预算时设定的假设条件的变动情况预测剩余月份的营业收支及利润, 从而滚动调整年度预测利润、目标利润及自营业务规模。由于离预算年度结束时间越远预算的准确度越差, 所以为了保证预算控制的灵活性, 年初时自营业务的规模应低于按上述方法计算的上限, 比如控制在上限的50%以下, 随着时间的推移这一比例逐步提高。当然, 实际的投资规模还应根据对市场的判断来决定, 但不应超过按以上方法计算的规模上限。
四、预算模型的建立及应用
为了预测不同因素组合下利润预测值的变动情况, 及通过收支项目的平衡与调整以实现预算目标, 为预算的编制、分析与调整建立基础, 在上一部分内容的基础上通过EXCEL表格建立预算模型如表1所示。
通过该模型可以看出, 任何影响财务收支项目的因素及影响其他财务收支项目的收支项目的变动都可以通过模型自动计算出各财务收支项目和净利润的结果。这一模型还可以用来进行盈利敏感性分析和盈亏平衡分析, 是一个重要的财务分析工具。
交易量预算法是一种用于财务控制的预算方法, 所以任何预算基础的变动都要通过模型的调整来重新计算利润预测值, 以便随时因应这些因素的变化来进行财务控制。一般来说, 在每月初根据截止上月末财务收支的实际情况及各种预算因素的变化情况重新编制年度预算, 并据以计算预测利润、目标利润、自营业务规模等, 所以, 建立在交易量预算法基础上的用于财务控制的预算是一种滚动预算。需要说明的是, 实际的财务收支预算模型要比以上模型复杂得多, 还应有与之相关的营业费用预算模型相配套。各公司应根据自身的业务及费用特点建立合适的财务收支预算和营业费用预算模型。
五、财务预算的层次及相互衔接
根据作用不同, 财务预算可分为三个层面, 即:用于财务控制的预算、用于内部业绩考核的预算、用于董事会对管理层考核的预算。根据交易量预算法编制的预算更具预测的性质, 属于用于财务控制的预算, 但它没有考虑公司对各业务线的业绩增长要求, 因而不适用于内部业绩考核。用于内部业绩考核的预算应体现对各业务线的业绩增长要求和成本控制要求, 它源于预测但应高于预测。而用于董事会对管理层考核的预算是董事会对公司及管理层进行业绩考核的依据, 它是管理层和董事会博弈的结果, 一般介于用于财务控制和用于内部业绩考核预算之间。这三个层面的预算侧重点不同, 但用于财务控制的预算是基础, 根据交易量预算法编制的预算属于用于财务控制的预算。
参考文献