Chromeのなかの コンピュータ・サイエンス * haraken@chromium.org 2015 Sep *
離散構造の オンライン予測 畑埜 晃平 九州大学 IBIS2013 企画セッション「学習理論」 離散構造を用いた “オンライン”意思決定問題 （敵対的）環境 プレイヤー 累積損失を 小さくしたい For t=1,…,T: 離散構造 C t c 損失 ) ( t c lt 具体例：資源割当，ネットワーク最適化，最短経路， スケジューリング，ランキング 本発表：学習理論の立場からのサーベイ 目次 1. 離散構造のオンライン予測問題 2. 離散→連続ベクトル予測への帰着 3. オフライン－オンライン変換 例１：オンライン資源割当問題 バス2 バス3 バス1 路線A 路線B 路線C 0.6 0.3 0.9 0.7 0.5 0.7 0.8 0.4 0.4 For t=1,…,T日間: バスを路線 へ割当 １ コスト を割当 ２ t日目におけるプレイヤーの損失 ３ プレイヤー （バス会社） 環境
国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです． 今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'
マンガでわかるフーリエ解析 作者:渋谷道雄,晴瀬ひろきオーム社Amazon やあ子どもたち。数値配列を日常的に扱っている俺達プログラマーにとって、フーリエ変換がいかに簡単かというイメージを忘れないように以前日記を書きました。その中で、DFT（離散フーリエ変換）計算の実践実装例も見ました。 そして今日はその高速版、FastFourierTransform（高速フーリエ変換）（以下、FFT）の実装及び原理を紹介します。（実際に動くC++のプログラムソースコードは本記事の一番最後の方にあります。） FFTは20世紀の10大アルゴリズムの中にも数えられる、とても有名なアルゴリズムでもあります。とはいえその歴史は古く、FFTやDFTの本当の起源というところまで行くと、あの大数学者ガウス（1777年生まれ）が既に気付いていた？などという噂もあるらしく、それ自体をテーマにした研究論文が出版されたりしてい
Graphillion は膨大な数のグラフに対して検索や最適化、列挙を行うための Python モジュールです。このビデオは Graphillion の概要を知るためのチュートリアルです。「フカシギの数え方」 http://youtu.be/Q4gTV4r0zRs の続編として作成されました。 Graphillion is a Python software package on search, optimization, and enumeration for a very large set of graphs. This video is a quick tutorial to learn what Graphillion is. The story follows our previous episode, "Let's count!" http://youtu.be/Q4gT
柔軟な発想で問題を定式化できれば、定番のアルゴリズムを驚くほど広い範囲に適用できます。 トップクラスのプログラマが問題を解く際にどのように考えているのかを紹介します。 目次
前編 (平衡二分探索木編) はこちら http://www.slideshare.net/iwiwi/2-12188757
なにやらDan Kogai氏の以下の記事が話題になっている様子。 404 Blog Not Found:Algorithm - 連想配列の実装としてのハッシュはオワコン? 連想配列(キーワードを投げると対応する値が返ってくるデータ構造)はハッシュテーブルで実装するのではなく、これからはトライ(trie)木を使うのがイケてる！(意訳)という内容だった。 連想配列にハッシュテーブルを使うのが良いか悪いかについては色々と意見があると思うので特にこの記事では触れない。 今回は連想配列として使えると話題のトライ木とはなんぞ、という入門的な記事にしようと思う。 トライ木が持つ機能 最初にトライが持つ以下の3つの機能について説明する。 - lookup - common-prefix-search - predictive-searchまずトライは連想配列として利用できる。つまりキーワードと値のペアを登
リンクvia boeing boeingLondon Underground Map with Distance Grids自分は、東京に住んではいるものの、あまり都心の地下鉄には乗りません。なので、「○○駅から□□駅までは徒歩移動可能」みたいな土地勘がほとんど無いのが悩みです。しかも、路線図というのは実際の位置関係とは対応しないので、近いと思ったら遠かったり、わざわざ乗り換えて3駅移動したあげくすぐ近くだったりと失敗が多いです。（画像引用：上記サイトより）リンクは、ロンドン路線図に、実際の地理を表現したグリッドを表示するというものです。たぶん、ロンドンよりも東京の地下鉄の方が複雑だと思うので同じようには行かないと思うのですが、路線図が「トポロジー的に」正しければ、描画は可能なはずだと思うので、アルゴリズム的には興味深いかもしれません。
The document discusses hyperparameter optimization in machine learning models. It introduces various hyperparameters that can affect model performance, and notes that as models become more complex, the number of hyperparameters increases, making manual tuning difficult. It formulates hyperparameter optimization as a black-box optimization problem to minimize validation loss and discusses challenge
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
よくアルゴリズムの話とかすると「アルゴリズムとか業務で使わないから。ライブラリあるから」みたいな話が出ますね。今日もTwitterでkumagiさんが「競技プログラミングが業務で役に立たないって言ってる人は・・・」って話してたわけです。 でもまあ、アルゴリズムの勉強ってのは、実装したい問題をいかに効率のいいプログラムに落とすかっていう話なんで、プログラムを組むっていう業務をしていたら必要ないとは思わないはずなんで、「アルゴリズムいらない」っていう人がやってる業務はプログラミングじゃないんじゃないのかと思ったりするわけです。 で、noritunaさんが「コーダー」を挙げてて、こういう文脈でよく出るんだけど、これはちょっと違和感あって、「コーダー」は誰かが書いたプログラムをコンピュータに入力するだけくらいの語感で、別に「プログラマ」という職種が必要になるサポート的業種で、でも実際は「プログラマ
これはなんですか？ 奥村晴彦氏の著書「C言語による最新アルゴリズム事典」をPythonでやろうと決意。Rubyに翻訳されていたので、Pythonでもやってみようと。でも実は書籍はもっていなくてCとRubyのソースを見つつ翻訳しています。１日１個ペースで進んでいます。 やっているうちにこの本が欲しくなってきました。 個人のPython力を高めるために始めましたので、間違いが含まれているかもしれません。ご指摘等ございましたら連絡[syobosyobo at gmail dot com]ください。 ちょっと方針をかえて、ctopyで訳すことにした。またまた方針をかえて、、、ctopyはあまりつかえない。ちょっといじってやらないと、出力がよくない。コメントとか入ってると、うまく変換してくれないし。 で、そのあとPythonらしい書き方で書いていこう、かと。どうなるかわかりませんが。
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く