第一篇：hash算法
Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
数学表述为：h = H(M)，其中H()--单向散列函数，M--任意长度明文，h--固定长度散列值。
在信息安全领域中应用的Hash算法，还需要满足其他关键特性：
第一当然是单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的 Hash 又被称为“消息摘要(message digest)”，就是要求能方便的将“消息”进行“摘要”，但在“摘要”中无法得到比“摘要”本身更多的关于“消息”的信息。
第二是抗冲突性(collision-resistant)，即在统计上无法产生2个散列值相同的预映射。给定M，计算上无法找到M'，满足H(M)=H(M')，此谓弱抗冲突性；计算上也难以寻找一对任意的M和M'，使满足H(M)=H(M')，此谓强抗冲突性。要求“强抗冲突性”主要是为了防范所谓“生日攻击(birthday attack)”，在一个10人的团体中，你能找到和你生日相同的人的概率是2.4%，而在同一团体中，有2人生日相同的概率是11.7%。类似的，当预映射的空间很大的情况下，算法必须有足够的强度来保证不能轻易找到“相同生日”的人。
第三是映射分布均匀性和差分分布均匀性，散列结果中，为 0 的 bit 和为 1 的 bit，其总数应该大致相等；输入中一个 bit 的变化，散列结果中将有一半以上的 bit 改变，这又叫做“雪崩效应(avalanche effect)”；要实现使散列结果中出现 1bit 的变化，则输入中至少有一半以上的 bit 必须发生变化。其实质是必须使输入中每一个 bit 的信息，尽量均匀的反映到输出的每一个 bit 上去；输出中的每一个 bit，都是输入中尽可能多 bit 的信息一起作用的结果。
Damgard 和 Merkle 定义了所谓“压缩函数(compression function)”，就是将一个固定长度输入，变换成较短的固定长度的输出，这对密码学实践上 Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复“压缩”输入的分组和前一次压缩处理的结果的过程，直到整个消息都被压缩完毕，最后的输出作为整个消息的散列值。尽管还缺乏严格的证明，但绝大多数业界的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息也将是安全的。这就是所谓 Damgard/Merkle 结构：
在下图中，任意长度的消息被分拆成符合压缩函数输入要求的分组，最后一个分组可能需要在末尾添上特定的填充字节，这些分组将被顺序处理，除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外，当前分组将和前一个分组的压缩函数输出一起被作为这一次
压缩的输入，而其输出又将被作为下一个分组压缩函数输入的一部分，直到最后一个压缩函数的输出，将被作为整个消息散列的结果。
MD5 和 SHA1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。
1)MD4
MD4(RFC 1320)是 MIT 的 Ronald L.Rivest 在 1990 年设计的，MD 是 Message
Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。它的安全性不像RSA那样基于数学假设，尽管 Den Boer、Bosselaers 和 Dobbertin 很快就用分析和差分成功的攻击了它3轮变换中的 2 轮，证明了它并不像期望的那样安全，但它的整个算法并没有真正被破解过，Rivest 也很快进行了改进。
下面是一些MD4散列结果的例子：
MD4(“")= 31d6cfe0d16ae931b73c59d7e0c089c0
MD4(”a“)= bde52cb31de33e46245e05fbdbd6fb24
MD4(”abc“)= a448017aaf21d8525fc10ae87aa6729d
MD4(”message digest“)= d9130a8164549fe818874806e1c7014b
MD4(”abcdefghijklmnopqrstuvwxyz“)= d79e1c308aa5bbcdeea8ed63df412da9
MD4(”ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789“)= 043f8582f241db351ce627e153e7f0e4
MD4
(”***************67890“)= e33b4ddc9c38f2199c3e7b164fcc0536
2)MD5
MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。它较MD4所做的改进是：
1)加入了第四轮
2)每一步都有唯一的加法常数；
3)第二轮中的G函数从((X ∧ Y)∨(X ∧ Z)∨(Y ∧ Z))变为((X ∧ Z)∨(Y ∧ ～Z))以减小其对称性；
4)每一步都加入了前一步的结果，以加快”雪崩效应“；
5)改变了第2轮和第3轮中访问输入子分组的顺序，减小了形式的相似程度；
6)近似优化了每轮的循环左移位移量，以期加快”雪崩效应“，各轮的循环左移都不同。尽管MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好。
消息首先被拆成若干个512位的分组，其中最后512位一个分组是”消息尾+填充字节
(100...0)+64 位消息长度“，以确保对于不同长度的消息，该分组不相同。64位消息长度的限制导致了MD5安全的输入长度必须小于264bit，因为大于64位的长度信息将被忽略。而4个32位寄存器字初始化为A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它们将始终参与运算并形成最终的散列结果。
接着各个512位消息分组以16个32位字的形式进入算法的主循环，512位消息分组的个数据决定了循环的次数。主循环有4轮，每轮分别用到了非线性函数
F(X, Y, Z)=(X ∧ Y)∨(～X ∧ Z)
G(X, Y, Z)=(X ∧ Z)∨(Y ∧ ～Z)
H(X, Y, Z)=X ⊕ Y ⊕ Z
I(X, Y, Z)= X ⊕(Y ∨ ～Z)
这4轮变换是对进入主循环的512位消息分组的16个32位字分别进行如下操作：将A、B、C、D的副本a、b、c、d中的3个经F、G、H、I运算后的结果与第4个相加，再加上32位字和一个32位字的加法常数，并将所得之值循环左移若干位，最后将所得结果加上a、b、c、d之一，并回送至ABCD，由此完成一次循环。
所用的加法常数由这样一张表T[i]来定义，其中i为1...64，T[i]是i的正弦绝对值之
4294967296次方的整数部分，这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性性。
当所有512位分组都运算完毕后，ABCD的级联将被输出为MD5散列的结果。下面是一些MD5散列结果的例子：
MD5(”“)= d41d8cd98f00b204e9800998ecf8427e
MD5(”a“)= 0cc175b9c0f1b6a831c399e269772661
MD5(”abc“)= 900150983cd24fb0d6963f7d28e17f72
MD5(”message digest“)= f96b697d7cb7938d525a2f31aaf161d0
MD5(”abcdefghijklmnopqrstuvwxyz“)= c3fcd3d76192e4007dfb496cca67e13b
MD5(”ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789“)= d174ab98d277d9f5a5611c2c9f419d9f
MD5
(”***************67890“)= 57edf4a22be3c955ac49da2e2107b67a
参考相应RFC文档可以得到MD4、MD5算法的详细描述和算法的C源代码。
3)SHA1 及其他
SHA1是由NIST NSA设计为同DSA一起使用的，访问可以得到它的详细规范--[/url]”FIPS PUB 180-1 SECURE HASH STANDARD“。它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。因为它将产生160bit的散列值，因此它有
5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是4轮，但每轮进行20次操作，非线性运算、移位和加法运算也与MD5类似，但非线性函数、加法常数和循环左移操作的设计有一些区别，可以参考上面提到的规范来了解这些细节。下面是一些SHA1散列结果的例子：
SHA1(”abc“)= a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d
SHA1(”abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq“)= 84983e44 1c3bd26e baae4aa1 f95129e5 e54670f1
其他一些知名的Hash算法还有MD2、N-Hash、RIPE-MD、HAVAL等等。上面提到的这些都属于”纯“Hash算法。还有另2类Hash算法，一类就是基于对称分组算法的单向散列算法，典型的例子是基于DES的所谓Davies-Meyer算法，另外还有经IDEA改进的Davies-Meyer算法，它们两者目前都被认为是安全的算法。另一类是基于模运算/离散对数的，也就是基于公开密钥算法的，但因为其运算开销太大，而缺乏很好的应用前景。
没有通过分析和差分攻击考验的算法，大多都已经夭折在实验室里了，因此，如果目前流行的Hash算法能完全符合密码学意义上的单向性和抗冲突性，就保证了只有穷举，才是破坏Hash运算安全特性的唯一方法。为了对抗弱抗冲突性，我们可能要穷举个数和散列值空间长度一样大的输入，即尝试2^128或2^160个不同的输入，目前一台高档个人电脑可能需要10^25年才能完成这一艰巨的工作，即使是最高端的并行系统，这也不是在几千年里的干得完的事。而因为”生日攻击“有效的降低了需要穷举的空间，将其降低为大约1.2*2^64或1.2*2^80，所以，强抗冲突性是决定Hash算法安全性的关键。
在NIST新的 Advanced Encryption Standard(AES)中，使用了长度为128、192、256bit 的密钥，因此相应的设计了 SHA256、SHA384、SHA512，它们将提供更好的安全性。
Hash算法在信息安全方面的应用主要体现在以下的3个方面：
1)文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的”数字指纹“特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。它常被用在下面的2种情况下：
第一是文件传送后的校验，将得到的目标文件计算 md5 checksum，与源文件的md5 checksum 比对，由两者 md5 checksum 的一致性，可以从统计上保证2个文件的每一个码元也是完全相同的。这可以检验文件传输过程中是否出现错误，更重要的是可以保证文件
在传输过程中未被恶意篡改。一个很典型的应用是ftp服务，用户可以用来保证多次断点续传，特别是从镜像站点下载的文件的正确性。
更出色的解决方法是所谓的代码签名，文件的提供者在提供文件的同时，提供对文件Hash值用自己的代码签名密钥进行数字签名的值，及自己的代码签名证书。文件的接受者不仅能验证文件的完整性，还可以依据自己对证书签发者和证书拥有者的信任程度，决定是否接受该文件。浏览器在下载运行插件和java小程序时，使用的就是这样的模式。
第二是用作保存二进制文件系统的数字指纹，以便检测文件系统是否未经允许的被修改。不少系统管理/系统安全软件都提供这一文件系统完整性评估的功能，在系统初始安装完毕后，建立对文件系统的基础校验和数据库，因为散列校验和的长度很小，它们可以方便的被存放在容量很小的存储介质上。此后，可以定期或根据需要，再次计算文件系统的校验和，一旦发现与原来保存的值有不匹配，说明该文件已经被非法修改，或者是被病毒感染，或者被木马程序替代。TripWire就提供了一个此类应用的典型例子。
更完美的方法是使用”MAC“。”MAC“ 是一个与Hash密切相关的名词，即信息鉴权码
(Message Authority Code)。它是与密钥相关的Hash值，必须拥有该密钥才能检验该Hash值。文件系统的数字指纹也许会被保存在不可信任的介质上，只对拥有该密钥者提供可鉴别性。并且在文件的数字指纹有可能需要被修改的情况下，只有密钥的拥有者可以计算出新的散列值，而企图破坏文件完整性者却不能得逞。
2)数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。
在这种签名协议中，双方必须事先协商好双方都支持的Hash函数和签名算法。
签名方先对该数据文件进行计算其散列值，然后再对很短的散列值结果--如Md5是16个字节，SHA1是20字节，用非对称算法进行数字签名操作。对方在验证签名时，也是先对该数据文件进行计算其散列值，然后再用非对称算法验证数字签名。
对 Hash 值，又称”数字摘要“进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点：
首先，数据文件本身可以同它的散列值分开保存，签名验证也可以脱离数据文件本身的存在而进行。
再者，有些情况下签名密钥可能与解密密钥是同一个，也就是说，如果对一个数据文件签名，与对其进行非对称的解密操作是相同的操作，这是相当危险的，恶意的破坏者可能将一个试图骗你将其解密的文件，充当一个要求你签名的文件发送给你。因此，在对任何数据文件进行数字签名时，只有对其Hash值进行签名才是安全的。
3)鉴权协议
如下的鉴权协议又被称作”挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。
需要鉴权的一方，向将被鉴权的一方发送随机串（“挑战”），被鉴权方将该随机串和自己的鉴权口令字一起进行 Hash 运算后，返还鉴权方，鉴权方将收到的Hash值与在己端用该随机串和对方的鉴权口令字进行 Hash 运算的结果相比较（“认证”），如相同，则可在统计上认为对方拥有该口令字，即通过鉴权。
POP3协议中就有这一应用的典型例子：
S: +OK POP3 server ready <1896.697170952@dbc.mtview.ca.us>
C: APOP mrose c4c9334bac560ecc979e58001b3e22fb
S: +OK maildrop has 1 message(369 octets)
在上面的一段POP3协议会话中，双方都共享的对称密钥（鉴权口令字）是tanstaaf，服务器发出的挑战是<1896.697170952@dbc.mtview.ca.us>，客户端对挑战的应答是MD5(“<1896.697170952@dbc.mtview.ca.us>tanstaaf”)=
c4c9334bac560ecc979e58001b3e22fb，这个正确的应答使其通过了认证。
散列算法长期以来一直在计算机科学中大量应用，随着现代密码学的发展，单向散列函数已经成为信息安全领域中一个重要的结构模块，我们有理由深入研究其设计理论和应用方法。
第二篇：HASH算法安全性浅谈
HASH算法安全性浅谈
2011年12月，CSDN网站遭到黑客攻击，约600万用户的登录名、密码及邮箱遭到泄漏。随后，CSDN“密码外泄门”持续发酵，世纪佳缘、人人网、天涯社区等网站相继被曝出用户数据遭泄密，大量的用户账号和密码被公开，数量超过5000万。此次密码泄漏堪称近年来国内规模最大的网络安全事件。
事后，密码明文保存被认为是此次事件的“罪魁祸首”。当前，互联网越来越进入人们的生活。用户访问各种网站，在注册的时候需要输入用户名和密码，在仅仅考虑功能的前提下，可以把用户名和密码以明文的方式存储在数据表中。当用户登录时，直接将用户输入的明文密码与数据库中的密码进行比对，如果相同则授权用户登录。
明文密码保存方式在实现上非常简单，但面临的问题也很明显，那就是没有任何安全防护机制。任何有权读取或以某种方式获得数据库的人都可以获取所有用户的密码。因此我们需要一种即使数据文件被窃取，窃取者也不能获得用户密码的方式。
现在网站已经基本不再使用明文密码保存的方式，而是在数据库中保存散列算法处理的结果。通过HASH散列函数的方式，可以有效的降低密码泄露的风险。HASH散列函数是把输入的密码数据通过特定的算法处理后，输出为一个固定长度的字符串。这样，当用户输入密码时，直接将该密码代入散列算法得出散列结果，再与保存的数据对比，相同则允许登录。如“abc”经过MD5散列之后，结果为
“900150983CD24FB0D6963F7D28E17F72”，将这个字符串保存到数据库中替代密码明文。通过HASH函数的处理，即使密码数据库文件被窃取，窃取者也不能直观的获取到账号的密码。
HASH散列函数的特点是单向性，即由输入数据可以得到确定的输出字符串，但从输出的字符串反向获取输入数据的难度很大，几乎是不可能做到的。
目前常见的散列算法有MD5和SHA1。MD5的输出是128位字符串，SHA1的输出是160位字符串。还有更复杂的SHA256，SHA512，其输出分别是256位和512位。输出结果的长度越长，HASH函数的安全性就越高。
当前HASH散列算法最大的安全隐患就是字典攻击。所谓字典攻击，即根据密码所使用字符范围及密码长度穷举出所有可能的密码，对这些密码进行HASH处理，把HASH值保存在数据库中，一旦获得用户密码HASH值，将其与数据库中的HASH值进行对比，就可以快速的找到明文密码。
对抗字典攻击的办法主要是限制密码最短长度，扩大密码字符组成，采用更长位数的HASH散列算法。这些都可以增加攻击者生成字典的时间成本和经济成本。
个人认为还可以参照3DES加密算法，采用多重HASH算法，即对HASH值再进行多次HASH处理，这样也可以增加攻击者破解难度。但在各种资料中，尚未看到有人有提到此种方法，不知何故。
上述方法都是不断增加攻击者的难度，但随着现在计算机的计算
速度和存储能力的不断提高，攻击者破解的时间、经济成本都在不断降低，因此这些方法都不是永久有效的。
2004年，山东大学王小云教授公布了利用差分技术实现对HASH算法的碰撞攻击，随后又公布了碰撞攻击的详细原理过程。MD5、SHA-1是当前国际通行的两大密码标准。MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Ronald L.Rivest设计，SHA-1是由美国专门制定密码算法的标准机构——美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。
王小云教授的碰撞攻击算法，具有非常重要的理论意义，对密码学的发展具有极大的推动作用，为HASH函数的密码分析学开辟了一条新的道路。碰撞算法从理论上表明了电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。这一成果说明了MD5和SHA1已经不能用作身份验证或数字签名，另外在理论上说明了数字摘要算法用于数据的完整性鉴别具有先天缺陷。但另一方面，由于方法上的限制，要构造具有特定语义的碰撞攻击几乎是不可能的，因此并不是所有采用MD5等算法的应用都彻底失效。在实际中，MD5和SHA1算法经常与其它算法一起使用，或者进行了很多变形，简单地找到MD5碰撞对并没有实际性的威胁。
同时，她的研究成果也给其他研究者以极大的参考价值，后续研究者在其基础上，不断推出新的研究成果。2005年3月，用笔记本
在几个小时内找到MD5碰撞；2006年3月，用笔记本在1分钟内找到MD5碰撞；2007年12月，用Chosen-Prefix Collision，伪造出了符合X.509标准的数字证书；2008年12月，利用MD5碰撞，创造了一个假的来自可信CA的数字证书。因此，寻找MD5 碰撞的算法的时间、空间复杂度都已降至实用水平。但从实践角度，不同信息具有相同MD5值的可能性还是非常低的，通过碰撞的方法也很难碰撞出复杂信息的MD5值。现在MD5破译技术的研究者们正重点研究MD5碰撞的实际应用。
为了防止网络监听及重放攻击，在网站登录过程中，通常还使用干扰字符串，即在用户登录时，服务器随机生成一段前缀或后缀字符串，浏览器将用户的密码HASH处理后，再加上干扰字符串，再HASH处理一遍，再提交给服务器。干扰字符串是随机生成，用过一次即失效，因此即使登录过程中HASH值被截取，也无法再次使用其来登录。
如果需要更安全的算法，建议使用SHA256或SHA512。目前还没有出现针对SHA256，SHA512算法的有效碰撞攻击方法。该算法可以是MD5及SHA1的不错的后继者。
总之，HASH算法是在不断被破解的过程中，不断改进的。所谓“魔高一尺，道高一丈。”其安全性也是在不断提高的。当前主流的MD5和SHA1正在改为SHA256和SHA512。或许以后还会有更复杂的HASH演进算法，甚至更高级的密码处理算法，我们都拭目以待。
对于碰撞攻击的实际应用研究，我们也持续关注。王小云教授的差分碰撞攻击算法，虽然里面没有太高深的数学算法，但过程还是很
复杂繁琐的，有兴趣可以参考其原始论文，仔细研读分析。碰撞攻击的后续研究成果也有很大的参考价值。论文列举如下：
Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD； How to Break MD5 and other Hash Functions；
Finding Collisions in the Full SHA-1；
Finding MD5 Collisions a Toy For a Notebook；
Tunnels in Hash Functions MD5 Collisions Within a Minute； Efficient Hash Collision Search Strategies on Special-Purpose Hardware；
Chosen-prefix Collisions for MD5 and Applications；
Fast Collision Attack on MD5。
第三篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
第四篇：算法复习材料
1.假票统计
问题描述：
由于你们团队在国际大学生诗歌大赛上取得的巨大成就，你们学校决定为你们召开一次庆功鸡尾酒会，到来的人数大大超出了预期。然而庆功会的主管却抱怨发现了有人使用假票，实际的门票是从1到N(N <= 10000)，主管怀疑有人采用复印、打印等手段伪造了门票。他把所有收上来的门票拿给你，要求你编写程序，统计所有门票中存在假票的门票数。输入：
输入文件中包含多组测试数据，每组测试数据占两行。第1行包括两个整数N和M，分别表示门票的初始总张数和参加晚会的总人数(1 <= N <= 10000,1 <= M <= 20000)。第2行为M个整数Ti，表示收到的M张门票的号码(1 <= Ti <= N)。输入文件最后一行为0 0，表示输入结束。输出：
对每组输入测试数据，输出一个整数，占一行，表示收上来的门票中共有多少张票被伪造过。输入样例： 5 5 3 3 1 2 4 6 10 6 1 3 6 6 4 2 3 1 2 0 0 输出样例： 1 4
参考代码：
//计算有几个号码被复制过 #include
2.看和说
问题描述：
看和说的顺序定义如下：任何一个字符串都是以数字开头，每个随后的元素都是被前一个元素重新定义。例如，字符串“122344111”可以被描述为“1个1，两个2，1个3，2个4和3个1”。因此，122344111以序列的形式表示出来就是1122132431。同理，101就表示1111111111。输入：
输入包括测试数据的组数，然后依次为相应的测试数据，每个数据占一行，不会超过1000位。输出： 对于每个测试数据，输出对应的字符串。
输入样例： 3 122344111 1111111111 12345 输出样例： 1122132431 101 1112131415 参考代码：
#include
num=1;
gets(s);
len=strlen(s);
for(i=0;i { if(s[i]!=s[i+1]) { printf(“%d%c”,num,s[i]); num=1; } else num++; } printf(“n”);} return 0;} 3．二进制转化为十六进制 问题描述： 输入一个2进制的数，要求输出该2进制数的16进制表示。在16进制的表示中，A-F表示10-15 输入： 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000。输出： n行，每行输出对应一个输入。输入样例： 100000 111 输出样例： 7 参考代码1： #include inti,n,dec,len; char bin[10001]; scanf(“%d”,&n); while(n--) { scanf(“%s”,bin); len=strlen(bin);//求二进制数的长度 dec=4-len%4; if(len%4)//处理头几位，后移dec位，使得变成4的整数倍，前面补0 { for(i=len;i>=0;i--) bin[i+dec]=bin[i]; for(i=0;i bin[i]='0'; len+=dec; } for(i=0;i printf(“%X”,(bin[i+3]-'0')+(bin[i+2]-'0')*2+(bin[i+1]-'0')*4+(bin[i]-'0')*8); printf(“n”); } return 0;} //参考代码2： #include int main(){ int i, j, t, tp, p;charstr[maxn], str_rev[maxn];char res[maxn/4], tmp[6], tmp_rev[6];while(scanf(“%d”, &t)!=EOF){ while(t--){ p = 0;scanf(“%s”, &str);intlen = strlen(str);for(i = lenii;strncpy(tmp, str_rev + i, k);for(j = kj-1] = tmp[j];sscanf(tmp_rev, “%d”, &tp);//printf(“k = %d tp = %d tmp = %s tmp_rev = %sn”, k, tp, tmp, tmp_rev);switch(tp){ case 0: res[p++] = '0';break;case 1: res[p++] = '1';break;case 10: res[p++] = '2';break;case 11: res[p++] = '3';break;case 100: res[p++] = '4';break;case 101: res[p++] = '5';break;case 110: res[p++] = '6';break;case 111: res[p++] = '7';break;case 1000: res[p++] = '8';break;case 1001: res[p++] = '9';break;case 1010: res[p++] = 'A';break;case 1011: res[p++] = 'B';break;case 1100: res[p++] = 'C';break;case 1101: res[p++] = 'D';break;case 1110: res[p++] = 'E';break;case 1111: res[p++] = 'F';break;default: break;} i += 4; } for(i = p-1;i >= 0;i--)printf(“%c”, res[i]);printf(“n”);} } return 0;} 算法分块总结 为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可能涉及的算法思路。算法设计中，时刻都要牢记要减少冗余，要以简洁高效为追求目标。另外当遇到陌生的问题时，要想方设法进行模型简化，转化，转化成我们熟悉的东西。 图论模型的应用 分层图思想的应用： 用此思想可以建立起更简洁、严谨的数学模型，进而很容易得到有效算法。重要的是，新建立的图有一些很好的性质： 由于层是由复制得到的，所以所有层都非常相似，以至于我们只要在逻辑上分出层的概念即可，根本不用在程序中进行新层的存储，甚至几乎不需要花时间去处理。由于层之间的相似性，很多计算结果都是相同的。所以我们只需对这些计算进行一次，把结果存起来，而不需要反复计算。如此看来，虽然看起来图变大了，但实际上问题的规模并没有变大。层之间是拓扑有序的。这也就意味着在层之间可以很容易实现递推等处理，为发现有效算法打下了良好的基础。 这些特点说明这个分层图思想还是很有潜力的，尤其是各层有很多公共计算结果这一点，有可能大大消除冗余计算，进而降低算法时间复杂度。二分图最大及完备匹配的应用： ZOJ place the robots: 二分图最优匹配的应用： 最大网络流算法的应用：典型应用就求图的最小割。最小费用最大流的应用： 容量有上下界的最大流的应用： 欧拉路以及欧拉回路的应用：主要利用求欧拉路的套圈算法。最小生成树： 求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。最小K度限制生成树： 抽象成数学模型就是： 设G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出 现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中 dT(v0)≥m。也就是说，当k 首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。 假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞|(v0,v’)∈E(T)。 状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。1 先求出最小m度限制生成树； 2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。 加边和去边过程，利用动态规划优化特别值得注意。 次小生成树： 加边和去边很值得注意。 每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。具体做法： 首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。 最短路径的应用： Dijkstra 算法应用： Folyed 算法应用： Bellman-Ford 算法的应用： 差分约束系统的应用： 搜索算法 搜索对象和搜索顺序的选取最为重要。一些麻烦题，要注意利用数据有序化，要找一个较优的搜索出发点，凡是能用高效算法的地方尽量争取用高效算法。基本的递归回溯深搜，记忆化搜索，注意剪枝： 广搜（BFS）的应用： 枚举思想的应用： ZOJ 1252 island of logic A*算法的应用： IDA*算法的应用，以及跳跃式搜索探索： 限深搜索，限次： 迭代加深搜索： 部分搜索+高效算法（比如二分匹配，动态规划）： ZOJ milk bottle data: 剪枝优化探索： 可行性剪枝，最优性剪枝，调整搜索顺序是常用的优化手段。 动态规划 动态规划最重要的就是状态的选取，以及状态转移方程，另外还要考虑高效的预处理（以便更好更快的实现状态转移）。最常用的思想就是用枚举最后一次操作。 状态压缩DP，又叫带集合的动态规划：题目特点是有一维的维数特别小。类似TSP问题的DP： 状态划分比较困难的题目： 树形DP： 四边形不等式的应用探索：四边形不等式通常应用是把O(n^3)复杂度O(n^2) 高档数据结构的应用 并查集的应用： 巧用并查集中的路径压缩思想： 堆的利用： 线段树的应用： 总结用线段树解题的方法 根据题目要求将一个区间建成线段树，一般的题目都需要对坐标离散。建树时，不要拘泥于线段树这个名字而只将线段建树，只要是表示区间，而且区间是由单位元素(可以是一个点、线段、或数组中一个值)组成的，都可以建线段树；不要拘泥于一维，根据题目要求可以建立面积树、体积树等等 树的每个节点根据题目所需，设置变量记录要求的值 用树形结构来维护这些变量：如果是求总数，则是左右儿子总数之和加上本节点的总数，如果要求最值，则是左右儿子的最大值再联系本区间。利用每次插入、删除时，都只对O(logL)个节点修改这个特点，在O(logL)的时间内维护修改后相关节点的变量。 在非规则删除操作和大规模修改数据操作中，要灵活的运用子树的收缩与叶子节点的释放，避免重复操作。 Trie的应用：； Trie图的应用探索： 后缀数组的应用研究： 在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。 树状数组的应用探索：； 计算几何 掌握基本算法的实现。凸包的应用：； 半平面交算法的应用：； 几何+模拟类题目：几何设计好算法，模拟控制好精度。扫描法：； 转化法：ZOJ 1606 将求所围的格子数，巧妙的转化为求多边形的面积。离散法思想的应用：； 经典算法：找平面上的最近点对。 贪心 矩形切割 二分思想应用 活用经典算法 利用归并排序算法思想求数列的逆序对数： 利用快速排序算法思想，查询N个数中的第K小数： 博弈问题 博弈类题目通常用三类解法：第一类推结论； 第二类递推，找N位置，P位置； 第三类SG函数的应用。第四类极大极小法，甚至配合上αβ剪枝。最难掌握的就是第四类极大极小法。 第一类：推结论。典型题目： 第二类：递推。典型题目： 比如有向无环图类型的博弈。在一个有向图中，我们把选手I有必胜策略的初始位置称为N位置(Next player winning)，其余的位置被称为P位置(Previous player winning)。很显然，P位置和N位置应该具有如下性质： 1． 所有的结束位置都是P位置。 2． 对于每一个N位置，至少存在一种移动可以将棋子移动到一个P位置。3． 对于每一个P位置，它的每一种移动都会将棋子移到一个N位置。 这样，获胜的策略就是每次都把棋子移动到一个P位置，因为在一个P位置，你的对手只能将棋子移动到一个N位置，然后你总有一种方法再把棋子移动到一个P位置。一直这样移动，最后你一定会将棋子移动到一个结束位置（结束位置是P位置），这时你的对手将无法在移动棋子，你便赢得了胜利。 与此同时，得到了这些性质，我们便很容易通过倒退的方法求出哪些位置是P位置，哪些位置是N位置，具体的算法为： 1． 将所有的结束位置标为P位置。 2． 将所有能一步到达P位置的点标为N位置。 3． 找出所有只能到达N位置的点，将它们标为P位置。 4． 如果在第三步中没有找到新的被标为P位置的点，则算法结束，否则转到步骤2。这样我们便确定了所有位置，对于题目给出的任一初始位置，我们都能够很快确定出是选手I获胜还是选手II获胜了。第三类：SG函数的应用。 关于SG函数的基本知识：对于一个有向图(X, F)来说，SG函数g是一个在X上的函数，并且它返回一个非负整数值，具体定义为 g(x)min{n0,ng(y)对于所有yF(x)} 1． 对于所有的结束位置x，g(x)= 0。 2． 对于每一个g(x)≠ 0的位置x，在它可以一步到达的位置中至少存在一个位置y使得g(y)= 0。 3．对于每一个g(x)＝ 0的位置x，所有可以由它一步到达的位置y都有g(y)≠ 0。 定理 如果g(xi)是第i个有向图的SG函数值，i = 1,…,n，那么在由这n个有向图组成的状态的SG函数值g(x1,…xn)= g(x1)xor g(x2)xor … xor g(xn) 第四类：极大极小法。 典型题目：ZOJ 1155：Triangle War ZOJ 1993：A Number Game 矩阵妙用 矩阵最基本的妙用就是利用快速乘法O（logn）来求解递推关系（最基本的就是求Fibonacci数列的某项）和各种图形变换，以及利用高斯消元法变成阶梯矩阵。典型题目： 数学模型举例 向量思想的应用： UVA 10089：注意降维和向量的规范化 ； 利用复数思想进行向量旋转。 UVA 10253： 递推 数代集合 数代集合的思想： ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion 中有一题：Intuitionistic Logic 用枚举+数代集合思想优化，注意到题中有一句话：“You may assume that the number H = |H| of elements of Hdoesn't exceed 100”，这句话告诉我们H的元素个数不会超过100，因此可以考虑用一个数代替一个集合，首先把所有的运算结果都用预处理算出来，到计算的时候只要用O(1)的复杂度就可以完成一次运算。 组合数学 Polya定理则是解决同构染色计数问题的有力工具。 补集转化思想 ZOJ 单色三角形： 字符串相关 扩展的KMP算法应用：；最长回文串； 最长公共子串； 最长公共前缀； 填充问题 高精度运算 三维空间问题专题 无论什么问题，一旦扩展到三难空间，就变得很有难度了。三维空间的问题，很考代码实现能力。 其它问题的心得 解决一些判断同构问题的方法：同构的关键在于一一对应，而如果枚举一一对应的关系，时间复杂度相当的高，利用最小表示，就能把一个事物的本质表示出来。求最小表示时，我们一定要仔细分析，将一切能区分两个元素的条件都在最小表示中体现，而且又不能主观的加上其他条件。得到最小表示后，我们往往还要寻求适当的、高效的匹配算法（例如KMP字符匹配之类的），来比较最小表示是否相同，这里常常要将我们熟悉的高效算法进行推广第五篇：算法总结
点击咨询 