抽象语法树
概念：
抽象语法树（abstract syntax code，AST）是源代码抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，之所以说语法是’抽象’的，是因为这里的语法不会表示出真实语法中出现的每个细节。
在这里先补充一个概念：具象语法树(Concret Syntax Tree, 简称CST)。

什么是具象语法树呢？

我们知道一颗解析树是包含代码所有语法信息的树形结构，它是代码的直接翻译，所以解析树也被称为具象语法树。抽象语法树实际只是解析树的一个精简版。
避免混淆，我们来简化一下概念：
解析树 = CST = 具象语法树

抽象语法树 = AST
那么抽象语法树到底是什么样的呢？我们可以来看一个简单的例子：
我们来写一段最简单js代码 20 + (15 - 3)*2，没错，这是一个简单的四则运算表达式，那么它的抽象语法树应该表现为什么样呢，在看AST(抽象语法树)之前，我们先来看一下它的解析树:


但是我们看到这样的一颗解析树显然是有些冗余的，那么我们可不可以对这颗解析树去繁取简呢，当然是可以的：

这里我们得到了一棵最简洁的树，去除了冗余的描述和符号，很直观的就可以看出树上每一个阶段节点之间的关系，从而也更能容易的推断出原表达式的样子，此时我们所得到的这颗树就是我们最终要得到的 20 + （15 - 3）*2 表达式的抽象语法树。

这里只是简单的对抽象语法树概念的简单理解，当然还有从分析树到抽象语法树的具体的转化过程以及具体的表现形式，如果有需要请自行查阅相关资料。

上述文章或许有理解错误，请不吝赐教！

群论的基本概念点较多，且各概念点之间关系纵横交错，学习起来颇有本科时初学线性代数时的感觉，觉得有必要整理一下，先梳理一下群的基本定义和例子。 

首先作几点说明： 

1、群(group)、环(ring)、域(field)是抽象代数(abstract algebra)中基本的代数结构(algebraic structures) 

2、上述这些代数结构是抽象代数(abstract algebra)的研究对象之一，另一个研究对象是通过研究这些代数结构间的保持运算的映射(态射(morphism)) 

3、1872年，F.Klein在被聘为埃尔朗根大学的数学教授的就职演讲中阐述了几何学统一的思想：所谓几何学，就是研究几何图形对于某类变换群保持不变的性质的学问，或者说任何一种几何学只是研究与特定的变换群有关的不变量（《埃尔朗根纲领(Erlangen Program)》）

〇、前置概念

名称
  
英文名称
  
定义
  
说明
代数运算
  
Algebra Calculation
  
非空集合S与自己的笛卡尔积S×S到S的一个映射
  
在群论中通常是指所谓的二元代数运算
正交点变换
  

  

  
又称为保距变换(isometry)
正交矩阵
  
Orthogonal Matrix
  
AAT=ATA=E
  

酉矩阵
  
Unitary Matrix
  
UUH=UHU=En
  
式中H为共轭转置


一、群的定义



1、群的基本定义

序号
  
定义
  
说明
1
  
代数运算
  
定义了一个代数运算的非空几何
2
  
结合律
  
(ab)c=a(bc),∀a,b,c∈G
3
  
单位元存在律
  
∃s∈G,ea=ae=a,∀a∈G
4
  
逆元存在律
  
∀a∈G,∃b∈G,ab=e
2、 群定义的衍生

名称
  
英文名称
  
定义
  
说明
群
  
Group
  
满足前述全部4条群的基本定义的非空集合
  

半群
  
Semigroup
  
仅满足前述群的基本定义中的前2条的非空集合，即：
1）定义了集合上的代数运算
2）适用结合律
但是，并不要求存在单位元和逆元
  
也有地方称为仿群
幺半群
  
Monoid
  
满足前述群的基本定义中的前3条的非空集合，即：
1）定义了集合上的代数运算
2）适用结合律
3）存在单位元
但是，并不要求存在逆元
  

阿贝尔群
  
Abel Group
  
