---------!!!!!!!!!!!!!!!!-----------------
检测到您正在使用IE9或更低版本浏览器访问本站,为了您的阅读体验,本站推荐您使用Chrome浏览器 或者Firefox浏览器 对本站进行访问
扫一扫,分享到微信

哈佛公开课CS50  2015学习笔记

前言

维基百科对CS50的介绍:

CS50 (Computer Science 50) is an on-campus and online introductory course on computer science from Harvard and, as of 2015, Yale Universities. The course material is available for free with a range of certificates available for a fee. The on-campus version is Harvard’s largest class with 800 students, 102 staff and up to 2,200 participants in their regular hackathons

这是我个人的学习笔记,多数内容为自己的理解,不保证内容的正确性,如果您在阅读的过程中,发现了其中的一些问题,还请不吝赐教,我也感激不尽。

CS50 week 2

这次课 ,是讲的数组的概念,这个当然也并不陌生,但是这里将电脑(computer)的内存RAM 与之结合在一起来讲,这就很有意思了。

内存的分配,一个字节(byte)也就是八个比特(bit),它是内存中的最小的单位。计算机所谓的二进制运算的最底层,也就是这里了。每一个bit都有0和1的划分,这样,八个bit就组成了一个byte,通过bit的变换组合,就能够形成2^8,256种不同的形式的表示,我们再人为地将这256种表示赋以不同的意义,这也就是ASCII码的由来了。

这也让我想起来,之前看过的一本书,《code》,这本书的开头部分,就是讲的一个两个小男孩之间如何进行无声的交流,从此而引出了电报,又从电报引向了计算机的发明,其实还是一脉相承的。

数组很重要,通过使用数组,能够将很复杂的数组进行很简单地表示,如果我们想要10000个数字,我们不必每一个都逐一赋值,而只需要一个数组[10000] 即可啦。

在内存中的存储之中,空格当然也是要有存储空间的,就像是ASCII码里面也是有空格(space)的对应位置的,这里也解释了原因,如果说字符串A为”abc”,字符串B为”defg”,他们两个字符串在内存之中是紧紧相邻的话,那么如果没有空格的话,也就会造成将这两个字符串看成一个字符串。

week 3

第三周讲的是算法,开头讲各种排序。

排序当然很重要,有多重要呢?

冒泡排序

冒泡排序算法,这个当初在某公司面试的时候,面试官有问过我,但是当然还是记忆不清。这里看CS50的课程,还是比较好理解的,所谓的冒牌,就是交换排序,在上面的课程截图可以看出来,每一个志愿者(volunteer)手里都拿着一张贴着一个数字的纸,老师正在演示的就是冒牌的过程。

冒泡算法(bubble sort)的核心是交换顺序,如果是要求后面的数比前面的数大的话,那么从当前的第一个数开始判断,如果该数比他后面那个数要大的话,交换顺序,这样进行过一轮之后,还是不行,要进行N-1轮才能够最终确定。

我自己使用JS写的冒泡算法如下所示:

function bubblesort(arr) {



 for(var j=0;j<arr.length;j++)

   {

     bubble(arr);



   }

  return arr;

}



 function bubble(arr){

  for (var i = 0; i < arr.length; i++) {

    if (arr[i] > arr[i + 1])

      {

      var a = arr[i + 1];

      arr[i + 1] = arr[i];

      arr[i] = a;

      }

  }

  return arr;

  }





bubblesort([2, 3, 7,5, 4,3,6,8,4,34,56,34,23,6]);

我在之前的JS入门(12)插空排序问题 这一篇里也提到过,在javascript中有对应的排序的方法,可以直接调用。

function bubblesort(arr) {

  arr.sort(function(a,b)

          {



    return a-b;

  }



          );

  return arr;

  }





bubblesort([2, 3, 7,54,34,56,34,23,6]);

时间复杂度

这里也就接着引入了时间复杂度的概念:

如上图所示,所谓的时间复杂度,在这里,老师表明了,就是说你假设是最复杂的情况之下,比如对8个数字排序,那么最好的情况肯定是正序排好的,那么对应的,最坏的情况一定是完全相反的逆序排列了。

如果是上面提到的最坏的情况的话,那么进行的步骤数目就是

n^2/2-n/2

数学上的知识告诉我们,当N趋近于无穷的时候,上面这个式子趋近于n的平方。因此:

另外我们也能够看到一些其他的时间复杂度,比如O(n),也就是进行N次步骤了,这里举例是,如果从1-10十个数字中找出来5这个数字,那么随机地取数字,直到找到这个数字为止,那么最多进行十步了。而O(1)也举出了相应的实例,当要求printf(“c”),这显然就是一个O(1)了。(实例用到的是C语言)

插入排序

这里插入排序的思路是找出每一个value对应的index。将每一个value放入到对应的index之中。

按照维基百科的说法则是:

它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

