• 内置数据类型

1. Booleans【布尔型】 或为 True［真］ 或为 False［假］。
2. Numbers【数值型】 可以是 Integers【整数】（1 和 2）、Floats【浮点数】（1.1 和 1.2）、Fractions【分数】（1/2 和 2/3）；甚至是 Complex Number【复数】。
3. Strings【字符串型】 是 Unicode 字符序列，例如： 一份 html 文档。
4. Bytes【字节】 和 Byte Arrays【字节数组】， 例如: 一份 jpeg 图像文件。
5. Lists【列表】 是值的有序序列。
6. Tuples【元组】 是有序而不可变的值序列。
7. Sets【集合】 是装满无序值的包裹。
8. Dictionaries【字典】 是键值对的无序包裹。

• 内置异常类型

1. BaseException: 所有内建异常的基础类。
2. Exception: 所有的内建的、非系统预置的异常均继承这个类，所有用户定义的异常也应该继承这个类。
3. StandardError: 所有内建异常的基础类，除了StopIteration, GeneratorExit, KeyboardInterrupt和SystemExit。 StandardError 是继承Exception而来的。
4. ArithmeticError: 一些内建算术错误异常的基类，如： OverflowError, ZeroDivisionError,FloatingPointError.
5. LookupError: 当一个键值或索引在数组或序列中无效时所触发的所有异常的基类: IndexError,KeyError. 它也会由sys.setdefaultencoding()直接触发。
6. EnvironmentError: 所有能发生在Python系统之外的异常的基类:IOError, OSError.
7. AssertionError: 当判定条件失败时，触发此异常。
8. AttributeError: 当一个属性被引用或赋值时出现错误会引发此异常（当一个对象不支持属性被引用或赋值时，会触发TypeError异常）
9. EOFError: 当内建函数(input() 或 raw_input()) 达到文件尾时触发此异常。
10. FloatingPointError: 浮点操作失败时触发此异常。
11. GeneratorExit: 当调用生成器的close() 方法时，触发此异常。它直接继承了Exception 用于替代 StandardError ，毕竟这是一个技术手段并不是一个错误异常。
12. IOError: 当I/O操作(如一个 print 语句、内建 open()函 数或调用文件对象的某个方法)因为I/O相关的问题而失败时触发此异常，例如：“无此文件”或“没有足够的磁盘空间”。这个类继承于EnvironmentError。
13. ImportError: 当 import 语句无法找到对应的模块定义或from…import 无法找到对应名字的内容时触发此异常。
14. IndexError: 当一个序列子集超出范围时触发此异常。(索引会被截取以保证在合理的范围内； 如果索引x不是一个整数， TypeError异常会被触发)
15. KeyError: 当键值并不存在于图（字典）中，会触发此异常。
16. KeyboardInterrupt: 当用户按下终止键时触发此异常（通常是Ctrl+C或者Delete键）。
17. MemoryError: 当某些操作导致内存耗尽但应能恢复的情况下（通过删除一些对象来释放内存），触发此异常。
18. NameError: 当无法找到对应名字的本地变量或全局变量时，触发此异常。这只针对无效的名字。 附带参数是包含了无法找到的名字的错误信息。
19. NotImplementedError: 这个异常继承于 RuntimeError. 用户定义基类后，抽象方法可以触发这个异常来要求派生类必须实现该抽象方法。
20. OSError: 这个类继承于 EnvironmentError ，主要用于os模块的os.error异常。
21. OverflowError: 当一个算术运算太大导致数值溢出时触发此异常。
22. ReferenceError: weakref.proxy()函数产生一个弱引用代理时，此异常被触发。弱引用代理通常访问一个被引用对象的属性，但这个对象已经被垃圾回收。更多的弱引用信息，请参考weakref模块。
23. RuntimeError: 当一个无法分类的错误发生时，触发该异常。
24. StopIteration: 当一个迭代器的next()方法无法获得更多的值时，触发该异常。
25. SyntaxError: 当语法解析器遇到语法错误时触发此异常。
26. SystemError: 当解释程序遇到一个内部错误，但是情况看来可以纠正，不需要放弃退出。辅助参数是一个字符串，标明在更顶层什么出错了。
27. SystemExit: 这个异常被 sys.exit() 函数触发。当这个异常没有被有效处理，Python终止程序并退出；没有堆栈信息打印。如果辅助参数是整数，它表示系统退出状态（和C语言的exit() 函数类似）；如果它是空则退出状态为0；如果它是其它类型（例如字符串），这个对象会被打印输出，并且退出状态为1。
28. TypeError: 当一个操作或函数调用一个不恰当的对象类型时，触发此异常。附带参数是一个字符串，表明具体的不匹配的类型。
29. UnboundLocalError: 当在一个函数或方法内引用本地变量但变量并没有赋值时，触发此异常。
30. UnicodeDecodeError: 当一个Unicode相关的编码、解码错误发生时，触发此异常。它是ValueError的子类。
31. UnicodeEncodeError: 在文字编码时发生一个Unicode相关的错误则触发此异常。它是UnicodeError的子类。
32. UnicodeError: 在文字解码时发生一个Unicode相关的错误则触发此异常。它是UnicodeError的子类。
33. UnicodeTranslateError: 在转换文字编码时，当一个Unicode相关的错误发生，触发此异常。它是UnicodeError的子类。
34. ValueError: 当一个内建操作或函数接收了参数，参数的类型是对的但值并不符合并且无法匹配一个更加精准的异常（例如：IndexError）， 触发此异常。
35. WindowsError: 当Windows系统下特定的错误发生或当错误编号无法映射 errno值时，触发此异常。
36. ZeroDivisionError: 当除法或取余操作分母为0时，触发此异常。附带的参数是一个文字信息，标明了运算类型和具体运算数据。

