【独習】正しいアルゴリズムとは何か?

what_is_correctness_algorithm

正しいアルゴリズムとは何かを理解しているだろうか。

アルゴリズムについては、過去記事から理解していることだろう。
では、そのアルゴリズムが正しいアルゴリズムかどうかの説明ができるだろうか。
今回は、正しいアルゴリズムの説明を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

広告

正しいアルゴリズムとはなにか?

正しいアルゴリズムには2つの条件が必要である。

  • 必ず停止する
  • 必ず正しい結果が得られる



この2つの条件が満たされた状態を
「完全正当性」という。

一方で、正しい結果が得られるが、停止しないこともある状態は
「部分正当性」という。

そして、正しいかはわからないが、必ず停止する状態を
「停止性」という。

完全正当性(Total Correctness)は、アルゴリズムが常に停止することも要求される。一方、部分正当性(Partial Correctness)は単に返ってくる答えが正しいことのみを要求する(常に答えが返ってくるとは限らない)。
(Wikipediaよりより)


正しいアルゴリズムとはなにかを説明してください。

さて、先程の説明を読んだ人は、正しいアルゴリズムとはなにかを説明できますね。
条件があったはずです。覚えてますか?

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。


じゃあね〜〜〜。