function insertsort(arr) {



  for( var j=0;j<arr.length;j++){



    for(var i=j+1;i<arr.length;i++)

      {



        if(arr[i]<arr[j])

           {

           arr[j]=arr[i]; 



          }





      }





  }

  return arr;



  }



insertsort([2, 734,56,34]); 

这种情况是错误的,理由是没有进行交换顺序。正确的算法应该是:

function insertsort(arr) {



  for( var j=0;j<arr.length;j++){



    for(var i=j+1;i<arr.length;i++)

      {



        if(arr[i]<arr[j])

           {

           var middle;  

           middle=arr[i];

           arr[i]=arr[j];

           arr[j]=middle;



          }





      }





  }

  return arr;



  }





bubblesort([2, 734,56,45,87,3,4,6,84,34]); 

插入排序的时间复杂度同样是O(n^2),依然是从最复杂的情况来考量。

week 4

软件并非如它所称的在执行任务

这一讲其实内容比较杂了,一开始以最近的大众汽车召回案为例,介绍软件程序的不可控性,如果一个软件程序,我们不能知道他的源代码,那么我们又怎么能够确定这个软件所执行的就是这个软件声称在做的事情呢?

所谓的大众汽车召回案,在这里老师侧重于讲述软件程序中的作弊。作为欧洲最大的汽车制造商,大众此前承认全球有1100万辆汽车都装有所谓的尾气排放作弊装置。

开源的好处

由前面对大众召回门这个热门事件的探讨,转向了对开源的介绍。一个软件,如果我们能够知道他的底层源代码,那么也就意味着它是已经呈现在阳光之下的,如果你能力足够,我们可以对这个软件一清二楚,那么也就不会出现类似大众事件中汽车尾气作弊这样的事情。在这里,老师注重介绍了UNIX和LINIX,在开源方面这的确是始祖级的。

递归

接着却又讲了另外一个截然不同的主题,递归。并且使用了一个例程来做演示,递归对我来讲倒是并不陌生。

在这里,使用的递归函数的作用是叠加。原函数是使用的C语言进行编写的。在这里我使用Javascript另外写了一个同样能够达到递归叠加之目的:

function sigma(a) {

      if(a<=0){

        return 0;



      }

      else {

        return a+sigma(a-1);



      }





    }

    sigma(6)  ;  //result:21

对上面的叠加递归稍作改动,就可以改变成递归阶乘

function sigma(a) {

      if(a<=1){

        return 1;



      }

      else {

        return a*sigma(a-1);



      }





    }

    sigma(5)  ;  //result:120

交换

接着就是将交换的算法实现。这在现在的我看来,偶尔还是会有一点懵。但是这老师给出的例子是非常好理解的。拿出两个杯子,一个杯子里是橙汁,一个杯子里是白水,要求将两个杯子里的饮料调换,这让志愿者有点犯难,接着老师拿出来另外的一个空杯子,一切就迎刃而解了。

先将橙汁倒入到空杯子里,然后把白水倒入到原来盛着橙汁的杯子里,最后把橙汁导入到原来盛着白水的杯子。

抽象的实物不容易理解,倒是实体的却非常容易理解,类比是一门学问。

这也让我想到了之前做过的一道题:两个不规则的容器,一个能盛3升水,一个能盛5升水,要求倒出4升水来。

这其实也是一个很经典的题目了。具体的步骤应该是:

1、将5升的瓶子装满,倒满3升的瓶子。此时,5升的瓶子里有2升水。

2、将3升的瓶子的水倒掉,将5升瓶子里的2升水倒入3升的瓶子。

3、将5升的瓶子装满水,向3升的瓶子中倒,倒满为止。此时,5升的瓶子中的水就是4升。

抽象的算法可以借由实体事物来方便地理解,实体事物也可以考察对算法的理解。

地址和指针

表面上看上去是同样的字符串mom,但是却因为存放在不同的地址而出现程序错误。这也是我们需要进一步理解的。

在后来的课程中,对这一问题进行了解释。提到了指针的巨大作用(pointer)

不过话说回来,在JS之中其实并没有int* a 这样的语法,在JS之中所谓的指针其实是this。

关于C语言中指针的重要性,也看到知乎上有回答:

C 语言只有值的传递,无法直接传递引用,要想传递引用必须通过指针间接实现。

如果 C 语言没有指针,一切都通过值传递,参数将永远只有输入参数,所有的结构体只要参与运算都具有极高的开销,因为每传递进函数参数一次就必须全体复制一次。

这样的解释,其实也是和老师前面所讲述的不谋而合的。

在上面的图例中,x是作为地址的,y也是作为地址的,当这两个地址同时指向13时,就达到了传递值的作用。这个时候我们再回过头来看C语言中的scanf函数:

scanf函数也是通过在查找到x的地址之后对x地址上的值进行修改的,或者说是copy(复制)过来。在英语中,scan的本身意思就是扫描,因此机器实际上也是处在持续地等待扫描状态,一旦键盘上有key输入,就将键盘的输入值copy到对应的地址上。这里需要说明的是,我们虽然在输入之前尚不知道x的具体值,但是由于已经用int x来定义了他,也就相应对产生了他的地址。