异常处理详解：http://www.w3cschool.cc/python/python-exceptions.html

• Python yield

带有 yield 的函数在 Python 中被称之为 generator（生成器）。
用yield生成Fibonacci序列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def fib(max): 
    n, a, b = 0, 0, 1 
    while n < max: 
        yield b 
        a, b = b, a + b 
        n = n + 1
        
for i in fib(5):
	print(i)

	
1
1
2
3
5

yield 的作用就是把一个函数变成一个 generator，带有 yield 的函数不再是一个普通函数，Python 解释器会将其视为一个 generator，调用 fib(5) 不会执行 fib 函数，而是返回一个 iterable 对象！在 for 循环执行时，每次循环都会执行 fib 函数内部的代码，执行到 yield b 时，fib 函数就返回一个迭代值，下次迭代时，代码从 yield b 的下一条语句继续执行，而函数的本地变量看起来和上次中断执行前是完全一样的，于是函数继续执行，直到再次遇到 yield。
调用fib函数可以看到其返回一个generator object:

1
2

>>> fab(5)
<generator object fib at 0x010DEE40>

• import

使用import导入模块，可以自定义模块，模块名即文件名不含后缀。在程序中使用import时，Python解释器会依照特定路径搜索。可以使用sys.path查看：

1
2
3
4
5

>>> import sys
>>> sys.path
['', 'C:\\Python33\\Lib\\idlelib', 'C:\\WINDOWS\\system32\\python33.zip', 'C:\\Python33\\DLLs', 'C:\\Python33\\lib', 'C:\\Python33', 'C:\\Python33\\lib\\site-packages']
>>> sys.path[0]
''

sys.path[0]表示当前目录。

• __name__ 变量

由于主程序代码无论模块是被导入还是被直接执行都会运行，我们必须知道模块如何决定运行方向。一个应用程序可能需要导入另一个应用程序的一个模块，以便重用一些有用的代码。如果模块是被导入， __name__ 的值为模块名字；如果模块是被直接执行， __name__ 的值为 ‘main‘

• 运算符优先级(从高到低)

• 类成员访问控制

Python并不支持正式的访问控制。但是有一个惯例，那就是以单下划线_开头的成员被认为是protected的(本类和子类是可以访问的)，以双下划线__开头的成员被认为是private的(只在本类可以访问)。

• __slots__用法

一般来说，一个实例可以动态地添加任意新的属性，Python中每个实例均有一个__dict__属性，其为字典类型，它保存着实例的所有属性。如果不想在实例化时生成__dict__，我们可以使用__slots__。具体做法是在类中申明__slots__ = (属性1, 属性2, 属性3...)，那么类的实例对象便不能再添加新的属性。
举例说明：
先不用__slots__

1
2
3
4
5
6
7

class Person:
	def __init__(self, name, age, height):
		self._name = name
		self._age = age
		self._height = height

zhangsan = Person('zhangsan', 21, 180)

查看__dict__：

1
2

>>> zhangsan.__dict__
{'_name': 'zhangsan', '_height': 180, '_age': 21}

动态添加成员变量：

1
2
3

>>> zhangsan._weight = 65
>>> zhangsan.__dict__
{'_name': 'zhangsan', '_weight': 65, '_height': 180, '_age': 21}

如果使用__slots__：

1
2
3
4
5
6
7
8

class Person:
	__slots__ = ('_name', '_age', '_height')
	def __init__(self, name, age, height):
		self._name = name
		self._age = age
		self._height = height

zhangsan = Person('zhangsan', 21, 180)

再来查看__dict__：

1
2
3
4
5

>>> zhangsan.__dict__
Traceback (most recent call last):
  File "<pyshell#20>", line 1, in <module>
    zhangsan.__dict__
AttributeError: 'Person' object has no attribute '__dict__'

