第01章习题答案

第一章习题答案

1. 什么是Internet和万维网，它们的区别在哪里？

答：Internet是由成千上万台计算机设备互相连接，基于TCP/IP协议进行通信从而形成的全球网络。万维网是Internet上最重要的服务之一，也常被简称为“W3”或“Web”。万维网主要使用HTTP协议将互联网上的资源结合在了一起，并在浏览器中以Web页面的方式呈现给用户。
请简单描述用户上网浏览网页的原理。
答：用户打开Web浏览器并输入需要访问的URL地址，该地址将发送给对应的Web服务器。Web服务器然后将该地址对应的文本、图片等内容发送给用户并显示在用户使用的Web浏览器中。

2. Web前端技术的三大核心基础是哪些内容？

答：HTML、CSS和JavaScript。

3. Web前端新技术HTML5与HTML有什么关系?

第1章 算法引论

1.1 算法与程序

• 输入: 有零个或多个外部量作为算法的输入。
• 输出: 算法产生至少一个量作为输出。
• 确定性: 组成算法的每条指令清晰、无歧义。
• 有限性: 算法中每条指令的执行次数有限，执行每条指令的时间也有限。

区别:

• 算法: 满足上述性质的指令序列。
• 程序: 算法用某种程序设计语言的具体实现，程序可以不满足算法的有限性。

1.3 描述算法

算法的描述方法可以归纳为以下几种：

1. 自然语言
2. 图形，如流程图，图的描述与算法语言的描述对应
3. 算法语言，即计算机语言、程序设计语言、伪代码
4. 形式语言，用数学的方法，可以避免自然语言的二义性

第2章 递归与分治策略

2.1 递归的概念

• 递归算法：直接或间接地调用自身的算法。
• 递归函数：用函数自身给出定义的函数。
• 递归分类：
  • 直接递归
  • 间接递归
• 递归本质：将原问题转化为同质子问题求解。

例1 阶乘函数

阶乘函数可递归地定义为：

边界条件:

n = 0
n! = 1
n > 0
n! = n * (n - 1)!

第3章 动态规划

3.1 动态规划的起源

20世纪50年代初，美国数学家R.E. Bellman等人在研究多阶段决策过程（multistep decision process）的优化问题时，提出了著名的最优化原理（principle of optimality）。他们将多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

3.2 动态规划的应用

自问世以来，动态规划在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用，包括但不限于：

• 最短路线
• 库存管理
• 资源分配
• 设备更新
• 排序
• 装载问题

使用动态规划方法比使用其他方法求解这些问题更为方便和高效。

第4章 贪心算法

4.1 学习要点

• 理解贪心算法的概念
• 掌握贪心算法的基本要素
  1. 最优子结构性质
  2. 贪心选择性质
• 通过应用范例学习贪心设计策略

4.2 问题提出

例：货币兑付问题

银行出纳员支付一定量的现金，其手中有各种面值的货币，要求用最少的货币张数来支付现金。

第5章 回溯法

5.1 回溯法简介

回溯法是一种系统的搜索策略，广泛应用于解决组合优化问题。它通过构建解空间树，逐步探索可能的解，并在发现当前路径无法得到有效解时进行回溯，从而避免无谓的搜索。

5.1.1 回溯法的关键概念

• 解空间：问题所有可能解的集合。
• 解向量：用一个n元组 (x₁, x₂, ..., xₙ) 表示问题的解，其中每个 xᵢ 代表解的一个组成部分。
• 显式约束：对解向量中各分量 xᵢ 的取值进行限制。
• 隐式约束：为了满足问题的整体解，还需要对不同分量之间施加约束。

5.1.2 回溯法的基本思想

动态规划【自用】

动态规划是数学和计算机科学中使用的一种方法，通过将复杂问题分解为更简单的子问题来解决这些问题。通过仅求解每个子问题一次并存储结果，它避免了冗余计算，从而为各种问题提供了更高效的解决方案。

关键概念：

• 最优子结构：问题的最优解可以从其子问题的最优解中构建。
• 重叠的子问题：子问题通常在较大的问题中重复出现，从而导致冗余计算。
• Memoization / Tabulation：存储子问题的解决方案以避免重新计算。

分支和限界法【自用】

Branch and Bound Algorithm 是组合优化问题中使用的一种方法 ，用于系统地搜索最佳解决方案。它的工作原理是将问题划分为更小的子问题或分支，然后根据最佳解决方案的边界消除某些分支。此过程一直持续，直到找到最佳解决方案或探索了所有分支。分支和限界法 通常用于旅行推销员和作业调度等问题。

分支和限界法 简介：

• DSA 中的 分支和限界法 含义
• 分支和限界法 简介
• 回溯和 Branch-N-Bound 之间的区别

贪心算法【自用】

顾名思义，该算法一次构建一个解决方案，然后选择下一个提供最明显和直接好处的部分，即，这是当时最优化的选择。因此，选择局部最优也会导致全局解的问题最适合 Greedy。

贪心算法的一些重要问题是：