函数式编程:密码学和素数

函数式编程:密码学和素数3.1 密码学和素数外星人坐在咖啡馆里,享受着他们精心制作的含咖啡因的饮料。他们要购买全套的《星球大战》传奇,但无法通过流传输到自己的星球!

大家好,欢迎来到IT知识分享网。

3.1 密码学和素数

外星人坐在咖啡馆里,享受着他们精心制作的含咖啡因的饮料。他们要购买全套的《星球大战》传奇,但无法通过流传输到自己的星球!他们准备输入信用卡号,从Nile网站完成购买,但他们停下来想了一下:当他们的财务信息通过Wi-Fi和许多互联网节点到达Nile网站,再到他们的银行授权这次购买时,如何保护信息的安全。这种担心很合理。好消息是,即使通信链路是开放的和公开的,加密技术仍可确保此类交易的安全。

很快就要回家了,但先要再买一些东西!

RSA是最广泛使用的加密策略之一,它是3位设计者Ron Rivest、Adi Shamir和Leonard Adleman的姓氏首字母缩写。RSA的工作方式如下:在线商店具有自己的数学函数(可公开获得),所有用户都可以使用该函数对数据进行加密,然后再通过网络进行传输。(确切地说,浏览器或其他软件可以代表用户执行此操作。)仅将生成的加密数据从一个地方发送到另一个地方,即使在不安全的通道上也可以保证安全。设计该数学函数,以便任何人都可以轻松地使用它来加密数据,而只有商店(或其他受信任的代理,例如银行)可以“恢复”或“反转”该函数。因此,只有受信任的代理才能解密数据并恢复原始的敏感信息。

因为他们设计了密码系统RSA,Rivest、Shamir和Adleman获得了著名的图灵奖。

请注意,我们要发送的任何数据总是可以表示为数字。无论是什么数据,这都是真的,但是如果数据已经是一个数字(例如信用卡号),则尤其清楚。假设Nile网站告诉其用户,用加密函数f(x) = 2x来加密数字数据x。

对于这个简化的例子,我们可以很容易地加密我们要发送的任何数字,只需将它加倍即可。不幸的是,任何人都可以简单地将消息除以2,从而解密消息,这使得加密函数根本不安全。

真正的RSA方案使用较复杂的函数,但仅稍微复杂一些。如果x是我们的信用卡号,则RSA使用函数f(x) = xe mod n对其进行加密,其中e和n是精心选择的常数。上一章中提到,xe mod n表示xe 除以n的余数。在Python中,这可以用表达式(x**e) % n进行计算。

事实证明,如果适当选择e和n,那么在线商店将能够解密该消息以检索信用卡号x。但是即使公开了e和n,也没有其他人可以解密该消息!

怎么会这样?我们如何选择e和n(并与每个人共享,使得每个人都可以加密消息),但仍然只让我们自己有解密的能力?下面是具体做法。首先,我们随机选择两个不同的大素数p和q。接下来,我们将n定义为这两个数字的乘积,n = pq。然后,我们执行两个步骤以找到适合e的值:我们计算m = ( p-1)(q-1),然后选择e为小于m的随机素数,它也不是m的因数。这就行了!它不像加倍那么简单,但也相当简单,用一个简短的Python程序就可以表示。

这就是选择e和n的过程,这些值可以与希望发送加密信息的任何人公开共享。加密很简单:对小于n的任意x,可以通过计算xe mod n进行加密。(较大的值可以分解为较小的值,但是我们在这里不必担心。)在典型的网上购物交易中,你的浏览器将从在线商店获取e和n的公开可用值,并使用它们来加密你的信用卡号x。值e和n一起称为该商店的公钥。在密码学中,公钥是一组可以安全发布的值,但不会泄露相应的私钥。让我们用一个具体的例子来详细说明。

