アルゴリズムイントロダクションとは
世界標準MIT教科書
大学などで情報処理を専門に学ぶが読む本
私は現在エンジニアとして働いているが、教育機関で訓練を受けたわけではないので、
このあたりの知識が不足しているので読んでみてます。
本書で紹介されているアルゴリズムはGithubにGo言語で実装しています。
リポジトリはこちら
ペースもゆっくりですが、マイペースに勉強進めていきます。
#本記事の目的
アルゴリズムイントロダクションでは練習問題が記載されていますが、
模範回答が見つからないのでQiitaに投稿すればレビューしてもらえるのでは！？
と思い、投稿してみます。
皆様の知恵と知識をお貸し頂けますと幸いです。
また、これを機に一緒に勉強したい、自分も基礎から計算機科学を勉強したい、という人が出てくると嬉しいです。
ちなみに私の回答は間違っている可能性が高いので、そのあたりはご了承頂きたく。
#練習問題1
第一章は具体的なアルゴリズムの話ではないのですが、
じっくり考えると意外と難しいですね。
##1.1-1
ソートを必要とする実社会での応用あるいは凸包を必要とする実社会での応用を説明せよ。
ソートはまあいいとして、凸包は初めて聞きました。
凸包-wikipedia
こんな感じで与えられた要素(画像の場合は点)を全て内包する最小の凸多角形のことらしいです。
これらの点が釘の場合、輪ゴムを引っ掛けると凸包の形になります。
回答
ソート-図書館の本の陳列
凸包-CG処理(ポリゴングラフィック)
昔の3Dゲームのグラフィックは3次元の凸包の組み合わせで表現されているように見えます。
(FF7の戦闘シーンとか、そんな感じ)
ソートは色んな所で使われている気がしますが、例で出した図書館で言うと、本とかがソートされずにどこにあるかわかんない！ってなったら借りるほうも困るし、図書館で本を管理する人たちも困りますよね。
##1.1-2
実社会の枠組みの中で用いられる計算速度以外の効率の尺度をあげよ。
回答
メモリ使用量、データ転送量
省メモリなアルゴリズム
無駄なI/Oのないアルゴリズムを心がけたいです。
##1.1-3
以前に見たことのあるデータ構造についてその長所と短所を挙げよ
回答
データ構造-配列
長所-検索が高速。O(1)
短所-要素の挿入、削除が遅い。挿入or削除した分、メモリのアドレスをずらさなければならない。
逆に連結リストの場合は
長所-検索が遅い。1番目に格納されているデータからポインタをたどる必要がある
短所-要素の挿入、削除が高速。挿入、削除した前後のデータのポインタを変更すれば良い。
##1.1-4
最短経路問題、巡回セールスマン問題の類似点と違いについて述べよ。
巡回セールスマン問題-wikipedia
最短経路問題-wikipedia
回答
複数のルートから距離が最短となるものを選択する、という点が類似点。
違いは巡回セールスマン問題は全てのノードを通る必要があるが、
最短経路問題はスタートとゴールのみが決められていて、他のノードは必ずしも通る必要がない。
##1.1-5
最適解しか意味を持たない実社会の問題を示せ。また近似解で意味を持つ場合の問題も示せ。
回答
電子商取引の暗号化複合化は最適解でないと意味がない。(暗証番号盗まれたなどのアルゴリズム以外の原因を除いて、本人だと証明出来なければ意味がない。)
トラックのドライバーが荷物を運ぶ最短ルートを計算する問題は現実的な計算時間で、ある程度効率的なルートが判明するのであれば問題ない。
次回
次回は1.2の練習問題解いていきます！！！