JamGamBlog

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


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








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

正しいアルゴリズムには２つの条件が必要である。
•必ず停止する
•必ず正しい結果が得られる



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

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

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