在满足前述全部4条群的基本定义的前提下，再补充一条：群元素满足交换律
  
ab=ba,∀a,b∈G
二、群的例子

1、生活中群的例子

名称
  
英文名称
  
说明
平面晶体群
  
Plane Crystallographic Group
  
又被称为贴墙纸群(Wallpaper Group)
已经G.Polya在1924年完成对平面晶体群的分类：共有17种不同的平面晶体群
空间晶体群
  
Space Crystallographic Group
  
Fedorov和Schonflies分别独立地证明了空间晶体群共有230个
魔方群
  
Rubik’s Cube group
  
https://en.wikipedia.org/wiki/Rubik%27s_Cube_group
2、数集中群的例子

名称
  
符号
  
定义
  
说明
整数加群
  

  

  

实数加群
  

  

  

n次单位根群
  
Un
  

  
Un的生成元成为复数域中的本原n次单位根(primitive n th root of unity)
3、几何中群的例子

中文名称
  
英文名称
  
符号
  
定义
  
说明
欧几里得群
  
Euclidean Group
  
En
  
n维空间所有正交点变换的集合
  
E2 为平面欧氏群E3 为空间欧氏群
二面体群
  
Dihedral Group
  
Dn
  
正n边形的对称（性）群，n≥3
  

4、代数中群的例子

中文名称
  
英文名称
  
符号
  
定义
  
说明
模n剩余类环
  

  
Zm
  
Zm=0,1,2,…,m−1
  
该群的生成元是1¯(i¯=i1¯)
Zm的单位群
  
Zm’s Group of Units
  
U(Zm)或Z∗m
  
Zm=0,1,2,…,m−1
  
该群的生成元是1¯(i¯=i1¯)
Zp的乘法群
  

  
Z∗p
  
当m为素数p时，Zm中所有非零元组成的集合对于乘法构成的一个abel群
  
该群是一个abel群
当m为素数时，根据欧拉定理Zp中的所有元素都有逆元(inverse unit)
一般线性群
  
General Linear Group
  
GLn(F)
  
域F上所有n级可逆矩阵组成的集合，对于矩阵的乘法所成的群
  
是矩阵群(Matrix Group)的一种
特殊线性群
  
Special Linear Group
  
SLn(F)
  
在一般线性群定义的基础上再补充定义，所有的矩阵行列式为1
  
是矩阵群(Matrix Group)的一种
正交群
  
Orthogonal Group
  
On
  
实数域上所有n级正交矩阵(AAT=ATA=E)组成的集合
  
是矩阵群(Matrix Group)的一种
特殊正交群
  
Special Orthogonal Group
  
SOn
  
在正交群定义的基础上再补充定义，所有的矩阵行列式为1
  
是矩阵群(Matrix Group)的一种
通常SOn被称为n维旋转群(Rotation Group)
它所指定的旋转对应的旋转轴可以通过求解一个线性方程组的基础解析来计算得到
酉群
  
Unitary Group
  
Un
  
复数域上所有n级酉矩阵组成的集合，对于矩阵乘法所成的群
  

特殊酉群
  
Special Unitary Group
  
SUn
  
在酉群定义的基础上再补充定义，所有的矩阵行列式为1
  

集合Ω的全变换群
  
Full Transformation Group on Set Ω
  
SΩ
  
非空集合Ω到自身的所有双射组成的集合，对于映射的乘法构成的一个群
  

n元对称群
  
Symmetric Group on n letters
  
Sn
  
SΩ，当Ω为有限集合时
  
Sn具备对称性
这时其中的每一个元素(是一个双射)被称为Ω的一个置换(permutation)，对于Ω有n个元素的情形，该置换被称为n元置换(permutation on n letters)
Sn中引入了r-轮换(r-cycle)的概念；特别的，当r=2时，轮换被称为对换(transposition)；并且可以说明：每一个置换都可以表示成一些对换的乘积
并且对于置换进一步引入了由其等价的对换分解式中的对换的个数的奇偶性确定的奇置换或偶置换
n元交错群
  