在我们的例子中,令p = 3和q =5。尽管它们太小而不能实际确保安全,但它们肯定是素数。现在,n = 3 × 5 = 15且m = (3-1) × (5-1) = 8。对于我们的加密指数e,我们可以选择素数3,因为它小于8,并且也不是8的因数。现在,使用值e = 3和n = 15,我们可以加密小于n的任何数字。让我们对数字13进行加密:在Python中,我们可以将133 mod 15表达为(13 ** 3)%15。结果是7。所以7是我们的加密数字,我们通过互联网将它发送到在线商店。

我认为密码学的在数学上应该称为“离散数学”!

商店如何解密这个7,以发现原来的数字实际上是13?在计算加密指数e的同时,商店还计算了解密指数d,它具有两个属性:介于1和m-1之间,并且e × d mod m = 1。由于e和m的选择方式不同,总是只有一个具有这两个属性的值(对于证明,我们听离散数学家的)。我们将该值d称为e模m的乘法逆(multiplicative inverse)。在我们的例子中,e = 3且m = 8,因此d也是3(并非总是与e相同,尽管可以相同)。我们确认e × d mod 8 = 9 mod 8 = 1。

利用这个解密指数d,在线商店可以通过计算yd mod n解密它收到的任意数字y。在我们的示例中,我们收到了加密数字y =7。我们用Python表达式((7**3) % 15)计算了73 mod 15,结果为13。确实,这就是我们刚才加密的值!请记住,虽然加密密钥e和n是公开的,但在线商店保持解密密钥d私有。能够获得d的任何人,都可以解密用加密密钥发送的任何消息。

在离散数学或算法导论课程中常常会展示该方案始终有效的证明。然而,对我们而言,更重要的问题是:“为什么这种方案是安全的?”由于值e和n是公开的,因此如果邪恶的特工能够找到最初选作n的因数的两个素数p和q,他们也可以找出m和d,然后从那里激活成功教程代码。但是,将数字n“因数分解”为素数之积是一个难计算问题。难计算问题是指用已知最好的技术,需要很长时间才能计算出来的问题。第7章更详细地探讨了该主题。但是现在,考虑一下:美国国家标准技术研究院(National Institute of Standards and Technology, NIST)估计,如果今天我们用大约900位数字的公共密钥来加密消息,那么通过因数分解的结果来解密将远远超出2042年——即便用非常快的计算机进行攻击。

3.2 一等函数

在上一章中,我们了解了Python函数,并探讨了递归的“威力”。我们研究过的程序设计风格[即由相互调用的函数(可能还会调用它们自己)构成的程序]称为函数式编程。

在Python这样的函数式编程语言中,函数是数据,就像数字、列表和字符串是数据一样。在Python之类的语言中,我们说函数是该语言的“一等公民”,因为我们可以编写一些函数,以其他函数作为其输入。我们还可以编写一些函数,以其他函数作为其返回值。在本章中,我们将探讨这些思想。首先我们来编写一个简短的程序,该程序可以有效地生成较长的素数列表。我们将构建可在RSA加密中实现加密和解密的函数。在本章结束时,你将编写一些Python程序,用于发送和接收加密数据,即只有你和你的朋友才能解密的数据。

我喜欢所有事都做到一等!

3.3 生成素数

受RSA密码学的激励,我们的首要任务是找到一种生成素数列表的方法。我们计划:先编写一个函数,确定其参数是否为素数;然后,我们可以利用该函数测试一系列连续整数是否为素数,并将是素数的整数保存在一个列表中。

如何测试单个正整数n是不是素数?根据定义,如果2~n-1的任意整数能整除n,则n不是素数。如果2~n-1没有整数能整除n,则n是素数。只要测试2~sqrt(n)的数字就足够了,但目前我们就测试2~n-1的所有可能的因数。我们将设计一个函数divisors,可以实现这些可能性以及更多的可能性。

为此,我们设计divisors(n, low, high),它接受整数n、low和high作为输入。如果n在low和high之间(包括两个端点)有任何因数,则函数divisors应返回True。如果n在low和high之间没有因数,则divisors应返回False。

