第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 ページ)
AtCoder緑になるまでに勉強した基本的なアルゴリズムやデータ構造まとめ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 先日開催されました東京海上日動プログラミングコンテスト 2020 で緑レートになることができました。 中には初回参加で緑になってしまう人もいるようですが、自分の場合そう順調にいくはずもなく、ここまで来るのに結構自己学習を重ねてきました。初参加したコンテストはアルゴリズムやデータ構造などは No 勉強、過去問も大体 10 門程度を解いただけでの参加ということもあり、灰色 diff でした。そこからコツコツ勉強を重ね、10 回目のコンテスト参加でようやく緑になれました。このブログでは今までに自身が学習したアルゴリズムやデータ構造を備忘録の意
NASAが宇宙規模の通信などで発生する損失にも耐えられるよう作った画像圧縮アルゴリズム「ICER」が誰でも利用可能に
NASAは、「宇宙から地球に無線で画像を転送する」といったデータ損失の大きな状況に最適化した画像圧縮アルゴリズム「ICER」を開発しています。そんなICERをC言語のライブラリとして実装したものがGitHubで無料公開されています。 GitHub - TheRealOrange/icer_compression: Progressive, error tolerant, wavelet-based image compression algorithm https://github.com/TheRealOrange/icer_compression NASAは火星探査などのミッションで現地の様子を撮影した画像データを地球へ送信しています。異なる場所へデータを送信する際は、地球上での通信であってもデータの損失が発生しているのですが、地球と火星などの宇宙規模の通信ではデータの損失は非常に大き
マッピング | RNA-seq による遺伝子発現解析
2020.08.12 シークエンシングされたリードは、トランスクリプトの一部となっている。これらのリードの塩基配列とゲノム（リファレンス）配列を比べることで、各々のリードがゲノム上のどの遺伝子領域に由来するのかを明らかにすることができる。このように、リードとゲノム配列を比較して、リードの由来箇所を決めることをマッピングあるいはアラインメントとよぶ。 マッピング用のプログラムとして、STAR、HISAT2、BWA などが有名である。これらのプログラムは、FM index とよばれる文字列検索アルゴリズムを使用してマッピングを行なっている。したがって、これらのプログラムを使用するには、まずゲノム配列を FM index で検索できるように Burrows-Wheeler 変換しておく必要がある。この作業をインデックスの作成などという。インデックスを作成してから、FM index でリードと完全
自分を支配するアルゴリズムとどう付き合っていくべきか──『Uberland ウーバーランド アルゴリズムはいかに働き方を変えているか』 - 基本読書
Uberland ウーバーランド ―アルゴリズムはいかに働き方を変えているか― 作者: アレックス・ローゼンブラット,飯嶋貴子出版社/メーカー: 青土社発売日: 2019/07/25メディア: 単行本（ソフトカバー）この商品を含むブログを見るウーバーランドとは日本の有名な六人組ロックバンドの弟分──ではなく、Uberという配車アプリを提供する企業と、そのアルゴリズムがもたらす新しい経済圏のことである。Uberは、日本では法的な面で規制されていて広く使われているわけではないが(uber eatsは別として)、世界65カ国に導入されており、海外旅行に行った時にタクシーの代わりとして使ったことあるわ、という人も多いのではないか。 Uberのウリは便利なタクシーの配車というよりかは(普通のタクシーより安くて、アプリで目的地の指定も支払いもできるし、便利だけど)、本人確認が通って車さえ持っていれば、
読んだ直後から滅茶苦茶役に立つ──『アルゴリズム思考術:問題解決の最強ツール』 - 基本読書
アルゴリズム思考術:問題解決の最強ツール 作者: ブライアンクリスチャン,トムグリフィス,田沢恭子出版社/メーカー: 早川書房発売日: 2017/10/19メディア: 単行本（ソフトカバー）この商品を含むブログを見る『アルゴリズム思考術:問題解決の最強ツール』とは個人的にそそられる書名ではなかったので(ほぼ原題「ALGORITHMS TO LIVE BY」通り。)なかなか手が出なかったのだが、さらっと読み流すか……と手を出してみたらおもしろくて、その上読んですぐに役に立つ内容が満載なのであっという間に最後まで読んでしまった。 基本的にはアルゴリズム──より具体的な言葉でいえば「計算によってあらかじめ算出された、最適な手順」を知っていることが、いかに現実的な問題を解決する役に立つのかを紹介した一冊なのだが、なにしろ単なる手順なので、準備も何もいらないし読んだだけで「おーそうなんだ」とすぐに使
機は熟した！グラフ構造に対するDeep Learning、Graph Convolutionのご紹介 - ABEJA Tech Blog
はじめまして。ABEJAでResearcherをやらせていただいている白川です。 先日、化合物の物性推定をDeep Learningをつかって従来手法より300,000倍高速に処理するという論文がでました（[1], [2]）。この論文の手法は、Graph Convolutionというグラフ上に定義されたConvolution演算がベースとなっています。物性推定に限らず、グラフ解析全般を Deep Learning で上手にこなせるようになれば、Deep Learningのアプリケーションの幅がぐっと拡がり、さらなるイノベーションが起きそうな予感がします。 ICMLやNIPSなどの機械学習系の主要国際会議でも数年前からGraph Convolutionについての論文がちらほら出現しはじめており、とくに最近その勢いが増してきている印象があります。個人的にも最近（前から？）にわかにグラフづいてい
府大生が趣味で世界一の認識精度を持つニューラルネットワークを開発してしまった論文を読んだ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Deep Learning Advent Calendar 2016の20日目の記事です。 ConvNetの歴史とResNet亜種、ベストプラクティスに関連スライドがあります（追記） 背景 府大生が趣味で世界一の認識精度を持つニューラルネットワークを開発してしまったようです。 M2の学生が趣味でやっていたCIFAR10とCIFAR100の認識タスクで，現時点での世界最高性能の結果を出したそうだ…趣味でっていうのが…https://t.co/HKFLXTMbzx — ニーシェス (@lachesis1120) 2016年12月7日 府
「巡回セールスマン問題」を解くアルゴリズムを可視化したムービー
by Gaël Sacré いくつもの都市を移動するセールスマンが、すべての都市を最も効率よく(最小の移動コストで)移動できる方法を求める問題を「巡回セールスマン問題」といいますが、その解き方をビジュアル化したムービーがYouTubeで公開されています。 Traveling Salesman Problem Visualization - YouTube たとえば8つの都市があるとき、これを結ぶルートは5040通りが考えられます。 解法の一つが「欲張り法(Greedy Algorithm)」という、1つの都市から常に最寄りの都市へ移動しようと考える方法。 「最適」ではないものの、最適に近い答えを導き出してくれます。 ここで、組み合わせて使うのが「2-opt法」という方法。かなり単純なアルゴリズムで、2辺を繋ぎ直していきます。このとき、ルートに重なりがあると解消して新しいルートを作ります。
Alpha Goの話 - 発声練習
Google DeepMind社が開発しているAlpha Goの論文を読んでみたけど、うっすらとしか理解できない。機械学習の知識が足りない。stochastic gradient descentとstochastic gradient ascentってなんだよ！なんかの必殺技にしか見えない。いろいろ調べながら読んでみると、コンピュータ囲碁が劇的に強くなった原因であるモンテカルロ木探索におけるプレイアウト（Natureの論文だとrollout）時の打ち方（Policy network）とモンテカルロ木探索のノードの評価値（value network）を決めるところに畳み込みニューラルネットワークを使った深層学習を適用しているらしい。モンテカルロ木探索については情報処理学会学会誌「情報処理」の以下の記事がわかりやすかった。 美添一樹: モンテカルロ木探索-コンピュータ囲碁に革命を起こした新手法
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
無敵のポーカー・プログラム完成、カナダ研究
テーブルを囲んで行われる「テキサス・ホールデム（Texas hold'em）」。仏領コルシカ（Corsica）島で（2007年2月撮影、資料写真）。(c)AFP/STEPHAN AGOSTINI 【1月9日 AFP】プレーヤー2人に限定したポーカーの「テキサス・ホールデム（Texas hold'em）」で、理論上絶対に負けないコンピュータープログラムを開発したとする研究論文が、8日の米科学誌サイエンス（Science）に掲載された。 論文の主執筆者、カナダ・アルバータ大学（University of Alberta）のマイケル・ボーリング（Michael Bowling）氏はAFPの取材に、研究チームは2003年より「現在の超一流プレーヤーに負けない、またどんな戦略にも負けない、完璧なプレーヤーを作り出すこと」を目標に掲げてきたと語る。 研究チームは2008年、ポラリス（Polaris）と
テキサスホールデムの最適解は求まるか | Scene Research Station
これは以前テキサスホールデムのゲーム理論上の最適解について調べ物をしていたときの備忘録です。 ゲーム理論とは ここを読んでいただくのが手っ取り早いですが、複数人のプレイヤでゲームをするとき、どうやったら最大の利益が得られるかを考える学問です。第二次世界大戦前後にフォン・ノイマンが戦略を確率的に混ぜた混合戦略を用いることで様々なゲームにおいて均衡が見つかることを示し、そこから軍事等に応用されました。さらにナッシュが非協力ｎ人ゲームでも均衡が存在することを示し、殆どの現実のモデルにゲーム理論を適用可能となりました。当然ポーカーにも理論上は適用可能です。もし均衡が分かれば、それは絶対に搾取されない無敵の戦略となります。(ただし誰にも負けないことを保証するだけで、プラスになるとは限りません。例えば、ジャンケンのナッシュ均衡はグーチョキパーを1/3ずつの割合で出す戦略ですが、誰にも負けませんが誰にも
Deep Learningと画像認識� �～歴史・理論・実践～
SSII2022 [SS1] ニューラル3D表現の最新動向〜 ニューラルネットでなんでも表せる？？ 〜
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
文字列傾斜錯視の自動生成
壁にかかったカレンダー，掛け軸，額縁などを見て，もし斜めに傾いていれば，それをまっすぐに直すと思います．ここで一つの疑問が起こります．なぜ人は水平であるとか，斜めに傾いていることがわかるのでしょうか？
あらゆる数独パズルを解く
Peter Norvig / 青木靖 訳 このエッセイでは、 あらゆる数独パズルを解くという問題に取り組む。制約伝播と探索という2つのアイデアを使うと、ごく簡単に解けるということがわかる(主要なアイデアはコードにして1ページたらずで、補足的なコードが2ページある)。 数独の記法と予備概念 最初に記法をいくつか決めておこう。数独パズルは81個のマス(square)からなる盤面を使う。数独ファンの多くはカラムを1-9で、行をA-Iでラベル付けしており、カラム、行、ボックスのような9個のマスの集まりをユニット(unit)と呼び、ユニットを共有するマスをピア(peer)と呼んでいる。パズルではマスのいくつかが空いており、他は数字が入っている。パズルの目的はこうだ。 それぞれのユニットのマスが1から9の数字の順列によって埋められるようにする。 つまり、1つのユニットに同じ数字が2度現れてはならず、そ
Next generation of algorithms inspired by problem-solving ants
Next generation of algorithms inspired by problem-solving ants by University of Sydney The ants were able to find the shortest route from one end of the maze to the other in under an hour, then were able to adapt and find the second shortest route when obstacles were put in their path. (PhysOrg.com) -- An ant colony is the last place you'd expect to find a maths whiz, but University of Sydney rese
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
When Bad Things Happen to Good Scientists
An Algorithm To Explain Sex