Alternating Group on n letters
  
An
  
Sn中所有偶置换组成的集合
  

References


  
丘维声，抽象代数基础
  
F. Klein，A comparative review of recent researches in geometry，http://arxiv.org/abs/0807.3161
  
https://en.wikipedia.org/wiki/Group_(mathematics)
  
https://en.wikipedia.org/wiki/Rubik%27s_Cube_group
  

在平时的项目中，许多东西都是用到了才看，甚至是只用不看。对下面几个知识点进行总结，加深自己对C#的理解。


今天刚好看到一篇讲C#数据结构很不错的博文，就不转载了。
贴上网站：http://www.cnblogs.com/gaochundong/p/data_structures_and_asymptotic_analysis.html#hashtable


1.Array，ArrayList，List<T>，LinkedList<T>，Queue<T>，Stack<T>，Dictionary<K,T>
（1）Array
最常用的数据结构，顺序存储相同数据类型的内容，可以通过下标O(1)进行访问。数组定义使用需要显示指定数组长度，不能更改。
一般定义为：
int[] arr1=new int[5];
int[,] arr2=new int [5,6];//矩形数组


int[][] arr3 = new int[3][];//锯齿形
arr3[0]=new int[4];
arr3[1]=new int[5];
arr3[2]=new int[6];
（2）ArrayList
A.在System.Collections命名空间下，不必指定长度，存储空间会根据需要动态增减。
B.可以存储不同的数据类型，都视为Object；导致不是类型安全，并且有频繁的装箱拆箱操作，造成性能和效率上的影响。

C.每次增加新元素时，会检查内部存储空间是否不够，是否以当前容量两倍进行扩容，将旧元素复制到新空间，然后删除旧空间。
D.若了解数据量范围，可以指定空间大小，比如 ArrayList List = new ArrayList( 200);是开辟200个存储空间。ArrayList List = new ArrayList()；
则按系统默认容量进行初始化，网上有称为默认容量为16，具体没去考证过。
（3）List<T>
数据类型要求相同，类型安全，不需要频繁装箱拆箱。可视为是ArrayList的改进，底层实现与ArrayList一样，都使用Array。
（4）Queue<T>和Stack<T>LinkedList<T>
A.队列：先进先出
B.栈：先进后出
C.链表，存储不要求是内存顺序存储。与C++中的顺序存储跟链式存储类似~优缺点一样，这里不废话。

（5）Dictionary<K,T>
字典的实现方式就是哈希表的实现方式，不过字典是类型安全的，定义时要声明key和item数据类型。通过K来“检索”T。


另外还有SortedList/HashSet等~名称上有Hash的都是基于hash的，比如HashSet<T>不能按索引访问，不能有重复数据,其Contains()方法为O(1),而
List的为O(n)。list 就是强化版本array， 很多情况下list的功能是不可替代的 所以 在集合的目的是为了检索的情况下，我们才应该使用HashSet<T>代替List<T>。

hash code会改变的对象不适合放在hash表中 所以也要少为注意下


2.委托和事件
做项目在用C#，由于一直没有完全搞清楚委托和事件，一直觉得很不开心。。。看了别人文章整理下。用得上的同学或者想学的同学好好看看下面转载地址的文章~
推荐阅读：http://www.tracefact.net/CSharp-Programming/Delegates-and-Events-in-CSharp.aspx，讲得很清晰，下面的例子也引用其中！



（1）委托
委托可以理解为C++中的函数指针，可以将方法作为参数传递。
现在，请看看这个范例的完整代码：


using System;
using System.Collections.Generic;
using System.Text;
namespace Delegate {
     //定义委托，它定义了可以代表的方法的类型
     public delegate void GreetingDelegate(string name);
        class Program {
           private static void EnglishGreeting(string name) {
               Console.WriteLine("Morning, " + name);
           }
           private static void ChineseGreeting(string name) {
               Console.WriteLine("早上好, " + name);
           }
           //注意此方法，它接受一个GreetingDelegate类型的方法作为参数
           private static void GreetPeople(string name, GreetingDelegate MakeGreeting) {
               MakeGreeting(name);
            }
           static void Main(string[] args) {
               GreetPeople("Jimmy Zhang", EnglishGreeting);
               GreetPeople("张子阳", ChineseGreeting);
               Console.ReadKey();
           }
        }
    }

