國立東華大學應用數學系

專    題    演    講

  主講人：Dr. Jed Yang

                       School of Mathematics, University of Minnesota

  講  題： Complexity of tiling by rectangles

  時  間：102 年 12 月 25 日 (星期三)  10: 30-12:00

  地  點：理工一館 A324 會議室

摘   要

Can a set of tiles (think polyominoes) tile a finite region? This decision problem is (computationally) hard in general. In the case of simply connected regions, the problem can be solved in polynomial time for some simple sets of tiles using combinatorial group theory; whereas the NP-completeness proofs rely heavily on the regions having lots of holes. In this talk, we will describe a set of rectangular tiles whose tileability problem is NP-complete for simply connected regions. If time permits, we will also discuss some tiling problems in the infinite setting.

※※※   歡      迎      參      加   ※※※se1021225

  附檔: