グラフアルゴリズム実践活用術情報オリンピック夏季セミナー 2023: https://jcioi-summer-seminar-2023.peatix.com/ での講演スライドです。 講義概要: アルゴリズムを勉強していると，グラフアルゴリズムにたくさん出会います．しかし，グラフアルゴリズムが現実世界でどのように活躍してい…
プリム法ベースのシュタイナー木 - bowwowforeachの日記
AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
[書評] 『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』をしっかり読み直しました | DevelopersIO
こんにちは、AWS事業本部コンサルティング部に所属している今泉(@bun76235104)です。 最近サボっていたのですが、また面白くなって競技プログラミングにハマりつつあります。（以前は以下のようなブログ記事をかいていました） 今は「文系」とか「数学が苦手」とかを意識しすぎていたなと少し反省しています。 数学が苦手なのは事実なのですが、そこと向き合った上で意識変えないと本当に一生苦手になっちゃうなと思い返しました。 ということで、上の記事でも少し触れているのですが、1年ちょっとガッツリ活用できていなかった（手計算の問題を飛ばしたり）していた以下の書籍をもう一度最初から最後までやりきってみたら、色々と感動ポイントがあったので紹介します。 Key Value
![[書評] 『問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本』をしっかり読み直しました | DevelopersIO](https://cdn-ak-scissors.b.st-hatena.com/image/square/ff9c702744b7dd6f6d0c0ab0642e02bf398a5989/height=288;version=1;width=512/https%3A%2F%2Fdevio2023-media.developers.io%2Fwp-content%2Fuploads%2F2023%2F06%2Fmondaikaiketu_sugaku_algorithm_1200x630.png)
ハーバード大学のコンピューターサイエンスの講義（日本語版）が無料公開されている件「聞き取りやすいから英語も勉強できる」
QDくん⚡️Python x 機械学習 x 金融工学 @developer_quant 東工大が無料公開しているPython解説サイト chokkan.github.io/python/index.h… 初心者の目線に合わせた丁寧な説明で、かゆいところに手が届く教材。 基本的な文法、データ構造、ファイル入出力やオブジェクト指向、NumpyとMatplotlibの使い方などをひと通り学べる。 pic.twitter.com/XyBBslyeBa QDくん⚡️AI関連の無料教材紹介 @developer_quant 東工大が無料公開しているPython解説サイト chokkan.github.io/python/index.h… 初心者の目線に合わせた丁寧な説明で、かゆいところに手が届く教材。 基本的な文法、データ構造、ファイル入出力やオブジェクト指向、NumpyとMatplotlibの使い方
圧縮アルゴリズムBrotliとは？導入方法とメリット【nginx】
Brotliの特徴 brotliは2015年に発表され、その後Googleによってアップデートされたデータ圧縮アルゴリズムです。 httpにおける圧縮アルゴリズムとして使われることを主な目的としています。従来から広く使われているgzipと比較して、圧縮率が向上していながら、圧縮/伸長速度は同程度を維持しています。ただし、SSL/TLSが必須となっています。どの程度圧縮率が向上しているのかは、Brotilの効果を参照。 圧縮に辞書を併用しているのが特徴で、辞書には”<div/>”、”before”、”普通”などの頻繁に使われるHTMLタグや各言語の表現が約1万語入っており、圧縮をより効率的にしています。 ちなみに、辞書の中身はhttps://gist.github.com/klauspost/2900d5ba6f9b65d69c8eで見ることができます。 対応状況 IE以外の主要ブラウザは1
これでわかるB-treeアルゴリズム / B-tree algorithm
・二分探索木 (binary search tree) ・AVL tree ・B-tree ・B+ tree について順を追いながら説明。 流れを細かく書いたので、わかりやすいと思います。
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
繋がりを可視化する グラフ理論入門｜es
個人的に、一番面白いデータ構造であり探索アルゴリズムです。 ここで言うグラフは円グラフや、棒グラフのことではないです。プログラミングで扱うのは、図のように、点と線を繋げたものです。 ズバリ、人と人の繋がりを表現できます。 今回もJavascriptで実装します。 グラフ理論は、SNSだったり、レコメンドだったり、地図の経路だったり ルーティングだったり、点と点の繋がりを可視化します。繋がりを表現するデータ構造です。 巨大なインターネットもそうです。 そいう意味で、すごく身近なアルゴリズムですよ。 グラフの基本は次の２点で構成されています。 ・ノード：node(vertex) - 点（人、物、場所） ・エッジ：edge - 辺(繋がり、経路) 上の図を見ると一目瞭然ですね。ノードを人だとしたら、エッジが関係性です。まずは、これだけ理解できれば大丈夫です。 ちなみに、方向がない辺を無向グラ
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
分散プログラミングモデルおよびデザインパターンの考察 その3 - Software Transactional Memo
昨日に引き続いて分散システムのデザインパターンについて書いていきたい。 だがそれ以前に故障モデルに関する前提を忘れてはならない。人によって様々な方針があるが、個人的には分散システムの世界において意識しなくてはならない故障モデルは4つだと考えている。僕は前回のブログに書いた Replication の本をベースに書いており、少し言葉遣いや定義が他とやや違う点は許して欲しい。また、通信の脱落・遅延とはレイヤーが異なる議論である。 故障モデルの分類 故障が起きないモデル これは故障が起きない世界を仮定するモデルである。これ自体はプロダクションにそのまま投入できるものではない。だがこの故障モデルを想定しても解けない問題は故障が発生する状況では絶対解けない事が断言できたり、合意プロトコルが正しいかを議論する土台となったり、様々な実用的なアルゴリズムや分散システムの土台となるアルゴリズムが生まれる土壌
画風を変換するアルゴリズム - Preferred Networks Research & Development
Deep Neural Networkを使って画像を好きな画風に変換できるプログラムをChainerで実装し、公開しました。 https://github.com/mattya/chainer-gogh こんにちは、PFNリサーチャーの松元です。ブログの1行目はbotに持って行かれやすいので、3行目で挨拶してみました。 今回実装したのは”A Neural Algorithm of Artistic Style”(元論文)というアルゴリズムです。生成される画像の美しさと、画像認識のタスクで予め訓練したニューラルネットをそのまま流用できるというお手軽さから、世界中で話題になっています。このアルゴリズムの仕組みなどを説明したいと思います。 概要 2枚の画像を入力します。片方を「コンテンツ画像」、もう片方を「スタイル画像」としましょう。 このプログラムは、コンテンツ画像に書かれた物体の配置をそのま
初心者でもアルゴリズムが学べる・身につく書籍とサイト一覧 - paiza times
Photo by Anders Sandberg こんにちは、谷口です。 皆さんは、アルゴリズムの勉強はどのようにしていますか？ 情報系の学部出身の方は授業で勉強したことがあるかもしれませんが、文系の方や、プログラミングの業務経験のない方は、「そういえばちゃんと勉強したことない」という方も多いかと思います。（私もかつてそうでした……） アルゴリズムとは、「問題を解くための手順を定式化した形で表現したもの」のことです。例えば、複数のデータを並べ替えるソートの方法として、バブルソートやヒープソートといったアルゴリズムがあるということは、アルゴリズムをきちんと勉強したことがなくても、知っている方は多いかと思います。 仕様書の通りにコーディングをしていくだけの業務であれば、アルゴリズムを勉強する必要はないかもしれません。さらに前述のようなソート等に関しては、多くの場合既に関数が用意されており、アル
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
量子コンピュータの基礎から応用まで/quantum summit 2019