该资源为北京大学理论计算机科学基础课程全套PPT，包含70个讲座内容，全面覆盖理论计算机科学的核心概念与重要议题。
《北京大学理论计算机科学基础70讲》是一套深入浅出的教程，旨在为学生和爱好者提供坚实的理论基础，帮助他们理解计算机科学的本质与核心原理。
1. **计算模型**：讲解了图灵机、λ演算和寄存器机等不同的计算模型。这些概念是理解和分析算法效率及复杂性的基石。
2. **算法设计与分析**：涵盖基本排序（如冒泡排序、快速排序）以及高级查找技术，包括动态规划、贪心策略和回溯法，并详细探讨了各种算法的时间和空间复杂度。
3. **数据结构**：介绍数组、链表、栈、队列等基础数据类型及树与图的性质，在实际应用中如何有效使用这些工具进行问题解决。
4. **图论**：讨论路径、环路以及连通性，涉及最小生成树和最短路径算法（如Prim, Kruskal, Dijkstra 和 Floyd 算法）。
5. **形式语言与自动机理论**：包括正则表达式、有限状态自动机(NFA/DFA)、上下文无关语法(CFG)，以及编译器设计中的相关概念。
6. **计算复杂性理论**：讲解P类问题和NP类问题，NPC问题的概念及重要性，并介绍了时间复杂性和空间复杂性的基本知识。
7. **编码理论**：探讨错误检测与纠正码（如奇偶校验、汉明码），以及更复杂的纠错技术（例如Reed-Solomon码）。
8. **信息论**：阐述熵、互信息和信道容量等概念，讨论了霍夫曼编码及香农定理的基本原理。
9. **概率与随机化算法**：介绍概率理论，并探讨如何在算法设计中利用随机技术提高效率或解决NP难问题（如Monte Carlo 和 Las Vegas 算法）。
10. **计算几何学**：涉及点、线和面的处理，以及计算机图形学中的应用（例如最近邻搜索及多边形剪切）。
11. **计算机系统基础**：介绍硬件架构、操作系统原理等基础知识，帮助理解程序执行过程。
这套教程通过理论与实践相结合的方式传授知识，并提供了丰富的实例和练习题以加深理解和实际运用能力。对于希望深入了解计算机科学理论的学者来说，《北京大学理论计算机科学基础70讲》是一个宝贵的资源。
5星