让我们设定期望的结果:一方面,divisors(15, 2, 14)应该返回True,因为15在2到14之间(包括2和14)有因数,实际上有几个;另一方面,divisors(11, 2, 10)应该返回False,因为11在2到10之间(包括2和10)没有因数。如果divisors(n, 2, n-1)返回False,则数字n就是素数。

为了强化上一章中的递归设计思想,我们用递归来编写divisors(n, low, high)。首先是基本情况:如果low>high,则从low到high的范围内没有整数。故而,在该范围内不可能存在因数。因此,如果low > high,则divisors应返回False。

如果low <= high,那么我们需要检查low是不是n的因数。我们可以测试n是否可以被n整除,如果可以,则可以找到该范围内的因数。在这种情况下,divisors必须返回True。

当low<=high,但low不是n的因数时,存在什么递归子结构?如果low不是n的因数,则只需要检查从low + 1到high的整数。这可以通过调用divisors(n, low+1, high)来实现,函数编写如下:

def divisors(n, low, high): """ divisors returns True if n has a divisor between low and high (inclusive) otherwise, divisors returns False """ if low > high: return False elif n % low == 0: # check if n is divisible by low? return True else: return divisors(n , low+1, high)

如前所述,我们可以通过检查n在2到n-1之间是否有因数,来测试n是不是素数:

def isPrime(n): """ For any n greater than or equal to 2, isPrime returns True if n is prime. isPrime returns False if n is not prime """ # if there's a divisor, it's not prime if divisors(n, 2, n-1) == True: return False else: return True

可以更简洁地编写如下:

def isPrime(n): """ For any n greater than or equal to 2, isPrime returns True if n is prime. isPrime returns False if n is not prime """ return not divisors(n, 2, n-1)

回想一下,not用于否定一个布尔值。如果divisors(n, 2, n-1)为True,则not divisors(n, 2, n-1)为False;如果divisors(n, 2, n-1)为False,则not divisors(n, 2, n-1)为True。尽管更简洁,但后一个版本不一定可读性更好。有些人更喜欢前者,而有些人更喜欢后者。

无论哪种方式,我们接下来都使用isPrime生成素数列表,再次利用递归。想象一下,我们想知道从整数low(至少2)到上限high(例如100)的所有素数。对于该范围内的每个数字,我们可以测试它是不是素数,如果是素数,就将它加入一个不断增长的素数列表中。在查看下面的代码之前,看看你是否能确定这个函数的基本情况和递归情况。

下面是一个Python实现:

def listPrimes(low, high): """ Returns a list of prime numbers between low and high, inclusive """ if low > high: return [] elif isPrime(low) == True: return [low] + listPrimes(low+1, high) else: return listPrimes(low+1, high)

在elif语句块中,我们返回[low] + listPrimes(low+1, high)而不是low + listPrimes (low+1, high)。为什么?

请记住,listPrimes(low+1, high)返回一个列表。后一个表达式尝试向该列表添加一个整数low。前一个表达式(正确的表达式)将一个列表[low]添加到该列表。Python在实现列表加列表时很轻松,这是“列表连接”。Python不会将整数加入列表。(尝试一下,你收到的错误消息也会这么说!)

上述生成素数的策略是可行的,但速度很慢。问题是它重复了很多工作。例如,按照上面的写法,listPrimes(2,100)会发现2是素数,并且仍然检查2的每一个倍数是否为素数。同样,它会发现3是素数,然后继续检查3的每一个倍数是否为素数。也许,一旦找到一个素数,就可以避免检查该素数的倍数,因为我们确信这些倍数不是素数。

尚不十分清楚Eratosthenes是否真的发现了名为“埃拉托斯特尼筛法”的算法。

