博文
[转]计算机科学数学理论浅谈(2008-10-17 15:52:00)
摘要：
作者：曾毅 转载自：CSTC文档中心
计算机自从其诞生之日起，它的主要任务就是进行各种各样的科学计算。文档处理，数据处理，图像处理，硬件设计，软件设计等等，都可以抽象为两大类：数值计算与非数值计算。作为研究计算机科学技术的人员，我们大都对计算数学对整个计算机科学的重要性有一些了解。但是数学对我们这些专业的研究和应用人员究竟有多 大的用处呢？我们先来看一下下面的一个流程图：
上图揭示了利用计算机解决科学计算的步骤，实际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。从中我们不难看出计算数学理论对用计算机解决问题的重要性。下面我们将逐步展开对这个问题的讨论。
计算机科学的数学理论体系是相当庞杂的，笔者不敢随意划分，参考计算机科学理论的学科体系，我们谈及的问题主要涉及：数值计算，离散数学，数论，计算理论四大方向。
[一]数值计算（Numerical Computation）主要包括数值分析学、数学分析学、线性代数、计算几何学、概率论与数理统计学。
数值分析学又常被称为计算方法学，是计算理论数学非常重要的一个分支，主要研究数值型计算。研究的内容中首先要谈谈数值计算的误差分析，误差是衡量我们的计算有效与否的标准，我们的算法解决问题如果在误差允许的范围内，则算法是有效的，否则就是一个无效的问题求解。另外就是数值逼近，它研究关于如何使用容易数值计算的 函数来近似地代替任意函数的方法与过程。感觉应用比较广的不得不提切雪比夫逼近和平方逼近了。笔者曾经尝试过的就是通过最佳平方逼近进行曲线的拟合，开发工具可以选择VC++或者Matlab。插值函数是另外一个非常重要的方面，现代的计算机程序控制加工机械零件，根据设计可给出零件外形曲线的某些型值点，加工时走刀方向及步数，就要通过插值函数计算零件外形曲线及其他点函数值。至于方程求根、线性方程组求解，一般的计算性程序设计问题都会多多少少的涉 及一些，我们这里就不赘述了。关于数值分析学的一个学习误区......
产生式系统(2008-10-16 13:33:00)
摘要： 产生式系统由3个基本要素组成：一个综合数据库(Globle database)，一组产生式规则(Set Of rules)和一个控制系统(Control System)。
1．综合数据库
它是产生式系统所用的主要数据结构。它主要表示问题的状态，即初始状态、目标状态和中间状态，以及状态之间的关系等。它不是固定不变的，在求解过程中，它的内容将越来越多，状态之间的关系也越来越复杂。
经常用来表示数据库的数据结构有串、集合、数组、树、表、记录、队列等。
2．产生式规则
是对数据库进行操作的一系列规则。规则的一般形式是：
IF 条件THEN 操作即满足应用的先决条件后，就对数据库实行后面的操作。
3．控制策略
它规定了操作的顺序，即在什么条件下用什么规则进行操作，什么条件下停止运行，即它规定了问题求解的搜索策略和路线。一般，控制策略可分为两大类：
＃不可撤回方式(Irrevocable)
＃试探法(Tentative)
a)回溯法(Backtracking)
b)图搜索法(Graph-search)</PRE></P>......
DFT详解(2008-10-14 11:18:00)
摘要：
本文的目的不是讲如何实现FFT, 而是讲DFT到底是怎么计算的. 对每一个公式进行解释
DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。
然而对于傅里叶变换的公式,很多人看起来头疼, 周期性与加和公式在一起, 使得很多的人不能真正地理解它, 更没有办法来计算它, 我们编程的人一个习惯, 那就是一个算法, 一般来说是要先能够用一个简单的实例来自己先在纸上能够用笔计算出来, 然后才能实现, 像傅里叶变换, 如果给一个简单的4点序列{2, 3, 3, 2} 我们不能用笔计算出来的话, 更不用说用程序来实现了.
1. 长度为N的有限长序列x(n)的DFT为
2. 旋转因子的周期性、对称性、可约性。
1) 周期性:
2) 对称性:
3) 可约性:
3. 公式解释:
再根据复变函数论里的欧拉公式, 我们可以很容易的得到.
比如说4点序列的Wn4 分别为{Wn0,Wn1,Wn2,Wn3}={1, -j, -1, j}, 实际上Wnm其实就是将单位圆(2 pi)等分为N份的点所表示的复数.
4. 简单的举例:
4点序列{2, 3, 3, 2}的DFT的计算:
......