Início » 澳門理工大學研究團隊解開高德納經典數學迷題

澳門理工大學研究團隊解開高德納經典數學迷題

澳門理工大學研究團隊成功解開由著名電腦科學家高德納(Donald Knuth)於2011年提出的經典數學迷題。研究成果成功入選全球計算機科學領域頂級學術會議—ACM-SIAM離散算法研討會(SODA 2026),填補了圖論與組合算法領域的空白,展現澳理大的卓越科研實力。

澳門平台

澳理大校長嚴肇基及應用科學學院院長林燦堂的指導下,副教授黃智謙聯同計算機應用技術博士研究生柳博文組成的研究團隊,提出首個完全圖生成樹的樞軸格雷碼(Pivot Gray code for spanning trees of complete graphs),成功解答了高德納於經典巨著《電腦程式設計藝術》(The Art of Computer Programming)提出的公開習題─「有沒有簡單的格雷碼把完全圖 K_n 的所有 n^{n-2} 個生成樹列出來?」。該習題被評為難度46分(滿分50),被視為圖論與組合算法領域最具挑戰性的謎題之一。

澳理大研究團隊設計了一種簡單高效的遞歸算法,其特點是列出的每兩個相鄰生成樹之間僅有一條邊發生變化,成功生成完全圖生成樹的格雷碼。同時,研究團隊提出了一種嶄新的方式來證明Cayley公式(即完全圖的生成樹數量為n^(n-2))。研究成果具創新性與實用價值,更入選計算機科學領域頂級學術會議SODA 2026,充分彰顯澳理大科研實力的國際化水平。

ACM-SIAM離散算法研討會(SODA, ACM-SIAM Symposium on Discrete Algorithms)由計算機協會(ACM, Association for Computing Machinery)與工業與應用數學學會(SIAM, Society for Industrial and Applied Mathematics)聯合主辦,是全球計算機科學與離散算法領域最具聲望的頂級學術會議之一,被中國計算機學會(CCF)評定為A類會議、CORE評為A*類會議,是理論計算機科學領域最具影響力的學術盛會之一。該會議歷年來匯聚眾多圖靈獎得主參與,彰顯其在學術界的崇高地位。

相關報導:澳理大與科英布拉大學啟動數智人文科研合作

澳理大應用科學學院積極推動人工智能技術發展,開設電腦學理學士學位課程、人工智能理學士學位課程、大數據與物聯網碩士課程、環境智能碩士課程、運動科技與創新碩士課程、計算機應用技術博士學位課程、人工智能藥物發現博士學位課程、教育技術與創新博士學位課程,構建本碩博全人才的培養模式。開展多項科技、環境科學、醫學、教育、運動等領域的跨學科交叉融合,推動科研創新,為全球科學發展作出貢獻。

Tags:

聯絡我們

平台媒體,聚焦中葡關係。

平台編輯部

關於我們

電子報

訂閱平台電子報,縱觀全球新聞

© 2025 – Copyright Plataforma Media.

Uh-oh! It looks like you're using an ad blocker.

Our website relies on ads to provide free content and sustain our operations. By turning off your ad blocker, you help support us and ensure we can continue offering valuable content without any cost to you.

We truly appreciate your understanding and support. Thank you for considering disabling your ad blocker for this website