$30 off During Our Annual Pro Sale. View Details »
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
計算情報学研究室 (数理情報学第7研究室)紹介スライド (2025)
Search
Tomohiko Yokoyama
April 15, 2025
Education
0
1.2k
計算情報学研究室 (数理情報学第7研究室)紹介スライド (2025)
Tomohiko Yokoyama
April 15, 2025
Tweet
Share
More Decks by Tomohiko Yokoyama
See All by Tomohiko Yokoyama
The Economics of Platforms 輪読会 第1章
tomonatu8
0
240
Other Decks in Education
See All in Education
Web Architectures - Lecture 2 - Web Technologies (1019888BNR)
signer
PRO
0
3.2k
CSS3 and Responsive Web Design - Lecture 5 - Web Technologies (1019888BNR)
signer
PRO
1
3k
Ch1_-_Partie_1.pdf
bernhardsvt
0
460
Linguaxes de programación
irocho
0
490
とある長岡高専卒のおっさんがIT企業のマネージャーになるまで / journey-from-nagaoka-kosen-grad-to-it-manager
masaru_b_cl
0
160
Introdución ás redes
irocho
0
500
Présentation_1ère_Spé_2025.pdf
bernhardsvt
0
440
データで見る赤ちゃんの成長
syuchimu
0
360
RSJ2025 ランチョンセミナー 一歩ずつ世界へ:学生・若手研究者のための等身大の国際化の始め方
t_inamura
0
340
the difficulty into words
ukky86
0
300
沖ハック~のみぞうさんとハッキングチャレンジ☆~
nomizone
1
510
AIを使って最新研究 について調べて発表しよ う!
mickey_kubo
4
170
Featured
See All Featured
Why You Should Never Use an ORM
jnunemaker
PRO
60
9.6k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
359
30k
Building a Modern Day E-commerce SEO Strategy
aleyda
45
8.3k
VelocityConf: Rendering Performance Case Studies
addyosmani
333
24k
The Web Performance Landscape in 2024 [PerfNow 2024]
tammyeverts
12
970
How GitHub (no longer) Works
holman
316
140k
Intergalactic Javascript Robots from Outer Space
tanoku
273
27k
Practical Orchestrator
shlominoach
190
11k
Reflections from 52 weeks, 52 projects
jeffersonlam
355
21k
The Art of Programming - Codeland 2020
erikaheidi
56
14k
Scaling GitHub
holman
464
140k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
31
2.7k
Transcript
計算情報学研究室 (数理情報学第7研究室) 岩田 覚 谷川 眞一 五十嵐歩美
計算手法を軸とした 分野横断型研究の展開 離散最適化 連続最適化 圧縮センシング 化学情報 機械学習 エネルギー システム 線形計算
情報通信 回路・プラント シミュレーション メカニズムデザイン
離散最適化法 • 解き易い問題 (最大流問題,最小木問題) アルゴリズムの高速化 一般的な枠組 • 解き難い問題 (巡回セールスマン問題) 近似アルゴリズム
メタヒューリスティック 厳密解法 (分枝限定法,切除平面法) 劣モジュラ関数
劣モジュラ関数 • ネットワークのカット容量関数 • 行列の階数関数 • 多元情報源のエントロピー関数 ! " !
" ! " ! " ! " # ! " # ! # " # ! + " # + ! " # ! " ! ! ! ! ! " # ! ! " ! ! 有限集合
組合せ的計算幾何学 • 幾何的対象に対する計算問題を解くためのアルゴリズム基盤 – 動作計画 – 幾何的情報システム – 幾何学的モデリング(CAD) •
目標:幾何的対象に背後に潜む組合せ構造を解明したい → 効率的アルゴリズムの設計 goal
幾何的グラフ理論 • グラフの埋め込みや剛性 – タンパク質の挙動解析, 結晶構造の同定, ロボット分散制御 • 幾何的特徴を有するグラフの特徴づけ •
幾何的性質 ⇦ 代数的制約 ⇦ 凸緩和 (半正定値計画緩和など) ⇦ 組合せ論
メカニズムデザイン 7 • メカニズムデザイン: みんなが納得する妥協点を 見つけるにはどうすれば良いか – マッチング(研究室配属, 学校選択) –
投票(選挙, 市民参加型予算) – 資源配分(業務分担, 授業割当, 医療物資の配分)
メカニズムデザインとアルゴリズム 8 目標:望ましい性質を満たすメカニズム(アルゴリズム)の設計 → そのようなメカニズムを構築するための数理構造の解明 • 望ましい性質:公平性, (資源配分の)効率性, 嘘をついても 得をしない…
メカニズム 例: 劣モジュラ性を 満たす選好構造 公平かつ効率的な 資源配分
数理情報学第7研究室 h"p://www.opt.mist.i.u-tokyo.ac.jp 知性に裏付けられた楽観主義 合理性(最適性)の追求