The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
再帰再考 : 404 Blog Not Found
2006年07月23日13:00 カテゴリLightweight Languages 再帰再考 今やこれは逆ではないか。 再帰的アルゴリズム まずは，非再帰プログラムで問題を考えてみる。 難しいと判断した場合，再帰プログラムで考えてみる。 むしろ私はこうしてきた。 まずは再帰で実装する。 速度と資源の制約があるとき、非再帰で実装しなおす 一番の理由は、今やプログラミングそのもののコストの方がプログラムを実行するコストよりも大きいからだ。早くプログラムを書く要請の方が速いプログラムを書く要請より強いからだ。 次の理由は、再帰は遅いとは限らないからだ。特にLisp系では、末尾再帰(tail recursion)は重くない。これはもうshiroさんが力説しているのでそちらを参照して欲しい。フィボナッチ数列を解くプログラムはとにかく、階乗を解くプログラムぐらいだとわざわざ再帰しないようにするご利益
再帰的アルゴリズム
このようにして３！が計算されます。 このような定義の仕方を再帰的定義と言います。 この階乗関数を Basic プログラムとして実現してみると，（Tiny Basic には階乗関数 Factorial が内蔵されていますから，実際にこのようなプログラムを書く必要はありませんが。） Function Kaijyou(n) If n = 0 then Kaijyou = 1 Else Kaijyou = Kaijyou(n-1)*n End if End Function となります。しかし，実は階乗関数は，再帰を使わなくても，次のように実現することが出来ます。 Function Kaijyou(n) F = 1 For i = 1 to n F = F * i Next i Kaijyou = F End Function このように再帰的プログ
An Algorithm for Compressing Space and Time | 3 1, 2006
An Algorithm for Compressing Space and Time By Tomas G. Rokicki, April 01, 2006 Making a slow program fast can lead to both joy and frustration. But sometimes a new approach yields amazing improvements. Making a slow program fast can lead to both joy and frustration. Frequently, the best you can do is a low-level trick to double or maybe quadruple the speed of a program; for instance, many readers
再帰呼び出しを含む手続きの処理の難しさ
: 1. はじめに The Difficulty of Using Procedures with the Recursive Call, Hajimu Hayashi (Graduate School of Education, Kyoto University) 概要: This study examined why it is difficult to use recursive processing. Kurland89 took up the recursive call of LOGO procedure and suggested that ``embedded recursion''(the recursive call was embedded in between) was more difficult than ``tail recursion''(the recur
遅延評価によるストリーム、Perl で。 : torus solutions!
SICP の 3.5 節「ストリーム」に出てきたストリームを Perl で実装してみた。 意外と簡単に書けた。 SICP のお買い上げは、アマゾンの 『計算機プログラムの構造と解釈』 のページからどうぞ〜。 概要 ストリームを使うと、 プログラムに状態変化を持ち込むことなく、 物事の変化を扱うことができるらしい。 必要な時に必要なだけの計算をするのに、 実際に計算をする部分と、 その計算された値を使う部分を完全に分離した形でコーディングできるので、 非常に強力なテクニックとなり得る。 ストリームは遅延リストとして実装するので、 まず遅延評価を実現するための手続き delay と force をそれらしく作り、 その上にストリームを構成するいくつかの関数を書いてみた。 実装 以下に、 テキストに出てきた Scheme でのコードと、 それに対応する Perl のコードを順番に載せます。 スト
デフレート圧縮(LZ77圧縮)処理の概要 - ウェブで用いられる画像形式。
PNG画像を生成するのに欠かせないデフレート圧縮(LZ77圧縮)について解説します。 デフレート圧縮とは。 デフレート圧縮は、LZ77圧縮アルゴリズムを応用したもので、圧縮技術としてはかなり旧くからあるもので、GZIP(ZLib)やZIPファイル圧縮技術などに用いられております。 デフレート圧縮は枯れた技術であり、特許問題も無い技術として知られており、この為PNG画像の基幹技術としても採用されたのです。 特許問題の無い技術とされるデフレート圧縮にも、実は特許に引掛かるアルゴリズムが存在します。しかしながら、特許問題が生じるアルゴリズムは効率を上げるためのものなので、効率が悪くても特許に触れないアルゴリズムを撰べば問題はありません。 そもそもPNG画像形式はGIF画像の基幹技術に特許問題が絡んだことに対応して策定されたもので、実際仕様書にも特許問題が生じない事の確認に長い時間を費やしたと書か
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 こんなことやって意味あるのかどうか正直言って迷いました。プログラマはたいてい知っているような内容だし見る人もいないんじゃないかと思いましたが、これからプログラミングを始めてみようという方にとっては参考になるかもしれないし、何よりも自分にとって頭の中を整理できたりするので、これから定期的にやっていこうかと考えてます。 ところで、紹介する内容はほとんど過去に出版された書物関係から抜粋しています。一応下の方に参考文献として挙げておきますので興味を持たれた方は書店などで探してみてはいかがでしょうか？ ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。
不完全性定理についてのゲーデルの証明
Up: 不完全性定理のLisp, Mathematicaによる記述 G. J. Chaitin Godel's Proof of his Incompleteness Theorem の例をMathematicaとCommon Lispで書き直した 準備運動 Mathematicaの場合 Schemeの場合（MIT Scheme） Common Lispの場合 ゲーデルの定理 Mathematicaの場合 Schemeの場合（MIT Scheme） Lispの場合 うそつきのパラドックス：「この文はうそである」 ゲーデルの定理：「この命題は証明できない」（真なのに証明できない命題がある） 準備運動 これは自分のコードを出力するプログラムの例でもある Mathematicaの場合 Mathematicaで書くともっともわかりやすいだろう。まず x -> x[x]
高度プログラミング演習（九州大学全学共通教育科目）の説明資料
実践プログラミング ＣとＣ＋＋プログラミングに関するいくつかの例題と解説． 単なるプログラミングテクニックや文法の解説ではなく， 背後にある考え方の習得（アルゴリズム，データ構造，数学など）を重視して いる． プログラムをじっくり眺めそこから技法を学び取る． 最大値 [HTML] 曜日の計算 [HTML] 平均値，分散 [HTML] 2次方程式の解 [HTML] 最小自乗法 [PPT], [HTML] 待ち行列シミュレーション [PPT], [HTML] アーランの即時式モデル [PPT], [HTML] 行列のＬＵ分解 [PPT], [HTML] ニュートン法による非線型方程式の解 [PPT], [HTML] 数値積分 [PPT], [HTML] ２分探索木 [PPT], [HTML] ヒープソート [PPT], [HTML] クイックソート [PPT], [HTML]
プログラミング言語論教材
List of Examples 1. Esoteric languages 2. Various syntax for iteration 3. An example of tokens 4. Simple grammar 5. Simple arithmetic expression 6. Parse tree of A*(B+C) 7. An example of ambiguous grammar 8. Dangling else 9. Fortran has no reserved word 10. Namespace in C++ 11. Importing a module in Python 12. TinyBASIC 13. Variable declaration in Java 14. Anonymous function in JavaScript 15. Anon
http://ocw.kyoto-u.ac.jp/jp/engineering/course07/index.htm
国際交流センター 日本語入門初級 日仏交流150周年・京都大学創立111周年国際フォーラム 国際フォーラム ビデオ→ 動画で見る京都大学 ・What is Life? The Next 100 Years of Yukawa's Dream Nishinomiya-Yukawa International & Interdisciplinary Symposium 2007 October 15(Mon)〜20(Sat) 2007 CO-OP Inn Kyoto Conference Hall →詳細 →シンポジウム詳細PDF →シンポジウム ビデオとPDF OCW関連講義 全学共通科目 生命とは何か？（村瀬雅俊准教授） 京都大学オープンコースウェア総長懇談会 日時２００７年１０月３０日(火) 場所：京大会館
『C言語による最新アルゴリズム事典』
奥村晴彦『C言語による最新アルゴリズム事典』技術評論社，1991年，ISBN4-87408-414-1，2400円 大きな画像（1.1M） 1987年10月にPascalを使った『コンピュータ・アルゴリズム事典』を，1991年2月にその改訂版としてANSI C言語を使った『C言語による最新アルゴリズム事典』を出版しました（いずれも技術評論社）。そのサポートページをつくろうと思いながら多忙のためなかなかできませんでした。とにかく始めなければ……というわけで，サポートページまがいのものを作ってみました。 石田晴久ほか『コンピュータの名著・古典100冊』（インプレス，2003年）に選んでいただきました。100冊といっても日本人の書いたものは20％しかなく，たいへん恐縮しています。 Frequently Asked Questions どの銘柄のC言語ですか？ ほぼ当時のANSI Cドラフトに基づ
Super Technique 講座〜再帰関数の技
Ｃ言語初心者が戸惑うものとして、「再帰」に関する技法がある。まあ、今時の言語で「再帰関数」を書けないのは、COBOL と FORTRAN, 古典的BASIC くらいのものだが、一般的な言語解説書での説明は大変おざなりなものである。だから、これは意識して憶えないことには、やはり身に着かない。 そこで「Super Technique 講座」では、再帰の技法を、再帰という発想の親玉である Lisp(Scheme) を利用して理解する、という無謀な企てをしてみることにする。「ある言語を理解するのに、何で別な言語を勉強するの？」という当然の疑問が湧くことだろう。しかし、しかし、「それがハッカーというものである」。筆者は MS-DOS の時代に、UNIXのテキストツールの使い方を理解するために、それらを自分で実装した。一見「無駄」に見える技術投資は、ことプログラマにとっては決して「無駄」ではない。Li
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://taweb.aichi-u.ac.jp/saitom/joho/tekisutoshori.htm
http://ews2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/
Programming Place Plus
Algorithms with Python
ウェブで用いられる画像形式について。
UNIXの楽しみ