大規模な組合せ最適化問題に対する発見的解法
5. 最適化問題に定式化する ⽣生産計画問題 あるシャトーでは3種類のブドウ，カルベネ，メルロー，セミヨンを原 料料として，3種類のワイン，⾚赤ワイン，⽩白ワイン，ロゼワインを製造し ている．収益が最⼤大となる各ワインの1⽇日当たりの製造量量を求めよ． 種類 ⾚赤ワイン ⽩白ワイン ロゼワイン 最⼤大供給量量 カルベネ 2 0 0 4(t/⽇日) メルロー 1 0 2 8(t/⽇日) セミヨン 0 3 1 6(t/⽇日) 収益 3 4 2 (百万円/⽇日) → 収益を最⼤大化 → カルベネの使⽤用量量は4t/⽇日以内 → メルローの使⽤用量量は8t/⽇日以内 → セミヨンの使⽤用量量は6t/⽇日以内 → 各ワインの製造量量は⾮非負 maximize 3x1 + 4x2 + 2x3 subject to 2x1 4, x1 + 2x3 8, 3x2 + x3 6, x1
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
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の符号をもたせる
A/Bテストよりすごい？バンディットアルゴリズムとは一体何者か - Qiita
オバマ大統領の再選に大きく寄与したことで大きな注目を集めているA/Bテスト。A/Bテストを導入した、することを検討している、という開発現場も多いのではないだろうか。 そんな中、Web上で次のような議論を見つけた。 20 lines of code that will beat A/B testing every time Why multi-armed bandit algorithm is not “better” than A/B testing 一言でまとめると「A/Bテストよりバンディットアルゴリズムの方がすごいよ」「いやいやA/Bテストの方がすごいし」ということだ。 で、バンディットアルゴリズムとは一体何者なのか？ そこでBandit Algorithms for Website Optimization (O'REILLY)を読んでみた。その結果分かったことを踏まえてざっくりと
ChordアルゴリズムによるDHT入門
Chordアルゴリズムの解説ページです。 掲載コンテンツへのリンク先を変更する可能性があるので、ブックマークやリンクは、このページにお願いします。 Chordは、DHT（Distributed Hash Table）と呼ばれる種類のPeer-to-Peerアルゴリズムです。 特に、構造化オーバレイ（Structured Overlay Network）と呼ばれるルーティング手法に特徴があります。 解説スライドでは、そもそもDHTとは何なのかという初歩的なことから、successorやpredecessor、finger tableと呼ばれるChordの有名な経路表の解説や、多くの解説ではあまり触れられることがないけれどもきわめて重要である、ネットワークの構築方法（join・stabilize）についても詳細に解説しています。 スライドのページ数は多いですが、１ページ当たり平均数秒で読めるは
博士公聴会：定数時間アルゴリズムについて | Preferred Research
吉田です． 先日，博士論文の公聴会が終わりました． タイトルは「次数を制限したグラフと制約充足問題に対する定数時間アルゴリズムの研究」というものでした． また，博士課程での研究の成果が認められて，日本学術振興会から育志賞という賞を頂くことになりました． こちらは他の受賞者の研究内容が分からなさ過ぎて凄いですね． 今後もPreferred Infrastructureにはアドバイザーの様な形で勤めることになると思いますので宜しくお願い致します． ということで博士課程の終わりも近く，良い区切りですので， これまで専門に研究してきた定数時間アルゴリズムについて簡単に話をすることにします． 定数時間アルゴリズムは，その名のとおり入力長に依存しない計算時間で動作するアルゴリズムのことです． 普通に考えてそんなアルゴリズムはあり得ないように思えますが，どうすればそんなアルゴリズムが実現出来るでしょうか
Sony Japan | 新卒採用｜ソニー株式会社 採用情報 | 新卒採用 | GO FOR IT コードで世界は変えられる
あなたならどう答えますか？ 我こそはと思う方、腕試ししたい方、あなたのちからを世の中に示してみませんか？ 2012年2月6日（予定）にこちらのページで発表される問題を解き、あなたの解答をだれよりも早くネットに公開してください。 詳細は後日、こちらのページにてご案内します。 ソニーは小型化・軽量化といったハードウェアの開発が得意な会社、という印象を持っている方もいるでしょう。 しかし、ソフトウェアやネットワークサービスを通じて、新たなユーザー体験をお客さまに提供することもソニーの重要なミッションです。 ソフトウェアエンジニアが活躍する場は数多くあり、これからも拡大します。 ソニーは、高いソフトウェア開発力を持つエンジニア(ソフトウェアスペシャリスト)を必要としています。 2013年新卒採用では、「ソフトウェアスペシャリスト」向けの選考コースを新設し、ソフトウェアの専門性を発揮できる
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei
検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり というようなものを想像する。 この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目が
待ち行列に入門した - steps to phantasien(2008-08-12)
先週, 会社をさぼって システム性能評価と待ち行列理論 という講義を受けてきた. 待ち行列理論の入門講義で, 大学の学部でやるレベルの話らしい. 私は学部でも学部以外でも勉強したことがない話題だったので, とても興味深く聞いた. 受講後はすっかり盛り上り, 待ち行列で性能評価するぜ! という気分になったのだが, 実際は難しい. 性能評価一般の難しさはさておくとして, 待ち行列理論そのものがけっこう複雑. 数学が苦手な身には辛い. 理論の常として, 待ち行列の理論もまず解析対象の特性に様々な制限や前提を設けた上でモデルをたてる. そのモデルがうまく解析できたら, 少しずつ制限をとりはずしていく. 現実を扱えるモデルに至る道程は険しそうだ. 高価なツールを使えばそんな洗練されたモデルも扱えるのかもしれないけれど, もうちょっと庶民に優しい路線であってほしい. 解析に挫ける一方, 理論の成果が明
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
ラムダ計算の勉強のしかた、プログラム意味論 - きしだのHatena
先日のエントリで手続きを記述するという側面と、式を記述するという2つの側面があるということを書きました。 プログラムの理論とはなにか そして、手続きの性質として代表的な、アルゴリズムについての勉強のしかたについてまとめてみました。 アルゴリズムの勉強のしかた そこで、今回は、式を記述するという側面の勉強のしかたと、あとこの分野は自分でもまだ全然勉強してなかったので、これからどういう本を読もうと思っているかをまとめてみます。 プログラム意味論 プログラムは必ずプログラム言語、少なくとも記号で記述します。*1 そこで、プログラムの勉強という点では、どのように動くかというアルゴリズムの勉強だけではなく、どのように書けるか、書いたものにどのような性質があるのかということも知る必要があります。 例えば、2005年あたりからRubyのような動的型付け言語が流行りだし、Javaなどの静的型付けの言語との
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
乱択アルゴリズム紹介(最小カット) - Preferred Networks Research & Development
\(G\)のカット\(C \subseteq E\)とは、\(G\)から\(C\)を取り除くと、二つ以上(の連結成分)に分かれてしまうようなもののことを言います。特にカットの中で大きさが一番小さいものを最小カットと言います。恐らく具体例を見た方が良いと思いますので、下の図を見てください。 さて「\((s,t)\)-最小カット=\((s,t)\)-最大フロー」という有名な事実が有ります。今回の目的ではないので、余り深入りはしませんが、\((s,t)\)-最小カットとは、グラフ中の頂点\(s, t\)を分けるカットで最小のものを指し、\((s,t)\)-最大フローは\(s\)から\(t\)に流れる”フロー(流れ)”で最大のものを指します。 \((s,t)\)-最大フローを求める決定性アルゴリズム(乱数を使わないアルゴリズム)はよく研究されていて、今現在最速なものは\(O(nm \log(n^2
Python dictionary implementation – Laurent Luce's Blog
This post describes how dictionaries are implemented in the Python language. Dictionaries are indexed by keys and they can be seen as associative arrays. Let’s add 3 key/value pairs to a dictionary: >>> d = {'a': 1, 'b': 2} >>> d['c'] = 3 >>> d {'a': 1, 'b': 2, 'c': 3} The values can be accessed this way: >>> d['a'] 1 >>> d['b'] 2 >>> d['c'] 3 >>> d['d'] Traceback (most recent call last): File "<s
病みつきになる「動的計画法」、その深淵に迫る
数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ
マルチコア時代の"データ構造とアルゴリズム"再入門
データ構造とアルゴリズム再入門 はじめに ・並{行|列} & {Lock|Wait}Free ・ABA & ABA' ・volatile ＆ メモリバリア ・プリミティブ ・CAS ・MCAS ・STM ・メモリ管理:free & GC ・Toots List & Skiplist [単方向List] ・リスト ・細粒度リスト ・Lazyリスト ・Lock-Freeリスト ・Lock-Freeリスト2 [SkipList] ・スキップリスト ・Lazyスキップリスト ・Lock-freeスキップリスト [双方向List] Queue & PriorityQueue [UnBounded Queue] ・Queue ・CAS based Lock-Free Queue ・LL/SC based Lock-Free Queue [Unbounded Priority Queue] ・Heap
分散ストレージに使えるかもしれないアルゴリズム
What's New in Teams Calling, Meetings and Devices April 2024
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Programming and prejudice: Computer scientists discover how to find bias in algorithms
幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
生物情報科学科 情報基礎実験 ３年生冬学期 10/26 – 11/5 （森下研究室担当）