アルゴリズムについて
会社の同期2人と持ち回りで定期的に課外活動をしています。
そのログを書き連ねたものを公開することにしました。
テーマはアルゴリズムについてです。
以下、当日のログです。
私(sasaki_hm)の発言：
・本日の進行の説明
①アルゴリズムの例題を解いてみよう
・一斉射撃問題
・長方形の重なり問題
②「NP困難」の事例紹介
・なぜアルゴリズムを勉強しているか
・目標に対する課題という位置づけでアルゴリズムの勉強があることを説明
・読んでいる本、取り組みの紹介
・「思考する機械」
・「エンジニアとしての生き方」
Y氏の発言：
・アルゴリズムを勉強することの意味を再確認する
・自身も以前取り組んでいたことがあることを紹介
・代替案をサジェストする
・TopCoderのこと
・高橋直大のweb pageのこと
・他人のコードを読むことの有用性
n_haretsu(以下N氏)の発言:
Y氏：「今日の例題は、アルゴリズム分野の全体の中ではどういう位置づけになるの？」
私：「位置づけはあまり気にしてなかった。一問目が有限状態機械に関する問題、二問目が図形に関する問題。NP困難の事例がグラフに関する問題。」
Y氏：「図形とグラフは性質としては同じじゃないの？」
私：「まぁ、そうかも」
Y氏：「有限状態機械って、有限オートマトンのことだっけ」
私：「そう」
Y・N氏：「有限オートマトンって何だっけ」
私：「（本を見せながら）こういう、フローチャートみたいに状態遷移を図示できる系のこと」
・・・（略）という感じで、三人ともコンピュータサイエンスの基礎がちょっと怪しいことが露呈する。
その後、ブルーオーシャン・レッドーオーシャンの話に。
私：「多分、コンピュータサイエンスをしっかり理解出来てる人って、そうそう居ないんだと思う。」
N氏：「情報系がメインの会社だったら、しっかり理解出来てる人もたくさん居るんじゃない? でもそういうとこで勝負するのは結構大変だろうなぁ。それに対して情報系の分野に弱い会社の場合、ある程度の理解であってもまだ手がつけられてない問題があったりして活躍できたりするよね。」
私：「でもそれって難しい問題で、短期的に見た時にはそれで良くても、長期的に見ると自分のためにならなかったりするよね。
ブルーオーシャンでの活躍を選ぶのか、レッドオーシャンでの競争を選ぶのか、みたいな話だけど。」
私：「最近は、どっちがどうとうとかあんまり気にせず、やりたいことやるのが一番かなって思うけど。」
Y氏：「そうだね。」
＜出題＞
例題①：一斉射撃問題
・問：以下の条件において、横一列に並んだ兵隊に一斉射撃させよ。
・各兵隊に声が届くまでには距離毎に時間差がある。このため「射撃せよ」と発声するだけでは一斉射撃とならない。
・並びの兵士の後ろでは一定時間間隔で太鼓が鳴っている。兵隊は隣の兵隊に情報を伝えることができる。
・出典：思考する機械
例題②：長方形の重なり問題
・問：平面空間において、２つの長方形が重なっているかどうかを判定する方法を答えよ。
・出典：エンジニアとしての生き方
Y・N：・・・熟考、解答が出揃う
以下、二人の思考過程。
＜NP困難について＞
・Sが現在勉強中であるNP困難の事例として巡回セールスマン問題を紹介する。
・Nさんが巡回セールスマン問題を遺伝的アルゴリズムで解く例を解説する。
