形式化基础 ·难”的形式化表达 ·图灵机模型 ·七元组各元素之间的关系、状态转移函数 ·确定性图灵机、非确定性图灵机 ·语言、判定、优化问题 ·问题和语言的关系 ·如何形式化定义判定问题、优化问题？ ·常见的判定/优化问题的形式模型 ·优化问题的M集合、c0st函数分别代表什么意思？ ·P、NP、NPC(H)、NPO ·上述概念的基本意义及其关系 ·如何证明某个问题的难”：归约！形式化基础 • “难”的形式化表达 • 图灵机模型 • 七元组各元素之间的关系、状态转移函数 • 确定性图灵机、非确定性图灵机 • 语言、判定、优化问题 • 问题和语言的关系 • 如何形式化定义判定问题、优化问题？ • 常见的判定/优化问题的形式模型 • 优化问题的M集合、cost函数分别代表什么意思？ • P、NP、NPC(H)、NPO • 上述概念的基本意义及其关系 • 如何证明某个问题的“难”：归约！