1、数学文化之运筹学刘丙强山东大学数学学院知新楼 B835; 2013-11-13 (2)1运筹学理论内容：2数学规划线性规划整数规划内容组合优化图与网络网络优化算法分析算法复杂性近似算法非线性规划组合优化综述 组 合最 优 化：解决离散 结 构上的 优 化 问题 ； 主要包括： 组 合数学； 数学 规 划（ 线 性 规 划）； 算法理 论 与方法； 图论 中的 优 化 问题 ； 本 节 内容： 组 合 优 化化 问题 与算法； 算法复 杂 性； 近似算法3算法理论 算法：解决 问题 的步 骤 ； 输 入与 输 出； 流程与 语 言； 复 杂 性： 时间 、空 间 复 杂 性； 准确性的衡量； 计
2、 算机与算法； 算法思想： 精确算法； 贪 婪算法； 启 发 式算法； 近似算法； 确定性算法、非确定性算法； 4算法理论：复杂性 时间复杂性（算法可行性与扩展性）： 算法运行时间的快慢； 与输入数据规模有关； 上界 ：函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在正整数 n0 和正常数 c， 使得对所有 n n0 ， 都有 f(n) cg(n)， 就称 f(n) 的阶至多是 O(g(n)。 下界 ： 函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在正整数 n0 和正常数 c， 使得对所有 n n0 ， 都有 f(n) cg(n)， 就称 f(n) 的阶至少是 (
3、g(n)。 准确界 ： 函数 f(n) 和 g(n) 都是整数到正实数的函数，如果存在正整数 n0 和正常数 c1 和 c2 ( c1 c2 )， 使得对所有 n n0 ， 都有 c1 g(n) f(n) c2 g(n)， 就称 f(n) 的阶至多是 (g(n)。 1 loglogn logn n1/2 n3/4 n nlogn n2 2n n! 2n2 多 项 式与非多 项 式； 5算法理论：复杂性 例：排序 问题 ： 遍 历 排序 ： O(n2)； 分 组 排序： O(nlogn)； 多 项 式 时间 与指数 时间 ：6计算量 规模 n 的近似值10 100 1000n 10 100 10
4、00nlogn 33 664 9966n3 103 106 1092n 1024 1.27*1030 1.05*10301n！ 3628800 10158 4*102567算法理论 图 灵（ Alan Mathison Turing， 1912-1954） 数学家、 逻辑 学家、密 码 学家，被称 为计 算机科学之父、人工智能之父； 师 从数学家哈代； 二 战 中有巨大 贡 献； 图 灵机； 图 灵 奖 ： 姚期智（ 2000）7算法理论：复杂性 图 灵机与判定性 问题 ： 判定性 问题 ：用 “是 ”和 “否 ”回答的 问题 。 确定性 图 灵机； 非确定性 图 灵机；（ 带 神 谕 的 图
5、 灵机）8有限状态控制器1 1 1 1 1 10 0000 0 0B B B1 算法理论：复杂性 P 与 NP 问题 ： P：所有可以用确定性 图 灵机在多 项 式 时间 内求解的判定 问题 。 NP：所有可以用非确定性 图 灵机在多 项 式 时间 内求解的判定 问题 。 通俗定 义 ： P：存在多 项 式 时间 算法的判定 问题 。 NP：多 项 式 时间 内可以 验证 的判定 问题 。 P 属于 NP； P =？ NP 2000年巴黎法 兰 西学院宣布： 对 七个 “千僖年数学 难题 ”每一个 悬赏 一百万美元。 P =？ NP为 第一个 难题 。 9算法理论：复杂性 如何比 较难 易？ Karp归约 （ 1972）： 问题 A 多 项 式 时间 内 转 化 为问题 B 的特殊情况， 则 称 A 可多 项 式 归约 于 B， 记为 转 化 时间为 多 项 式； 对 于 A 的 输 入 I 的回答与其 对应 的 B 的 输 入 f(I) 一致； 例： TSP 归约为 整数 规 划10
