「アルゴリズムとデータ構造」とはについてのメモ。
アルゴリズムとは
アルゴリズムは問題を解決する手順のことです。
まつもと直伝 プログラミングのオキテ 第1回（2） | 日経 xTECH（クロステック）
厳密な定義
アルゴリズム - Wikipedia
1920〜30年代、アルゴリズムの概念を定式化するための数学モデル（計算モデル）がいくつも提案された（チューリングマシン、帰納的関数、λ計算など）。後にこれらの定義はすべて同等であることがわかり、チる手順のことです。
厳密な定義
アルゴリズム - Wikipedia
1920〜30年代、アルゴリズムの概念を定式化するための数学モデル（計算モデル）がいくつも提案された（チューリングマシン、帰納的関数、λ計算など）。後にこれらの定義はすべて同等であることがわかり、チャーチはこれらの同値な概念をアルゴリズムと考えることを提案した（チャーチの提唱）。したがって、現在では、チューリング機械の状態遷移図（またはそれと等価なもの）をアルゴリズムと呼ぶ。
アルゴリズムイントロダクション 第1巻 数学的基礎とデータ構造 P.5
アルゴリズム(algorithm)は、ある値または値の集合を入力(input)とし、ある値または値の集合を出力(output)する、明確に定義された(well-defined)計算手続きである
それでは、アルゴリズムとはなにか、方法である。それも、「愛情をこめて」とか「気合いで」とかという、解釈が曖昧で誰でも実行できるとは限らない、昨今巷にあふれている「〜の技術」という本に書かれた「技術」ではなく、「その方法を一つ一つ愚直にたどれば、必ずその問題が解決する」という方法である。だからアルゴリズムは計算機でなくても役に立つ。が、曖昧さを許さない、しかし愚直に実行する機械である計算機と相性が抜群だということは、アルゴリズムという言葉を知らない人でも直感的に理解できるだろう。
その意味で、アルゴリズムは一生ものだ。いや、一生ものどころかその寿命は半永久的。互除法のように数千年前に見つかって(Euclidよりに前に見つかっていたのは確実)、今でも実地で使われているものも少なくない。それに比べれば、電脳言語ですら刹那的であり、極論してしまえば言語も単にアルゴリズムを清書するための道具に過ぎない。
404 Blog Not Found:書評 - アルゴリズム・サイエンス (入口|出口)からの超入門
アルゴリズムという呼び方の由来
「アルゴリズム」という名称は、現在のイラクのバグダードにおける9世紀の数学者アル・フワーリズミー の名前から来ているといわれている。825年に書かれた彼の著作『インドの数の計算法』が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorum アルゴリトミ・デ・ヌーメロ・インドルム』（直訳すると「インドの数におけるアルゴリトミ」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭に「Algoritmi dicti（アル・フワリズミーに曰く）」という一節があるので『Algoritmi（アルゴリトミ）』と呼ばれていた。
アルゴリズム - Wikipedia
アルゴリズムとデータ構造
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)
P.149
アルゴリズムの本などを見ると、アルゴリズムとデータ構造は、アルゴリズム+データ構造のようにセットで扱われることがよくあります。データ構造は、配列、木構造のように、対象とするデータを保持するまたは表現するための構造のことです。
データ構造とアルゴリズムがセットで論じられるのは、アルゴリズムでよく使う操作に合わせてデータ構造を選ぶ必要があるからです。たとえば、あらかじめ適切な木構造でデータを保持しておくと、多くの場合探索処理が単純化できて、計算量を下げることができます。
RDBMSのインデックスの実装にはB+木という木構造がよく使われているというのはLesson11で見ましたね。B+木は二次記憶上に木構造を配置するのに空間的にも適した構造です。B+木でインデックスを保持しておくと、探索に伴うステップ数も少なく抑えつつ、ディスクの読み出し回数も最小化できる…という特性があります。このようにRDBMSのインデックスではB+木を採用しつつ、そのデータ構造に合わせたアルゴリズムで探索・挿入・ソートなどを行うのが普通です。
このように、アルゴリズムとデータ構造は切っても切れない関係にあります。
データ構造（データこうぞう、英: data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。
ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。
多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。データ構造が選択されれば、使用するアルゴリズムは自明であることが比較的多いが、逆の場合もある。いずれにしても適切なデータ構造の選択は極めて重要である。
データ構造 - Wikipedia
