アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く
厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j
The Best Algorithm No One Knows About
Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication. You may think you know how to do this, but you almost assuredly don’t. Say you work at Twitter and have to select just one tweet at random. This is an easy problem. Generate a random number less than the total number of tweets, and draw the tweet that corresponds somehow to your num
de Bruijn Graph を使った de novo アセンブリの発想がすごい件 - ほくそ笑む
Velvet や ABySS などの代表的な de novo アセンブリツールでは、アルゴリズムに de Bruijn Graph というのを使っているそうです。どうやってアセンブルしているんだろう？と興味を持っていたので、元ネタの An Eulerian path approach to DNA fragment assembly を読んでみたんですが、その発想のすごさに度肝を抜かれました。せっかくなので、ここで簡単に説明してみたいと思います。 ケーニヒスベルクの橋 まずはグラフ理論の説明から。グラフ理論は、18世紀にオイラーという数学者が「ケーニヒスベルクの橋」という問題を解くために考え出したといわれています。 「ケーニヒスベルクの橋」は、次のような問題です。 18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルクという大きな町があった。この町の中央には、プレーゲル川という大き
arxiv に P≠NP 問題を解決した論文が投稿される | スラド サイエンス
計算機科学の未解決問題であるP≠NP予想を解決したとする論文がarxivに投稿された（結城浩氏のツイート、論文のページ）。 NP完全問題は、巡回セールスマン問題のような、入力（重み付きグラフと閾値）に対する証拠（巡回経路）があれば入力を多項式時間で判定できる問題の中では最も難しいものである。NP完全問題を多項式時間で解くアルゴリズムはまだ見つかっていない。そのようなアルゴリズムが存在すればP＝NPであり、存在しないならばP≠NPであるが、現在までどちらなのか分かっていない。 今回投稿された論文では、P≠NP（つまり、NP完全問題は多項式時間で解けない）と結論付けている。著者が計算機科学の専門家（大学の情報科学科の教授）である点から、この論文に期待する意見もある。しかし、arxivには査読の仕組みがないため、この証明が正しいかどうかは、現段階では不明である。 ところで、P≠NP問題を解決した
Optimizing Pattern Matching
Optimizing Pattern Matching Fabrice Le Fessant, Luc Maranget INRIA Roquencourt, B.P. 105, 78153 Le Chesnay Cedex, France (Email: {Fabrice.Le_fessant, Luc.Maranget}@inria.fr) Abstract: We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimi
Contraction hierarchies - Wikipedia
In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights
長さ制限つきのハフマン符号化(The Coin Collector's Problem) - sileのブログ
冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマン符号化は、以前に簡単なものを実装したことがあるが、DEFLATEアルゴリズムで使用するハフマン符号化では、一般的なそれとは異なり、(符号化される)各コードを表現するビット列の長さに制限(15ビットまで)を付けられる必要があるらしい。 なので今回はまず、その長さ制限付きのハフマン符号化アルゴリズムの実装を試してみることにする。 The Coin Collector's Problem 参考にしたのは、以下のWikipediaの記事。 Package-merge algorithm 編集日時: 2007/06/23 00:2
ビット演算クイズを解いた時の話 - 兼雑記
http://herumi.in.coocan.jp/diary/1804.html#13 を解いた時の話。光成さんは実験的に解かれたようだったんですが、割と理詰めで解けたので、思考過程をダンプしてみます。元のコードは int calc(int a, int b, int s) { const int Q = 1 << s, Q2 = Q * 2, Q3 = Q * 3; assert(0 <= s && s <= 16 && && 0 <= b && b < a && a < Q * 4); int n = 0; for (;;) { if (a < Q2) { // A n = n * 2; } else if (b >= Q2) { // B n = n * 2 + 1; a -= Q2; b -= Q2; } else if (b >= Q && a < Q3) { // C a
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
15 Great Articles About Decision Trees - DataScienceCentral.com
Home » Uncategorized15 Great Articles About Decision Trees Vincent GranvilleFebruary 21, 2018 at 1:30 pm This resource is part of a series on specific topics related to data science: regression, clustering, neural networks, deep learning, Hadoop, decision trees, ensembles, correlation, outliers, regression, Python, R, Tensorflow, SVM, data reduction, feature selection, experimental design, time se
Masaaki Imaizumi - 研究解説（日本語）
A.Sannai, M.Imaizumi, "Improved Generalization Bound for Permutation Invariant Neural Networks" (arXiv 2019) 置換不変な性質を持つ深層学習について、その高い性能を数学的に解析した論文です。 置換不変な深層学習は、点群や画像セットなどのデータを交換しても性質が変化しないデータについて、高い性能を出すことが経験的に知られています。 本研究は、そのような深層学習の性質を数学的に解析し、その誤差率（汎化誤差）が置換不変でない場合に比べて、置換要素の数の階乗分だけ改善することを示しました。 置換要素の数は、一般的な点群のデータにおいては1,000程度あり、その階乗分の誤差の改善は、非常に大きな理論的誤差の改善になることが期待されます。 原稿 / 共著者：三内研究員（理研）
Simultaneous localization and mapping - Wikipedia
2005 DARPA Grand Challenge winner Stanley performed SLAM as part of its autonomous driving system. A map generated by a SLAM Robot Simultaneous localization and mapping (SLAM) is the computational problem of constructing or updating a map of an unknown environment while simultaneously keeping track of an agent's location within it. While this initially appears to be a chicken or the egg problem, t
Minimal Perfect Hash-Tables in Common Lisp
Recently, my twitter pal @ifesdjeen wrote a line that resonated with me: "Looks like it's easier for people to read 40 blog posts than a single whitepaper." And although he used it in a negative context, I recognized it as a very precise (and, actually, positive) description of what a research engineer does: read a whitepaper (or a dozen, for what it's worth) and transform it into working code and
Using Self-Organizing Maps to solve the Traveling Salesman Problem
Using Self-Organizing Maps to solve the Traveling Salesman ProblemThe Traveling Salesman Problem is a well known challenge in Computer Science: it consists on finding the shortest route possible that traverses all cities in a given map only once. Although its simple explanation, this problem is, indeed, NP-Complete. This implies that the difficulty to solve it increases rapidly with the number of
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://twitter.com/fushiroyama/status/1525035162546761728?t=LPwJFAp3Q2pP8-WqT6n0mA&s=09
de novo アセンブリー | de Bruijn graph によるゲノムアセンブリー
https://codeday.me/jp/qa/20190218/272904.html
GitHub - ronomon/hash-table: Fast, reliable cuckoo hash table for Node.js.
Redirect
algorithms and data structures term1