プログラムの実行モデル

Last updated Unknown Edit Source

• プログラムについて、立てれる問い

  • あるプログラムは、絶対にプログラムBより早く終了するか
  • あるプログラムは絶対に答えを出力するか
  • 等

• これらを実験（実際に実行）するのではなく、数学的モデルを作って証明しよう、という分野

• 考え方としては、いわゆる疑似コードに近い

  • 「プログラムの実行」を抽象化する

• 何が嬉しい?

  • いろんな問いに答えられる
  • あるプログラムAとBは同じ結果を常に出すか
    • これが分かると、コンパイラの最適化の安全性が証明できる
    • 実行モデルは抽象化たりないみたいな話もあるけど、あるグラフ式ならいけるかも?
  • 時間コスト/空間コストの分析
    • こっちのほうが実行モデルは得意と言われている

#情報科学