凌动魅力

Tag: 算法

倒数第226天

之前学得好好的,直到今天在《C语言程序设计精髓》里刷题的时候才注意到C语言里有这么多细节……

初步接触深度优先搜索算法,还在琢磨。看《啊哈!算法》时对书中给的实例不太满意,效率不高,但考虑到是教初学者用的就释然了,写工业级的算法俺们也看不懂~

积累词汇1982个。

倒数第241天

高数与《啊哈!算法》交替着来,后者是本很有趣的算法书,特别是插画,萌爆了,关键是讲得非常朴实明了,不生涩。

完成词汇1448个。

考研日记D17 折衷

没有一种算法能够面面俱到,计算学科中有个很重要的概念叫折衷:不同设计策略下的同种算法,求解质量和收敛速度也会有巨大差异,还有可能求不出最优解,只能得到近似解,因此需要在各个算法中做出权衡,质量优先还是性能优先,即折衷,这是算法技术性和艺术性的体现。另外,随机和概率也需考虑进来。

当然,以上知识算法理论的一些知识,真正理解算法还需要应用到生活中,才叫学会了算法,不然都是纸上谈兵。

看了下在上课程的测验截止日期,《大学物理-相对论》是12月2号,《工科数学分析》是12号,《计算思维导论》是24号,这个周末都得玩儿了- -|||

今天学的内容不多,花了些时间反思自己之前的感情。尽管俺已经不求被谅解,但依然会通过暗地里地帮助,获取慰藉。

那些曾经走过的日子,就让它静静消逝掉吧。

考研日记D16

今天一过考研日记就写了半个月了,这半个月有什么收获呢?问这个问题为时过早。这半个月除了坚定自己考研的决心以外,进行的更多的是生活层面上的思考。

今天在《计算思维导论》中学到了遗传算法,神奇之处在于,学习的对象是社会、自然现象中的生物遗传与进化现象,剥开本质后,生物的一代一代地交换染色体,在自然选择中淘汰掉无法生存的一批,诞生出新的群落,如此往复,便有了优秀的后代。

抽象成算法之后的框架如下:

begin /* 遗传算法 */

t ← 0; /* 进化的种群代数 */

生成初始种群P(t);

计算初始种群P(t)中每个个体的适应值;

while(不满足终止条件) do

/* 利用下述操作生成新个体,并选择更优个体组成新种群 */

(1)通过复制、交叉或变异操作重组种群P(t)中

的个体,产生新个体,形成候选种群C(t);

/*注意此处C(t)并未包含P(t)中的个体 */

(2)计算C(t)中每个个体的适应值;

(3)根据适应值从C(t)和P(t)中选择更优的个体

组成新种群P(t+1);

(4) t ← t+1;

end while

选择P(t)中最优个体为所求的解;

end begin

类似的仿生学算法还有 人工蜂群算法蚁群算法粒子群算法免疫算法等。

考研日记D15

哈工大《计算机思维导论》的深度比之前国防科大的《大学计算机基础》难度高了不少,但还好每次都有练习题集,因此平时得分反而要高一些。

大体上介绍了算法,刚上了 数据表查找、内排序、外排序(多路归并排序,资源约束下的解决办法)之后就开始学习 PageRank网页排序算法—— 网页权值(网页重要度的迭代计算)。PageRank几乎成了学算法的必学课程,就是计算正向链接和反向链接(反向链接数更重要;单一页面也需要进行多次计算;线性代数课有关于PageRank的简化计算方法,即“特征方程”),一学就明白,但难度高的是大规模计算数十亿数百亿网页的权值。

当然,虽然课上讲了这些算法,但离真正的应用还差得远。现在只是以算法为例,理解由 问题-问题环境-算法设计 的过程。

上面扯了些上课的内容,再谈点其他的。最近 罗塞塔计划 很火,刚还看见新闻《“菲莱”号在彗星上发现有机分子》,人类已经进入太空探索的小爆发期,中国、美国、欧洲、印度的探空计划不断曝光。

相对于天文尺度,动则光年、亿年,人类的生命太短暂,终其一生也看不到3次同一颗彗星。儿时以为认识世界靠的是眼看耳听,看了诸多科普、哲学书之后才意识到,真正拿来认识世界的工具,是数学和物理。

考研日记D12 算法

今儿总算步入算法的相关课程了,以前对算法是“只闻其声”,只知道是计算机的灵魂,广泛地说任何从输入到输出中间的过程都可以叫做算法。门外汉不太清楚算法与数学、数据结构的关系,那么可以直接看下图

图中拿TSP问题(寻找节点间的最短路径)举例,一个完整的算法求解需要

  1. 把问题抽象成计算机可理解的数学问题
  2. 选择适用的算法,这里要考虑算法的时间复杂度
  3. 算法的数据结构设计(存储、指针、数据…)
  4. 编程,将想法具现为程序(设计语言的选择也这这一步中)
  5. 验证程序的正确性,有的算法过于复杂只能验证其正确性而不能得出结果,比如TSP的遍历算法
  6. 考虑算法复杂性,优化

上完这一课看到56道题头略大~

Copyright © 2017 凌动魅力

蜀ICP备15003767号-1 Up ↑