图形的二进制表示

在好莱坞的电影里面,我们经常能够看到这样的场景;

警察包括但不限于FBI.CIA等通过录像锁定了嫌疑人,这个时候嫌疑人的面部还是很模糊的,于是警察下达指令,放大图像、增强图像,嫌疑人的面部就变得越来越清晰,最终通过这种高科技找到了嫌疑人。

但是真实的世界是怎样的呢?每一张数字化的图片都是由像素点组合而成,这些图片放到之后并非可以通过增强而实现清晰化,而是像下图这样:

这就引出了对图片格式的说明:bitmap、jpeg、jpg等图片格式。如果我们还是不能够理解为什么像素点可以组成变化的图片,那么下面这张图能够帮助我们理解:

在上图之中,每一个像素点只能由0和1来组成,因此上图是一张黑白的图片。那么,如果每一个像素点,我们给他更多的内存,也就能够让每一个像素点显示更多种类的颜色了,那么图片就可以是彩色的了。每一张图片的像素点越多,我们就说这张图片的分辨率越高。

这时候就又引出了Color Hex Color Codes的概念。事实上,当我在学习CSS、PHOTOSHOP的时候,也是频繁地在和它打交道。不过这里的原理其实是三原色,也就是R(red 红)、G(green 绿)、B(blue 蓝)。在自然世界中,通过按照不同的比例混合这三种不同的颜色,可以组合成不同的颜色。我们将每一个原色切分成256份,再通过16进制的方式加以组合。

因此,可以很显然的得出来:

#FF0000

上面表达的自然是red(红色)了,因为#FF0000的第一部分是FF,G和B的部分是空的,则表示只混合了R色。

类似的#00FF00就是表达的绿色,#0000FF就是表达的蓝色了。

#FFFFFF表达的是三原色按照相同比例混合,是为白色。

P.S在写作过程中,由于使用的Markdown进行编辑,在输入#FF0000这样的color code时,如果直接输入#FF0000,就会被Markdown误判为一级标题,这时候需要使用转义字符\,类似于其他计算机语言对特殊字符进行转义。

week 5

内存溢出和buffer

wikipedia中对于data buffer的定义:

In computer science, a data buffer (or just buffer) is a region of a physical memory storage used to temporarily store data while it is being moved from one place to another.

Typically, the data is stored in a buffer as it is retrieved from an input device (such as a microphone) or just before it is sent to an output device (such as speakers). However, a buffer may be used when moving data between processes within a computer. This is comparable to buffers in telecommunication. Buffers can be implemented in a fixed memory location in hardware—or by using a virtual data buffer in software, pointing at a location in the physical memory. In all cases, the data stored in a data buffer are stored on a physical storage medium. A majority of buffers are implemented in software, which typically use the faster RAM to store temporary data, due to the much faster access time compared with hard disk drives. Buffers are typically used when there is a difference between the rate at which data is received and the rate at which it can be processed, or in the case that these rates are variable, for example in a printer spooler or in online video streaming.

当我们的buffer有限,而需求较大时,就会造成内存溢出。

内存溢出并不少见,这也让我想起来我自己的电脑程序以及我自己曾经写过的程序。在我的电脑上,最常出现崩溃的软件程序是Firefox,他也经常是在运行之中崩溃,接着是重启。而我将笔记本的操作系统更新到win10之后,由于我的电脑ram不足4GB,也常常出现系统的卡顿和崩溃重启,在这里我也意识到RAM的重要性,以后买笔记本或者以后对笔记本升级RAM也是需要重点考虑的啦。

数据结构

上图图例是在C语言中的结构体,结构体的特点是能够将多个属性划归到一个对象上,因此在我看来其实在面向对象的编程中更好用吧,所以我们也看到了在JSON(javascript object notation)中有这样的表达。

每一种数据结构都对应的有他自己无可替代的优势。接着老师讲到了链表,所以我们也来看看数组和链表的优缺点比较

1)数组在内存中是逐个存放的,也就是说倘若数组的第一个元素在地址A,则数组第二个元素就在地址A+1。

而链表则不是,链表每个节点没有相对固定的位置关系。某个节点在地址A其后的节点不一定是A+1,而在内存的其他空闲区域,呈现一种随机的状态。

2)数组一旦显式的被申明后,其大小就固定了,不能动态进行扩充。而链表则可以,可以动态生成节点并且添加到已有的链表后面。

3)链表灵活,但是空间和时间额外耗费较大;数组大小固定,元素位置固定,但是操作不灵活,且容易浪费空间,但是时间耗费较小,尤其是元素变化不大的时候效率很高。双向链表比单向的更灵活,但是空间耗费也更大

week 6

哈希表

定义

