著者

森畑 明昌

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.29, no.1, pp.1_147-1_158, 2012-01-26 (Released:2012-02-26)

被引用文献数

1

---

正規表現はスクリプト言語などで広く使われているが,既存の処理系の多くはバックトラックを用いてこのマッチング処理を実装しており,最悪時の効率が悪い.実用的な様々な拡張を加えた正規表現に対するマッチングアルゴリズム,特に,文字列置換等の用途で用いられる「部分マッチの取り出し」を行えるアルゴリズムが望まれる.本論文では多くの処理系で利用可能な「先読み・否定先読み」をもつ正規表現の有限状態オートマトンへの変換を示す.まず,先読み・否定先読みを持つ大きさmの正規表現を状態数O(22m)の決定的有限オートマトンに変換する手法を示す.次に,部分マッチの取り出しを扱うため,重み付き正規表現を議論する.そして先読み・否定先読みを持つ大きさmの重み付き正規表現を状態数O(22m)の重み付き非決定的有限オートマトンに変換する手法を示す.これらのオートマトンにより効率の良いマッチングを達成できる.

著者

森畑 明昌

雑誌

情報処理

巻号頁・発行日

vol.57, no.6, pp.544-549, 2016-05-15

---

自動プログラム作成とは,入出力例などの補助的な情報から,プログラムを自動的に生成する技術である.古来非常に難しいものだとされてきた自動プログラム作成だが,近年著しい進展を見せ,実用的なシステムが作られるようになってきている.理由としては,(1)ライブラリ関数をいくつか呼ぶだけというような,小さなプログラムが多数必要になったこと,(2)計算機による力ずくの探索が可能になってきたこと,(3)学習や自然言語処理などによりユーザの意図をより正確に推測できるようになってきたこと,などが挙げられる.本稿では最新の研究成果を紹介し,もって自動プログラム作成技術が現在どの水準に達しつつあるのかを示す.

著者

森畑 明昌

雑誌

情報処理

巻号頁・発行日

vol.57, no.4, pp.362-365, 2016-03-15

---

東京大学の1年生は全員,まず夏学期に必修講義である「情報」で情報に関する基本的な知識を学ぶ.理系の学生は,続く冬学期の「アルゴリズム入門」で,プログラミングをさらに学び,アルゴリズムや計算量,数値計算等についての理解を深める.東京大学は総合大学であるため,これらの全学教育では,情報系に興味のない学生にも,プログラミングを学び,面白さを感じてもらわなければならない.しかも,「情報」では履修者が数千人(数十クラス)にも達するため,プログラミングが専門ではない教員も授業を担当せざるを得ない.本稿では,これらの困難を解決するための工夫を中心に,東京大学での全学プログラミング教育の理念と現状について報告する.