孙成敏教授讲解取整函数性质与算法设计

本篇课件主要聚焦于取整函数的若干性质及其在计算机算法设计与分析中的应用。取整函数f(x)=  x  和g(x)=  x  是两个重要的数学工具，它们满足以下关键性质： 1. **性质1：取整不等式** - 表达式 x-1 <  x  ≤ x ≤  x  < x+1 描述了取整函数的边界行为，即整数部分（小于等于）不大于原数，且大于等于其下一个整数的部分。 2. **性质2：对半数的特殊性质** - 对于任何正整数n，有  n/2  +  n/2  = n，这表明整数部分和分数部分相加等于原数的整数部分。 3. **性质3：取整的乘法性质** - 对于非负数n和a,b，取整函数具有分配性，即   n/a  /b  =  n/ab  和   n/a  /b  =  n/ab 。 4. **性质4：取整的线性不等式** - 对于正数a和b，取整函数的界限关系为  a/b  ≤ (a+(b-1))/b 和  a/b  ≥ (a-(b-1))/b，体现了整数除法的下界和上界。 5. **取整函数的单调性** - 函数f(x)=  x  和 g(x)=  x  都是单调递增函数，这意味着随着x的增加，它们的值也相应增加。 这些性质在算法分析中至关重要，尤其是在处理涉及精度和效率的场景，如近似计算、数据处理和编程中。课程大纲涵盖了多种核心算法设计策略，如分治法、贪心法、动态规划、回溯法和分支-限界法，以及基本的算法分析方法，如时间复杂度和空间复杂度分析。学习目标包括掌握基本算法设计方法、理解分析算法的数学基础，并灵活运用这些方法解决实际问题。课程还强调算法与数据结构的关系，以及如何用SPARKS语言编写算法。 通过本课程的学习，学生将能够理解和应用这些取整函数性质，提升算法设计和分析能力，为解决各种计算机科学问题奠定坚实的基础。