ブラウザよりも高速アクセス！
29 関係: 契約プログラミング、並行性、一階述語論理、形式的検証、ペール・マルティン＝レーフ、ポインタ (プログラミング)、ループ不変条件、ロバート・フロイド、プログラミング言語、プロシージャ、フローチャート、ニクラウス・ヴィルト、分岐命令、命令型プログラミング、アントニー・ホーア、エドガー・ダイクストラ、カリー＝ハワード同型対応、ソフトウェア工学、公理、公理的意味論、Communicating Sequential Processes、静的コード解析、順序集合、述語変換意味論、Pascal、推論規則、構造化プログラミング、正当性 (計算機科学)、整礎関係。
契約プログラミング
契約プログラミング（けいやくプログラミング、Programming By Contract）または契約による設計（けいやくによるせっけい、Design By Contract）とは、プログラムコードの中にプログラムが満たすべき仕様についての記述を盛り込む事で設計の安全性を高める技法。プログラミング言語Eiffelで初めて導入された。"Design by Contract" の頭文字からとった DbC (ディービーシー) でよばれることが多い。.
新しい！!: ホーア論理と契約プログラミング · 続きを見る »
並行性
並行性(へいこうせい、concurrency)とは、計算機科学において、時間的にオーバーラップして実行される計算を伴うシステムの属性であり、そのような計算ではリソースを共有することがある。並行計算は、同一チップ上の複数のコア、単一プロセッサ上のプリエンプションを伴うマルチスレッド、物理的に分離した複数プロセッサ上などで行われる。並行計算のための数学的モデルとして、ペトリネット、プロセス計算、並列ランダムアクセス機械モデル、アクターモデル、 などが開発された。.
一階述語論理
一階述語論理（いっかいじゅつごろんり、first-order predicate logic）とは、個体の量化のみを許す述語論理 (predicate logic) である。述語論理とは、数理論理学における論理の数学的モデルの一つであり、命題論理を拡張したものである。個体の量化に加えて述語や関数の量化を許す述語論理を二階述語論理（にかいじゅつごろんり、second-order predicate logic）と呼ぶ。それにさらなる一般化を加えた述語論理を高階述語論理（こうかいじゅつごろんり、higher-order predicate logic）という。本項では主に一階述語論理について解説する。二階述語論理や高階述語論理についての詳細は「二階述語論理」「高階述語論理」を参照。.
新しい！!: ホーア論理と一階述語論理 · 続きを見る »
形式的検証
形式的検証（けいしきてきけんしょう）とは、ハードウェアおよびソフトウェアのシステムにおいて形式手法や数学を利用し、何らかの形式仕様記述やプロパティに照らしてシステムが正しいことを証明したり、逆に正しくないことを証明することである。.
新しい！!: ホーア論理と形式的検証 · 続きを見る »
ペール・マルティン＝レーフ
ペール・マルティン＝レーフ (Per Martin-Löf, 1942年 -) はスウェーデンの論理学者、哲学者、数学者。の創案者として知られる。２００９年までストックホルム大学数学部および哲学部教授を務めた。.
新しい！!: ホーア論理とペール・マルティン＝レーフ · 続きを見る »
ポインタ (プログラミング)
ポインタ (pointer) とは、あるオブジェクトがなんらかの論理的位置情報でアクセスできるとき、それを参照する（指し示す）ものである。有名な例としては Pascal のポインタが挙げられる。 なお、C++では、さらに独立した「参照」という機能がある。.
新しい！!: ホーア論理とポインタ (プログラミング) · 続きを見る »
ループ不変条件
ループ不変条件（Loop invariant）とは、計算機科学において、ループの不変条件のこと。ループとは、繰り返し実行されるコードのこと。ループの不変条件とは、ループ実行前にも、反復を実行するたびにも成立する条件のこと。これは、論理アサーションであり、アサーションを使ってコードが書かれることもある。不変条件を知ることは、ループの意味を知るのに重要である。 形式的検証において、特にホーア論理を使った方法では、ループ不変条件は形式的な述語論理で表現され、ループの特徴やループのアルゴリズムを証明するのに使われる。ループ不変条件はループに入る前の段階でも真であり、ループを繰り返すたびにも真である必要がある。これは、ループが終了する際には、ループ不変条件とループ終了条件の両方が真であることが保証される。 ループと再帰の基礎的な類似性により、ループ不変条件を使いループの部分的な正しさを証明するのと、再帰プログラムを構造的帰納法を使い証明するのは、非常に類似している。事実、ループ不変条件は、たいていは、ループと等価な再帰的プログラムで証明しないといけない帰納法の仮説と同じである。.
新しい！!: ホーア論理とループ不変条件 · 続きを見る »
ロバート・フロイド
バート・W・フロイド（Robert W. Floyd、1936年6月8日 - 2001年9月25日）は、アメリカ合衆国の計算機科学者。 彼の貢献としてワーシャル-フロイド法の設計がある（とはそれぞれ独立に考案）。これはグラフ理論における最短経路問題の解法のひとつである。また、数列の循環を検出するフロイドの循環検出法があり、これらは構文解析にも利用できる。また、別の論文で彼は画像描画のための誤差拡散に関する重要な概念を提案しており、これがフロイド-スタインバーグ・ディザリングとして知られている（ただしフロイド自身は誤差拡散とディザリングは区別して考えていた）。特に有名な貢献は1967年の論文 Assigning Meanings to Programs（プログラムへの意味の割り当て）である。この中でプログラム検証を数理論理学の手法を使って行うという先駆的な試みがなされている。これは後のホーア論理につながる重要な貢献となった。.
新しい！!: ホーア論理とロバート・フロイド · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: ホーア論理とプログラミング言語 · 続きを見る »
プロシージャ
プロシージャ （procedure）とは、プログラミングにおいて複数の処理を一つにまとめたものをいう。手続きとするのが定訳である。一連の処理を意味を持った一まとまりにすることで、再利用性が高まり、プログラム中に繰り返して現れる処理を1ヶ所で記述でき、プログラムの保守、管理を容易にする。 繰り返し利用されることから、ルーチンとも言う。呼び出し関係は通常階層構造をなし、その最上位にある、プログラム全体のエントリーポイントを含むルーチンをメインルーチン、呼び出されるものをサブルーチンと言う。また、関数と呼ばれることもある（通常、数学における関数とは違ったものであるので、注意が必要である）。 プログラミング言語により、プロシージャのような構文の分類や呼称はさまざまである。詳細はサブルーチンの記事を参照のこと。 Category:プログラミング言語の構文 he:שגרה ur:دستورالعمل.
新しい！!: ホーア論理とプロシージャ · 続きを見る »
フローチャート
フローチャート (flowchart、流れ図) は、プロセスの各ステップを箱で表し、流れをそれらの箱の間の矢印で表すことで、アルゴリズムやプロセスを表現する図である。アルゴリズムやプロセスについて、単にその順序だけを示すものであり、全体から詳細へというような「段階的」な説明ではない（ないし、記述者が意識してそのような階層を作る必要がある）。また、データフロー図と対比すると、より重要である、データの流れをフローチャートは表すことがなく、操作を順に示すことでデータの流れを暗示する。しかし、フローチャートは様々な分野の工程の解析・設計・文書化・管理に用いられている.
新しい！!: ホーア論理とフローチャート · 続きを見る »
ニクラウス・ヴィルト
ニクラウス・ヴィルト (Niklaus Wirth, 1934年2月15日 -)はスイスの計算機科学者。プログラミング言語Pascal、Modula-2などの開発や、ソフトウェア工学分野の開拓的研究で知られる。.
新しい！!: ホーア論理とニクラウス・ヴィルト · 続きを見る »
分岐命令
分岐命令（ぶんきめいれい）は、プロセッサの命令の一種である。ジャンプ命令ともいう。条件ジャンプ命令と無条件ジャンプ命令があり、厳密には「分岐」するのは条件ジャンプであって無条件ジャンプは「分岐」と言えないかもしれないが、特に区別しないことが多い。サブルーチン呼出や戻りの命令も分岐命令の一種とすることもある。 一般的なプロセッサでは、機械語の命令列はアドレスの昇順に逐次実行されるが、分岐命令が実行されると次に実行される命令が切り替わる。高水準言語のコンパイラは、条件文・Goto文・サブルーチンなどの制御構造から分岐命令を生成する。 分岐命令は引数として少なくともターゲットアドレスを持つ。ターゲットアドレスは、分岐命令の実行により、プログラムカウンタに代入される。 命令パイプラインが深い一方で、先読みが浅いプロセッサでは、ジャンプによりパイプラインにバブルが発生しペナルティとなる設計にならざるをえないことがある。そのペナルティを軽減するため、分岐命令の直後を「遅延スロット」と称し、そこにある命令は分岐処理の直前に実行されるものとする、遅延分岐という方式がある。MIPS、SH、SPARCなど、初期のいわゆるRISCに採用例が多いが、1986年にNECから発表されたμPD77230、1988年にTIから発表されたTMS320C30、デジタルシグナルプロセッサにも（その前から）多い。ディレイスロット（にある命令）の数は、μPD77320の場合で 1 、TMS320C30の場合で 3 であった。大多数のRISCのディレイスロットは 1 である。 パイプライン処理では命令のフェッチが重要であり、分岐予測が用いられることがある。分岐予測は失敗時のコストが大きいので、これを減らすために投機的実行などの技術が用いられる。 ARMやIA-64では、全ての命令を条件実行命令として、分岐命令の必要性を低減しパイプラインストールの可能性を低くする工夫をしている。.
新しい！!: ホーア論理と分岐命令 · 続きを見る »
命令型プログラミング
命令型プログラミング（めいれいがたプログラミング、Imperative Programming）とは、計算機科学において宣言型プログラミングの対となる概念であり、計算をプログラム状態を変化させる文の列で記述するプログラミングパラダイムの一種。自然言語の命令法がなすべき行動への指令を表現するのとよく似た方法で、命令型プログラムはコンピュータが実行すべき命令列で構成される。命令型プログラミングに従ったプログラミング言語を命令型（プログラミング）言語と呼ぶ。一般に命令型プログラミングは、手続き型プログラミングと同義として扱われる。 命令型プログラミングは、宣言型プログラミング（関数型や論理型言語など）と対照的である。Haskellなどの関数型プログラミング言語では、プログラムは文の並びではないし、命令型言語が持つような広域状態を持たない。Prologのような論理プログラミング言語では、命令型言語のように計算の「方法」をプログラムとして記述するのではなく、計算すべき「事物」を定義する。.
新しい！!: ホーア論理と命令型プログラミング · 続きを見る »
アントニー・ホーア
チャールズ・アントニー・リチャード・ホーア（Charles Antony Richard Hoare、1934年1月11日 - ）はイギリスの計算機科学者。通称はトニー・ホーア（Tony Hoare）またはC・A・R・ホーア。 クイックソート（一般的な場合には最も性能の良い実装ができるとされるソートアルゴリズム）の考案でも知られるが、専門的な業績としては、ホーア論理や、並行プロセスを形式記述するCommunicating Sequential Processes（CSP）などがある。CSPはプログラミング言語Occamに示唆を与えた。.
新しい！!: ホーア論理とアントニー・ホーア · 続きを見る »
エドガー・ダイクストラ
ドガー・ダイクストラ（Edsger Wybe Dijkstra, 1930年5月11日 - 2002年8月6日）は、オランダ人の計算機科学者。1972年、プログラミング言語の基礎研究への貢献に対してチューリング賞を受賞。構造化プログラミングの提唱者。1984年から2002年に亡くなるまでテキサス大学オースティン校の計算機科学の Schlumberger Centennial Chair を務めた。 2002年の死の直前、プログラム計算のについての仕事に対して ACM PODC Influential Paper Award を授与された。この賞は翌年からダイクストラを称えてと呼ばれるようになった。 エズガー・ダイクストラと表記されることもある。オランダ語での発音は、IPA表記で で、エツハー・ウィベ・デイクストラに近い。.
新しい！!: ホーア論理とエドガー・ダイクストラ · 続きを見る »
カリー＝ハワード同型対応
リー＝ハワード同型対応（カリー＝ハワードどうけいたいおう、Curry-Howard correspondence）とは、プログラミング言語理論と証明論において、計算機プログラムと証明との間の直接的な対応関係のことである。「プログラム＝証明」(proofs-as-programs)・「型＝命題」(formulae-as-types)などとしても知られる。これはアメリカの数学者ハスケル・カリーと論理学者ウィリアム・アルヴィン・ハワードにより最初に発見された形式論理の体系とある種の計算の体系との構文論的なアナロジーを一般化した概念である。通常はこの論理と計算の関連性はカリーとハワードに帰属される。しかしながら、このアイデアはブラウワー、ハイティング、コルモゴロフらが定式化した直観主義論理の操作的解釈の一種と関係している。 At the very beginning, the Curry–Howard correspondence is.
新しい！!: ホーア論理とカリー＝ハワード同型対応 · 続きを見る »
ソフトウェア工学
フトウェア工学（ソフトウェアこうがく、Software engineering）は、コンピュータのプログラム、およびその作成行為であるプログラミングを対象とした工学である。.
新しい！!: ホーア論理とソフトウェア工学 · 続きを見る »
公理
公理（こうり、axiom）とは、その他の命題を導きだすための前提として導入される最も基本的な仮定のことである。一つの形式体系における議論の前提として置かれる一連の公理の集まりを (axiomatic system) という 。公理を前提として演繹手続きによって導きだされる命題は定理とよばれる。多くの文脈で「公理」と同じ概念をさすものとして仮定や前提という言葉も並列して用いられている。 公理とは他の結果を導きだすための議論の前提となるべき論理的に定式化された（形式的な）言明であるにすぎず、真実であることが明らかな自明の理が採用されるとは限らない。知の体系の公理化は、いくつかの基本的でよく知られた事柄からその体系の主張が導きだせることを示すためになされることが多い。 なお、ユークリッド原論などの古典的な数学観では、最も自明（絶対的）な前提を公理、それに準じて要請される前提を公準 (postulate) として区別していた。.
公理的意味論
公理的意味論（こうりてきいみろん、Axiomatics Semantics）とは、数理論理学に基づいてプログラムの正当性を証明する手法。ホーア論理と密接に関連している。.
新しい！!: ホーア論理と公理的意味論 · 続きを見る »
Communicating Sequential Processes
Communicating Sequential Processes（CSP）とは、並行性に関するプロセス計算の理論のひとつである.
新しい！!: ホーア論理とCommunicating Sequential Processes · 続きを見る »
静的コード解析
静的コード解析 (static code analysis) または静的プログラム解析 (static program analysis)とは、コンピュータのソフトウェアの解析手法の一種であり、実行ファイルを実行することなく解析を行うこと。逆にソフトウェアを実行して行う解析を動的プログラム解析と呼ぶ。静的コード解析はソースコードに対して行われることが多く、少数ながらオブジェクトコードに対して行う場合もある。また、この用語は以下に列挙するツールを使用した解析を意味することが多い。人間が行う作業はインスペクション、コードレビューなどと呼ぶ。.
新しい！!: ホーア論理と静的コード解析 · 続きを見る »
順序集合
数学において順序集合（じゅんじょしゅうごう、ordered set）とは「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。ただし、順序集合内の2つの元, に順序関係が定まっている（「比較可能」である）必要はなく、両者が「比較不能」であってもよい。 比較不能のケースを許容していることを強調して順序集合の事を半順序集合（はんじゅんじょしゅうごう、partially ordered set, poset）ともいう。一方、半順序集合の中で比較不能のケースがないものを特に全順序集合 という。（「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である。） 全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。 一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序とみなしたものがある。例えば2元集合 において と はいずれも他方を包含していないので S の冪集合は全順序ではない。 実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。.
新しい！!: ホーア論理と順序集合 · 続きを見る »
述語変換意味論
述語変換意味論（じゅつごへんかんいみろん、Predicate Transformer Semantics）は、エドガー・ダイクストラによるホーア論理の拡張であり、その後も他の研究者が改良を加えたものである。最初に登場したのはダイクストラの論文 "Guarded commands, nondeterminacy and formal derivation of programs" であった。.
新しい！!: ホーア論理と述語変換意味論 · 続きを見る »
Pascal
Pascal（パスカル）は、ニクラウス・ヴィルトの設計（デザイン）によるコンピュータ・プログラミング言語である。ALGOL（直接的にはその一派生である、ヴィルトが関与したALGOL W）などの影響があるが、個人の設計であることに由来する簡素だがよく整った言語仕様（構文と意味）を持つ。用途の中に教育を意識しており、構造化された制御構造など、その当時「良きプログラミングの慣習」と考えられていたことの影響もある。一方で批判者からは、あくまでも教育用に過ぎない言語だ、といったような評もあることにはあったが、PascalコンパイラをPascalで書ける（いわゆる言語処理系のブートストラップ）ことをはじめ、Pascalで書かれた#実用プログラム例は多くある。名前は、哲学者・数学者・科学者で、機械式計算機を製作するなど技術者でもあったブレーズ・パスカルにあやかったものである。.
新しい！!: ホーア論理とPascal · 続きを見る »
推論規則
推論規則（すいろんきそく、rule of inference, inference rule, transformation rule）とは、論理式から他の論理式を導く推論の規則である。 記号、公理、代入規則、推論規則によって理論を形式化したものを公理系という。 公理は記号だけで記述されるが、推論規則や代入規則はこれらの記号について述べているメタ言語で記述される。 恒真式 （トートロジー）から推論規則を導くと妥当性のある推論になる。.
新しい！!: ホーア論理と推論規則 · 続きを見る »
構造化プログラミング
構造化プログラミング（こうぞうかプログラミング、structured programming）は、1960年代後半にエドガー・ダイクストラらによって提唱された、構造化されたプログラムの構成要素（制御構造）の利用や、 p.49)-->段階的詳細化などを特徴とするプログラミング手法である。.
新しい！!: ホーア論理と構造化プログラミング · 続きを見る »
正当性 (計算機科学)
計算機科学における正当性（Correctness）とは、アルゴリズムがその仕様に照らして正しいことを意味する。「機能的」正当性とは、アルゴリズムの入出力動作に関する正当性である（すなわち、各入力に対して正しく出力を生成すること）。形式的検証を参照されたい。 完全正当性（Total Correctness）は、アルゴリズムが常に停止することも要求される。一方、部分正当性（Partial Correctness）は単に返ってくる答えが正しいことのみを要求する（常に答えが返ってくるとは限らない）。停止問題には汎用的解法はないので、完全正当性はより深い問題をはらんでいる。 例えば、整数を 1 から順に調べて奇数の完全数を探すとした場合、部分正当性を備えたプログラムを書くのは極めて簡単である（素因数分解を行って n が完全数かどうかを調べる）。しかし、そのプログラムが完全正当性を備えているとするには数論において未知の知識を必要とする。 正当性の証明は数学的証明でなければならず、アルゴリズムもその仕様記述も形式的に与えられなければならない（形式的仕様記述）。特にその証明は、そのアルゴリズムを特定のマシン上でプログラムとして実装したものについて正当性を意味するものではない。その場合メモリ量の限界を考慮する必要がある。 証明論におけるカリー・ハワード対応は、直観主義論理における機能的正当性の証明がラムダ計算における特定プログラムに対応するとしている。このような証明の変換を「プログラム抽出; program extraction」と呼ぶ。.
新しい！!: ホーア論理と正当性 (計算機科学) · 続きを見る »
整礎関係
数学において、二項関係が整礎（せいそ、well-founded）であるとは、真の無限降下列をもたないことである。.
新しい！!: ホーア論理と整礎関係 · 続きを見る »
