博力學術論壇計通學院分論壇|徐超：結合字符支配規則和消解原理最大可滿足性問題的（理論）算法研究
發布時間: 2021-11-20 20:55:22 瀏覽量:
2021年11月20日下午15:00，計算機與通信工程學院的徐超老師受邀作主題為“結合字符支配規則和消解原理最大可滿足性問題的（理論）算法研究”的學術報告。本次報告會在云塘校區理科樓B-311舉行，由學院研究生會主席王蓉同學主持，部分計通學院老師、2019級和2020級研究生參加了報告會。
會議伊始，王蓉同學簡單介紹了徐超老師的個人簡介，并對徐超老師的到來表示熱烈歡迎。隨后，他重點從領域背景、MaxSAT問題(理論)算法框架、前期研究成果、消解原理結合字符支配規則、MAXSAT精確算法等五個層面進行相關介紹。首先，徐超老師以NP問題為出發點，再由此引入最大可滿足性問題以及強指數時間猜想，與強指數時間猜想相對應，消解原理是可滿足性問題求解中的一種著名且有效的不基于分支搜索的技術。基于以上分析，徐超老師介紹了?種“理想且完美”的最大可滿足性問題算法框架：重復、消解、核?化。之后，他又圍繞上述問題介紹了自己的一些前期研究成果以及消解原理在字符?配規則中的應用。最后，徐超老師還介紹了MaxSAT精確算法，它是一種最?可滿?性問題精確算法改進，其時間復雜度上界O*(1.2989m)，而在此之前最好的理論算法時間復雜度上界為O*(1.3248m)。
最終，本次講座在雷動的掌聲中結束。徐超老師在作報告的過程中思路清晰，邏輯嚴謹，匯報有序，在場的老師和同學也認真聽講，學習新的研究思想，開拓視野，增進知識。這場學術報告提高了同學們對優化算法的認知，活躍了計算機與通信工程學院的學術氣氛。
（圖/姚佳藝 文/余秋林 審/易亭亭）
