D上的关系集,D和S二者定义了数据的模型,是对数据的抽象;P是表示D上的基本操作 集,定义了该数据模型的功用,是对数据操作的抽象 学生不易理解的是抽象数据类型和数据运算的具体实现之间的关系,需通过实例多加说 明 (4)算法及其复杂性的分析与评价 算法设计与算法分析是计算机科学的核心问题 算法设计是求解问题时必须要考虑的问题,其任务是对各类具体问题设计良好的算法及 研究设计算法的规律和方法。需要在此简单介绍包括穷举法、回溯法、分治法、递归法和贪 心法等在内的常用的算法设计方法的基本思想,并在后续章节使用到时详加阐述 算法的复杂性是度量算其效率、评价其优劣的重要依据。算法分析技术即是利用数学工 具,对每一个具体算法讨论其各种复杂度,以探讨某种具体算法适用于哪类问题,或某类问 题宜采用哪种算法;并从解决同一问题的不同算法中选择出较为合适的一种,或者是对原有 的算法进行改造、加工,使其更优、更好 算法复杂性体现在运行该算法所需要的计算机资源的多少上面,所需的资源越多表明该 算法的复杂性越高:反之,该算法的复杂性越低。计算机资源中最重要的是时间资源和空间 资源。所以,算法的复杂性通常由时间复杂性和空间复杂性两个指标来表示。 讲授算法分析方法时需要强调的是,算法复杂性并非采用诸如微秒、纳秒这样的真实的 时间单位来表示,也即,算法分析感兴趣的并非具体的时间、空间单位,而是算法与输入规 模之间的关系,即用一定“规模”的数据作为输入时程序运行所需的“基本操作”或“基本 空间”数来描述时间或空间效率。另外,由于用来表示数据规模和时间、空间开销关系的函 数都相当复杂,通常采用渐进分析方法,即在分析时忽略那些不能显著改变函数量级的部分, 而把注意力集中在相对重要的部分 6.课后练习和实习 作为教学的重要一环,课后练习和实习帮助学生巩固课堂所学理论知识,训练学生创新 思维能力训练、工程实践能力。 概论部分可以安排2-3道书面作业,也可酌情采用 ACM/ICPC程序竞赛题库POJ系统 安排1道相对简单的实习题来训练学生熟悉POJ环境和使用方法。例如,下面的ACM题目 http://acm.pku.edu.cn/judgeonline/problem?id=1000 http://acm.pku.edu.cn/judgeonline/problem?id=1045 7.教学案例 以算法时间复杂性分析作为讲解渐进分析方法的实例 大多数情况下,算法的时间复杂度是根据算法执行过程中需要实施的赋值、比较等运算 数目的多寡来衡量的。 可以先从简单的例子开始分析。例如, for( 0,i<n;,i++) sum +=all 是一段对数组中的各个元素求和的代码。其中主要的操作为赋值运算,故其时间代价主要体 现在赋值操作的数目上。在循环开始之前有两次赋值,分别对ⅰ和对sum进行;循环进行 了n次,每次循环中执行两次赋值,分别对sum和对i进行更新操作。总共有2+2n次赋D 上的关系集，D 和 S 二者定义了数据的模型，是对数据的抽象；P 是表示 D 上的基本操作 集，定义了该数据模型的功用，是对数据操作的抽象。 学生不易理解的是抽象数据类型和数据运算的具体实现之间的关系，需通过实例多加说 明。 （4）算法及其复杂性的分析与评价 算法设计与算法分析是计算机科学的核心问题。 算法设计是求解问题时必须要考虑的问题，其任务是对各类具体问题设计良好的算法及 研究设计算法的规律和方法。需要在此简单介绍包括穷举法、回溯法、分治法、递归法和贪 心法等在内的常用的算法设计方法的基本思想，并在后续章节使用到时详加阐述。 算法的复杂性是度量算其效率、评价其优劣的重要依据。算法分析技术即是利用数学工 具，对每一个具体算法讨论其各种复杂度，以探讨某种具体算法适用于哪类问题，或某类问 题宜采用哪种算法；并从解决同一问题的不同算法中选择出较为合适的一种，或者是对原有 的算法进行改造、加工，使其更优、更好。 算法复杂性体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多表明该 算法的复杂性越高；反之，该算法的复杂性越低。计算机资源中最重要的是时间资源和空间 资源。所以，算法的复杂性通常由时间复杂性和空间复杂性两个指标来表示。 讲授算法分析方法时需要强调的是，算法复杂性并非采用诸如微秒、纳秒这样的真实的 时间单位来表示，也即，算法分析感兴趣的并非具体的时间、空间单位，而是算法与输入规 模之间的关系，即用一定“规模”的数据作为输入时程序运行所需的“基本操作”或“基本 空间”数来描述时间或空间效率。另外，由于用来表示数据规模和时间、空间开销关系的函 数都相当复杂，通常采用渐进分析方法，即在分析时忽略那些不能显著改变函数量级的部分， 而把注意力集中在相对重要的部分。 6．课后练习和实习 作为教学的重要一环，课后练习和实习帮助学生巩固课堂所学理论知识，训练学生创新 思维能力训练、工程实践能力。 概论部分可以安排 2-3 道书面作业，也可酌情采用 ACM/ICPC 程序竞赛题库 POJ 系统 安排 1 道相对简单的实习题来训练学生熟悉 POJ 环境和使用方法。例如，下面的 ACM 题目： http://acm.pku.edu.cn/JudgeOnline/problem?id=1000 http://acm.pku.edu.cn/JudgeOnline/problem?id=1045 7．教学案例 以算法时间复杂性分析作为讲解渐进分析方法的实例。 大多数情况下，算法的时间复杂度是根据算法执行过程中需要实施的赋值、比较等运算 数目的多寡来衡量的。 可以先从简单的例子开始分析。例如， for (i = sum = 0; i<n; i++） sum += a[i]; 是一段对数组中的各个元素求和的代码。其中主要的操作为赋值运算，故其时间代价主要体 现在赋值操作的数目上。在循环开始之前有两次赋值，分别对 i 和对 sum 进行；循环进行 了 n 次，每次循环中执行两次赋值，分别对 sum 和对 i 进行更新操作。总共有 2 + 2n 次赋