推移律はいらない? ─比較ソートの正当性に必要な比較関数の性質─ - λx. x K S K ＠はてな
この記事は Theorem Prover Advent Calendar 2013 最終日 (25日目)*1の記事です． 元々このネタは， 後学期の3年生向けの実験でCoqを教える際に提示した 「挿入ソートの正当性を示す」という最終課題の模範解答を作成する際に気づいたことです． このため，ここで紹介するプログラムや証明は， タクティクの種類やライブラリの利用が必要最低限に絞られているので， もしかしたら Coq 初心者の方にも参考になるかもしれません (各タクティクの作用を明確に理解してもらうため，敢えて auto も使いませんでした)． Coq 上級者には冗長な証明が気になるかもしれませんが，その点は予めご了承ください． はじめに 比較関数を利用して整列するアルゴリズムは比較ソートと呼ばれ， クイックソートやマージソートをはじめとする多くの整列アルゴリズムがこれに属します (逆に比較ソー
ProofCafe - 名古屋を中心に活動する定理証明器・関数型言語のコミュニティ
開催勉強会 ProofCafeではいくつかの勉強会を定期開催しています。 詳細は個別のページをご覧ください。 Coqを用いたプログラムの証明について勉強する勉強会です。 コーヒーを飲みながら楽しく証明しましょう。 TAPL-nagoya Types and Programming Laungages(通称TAPL)の読書会です。 ScalaやF#などの静的型付け言語の基礎になっている型理論について学びます。 休日カフェタイム, KCTNagoya 圏論に関する勉強会です。 どえりゃあ Haskell Haskellに関する勉強会です。 サービス Software Foundations(和訳) Benjamin C. Pierce氏による同名のテキストの和訳です。関数プ ログラミグやラムダ計算についてCoqによる実例を交えながら丁寧 に説明されています。 Cochin Coqの定理検索サー
後半は発表大会。 - dominion525の日記
csnagoya | 03:08 | GC関連のネタを仕込んできてくれたのが4名。CoqでGCを証明してみたよ(id:mzpさん）Proove Mark&Sweep GC with CoqView more presentations from mzpi.Coq、定理証明器ですよ。夢の「バグのないGC」の実現ですよ！ ただぼくはまだCoqの入り口にすらも触れていないので正しく理解していないわけで、最低限雰囲気がわかる程度には知っておきたいなあと思う次第です。iPhone/iPadのメモリ管理 （id:sunflatさん）iPhone and iPad Memory ManagementView more presentations from sunflat.うわー面倒くさそうだなぁObjective-C。なんでGC対応しないんだろ？性能的に超高速というわけじゃないiPhoneではリアルタイ
証明してみた。 - 菊やんの雑記帳
http://d.hatena.ne.jp/m-hiyama/20100629/1277774676 を証明してみた。 とりあえず、問題設定 Axiom A : Set. Axiom A_eq_dec: forall a b: A, { a = b } + { a <> b }. Axiom A_mul : A -> A -> A. Axiom A_zero: A. Axiom A_one: A. Infix "*" := A_mul. Notation "0" := A_zero. Notation "1" := A_one. Axiom A_mul_assoc: forall a b c, (a * b) * c = a * (b * c). Axiom A_mul_comm: forall a b, a * b = b * a. Axiom A_mul_1_r: forall a,
日本語の Coq 情報 - まめめも
ついでに、主に日本語の Coq 情報を (10 分で思い出せる範囲で) まとめてみます。順不同。 公式に近い情報 本家 Coq'Art (Coq の教科書) Cocorico! (本家 Coq wiki) CiteSeer (笑) Coq のことをまとめようとしている wiki 菊さんの Coq wiki Tossy-2 の Coq wiki たまに Coq のことが書いてあるブログ yoshihiro503 さんのブログ (LL 魂で Coq の発表をされた方、Coq の話ばっかり) いまいけいごさんのブログ 菊さんのブログ Tossy-2 のブログ あろはさんのブログ (2006/04 〜 05 頃) 他にもちらほら見かけるはずなのですが、ちゃんとメモしてなかったので思い出せません。見つけたら自発的に適宜追加するかもしれませんが、教えてもらえると助かります。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
イベントレポート：「ProofSummit2011」
http://proofcafe.org/
ProofSummit2011(仮題) - [PARTAKE]
anarchy proof -