動くおもちゃを作ろう

◆実験内容:
 自由にアイデアを出してもらって、何らかの目的を持って動くおもちゃを作ってもらいます。過去にはパソコンとつないで PIC で制御するものを作ってもらったことが多いですが、必須というわけではありません。性能や実用性は二の次でも構わないので、見る人をあっと言わせる、おもしろいおもちゃを作って下さい。
◆助手から学生へのアドバイス:
 手を動かして作業をしてみると、頭で考えていてはまったく想定できない、でも気がついてみれば当り前の問題にぶつかる、ということがよくあります。この演習では、数理情報の授業では数少ない、物を作る場面を提供しますので、このような貴重な体験ができることと思います。ぶつかった問題をどう解決するか、やわらかい頭で知恵を絞ってみて下さい。共同作業でアイデアを出し合う経験も、将来の役に立つことと思います。

ウェブグラフを用いたグラフ探索アルゴリズムの実習

◆実験内容:
 この実習は,離散手法に関する学習を行なうことを目的とします.実習では,ウェブページとリンクとをそれぞれ節点 (ノード) と辺 (エッジ) とに見立てた「ウェブグラフ」を題材とし, JavaもしくはC言語でのプログラム作成を行います.
(数理情報第七研究室と共同実験)
◆助手から学生へのアドバイス:
 日頃ウェブブラウザを用いてインターネット上の情報を閲覧していることと思います.本実験で, ウェブの構造の数理的な側面にも興味を持ってもらいたいと思います.
◆学生からのコメント:
 普段何気なく使用しているWebのグラフ構造をプログラムで抽出できることと,それをGraphvizを使用してビジュアルに表示できることに興味を持った.

数理2-平井

教員紹介

平井 広志(ひらい ひろし)
平井 広志

東京大学大学院 情報理工学系研究科
数理情報学専攻
准教授

〒113-8656 東京都文京区本郷 7-3-1 工学部 6 号館 350 号室
Tel: 03-5841-7411
Fax: 03-5841-7411

E-mail:hirai@mist.i.u-tokyo.ac.jp

[ホームページ]

略歴

2002年3月 東京大学 工学部 計数工学科 卒業
2004年3月 東京大学大学院 情報理工学系研究科 数理情報学専攻 修士課程 修了
2004年4月 京都大学 数理解析研究所 助手
2010年11月 東京大学大学院 情報理工学系研究科 数理情報学専攻 講師
2014年4月 東京大学大学院 情報理工学系研究科 数理情報学専攻 准教授

研究テーマ

離散最適化と関連する離散数学を研究している.最近のテーマは,多品種流理論である.多品種流は,ネットワークに複数の種類の異なる「フロー」が流れている状況を扱う数学モデルで,VLSI設計,交通網,インターネット等の多くの工学的諸問題に動機付けられている.多品種流問題における各種問題クラスの計算複雑度の解明やアルゴリズム設計を目標として研究を進めている.また関連して現れる有限距離空間や施設配置問題も研究している.

主な論文・著書

H. Hirai: Metric packing for K3 + K3, Combinatorica 30, (2010), 295-326.
H. Hirai: Tight spans of distances and the dual fractionality of undirected multiflow problems, Journal of Combinatorial Theory, Series B 99, (2009), 843-868.
H. Hirai: A geometric study of the split decomposition, Discrete and Computational Geometry 36, (2006), 331-361.

数理2-定兼

教員紹介

定兼 邦彦(さだかね くにひこ)
定兼 邦彦

東京大学大学院 情報理工学系研究科
数理情報学専攻
教授

〒113-8656 東京都文京区本郷 7-3-1 6号館 341号室
Tel: 03-5841-6955 内線 26955
Fax: 03-5841-6955

E-mail:sada@mist.i.u-tokyo.ac.jp

[ホームページ]

略歴

1995年3月 東京大学 理学部 情報科学科 卒業
2000年3月 東京大学大学院 理学系研究科 情報科学専攻 博士課程 修了
2000年4月 東北大学大学院 情報科学研究科 助手
2003年4月 九州大学大学院 システム情報科学研究院 助教授
2009年4月 国立情報学研究所 准教授
2014年3月 国立情報学研究所 教授
2014年4月 東京大学大学院 情報理工学系研究科 数理情報学専攻 教授

研究テーマ

・大量データ処理のためのアルゴリズムとデータ構造
・圧縮したままデータを処理できる圧縮方法,簡潔データ構造の理論と応用
・GPUなどのメニーコア環境での計算モデルとアルゴリズムの開発

主な論文・著書

Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung: Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. SIAM J. Comput. 38(6): 2162-2178 (2009)
Kunihiko Sadakane: Compressed Suffix Trees with Full Functionality. Theory Comput. Syst. 41(4): 589-607 (2007)
Kunihiko Sadakane, Gonzalo Navarro: Fully-Functional Succinct Trees. ACM Transactions on Algorithms, 10(3), Article No. 16 (2014)
定兼 邦彦.簡潔データ構造,アルゴリズム・サイエンスシリーズ,共立出版,2018.

数理情報第2研究室

離散情報学研究室(数理情報第2研究室)
– 個性を伸ばして世界を目指す –
研究室のHomePage→
定兼 邦彦
定兼 邦彦

教授
平井 広志
平井 広志

准教授
河瀬 康志
河瀬 康志

特任准教授
アルゴリズムとデータ構造
文字列,グラフ等の離散データを効率的に処理するためのアルゴリズムとデータ構造を研究しています.ビッグデータを圧縮したまま処理する簡潔データ構造や,グラフ処理を高速化する索引構造等を扱います.理論だけでなく,ゲノム情報処理,地理情報処理 等への応用も行います.
離散最適化
離散的構造を有するシステムの最適化問題をグラフ・ネットワーク・マトロイドといった離散数学理論を駆使して研究しています.これに関連して,凸性,対称性,疎性,階層構造,距離構造などの数理的構造を代数的,アルゴリズム的な視点から研究しています.実用的であり,かつ,美しい応用数学を目指しています.
グラフに基く表現による離散構造圧縮処理
巨大なデータを扱う問題や,NP困難な問題を実用的な制約下で解く技法を研究しています.特に,二分決定グラフというデータ構造を用い大規模な離散構造データを圧縮してから処理することで,高速な解の列挙や省領域な索引構築に取り組みます.