新南威尔士大学COMP6741课程大纲总结

新南威尔士大学COMP6741课程着重于精确解决NP难计算问题的算法。由于对于这些问题中的任何一个都没有已知的多项式时间算法，所以算法的运行时间将对输入大小或输入的一些其他参数具有超多项式依赖性。新南威尔士大学COMP6741课程大纲总结如下。

一、新南威尔士大学COMP6741课程概述

考虑到解决一个实例的难度可能不仅取决于其大小n，每个实例都与参数k相关联。参数化复杂度框架旨在为可计算函数f设计固定参数算法，其运行时间为f(k)*poly(n)。这为通过分支、颜色编码和内核化(预处理)等技术获得的小参数值提供了有效的算法。课程还研究了一些问题，这些问题不是固定参数可处理的，也不是基于复杂度理论假设的多项式核可内核化的。重点在于这种算法的设计和最坏情况分析，特别是通过测量与征服方法的分支算法。课程还探讨了算法的下限，以及如何在(强)指数时间假设下排除某些运行时间。

二、新南威尔士大学COMP6741课程成果

1、使用各种算法方法设计和分析NP难问题的非平凡指数时间算法。

2、假设(强)指数时间假设，证明某些问题不能在次指数时间或比特定指数时间界限更快的时间内解决。

3、使用各种算法方法为NP难问题设计参数化算法。

4、证明问题的某些参数化不是固定参数可处理的，除非FPT=W[1]。

三、新南威尔士大学COMP6741课程主题

1、NP完全性综述

2、内核化；近似算法；(整数)线性规划

3、内核化；参数化复杂性基础

4、参数化难题

5、分支算法

6、树宽

7、随机化算法；迭代压缩

8、指数时间假说

9、启发式和局部搜索

以上就是新南威尔士大学COMP6741课程大纲总结。若有同学在学习COMP6741的过程中遇到难题，随时都可以联系我们，我们能及时根据同学的学习情况来安排新南威尔士大学课程辅导帮助。