一种更快的生成素数的算法称为“埃拉托斯特尼筛法”(sieve of Eratosthenes),以古代希腊数学家的名字命名。我们的想法是对已经发现的素数的倍数进行筛选或过滤。如前所述,listPrimes(2,100)会发现2是素数。然后,我们从考虑的数字中删除或筛掉2的所有倍数,这些倍数不是素数。数字3是筛掉所有2的倍数后剩下的最小值,因此3是素数。然后,我们从剩余值中筛掉所有3的倍数,它们也不是素数。完成后,剩余值中最小的是5。因此5是素数,我们筛掉它的倍数。我们继续这个过程,直到达到high或100。

网上有埃拉托斯特尼筛法的精美动画。其中最后一个画面显示如图3.1所示。

我们来实现一种基于筛子的算法(本着埃拉托斯特尼筛法的精神),我们称之为primeSieve。primeSieve函数将接受我们感兴趣的整数列表,返回一个列表,仅包含原始列表中的素数。Python有一个内置函数range(low, high),该函数创建顺序的整数列表。下面是使用range的两个例子:

>>> list(range(0,5)) [0, 1, 2, 3, 4]   >>> list(range(3,7)) [3, 4, 5, 6]
函数式编程:密码学和素数

图3.1 埃拉托斯特尼筛法

请注意,我们从range返回的列表似乎过早停止了,少了一个数字——最终整数为high-1。这是Python中的约定。另外,要查看得到的列表的各个元素,我们需要在结果上调用list。因此,如果要查看2~1000的整数列表,可以调用list(range(2, 1001))。试试吧!

在编写primeSieve之前,让我们考虑一下它如何工作。设想我们从列表range(2, 11)开始,它是:

[2, 3, 4, 5, 6, 7, 8, 9, 10]

将此列表传递给primeSieve就是问:“您能在这个列表中找到所有素数吗?”为了回应这个礼貌的请求,primeSieve函数应提取第一个元素2并保留它,因为2是素数。然后,应从该列表中筛掉所有2的倍数,从而得到一个新列表:

[3, 5, 7, 9]

现在怎么办?好吧,我们现在有一个较小的列表,想知道它的哪些元素是素数。啊哈!我们可以将这个较小的列表发送回primeSieve——毕竟,primeSieve的任务是返回输入列表中存在的素数。递归!

继续我们的例子,我们第一次调用primeSieve时发现了2,筛掉2的倍数后得到列表[3, 5,7,9],并在新列表上调用primeSieve。递归调用返回的所有结果都将附加在我们当前保持的2之后,因此我们会得到2~10的所有素数的列表。

设想我们有一个名为sift(p, L)的函数,该函数以数字p和一个列表L作为输入,返回一个列表,从L中删除了p的所有倍数。然后,我们可以像这样实现primeSieve:

def primeSieve(numberList): """ primeSieve returns the list of all primes in numberList using a prime sieve algorithm """ if numberList == []: # if the input list is empty, return [] # ...we're done else: p = numberList[0] # the first element is prime return [p] + primeSieve(sift(p, numberList[1:]))

在这里,primeSieve假定其初始输入是从2开始的整数顺序列表。因此,每次递归调用时p都是素数。例如,筛掉2的倍数后,对primeSieve的递归调用将接受参数列表[3, 5, 7, 9]。然后else语句块将从列表的最前面取得3,筛掉3的所有倍数,得到[5, 7],然后再次递归。在下一次递归调用中,p将为5,并且函数将对列表[7]递归调用。该递归调用将取得7并递归到空列表。每次输入列表都会变得越来越短,更接近于处理空列表输入的基本情况。在这种情况下,primeSieve正确报告“输入参数中所有素数的列表为空”,并且它会返回空列表。

自顶向下的设计?将它称之为“如意算盘”方法怎么样?因为我们的愿望是在需要时就有一个辅助函数!

我们仍然需要一个可以进行实际筛选的函数!上面,我们设想有一个名为sift的函数,该函数接受两个参数(一个数字p和一个列表L),并返回L中不是p的倍数的所有数字。请注意,即使尚未实现sift,我们已经在假设有sift的情况下编写了primeSieve。这种编写程序的方法称为“自顶向下的设计”,因为我们从“顶部”(我们想要的)开始,然后逐步进行到所需的细节。

