17.txt

This complete matlab for neural network

发信人: GzLi (笑梨), 信区: DataMining
标  题: [转载] 作为学科的计算科学[续3]
发信站: 南京大学小百合站 (Fri Jan  3 19:38:28 2003)

【 以下文字转载自 AI 讨论区 】
【 原文由 yinxucheng 所发表 】


/////////////////////////////////////
// 附录的第二部分
////////////////////////////////////

一 算法和数据结构
    本领域研究一些特定类型的问题及它们的有效的解。基本问题包括：对给定类型的问
题，最好的算法是什么?它们要求多少存储空间和时间?空间与时间的折衷方案是什么?存取
数据最好的方法是什么?最好算法的最坏情况是什么?算法的运行按平均来说好到何种程度
?算法一般化到何种程度——即什么类型的问题可以用类似的方法处理?
    1.理论
    算法和数据结构领域理论的主要原理是：
    (1)可计算性理论。它定义机器能干什么、不能干什么。
    (2)计算复杂性理论。它告诉你如何测度町计箅函数的时空要求，把问题的大小和解决
该问题算法的最好或最坏情况的性能联系起来，并提供证明对问题的任何可能解的下界的
方法。
    (3)算法和算法类的时间和空间界限。
    (4)难解性(intractability)水平。例如，确定性的多项式时间内可解的问题(P-问题
)；非确定性的多项式时问内可解的问题(NP-问题)；以及有效的并行机可解问题(NC-问题
)。
    (5)从算法的数据流要求到机器通讯通路的并行计算、下界和影射。
    (6)在时空上比确定性算法更加有效、且以足够高的概率获得TF确结果的概率算法。蒙
特卡洛方法。
    (7)密码术。
    (8)图论、递归函数、递推关系、组合论、微积分、归纳、谓词逻辑和时态逻辑(Temp
oral logic)、语义学、概率和统计等支撑领域。
    2．抽象
    算法和数据结构的抽象的上要部分是：
    (1)对重要问题类的有效的最优的算法和对最好、最坏和一般性能的分析。
    (2)控制和数据结构对各种问题类时空要求的影响的分类。
    (3)重要的技术类型，像分治(divide-and-conquer)、格里地算法、动态舰划、有限状
态机解释器、堆栈机解释器。
    (4)并行和分布式算法，把问题分由可以在不同处理器上执行的任务的划分方法。
    3.设计
    算法和数据结构领域的避计和实验的主要内容是：
    (1)时最要问题类的算法的选择、实现和测试。这些问题类包括搜索、排序．随机数产
叶和结构模式匹配。
    (2)对于许多类型的问题都可以使用的通用方法的实现和测试。如杂凑法(hashing)、
图和树。
    (3)分布式算法的实现和测试。例如网络协议、分布式数据更新、信号(semaphores)、
死锁检测器和同步方法。
    (4)存储管理的实现与测试。例如无用单元收集、伙伴系统(buddy system)、表(list
s)、表格(tables)和分页。
    (5)对组合问题启发式算法的大量实验测试。
    (6)能够安全可靠和秘密通信的密码协议。

二、程序设计语言
    本领域研究执行算法的虚拟机的符号表达、算法和数据的符号表达以及从高级语言到
机器码的有效的翻译。基本问题包括：由一钟语言给出的虚拟机的可能的组织(数据类型、
运算、控制结构、引入新类型和运算的机制)是什么?这些抽象怎样在计算机上实现?用什么
样的符号表达(语法)可以有效地指明计算机应该做什么?
1.理论
程序设计语言领域的理论的主要部分是：
(1)形式语言和自动机，包括语法分析和语言翻译的理论。
(2)图灵机(过程性语言的基础)。
(3)形式语义：定义计算机数学模型及模型、语法和实现之间关系的方法。主要的方法包括
标志的、代数的、操作的和公理的语义。
(4)支撑领域：谓词逻辑、时态逻辑、近世代数和数学归纳。
2．抽象
程序设计语言领域的抽象的主要部分包括：
(1]基于语法和动态语义模型的语言的分类：即静态型、动态型、功能的、过程性的、面向
对象的、逻辑的，说明性的、报文传递和数据流。
(2)语言按应用领域的分类：即商业数据处理、模拟、表处理和图形。
(3)程序结构的主要语法和语义模型的分类：即过程分级、功能合成、抽象数据类型和通信
的并行过程。
(4)每种语言的主要类型的抽象实现模型。
(5)语法分析、编译、解释和开标码优化的方法。
(6)语法分析器、扫描器、编译器部件和编译器自动产生的方法。
3.设计
程序设计语言倾向的设计与实验的主要内容是：
(1)和特定抽象机器(语义)和语法一起，能形成统一的一可实现的整体的特定语言。例如，
过程性的(COBOL，FORTRAN，ALGOL，Pascal，Ada，C)、功能的(Lisp)，数据流(SISAL，V
AL)、面向对象的(Smalltalk，CLU)，逻辑(Prolog)，串处理(Snobol)，和并行性(CSP，O
ccam，Concurrent Pascal，Modula2)。
(2)特定类型语言的指定的蛮现方法：运行时间模型，静态和动态执行方法、打印检查、存
储和寄存器分配、编详器、交叉编徉器和解释器、在程序巾寻找并行性的系统。
(3)程序设计环境。
(4)语法分析器和扫描器的产生器(例如YAcc，LEx)、编译器产生器。
(5)语法和语义错误检查程序、剖面(profing)、查错和跟踪。
(6)程序设计语言方法对文件处理功能的应用，如制表、图、化学公式、展开片、方程式、
输入和输出以及数据开关。其他应用，如统计处理。

