アルゴリズムの世界地図 - Qiita
0. アルゴリズムとは？ まず、アルゴリズムとは何かを説明します。（0 節の説明はスライド「50 分で学ぶアルゴリズム」 の説明を参考にして書きました） さて、次の問題を考えてみましょう。 問題： 1 + 2 + 3 + … + 100 の値を計算してください。 単純な方法として、式の通りに 1 つずつ足していく方法が考えられます。すると、以下の図のように答えが計算されることになります。 これで答え 5050 が正しく求まりました。これはれっきとした アルゴリズム であり、この問題を 99 回の足し算 で解いています。しかし、計算回数が多く、計算に時間がかかるのではないかと思った方もいると思います。 ここで、方法を変えて、「1 + 100」「2 + 99」「3 + 98」…「50 + 51」の合計を求めることで、1 + 2 + 3 + … + 100 の値を計算してみましょう。 50 個の
最適輸送の解き方
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
異常検知入門と手法まとめ - Qiita
異常検知について勉強したのでまとめておきます。 参考文献 下記文献を大いに参考にさせていただきました： [1] Ruff, Lukas, et al. "A Unifying Review of Deep and Shallow Anomaly Detection." arXiv preprint arXiv:2009.11732 (2020). [2] 井手. "入門 機械学習による異常検知―Rによる実践ガイド" コロナ社(2015) [3] 井手,杉山. "異常検知と変化検知 (機械学習プロフェッショナルシリーズ)" 講談社サイエンティフィク(2015) [4] 比戸. "異常検知入門" Jubatus Casual Talks #2(2013) [5] Pang, Guansong, et al. "Deep learning for anomaly detection: A rev
Linuxを生み出したリーナス・トーバルズが考える「優れたコード」とは何か？
プログラミングをする上で、コメントをきちんと残したり、わかりやすい変数名をつけたりして「読みやすいコード」を目指す作業は重要です。しかし、「読みやすいコード」と「優れたコード」の間には、時として構造上の大きな違いがあるのも事実。そんな「優れたコード」に対するLinuxの開発者リーナス・トーバルズ氏の考え方について、エンジニアのmkirchner氏が説明しています。 mkirchner/linked-list-good-taste: Linus Torvalds' linked list argument for good taste, explained https://github.com/mkirchner/linked-list-good-taste Linus Torvalds: The mind behind Linux | TED Talk https://www.ted.co
2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
アルゴリズムとは何か！？ ～ 文系理系問わず楽しめる精選 6 問 ～ - Qiita
今の場合は A さんが 31 歳の場合のストーリーでしたが、A さんが 20 歳～ 35 歳のうちのどの年齢であったとしても、似たようなストーリーで必ず 4 回の質問で当てることができます！(他の例も是非考えてみてください。) ちなみに、このような「真ん中で切ってどちらかに絞って行く」タイプのアルゴリズムには二分探索法という名前がついています。応用情報技術者試験でも頻出のテーマですので馴染みのある方も多いと思います。 1-2. つまり、アルゴリズムとは 上の年齢当てゲームという問題では、相手の年齢を当てる「方法・手順」を二分探索法に基づいて導きました。このようにアルゴリズムとは、 問題を解くための方法・手順 のことです。さて、アルゴリズムと聞くと「コンピュータ上で実装されたプログラム」のことを思い浮かべる方も多いと思いますが、必ずしもコンピュータと関係がある必要はなく、日常生活でも多々登場
「ループ・再帰・gotoを使わず1から100までの数値を印字する」Conner Davis 氏の回答の考察 - Qiita
2019年6月に以下の記事が投稿されました。 ループ、再帰、gotoを使わずに1から100までを印字するC++プログラムは書けますか？に対するIchi Kanayaさんの回答 - Quora 英語版の記事「How to print 1 to 100 in C++ without a loop, goto or recursion - Quora」から興味深い回答を抜き出して、それにランク付けをしながら和訳してくださっている記事です。 初級や中級は「まぁあるよね（C++知らないけれど……）」という感じですが、 上級とされた「マイクロソフト社のデータサイエンティスト Conner Davis 氏」の回答が面白かった ので、ご紹介を兼ねてその発想の源泉を推測してみることにしました。 以下に Conner Davis 氏の回答の和訳を引用します。 マイクロソフト社のデータサイエンティスト Conn
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
決定木分析についてざっくりまとめ_理論編 | DevelopersIO
概要 こんにちは、yoshimです。当エントリは「Machine Learning Advent Calendar 2017」の11日目のエントリです。 今回は教師あり学習の１手法である「決定木分析（decision tree）」をご紹介します。 目次 1.決定木分析とは 2.特徴 3.処理の流れ 4.情報利得と不純度 5.剪定方法 6.決定木分析におけるメジャーなアルゴリズムの紹介 7.まとめ 1.決定木分析とは まず、決定木分析とはなんなのか、ということをざっくり説明しようと思います。 決定木分析は、「段階的にデータを分割していき、木のような分析結果を出力する」ものです。 言葉だけではイメージがつかないと思いますが、具体的には下記のような分析結果を出力します。 機械学習に興味がある方なら見たことがあるのではないでしょうか？ 決定木分析ではこの画像のように上からデータを分割していき、デー
読んだ直後から滅茶苦茶役に立つ──『アルゴリズム思考術:問題解決の最強ツール』 - 基本読書
アルゴリズム思考術:問題解決の最強ツール 作者: ブライアンクリスチャン,トムグリフィス,田沢恭子出版社/メーカー: 早川書房発売日: 2017/10/19メディア: 単行本（ソフトカバー）この商品を含むブログを見る『アルゴリズム思考術:問題解決の最強ツール』とは個人的にそそられる書名ではなかったので(ほぼ原題「ALGORITHMS TO LIVE BY」通り。)なかなか手が出なかったのだが、さらっと読み流すか……と手を出してみたらおもしろくて、その上読んですぐに役に立つ内容が満載なのであっという間に最後まで読んでしまった。 基本的にはアルゴリズム──より具体的な言葉でいえば「計算によってあらかじめ算出された、最適な手順」を知っていることが、いかに現実的な問題を解決する役に立つのかを紹介した一冊なのだが、なにしろ単なる手順なので、準備も何もいらないし読んだだけで「おーそうなんだ」とすぐに使
Pythonメモ : pygorithmで探索、ソートのアルゴリズムを学ぶ - もた日記
pygorithm インストール 使い方 その他のアルゴリズムまとめリポジトリ pygorithm github.com pygorithmという探索、ソートなどのアルゴリズムを学ぶためのモジュールがあったので試してみる。 インストール pipでインストールできるので下記コマンドを実行。 $ pip install pygorithmが、少し試したところ最新バージョンではなかったのでGitHubのリポジトリをインストールした。 $ pip install git+https://github.com/OmkarPathak/pygorithm 使い方 バブルソートを例に試してみる。 まずはbubble_sortをインポートして実際にソートする。 from pygorithm.sorting import bubble_sort myList = [12, 4, 3, 5, 13, 1, 1
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
二つで十分ですよ - カレーなる辛口Javaな加齢日記
「初心者でもOK！レベル別・アルゴリズムをすぐに学べる書籍とサイト12選」 http://paiza.hatenablog.com/entry/2017/01/24/%E5%88%9D%E5%BF%83%E8%80%85%E3%81%A7%E3%82%82OK%EF%BC%81%E3%83%AC%E3%83%99%E3%83%AB%E5%88%A5%E3%83%BB%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E3%81%99%E3%81%90%E3%81%AB%E5%AD%A6 うあ，またpaizaの糞記事がブクマ集めてるよ．きっと「あとで読む」だらけの． 「これはヒドイ「初中級エンジニアが【アルゴリズムを優しく学べる】本とサイト16選」」 http://d.hatena.ne.jp/JavaBlack/2
Javaで冪集合を生成する - アルゴリズム学習(その3) - $shibayu36->blog;
同僚に冪集合作ってみては、と言われたので作った。冪集合はhttp://www.geocities.jp/k27c8_math/math/set_theory/power_set.htmとかに書いてあるとおり、渡された集合の部分集合全体。 考え方 思いついたのは以下の考え方。 [ 1, 2, 3 ]と渡されたとする 冪集合とは、それぞれを含む・含まないを全通り集めたものと考える すると、[ 0, 0, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ], ..., [ 1, 1, 1 ]のようなbit配列を考え、1なら対応する要素をピックアップすると考えたらいい ループは2の3乗分行えば良いはず 実装 import java.util.ArrayList; import java.util.List; public class PowerSet1 { public static Li
Javaで組み合わせを生成する - アルゴリズム学習(その2) - $shibayu36->blog;
Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;で順列を作ったので、続いて組み合わせを作ってみた。 考え方 いろんな考え方があると思うけど、僕が最初に思いついたのは次の考え方。 [ 1, 2, 3, 4, 5 ]から3つ取り出す組み合わせを考える まず、1を取り出して、[ 2, 3, 4, 5 ]から2つ取り出す組み合わせのリストを作り、全てのリストの先頭に1を結合する 次に、2を取り出して、[ 3, 4, 5 ]から2つ取り出す組み合わせのリストを作り、全てのリストの先頭に2を結合する 組み合わせなので、前に取り出した1を使ったらだめなことに注意 次に3を取り出して、[ 4, 5 ]から2つ取り出す組み合わせのリストを作り(つまり [4, 5]だけど)、全てのリストの先頭に3を結合する 1, 2, 3を取り出して作り出したリ
Javaで順列生成アルゴリズムを実装する - アルゴリズム学習(その1) - $shibayu36->blog;
アルゴリズムを勉強しようと思って、以下の本のアルゴリズムをJavaで自分で考えて再実装するという取り組みをやっている。以下の本は基本的なアルゴリズムが簡単に説明されていて、しかも薄いのでやりやすい。2011-09-22を見て購入した。 Java データ構造とアルゴリズム基礎講座 作者:長尾 和彦技術評論社Amazon それで最初に順列生成の話が出てきたので、まずはこれを作ってみた。実装は https://github.com/shibayu36/algorithm-study/tree/master/java-data-structure-and-algorithm においてある。 順列の内容をprintlnする関数を作る まずは簡単に順列の内容をprintlnする関数を作ってみる。 この本に書いてあった説明がいまいちわからなかったので、順列生成のアルゴリズムを説明しているブログ記事とかを
サーバー証明書は本当に安全？
答え：問題が見つかったら無効にする仕組みがあります 今まで解説したように、サーバー証明書はTLSの安全性のキモと言うべき重要な要素だ。サーバー証明書に含まれる公開鍵が、証明書に記載された企業・組織あるいはドメインのものだと保証するお墨付きとして機能するからだ。 TLSで使われている証明書は、ITU▼が定めた「X.509 バージョン3（v3）」というフォーマットに従って記述されている。どのようなデータが書き込まれているか具体的に見ていこう。 3パートで構成する 証明書は、「署名前証明書」「署名のアルゴリズム」「認証局による署名」の3パートで構成される（図6-1）。署名前証明書のパートには、この証明書を使うWebサーバーの運営企業や、証明書を発行した認証局、証明書の有効期限などの基本的な情報が入る。 TLSで使われている証明書フォーマット「X.509 v3（version 3）」の構造。大きく
「日本語ボキャブラリーテスト」のアルゴリズム - Qiita
語彙力診断の点数分布 - Qiita を読んでなんとなくやってみたくなったので。当該診断のアルゴリズムを読んでいきます。 日本語ボキャブラリーテストのソースコードを見ると結果表示スクリプトが function resultParse() { $("#collection, #progress").hide();$("#result_details, #emoji, .result_link, .footer-share").show(); iq_value = getVocSizeByAnswers(voc_answers); prestige = "私の語彙力は・・・【" + parseInt(iq_value * lang_ratio) + "】です！あなたは？"; ... } function getVocSizeByAnswers(arr){ var size = 0; var H
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
