VISUAL GROUP THEORY

一、群是什么
群不是关于数字的，而是关于模式的。群论研究的是关于旋转模式的对称。
群的法则：

存在一个预先定义的、不会改变的作用列表。
每个作用都是可逆的。
每个作用都是确定性的。
任何连续作用的序列仍是一个作用。


二、群看起来像什么
群的操作是群的生成元。
凯莱图（状态为节点，生成元为边）：群的可视化工具。通过凯莱图，可以看出抽象群的结构。

Group Explorer


三、为什么学习群
任何群都可以看作是由一些事物重新排列的方式组成的。群之所以和对称有关，是由于一个物体的对称可以描述为其组成部分的重新排列。

一维重复模式：饰带模式。任何饰带模式的对称都可以由七个不同的无限群中的一个来描述。

群论的起源：多项式的解之间彼此存在着某种联系。这些联系构成一个群。
群的应用：

群论和线性代数描述空间变换。
群论和拓扑学对空间与形状进行分类。
子集和陪集用来设计纠错码，用来减少信息传递过程中的错误。


四、群的代数定义
作用的乘法表：揭示了作用在群中组合的模式。




群的非标准定义
群的标准定义




作用
元素


两个作用组合成一个新作用
二元运算


群的经典定义：




群的经典定义
群的非标准定义




有一个二元运算
作用的组合


运算满足结合律
作用的组合允许加括号，括号既不是必须的，也不会改变运算的意义


存在单位元
无作用


存在逆元
逆作用



对于代数群来说，作用既不是数字也不是运算，而是数字加运算。例如：+2，x3，其中 +0 和 x1 为单位元。


五、五个群族

循环群：Cn，仅有旋转对称

轨道：从单位元出发，沿着某个作用的轨迹进行状态转换。对于循环群来说，所有的轨道都是圈。


阿贝尔群：An，作用的先后顺序是可以调换的，所有的循环群都是阿贝尔群


二面体群：Dn，同时具有旋转对称和轴对称


二面体群包含旋转，旋转将凯莱图分成内环和外环，各为一个循环群。
置换：对一系列物体进行重新洗牌


对称群：Sn，表示由 n 个物体的所有置换组成的群


交错群：An，选取 Sn 中的一半置换，即可构成一个群


凯莱定理：每个群都同构与一个置换群。（对一个群的乘法表的每一列构造一个置换，然后观察这些置换作用在群的单位元上的结果。就会发现两个群是同构的）

六、子群
子群：一个群完全包含在另一个群众（凯莱图上的包含）
陪集：和子群类似，但不包含单位元的群副本，不构成子群，构成陪集
所有的陪集构成了群的一个分划。
左陪集：如果从元素a开始沿着生成元H进行勘察，形成 aH
右陪集：作用的顺序相反，形成 Ha

因为在凯莱图中，作用箭头表示右乘，所以左陪集的元素是集中的，右陪集的元素是分散的

正规子群：如果左陪集和右陪集相同。
拉格朗日定理：由于子群及其陪集构成了群的一个分划，所以子群的阶必整除群的阶，即不整除的阶肯定不构成子群

七、积与商
直积：将一个群的元素用另一个群来替代，即为两个群的直积，直积都是可交换的
在直积群中，其因子群为正规子群
直积用简单的过程展示了如何由小群构造大群
直积群的乘法表表现为因子群的乘法表矩阵的直积
直积群的乘法表具有独立性：即一个作用完全可以拆分成两个因子群中的作用（正规子群或许和正交有关系）
半直积：将一个群的元素用另一个群的重布线来替代（重布线即改变作用箭头的方向，但是节点不变）
商群：将群的每个陪集看成一个结点，如果得到的新凯莱图是一个群，那么就为正规子群的商群，否则不能整除
只有商运算成功时，子群才是正规的
正规化子：衡量一个子群的正规程度，大群去掉多少个元素后，才能拥有正规子群。
共轭：对正规子群，gH = Hg，即 gHg^-1 = H，即 g 和 h 共轭
每个正规子群都是由若干个共轭类组成的，我们可以通过合并共轭类来寻找正规子群。

