第1章 導入 (6～54 ページ) 第2章 P 対 NP 問題の定義 (55～90 ページ) 第3章 P=NP の場合にわかること (91～111 ページ) 第4章 P≠NP の場合にわかること (112～226 ページ) 第5章 まとめ (227～234 ページ)
90 分で学ぶ P 対 NP 問題
第1章 導入 (6～54 ページ) 第2章 P 対 NP 問題の定義 (55～90 ページ) 第3章 P=NP の場合にわかること (91～111 ページ) 第4章 P≠NP の場合にわかること (112～226 ページ) 第5章 まとめ (227～234 ページ)
線形代数学+Rustで画像圧縮のアルゴリズムを実装する - Qiita
こんにちは👋 長く暑い夏が終わろうとしている今ですが、筆者は秋の季節を満喫しております。 LabBaseでは線形代数学の基礎を使って検索エンジンを構築していますが、レコメンド、検索アルゴリズムによく使われる王道の手法について記事を書くことにしました。 概要 線形代数学の特異値分解（SVD）の知識を活かして、原始的な画像圧縮アルゴリズムをRustで実装します。 SVDとは？ SVDは、線形代数学でよく使われる行列の分解です。行列の分解は、同じマトリックスを他のマトリックスに分けて表現することです。SVDの他に、LU三角分解、QR分解などがあります。 SVDは、あるAというマトリックスの列空間と行空間の固有ベクトルを計算して、それぞれをUとVというマトリックスに収めます。さらに、Σという対角行列に、固有値の平方根を入れます。Vの転置行列をV'と定義しますが、以下の分解になります。 Σの体格行
統計学で用いる行列演算の小技 - Qiita
はじめに 千葉大学・株式会社Nospareの川久保です．今回は，統計学（特に多変量解析）で多く出てくる行列演算の小技集を，線形回帰モデルにおける簡単な実用例を交えて紹介します． 転置に関する公式 行列の転置とは，$(i,j)$要素を$(j,i)$要素に入れ替えることです．$m$行$n$列の行列$A$の$(i,j)$要素を$a_{ij} \ (i=1,\dots,m; j=1,\dots,n)$とすると，$A$を転置した$n$行$m$列の行列$A^\top$の$(j,i)$要素が$a_{ij}$となります．また，自明ですが，転置行列の転置は元の行列になります．すなわち，$(A^\top)^\top = A$です． 行列の和の転置 行列$A$と$B$の和の転置は，転置行列の和です．つまり， が成り立ちます． 行列の積の転置 次に，行列$A$と$B$の積$AB$の転置としては，以下の公式が成り立
【JS体操】JavaScript で頭の体操をしよう！〜第1問 44文字 解説編〜 - KAYAC Engineers' Blog
こんにちは！カヤック面白プロデュース事業部のおばらです。 普段は受託案件、特にインタラクティブな WebGL や Canvas2D を駆使する案件のデザイン＆実装を担当しています。 先日出題したJS体操 第1問目、挑戦してくださったみなさまありがとうございました！ 早速ですが最短文字数の回答は 44文字 でした！ export default x=>x-(x%=.2)+.2-(.04-x*x)**.5 みごと44文字を達成した方は、 halwhite さん koyama41 さん sugyan さん tkihira さん たつけん さん の5名！（※ Unicode コードポイント順） おめでとうございます！！ 最短文字数を狙った正統派の回答以外にも、裏技的な面白アプローチがたくさんありました笑 このアプローチは面白い、ぜひ紹介したい！という回答がいくつかあったので、解説記事は2回に分けて
楕円曲線暗号の（比較的理解しやすい）入門書
楕円曲線暗号（ECC）は、今日広く使用されている暗号の中でも最も強力で、最も理解されていないタイプの1つです。Cloudflareでは、お客様のHTTPS接続からデータセンター間のデータの送信方法まで、ECCを幅広く活用しています。 基本的には、セキュリティシステムの背後にある技術を理解し、信頼できることが重要であると信じています。そのために、ユーザーと共有するために、ECCに関する優れた、比較的分かりやすい入門書を探しました。しかし、みつけることができなかったので、入門書を自分たちで作ることにしました。それが、この入門書です。 注意：これは、複雑な主題でブログ記事一つに要約することはできません。つまり、カバーすることがたくさんあるため長くなりますので、腰を据えて読んでみてください。要点だけが必要な方のために、要約は「ECCは次世代の公開鍵暗号であり、現在理解されている数学に基づいて、RS
激ムズ数え上げパズルと驚きの解法
この動画は3Blue1Brownの動画を東京大学の学生有志団体が翻訳・再編集し公式ライセンスのもと公開しているものです。 チャンネル登録と高評価をよろしくお願いいたします。 関連するこちらの動画もどうぞ 畳み込みの仕組み | Convolution https://youtu.be/CHx6uHnWErY 日本語版Twitter https://twitter.com/3B1BJP 元チャンネル（英語） https://www.youtube.com/c/3blue1brown 元動画（英語） https://youtu.be/bOXCLR3Wric ゼータ関数の見た目【解析接続】 https://youtu.be/Xjja6Cc7lio 【視覚的に理解する】フーリエ変換 https://youtu.be/fGos3wrKeHY 最後の問題の解説 https://benjamin-
畳み込みの仕組み | Convolution
確率から画像処理まで、離散畳み込みと高速フーリエ変換(FFT) 激ムズ数え上げパズルと驚きの解法 https://youtu.be/FR6_JK5thCY フーリエ変換の解説動画 https://youtu.be/fGos3wrKeHY 【注釈】 整数のかけ算のアルゴリズムについて、FFTの"straightforward"な適用はO(N * log(n) log(log(n)) )の実行時間になる。log(log(n))の項は小さいが、2019年になってHarvey and van der Hoevenがこの項を取り除くアルゴリズムを発見した。また、O(N^2)を、必要な計算量がN^2と共に大きくなると表現したが、厳密にはこれはTheta(N^2)が意味するところである。 O(N^2)は計算量が高々N^2の定数倍になるという意味で、特に、実行時間がN^2項を持たないが有界であるアル
Othello is Solved 論文解説 (私見) - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどう
Longest palindromic substring - Wikipedia
In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindro
Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - ヴァルの開発記
概要 この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。 この記事を読むために必要な知識は以下です。 ・モンテカルロ木探索＋UCB1 ・MiniMax探索 ・ボンバーマンの基本的なルール 名のある木々 名もなき木々を紹介する前に、まずは名のある木々を紹介します。 MCTS モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。 有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。 一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。 →A Survey of Monte Carlo Tree Search Methods 最良優先MiniMax 最良優先MiniMax探索についてはこちらの論文が
[2023年1月版]競技プログラミングを始めたばかりの人にオススメの問題集 - Qiita
最推し: アルゴ式 2023年1月現在、初心者向けの最初の問題集としてお勧めしたいのは アルゴ式 です。アルゴ式の特徴として次のようなものがあると思っていて、それが初心者が練習するうえで適した特徴だと考えるからです ジャンルごとに問題が分かれている 1ジャンルごとの問題数がそれなりにある ひとつひとつの問題の難易度が易しめ 興味の湧いた人は、とりあえずアカウントを作って問題を解いてみてください。 なお、「競技プログラミングを始めたばかりの人」と言っても、その人の経験によって最適なものは変わってくるとは思いますが、次のような人を想定したときに特にアルゴ式が適していると思います。 プログラミング自体の初心者ではない。 初歩的なプログラミングの概念は一通り把握しているくらいを想定。 過去問に取り組もうとしたけど、A問題やB問題でも結構難しいと感じる。 この想定にマッチしない人であれば、次節以降で
![[2023年1月版]競技プログラミングを始めたばかりの人にオススメの問題集 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/ca69d5036112e102e8d4d669c6ed456421eeef8b/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fqiita-user-contents.imgix.net%252Fhttps%25253A%25252F%25252Fcdn.qiita.com%25252Fassets%25252Fpublic%25252Farticle-ogp-background-afbab5eb44e0b055cce1258705637a91.png%253Fixlib%253Drb-4.0.0%2526w%253D1200%2526blend64%253DaHR0cHM6Ly9xaWl0YS11c2VyLXByb2ZpbGUtaW1hZ2VzLmltZ2l4Lm5ldC9odHRwcyUzQSUyRiUyRnFpaXRhLWltYWdlLXN0b3JlLnMzLmFtYXpvbmF3cy5jb20lMkYwJTJGMTUzMjAlMkZwcm9maWxlLWltYWdlcyUyRjE0OTIwNzA1ODg_aXhsaWI9cmItNC4wLjAmYXI9MSUzQTEmZml0PWNyb3AmbWFzaz1lbGxpcHNlJmZtPXBuZzMyJnM9MjhjZDc5YTBhYTc3YjMxMzk4OTU5ODlmN2M2YmU1OWY%2526blend-x%253D120%2526blend-y%253D467%2526blend-w%253D82%2526blend-h%253D82%2526blend-mode%253Dnormal%2526s%253D87a2c91a9fc9fd3a1e728fa2e91e382c%3Fixlib%3Drb-4.0.0%26w%3D1200%26fm%3Djpg%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk2MCZoPTMyNCZ0eHQ9JTVCMjAyMyVFNSVCOSVCNDElRTYlOUMlODglRTclODklODglNUQlRTclQUIlQjYlRTYlOEElODAlRTMlODMlOTclRTMlODMlQUQlRTMlODIlQjAlRTMlODMlQTklRTMlODMlOUYlRTMlODMlQjMlRTMlODIlQjAlRTMlODIlOTIlRTUlQTclOEIlRTMlODIlODElRTMlODElOUYlRTMlODElQjAlRTMlODElOEIlRTMlODIlOEElRTMlODElQUUlRTQlQkElQkElRTMlODElQUIlRTMlODIlQUElRTMlODIlQjklRTMlODIlQjklRTMlODMlQTElRTMlODElQUUlRTUlOTUlOEYlRTklQTElOEMlRTklOUIlODYmdHh0LWFsaWduPWxlZnQlMkN0b3AmdHh0LWNvbG9yPSUyMzFFMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT01NiZ0eHQtcGFkPTAmcz1kOTY3NDdjNDgzZjk4NzAxNDEyOTlkYjA0NGIzYjRmYQ%26mark-x%3D120%26mark-y%3D112%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTgzOCZoPTU4JnR4dD0lNDBrdGF0ZWlzaCZ0eHQtY29sb3I9JTIzMUUyMTIxJnR4dC1mb250PUhpcmFnaW5vJTIwU2FucyUyMFc2JnR4dC1zaXplPTM2JnR4dC1wYWQ9MCZzPTQ0NThlNjY4MjljZWM0OGY1NTI5Zjk3NjEyOWExZmVh%26blend-x%3D242%26blend-y%3D480%26blend-w%3D838%26blend-h%3D46%26blend-fit%3Dcrop%26blend-crop%3Dleft%252Cbottom%26blend-mode%3Dnormal%26s%3D8fd684b1ae70325c7fef1969922ac531)
2023 パズルの逆ポーランド記法(RPN)による解法の解説
2023 年、あけましておめでとうございます！私は元旦に次のようなオリジナル・パズルを出しました。 上の例のように、数字の合間に四則演算（＋−×÷）や括弧を入れることで、2023 を作ってください。 数字の間に必ず演算子を 1 つ入れてください ただし 9 と 8 の間には既に ÷ が入っています 括弧は複数重ねて使用できます 10×(-9 ÷ 8) のようなマイナス記号の使用は禁止です オリジナルツイートはこちらです。この記事では、JavaScript によるこのクイズの解き方をご紹介します。 括弧の数式をプログラムで扱うには さて、この問題の一番厄介な点は、括弧の絡む数式をプログラムで処理するという点ではないかと思います。この記事でもそこを重点的に解説したいと思います。 中置記法 まず、我々が日常的に使っている数式は、いわゆる「中置記法」と呼ばれる記法です。例えば (1 + 1 / 9
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
RDBでのツリー表現入門2024 | ドクセル
Kosaraju's Algorithm for Strongly Connected Components
Barrett reduction - Wikipedia
Google Colab
Google Colab
データ構造 Fenwick tree (binary indexed tree, BIT) にどっぷりと入門し、その美しき構造に心を洗われたい方のための紹介記事です！ - Qiita
Basic Theory of Permutations. With an Implementation in Rust.