维基百科对哈希表(散列表)的定义:

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名 x {\displaystyle x} x到首字母 F ( x ) {\displaystyle F(x)} F(x)的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则 F ( ) {\displaystyle F()} F(),存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

在这次课上,老师也举了一个类似的例子。

接着讲道了加密技术,但也只是普及性质的,事实上,由于哈希表具有key-value的性质,能够通过一个key来查找相应的value,因此可以利用哈希进行加密解密等。

一种常见的哈希算法SHA1,这也是一种很广泛的加密算法。除此之外,还有MD4,MD5等哈希加密算法等。

MD5之前有过一定的了解,所谓的种子洗白,很重要的一点就是修改它的MD5值,让服务器不能够识别。

TCP/IP

这一讲主要是将TCP/IP

IP

首先介绍了IP的概念,IPv4,IPv6等,这个已经很熟悉了。之后是介绍私有ip,所谓的私有IP是利用路由器而生成的,通过路由器的线路转换,处在同一个路由器之下的这个局域网中的用户所使用的是同一个ip地址。

接着讲述了用户请求从发出到接受数据的整个过程。用户端发出请求到服务器端,服务器接收数据根据要求发出相应的数据返回到客户端。这里也解释了物理实在的构成—光纤。如果想要从中国上服务器设置在美国的网站,换句话说客户机在中国,服务器在美国,这时候就需要有海底电缆(undersea cable)这样的物理介质了。

这里也介绍了最早的跨越大西洋的海底电缆建设于19世纪50年代,是为了从加拿大的纽芬兰发送电报到爱尔兰的。

我们需要有IP地址,但是IP地址往往很难以记忆,这个时候就需要有DNS,也就是域名的管理系统,通过它,我们就可以将每一个IP地址指向到对应的域名(需要注意的是,一个域名可以有多个IP地址指向),有了DNS,有了域名,以后我们只需要在浏览器的地址栏输入相应的域名即可得到相应的website。而等到出现了搜索引擎之后,我们甚至不需要记忆相应的URL,只需要记住唯一一个域名www.google.com也是可以完成几乎任意网站的浏览的。(所谓的暗网或者深网不在讨论范围之内)

TCP

IP是互联网的传输协议(Internet Protocol),而TCP则是传输协议,是客户端和服务端两方面之前传输的协议。数据以包(packet)的形式来发送,在这一讲中,老师使用了一个例子,就是将一张打印了某人头像的纸撕成四部分,放入信封之中,在信封上写上发件人和收件人。这里的每一部分撕成的纸都是一个包(packet),而信封上的发件人就是客户,收件人就是服务端。TCP协议是需要做出反馈的,这封信是不是已经发送出去,信里面的内容是否完好无损等,这些信息还要传达回客户端。当出现问题时2,客户端需要根据这些反馈信息采取相应的措施。

所以,我们也能够看到状态码

我们一般常用到的是404,403,500等,这些是需要记忆的。在使用TCP/IP协议的过程中,有时候,并不只是通过HTTP来传输的,因此还要有

TCP协议中的一些端口,这些端口有各自的作用。例如port:21的作用是文件传输,port:25是邮件的发送,上面所列的也是常见的一些TCP协议端口。

接着继续讲TCP协议,在TCP协议之中,还要有很多的指令。比如:

像上面就是客户端在发送请求到服务端。

相应的,服务端在接受到客户端的请求之后,也要做出相应的响应。服务端会将文件以html文件的方式发送回客户端。

这时候就会产生一些问题,前面已经提到过当TCP的状态码是200的时候,是说明能够正常的接受和发送数据。但是还有一些情况是不能相应的,比如在地址栏输入一个错误的URL,那就会产生一个404的错误,我们也方便根据这样的错误来对问题进行排查。

信息安全

这时候就又牵扯到了信息安全的问题,如果我们使用HTTP方式的话,如果我们和别人处在同一个私有网络之下(比如接入了同一个wifi网络),那么事实上,我们的信息实际上是不安全的,处在同一个网络之下的人可以很容易地窃取(hack)你所上网络的账号密码等。

这个时候,VPN就派上了用场了,所谓的VPN是虚拟私有网络,他能够作为一个数据的中转站,这个时候即便是处在同一个网络之内,其他人看到的也只是你不断地在向某个IP地址请求数据,和这个IP地址返回数据,而这个IP地址这个过程中做了什么他是无从知道的。VPN有点像黑箱,通过他来保护我们的信息安全。

在这一讲里面,也介绍了GFW,讲到了我们如果跨越防火墙。我们只需要连接一个VPN,通过这个VPN来得到数据和返回数据,只要保证这个VPN所在的IP没有被墙,那么就能够确保跨越,只是说,通过中间加上这一个过程,必然也会延长从请求数据到得到数据的这一个过程,这也是我们要付出的代价。

week 7

第七周开始讲的是HTML、CSS等的常识知识,本身都比较浅显,只是作为这个课程的系统中的组成部分来看,要说细节,倒也没有太多,之前我也较系统地学习了这方面的知识,因此不再赘述。

