《离散数学及其应用》章节试读

《离散数学及其应用》的笔记-第145页 - Functions

复习了下函数的定义
记几个名词：
domain, codomain
好像以前不知道的概念
injective(one to one),surjective(onto),bijective(both one to one and onto)

《离散数学及其应用》的笔记-第202页 - Algorithms

1. There are several properties that algorithms generally share:
> Input
> Output
> Definiteness
> Correctness
> Finiteness
> Effectiveness
> Generality
2. Some useful algorithms:
> linear search
> binary search
> bubble sort
> insertion sort
> Greedy algorithm

《离散数学及其应用》的笔记-第254页 - Integer Representations and Algorithms

Representation:
2 based to 8 based: each octal digit corresponds to a block of three binary digits.
2 based to 16 based: each hexadecimal digit corresponds to a block of four binary digits.
Example:
b(11 1110 1011 1100) = oct(37274)
b(11 1110 1011 1100) = hex(3EBC)
Algorithm for modular exponentiation(P 254):
procesure modular exponentiation(b: interger, n=bin(a(k-1)a(k-2)...a1a0), m: positive integers)
x := 1
power := b mod m
for i :=0 to k-1
if ai=1 then x := (x*power) mod m
power := (power * power) mod m
return x {x equals b(n) mod m}

《离散数学及其应用》的笔记-第155页 - Functions

Inverse Functions:
A function is not invertible if it is not a one-to-one correspondence.
Composition of Functions:
没什么说的
floor and ceiling function:
写程序的时候用过，原来是通用的名字。
floor: ($\lfloor x \rfloor$)
ceil: ($\lceil x \rceil$)
图解，F6\F7一目了然，很容易理解inverse Func与Compositions of Func。我们也得借鉴借鉴哇

《离散数学及其应用》的笔记-第176页 - summations and cardinality of sets

summations 复习了下序列和和一些常见序列和的公式。推导一些常见的如1+2+3..., 平方和、六方和等
candinality of sets 主要学习了两个概念：countable与uncountable。。说实话，没怎么看懂。特别是对于一个无限的集合，只要能找到一个函数一一与自然数列对应就是countable的，没理解。。

《离散数学及其应用》的笔记-第272页 - Primes and Greatest Common Divisors

1. greatest common divisors（最大公约数）
a = ($p_1^{a1} p_2^{a2} \centerdot \centerdot \centerdot p_n^{an}$)
b = ($p_1^{b1} p_2^{b2} \centerdot \centerdot \centerdot p_n^{bn}$)
gcd(a, b) = ($p_1^{min(a1,b1)} p_2^{min(a2,b2)} \centerdot \centerdot \centerdot p_n^{min(an, bn)}$)
lcm(a, b) = ($p_1^{max(a1,b1)} p_2^{max(a2,b2)} \centerdot \centerdot \centerdot p_n^{max(an, bn)}$)
Euclidean algorithm:
a = bq + r => gcd(a, b) = gcd(b, r)
then, for example:
gcd(287,91) = gcd(91, 287 % 91) = gcd (287 % 91, 91 % (287 % 91)) ...
until one of the integers is zero.