接下来,我们将着手编写sift函数。

3.4 过滤

Python有一个名为filter的内置函数,它几乎完成了我们要进行的所有筛选工作。filter的不寻常之处在于,它接受一个函数作为输入参数。我们来看看filter的样子以及工作原理。首先,我们将定义一个供filter使用的函数:

def is_not_divisible_by_two(n): """ this function returns True if n is NOT divisible by 2, and returns False if n IS divisible by 2 """ return n%2 != 0

这似乎是个奇怪的函数!

回想一下,n%2 == 0会检查n是否可被2整除。因此,如果n无法被2整除,则n%2!= 0将返回True。例如:

>>> is_not_divisible_by_two(41) True >>> is_not_divisible_by_two(42) False

利用我们的函数is_not_divisible_by_two,下面是使用filter的一个例子:

>>> list(filter(is_not_divisible_by_two, [2,3,4,5,6,7,8,9,10])) [3, 5, 7, 9]

你可能已经推断出filter在做什么:它的第一个输入参数是一个函数,第二个输入参数是一个列表。输入函数需要接受单个输入并返回布尔值。返回布尔值的函数称为“谓词”(predicate)。你可以认为谓词是在告诉我们它是否“喜欢”它的参数。然后filter会返回列表中该谓词“喜欢”的所有元素。在我们的例子中,is_not_divisible_by_two是“喜欢”奇数的谓词,因此filter返回一个列表,包含原始列表中所有的奇数。

与range一样,filter要求将它的结果传递给list,以便我们查看它的值。这是因为这两个函数会等待,直到需要结果时,才会计算其结果。

一个函数接受其他函数作为参数?也许很奇怪,但绝对是允许的,甚至是鼓励的!这个想法对于函数式编程非常重要:函数可以像其他任何类型的数据一样传入或传出其他函数。实际上,第4章将说明为什么这个想法根本不那么奇怪。

数字列表不是唯一可以过滤的数据类型。下面是filter的另一个例子,这次使用字符串列表。为了准备再次访问地球,外星人正尝试掌握英语和许多其他语言。他们有很多单词需要学习,但是他们听说4个字母的单词是最关键的,他们首先关注这些单词。因此,假设外星人希望过滤[‘aardvark’,’darn’,’wow’,’spam’,’zyzzyva’]这样的列表,以获取仅有4个字母的单词列表[‘darn’,’spam’]作为输出。

如前所述,我们先定义一个谓词函数:一个名为hasFourLetters的函数。该函数以一个名为s的字符串作为输入,如果输入字符串的长度为4,则返回布尔值True,否则返回False。

def hasFourLetters(s): """ returns True if the length of s is 4, else returns False """ return len(s) == 4

利用hasFourLetters,下面是filter的另一个例子:

>>> list(filter(hasFourLetters, ['ugh', 'darn', 'wow', 'spam', 'zyzzyva'])) ['darn', 'spam']

3.5 lambda

我们已经看到,函数filter可以帮助我们筛选数字列表,但到目前为止,我们只筛掉了偶数数字,留下了不能被2整除的值。请记住,埃拉托斯特尼筛法利用反复筛选,即针对序列中的不同值进行筛选。如果要筛选3的倍数,可以使用另一个辅助函数:

def is_not_divisible_by_3(n): """ returns True if n is not divisible by 3, else False """ return n % 3 != 0

以这种方式继续,我们需要一个函数来删除5的倍数,另一个针对7,再针对11,依此类推。但这种方法不通用!作为替代,我们可以尝试在谓词函数中添加第二个参数,如下所示:

def is_not_divisible_by_d(n, d): """ returns True if n is not divisible by d, else False """ return n % d != 0

这个函数执行正确的计算,但filter要求它的第一个输入是只接受一个输入自变量的谓词函数,而不是像我们在这里所做的那样接受两个输入。