输出如下：
Morning, Jimmy Zhang
早上好, 张子阳
 
委托的声明方式和类却完全不同，这是怎么一回事？实际上，委托在编译的时候确实会编译成类。因为Delegate是一个类，所以在任何可以声明类的地方都可以声明委托。委托是一个类，它定义了方法的类型，使得可以将方法当作另一个方法的参数来进行传递，这种将方法动态地赋给参数的做法，可以避免在程序中大量使用If-Else(Switch)语句，同时使得程序具有更好的可扩展性。


可以将多个方法绑定到同一个委托，当调用这个委托的时候，将依次调用其所绑定的方法。如果要将方法解绑就使用-=。
在这个例子中，语法如下：

static void Main(string[] args) {
    GreetingDelegate delegate1;
    delegate1 = EnglishGreeting; // 先给委托类型的变量赋值
    //注意是=号，因为要先赋值//也可以在定义时实例化，即GreetingDelegate delegate1 = new GreetingDelegate(EnglishGreeting);
    delegate1 += ChineseGreeting;   // 给此委托变量再绑定一个方法//已经赋值过，使用+=进行多个方法的绑定
     // 将先后调用 EnglishGreeting 与 ChineseGreeting 方法
    GreetPeople("Jimmy Zhang", delegate1);  
    Console.ReadKey();
}

输出为：
Morning, Jimmy Zhang
早上好, Jimmy Zhang
也可以绕过GreetPeople方法，通过委托来直接调用EnglishGreeting和ChineseGreeting
static void Main(string[] args) {
    GreetingDelegate delegate1;
    delegate1 = EnglishGreeting; // 先给委托类型的变量赋值
    delegate1 += ChineseGreeting;   // 给此委托变量再绑定一个方法
    // 将先后调用 EnglishGreeting 与 ChineseGreeting 方法
    delegate1 ("Jimmy Zhang");   
    Console.ReadKey();
}
再看看以下代码：
public class GreetingManager{
    //在GreetingManager类的内部声明delegate1变量
    public GreetingDelegate delegate1;  

    public void GreetPeople(string name) {
        if(delegate1!=null){     //如果有方法注册委托变量
          delegate1(name);      //通过委托调用方法
       }
    }
}
static void Main(string[] args) {
    GreetingManager gm = new  GreetingManager();
    gm.delegate1 = EnglishGreeting;
    gm.delegate1 += ChineseGreeting;

    gm.GreetPeople("Jimmy Zhang");      //注意，这次不需要再传递 delegate1变量
}

输出为：
Morning, Jimmy Zhang
早上好, Jimmy Zhang
（2）事件
事件封装了委托类型的变量，使得在类的内部，不管你声明它是public还是protected，它总是private的。
在类的外部，注册“+=”和注销“-=”的访问限定符与你在声明事件时使用的访问符相同。
事件的声明与委托变量delegate的声明唯一的区别是多了一个event关键字。所以声明一个事件不过类似于声明一个进行了封装的委托类型的变量而已。


.Net Framework的编码规范：
委托类型的名称都应该以EventHandler结束。
委托的原型定义：有一个void返回值，并接受两个输入参数：一个Object 类型，一个 EventArgs类型(或继承自EventArgs)。
事件的命名为 委托去掉 EventHandler之后剩余的部分。
继承自EventArgs的类型应该以EventArgs结尾。