第七周的第二次课讲的是基础的PHP,老师在这里讲了CS50对待PHP的态度,即不要求在CS50这个课程中学会使用PHP,但要将他在哪里应用,为什么要应用,PHP对于CS这个课程体系的重要性有所了解。

PHP是一门后端开发语言,我们在填写表单,处理数据的时候会用到它。

在这里老师也比较了PHP和C的区别,除了数组(array)的可扩展性,$操作符、非强制类型等很明显的区别之外,PHP作为一种高级语言,它所承受的代价就是运行速度相对于C来说一定会减慢,而C是可以直接编译成机器码的,就像是汇编语言那样(汇编是比C还要低级的计算机语言)。而PHP、JAVA、JAVASCRIPT等高级语言则是interpret language(解释语言),需要进行转换,才能够被机器识别。

我对PHP并不熟悉,在这里老师在命令行中应用的指令是:

PHP hello.php

我之前学习JAVA,JAVA程序的编译也是类似,在命令行中要有相应的指令,除此之外,还需要预先设置好JAVA的环境变量,无论是windows系统还是linux系统、macos都是如此。

在这堂课上,主要的任务是利用PHP语言实现自动化地给一个CSV文件中的所有同学发送短信。

整个的思路是这样的:

  • 了解CSV文件,所谓的CSV文件(Comma-Separated Values),如果用记事本打开的话,就可以很清楚地看到CSV文件中每一行(ROW)都是以逗号作为分隔符。当使用Microsoft excel来打开的时候,就是每一个逗号分隔出来的value占据一个单元格。
  • 发送信息使用了PHP中对应的mail library。这个有点像我之前做过的python发送邮件。
  • PHP使用fopen,fget读取到每一个电话号码和他的运营商,然后就是自动化地循环发送邮件的操作了。在这里使用的是gmail,其实我们还是可以看到gmail在这方面做得很好,像QQ、sina等国内邮箱都需要所谓的验证,而gmail只需要提供用户名和密码即可实现PHP发送邮件的操作。

上图就是美国version公司的电话号码的电子邮箱形式了,通过Gmail可以手动发送邮件,也可以使用PHP通过stmp填入Gmail用户名及密码程序化完成。

  • 我们知道正常情况下是用邮箱来发送邮件的,但是这里的要求是发送邮件即可发送到指定的电话号码短信息。在美国,这有移动运营商的作用,每个运营商都有一个邮箱,对应的用户名是他们的号码,这样就可以实现发送了但是好像在中国大陆,无论是中国联通、移动还是电信都没有提供这样的接收短信的方式。这又牵扯到另一个问题,在中国如何群发短信,因为服务端经常会遇到发送验证码的情况,这个时候肯定是不能手动操作了。

实际上美国那边利用的是短信网关,而在中国这边,三大运营商也是提供这个短信网关的,只是说要收取一定费用,他的使用也往往是集团化的商用,通过调用API来实现。,当然这也可以理解,如果这样的技术公开,也很容易造成垃圾短信的泛滥。

week 8

MVC

所谓的MVC是指由M(model)、V(view)、C(controller)构成的一个系统。在MVC系统之中,V既是网站的前端界面,M既是该网站的数据库等后端支持、C既是作为控制器,客户端下达请求到服务端的控制器,控制器根据请求内容选择view,将这些内容发送回客户端。

前面所了解的内容是为前端,因此接下来也要对后端的内容做一些认识。

SQL

我们知道PHP语言的代码是这样的呈现方式:

<?php



?>

在处理网站表单时,PHP语言要和SQL语言发挥更大的作用。PHP可以用来分析数据,SQL可以用来存储数据。

所谓的SQL,也就是structure query language,中文是结构化数组语言。他和微软的excel,谷歌的spreadsheet,苹果的number在性质上作用是相同的,都是起到存储数据的目的。

这里提到了一个细节,在早期的Excel中,每一个表单最多只能够到达65535行,这个限制也使得当有大规模的数据存储时,受到了严格的限制。我们试想一下淘宝的商品数据库,即便是一个门类上,也不止65535种商品。而在这一方面,SQL做得就非常好了。

接着结合管理软件phpMyadmin介绍SQL,做一个简单的归纳就是:

  • 在SQL中,每一个值都有他的一个类型,我们要结合使用场景,给他一个权衡,达到最优化。这里举例,如果要建一个学生数据库,那么对于学生的id就可以设置为int类型,他的最高位数可以设置为10位。
  • 对于每一个表格,我们都要求有唯一的一个值,来保证它是独一无二的。在上面的例子中,显然使用ID是一个很好的选择。而如果我们再拓宽想一下,也会发现,在QQ的系统中,昵称并不是唯一的,我的QQ昵称是「海阔天空」,可能全国有几千几万个昵称是「海阔天空」的人,在QQ系统数据库中,是将QQ号的数字编码作为独一无二的身份验证凭据的。
  • PHP与SQL的关系。在处理表单方面,PHP负责将用户填写的表单填入到SQL,数据库之中。PHP也会对数据是否在数据库之中进行检查,数据库中数据的增添删减检查都可以通过使用PHP来完成。

