Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
計算情報学研究室 (数理情報学第7研究室)紹介スライド (2025)
Search
Tomohiko Yokoyama
April 15, 2025
Education
0
430
計算情報学研究室 (数理情報学第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
190
Other Decks in Education
See All in Education
AIの時代こそ、考える知的学習術
yum3
2
140
人になにかを教えるときに考えていること(2025-05版 / VRC-LT #18)
sksat
4
980
Case Studies and Course Review - Lecture 12 - Information Visualisation (4019538FNR)
signer
PRO
1
2k
SkimaTalk Teacher Guidelines
skimatalk
0
770k
演習問題
takenawa
0
480
Gesture-based Interaction - Lecture 6 - Next Generation User Interfaces (4018166FNR)
signer
PRO
0
1.7k
Common STIs in London: Symptoms, Risks & Prevention
medicaldental
0
130
2025年度春学期 統計学 第2回 統計資料の収集と読み方(講義前配付用) (2025. 4. 17)
akiraasano
PRO
0
130
ANS-C01_2回不合格から合格までの道程
amarelo_n24
1
210
Implicit and Cross-Device Interaction - Lecture 10 - Next Generation User Interfaces (4018166FNR)
signer
PRO
2
1.7k
2025年度春学期 統計学 第3回 クロス集計と感度・特異度,データの可視化 (2025. 4. 24)
akiraasano
PRO
0
110
技術勉強会 〜 OAuth & OIDC 入門編 / 20250528 OAuth and OIDC
oidfj
4
860
Featured
See All Featured
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
656
60k
Faster Mobile Websites
deanohume
307
31k
Building an army of robots
kneath
306
45k
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
19
1.3k
Fontdeck: Realign not Redesign
paulrobertlloyd
84
5.5k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
52
2.8k
Keith and Marios Guide to Fast Websites
keithpitt
411
22k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Understanding Cognitive Biases in Performance Measurement
bluesmoon
29
1.7k
Fantastic passwords and where to find them - at NoRuKo
philnash
51
3.2k
[RailsConf 2023] Rails as a piece of cake
palkan
55
5.6k
Transcript
計算情報学研究室 (数理情報学第7研究室) 岩田 覚 谷川 眞一 五十嵐歩美
計算手法を軸とした 分野横断型研究の展開 離散最適化 連続最適化 圧縮センシング 化学情報 機械学習 エネルギー システム 線形計算
情報通信 回路・プラント シミュレーション メカニズムデザイン
離散最適化法 • 解き易い問題 (最大流問題,最小木問題) アルゴリズムの高速化 一般的な枠組 • 解き難い問題 (巡回セールスマン問題) 近似アルゴリズム
メタヒューリスティック 厳密解法 (分枝限定法,切除平面法) 劣モジュラ関数
劣モジュラ関数 • ネットワークのカット容量関数 • 行列の階数関数 • 多元情報源のエントロピー関数 ! " !
" ! " ! " ! " # ! " # ! # " # ! + " # + ! " # ! " ! ! ! ! ! " # ! ! " ! ! 有限集合
組合せ的計算幾何学 • 幾何的対象に対する計算問題を解くためのアルゴリズム基盤 – 動作計画 – 幾何的情報システム – 幾何学的モデリング(CAD) •
目標:幾何的対象に背後に潜む組合せ構造を解明したい → 効率的アルゴリズムの設計 goal
幾何的グラフ理論 • グラフの埋め込みや剛性 – タンパク質の挙動解析, 結晶構造の同定, ロボット分散制御 • 幾何的特徴を有するグラフの特徴づけ •
幾何的性質 ⇦ 代数的制約 ⇦ 凸緩和 (半正定値計画緩和など) ⇦ 組合せ論
メカニズムデザイン 7 • メカニズムデザイン: みんなが納得する妥協点を 見つけるにはどうすれば良いか – マッチング(研究室配属, 学校選択) –
投票(選挙, 市民参加型予算) – 資源配分(業務分担, 授業割当, 医療物資の配分)
メカニズムデザインとアルゴリズム 8 目標:望ましい性質を満たすメカニズム(アルゴリズム)の設計 → そのようなメカニズムを構築するための数理構造の解明 • 望ましい性質:公平性, (資源配分の)効率性, 嘘をついても 得をしない…
メカニズム 例: 劣モジュラ性を 満たす選好構造 公平かつ効率的な 資源配分
数理情報学第7研究室 h"p://www.opt.mist.i.u-tokyo.ac.jp 知性に裏付けられた楽観主義 合理性(最適性)の追求