八、同态的力量
子群和商群中，都会遇见同态的概念
群中的每个元素和作用，映射到一个新的元素和作用，映射到的群即为陪域，映射到的元素即为像（Img），这样的一个函数映射就是同态。
同态把定义域中的结点映射到陪域中的结点，把定义域中的路径映射到陪域中的路径
上述同态在乘法表中的表示是一个群的乘法表嵌入到另一个群的乘法表中
如果一个嵌入的像是整个陪域，就是同态，即两个群具有完全相同的结果
商映射：把多个定义域元素映射到同一个陪域元素，即非嵌入的同态称为商映射
核（Ker）：定义域到陪域的元素映射，对于商映射为多个元素，嵌入只有单位元
同态包含两种类型：嵌入和商映射。
同态基本定理：若 G 和 H 关于函数 φ 同态，则 Img（φ）和 G/Ker（φ）是同构的，

整数无限循环群可以看做只有一个生成元，那就是 1

循环群 Cn X Cm（直积）和 Cnm 同构当且仅当 n，m 互素
阿贝尔群基本定理：每个有限阿贝尔群都同构于循环群的直积。其表现就是，阿贝尔群的凯莱图是网格状的，有一维网格，二维网格，三维网格等，这些网格即为循环群子群，同时揭示了阿贝尔群的直积结构
每个群的重布线都是到自身的同构，所以半直积是将一个群的元素用另一个群的自同构群来替代

九、西罗定理
每个群都同构于置换群的一个子群。每个群都能嵌入到某个 Sn。

十、伽罗瓦理论
算数方程：只用到算数运算、有理数和一个表示未知量的变量。
算数方程都能化简成一边是多项式另一边是零的形式。
如果 r 是多项式的根，那么 r 的共轭也是多项式的根。
通过证明某个群的共轭类，以说明它没有正规子群，得到一个不可解群。如果一个五次多项式，其根的伽罗群包含这个不可解群，那么这个多项式就是无解的。**e.g. x5+10·x4-2

                                       Chapter 1 词法陷阱

    程序中的单个字符孤立起来看并没有什么意义，只有结合上下文才有意义，如p->s = "->";两处的-意义
是不同的。

    程序的基本单元是token ,相当于自然语言中的单词。 一个token的意义是不会变的。 而组成token 的字
符序列则随上下文的不同而改变。

    token之间的空格将被忽略。


1.1 = 不同于 ==

1.2 &和|不同于&&和||

