Download presentation
Presentation is loading. Please wait.
1
ACM/ICPC と アルゴリズム speech @ 「実践的プログラミング」 稲葉 一浩
2
自己紹介 ﻪ 理Ⅰ → 理学部情報科学科 → 情報理工学系研究科コンピュータ科学専攻 ﻩ 博士課程１年 ﻩXML を扱う専用言語の研究など ﻪ 個人的には ﻩhttp://www.kmonos.net/ ﻯD 言語 ﻯC++. Boost ﻪACM/ICPC 歴 ﻩ2003 [Lighthouse] ビバリーヒルズ大会 (11 位 ) ﻩ2004 [Gokuri] ソウル予選、会津予選で敗退 ﻩ2005 [Gokuri-Squeeze] 上海大会（惨敗 orz ）
3
「アルゴリズム」とは ﻪ アルゴリズム (algorithm) は、なんらか の問題を解くための手順のことである。 算法（さんぽう）と訳されることもあ る。 -- Wikipedia より ﻪ 例 ﻩ なんらかの問題 ： 整列（ sorting ） ﻩ アルゴリズム ： クイックソート、バケツ ソート,...
4
発表の内容 ﻪ どういう問題を解くアルゴリズ ムを 知っているとよいのか！？ ﻪ どういう問題を解くアルゴリズ ムは 知らなくてもいいのか！？
5
「 NP 完全問題」 ﻪNP 問題 ﻩ 「答えがあってるかのチェック」は簡単な問題 ﻯSorting とか ﻪNP 困難問題 ﻩ どんな NP 問題よりも、それ以上に「難しい」問題 ﻯ 「この問題が効率よく解ければ他のどんな NP 問題も解け る」 とわかっている問題 ﻪNP 完全問題 : NP かつ NP 困難 ﻩNP 問題の中で一番「難しい」問題
6
「 NP 完全問題」 ﻪICPC などでも、よく出題される ﻪ でも、 NP 完全問題を効率よく解く アルゴリズムは、まだ誰も発見していない ﻩ もちろん ICPC の出題者も！ ﻪ うまい解き方が思いつかなくても問題なし ﻩ 「 NP 完全問題だ」と気づいたら、 なんの工夫もないプログラムで突撃して OK! ﻩ そういう風に入力が作ってあるはず
7
「 NP 完全問題」の例 ﻪ 巡回セールスマン問題 ﻪ ハミルトン経路問題 ﻪ 集合分割問題 ﻪ 最大クリーク問題 ﻪ ナップザック問題
8
Traveling Salesperson Problem ﻪ 入力：都市間の移動にかかる時間 ﻪ 出力：全ての都市を巡って戻ってくる最短 経路
9
Hamiltonian Path ﻪ 入力：点と辺でできた図形（グラフ） ﻪ 出力：全点を一度ずつ通るような経路 「ひとふでがき」 とはちょっと違う
10
Partition ﻪ 入力：数の集合 ﻪ 出力：和が丁度半分になるように分けられ る？ {1.2, 3.4, 5.6, 5.3, 0.9, 3.5} ただし、 数の集合が「小さい整数」と わかっているときは、 効率よく解ける。（ DP ）
11
Maximum Clique ﻪ 入力：グラフ ﻪ 出力：どの２点も辺でつながってるよ うな 頂点集合の最大サイズ
12
Knapsack Problem ﻪ 入力：荷物（重さ、価値） ﻪ 出力：重量制限を満たす 範囲でできるだけ 価値を増やす荷物の 選び方
13
そのほか ﻪGoogle “ NP 完全 ” ﻪWikipedia “ NP 完全 ”
14
実際に出た問題 ﻪ2005 F ( 巡回セールスマン問題 ) ﻪ2003 E ( 最適配置問題 ) ﻪ2002 D (Hit & Blow) ﻪ...
15
おまけ ﻪ 知っているとよいアルゴリズム ﻩ グラフ理論 ﻯ 『データ構造とアルゴリズム』 培 風館 エイホ、ウルマン、ホップクロフ ト ﻯ 『アルゴリズム C++ 』 近代科学社 セジウィック ﻩ 図形問題 ﻯ 高校の数学の教科書
Similar presentations