我们真正需要的是一次性使用的函数——在我们需要它时,可以用当前要过滤的数字来定义它,然后在用完后立即丢弃它。Python支持临时函数的创建和使用,甚至我们都不必为它们命名!这样的函数称为“匿名函数”。

初次接触时,匿名(或无名)函数似乎违反直觉,但请记住,Python(和每种编程语言)很自然地支持匿名数据:

>>> 14 * 3 42 >>> [6,7] + [8,9] [6,7,8,9]

在这两个例子中,正在操作的数据和结果都没有Python名称。我们没有分配变量来保存它们。我们对它们有自然语言名称,例如“四十二”或“八,九的列表”,但这些语言便利性与Python无关。

由于Python将函数视为一等公民,因此它们也可以不用名称来表达和使用。下面是一个匿名函数的例子:

>>> lambda x: 2*x <function _ _main_ _.<lambda>>

“lambda”源自名为“lambda演算”的数学分支(请参见3.6.3节的补充内容),它影响了第一种函数式编程语言LISP。

请注意,Python将这视为函数。lambda不是名字,而是一个Python保留字,表示我们正在定义一个匿名函数。在关键字lambda后面出现该函数的输入参数的名称。在这个例子中,它有一个名为x的参数,接着是一个冒号,然后是匿名函数应返回的值。

让我们看3个使用lambda的例子:

>>> (lambda x: 2*x)(50) # compare to f(50) 100 >>> (lambda x, y: x-2*y)(50,4) # compare to f(50,4) 42 >>> (lambda n: n%2 != 0)(41) # compare to is_not_divisible_by_2(41) False

匿名函数的工作原理与命名函数完全相同。为了直接调用它们,有必要将它们放在括号内,但是如果它们用于传递,就不必放在括号内。

最后一个示例lambda n: n%2 != 0,完全等价于我们的is_not_divisible_by_2函数。从而:

>>> list(filter(lambda n: n%2 != 0, [2,3,4,5,6,7,8,9,10])) [3,5,7,9]

Python中的匿名函数语法不寻常,因为我们没有将函数的参数括起来,也没有return语句。作为替代,Python中的匿名函数返回冒号后面的任意值。

为了指出匿名函数确实是完全意义下的函数,我们想说,如果你愿意,可以给它们命名,就像所有其他Python数据一样:

>>> double = lambda x: 2*x >>> double(50) 100

在第一行中,我们将一个名为double的变量赋值lambda x: 2 * x。从那里开始,double行为就像是以更传统的方式用def定义的函数一样。所以double是一个函数,带有一个参数。如果要使用它,需要以习惯的方式向它传递一个值。

让我们利用匿名函数完成sift的编写,如下所示:

def sift(toRemove, numList): """ sift takes a number, toRemove, and a list of numbers, numList. sift returns the list of those numbers in numList that are not multiples of toRemove """ return list(filter(lambda x: x%toRemove != 0, numList))

我们传递给filter的匿名函数在其函数体中使用了整数toRemove,而不必将它作为参数传入。匿名函数是在toRemove已经存在并具有值的环境中定义的。

为了进行比较,我们还可以用列表推导式来编写sift(请参见3.6.1节的补充内容):

def sift(toRemove, numList): """ sift takes a number, toRemove, and a list of numbers, numList. sift returns the list of those numbers in numList that are not multiples of toRemove """ return [x for x in numList if x%toRemove != 0]

因此,我们再次完成了primeSieve函数,现在有了一个改进的sift:

def primeSieve(numberList): """ primeSieve returns the list of all primes in numberList using a prime sieve algorithm """ if numberList == []: # if the input list is empty, return [] # ...we're done else: p = numberList[0] # the first element is prime return [p] + primeSieve(sift(p, numberList[1:]))

尝试运行primeSieve生成较长的素数列表。如果给它足够大的列表,Python会“抱怨”。例如:

>>> primeSieve(list(range(2, 10000)))