1.3 词法分析中的贪心法

    token分为单字符token和多字符token，如/ 和 == ，当有岐义时，c语言的规则是：每一个token应包括
    尽可能多的字符。

    另外token的中间不能有空白（空格，制表符， 换行符）
    y = x /*p 应写为y = x / *p  或者y = x / (*p);

    老编译器允许用=+来代表现在+=的含义。所以它们会将a=-1理解为a=- 1 即a = (a-1);
它们还会将复合赋值语句看成两个token,于是可以处理 a>> =1, 而现代的编译器会报错。


1.4 整型常量

    常量前加0代表是8进制。

1.5 字符与字符串

    用双引号引起的字符串， 代表的是一个指向无名数组起始字符的指针


    a+++++b的含义是什么？

    C不允许嵌套注释。


                                      Chapter 2  语法陷阱


2.1 构造函数声明

    构造函数声明的规则：按照使用的方式来声明。

    任何C声明都由两部分组成：类型及类似表达式的声明符（declarator)。


    float *g(), (*h)();
    g是一个函数，该函数的返回值类型为指向浮点数的指针。 h是一个函数指针， h所指向函数的返回值为
浮点类型。（）的优先级高于*。

    因为float (*g)();表示g是一个指向返回值为浮点类型的函数的指针。所以(float (*)())表示一个“指向
    返回值为浮点类型的函数的指针”的类型转换符。


    一旦我们知道如何声明一个给定类型的变量， 那么该类型的类型转换符就很容易得到了：只需要把声明
中的参量名和声明末尾的分号去掉，再将剩余的部分用一个括号整个“封装”起来即可。

    (*(void(*)())0)()表示什么意思呢？

    如果fp是一个函数指针， 那么(*fp)()就表示对其所指的函数的调用。简写为fp()。但这只是简写而已。
    而*((*fp)())可以简写为*fp()

    根据上文(void(*)()) 表示一个“指向返回值为void的函数的指针”的类型。这里不过是对0作强制转换而
已。其实用typedef更好：

    typedef void (*funcptr)();
    (*(funcptr)0)();

    signal的声明如下：
    void (*signal(int, void(*)(int)))(int);
    或者用typedef：
    typedef void (*HANDLER)(int);
    HANDLER signal(int, HANDLER);


2.2 运算符的优先级问题

    注意条件运算符优先级比赋值运算符高，书上第22页是错的。
    & > ^ > |

2.3 分号

2.4 switch 语句

2.5 函数调用

    f();
    是个函数调用。而f;则计算函数f的地址。
2.6 else

    C语言允许初始化列表中出现多余的逗号。


       
                                       Chapter 3 语义陷阱


3.1 指针与数组

    C语言中只有一维数组， 而且数组的大小必须在编译期间就作为一个常数确定下来。多维数组是通过一维
数组仿真的,因为数组的元素可以是任何对象，当然也可以是数组。

    对数组，我们只能做两件事，确定其大小，以及获得指向该数组下标为0的元素的指针。其它的有关数组
的操作，实际上是通过指针进行的。


    如果两个指针指向的是同一个数组中的元素，我们可以把这两个指针相减。如果它们指向的不是同一个数
组中的元素，即使它们指向的地址在内存中的位置正好间隔一个数组元素的整数倍，所得的结果仍然是无
法保证其正确性的。

    如果在应该出现指针的地方出现了数组名，则数组名就被当作指向该数组下标为0的元素的指针。
     int a;
     p = a;
     int *p;
是对的。但p = &a在ansi C中则是非法的。因为&a 是一个指向数组的指针，而p是一个指向整型变量的指针，
它们的类型不匹配。
    由于a[i] 即*(a+i);而a+i即i+a；所以a[i]即i[a];但不推荐后者的写法

    int cal[12][31];
    int *p;
    int i;

    i = cal[4][7]等于i = *(cal[4] + 7);也等于i = *(*(cal + 4) +7);


    p = cal; 是错误的，类型不匹配，后者是指向数组的指针。


    我们来声明指向数组的指针：
    int (*ap)[31];
    于是我们可以这样写：
    int cal[12][31];
    int (*monthp)[31];
    monthp = cal;

    两 个指针不能相加。负数的移位运算不等于相应的乘或除运算。

3.2 非数组的指针

    我们要将s和t连接成r.
    s = "abc";
    t = "efg";
    char *r;
    strcpy(r,s);
    strcat(r,t);
这并不能达到目的。

因为一是不能确定r指向何处, 二是不能保证r所指向的地址处还应该有内存空间可供容纳字符串。

较好的是把第一行改为char r[100];只是这样的话，大小固定了。

正确的应该是：

#include <stdio.h>
#include <ctype.h>

int main (void)
{
     char s[10];
     char t[10];
     
     char *r;
     char *malloc();
     r = malloc(strlen(s) + strlen(t) + 1);
     if(!r)
     {
          complain();
          exit(1);
     }
     
     scanf("%s",s);
     /*getchar();*/
     
     scanf("%s",t);
     
     strcpy(r,s);
     strcat(r,t);
     
     printf("%s\n",r);
     free(r);
     
}

3.3 作为参数的数组声明

    我们没有办法将一个数组作为函数参数直接传递。数组名会被转为指向该数组第一个元素的指针。

    int strlen(char s[]){}
    与下面的写法完全相同：
    int strlen(char* s){}

    但其它地方就未必相同了。
    下面两 个语句是完全不同的。
    extern char *hello;
    extern char hello[];

    下面则是一样的
    main(int argc, char* argv[]){}
    main(int argc, char** argv){}

3.4 避免“举隅法”

    复制指针并不同时复制指针所指向的数据。

3.5 空指针并非空字符串

    把常数0转为指针，则指针不等于任何有效的指针，即 void 指针。其它将整数转为指针得到的结果未定
义。当常数0被转为指针时，这个指针绝对不能被解除引用（dereferenc)。换句话说，当我们将0赋给一个指
针变量时，绝对不能企图使用该指针所指向的内存中存储的内容。

    下面的是合法的：
    if (p == (char *) 0)
    但下面是非法的
    if (strcmp(p, (char *) 0) == 0)

    如果p是一个空指针，即使printf(p);和printf("%s",p);的行为也是未定义的。

3.6 边界计算与不对称边界

    数组的下标如果用入界口加出界口来表达（即10个元素,其下标为0 <= n < 10 )，则元素个数即为上界与下界