3.接口和抽象类
为什么要有接口？CLR via C#中说道，CLR不支持多继承，所以通过接口（interface）提供了“缩水版”的多继承，接口的方法必须显示实现。
（1）接口
定义：接口是一种约束形式，其中只包括成员定义，不包含成员实现的内容。
目的：接口的主要目的是为不相关的类提供通用的处理服务，由于C#中只允许树形结构中的单继承，即一个类只能继承一个父类。
接口是让一个类具有两个以上基类的唯一方式。
声明：接口声明的方式与声明类的方式相似，但使用的关键字是interface，而不是 class。接口只包含方法、属性、索引器和事件的签名。
方法的实现是在实现接口的类中完成的。接口类型名称要用大写字母I开头，目的是方便在源代码中辨认接口类型。

接口可以继续其他的接口。接口方法要求显示标记为virtual，否则就会标记成virtual和sealed，这就会阻止派生类重写接口方法。这样就需要
重新继续同一个接口，并为该接口方法提供它自己的实现。
（2）抽象类

含有abstract修饰符的class即为抽象类，抽象类是特殊的类，只是不能被实例化，可以创建一个变量，其类型是一个抽象类，并让它指向具体子类的一个实例；
除此以外，具有类的其他特性；重要的是抽象类可以包括抽象方法，这是普通类所不能的。抽象方法只能声明于抽象类中，且不包含任何实现，派生类必须覆盖它们。
另外，抽象类可以派生自一个抽象类，可以覆盖基类的抽象方法也可以不覆盖。

（3）对比
相同点
 1. 都不能被直接实例化，都可以通过继承实现其抽象方法。
 2. 都是面向抽象编程的技术基础，实现了诸多的设计模式。


不同点 
1. 接口支持多继承；抽象类不能实现多继承。抽象类可以有构造方法，接口中不能有构造方法。
2. 接口只能定义抽象规则；抽象类既可以定义规则，还可能提供已实现的成员。 
3. 接口是一组行为规范；抽象类是一个不完全的类，着重族的概念。
4. 接口可以用于支持回调；抽象类不能实现回调，因为继承不支持。 
5. 接口只包含方法、属性、索引器、事件的签名，但不能定义字段和包含实现的方法；抽象类可以定义字段、属性、包含有实现的方法。
6. 接口可以作用于值类型和引用类型；抽象类只能作用于引用类型。例如，Struct就可以继承接口，而不能继承类。
7. 一个类可以实现多个接口，但只能继承一个抽象类。

8. 抽象类和接口中都可以包含静态成员变量，抽象类中的静态成员变量的访问类型可以任意，但接口中定义的变量只能是public static final类型，并且默认即为public static final类型。
9. 抽象类中可以包含静态方法，接口中不能包含静态方法
10.抽象类中的抽象方法的访问类型可以是public，protected，但接口中的抽象方法只能是public类型的，并且默认为public abstract类型。


知乎上看到一个例子：
一个类继承了某个抽象类表示它“是什么”，实现了某个接口表示它“有什么功能”或者“会做什么事”。比如：燕子（具体类）是鸟（抽象类），会飞（接口）。
C#中不支持多继承，即燕子只能是鸟，不会是其他东西了；但可以有多个功能，做很多事，比如会飞（IFly），会吃（IEat）。

    

            





image.png

抽象代数作为数学的一门学科，主要研究对象是代数结构，比如群、环、域、模、向量空间、格与域代数。“抽象代数”一词出现于20世纪初，作为与其他代数领域相区别之学科。
代数结构与其相关之同态，构成数学范畴。范畴论是用来分析与比较不同代数结构的强大形式工具。
泛代数是一门与抽象代数有关之学科，研究将各类代数视为整体所会有的性质与理论。例如，泛代数研究群的整体理论，而不会研究特定的群。
如同其他的数学领域一般，具体的问题与例子于抽象代数的发展中发挥着重要的作用。19世纪末期，许多（也许是最多）的问题都在某些程度上与代数方程的理论有关。主要问题包括：
1.解线性方程组的解，这导致了线性代数。

2.试图找出高次一般多项式方程的公式解，因而发现了群可以作为对称的抽象表示。

3.二次以上的丢番图方程之算术研究，直接影响了环与理想等概念的形成。