分类号图论密级公开UDC081202编号
计算机科学与技术学院
离散数学及其应用结课论文
图划分方法及其在社会网络分析和佩奇网站排名的应用
李英儒涂超杨凯航张蔚樊哲
指导教师张爱华教授
华中科技大学计算机科学与技术学院
班级计算机科学2013创新实验班
学科专业名称计算机科学与技术
学科名称离散数学及其应用论文提交日期2014年11月学院名称计算机科学与技术学院
学校名称华中科技大学
Typeset by Ying-Ru Li using L A T E X2εat November20,2014 With package CASthesis v0.2of CT E https://www.doczj.com/doc/474678017.html,
The Methods of Graph Partition
and
Its Applications in Social Network Analysis
and PageRank
Ying-Ru Li Chao Tu Kai-Hang Yang Wei Zhang Zhe Fan
Supervisor:
Prof.Ai-Hua Zhang
Computer Science and Technology
School of Computer Science and Technology
Huazhong University of Science and Technology
November,2014
Essay about Discrete Mathematics and Its Applications
of
ACM Class of Computer Science,2013
in Computer Science and Technology
摘要
本文是离散数学及其应用的结课论文，我们在本文中讨论了图划分这一经典问题和解决这一问题的一些古典与现代的算法，并且介绍了图划分问题在社会网络分析与网站评分上的应用，并提出我们自己的一些想法。
关键词：离散数学及其应用，图论，图划分，结课论文
Abstract
This paper is a thesis written by the end of the course Discrete Mathematics and Its Applications.We,in this essay,mention the classical problem of graph partition and some ancient or modern algorithms dealing with this problem. Additionally,the applications of this problem in social network analysis and pagerank are introduced as well in our own perspective.
Keywords:Discrete Mathematics and Its Applications,Graph Theory,Graph Partition,Essay in the end of Course
目录
摘要 (i)
Abstract (iii)
目录 (v)
第一章引言 (1)
1.1应用需求 (1)
1.2数学概念陈述 (1)
第二章图划分方法 (3)
2.1概括 (3)
2.2局部搜索方法 (4)
2.3多层级图划分算法 (5)
2.4谱划分和谱二分法 (5)
2.5谱聚类算法Spectral Clustering (5)
2.6其他的图划分方法 (6)
第三章应用之一社会网络分析 (7)
3.1社会网络分析及其主要内容 (7)
3.1.1关系距离及中心性分析 (8)
3.1.2小团体（子群）分析 (9)
3.2SNA的应用案例–探索人人网好友推荐系统 (9)
3.2.1读取数据 (9)
3.2.2绘制简单的好友关系网络 (10)
3.2.3子群分割 (10)
3.2.4起到中介作用的那些好友 (11)
3.2.5基于好友的一种简单推荐 (12)
vi图划分方法及其在社会网络分析和佩奇网站排名的应用
第四章应用之二图与PageRank (15)
4.1PageRank简介 (15)
4.2PageRank的思路及其意义 (15)
4.3基本数学模型 (16)
4.4佩奇改进模型 (16)
4.5图划分优化 (18)
参考文献 (19)
致谢 (21)
插图
3.1好友关系网络 (10)
3.2不同颜色标记的划分后的子群 (11)
3.3中心度散点图 (12)
3.4中间度高于3000的节点被标记出来 (13)
3.5根据子群进行的好友推荐 (13)
第一章引言
图的划分是一个非常基础的问题，在很多领域有着丰富的应用，例如在并行计算和集成电路设计问题等等都发挥着巨大作用。图的划分的目标就是把某种方式把目标图分解成若干个简单并且保持部分原有特性的子图，例如ratio cut ,normalize cut 。然而，最完美的图的划分却是个NP 完全问题，有一系列的试探算法和近似算法来解决部分问题。[9]
1.1应用需求
近几年，随着社会网络分析，数据挖掘技术，群落研究等等新兴研究的增长需求，激发了图划分问题新的研究兴趣。社会网络展现了其与常规图的不同的独有特性，而在这个小世界里的性质正好反映了现实生活的社会网络，例如一个俱乐部的新成员往往会通过他们亲密的朋友介绍给其他成员。拓扑学在图里面的应用源于并行系统的深层研究，即把一定程度的规则图按度来均分给每一个子图。作为对比，社会网络里的邻近关系的研究要联系到整个网络，而整个网络展示了一个强大的小型世界的特征，小型世界的特点告诉我们强大的群落结构会影响到群算法，不幸的是，这个关键的性质在现存的划分方法中大都没被考虑。
1.2数学概念陈述
在数学上，一个图G ,如果它有V 个结点，E 条边，即G =(V,E )，可以被分成若干更小的部分，设V 1,V 2,...,V k 是G 的顶点集的一个k ?部划分。用|V i |来表示V i 的边数，如果?1≤|V i ?V j |≤1,1≤i,j ≤k ，且当i =j 时V i ∩V j =?,V 1∪V 2∪...∪V k =V ，则称它是平衡的。在k ?部划分中，?1≤|V i ?V j |≤
1,1≤i,j ≤k ，由此可知|G |k ?1≤V i ≤|G |k
，因此各子图的边数均是均匀分配的，最大相差不会超过1.当k =2时，我们称为平衡二部划分。一般地，我们讨论的问题是建立在图的平衡划分上的。给定G 的一个k ?部划分V 1,V 2,...,V k 我
2图划分方法及其在社会网络分析和佩奇网站排名的应用们用e(V i)来表示导出子图V i的边数,且令
e(V1,V2,...,V k)=
k
∑
i=1
e(V i)
通常用e(V1,V2,...,V k)来表示k?部划分的大小。我们所关注的其中一类问题是寻找给定图G的一个k?部平衡划分V1,V2,...,V k使得e(V1,V2,...,V k)达到最小，例如在实现并行计算时，要将相互依赖较大的子任务划分在不同的并行集中，而将相互依赖较小的子任务进行并行化运算。与此相反,我们另外所考虑的一类问题是“公平”划分问题：给定一个图G,求它的一个划分e(V1,V2,...,V k),使e(V1,V2,...,V k)尽可能达到最大，例如在社会网络分析中将拥有更多共同特征的或拥有更多联系的人划分在一个子群中。
第二章图划分方法
2.1概括
由于图的划分问题实在太困难，实际上的解决方案是基于试探的方法。这里有两类方法，局部法和全局法，著名的局部法有Kernighan Lin algorithm和F iduccia Mattheyses algorithm，它们都是十分高效的平衡二部划分的局部搜索策略；全局法是基于整个图的性质而不是仅仅依赖任何一个最原始的划分的子图而言的方法，其最常见的例子是谱图划分（谱图是指通过图的矩阵（邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵等）表示，建立的图的拓扑结构）。
4图划分方法及其在社会网络分析和佩奇网站排名的应用
2.2局部搜索方法
Kernighan-Lin algorithm
1￡这个算法是O(n2log(n))复杂度的解决图划分问题的渐进式算法。
2￡下面是这个算法的伪代码：（From wikipedia）
3F unction Kernighan?Lin(G(V,E)):
4￡确定一个所有节点平衡的初始划分，将节点划分为A，B两个集合
5A1←A
6B1←B
7do
8￡对于每一个A1中的a和B1中的b计算所有的D的值
9for n←1to|V|/2
10do
11￡?nd a[i]from A1and b[j]from B1,
12￡such that g[n]=D[a[i]]+D[b[j]]?2?c[a[i]][b[j]]is maximal
13￡move a[i]to B1and b[j]to A1
14￡remove a[i]and b[j]from further consideration in this pass
15￡update D values for the elements of A1=A1a[i]and B1=B1b[j] 16
17￡?nd k which maximizes g max,the sum of g[1],...,g[k]
18if g max>0
19then
20￡Exchange a[1],a[2],...,a[k]with b[1],b[2],...,b[k]
21until g max<=0
22return G(V,E)
Fiduccia-Mattheyses algorithms
1￡这个算法是线性复杂度的渐进式算法相比较与上面的算法有很多新的特点：
2￡旨在减少net?cut的消耗；
3￡在划分的过程中，每次仅移动一个点；节点是有权重的；
4￡可以处理不平衡的划分，引入了一个新的平衡因素等等。
第二章图划分方法5
2.3多层级图划分算法
多层级图划分算法采用一个或多个阶段（stage）。每个阶段通过折叠点和边来减少图的大小，并且划分更小的图，然后再优化原图的划分。[7]有大量的划分和优化方法可以被用于整个的多层级方案。
2.4谱划分和谱二分法
给定一个有邻接矩阵A的图，邻接矩阵中Aij表示一条连接节点i,j的边。和一个度数矩阵D（是一个对角矩阵），对角线上每个项代表某个节点的度数。矩阵的拉普拉斯算子L被定义为
L=D?A
一个图G=(V,E)比率切分(ratio?cut partition)被定义为一个V的划分，V被划分为不相连的U和W，使切
cut(U,W)
|U||W|
的耗费最小。在这种情况下，L的倒数第二小的特征值λ，产生了一个最优比率切分的c的下界c≥λ/n。特征向量V与特征值λ有关被称作费德勒向量，将图平分为两个部分是基于对应向量项的的标志来进行的。最小切分划(cut partition)对于需要被划分的群体(communities)数目未知，或者划分大小未知的的情况下是不能使用的。
2.5谱聚类算法Spectral Clustering
在上一个方法求出矩阵的拉普拉斯算子后。
1.求L矩阵的前k个本征值和本征矢，将数据点投影到一个k维空间。第i本征矢的第j个值，就表示第j个点在k维空间中第i维的投影。就是说如果把k个特征矢量并成一个N×k的矩阵，则每一行代表一个点在k维空间的坐标。
2.根据每个数据点的k维空间坐标，使用K?means或者其它聚类算法在k维空间对数据进行聚类。
谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。只要将要研究的对象以及对象之间的关系转化为图模型，再用邻接矩阵转化为谱图模型，就可以用谱聚类算法了。
6图划分方法及其在社会网络分析和佩奇网站排名的应用
例如在自然语言处理中，[5]如果以文档作为处理的基点，那么先提取每篇文章的一些关键词，并将每个关键词抽象为图中的点，而点与点之间的边用两个关键词在同一篇文章中的共现(co?occurrence)概率来表示，这样一来关键词图(Keygraph)就做好了。在经过监督的SVM或非监督的（谱）聚类，将关键词以联系的紧密程度划分到不同的群落中，这样就可将数据集中的文章主题或潜在主题提取出来。[13][12][11]
2.6其他的图划分方法
自旋模型被用在了聚类多元数据中，其中相似性被转化为耦合强度[10]，基态自旋的值地配置可以直接被转化为群体communities。由此，一个图被划分从而减小已经被划分的图的哈密尔顿算子。哈密尔顿算子是通过下面四种“奖励”(rewards)和“惩罚”(penalties)来实现的：
1.同一组内部节点间的边奖励。
2.同一组失去得边惩罚。
3.不同组之间的边惩罚。
4.奖励不同组之间没有的链接
其他的一些方法把图划分问题表示为多准则优化问题，这种问题可以被一种局部化方法解决，这种方法被解释在一个每个节点都可以决定划分博弈论(Game T heory)框架中。
第三章应用之一社会网络分析
3.1社会网络分析及其主要内容
社会网络研究发端于20世纪20、30年代英国人类学的研究，其基本事实是每个行动者都与其他行动者有或多或少的关系，社会网络分析就是要建立这些关系的模型，力图描述群体关系的结构，研究这种结构对群体功能或者群体内部个体的影响。美国社会心理学家莫雷诺（Moreno）创立的社会测量法为社会网络分析奠定计量分析基础。发展至今，社会网络分析已经被广泛应用于网络社会关系发掘、支配类型发现（关键因素）以及信息流跟踪，通过社会网络信息来判断和解释信息行为和信息态度。而且作为一种跨学科的研究方法，在社会学、心理学、经济学、信息科学、系统科学与计算机科学的共同努力下，使得社会网络分析从一种隐喻成为一种现实的研究范式[1]。21世纪后,人们越来越多地通过网络进行沟通、交流以及形成人际关系。在这样的时代背景下，从人类学、心理学、社会学、传播学研究、数学以及统计学领域中发展起来的社会网络分析开始用于网络时代虚拟社区中人际交流的研究[2]。社会网络指的是社会行动者（social actor）及其间的关系的集合[3]。换句话说，一个社会网络是由多个点（社会行动者）和各点之间的连线（行动者之间的关系）组成的集合。社交网络图用结点代表信息的传递者和接受者，箭头表示信息传递的方向，连线的粗细表示信息传递的频率或传递的信息量，整体反映了组内成员之间信息流动的统计特征。用点和线来表达网络，这是社会网络的形式化界定。但是如果社会网络图涉及的点很多，图形就相当复杂，很难分析出关系的结构，在这种情况下，可以用矩阵方法来描述社会关系网络。社会网络分析（SNA）是研究一组行动者的关系的研究方法。一组行动者可以是人、社区、群体、组织、国家等，他们的关系模式反映出的现象或数据是网络分析的焦点。从社会网络的角度出发，人在社会环境中的相互作用可以表达为基于关系的一种模式或规则，而基于这种关系的有规律模式反映了社会结构，这种结构的量化分析是社会网络分析的出发点。因此，社会网络分析关注的焦点是关系和关系的模式，采用的方式和方法从概念上有别于传统的统计分析和数据处理方法。社会网络分析假定：在互动的单位之间存在的关系非常
8图划分方法及其在社会网络分析和佩奇网站排名的应用
重要。这种关系是资源传递或信息流动的“渠道”；既可能为个体的行动提供机会，也可能限制其行动。分析社会网络，主要是研究社会实体的关系连结以及这些连结关系的模式、结构和功能。社会网络分析被用于描述和测量行动者之间的关系或通过这些关系流动的各种有形或无形的东西，比如信息、资源等。根据分析的着眼点不同，社会网络分析可以分为两种基本视角：关系取向（relational approach）和位置取向（positionalapproach）。关系取向关注行动者之间的社会性粘着关系，通过社会连结（socialconnectivity）本身――如密度、强度、对称性、规模等――来说明特定的行为和过程。位置取向则关注存在于行动者之间的、且在结构上处于相等地位的社会关系的模式化。它讨论的是两个或两个以上的行动者和第三方之间的关系所折射出来的社会结构，强调用“结构等效”来理解人类行为。我们应用社会网络分析可以开展以下方面的研究：
3.1.1关系距离及中心性分析
3.1.1.1度（degree）
度指的是社会网络图中邻点的个数。
3.1.1.2密度（density）
密度指的是图中各个点之间关系的紧密程度，是实际分布图与完备图的差距。在一个群体的结构型态分析中，密度是一项重要变量，因为一个团体可以有紧密团体，也可以有疏离团体，一般来说，关系紧密的团体有效的合作行为较多，信息流通较容易，团体工作绩效也会较好，而关系十分疏远的团体则常有信息不通、情感支持太少、集体满意程度较低等问题。社会网络图（无向
图）的密度公式如下：
ρ=
2L
n(n?1)
其中n为图中节点的数目，L为图中线的数目。
3.1.1.3中心度（centrality）
如果一个行动者与很多其他行动者有直接的关联，该行动者就居于中心地位。因此在无向社会网络图中，一个点的度就是该点的中心度。在有向图中，中心度包括内中心度（in?centrality）和外中心度（out?centrality），分别
第三章应用之一社会网络分析9
对应“入度”和“出度”。A.Bavelas最先对中心度的形式特征进行了开创性研究[6]，验证了如下假设，即行动者越处于网络的中心位置，其影响力越大。
3.1.2小团体（子群）分析
派系（subgroup）是社群中的一小群人关系特别紧密，以至于结合成一个次团体。在一个社会网络图中，派系指的是至少包含三个点的最大完备子图。该定义意味着：
派系的成员至少包含三个点；
派系是“完备”的，即任何两点之间都是直接相关，都是邻接的；
派系是“最大”的，不能再向该派系加入新点，否则将改变“完备”这个性质。
但是上述派系的定义过于严格，不便于实际应用。有研究者对此概念进行了推广：
3.1.2.1成分（component）
如果一个点集的任何两点都可以通过一定的路径相连，这样的点集叫做成分（component）。很显然，派系比成分要严格得多，一个成分中的所有点之间不要求都是邻接的，而派系中的点都必须邻接。
3.1.2.2n?派系（n?cliques）
对于一个总图来说，如果其中的一个子图满足如下条件，就称之为n?派系：在该子图中，任何两点之间在总图中的最短距离最大不超过n。其形式化定义为：
?i,j∈N s,d(i,j)≤n
3.2SNA的应用案例–探索人人网好友推荐系统
3.2.1读取数据
之所以选择人人网作为分析的对象，很重要的一点原因在于其数据获取较为便利。数据读取过程借助命令行浏览器cURL。
10图划分方法及其在社会网络分析和佩奇网站排名的应用
图3.1:好友关系网络
3.2.2绘制简单的好友关系网络
首先，从读取到的数据集中筛选出希望分析的子集。这个子集包含了两个条件：
网络中没有自己（否则会呈现以自己为中心的分布，失去了分析的意义）； 网络中的用户都是自己的好友。
从图3.1中可以直观地看出，好友网络存在一定的人群分割，可以尝试对这个网络进行一些分析以提取出其中相对独立的子群（或者称为社群）。
3.2.3子群分割
信息的分类和过滤是社会网络服务的一项特征，例如人人网对好友关系有一套自己的分类方式，用户可以自行对好友进行分组，从而对信息的收发做分组的管理。但是作为用户却未必能够养成并保持这种分组的习惯。与此同时我们揣测，作为真实关系的线上反映，人人网的好友网络是能够自动呈现出一定的人群分割的，而在社会网络分析中，对网络成分的分析也确实是一项重点。
第三章应用之一社会网络分析11
图3.2:不同颜色标记的划分后的子群
通过分析网络的结构，提取出其中的子群，能够让我们更好地理解这个网络的组成方式，从而更好地管理和利用信息流。为了在网络图中展示这些子群，我们采用不同的颜色来标记他们。
从图3.2中可以直观地看出好友网络已经被划分为若干相对独立的子群。这也与我们对人人网（尤其是其前身校内网）的直观理解相符合――人人网的好友关系基本都是真实线下关系的反映，很自然地可以划分为初中同学、高中同学、大学同学，等等（例如网络的上半部分为小学及中学的同学，下半部分为大学同学，而左侧的五个节点，那是统计之都的同学们。）更进一步地，可以对照网络图来考察各个子群成员的分布情况。例如大学数学系同学（下方蓝色点）的链接较为紧密，而非数学系的大学同学（下方红色点）的分布则相对分散。
3.2.4起到中介作用的那些好友
在社会网络分析中，对节点的中介作用有一个经典的刻画叫做“中间度”。中间度衡量了节点作为中介的程度，当网络中某个个体的中间度较大时，我们
12图划分方法及其在社会网络分析和佩奇网站排名的应用
图3.3:中心度散点图
认为它在很大程度上起到了中介和沟通的作用。常用的中间度的定义是
∑g
iV j
,(i=j and i,j=V)
g ij
其中g ij表示联通i与j两个节点的捷径的条数，g iV j则表示联通i与j两个节点且经过V的捷径的条数（所谓捷径，就是两个节点之间的最短路径）。
根据得到的中间度散点图3.3，我们人为地选择了3000作为分界点，选取中间度高于3000的节点并在图形中利用节点的大小展示出来，如图3.4。
3.2.5基于好友的一种简单推荐
最后，我们也做了基于好友关系的好友推荐，如图3.5所示，推荐的逻辑与人人网自身的推荐逻辑相同：根据共同好友的数量来进行推荐。在具体实现的时候，仍然需要考虑用户同名的情况。
浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”
第三章集合论基础 1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。 ⑴{a}∈A T ⑵?({a}? A) F ⑶c∈A F ⑷{a}?{{a,b},c} F ⑸{{a}}?A T ⑹{a,b}∈{{a,b},c} T ⑺{{a,b}}?A T ⑻{a,b}?{{a,b},c} F ⑼{c}?{{a,b},c} T ⑽({c}?A)→(a∈Φ) T 2、证明空集是唯一的。（性质1：对于任何集合A，都有Φ?A。） 证明：假设有两个空集Φ1 、Φ2 ，则 因为Φ1是空集，则由性质1得Φ1 ?Φ2 。 因为Φ2是空集，则由性质1得Φ2 ?Φ1 。 所以Φ1=Φ2 。 3、设A={Φ},B=P(P(A)).问：(这道题要求知道幂集合的概念) a)是否Φ∈B?是否Φ?B? b)是否{Φ}∈B? 是否{Φ}?B? c)是否{{Φ}}∈B? 是否{{Φ}}?B? 解：设A={Φ}，B=P(P(A)) P(A)= {Φ,{Φ}} 在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a ,{Φ}=b, 于是{Φ,{Φ}}={a,b} B=P(P(A))=P({a,b}) ={B0, B1 , B2 , B3 }={B00, B01,B10 ,B11}={Φ, {b}, {a}, {a,b}} 然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ} ,{{Φ}}, {Φ,{Φ}}} 以后熟悉后就可以直接写出。 a) Φ∈B Φ?B b) {Φ}∈B {Φ} ? B c) {{Φ}}∈B {{Φ}}?B a)、b)、c)中命题均为真。 4、证明A?B ? A∩B=A成立。 证明：A∩B=A ??x(x∈A∩B ?x∈A) ??x((x∈A∩B → x∈A)∧(x∈A→ x∈A∩B)) ??x((x?A∩B∨x∈A)∧(x?A∨x∈A∩B)) ??x((?(x∈A∧x∈B)∨x∈A)∧(x?A∨(x∈A∧x∈B)) ??x(((x?A∨x?B)∨x∈A)∧(x?A∨(x∈A∧x∈B))) ??x(T∧(T∧( x?A∨x∈B))) ??x( x?A∨x∈B)??x(x∈A→x∈B)? A?B 5、(A-B)-C=(A-C)-(B-C) 证明：任取x∈(A-C)-(B-C) ?x∈(A-C)∧x?(B-C) ?(x∈A∧x?C)∧?(x∈B∧x?C) ?(x∈A∧x?C)∧(x?B∨x∈C) ?(x∈A∧x?C∧x?B)∨(x∈A∧x?C∧x∈C) ?x∈A∧x?C∧x?B?x∈A∧x?B∧x?C ?(x∈A∧x?B)∧x?C ?x∈A-B∧x?C?x∈(A-B)-C 所以(A-B)-C=(A-C)-(B-C)
泛函分析课程论文 数学与计算科学学院 09数本2班 黄丽萍 2009224725 大四新学年开始了，我们也开始学习了一门综合性及专业性强的课程——泛函分析。首先，理解下“泛函分析”这个概念。 泛函分析是20世纪发展起来的一门新学科，其中泛函是函数概念的推广，对比函数是数与数之间的对应关系，我们发现泛函是函数和数之间的对应关系。在学习泛函分析前，我们先确定学习目标：理解和掌握“三大空间和三大定理”。所以在接下来的两章内容的学习中，我们将先学习“两大空间”——度量空间和赋范线性空间及其相关知识（第七章和第八章）。在学习中慢慢体味泛函分析的综合性及专业性。 第七章的标题已经明确给出了学习任务——度量空间和赋范线性空间。 §1 度量空间 §1.1 定义：若X 是一个非空集合，:d X X R ?→是满足下面条件的实值函数，对于,x y X ?∈，有 （1）(,)0d x y =当且仅当x y =； （2）(,)(,)d x y d y x =； （3）(,)(,)(,)d x y d x z d y z ≤+， 则称d 为X 上的度量，称(,)X d 为度量空间。 【理解】度量空间就是：集合+距离；（满足非负性、对称性及三点不等式） 其实度量空间是在实变函数中接触的知识，但其在泛函分析学科中的重要性，我们可以通过度量空间的进一步例子来感受。 §1.2 度量空间的进一步例子 例：1、离散的度量空间(,)X d ，设X 是一个非空集合，,x y X ?∈，当1,(,)0,=x y d x y x y ≠?=??当当。
2、序列空间S ，i =1i |-|1(,)21+|-|i i i i d x y ξηξη∞ =∑是度量空间 3、有界函数全体()B A ，(,)sup|(t)-(t)|t A d x y x y ∈=是度量空间 4、连续函数[a,b]C ，(,)max|(t)-(t)|a t b d x y x y ≤≤=是度量空间 5、空间2l ，122=1(,)[(-)]k k i d x y y x ∞=∑是度量空间 §1.3度量空间中的极限，稠密集，可分空间 §1.3.1极限：类似数学分析定义极限，如果 {}n x 是(,)X d 中点列，如果?x X ∈，使n l im (,)=0n d x x →∞，则称点列{}n x 是(,)X d 中的收敛点列，x 是点列{}n x 的极限。 同样的类似于n R ，度量空间中收敛点列的极限是唯一的。 §1.3.2稠密子集与可分空间:设X 是度量空间，E 和M 是X 中两个子集，令 M M M ?表示的闭包，如果E ,那么称集M 在集E 中稠密，当E=X 时，称M 为X 的一个稠密子集，如果X 有一个可数的稠密子集，则称X 是可分空间。 即：{},n n M E x E x M s t x x n ??∈??→→∞在中稠密对 §1.3.3 例子 1、 n 维欧氏空间n R 是可分空间； 2、 坐标为有理数的全体是n R 的可数稠密子集； 3、 l ∞是不可分空间。 §1.4 连续映射 §1.4.1定义：设 (,),(,),> 0,X (,) < (T ,T ) < ,o o o o X X d Y Y d T X Y x X d x x x d x x T x εδδε==∈ 是两个度量空间，是到中映射，如果对于任意给定的正数，存在正数 使对 中一切满足 的 ，有 则称在连续。
数学小论文范文 随着课程改革的不断深入，新课程理念与课堂教学实践正在逐步融合，逐步改变了以教师、课堂或课本为中心的局面，促进了学生 创新意识与实践能力的发展，学生的学习产生了实质性的变化。那么，在课堂教学中如何使学生主动探索在课堂上显现呢?下面结合本 人的教学实践，谈几点体会及做法。 一给学生提供可探索的材料和可探索的学习内容 二给学生提供良好的学习背景和可探究的学习情境 在课堂教学中，教师应结合教学内容为学生的学习，创设良好的学习背景和可探究的学习情境，让学生在数学知识的广阔背景中更 好地建构知识的意义，并感受数学与生活实际的密切联系，体会数 学的价值，让学生的数学学习活动真正变为学生自己探究的创新过程。如，在教学“百分数的意义”时，可为学生创设这样的学习背景：“有甲乙丙三位工人师傅，甲每加工25个零件，有23个及格，乙加工20个零件，有19个及格，丙加工50个零件，有47个及格。如果有一批零件要其中一位师傅加工，你会选择谁?”通过探究，使 学生认识到这个现实问题实际上可转化成“求谁的合格率高”这一 数学问题。又如，教学“分数的基本性质”时，我有意识地给学生 提供以下的可探究学习情境：上课开始，我拿着一捆36本课外书， 从容地走进课堂。同学们在猜想：这节课老师让我们看课外书了。 于是我指着这捆课外书说：“这36本课外书，我要分给你们三个小组，要求让第一组分得这捆书的三分之一，第二小组分得这捆书的 六分之二，第三小组分得这捆书的九分之三，请同学们说一说，这 样分法合理不合理，谁分得多?谁分得少?结果分完没有?”这样问题 的创设，调动了学生思维的积极性，探究活动立即在课堂上显现， 有的按照自己的思路去画线段图，有的一会儿测量，有的一会儿皱 眉思索，兴趣盎然，学生会心地笑了，一样多。这时，学生又产生 困惑，为什么会一样多呢?最后经过引导探究，得出“分数的基本性质”。
第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。
泛函分析学习心得 学习《实变函数论与泛函分析》这门课程已有将近一年的时间，在接触这门课程之前就已经听闻这门课程是所有数学专业课中最难学的一门，所以一开始是带着一种“害怕学不好”的心理来学.刚开始接触的时候是觉得很难学，知识点很难懂，刚开始上课时也听不懂，只顾着做笔记了.后来慢慢学下来，在课前预习、课后复习研究、上课认真听课后发现没有想象中的那么难，上课也能听懂了.因此得出了一个结论：只要用心努力去学，所有课程都不会很难，关键是自己学习的态度和努力的程度. 在学习《泛函分析》的前一个学期先学习了《实变函数论》，《实变函数论》这部分主要学习了集合及其运算、集合的势、n 维空间中的点集、外测度与可测集、Lebesgue 可测集的结构、可测函数、P L 空间等内容，这为这学期学习《泛函分析》打下了扎实的基础.我们在这个学期的期中之前学习的《泛函分析》的主要内容包括线性距离空间、距离空间的完备性、内积空间、距离空间中的点集、不动点定理、有界线性算子及其范数等.下面我谈谈对第一章的距离空间中部分内容的理解与学习： 第一章第一节学习了线性距离空间，课本首先给出了线性空间的定义及其相关内容，这与高等代数中线性空间是基本一样的，所以学起来比较容易.接着是距离空间的学习，如果将n 维欧氏空间n R 中的距离“抽象”出来，仅采用性质，就可得到一般空间中的距离概念： 1.距离空间（或度量空间）的定义： 设X 为一集合，ρ是X X ?到n R 的映射，使得使得X z y x ∈?,,，均满足以下三个条件： （1）)(0,≥y x ρ，且)(0,=y x ρ当且仅当y x =（非负性） （2）)()(x y y x ,,ρρ=（对称性） （3）)()()(z y y x z x ,,,ρρρ+≤（三角不等式）， 则称X 为距离空间（或度量空间），记作)(ρ,X ，)(y x ,ρ为y x ,两点间的距离. 学习了距离空间定义后，我们可以验证：欧式空间n R ，离散度量空间，连
离散数学论文 —浅谈离散数学的学习及其在计算机中的应用一、对离散数学学习的认识 通过这一学期的学习，我对这门课程有一些初步的了解，现在的心情和当初也很不相同。在听过老师讲解以后，我觉得第一部分的数理逻辑自己都能很好的掌握。后面的开始深入一些，对于好多以前没有接触过的名词定义不能马上理解，但是只要跟着老师的思维走，上课认真听讲，课后看一下书本就能懂。有了这些认知，我觉得这门课的难点在于课程比较枯燥，好多理论的知识需要我们去理解。前五章主要是认识逻辑语言符号，了解了数理逻辑的特点，并做一些简单的逻辑推理和运算。第二部分讲的是集合论。在这一部分中进一步认识、运用数理逻辑语言，熟练强化练习，深入理解。这一章的难度相较于前几章要繁琐些，有很多的符号转换，运算，运算过程很复杂。对于计算能力不强的我来说，这一章或许是最吃力的，即使知道原理也需要通过大量的练习强化巩固，而这其中用到的还有线性代数里面的矩阵。在第三部分的代数结构中主要学习了代数系统、群与环，其中二元运算和代数系统有点难度，较以往学习非常吃力！第五部分的图论可以归结为本书的重点之一，“图”“树及其应用”又是其中的重中之重。它的用途非常广泛，并且应用于我们整个日常生活中。比如：一个计算机芯片需要多少层才能使得同一层的路线互不相交？一位流动推销员要以怎样的顺序到达每一个城市才能使得旅行时间最短？这些问题以及其他一些实际问题都涉及“图论”。 这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间
联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。 树是指没有回路的连通图。它是连通图中最简单的一类图，许多问题对一般连通图未能解决或者没有简单的方法，而对于树，则已圆满解决，且方法较为简单。而且在许多不同领域中有着广泛的应用。例如家谱图就是其中之一。如果将每个人用一个顶点来表示，并且在父子之间连一条边，便得到一个树状图。 通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 本以为枯燥乏味的离散数学竟然会是贴近生活是我意想不到的，这些历史难题等等，都让我对它产生了一定的兴趣，虽然不可否认的是，对我来说它确实是一门很难很深奥很抽象的课程，但是仍然不减我对图论产生的兴趣，或许这也就是我选择这门课程最大的收获吧。 二、离散数学在计算机中的应用 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们计算机专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培
我的离散数学学习心得 (1) -- 一类抽象代数题的解题思路 学习离散数学已经有一段时间了，书读了不少，题也做了一些。最近又常在群里和研友们讨论离散数学中的问题。所以对离散数学也有了一些心得和体会。在今后的一段时间里，我会不定期的写一些小的经验总结，以供后来人参考。：） 因为是“心得体会”，所以多半是想到什么写什么，组织和条理方面可能会比较差。还望各位看官多多包涵。；） 这次我们来讨论一类代数问题的解题思路。 问题：设R为含幺环，求证：对任意a,b∈R，若1-ab可逆，则1-ba也可逆。 分析： 我们知道，证明问题的方法大致可以分为两类：构造性证明和存在性证明。前者要求给出一个切实的方法，找出符合命题要求的元素（在这道题中，就是找到1-ba的逆元）。后者则只证明这样的元素必然存在，但并不给出切实的寻找方法。反证法是存在性证明的基本方法。 无论打算采用是哪种证明方法，确认一下我们可以使用的前提条件总是必要的。 就这道题而言，我们可以使用这些前提： 1、R是含幺环。这就意味着R对加法构成Abel群（从而我们可以自由地使用加法交换律、加法消去律、加法逆元等），R对乘法构成独异点（从而可以使用乘法单位元1），当然还有乘法对加法的分配律。 2、1-ab是可逆的，这就是说，存在c∈R，使得c(1-ab)=(1-ab)c=1。移项后得到：cab=abc=c-1。 需要注意的是： 1、在题设中没有假设R的可换性（事实上，如果R可换的话，整个问题就没有任何难度了），也没有假设a、b是可逆的。所以，在解题时，不能使用乘法交换律，也不能随便使用a、b的逆元（除非已经证明了它们的存在性）。 2、如果没有1-ab可逆这个条件，肯定是推不出1-ba可逆的（我们在环中可以找到太多的反例）。所以，cab=abc=c-1将是解题的关键。观察这个式子，我们注意到，它提供了在c的参与下，移动和消去ab 的方法。 我们的目的是，证明存在这样的一个元素d∈R，满足(1-ba)d=d(1-ba)=1。 初看到这道题，我们并不知道使用构造性证明容易还是使用反证法容易。 不过推理一下我们可以发现，如果要使用反证法的话，我们需要反设1-ba不存在乘法逆元，然后由此推出1-ab也不可能有逆元（或者推出R不是含幺环）。 但反设1-ba不存在乘法逆元后，我们到底能推出哪些结论来呢？似乎很少。我们甚至连“对任意x∈R，必有x(1-ba)≠1”这样简单的情况都难以证明（因为我们只假设了1-ba没有“乘法逆元”，并不能由此推出1-ba没有“乘法左逆元”）。 另一方面，利用等式cab=abc=c-1直接构造出一个1-ba的逆元应该一个比较有希望的方法。 这时，我们可以“取巧”了。注意到： 1、如果我们相信题目给的命题没有错的话，我们只要找到1-ba的左逆元（或者右逆元）就基本完成任务了（虽然最终书写证明时，我们需要证明我们找到的元素既是左逆元又是右逆元）。因为如果一个元素的左右逆元都存在的话，它的左右逆元是唯一且相等的（所以，1-ba确实可逆，而我们又找到了它的一
泛函分析作业 数学系08级5班 08020170 赵英杰
泛函分析主要内容 泛函分析是20世纪30年代形成的数学分科。是从变分问题，积分方程和理论物理的研究中发展起来的。它综合运用函数论，几何学，现代数学的观点来研究无限维向量空间上的函数，算子和极限理论。它可以看作无限维向量空间的解析几何及数学分析。主要内容有拓扑线性空间等。泛函分析在数学物理方程，概率论，计算数学等分科中都有应用，也是研究具有无限个自由度的物理系统的数学工具。泛函分析是研究拓扑线性空间到拓扑线性空间之间满足各种拓扑和代数条件的映射的分支学科。 泛函分析是分析数学中最“年轻”的分支，它是古典分析观点的推广，它综合函数论、几何和代数的观点研究无穷维向量空间上的函数、算子、和极限理论。他在二十世纪四十到五十年代就已经成为一门理论完备、内容丰富的数学学科了。 一、度量空间和赋范线性空间 1、度量空间 现代数学中一种基本的、重要的、最接近于欧几里得空间的抽象空间。19世纪末叶，德国数学家G.康托尔创立了集合论，为各种抽象空间的建立奠定了基础。20世纪初期,法国数学家M.-R.弗雷歇发现许多分析学的成果从更抽象的观点看来,都涉及函数间的距离关系,从而抽象出度量空间的概念。 度量空间中最符合我们对于现实直观理解的是三维欧氏空间。这个空
间中的欧几里德度量定义两点之间距离为连接这两点的直线的长度。 定义：设X为一个集合，一个映射d：X×X→R。若对于任何x,y,z属于X，有 （I）（正定性）d(x,y)≥0,且d(x,y)=0当且仅当 x = y； （II）（对称性）d(x,y)=d(y,x)； （III）（三角不等式）d(x,z)≤d(x,y)+d(y,z） 则称d为集合X的一个度量（或距离）。称偶对（X，d）为一个度量空间，或者称X为一个对于度量d而言的度量空间。 2、赋范线性空间 泛函分析研究的主要是实数域或复数域上的完备赋范线性空间。这类空间被称为巴拿赫空间，巴拿赫空间中最重要的特例被称为希尔伯特空间。 （一）、希尔伯特空间 希尔伯特空间可以利用以下结论完全分类，即对于任意两个希尔伯特空间，若其基的基数相等，则它们必彼此同构。对于有限维希尔伯特空间而言，其上的连续线性算子即是线性代数中所研究的线性变换。对于无穷维希尔伯特空间而言，其上的任何态射均可以分解为可数维度（基的基数为50）上的态射，所以泛函分析主要研究可数维度上的希尔伯特空间及其态射。希尔伯特空间中的一个尚未完全解决的问题是，是否对于每个希尔伯特空间上的算子，都存在一个真不变子空间。该问题在某些特定情况下的答案是肯定的。 （二）、巴拿赫空间
泛函分析课程总结 数学与计算科学学院 09数本5班 符翠艳 2009224524 序号：26 一．知识总结 第七章 度量空间和赋范线性空间 1. 度量空间的定义：设X 是一个集合，若对于X 中任意两个元素,x y ，都有唯 一确定的实数(),d x y 与之相对应，而且满足 ()()()()()()()1,0,,0=;2,,;3,,,,d x y d x y x y d x y d y x d x y d x z d z y z ≥=?? ??=????≤+?? 、的充要条件是、、对任意都成立。 则称d 为X 上的一个度量函数，（d X ,）为度量空间，),(y x d 为y x ,两点间的度量。 2. 度量空间的例子 ①离散的度量空间(),X d 设X 是任意的非空集合，对X 中任意两点,x y X ∈,令 ()1,,0,x y d x y x y ≠?? =??=?? 当当 ②序列空间S 令S 表示实数列（或复数列）的全体，对S 中任意两点 ()()12n 12,,...,,...,,...,,...n x y ξξξηηη==及，令 ()11,21i i i i i i d x y ξηξη∞ =-=+-∑ ③有界函数空间B （A ） 设A 是一给定的集合，令B （A ）表示A 上有界实值（或复值）函数全体，对B （A ）中任意两点,x y ，定义 (),()()sup t A d x y x t y t ∈=- ④可测函数空间m(X) 设m(X)为X 上实值（或复值）的L 可测函数全体，m 为L 测度，若()m X ≤∞，对任意两个可测函数()()f t g t 及，令 ()()(),1()() X f t g t d f g dt f t g t -=+-?
《离散数学》课程总结论文 专业：11级计科系计本三班姓名：学号：1104013045 一．课程小结 从学离散数学这门课程开始，到现在学期末也已经有了一个学期的认识。以下是对离散数学这门课程的总结： 第一部分：数理逻辑 1.首先我们学习了命题逻辑的基本概念。其实这一部分的内容在高中时已经讲过。其次.命题公式及其赋值，这一小结主要讲的是什么是合式公式以及命题的解释和成真赋值、成假赋值等。 2.命题逻辑等值演算。在这一章节中主要介绍了一些重要的等值公式，例如德摩根律和蕴含等值式等，然后介绍的就是什么是析取范式与析取范式，又进一步的引出主析取范式与主合取范式的概念。另外一个知识点为连接词的完备集。 3.命题逻辑的推理形式。就是如何去证明推理的正确性。这需要我们记住一些重要的推理定律。然后是自然推理系统。推理的一些构造证明的方法有附加前提证明法和归谬法等等。 4.一阶逻辑基本概念。主要说的是一阶逻辑命题的符号化和一阶逻辑公式及其解释。 5.一阶逻辑等值演算与推理，这节知道量词如何消去和一些基本的量词等值式就可以了。 第二部分：集合论 1.集合代数。这一章节中首先讲的是集合的基本概念和运算等等，其中大部分的知识我们高中的时候都已经接触过了。其中要知道什么是绝对补集，对称差集和绝对补集就可以了。 2.二元关系。要知道二元关系首先要知道什么是有序对和笛卡尔集，这是二元关系的基础。然后要清楚二元关系的表示方法有三种，即集合表达式、关系矩阵和关系图。知道了二元关系，紧接着就是关系的运算和性质。关系的性质有自反性、反自反性、对称性、反对称性和传递性。还有就是关系的闭包，其中包括自反闭包、对称闭包和传递闭包。最后一点就是偏序关系和等价关系，还需要知道哈斯图并且会画哈斯图。 第三部分：代数结构 1.代数系统。首先要能够判断一个运算是否为一个集合上的二元运算。在二院运算的基础上，要知道和能够判断单位元、零元和逆元。2群与环。在这一小节中首先要会判断一个代数系统是否为群。在也是这一章节的核心内容。如果一个代数系统，其二元运算时可结合的，又含有单位元，并且集合中的每个元素都有逆元，则此代数系统叫做群。 第四部分：图论 1.图的基本概念。其实在这一章节中，内容多数为一些基本概念。这就需要我们熟练的去掌握。只有清楚了概念才能够做题，比如说什么是有向图、零图、无向图和空图等等。另外图的矩阵表示在这一章节是尤为重要的。其中包括无向图的关联矩阵、有向图的关联矩阵、有向图的邻接矩阵和可达矩阵等。 2.欧拉图与哈
离散数学学习总结 一、课程内容介绍： 1．集合论部分： 集合论是离散数学中第一个抽象难关，在老师的生动讲解下，深入浅出，使得集合论成了相当有趣的知识。只是对于以后的应用还不是很了解，感觉学好它很重要。直观地说，把一些事物汇集到一起组成一个整体就叫集合，而这些事物就是这个集合的元素或成员。例如： 方程x2－1＝0的实数解集合； 26个英文字母的集合； 坐标平面上所有点的集合； 集合通常用大写的英文字母来标记，例如自然数集合N(在离散数学中认为0也是自然数)，整数集合Z，有理数集合Q，实数集合R，复数集合C等。 表示一个集合的方法有两种：列元素法和谓词表示法， 如果两个集合的交集为，则称这两个集合是不相交的。例如B和C 是不相交的。 两个集合的并和交运算可以推广成n个集合的并和交： A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An} A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An} 2．关系 二元关系也可简称为关系。对于二元关系R，如果
得到新的关系R'，使得R'具有自反性。但又不希望R'与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R'就称为R的自反闭包。通过添加有序对来构造的闭包除自反闭保外还有对称闭包和传递闭包。 3．代数系统 代数结构也叫做抽象代数，主要研究抽象的代数系统。抽象的代数系统也是一种数学模型，可以用它表示实际世界中的离散结构。例如在形式语言中常将有穷字符表记为∑，由∑上的有限个字符（包括0个字符）可以构成一个字符串，称为∑上的字。∑上的全体字符串构成集合∑*。设α,β是∑*上的两个字，将β连接在α后面得到∑*上的字 αβ。如果将这种连接看作∑*上的一种运算，那么这种运算不可交换，但是可结合。集合∑*关于连接运算就构成了一个代数系统，它恰好是抽象代数系统--半群的一个实例。抽象代数在计算机中有着广泛的应用，例如自动机理论、编码理论、形式语义学、代数规范、密码学等等都要用到抽象代数的知识。代数结构的主要研究对象就是各种典型的抽象代数系统。 构成一个抽象代数系统有三方面的要素：集合、集合上的运算以及说明运算性质或运算之间关系的公理。请看下面的例子。 整数集合Z和普通加法＋构成了代数系统〈Z,＋〉，n阶实矩阵的集合Mn(R)与矩阵加法＋构成代数系统〈Mn(R),＋〉。幂集P(B)与集合的对称差运算也构成了代数系统
浅谈泛函分析 数学科学学院 张健 20111101710 2011级数学与应用数学汉班 摘 要 泛函分析是分析数学中最“年轻”的分支，它是古典分析观点的推广，它综合函数论、几何和代数的观点研究无穷维向量空间上的函数、算子、和极限理论。它在二十世纪四十到五十年代就已经成为一门理论完备、内容丰富的数学学科了。 关键词 泛函分析、空间、度量、算子 泛函分析是20世纪30年代形成的数学分科,是从变分问题、积分方程和理论物理的研究中发展起来的。它综合运用函数论、几何学、现代数学的观点来研究无限维向量空间上的函数、算子和极限理论。它可以看作无限维向量空间的解析几何及数学分析。主要内容有拓扑线性空间等。泛函分析在数学物理方程、概率论、计算数学等分科中都有应用，也是研究具有无限个自由度的物理系统的数学工具。泛函分析是研究拓扑线性空间到拓扑线性空间之间满足各种拓扑和代数条件的映射的分支学科。 .1度量空间和赋范线性空间 1.1度量空间 现代数学中一种基本的、重要的、最接近于欧几里得空间的抽象空间。19世纪末叶，德国数学家.G 康托尔创立了集合论，为各种抽象空间的建立奠定了基础。20世纪初期,法国数学家..R M -弗雷歇发现许多分析学的成果从更抽象的观点看来,都涉及函数间的距离关系,从而抽象出度量空间的概念。 度量空间中最符合我们对于现实直观理解的是三维欧氏空间。这个空间中的欧几里德度量定义两点之间距离为连接这两点的直线的长度。 定义：设X 为一个集合，一个映射d ：R X X →?。若对于任何z y x ,,属于X ，有 ()1（正定性）(),0,≥y x d 且(),0,=y x d 当且仅当y x = ()2（对称性）()()x y d y x d ,,= ()3（三角不等式）()()()z y d y x d z x d ,,,+≤ 则称d 为集合X 的一个度量（或距离）。称偶对()X d ,为一个度量空间，或者称X 为一个对于度量d 而言的度量空间。 2.1赋范线性空间
分类号图论密级公开UDC081202编号 计算机科学与技术学院 离散数学及其应用结课论文 图划分方法及其在社会网络分析和佩奇网站排名的应用 李英儒涂超杨凯航张蔚樊哲 指导教师张爱华教授 华中科技大学计算机科学与技术学院 班级计算机科学2013创新实验班 学科专业名称计算机科学与技术 学科名称离散数学及其应用论文提交日期2014年11月学院名称计算机科学与技术学院 学校名称华中科技大学
Typeset by Ying-Ru Li using L A T E X2εat November20,2014 With package CASthesis v0.2of CT E https://www.doczj.com/doc/474678017.html,
The Methods of Graph Partition and Its Applications in Social Network Analysis and PageRank Ying-Ru Li Chao Tu Kai-Hang Yang Wei Zhang Zhe Fan Supervisor: Prof.Ai-Hua Zhang Computer Science and Technology School of Computer Science and Technology Huazhong University of Science and Technology November,2014 Essay about Discrete Mathematics and Its Applications of ACM Class of Computer Science,2013 in Computer Science and Technology
离散数学课程总结 姓名： 学号： 班级：级计科系软件工程（）班 近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。 一、课程总结 本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。第一部分：数理逻辑 数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演
算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。 1.在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联 结词、命题及其分类、联结词与复合命题、命题公式及其赋值。2.在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、 等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。 3.在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的 形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。 4.在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、 谓词、量词、一阶逻辑公式及其解释、一阶语言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。 5.在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本 等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统N及其推理规则。 第二部分：集合论 在集合论中，主要学习了集合代数、二元关系和函数。 1.在集合代数中，学习了集合的基本概念：属于、包含、空集、元 集、幂集、全集；集合的基本运算：并、交、补相对、对称差等； 集合恒等式：集合运算的主要算律、恒等式的证明方法。
泛函分析课程总结论文 第一部分：知识点体系 第七章：度量空间和赋范线性空间 度量空间：把距离概念抽象化，对某些一般的集合引进点和点之间的距离，使之成为距离空间，这将是深入研究极限过程的一个有效步骤。 泛函分析中要处理的度量空间，是带有某些代数结构的度量空间，例如赋范线性空间，就是一种带有线性结构的度量空间。 一、度量空间的进一步例子 1、度量空间的定义 定义1.1 设X 为一个集合，一个映射X X R ?→d ：.若对于任何x ,y,z 属 于X ，有 1°d(,)0x y ≥，且d(,)0x y =当且仅当x y =（非负性）； 2°(,)(,)d x y d y x =（对称性）； 3°(,)(,)(,)d x y d x z d z y ≤+ （三角不等式） 则称d 为集合X 的一个度量，同时称 () ,X d 为一个度量空间 （课本第二章第一节中已经讲解了度量空间的定义，第七章第一节接着讲解度量空间，下面介绍六种度量空间。） 2、常见的度量空间 例2.1 离散的度量空间 设 x 是任意的非空集合，对 x 中的任意两点 ，令 称 为离散的度量空间。 例2.2 序列空间S 令S 表示实数列（或复数列）的全体，对S 中的任意两点 令 称 为序列空间。 例2.3 （3）有界函数空间B(A ） 设A 是一个给定的集合，令B(A)表示A 上有界实值（或复值）函数全体， 对B(A)中任意两点x,y ，定义 ,x y X ∈1,(,)0,if x y d x y if x y ≠?=?=?(,)X d 1212(,,...,,...),(,,...,,...), n n x y ξξξηηη==1|| 1(,)21||i i i i i i d x y ξηξη∞ =-=+-∑(,)S d (,)sup |()()|t A d x y x t y t ∈=-
SHEN YANG NORMAL UNIVERSITY “离散数学”论文 课题名称：离散数学在计算机中的应用 学校：沈阳师范大学 姓名: 郑珊珊 学号： 08304019 院系：数学与系统科学学院 专业：数学与应用数学 班级： 08级3班 日期： 2010年11月28日
离散数学在计算机中的应用 离散数学是工科类计算机专业必修的基础课。它在科学研究、工程技术、国民经济等诸多领域都有广泛应用，所以说离散数学的重要性是不言而喻的。特别是离散数学对计算机中的程序的设计起着至关重要的作用。 离散数学中的集合论、数理逻辑、关系、图论、代数系统在计算机中有着广泛的应用。具体如下： 集合论：集合论被应用在计算机科学研究的各个方面。集合是构造离散结构的基础，离散结构是计算机的基本结构。从集合构造而来的离散结构包括：计数时广泛使用的组合、表示对象之间相互关联的关系、图形、以及用户模拟计算机的有限状态机等。集合论在人工智能领域、逻辑学及程序设计语言等方面都有着重要的应用。同时，集合论在新一代智能计算机的发展具有重要的应用。计算机智能利用模糊集合理论，把人类的语言和思维过程提炼成数学模型，使人类语言数量化、形式化，并通过对模糊逻辑、模糊控制、模糊识别、模糊聚类分析、模糊决策等方面的分析，使计算机能够模拟人脑的高级智能。 数理逻辑：数理逻辑在计算机科学的计算理论、算法、程序设计、人工智能、计算机硬件系统等方面发挥着重要而广泛的应用。从计算机程序设计语言方面来说，语言的理论基础是形式语言、自动机与形式语义学。而形式语言、自动机和形式语义学所采用的主要研究思想和方法来源与数理逻辑和代数。程序设计语言中的许多机制和方法，如子程序调用中的参数代换、赋值等都出自数理逻辑的方法。此外，在语言的语义研究中，四种语义方法最终可归结为代数和逻辑方法。而且，程序的语义及其正确性的理论基础仍然是数理逻辑或进一步的模型论。不仅如此，数理逻辑在计算机体系结构的研究中起着主导的作用，像容错计算机系统、Transputer计算机、阵列式向量计算机、可变结构的计算机系统结构及其计算机模型等都直接或间接与逻辑及代数密不可分。如容错计算机的重要基础之一是多值逻辑，Transputer计算机理论基础是CSP理论，阵列式向量计算机必须以向量运算为基础，可变结构的计算机系统结构及其计算机模型主要采用逻辑与代数的方法。 关系：数据库是多元关系的一种很重要的应用。通常情况下，我们会使用文件方式将信息保存在计算机上，但是当信息的规模越来越庞大的时候，这种单纯使用文件系统保存信息的方式就会存在很多问题：比如信息的一致性和完整性问题，以及在大量的文件中查找具有某些特征信息的问题，信息的并发访问和安全性问题。这些问题导致了数据库德产生和高速发展。数据库系统能够将大量的数据信息有序的组织起来，并提供相应的查询和访问策略以及安全性措施。数据库系统的应用领域覆盖了我们生活中的方方面面。比如银行和证券交易所得事务处理，所有公司和单位都需要的财务和工资管理以及学校里的学籍管理系统、人事管理系统、题库系统等。近几年来，数据库在决策支持系统、空间数据库、多媒体数据库、移动数据库、信息检索和分布式信息检索等领域发挥着越来越重要的作用。除此之外，关系理论在计算机科学的通讯网络、项目调度以及集合划分和计算机语义等方面具有重要的作用。 图论：图论是研究点线构成的图形问题的一门学科，它的起源很早，但它的发展在初期是比较缓慢的，根本原因在于图的分析计算量非常大，仅靠人工不但耗时耗力，而且也容易出错。直到20世纪50年代之后，随着计算机技术的高速发展，利用计算机的强大处理能力，图论的研究也达到了空前活跃的程度，同时，
离散数学总结 班级：学号：姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。《离散数学》这门课程当然也不会例外了。经过一个学期的学习我发现《离散数学》是一门理论性非常强的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 《离散数学》顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对《离散数学》我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于《离散数学》在计算科学中的重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 《离散数学》的特点是： 1、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边