You’re Doing It Wrong - ACM Queue
The Bike Shed June 11, 2010 Volume 8, issue 6 PDF You're Doing It Wrong Think you've mastered the art of server performance? Think again. Poul-Henning Kamp Would you believe me if I claimed that an algorithm that has been on the books as "optimal" for 46 years, which has been analyzed in excruciating detail by geniuses like Knuth and taught in all computer science courses in the world, can be opti
構文解析のオハナシを少し - 檜山正幸のキマイラ飼育記 (はてなBlog)
工作員お手伝いのショー君がid:aiue3という投げやりなIDでダイアリーを書いていたようです。http://d.hatena.ne.jp/aiue3/20061120#1164006565 のなかに再帰的下向き法（recursive decent; 再帰下降法）というのが出てくるので少し補足しておきましょう。 お馴染みの算術式（arithmetic expression）を素材にします。'+'は足し算, '*'は掛け算、そして'-'は引き算ではなくて符号反転の単項演算子とします。 式 ::= 数 | 和 | 積 | 符号反転 | '(' 式 ')' 和 ::= 式 '+' 式 積 ::= 式 '*' 式 符号反転 ::= '-' 式 これでも、構文的に正しい算術式を定義できます。しかし、3 + 5 * 2 が (3 + 5) * 2 なのか 3 + (5 * 2) なのかはわかりません。
- サルでもわかる待ち行列
(株)永和システムマネジメント 平鍋健児 作成日：初版 1999, 3/16 第2版 2002, 11/6 第3版 2004, 9/14 第4版 2008, 5/1 情報処理技術社試験の中で良く出て来る「待ち行列」理論を，直感的に覚えやすく解説してみました． 何度もトライしたけど待ち行列が理解できない人向けです． 正確な定義や論理展開は重視せず，いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました．
Gallery of Processor Cache Effects
Most of my readers will understand that cache is a fast but small type of memory that stores recently accessed memory locations. This description is reasonably accurate, but the “boring” details of how processor caches work can help a lot when trying to understand program performance. In this blog post, I will use code samples to illustrate various aspects of how caches work, and what is the impa
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
最長片道きっぷ - [2-1] 整数計画法で（準備編）
最長片道きっぷの経路を求める [2-1] 整数計画法で（準備編） あらまし LOP の最適解を求める手段として整数計画法を使うことを考えます。LOP を整数計画法の問題に置き換えることができれば、 あとはソルバーというソフトウェアが機械的に解いてくれるので、 問題をいかに整数計画法に帰着するか、 ということを考えればよいことになります。 このページでは、整数計画法と、グラフ理論のごくかんたんな用語（頂点、 枝など）について、まったく知らない人を対象にかんたんな説明をしています。 整数計画法やグラフ理論を知っている人は読み飛ばしてかまいません。 目次 問題の分析 整数計画法で 整数計画法で：準備編 整数計画法って？ ちょこっとグラフ 整数計画法で：定義編 整数計画法で：制約式編 整数計画法で：戦略編 全探索で 全探索で：導入編 全探索で：弁解編 全探索で：算法編 全探索で：分割編１ 全探索で
アルゴリズム行進こそ至高のアルゴリズムである - chokudaiのブログ
NHKで大人気の教育番組「ピタゴラスイッチ」における、アルゴリズム行進やアルゴリズム体操はあまりにも有名です。知ってる人も知らない人も、まずはこの動画を見ていただきましょう。 これが実際にNHKで放送された番組中の動画です。この動画を見ていただければ、タイトルの通りであるという説明をするまでもないとは思いますが、蛇足となることを覚悟しつつ、あえて、『なぜアルゴリズム行進が至高のアルゴリズムであるか』、その一部分を説明しようかと思います。 アルゴリズム行進から見える並列処理 皆さん、コンピュータがどう動いているかはご存知でしょうか？このブログを見てくれている方はかなり詳しく理解されている方が多いかとは思いますが、そうでない方も非常に多いのではないでしょうか？ここで少し難しい話をしますが、コンピュータの頭脳である、CPUがどのような働きをしているかを解説しようと思います。 CPUの場合 CPU
1 差分法 (Euler 法)
Chapter 1 差分法 (Euler 法) 1.1 Euler 法 物理の基本的な式はみな微分方程式です。ニュートンの運動方程式も量子力学のシュレディンガー方程式もそうです。そ れで、ここではコンピュータを使ってどうやって微分方程式を計算するのかを簡単に紹介したいと思いま す。 さて、最も簡単な形としてオイラー（Euler）法というものがあります。まずもっとも簡単な微分方程式として例え ば
MersenneTwister JavaScript Version
March 2025 (1) January 2025 (1) November 2024 (1) July 2024 (1) June 2024 (2) January 2024 (1) September 2023 (1) April 2023 (2) March 2023 (1) November 2022 (3) October 2022 (1) September 2022 (1) June 2022 (1) July 2021 (1) May 2021 (1) April 2021 (2) February 2021 (1) January 2021 (1) September 2020 (1) July 2020 (2) March 2020 (1) August 2019 (1) April 2019 (2) August 2018 (1) May 2018 (1) Apr
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
二分法 - Wikipedia
この項目では、数値解析における二分法について説明しています。ゼノンのパラドックスの二分法については「ゼノンのパラドックス」を、誤った二分法については「誤った二分法」を、論理学・哲学上の二分法（dichotomy）については「二項対立」を、数理的な二分法については「2値論理」をご覧ください。 数値解析における二分法（にぶんほう、英: bisection method）は、解を含む区間の中間点を求める操作を繰り返すことによって方程式を解く求根アルゴリズム。反復法の一種。 2分法 赤線は解の存在する範囲。この範囲を繰り返し1/2に狭めていく。 ここでは、となるを求める方法について説明する。 ととで符号が異なるような区間下限と区間上限を定める。 との中間点を求める。 の符号がと同じであればをで置き換え、と同じであればをで置き換える。 2.に戻って操作を繰り返すことにより、となるに近づく。 はとの間
Bisection method - Wikipedia
This article is about searching zeros of continuous functions. For searching a finite sorted array, see binary search algorithm. For the method of determining what software change caused a change in behavior, see Bisection (software engineering). A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function. In mathematics, the bisectio
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
みなさん、素数を数えてますか？ 『素数』は１と自分の数でしか割ることのできない孤独な数字。 暗号化できたり、乱数を作れたり、心を落ち着いたりして、私達に勇気を与えてくれます。 素数といえば「エラトステネスのふるい」ですが、あれは大きい桁の素数を生成しようとすると、とんでもなく時間が掛ります。 今回は、どんな大きな桁の素数でも高速で素数判定するプログラムを作ってみます。 基本は「フェルマーの小定理」 素数判定の基本は「フェルマーの小定理」です、数式は１行だけのごく簡単なものです。 a^(p-1) mod p の答えが1以外ならpは合成数である ただし、aとpが素の関係（最大公約数が1)であること 2つの数を「べき剰余算」して答えが1以外なら合成数(not 素数)という事です。 aに2を代入してqが素数なら答えが1になる、たったこれだけです簡単でしょ？ def is_prime(q): q =
微分方程式の数値計算（オイラー法）-数学アルゴリズム演習ノート-
数値計算による物理シミュレーションで出てくる微分方程式は、積分など解析的な方法では解くのが困難、もしくは解けない事があります。しかし、微分方程式とは言ってみれば変数の「変化」のしかたを表した方程式ですので、単純にその方程式にしたがって変数を変化させてその結果を積み重ねていけば（数値積分）、大体の様子はわかるはずですね。さらにそのように数値計算で解くのは、「計算機」たるコンピュータの最も得意とする分野とも言えるでしょう。 例えば、dy/dx=2x、x=1でy=1という微分方程式があったとします。これは積分すれば解析的にも簡単に解けます（y=x2)が、初期値を入れた後、y をdy/dx=2x に従って変化させていっても大体の値は求まるわけです。まず、x=1でのyは1で傾きはその時点でのx*2の値,すなわち2です。これを使ってx=1.1でのyを求めてみましょう。 すでに傾きがわかっているので、x
修正オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれに修正オイラー法を適用して解いていきます。 #include <stdio.h> double f1(double x,double v); double f2(double x,double v); int main() { double t,dt,x,v,tmax; double k0[2],k1[2]; dt=0.01; //刻み幅設定 x=1.0; //位置初期値 v=0.0; //速度初期値 tmax=100; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); fprintf(output,"%f %f\n",x,v); for(t=0;t<tmax;t+=dt) { k0[0]=f1(x,v); k0[1]=f2(x,v); k1[0]
オイラー法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにオイラー法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double x,v,t,dt,tmax; double k0[2]; FILE *output; output=fopen("output.data","w"); /*初期値*/ x=1.0; v=0.0; dt=0.01; tmax=100; for(t=0.0;t<=tmax;t+=dt) { k0[0]=dt*f1(t,x,v); k0[1]=dt*f2(t,x,v); x=x+k0[0]; v=v+k0[1]; fprintf(output,"%f
ルンゲクッタ法
vは速度です。常微分方程式が2つ出てきましたが難しいことはありません。それぞれにルンゲクッタ法を適用して解いていきます。 #include <stdio.h> double f1(double t,double x,double v); double f2(double t,double x,double v); int main() { double t,x,v,dt,tmax; double k1[2],k2[2],k3[2],k4[2]; x=1.0; //位置の初期値 v=0.0; //速度の初期値 dt=0.01; //刻み幅 tmax=500.0; //繰り返し最大回数 FILE *output; output=fopen("output.data","w"); for(t=0;t<tmax;t+=dt) { k1[0]=dt*f1(t,x,v); k1[1]=dt*f2(t,
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
2分探索木を通りがけ順になぞる並列アルゴリズム | CiNii Research
Documentation - Chaos Help
Filtering In PRMan