【投稿日】2018.02.28
共催: | 知の創出センター TFC Fusion Research Seminar |
---|---|
日時: | 2018年2月15日㈭ 16:30–17:30 |
場所: | 片平キャンパス 知の館 (TOKYO ELECTRON House of Creativity) 3階 |
備考: | 情報科学研究科研究科重点プロジェクト「数学と諸分野の協働推進による学際的・総合的な新領域研究の開拓」第20回講演会を兼ねています。 |
16:30–17:30
浦本 武雄 氏 (東北大学大学院情報科学研究科)
計算階層の分類と、その圏論的見方
例えば11010の様なバイナリ列が与えられ、それを2進数と見たときに、それが合成数か否かを判定するアルゴリズムは勿論ありますが、そのアルゴリズムはどの程度まで効率化することができるでしょうか?あるいは原理的にこれ以上効率化できないという限界を見極めるにはどうすれば良いでしょうか?———この種の、文字列を入力として受け取り一定の性質を判定する問題及びその計算量を見積もる問題は多くの文脈で自然に現れる問題ですが、形式的には文字列の集合(言語)の組合せ論的な問題として定式化されます。形式言語理論と呼ばれる分野では古くから、この様な組合せ論的な問題に対する研究が行われてきましたが、近年、あるクラスの言語に対する見通しの良い分類理論が整備され研究が進んでいます。本講演では、文字列に対する判定アルゴリズムの話から始め、その問題のクラスの良い分類を目指す過程で、いかにして数学の一分野である「圏論」が使われるのかについて、自身の研究を踏まえてお話しします。