形式化基础-算法正确性 ·循环算法正确性证明 ·什么是循环不变式？ ·循环不变式一般设置在哪里？ ·如何确定”循环不变式？ ·解空间或者问题空间搜索过程中的不变特性！和问题有关、和结论有关！ ·如何证明循环不变式？ ·数学归纳法的隐式应用」 ·递归算法的正确性证明 ·数学归纳法 ·如何分析递归算法正确性的定理”？ ·若干典型案例！汉诺塔算法、欧几里得算法等
形式化基础-算法正确性 • 循环算法正确性证明 • 什么是循环不变式? • 循环不变式一般设置在哪里？ • 如何“确定”循环不变式？ • 解空间或者问题空间搜索过程中的不变特性！和问题有关、和结论有关！ • 如何证明循环不变式？ • 数学归纳法的隐式应用！ • 递归算法的正确性证明 • 数学归纳法 • 如何分析递归算法正确性的“定理”？ • 若干典型案例！汉诺塔算法、欧几里得算法等
形式化基础 ·难”的形式化表达 ·图灵机模型 ·七元组各元素之间的关系、状态转移函数 ·确定性图灵机、非确定性图灵机 ·语言、判定、优化问题 ·问题和语言的关系 ·如何形式化定义判定问题、优化问题？ ·常见的判定/优化问题的形式模型 ·优化问题的M集合、c0st函数分别代表什么意思？ ·P、NP、NPC(H)、NPO ·上述概念的基本意义及其关系 ·如何证明某个问题的难”：归约！
形式化基础 • “难”的形式化表达 • 图灵机模型 • 七元组各元素之间的关系、状态转移函数 • 确定性图灵机、非确定性图灵机 • 语言、判定、优化问题 • 问题和语言的关系 • 如何形式化定义判定问题、优化问题？ • 常见的判定/优化问题的形式模型 • 优化问题的M集合、cost函数分别代表什么意思？ • P、NP、NPC(H)、NPO • 上述概念的基本意义及其关系 • 如何证明某个问题的“难”：归约！