导致了很长的、看似不友好的错误消息。问题在于,每个递归调用都会在栈内存中创建一个栈帧,如果没有更多可用的栈内存,计算将崩溃。第4章将详细介绍执行递归函数时计算机内部发生的情况,那时栈内存问题就更有意义了!现在,请注意,通过在源文件的提示符或顶部添加以下几行内容,你可以要求Python提供更多的栈内存:

import sys sys.setrecursionlimit(20000) # Allow 20000 # stack frames

在这里,我们要求为20000个栈帧留出空间。某些操作系统允许你要求的栈帧可能比这更多或更少。大多数现代计算机会允许更多。

CS课程的大胆推销!

这将我们带到了最后一个知识点:尽管primeSieve相当高效,但是RSA方案的大多数良好实现都使用更为有效的方法来生成较大的素数。实际上,在对互联网交易进行编码时,RSA使用的素数通常有几百位数!有关算法或密码学的计算机科学或数学课程,可能会展示更复杂、更有效的算法来生成素数。

本文摘自《计算机科学概论(Python版)》

函数式编程:密码学和素数

本书是美国哈维玛德学院“计算机科学通识”课程的配套教材,随后在美国许多学院和大学中被采用。在哈维玛德学院,几乎每个一年级学生都会学习这门课程(不论学生的最终专业是什么),它是学院核心课程的一部分。我们的教材也被克莱蒙特学院联盟的许多学校采用,包括主修人文科学、社会科学和艺术的学生都在使用。因此,这是学生的第一门计算课程,无论他们的专业是什么。

从第1章开始,本书强调解决问题和重要思想的特点就很明确。我们在第1章中描述了一种非常简单的编程语言,用于控制虚拟的“Picobot”机器人。读者花十分钟就可以掌握其语法,但这里提出的计算问题是深刻而有趣的。

本书的其余部分遵循了同样的思路。我们使用Python语言,因为它的语法简单,并且有一套丰富的工具和软件包,让新手程序员能够编写有用的程序。在第2章中,我们对使用Python进行编程的介绍仅限于该语言语法的有限子集,这体现了函数式编程语言的精神。通过这种方式,读者很早就掌握了递归,并意识到他们可以用极少的代码编写有趣的程序。

第3章在函数式编程上更进一步,介绍了高阶函数的概念。第4章关注一个问题:“我的计算机如何做到这一切?”我们研究了计算机的内部工作原理,从数字逻辑到计算机组织,再到用机器语言编程。

既然已经揭开了计算机的“神秘面纱”,读者也看到了“幕后”发生的事情的物理表示,于是我们在第5章中继续探讨了计算中更复杂的思想,同时探讨了诸如引用和可变性等概念,以及包括循环在内的构造、数组和字典。我们利用第4章介绍的计算机物理模型来解释这些概念和结构。根据我们的经验,如果读者建立了底层的物理模型,就更容易理解这些概念。所有这些都是在读者熟悉的场景下完成的,这就是一个推荐程序,就像在线购物中使用的那种。

内容新!有改进!有许多“边缘的”有用注释!

在第6章中,我们探讨了面向对象编程和设计中的一些关键思想。这里的目标不是培养专业级的程序员,而是解释面向对象范式的基本原理,并让读者了解一些关键概念。最后,在第7章中,我们研究了问题的“难度”——在计算复杂性和可计算性方面,提供了一些优雅的,但数学上非常合理的处理方法,最终证明了计算机上无法解决的许多计算问题。我们使用Python作为模型,而不是使用形式化的计算模型(如图灵机)。

本书意在与我们为课程开发的大量资源一起使用,这些资源可从网站https://www.cs. hmc.edu/csforall上获得。这些资源包括完整的授课PPT、丰富的每周作业集、一些附带的软件和文档,以及关于该课程已发表的论文。

我们有意让这本书的篇幅相对较短,并努力让它变得有趣、可读性好。本书准确地反映了课程的内容,而不是一本不可能在一个学期学完的、令人望而生畏的百科全书。我们编写这本书时相信,读者可以随着课程的进行而舒适地阅读所有内容。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/69631.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信