名词辨析

GNU

• GNU’s Not Unix!的递归缩写
• 一个自由的操作系统,起源于GNU计划,希望发展出一套完整的开放源代码操作系统来取代 Unix
• 基本组成包括：
  • GNU编译器套装（GCC）
  • GNU的C库（glibc）
  • GNU核心工具组（coreutils）

GCC

• GNU Compiler Collection, GNU编译器套装，最初是为了GNU操作系统而编写的编译器。
• 有多种语言前端，可用于解析不同的编程语言、操作系统、计算机系统结构，是GNU计划的关键部分，也是GNU工具链的主要组成部分之一
• 可以编译C、C++、JAV、Fortran、Pascal、Object-C、Ada，Go等语言

gcc/g++/MinGW

• gcc: GCC中的GUN C Compiler（C 编译器）
• g++: GUN C++ Compiler（C++编译器）
• MinGW: Minimalist GNU for Windows，是将GCC编译器和GNU Binutils移植到Win32平台下的产物

但根据GCC的gcc和g++区别的说法，gcc和g++并不是编译器，它们只是一种驱动器¹，它们会根据参数中要编译的文件的类型，调用对应的GUN编译器。以编译C语言为例，包含以下过程。

链接，将多个可重定位目标文件和标准库函数合并为可执行目标文件的过程，为了解决外部内存地址的依赖问题

过程包括：1. 地址和空间分配(Address and Storage Allocation) 2. 符号决议(Symbol Resolution) 3. 重定位(Relocation)

What does compiler do ?

分类

1. 队列式分支限界
2. 优先队列式分支限界

定义状态转移方程的关键在于对状态做出完整表示，举个例子，最长上升子序列问题中，不同的状态是一些子序列，以子序列的最后一项作为划分依据就可以完整表示不同的状态

贪心策略正确性证明

归纳法

归纳法证明的核心逻辑：证明采用贪心策略执行到任意步数时获得的解都是最优解的一部分