三、体系结构
    本领域研究将硬件(和相应软件)组织成有效和可靠系统的方法。基本问题包括：在一
个机器中实现处理器、存贮和通讯的好方法是什么?我们如何设计和控制大的计算系统并且
有说服力地表明，它们能够在有错误和故障的情况r完成预期的J．作?什么类型的体系结构
能使许多处理单元有效地协同工作，实现一个计算的并行?我们怎样测度计算机的性能?

l.理论
体系结构领域的理论主要部分是：
(1)布尔代数
(2)开关理论
(3)编码理论
(4)有限状态机理论
(5)统计、概率、排队论、可靠性理论、离散数学、数论和不同数制下的算术等支撑领域。

2．抽象
体系结构领域的抽象主要部分是：
(1)把功能和行为联系起来的电路的有限状态机和布尔模型。
(2)由基本元件综合出系统的其它一般的方法。
(3)在有限域上计算算术函数的电路和有限状态机的模型。
(4)数据通路和控制结构的模型。
(5)对各种模型和工作负荷情况下指令系统的优化。
(6)硬件可靠性：冗余，差错检测，恢复和测试。
(7)在VLSI装置设计中空间、时间和组织的折衷。
(8)各种计算模型的机器的组织：时序的、数据流、表处理、阵列处理、向量处理和报文传
送。
(9)分级设计的确定：即系统构成级、程序级、指令系统级、寄存器级和门级。
3.设计
体系结构领域的设计与实验的上要内容是：
(1)快速计算的硬件单元。例如算术函数单元、高速缓冲存储器。
(2)所谓冯.依曼机器(单指令序列存贮程序式计算机)：简单指令系统计算机(RIsc)和复杂
指令系统计箅机(CISC)实现。
(3)存储和记录信息、检测和改正差错的有效方法。
(4)对差错的特殊处理途径：恢复、诊断、重构和后备过程。
(5)为VISI电路设计的计算机辅助设计(CAD)系统和逻辑模拟、版图生成程序、故障诊断、
硅编译器。
(6)各种计算模型的机器实现；如数据流、树形、LISP、超立方(hypercube)、向量和多微
处理机。
(7)超级计算机，如Cray和Cyber机。

四、数值和符号计算
    本领域研究有效和精确地求解由系统的数学模型导出的方程的一般方法。基本问题包
括：我们怎么才能用有穷离散过程去精确地逼近连续或无穷的过程?我们怎么处理逼近导致
的误差?怎样才能按照给定精度很快地解出给定类型的方程?怎样对方程进行符号运算，例
如积分、微分和化简为最小项等?怎祥把这些问题的回答加入到有效的、可靠的、高质量的
数学软件包中去?
1.理论
数值和符号计算领域的理沦的主要部分是：
(1)数论
(2)线性代敬
(3)数值分析
(4)非线性力学
(5)微积分、实分析、复分析和代数等支持领域。
2．抽象
数值和符号计算领域抽象的主要部分是：
(1)把物理问题形式化为连续的(有时离散的)数学模型。
(2)连续问题的离散逼近。线性和非线性系统解的向后误差分析、误差传播和稳定性。特殊
情况下的特殊方法，例如快速富里叶变换和泊松解答器。
(3)可由正规网孔和边界值给定的大类问题的有限元模型，相应的迭代方法和收敛理论：直
接、隐含、多栅格、收敛率。并行解法。数值积分时自动格栅精炼。
(4)符号积分和微分
3．设计
数值和符号计算领域设计和实验的主要内容是：
(1)高级问题形式化系统，如CHEM和WEB。
(2)为线性代数、常微分方程、统计、非线性方程和优化而特殊设计的程序库和程序包，例
如LINPACKK，EISPACK，ElLPACK。
(3)将有限元算法映射到特定结构的方法  例如，这些特定结构可能是超立方体上的多栅格
。
(4)符号运算，例如MACSYMA和REDUCE，能进行有力的非显然的运算，特别是微分、积分和
表达式到最小项的简化。



--

※ 来源:．南京大学小百合站 http://bbs.nju.edu.cn [FROM: 218.247.128.195]
--
※ 转载:．南京大学小百合站 bbs.nju.edu.cn．[FROM: 211.80.38.17]