[B! アルゴリズム][数学] skypenguinsのブックマーク

skypenguins id:skypenguins

アルゴリズムと数学に関するskypenguinsのブックマーク (8)

竹内関数 - Wikipedia
竹内関数︵たけうちかんすう︶は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。概要[編集] 再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。特に変わる所は無いがLisp版[1]も参照のこと。定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数[2]、たらい関数 (Tarai function) とも呼ばれる︵後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある︶。電電公社研究員︵当時︶の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである[3]。竹内関数と命名したのは野崎昭弘である[4]。特性として、他のよくベンチ
skypenguins 2023/02/05
アルゴリズム

数学
リンク
アルゴリズムの世界地図 - Qiita
0. アルゴリズムとは？まず、アルゴリズムとは何かを説明します。︵0 節の説明はスライド﹁50分で学ぶアルゴリズム﹂の説明を参考にして書きました︶さて、次の問題を考えてみましょう。問題‥ 1 + 2 + 3 + … + 100 の値を計算してください。単純な方法として、式の通りに1つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。これで答え 5050 が正しく求まりました。これはれっきとしたアルゴリズムであり、この問題を99回の足し算で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。ここで、方法を変えて、﹁1 + 100﹂﹁2 + 99﹂﹁3 + 98﹂…﹁50 + 51﹂の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。50個の
skypenguins 2021/12/24
アルゴリズム

数学

プログラミング

競プロ
リンク
アルゴリズムと数学の本を書きました - E869120's Blog
1. はじめにこんにちは、はじめまして。東京大学1年生の米田優峻︵E869120︶と申します。私は競技プログラミングが趣味で、AtCoder や国際情報オリンピックなどの大会に出場しています1。2021 年11月時点で、AtCoder では赤色︵レッドコーダー︶です。また、2020 年以降、アルゴリズムを学べる以下のようなコンテンツや資料を作成してきました。レッドコーダーが教える、競プロ上達ガイドライン競プロ典型90問50分で学ぶアルゴリズムさて、このたびは技術評論社から、書籍を出版させていただくことになりました2。アルゴリズムと数学が同時に学べる新しい入門書です。﹁アルゴリズム×数学﹂が基礎からしっかり身につく本 - amazon 発売日は今年のクリスマス、2021/12/25 です。電子書籍版も同時期に出る予定です。本記事では、この本の内容と想定読者について、
skypenguins 2021/12/03
螺旋本とけんちょん本が同レベル帯にあるというのが初耳だった

アルゴリズム

数学

プログラミング
リンク
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました．その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました．最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1．さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました．今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
skypenguins 2021/07/03
量子コンピュータ

数学

アルゴリズム
リンク
高速逆平方根(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 - WikipediaC言語のコード高速逆平方根の関数を示します。0x5F375
skypenguins 2021/02/10
アルゴリズム

数学
リンク
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
skypenguins 2019/12/22
アルゴリズム

数学

代数学

動的計画法
リンク
確率的勾配降下法のメリットについて考えてみた
機械学習初心者です。機械学習やディープラーニングでは、﹁確率的勾配降下法﹂というアルゴリズムがよく出てきますが、そのメリットがいまいちピンとこなかったので考えてみました。素人のポエムなのでトンチンカンなこと書いていると思います︵そこそこ長いよ！︶。二次関数の最小値全てはここから始まります。今回の確率的勾配降下法も、それのもととなった最急降下法も全てこれの応用です。例‥$ y=x^2-4x$ の最小値とそのときの$x$を求めなさい参考‥二次関数の最大値，最小値の2通りの求め方数学的解法︵1︶～平方完成～高校数学でおなじみ︵？︶の平方完成をします。 $$y = (x^2-4x+4)-4 = (x-2)^2-4 $$ したがって、x=2のときに最小値-4です。簡単ですね。しかし、次数や次元が増えていくと簡単に平方完成できなくなります。もう少し一般的に使える方法を考えます。数学的解
skypenguins 2019/02/17
最適化

数学

機械学習

アルゴリズム
リンク
P≠NP問題がざっくり理解できる本 - hiroyukikojima’s blog
＊　追記(6月27日)　最後の紹介した﹁約数ゲーム﹂について、メールで解答を教えてくれた人がいたので、最後に追加しました。最近、野崎昭弘﹃﹁P≠NP﹂問題﹄ブルーバックスを読んだので、レビューをエントリーしようと思う。そもそも、この本を読もうと思ったのは、ある雑誌の企画で﹁数学の未解決問題﹂について、ある数学者と討論をすることになっていたのがきっかけだった。ミレニアム問題のいくつかが話題にのぼりそうなので、P≠NP問題についても少し知識を補充しておこうと思ったのだ。でも、アマゾンのレビューで酷評されているのを読んで、いくぶん躊躇した。それで、少し時間が空いたけど、本屋で立ち読みしてみて、その場で購入した。少なくともぼくには、アマゾンのレビューはミス・ディレクションにすぎないものだとわかった。買って帰って、速攻で読了したが、ぼくの要求にかなった本であった。アマゾンのレビュー欄は、まあ、
skypenguins 2016/06/27
P≠NP問題は「容疑者Xの献身」の小説で知りました…(小声)

アルゴリズム

コンピュータ

数学
リンク
1