week 9

第九周讲的是JS的基本语法和使用案例,由于此前学的很多了,也就没有仔细看。在第九周的最后,一个来自哈佛大学考古系的教授也上台来,讲述了技术与文化之间的密切联系,这一点很有趣,所以我这次也就将这部分的感谢贴在这里。

该教授讲述了古埃及金字塔的一些故事,讲述了现代考古学之父George Reisner (哈佛大学教授)为了探索古埃及金字塔所做的努力。到了当代,这位教授希望利用技术来实现3D的金字塔重构,让古代的建筑通过技术重新展现在人们眼前。

教授也提供了一个网址,能够在线地查看埃及金字塔的考古发现

http://giza3d.3ds.com/#discover

将技术与文化艺术结合在一起,也并不是新鲜事了。很早的时候,我就知道有google art project

我写这个笔记的时候是16年7月4日,也就是美国建国日,这一天发生了著名的波士顿倾茶事件。所以也看到了google art里面有相应的专题来介绍美国的近现代史。

比如有下面的一幅画:

值得一提的是,在google art上,处于版权的考虑,在该网站上的艺术作品及其所有文字介绍都是不能复制粘贴的,我上面的图片也只是截屏出来的。从这也能够看出来,前端技术在不同场景中的使用区别。

关于如何实现「文字不可复制,不可选择」,可以看

http://www.cnblogs.com/dudu/archive/2012/04/09/css_unselectable_uncopyable.html

或者是:

http://stackoverflow.com/questions/826782/css-rule-to-disable-text-selection-highlighting

上面两个对该实现的介绍,也都是使用的CSS来实现的。

不过,道高一尺,魔高一丈。能够限制复制粘贴,也就能够破解。比如,使用Firefox 的油猴脚本网页限制解除 就可以实现解除限制。我自己之前还曾经为了下载flickr上的一张图片而实现一个脚本来实现破解。

而这些扩展,其实也都是JS程序代码罢了,这也证明着JS的锋利。

除了google art项目之外,Google的街景服务也是一个将技术应用于生活的典型案例,就如该教授所说,有了这样的技术,我们甚至不用买飞机票而特意去某个地点旅行了。我自己就曾经使用google earth配合街景服务到美国洛杉矶的斯台普斯中心游览了一番,哈哈哈。

week 10

网络安全

本周,开头讲的是网络安全问题。

关于网络安全,首先需要注意的无疑就是各个网络服务的密码(password)了,一旦密码被破解(crack),那么相应地就会造成一定的损失。我自己的亲身经历是新浪微博账号被别人登录并且发送多条垃圾信息,原因是我自己在公共场所登录新浪微博而没有及时地退出账号,并不是密码被别人破解了,所以我后来更换了微博的密码。

这里面牵扯到cookies的问题。

下面是Chrome 帮助页面对于cookies的介绍:

What cookies are

Cookies are files created by websites you’ve visited. Cookies store browsing information, like your site preferences or profile information. There are two types of cookies:

First-party cookies are set by the site shown in the address bar.

Third-party cookies come from other sites that have things like ads or images embedded on the page you’re visiting.

Not all cookies are bad. For example, cookies help the website remember your preferred settings so it can reload them when you revisit the site next week. Cookies can also help a website remember your location, so it can provide you with locally relevant content, like weather.

网站是可以储存一些信息的,它并不总是怀的,有了cookies,我们就不必每次都需要输入账号密码了。我们也可以利用Chrome dev 来查看某个网站储存的cookies信息,比如:

上图是我个人知乎网站上的cookies信息部分截图。当然,前面已经提到过,有了cookies之后,我们就不必在下次访问某个网站的时候再次输入账号密码了,因此cookies中也一定储存了账号密码的信息,不过这些信息是加密的。

使用 Chrome 浏览器添加扩展程序cookies ,也可以使用扩展来方便地查看每一个网站的cookies信息,仍然以知乎为例:

后来我做了一个小实验,将这个Name为login的cookie删除掉,重启浏览器,结果chrome显示个人资料将丢失,不能执行,打开知乎之后仍然能够自动登录。

如何破解密码:

https://www.youtube.com/watch?v=SgEC3xzSdFA

这是说的改变你的个人电脑的密码,这在我看来很「标题党」,我个人电脑的密码我无须破解吧。而别人的个人电脑从一开始我可能就打不开,如果打开了我也没有必要再破解了。

安全措施

为了让我们的网络账户更加安全,也就引入了两步验证机制。

除此之外,当我们的网络账户数量庞杂的时候,切忌不要使用一个密码来针对所有的账户,否则一点击破,所有的账户也都会失陷。这里推荐的方法是使用像lastpass或者是1password这样的应用来进行管理,我们同样只需要记住一个密码即可。