添加成员变量：

1
2
3
4
5

>>> zhangsan._weight = 65
Traceback (most recent call last):
  File "<pyshell#21>", line 1, in <module>
    zhangsan._weight = 65
AttributeError: 'Person' object has no attribute '_weight'

可见使用__slots__之后类中的成员变量便不可再更改。
什么时候使用__slots__？
一般情况下不使用__slots__，只有在生成大量实例并且实例的成员变量固定的情况下使用__slots__可以节约内存。(不用保存__dict__)
这里有一个例子来说明节约内存的情况：http://tech.oyster.com/save-ram-with-python-slots/

文章结尾有一条：
Warning: Don’t prematurely optimize and use this everywhere! It’s not great for code maintenance, andit really only saves you when you have thousands of instances.

算法描述：

给定一个图和一个起点，找出该起点到图中其他各顶点的最短路径。Dijkstra算法是一种贪心算法。

Dijkstra算法和Prim算法非常相似。我们可以生成一棵以起点为根的最短路径树(shortest path tree)。然后我们维护2个集合：一个集合是最短路径树中的所有顶点(假设为A)；另一个集合是其他顶点(假设为B)。
通过迭代，每次在B中找一个到起点距离最短的顶点，加入到A中；当B为空集时，算法结束。

下面是具体的算法：

(1) 创建一个sptSet (最短路径树集合)，初始化该集合为空集。
(2) 给图中所有顶点赋值一个距离，初始化起点为0，其他顶点为INFINITE(无穷大∞)
(3)只要sptSet没有包含所有顶点：
a)从B中选一个顶点u, u的距离值最小。
b)将u加入sptSet.
c)更新u的邻接顶点的距离值，对于每一个邻接顶点v, 如果u的距离值加上边u-v的权值小于v的距离值，那么就更新v的距离值。(更新为u的距离值加上u-v的权值)

来看一个具体的例子:

选取顶点0为起始点。sptSet现在是空集，各顶点的距离值分别是{0, ∞, ∞, ∞, ∞, ∞, ∞, ∞}
顶点0加入到sptSet集合中，sptSet为{0}，然后更新顶点0的邻接顶点1和7，此时1的距离值为4, 7的距离值为8。
sptSet中的顶点显示为绿色：(∞的顶点未予显示)
选取距离值最小但不在sptSet集合中的顶点，因为1的距离值最小，所以将1加入sptSet中，现在sptSet变为{0, 1}。更新1的邻接顶点的距离值：2的距离值变为4+8=12
现在继续选取距离值最小但不在sptSet集合中的顶点，此时7为最小，所以选取7，sptSet变为{0, 1, 7}。接着更新7的邻接顶点：6的距离值变为8+1=9，8的距离值变为8+7=15
现在选取顶点6，sptSet变为{0, 1, 7, 6}。接着更新6的邻接顶点：5的距离值变为9+2=11，8的距离值为9+6=15
现在选取顶点5，sptSet变为{0, 1, 7, 6, 5}，更新5的邻接顶点：2为11+4=15>12故不更新，3为11+14=25，4为11+10=21

现在选取顶点2，sptSet变为{0, 1, 7, 6, 5, 2}，更新2的邻接顶点：3为12+7=19\<25 故更新3的距离值为19，8为12+2=14\<15 故更新8的距离值为14，5为12+4="16">11故不更新。

现在选取顶点8，sptSet变为{0, 1, 7, 6, 5, 2, 8}，8的邻接顶点：2, 7, 6不用更新。

现在选取顶点3，sptSet变为{0, 1, 7, 6, 5, 2, 8, 3}，3的邻接顶点2, 5, 4不用更新。

最后选取顶点4，sptSet变为{0, 1, 7, 6, 5, 2, 8, 3, 4}，此时已经包含图中所有顶点，故为最终结果。

C语言实现：
我们使用一个boolean数组sptSet[]表示SPT中的顶点，如果stpSet[v]=true, 则顶点v在SPT中。数组dist[]存贮所有顶点的最短路径值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>
typedef enum {false, true}bool;
// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
   // Initialize min value
   int min = INT_MAX, min_index;

   for (int v = 0; v < V; v++)
     if (sptSet[v] == false && dist[v] <= min)
         min = dist[v], min_index = v;

   return min_index;
}

// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
   printf("Vertex   Distance from Source\n");
   for (int i = 0; i < V; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}

