竹内関数 - Wikipedia
竹内関数（たけうちかんすう）は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。 概要[編集] 再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。 特に変わる所は無いがLisp版[1]も参照のこと。定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数[2]、たらい関数 (Tarai function) とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。電電公社研究員（当時）の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである[3]。竹内関数と命名したのは野崎昭弘である[4]。 特性として、他のよくベンチ
アルゴリズムの世界地図 - Qiita
0. アルゴリズムとは？ まず、アルゴリズムとは何かを説明します。（0 節の説明はスライド「50 分で学ぶアルゴリズム」 の説明を参考にして書きました） さて、次の問題を考えてみましょう。 問題： 1 + 2 + 3 + … + 100 の値を計算してください。 単純な方法として、式の通りに 1 つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。 これで答え 5050 が正しく求まりました。これはれっきとした アルゴリズム であり、この問題を 99 回の足し算 で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。 ここで、方法を変えて、「1 + 100」「2 + 99」「3 + 98」…「50 + 51」の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。 50 個の
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめに こんにちは、はじめまして。東京大学 1 年生の米田優峻（E869120）と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年 11 月時点で、AtCoder では赤色（レッドコーダー）です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。 レッドコーダーが教える、競プロ上達ガイドライン 競プロ典型 90 問 50 分で学ぶアルゴリズム さて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。 「アルゴリズム×数学」が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録
高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
確率的勾配降下法のメリットについて考えてみた
機械学習初心者です。機械学習やディープラーニングでは、「確率的勾配降下法」というアルゴリズムがよく出てきますが、そのメリットがいまいちピンとこなかったので考えてみました。素人のポエムなのでトンチンカンなこと書いていると思います（そこそこ長いよ！）。 二次関数の最小値 全てはここから始まります。今回の確率的勾配降下法も、それのもととなった最急降下法も全てこれの応用です。 例：$ y=x^2-4x$ の最小値とそのときの$x$を求めなさい 参考：二次関数の最大値，最小値の2通りの求め方 数学的解法（１）～平方完成～ 高校数学でおなじみ（？）の平方完成をします。 $$y = (x^2-4x+4)-4 = (x-2)^2-4 $$ したがって、x=2のときに最小値-4です。簡単ですね。 しかし、次数や次元が増えていくと簡単に平方完成できなくなります。もう少し一般的に使える方法を考えます。 数学的解
P≠NP問題がざっくり理解できる本 - hiroyukikojima’s blog
＊ 追記(6月27日) 最後の紹介した「約数ゲーム」について、メールで解答を教えてくれた人がいたので、最後に追加しました。 最近、野崎昭弘『「P≠NP」問題』ブルーバックスを読んだので、レビューをエントリーしようと思う。 そもそも、この本を読もうと思ったのは、ある雑誌の企画で「数学の未解決問題」について、ある数学者と討論をすることになっていたのがきっかけだった。ミレニアム問題のいくつかが話題にのぼりそうなので、P≠NP問題についても少し知識を補充しておこうと思ったのだ。 でも、アマゾンのレビューで酷評されているのを読んで、いくぶん躊躇した。それで、少し時間が空いたけど、本屋で立ち読みしてみて、その場で購入した。少なくともぼくには、アマゾンのレビューはミス・ディレクションにすぎないものだとわかった。買って帰って、速攻で読了したが、ぼくの要求にかなった本であった。アマゾンのレビュー欄は、まあ、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