在前面的学习中,也已经了解到,由于http协议是公开的,传输过程之中,运营商很有可能会添加一些其他信息,比如广告,也或者得到一些信息,比如Ip,访问的站点等,这也是不安全的,这时候就需要https了。

AI(人工智能)

在这一讲中,提到的人工智能侧重于Google Now的原理类。

文字类AI

![](https://lh3.googleusercontent.com/4rHdsdyr_OqE7pUMd1mpRcn1CpEnwDz9OcqCdQxn1wW7qNuUCBouwknmja7lRxraqAROgVi3-kLblDScGGU_K_GufurCJbG4_-TmCXPm8w2FiImb1YpUZnJtiyvsY88BokGBnfe2UsCWBdBEqcMjUooUArAXLuZXW23KiMT07SZ2jvCkPNhzjD9kDfDHc3kvcuhStw6FZiW-aWEZPdfX24dAiBLC7q19uvWw_AofkO6IymQfx_hcXZUMObg9YK9vtafAR3n0Dg79x3YhsQY8Rf1OYF6Qd1u3tpQ2sZFgNE2OF8rruznayoSiX9OXUxhk8dSolGRVs5AKrhA-机对话AI,它的基本原理是模块匹配。

下图是简单的模块匹配的应用:

这里很重要的一点语法,也就是人称与时态等等转化。比如人是A,机器是B

当人的输入语句中有I want 时,机器回答的匹配词汇是 WHY DO YOU WANT。这样的匹配不至于说错话,但是也都是废话,无关痛痒,因此这一阶段的AI谈不上有多高级。

文字AI部分程序

语音类AI

除了文字类的AI之外,明显有着更广泛应用的是语音类AI。我们常见的有Google Now,Siri,Amazon Echo 等。

针对语音类的AI,有三个层次上的研究:

分别是语音模型, 单词模型, 语言模型

这时候,就用到了概率统计

这也让我想到了之前阅读的吴军博士的《数学之美》 ,这本书一个重要的思想,就是介绍了当前的包括推荐系统,语音识别,图像识别等都广泛应用着概率统计,而不是利用的所谓的语法规则等。

在这里,也提到了能够为医疗行业服务的企业级AI,IBM公司的WATSON。这也让我想起来早在去年10月的时候,我本人就曾经翻译过一篇《未来十年,当我们谈起自动化及就业市场,我们在谈什么》 ,这篇文章是讲AI对人类就业市场产生的影响。其中有这样一段:

一些研究人员相信小规模的数据传递同样适用此道,安德罗斯.康奈( Andras Kornai )表示,“IBM当前正将watson电脑系统应用到医疗卫生领域,我期待相同的事情能够在法律领域发生” 。尽管“机器学习”有可能会用于诊断癌症或者其他疾病上,这些技术现在看起来仍然不太可能取代医生。

week 11

这一讲仍然是讲的AI,但是侧重点已经从类Google Now的人机对话,转移到了Google 公司Alpha-Go的基本原理。

航班选择问题

上图给出了从波士顿(Boston)出发前往旧金山(san Fransico)的树状图,通过使用树状的排列搜索,我们就能够找出来波士顿到旧金山的所有可能的航班。这个时候,我们只需要对比所有可能的航班的价格和时间,再做一个权衡(Trade off),就能够找到最优解。

由此,我们也能够看出来,在实际的应用之中,树状结构(Tree)是很有用处的,像二叉树等知识作为算法,将能够提高效率。

对抗问题

从前面的Search Trees引入到对抗搜索之中,仍然是先简单而后复杂的思路。

首先就是讲解了3×3连子棋(Tic-Tac-Toe),人机对抗时的计算机运算过程,这个时候,由于本身棋盘只有3×3的大小,因此计算机完全可以从树的开始到树的最底端来找到所有可能的情况,并根据可能的情况来找出一个最优解。

而查找这个最优解的基本原则是:

极小化极大算法:选出让你的对手处在最坏处境的一步棋

完整的算法步骤是:

  1. 设博弈双方中一方为MAX,另一方为MIN。然后为其中的一方(计算机)找一个最佳走法。
  1. 为了找到当前棋局的最优走法,需要对各个可能的走法所产生的后续棋局进行比较,同时也要考虑对方可能的走法,并对后续棋局赋予一定的权值(或者称之为分数)。也就是说,以当前棋局为根节点生成一棵博弈树,N步后的棋局作为树的叶子节点。同时从树根开始轮流给每层结点赋予Max和Min的称号
  1. 用一个评估函数来分析计算各个后续棋局(即叶子节点)的权值,估算出来的分数为静态估值
  1. 当端节点的估值计算出来后,再推算出父节点的得分。推算的方法是:对于处于MAX层的节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案;对处于MIN层的节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况,这样计算出的父节点的得分为倒推值。

5. 如此反推至根节点下的第一层孩子,如果其中某个孩子能获得较大的倒推值,则它就是当前棋局最好的走法。当端节点的估值计算出来后,再推算出父节点的得分。推算的方法是:对于处于MAX层的节点,选其子节点中一个最大的得分作为父节点的得分,这是为了使自己在可供选择的方案中选一个对自己最有利的方案;对处于MIN层的节点,选其子节点中一个最小的得分作为父节点的得分,这是为了立足于最坏的情况,这样计算出的父节点的得分为倒推值。

井字棋

相比之下3×3连子棋(也叫做井字棋,英文名:Tic-Tac-Toe)其实还并不算复杂,3×3的棋盘最多可以放9个棋子,先下棋的人最多可以下5颗棋子,也就是说机器最多可以预推出接下来的9步的所有可能性。

如果不考虑游戏规则的话,井字棋总共有 19,683种可能的棋面布局,也就是说在棋盘上的9个位置分别都可以防止黑棋,白棋或者不放置任何棋子(3^9),所有的棋局可能是362880(如果不把追求获胜的判定算进去的话,9步下完,第一步是有9个格子选择,第二步是有8个格子选择……:9!=362880),但是考虑到

  • 一旦有一方连成三子,则此局棋结束

  • 如若白棋先走,则棋局之中,总是白棋比黑棋多一子或白棋黑棋数量相同。

实际的可能情况会小很多,只有138种棋局了。91种棋局是执先者胜,44种棋局是执后者胜,而只有3种情况是平局。(而在实际的棋局过程中,出现平局的概率是非常高的,但是出现平局概率高并不意味着平局的花样就多),我们甚至可以将这三种平局的局面列出来。

下面两幅图都是在http://playtictactoe.org/ 网站上实际对战过程中出现的棋局:

棋局一

棋局二

实际上这两幅图中棋局外表看似不同,但其实是互为镜像的,如果将下面的图旋转180度,就能够得到如上面图一样的棋局。

因此实际上平局的所有可能 棋局只有

棋局一

棋局二

棋局三

Alpha-Go

三月份的时候,有一场李世石对阵AlphaGo的比赛轰动全球,而这次课程也提到了AlphaGo,值得注意的是这次课程的时间是15年的11月份。

这里首先需要说明的是在英语里面Go还有一个意思,那就是「围棋」,而我在之前了解到AlphaGo这个名字的时候,还以为这里的Go是取自于Google这个单词。

来看一下围棋的复杂度

在上面这张表中,也记录了机器人在国际象棋领域首次战胜世界大师这件事。

面对如此复杂的实现,就不能仅仅使用minimax算法了,还有另外加上一些条件。

通过过滤掉那些完全不可能的实现过程,来缩短算法的实现时间,但是即便如此,其计算量还是不可想象的。也正因此,DeepMind的AlphaGo挑战李世石并且最终战胜了他,才是那样的了不起。

游戏设计

这一部分只是简单介绍而已,提到了4X理念。

wikipedia对于4X的介绍:

  • Explore means players send scouts across a map to reveal surrounding territories.

  • Expand means players claim new territory by creating new settlements, or sometimes by extending the influence of existing settlements.

  • Exploit means players gather and use resources in areas they control, and improve the efficiency of that usage.

  • Exterminate means attacking and eliminating rival players. Since in some games all territory is eventually claimed, eliminating a rival’s presence may be the only way to achieve further expansion.

我们很快就可以想到几个即时战略类游戏,比如红色警戒,是有着这样的一套规律的:玩家可以探索地图上的未知区域,玩家可以在领土之上建立起新的工事,玩家可以收集和利用领土上的一些资源,玩家还可以与敌人展开争斗。

后记

整个课程学习下来,觉得还是很有收获的,总结起来,应该是这样几个方面。

  • 整个课程,总共是13周的时间,总计是24次课,每节课大约1小时,时常总计约24小时,内容也十分紧凑,从CS的概括讲到了C语言,又从C语言讲到数据结构、从数据结构讲到了WEB开发中的前端(HTML\CSS\JS)、后端(PHP),后来是网络安全和人工智能,甚至是游戏设计在这个课程中也有所涉及,内容真的是十分丰富。
  • 尽管内容丰富,但是毕竟这只是一个介绍性课程(introductory course ),因此他的知识深度并不够。虽然如此,但还是能够将它作为学习CS的一条线索,也能够用它来对一些普遍问题进行了解。
  • 课程十分有趣,很多比较抽象复杂的问题,都能够通过游戏的方式来解决,印象最深的当属解释冒泡算法(bubble-sort)的时候,请上台来几位同学,每人举一个标有数字的小牌子。
  • 这应该也是我第二个几乎所有课一次不落的学习完毕的公开课课程,上一个也是哈佛公开课,是那个更为人熟知的《幸福课》。
「喜欢,就赞一个呗!(:3 」∠)_ ( ̄y▽ ̄)~*」
「鼓励我写出更好的文字」
「支付宝」