之差,即下界。若为空，则上界等于下界。任何情况下上界也永远不可能小于下界。

    尽量采用非对称边界法。
    一个有N个元素的数组 ，我们可以使用a[N]进行比较和赋值，但不能引用其内容。


3.7 求值顺序

    C语言只有四个运算符（&&, ||, ?: , 和 ,）存在规定的求值顺序。另外，分隔函数参数的逗号并非逗号
    运算符。例如，在x和y在函数f（x，y）中的求值顺序是未定义的，而在函数g((x,y))是先算x，再算y，y
    的值为参数。特别是赋值运算符没有规定求值顺序。


3.9 整数溢出

    无符号算术运算中，没有所谓的“溢出”一说。有符号运算中发生溢出，则结果未定义。

    下面检测溢出的方法不可靠：
    if(a + b <0)
    complain();

    应该这样：
    if((unsigned) a + (unsigned) b >INT_MAX)
    complain();

或者这样
        if(a > INT_MAX - b)
        complain();

3.10 为函数main提供返回值

     如果没 有为函数声明返回类型，则默认为int.



free之后最好马上就p = NULL;


                                         Chapter 4 连接



4.1 什么是连接器
    连接器通常把目标模块看成是由一组外部对象组成的。 第个外部对象都代表着机器内存中的某个部分，并
通达一个外部名称来识别。因此， 程序中的每个函数和每个外部变量，如果没有被声明为static，就都是一个
外部对象。 某些编译器会对静态函数和静态变量的名称做一定改变，将它们也作为外部对象。

    除了外部对象，目标模块还可能包括了对其它模块中的外部对象的引用。


4.2 声明与定义


    每个外部变量只能定义一次。

4.3 命名冲突与static修饰符

4.4 形参、实参与返回值

    每个函数都要在调用之前进行声明定义，不然返回类型为int
    如果一个函数没有float，short或者char类型的参数，在函数声明中完全可以省略类型声明（定义不能省
    略）

4.5 检查外部类型

    同一个外部变量在不同的地方被声明为不同的类型，这种错误大部分编译器是检不出来的。
    char file[]= "/etc/password";
    与
    extern char* file;
是不一样的。

4.6 头文件

                                        Chapter 5 库函数


    C标准没有定义执行底层I/O操作的read和write函数。
5.1 返回整数的getchar函数

5.2 更新顺序文件

    为了与以前的程序保持兼容，一个输入操作不能随后紧跟一个输出操作，反之亦然。如果要同时进行输入
    和输出操作，必须在其中插入fseek函数的调用。

    FILE *fp;
    struct record rec;
   
    while (fread((char *)&rec, sizeof(rec),1,fp) = 1)
    {
        /*    */
        if(/* */)
        {
          fseek(fp, -(long)sizeof(rec), 1);
          fwrite((char *)&rec, sizeof(rec), 1,fp);
          fseek(fp, 0l,1);
         }
}

5.3 缓冲输出与内存分配

    #include <stdio.h>

void main(void)
{
     int c;
     char buf[BUFSIZ];
     setbuf(stdout,buf);
     
     while((c = getchar()) != EOF)
          putchar(c);
}
这个是不对的。buf最后一次被清空是在什么时候？答案是在main函数结束之后，作为程序交回控制给操作系
统之前C运行时库所必须进行的清理工作的一部分。但是在此之前buf已经被释放。

    解决方法一是加上static 声明。也可以把buf声明完全移到main函数之外。第二种办法是动态分配缓冲区，
在程序中并不主动释放分配的缓冲区


5.4 使用erron检测错误

    很多的库函数，特别是那些与操作系统有关的，当执行失败时会通过一个名称为errno的外部变量，通知
程序该函数调用失败。

    下面的是错误的：
    /*调用库函数*/
    if(errno)
        /*处理错误*/
   
    因为，在库函数调用没有失败的情况下，并没有强制要求库函数一定要设置errno为0,这样errno的值可能
    就是前一个执行失败的库函数设置的值。
    下面更正了，可还是错误的：
    errno = 0;   
    /*调用库函数*/
    if(errno)
     /*处理错误*/

     库函数在调用成功时，既没有强制要求对errno清零，但同时也没有禁止设置errno。

     下面才是对的：

     /* 调用库函数 */
     if(返回的错误值)
        检查errno