// Funtion that implements Dijkstra's single source shortest path algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
     int dist[V];     // The output array.  dist[i] will hold the shortest
                      // distance from src to i

     bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                     // path tree or shortest distance from src to i is finalized

     // Initialize all distances as INFINITE and stpSet[] as false
     for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

     // Distance of source vertex from itself is always 0
     dist[src] = 0;

     // Find shortest path for all vertices
     for (int count = 0; count < V-1; count++)
     {
       // Pick the minimum distance vertex from the set of vertices not
       // yet processed. u is always equal to src in first iteration.
       int u = minDistance(dist, sptSet);

       // Mark the picked vertex as processed
       sptSet[u] = true;

       // Update dist value of the adjacent vertices of the picked vertex.
       for (int v = 0; v < V; v++)

         // Update dist[v] only if is not in sptSet, there is an edge from
         // u to v, and total weight of path from src to  v through u is
         // smaller than current value of dist[v]
         if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
                                       && dist[u]+graph[u][v] < dist[v])
            dist[v] = dist[u] + graph[u][v];
     }

     // print the constructed distance array
     printSolution(dist, V);
}

// driver program to test above function
int main()
{
   /* Let us create the example graph discussed above */
   int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                      {4, 0, 8, 0, 0, 0, 0, 11, 0},
                      {0, 8, 0, 7, 0, 4, 0, 0, 2},
                      {0, 0, 7, 0, 9, 14, 0, 0, 0},
                      {0, 0, 0, 9, 0, 10, 0, 0, 0},
                      {0, 0, 4, 0, 10, 0, 2, 0, 0},
                      {0, 0, 0, 14, 0, 2, 0, 1, 6},
                      {8, 11, 0, 0, 0, 0, 1, 0, 7},
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}
                     };

    dijkstra(graph, 0);

    return 0;
}

输出：

1
2
3
4
5
6
7
8
9
10

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14

时间复杂度是\( O(V^2)\)，Dijkstra算法不适用于带负权值的图。

在密码学中重要的是能有效地求$ b^n mod (m) $, 其中$b, n, m$都是大整数。先计算$b^n$，再求$b^n$除以$m$的余数是不可行的，因为$b^n$是非常大的数。可行的是一种利用指数n的二进制展开的算法。这个算法依次求
$$
b mod (m), b^2 mod (m), b^4 mod (m), …, b^{2^{k-1}} mod (m)
$$
把其中$a_j = 1$的那些项$b^{2^j} mod(m)$相乘，在每次乘法后求乘积除以m的余数。

算法伪代码如下：

1
2
3
4
5
6
7

x = 1
power = b mod(m)
for i = 0 to k-1
begin
if a_i = 1 then x = x * power mod(m)
power = power * power mod(m)
end

如果p ↔ q是永真式，命题p和q称为是逻辑等价的。记号p≡q表示p和q逻辑等价。

• 逻辑等价公式

1. Identity laws 恒等律：

   p∧T≡p
   p∨F≡P

2. Domination laws 支配律：

   p∨T≡T
   p∧F≡F

3. Idempotent laws 幂等律:

   p∨p≡p
   p∧p≡p

4. Double negation laws 双非律:

   ﹁(﹁p)≡p

5. Commutative laws 交换律:

   p∨q≡q∨p
   p∧q≡q∧p

6. Assocative laws 结合律:

   (p∨q)∨r≡p∨(q∨r)
   (p∧q)∧r≡p∧(q∧r)

7. Distributive laws 分配律:

   p∨(q∧r)≡(p∨q)∧(p∨r)
   p∧(q∧r)≡(p∧q)∨(p∧r)

8. De Morgan’s laws 德摩根律:

   ﹁(p∧q)≡﹁p∨﹁q
   ﹁(p∨q)≡﹁p∧﹁q

9. Absorption laws 吸收律:

   p∨(p∧q)≡p
   p∧(p∨q)≡p

10. Negation laws 否定律:

    p∨﹁p≡T
    p∧﹁p≡F

• 包括蕴涵的逻辑等价：

1. p→q≡﹁p∨q
2. p→q≡﹁q→﹁p
3. p∨q≡﹁p→q
4. p∧q≡﹁(p→﹁q)
5. ﹁(p→q)≡p∧﹁q
6. (p→q)∧(p→r)≡p→(q∧r)
7. (p→q)∨(p→r)≡p→(q∨r)
8. (p→r)∧(q→r)≡(p∧q)→r
9. (p→r)∨(q→r)≡(p∨q)→r

• 包含双蕴涵（逻辑双条件）的逻辑等价：

1. p↔q≡(p→q)∧(q→p)
2. p↔q≡﹁p↔﹁q
3. p↔q≡(p∧q)∨(﹁p∧﹁q)
4. ﹁(p↔q)≡p↔﹁q

证明(p∧q)→q为永真式:

证明：(p∧q)→q ⇔ ﹁(p∧q)∨q
⇔ (﹁p∨﹁q)∨q (根据德摩根律)
⇔ ﹁p∨(﹁q∨q) (根据结合律)
⇔ ﹁p∨T (根据否定律)
⇔ T (根据支配律)
由此得证。