はてなＱより あなたが一番好きなアルゴリズム
⇒あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな
2 回答者：hakob 2007-11-25 10:33:37
クイックソートが好きです。
異様に件数が多い対象の整列に、いかに高速であるかを身をもって思い知りました。
（ヒープソートはメモリが足りないです。。。）
で、ホーア先生を思い出す。ご存命。
⇒アントニー・ホーア - Wikipedia
チャールズ・アントニー・リチャード・ホーア卿（Sir Charles Antony Richard Hoare、もしくはトニー・ホーア（Tony Hoare）, 1934年1月11日-）はイギリスの計算機科学者。1960年にクイックソートを開発したことで最もよく知られる。これは世界で最も広く使われているソートアルゴリズムであり、恐らくあらゆる種類のアルゴリズムの中でも、世界で最も広く使われているものであろう。
少し変わった経歴。
彼はスリランカのコロンボにてイギリス人の両親の元に生まれた。1956年にオックスフォード大学にて古典文学の学士号を取得。 その後オックスフォード大に１年残って大学院相当の統計学を学び、そしてロシアにて自然言語の機械翻訳について研究を始める。
ALGOL60の実装。作成ではなかったか。
1960年、エリオット・ブラザーズ社という小さなコンピュータ製造会社にて仕事を始め、ここでALGOL60を実装、各種アルゴリズムの開発に本格的に着手する。
ほいで。
彼はまたホーア論理や、形式言語の１つで並行プロセス間の通信を記述するのに使われるCommunicating Sequential Process（CSP）の開発、またプログラミング言語Occamに示唆を与えた事でも知られる。
CSPの説明がウィキペディアにはないや。あはは。嘲笑ではなくて、書く人いないのかな。これじゃミッシングリングみたいだ。
と思いきや⇒アクターモデル - Wikipedia
メッセージパッシング意味論
アクターモデルはメッセージパッシングの意味論でもある。
無制限の非決定性に関する議論
最初の並行プログラムは割り込みハンドラであった。コンピュータは通常処理の最中に外部（キーボード、ネットワークなど）からの情報を受け取る必要が生じた。そこで、情報が到着すると、コンピュータは割り込まれ、割り込みハンドラと呼ばれる特別なコードが呼び出されて情報をバッファに取り込み、逐次的に処理できるようにする。
これが「通信する逐次プロセス; Communicating Sequential Processes」というパラダイムの始まりであり、この並行プログラムは、バッファを使って同期的に通信した逐次プログラムを並列に並べたものであった。共有メモリを伴う並列性は並行性制御という問題を生じた。元々は、これは1つのコンピュータ上の排他制御の一種であると考えられていた。相互排他問題を解決するため、最初にエドガー・ダイクストラがセマフォを開発し、アントニー・ホーア[1974]と Per Brinch Hansen がモニタを開発した。しかし、これらの解決策は共有リソースへのアクセスをカプセル化するプログラミング言語構文には採用されなかった。カプセル化は後にシリアライザという構文で実現された（[Hewitt and Atkinson 1979]、[Atkinson 1980]）。
初期の計算モデル（チューリングマシン、ラムダ計算など）は数学に基づいており、状態によって計算「ステップ」を表現した。各計算ステップは、ある状態から別の状態への遷移である。このような状態遷移的手法は、非決定性のものを含む有限状態機械などのオートマタ理論へと発展していった。非決定性オートマトンには有限の非決定性があり、マシンが初期状態から動作開始したとき常に停止するなら、停止するときの状態数は有限である。
懐かしいな。ほとんど忘れちゃったな。