5.5 库函数signal

    从理论上说，一个信号可能在C程序执行期间的任何时刻上发生，甚至可能出现在某些复杂的库函数（如
malloc）的执行过程中。因此从安全的角度讲，信号的处理函数不应该调用上述类型的库函数。基于同样的原
因，从signal处理函数中使用longjump退出，通常情况下也是不安全的：因为信号可能发生在malloc 或者其它
库函数开始更新某个数据结构，却又没有最后完成的过程中。因此signal处理函数能够做的安全的事情，似乎
就只有设置一个标志然后返回，期待以后主程序能够检查到这个标志，发现一个信号已经发生。

    然而，就算这样做也并不总是安全的。当一个算术运算错误引发一个信号时，某些机器在signal处理函
数返回后还将重新执行失败的操作。因此对于算术运算错误，signal处理函数的惟一安全、可移植的操作就是
打印一条出错消息，然后使用longjump或exit立即退出程序。
    当一个程序异常终止时，程序输出的最后几行常常会丢失，原因是缓冲。


                                       Chapter 6 预处理器

6.1 不能忽视空格

6.2 宏并不是函数

6.3 宏并不是语句

    #define assert(e) ((void)((e)||_assert_error(_FILE_,_LINE_)))
6.4 宏并不是类型定义

我们没有办法在一个C表达式的内部声明一个临时变量。
避免副作用的一个办法就是再引入一个变量。

在某个上下文中本应需要函数而实际上却用了函数指针，那么该指针所指向的函数将会自动地被取得并替换这
个函数指针。


                                     Chapter 7 可移植性缺陷

7.1 应对C语言标准变更
7.2 标识符名称的限制

    c标准所能保证的只是，c实现必须能够区别出前6个字符不同的外部名称，且并没有要求区分大小写。
7.3 整数的大小

    一个普通（int）整数足够大以容纳任何数组下标。

    字符长度由硬件决定
7.4 字符是有符号整数还是无符号整数

    若为有符号，则将其转为int时，应该同时复制符号位，而无符号，则填 0即可。
    一个常见的错误是：如果c是一个字符变量，使用(unsigned)c就可得到与c等价的无符号整数。这是错误
    的，因为在将字符c转换为无符号整数之前，c将先被转为int型，而此时可能得到非预期的结果。
    正确的是使用语句(unsigned char)c，这样就直接转换。
7.5 移位运算符

    如果被移位的对象长度是n位，那么移位计数必须大于或等于0,而严格小于n。

    即使某些c实现将符号位复制 到空出的位中，有符号整数的向右移位运算也并不等于除以2的某次幂。
    (-1)>>1这一般不可能为0,但(-1)/2一般为0.

7.5 内存位置0

     NULL指针并不指向任何对象，只能用于赋值或比较运算。

7.7 除法运算的截断

    q = a / b;
    r = a % b;
    C 语言的定义只保证q*b+r==a,以及当a>=0且b>0时，保证|r|<|b|以及r>=0.最好避免a为负值。

7.8 随机数的大小

    RAND_MAX

7.9 大小写转换

   
7.10 首先释放，然后重新分配

     注意早期的C实现可以realloc一个已经free了的指示针。

7.11 一个例子

     因为字符串常量可以用来表示一个字符数组，所以在数组名出现的地方都可以用字符串常量末端替换。
     如：
     "0123456789"[n%10]

     -n可能溢出，因为最小负数的绝对值大于最大正数的绝对值。所以改亦正数的符号不会有问题，而改变
      负数的符号则可能有问题。

void printnum(long n, void (*p)())
{
        if(n<0)
        {
        (*) ('-');
        n=-n;
        }
        if(n>=10)
        printnum(n/10,p);
        (*p)((int)(n%10) + '0');
}
上面的是有问题的。下面的才是对的：
void printneg(long n, void (*p)())
{
        long q;
        int r;
        q = n / 10;
        r = n % 10;
        if(r>0)
        {r -= 10;
        q++;
        }
if (n <= -10)
   printneg(q,p);
(*p)("0123456789"[-r]);
}

void printnum (long n, void (*p)())
{
        if(n < 0)
        {
        (*p)('-');
        printneg(n,p);
        }
        else
        printneg(-n,p);
}