sasanqua_neuf - チューリング完全性 -
本稿では，sasanqua_neufのチューリング完全性を証明します．具体的には，チューリングマシンのエミュレータを構成することでチューリング完全性を示します． 概要 sasanqua_neufのテープTをチューリングマシンのテープと「概ね」同一視し，チューリングマシンの状態をCの値によって「概ね」表現します．C言語風にエミュレータの概要を記すと，全体の構造としては int Cq=1; while(Cq != n+1){ switch(Cq){ case 1: //qの添え字が1 switch(T[H]){ //T[H]にσが格納されている case 1: //σの添え字が1 T[H] = [δ_2(q_1,σ_1)]; //T[H]をテープと同一視 H += [δ_3(q_1,σ_1)]; //ただしLeft=-1,Right=+1と見て while(T[H] == 0){getchar
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
有限要素法(FEM)のページ
有限要素法(FEM)は偏微分方程式を解いたり力学解析をする上で非常に強力な方法です。 何十年にもわたり様々な研究が精力的になされ、この手法は目まぐるしく発展してきました。 しかし大企業の開発者や大学の研究者など、ごく一部の限られた人以外はその恩恵を被ることができないのが現状です。 誰でも簡単に有限要素法を理解して使えるようになることに少しでも役に立つことを、 このWebページを通じて目指しています。
誤り訂正符号Blog
2025 . 07 « 12345678910111213141516171819202122232425262728293031» 2025 . 09 前回までで、リードソロモン符号の符号化・復号の方法を一通り示すことができました。 ”「ちょっと誤り訂正符号を使ってみたいな」という実務家の皆さん向けに、非常に簡易に誤り訂正符号の原理・アルゴリズムについて説明する”ということを目的に作成された本ブログですが、いかがだったでしょうか。 多分に説明不足な点がありますが、「多項式の符号化・復号→多項式の係数を有限に制限したものとしてのリードソロモン符号」という流れは、自然で原理を理解しやすくて、もう少し肉付けして書けばなかなか良いのではないかと勝手に思っています。 しかし説明不足感は否めません。 何も知らずにこれを読んでリードソロモン符号をコーディングすることができた方がいましたら、すばらしい読
素数判定 - あどけない話
要約：素数判定に使われるミラーラビン法を解説しながら、Haskell で実装してみる。 フェルマーテスト 大きな数を確実に素数だと判定するには、大変時間がかかるので、実用的には「ほぼ素数だ」と確率的に判定する。確率的な素数判定の代表格がフェルマーテストである。 フェルマーテストには、以下に示すフェルマーの小定理を利用する。 a^p ≡ a (mod p) a は任意の整数。p は素数である。法 p の下で a を p 乗したものは、a と合同であると言う意味だ。a には制限はないが、特に a を p より小さい整数、0 ≦ a ≦ p - 1 とすれば、a を p 乗して、p で割ると a に戻るとも解釈できる。 最初に見たときは、だからどうしたと思われるかもしれない。しかし、有名なフェルマーの大定理が実用上何の役にも立たないのに対し、フェルマーの小定理はいろんな場面で活躍する。 実際に計
ベジエ曲線を整数の加減算だけで描画する方法 - Studio RAIN's diary
だいぶ前にちらっと書いたことがあるのだが、かれこれ 20 年ほど前に、ベジエ曲線を整数の加減算だけで描画する方法を考えたことがある。こういう会社員時代の仕事を紹介するためには、いろいろと制約があったりするのだが、このアルゴリズムは多分守秘義務には含まれていないし、技術自体がいい加減時代遅れの技術で、多分今はもっといい方法が開発されているはずなので、公開してもどこからも文句は来ないと思う。だから、機会があればいつか紹介したいと思っていた。 だだ、このアルゴリズムを説明するには、ややこしい数式を並べる必要があって、それが面倒で避けていたところもあった。しかし、今回 Maxima を使って計算したら、わりと簡単に再現できたので、せっかくだから記録にとどめておくことにする。 ベジエ曲線というのは、空間からいくつかの点を選択したときに、その点との関係で定義される。たとえば、２次のベジエ曲線だったら、
ベイズ理論 - yasuhisa's blog
同時確率、条件付き確率からベイジアンアップデートまで。パラメトリック、ノンパラメトリック(データサイズが増えるにつれて、パラメータ数が対数オーダーで増える)のところは初めてだとたぶんわけわからないところで、ちょっと前で説明してみたけど、若干でしゃばりすぎた気がする。どうするべきかちょっと迷うところではある。難しい。 ベイジアンな考え方は、自分もちゃんと理解するまで3ヶ月はかかったので(パラメータの事前分布ってなんですか!!とか)、今日初めてという人はたぶんわけわからなかったかもなーと(宗教なので、最初は受け入れ難いものなんですよ、きっと)。コインの例のやつは、自分も最初よく分からなかったので、Rで事後分布がupdateされていく様子とかをRで書いたりしていました。 ベイズの事後分布と事後予測分布を出してみた - Seeking for my unique color. FSNLPの例は分か
「言語処理のための機械学習入門」を参考に各種モデルに対するEMアルゴリズムを実装したよ - nokunoの日記
Amazonにもレビューを書いたのですが、高村さんの「言語処理のための機械学習入門」を読みました。実はこの本を読むのは2回目で、1回目はドラフト版のレビューをさせていただく機会があったのですが、そのときは「言語処理研究者のための機械学習入門」というタイトルで、ちょっと敷居が高いのではないかとコメントしたら「研究者」の部分が削られたという経緯があったりしました。 それはともかくとして、以前読んだときは時間もなくて実装までする暇はなかったのですが、今度はもうちょっとじっくり読みたいなということで、このブログに書いてみようと思います。EMアルゴリズムは教師なし学習を確率モデルと最尤推定でやろうとするときに必ず出てくる手法で、隠れ変数や欠損値を含む色々なモデルに適用できる汎用的なフレームワークになっています。一般的には混合ガウス分布の場合をまず説明して、それがk-means法の一般化した形になって
紫ログ:GaucheでR風に行列演算を記述する - livedoor Blog（ブログ）
【C.M.ビショップ「パターン認識と機械学習(PRML)」読書会の情報はこちら】 行列に関する操作は、R をマスターする基本です。関連する Tips を脈絡なくできるだけ集めたいと思います。お気づきの正統派・裏技テクニックをお寄せください。一部重複はむしろ好ましいと思います。 PRMLに出てくるアルゴリズムを実装するには行列演算が書きやすくないと辛いので、Rの記法を参考にしながら試行錯誤中。 夢見ている書式仕様 matrix(): 要素ベクトルを与えて行列を作る： matrix(1:12, nrow=3, ncol=4) → (%matrix (iota 12 1) :nrow 3 :ncol 4) → (%matrix (%: 1 12) :nrow 3 :ncol 4) matrix(1:12, nrow=3) # 自動的に ncol=4 とされる → (%matrix (%: 1 1
紫ログ:PRML: §1.1 多項式曲線フィッティング - livedoor Blog（ブログ）
【C.M.ビショップ「パターン認識と機械学習(PRML)」読書会の情報はこちら】 Rを参考にして書いた、Gaucheで行列演算を記述するためのオレオレライブラリを使い、１章の最初の多項式曲線フィッティングから復習コーディング中。 訓練データ集合（sin(2πx) + ガウス分布ノイズ）と元の曲線: 次数M=0〜9でフィッティング: 次数M=9、N=15とN=100の比較: 次数M=9、ペナルティ項つき: ソース: (require "./lib/random") (require "./lib/util") (require "./lib/gd-graph") (require "./lib/mac") (require "./lib/matrix") ;; [0..1]の範囲で均一に分布する乱数 (define rand-0to1 (make-uniform-rand 0 1)) ;;
準ニュートン法 - Wolfram Mathematica Documentation Center
上記の経路でまず目に付くのはこれが間違った方向に向かって始まっている点である．最初のステップではすべての方法がその勾配に従わなければならないために，最急降下のこの方向が選ばれたのである．しかし，後続のステップでは，ヘッセ行列の近似モデルの構築のために取られたステップにおける関数値および勾配値からの情報が組込まれている． Mathematica は，BFGS (Broyden-Fletcher-Goldfarb-Shanno)更新法を使い，大規模システムでは，メモリ節約型のL-BFGS法を使う．L-BFGS法ではモデル Bk は明示的には保存されず，過去のステップから保存された勾配とステップ方向によって Bk-1f (xk)が計算される． 大規模で疎な問題の場合，BFGS法には少々問題がある．一般にコレスキー因子（あるいはヘッセ行列の近似 Bk またはその逆行列）は密なので，O (n2)のメ
フォードファルカーソン法をRubyで実装 - yasuhisa's blog
グラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。 繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。 # -*- coding: utf-8 -*- require "pp" class DirectedGraph attr_reader :nodes attr_reader :weights attr_reader :edges
情報と通信のハイパーテキスト
Home 「情報と通信のハイパーテキスト」 は下記へ移動しました。 http://www.mnc.toho-u.ac.jp/v-lab/
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
2009年3月2日に、はてな京都オフィスで開催された アルゴリズムイントロダクション輪講 の第12回で「動的計画法」について発表しました。資料をここにおいておきます。View more presentations from nitoyon.分かりやすくしようと気合を入れてまとめたら165ページの大作になっちゃいました。無駄に長くてすいません。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)作者: T.コルメン, R.リベスト, C.シュタイン, C.ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一出版社/メーカー: 近代科学社発売日: 2007/03メディア: 単行本
CS 294-5, Spring 2006 : Great Algorithms
CS 294-5, Spring 2006 Great Algorithms Instructor: Richard Karp (karp AT cs, M 1:30-2:30, 621 Soda Hall, 642-5799) Lectures MW 10:30-12:00, 310 Soda Announcements Course Overview Lecture notes Assignments Announcements announcements go here.. Course Overview From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application b
Support Vector Machine
人間には卓越した学習能力が備わっている．人間は目で見たり，耳で聞いたものが何であるかをいとも簡単に認識できる．また，未知の環境に適応する能力も優れている．それに対し，コンピュータは，与えられた指示（プログラム）どおりに高速に計算を行う能力においては優れているが，学習能力という点においては，人間とは比較にならない． そこで，人間のような学習能力をもった機械（モデル）を作るための学習理論が発達してきた．その代表的な成果の1つとして，多層パーセプトロンが挙げられる．多層パーセプトロンは1980年代に開発され，これまで多方面に応用されてきた．しかし，望ましくない局所最適解への収束，中間層の素子数の選択など，いくつかの問題点がある． サポートベクターマシン(Support Vector Machine:SVM) は，このような問題を解決した学習機械として知られている．サポートベクターマシンとは，1
連載：はじめMath! Javaでコンピュータ数学｜gihyo.jp … 技術評論社
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
イプシロン計算ってなんですかぁ？ こんなもんですよぉ - 檜山正幸のキマイラ飼育記 (はてなBlog)
ラムダ計算は、計算モデルとしてだけでなく、手計算の実際的手段としても役立ちます。しかし、通常使われる各種変換（アルファ、ベータ、イータ、デルタ）ではうまく計算が進まないときがあります。例えば、gがfの逆関数のとき、f(g(y)) は y に簡約されるのだけど、f(g(y)) ⇒ y って簡約規則は通常のラムダ計算ではうまく定式化できません（いや、できるかもしれませんが、僕にはうまい方法が思いつきません）。 そこで、ラムダ計算に加えてイプシロン計算も使うとよさそうです。でも、イプシロン計算は、ラムダ計算ほどにポピュラーではないですね。簡単な例でイプシロン計算を紹介しましょう。 内容： イプシロン記号とイプシロン項 イプシロン項の意味 イプシロン項が定義する関数 例題：gがfの断面（セクション）であること イプシロン記号とイプシロン項 負の数-1とか、無理数√2とかを導入するとき、次のような定
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://www.mech.tohoku-gakuin.ac.jp/rde/contents/course/controlII/digicont.html