博士公聴会：定数時間アルゴリズムについて | Preferred Research
吉田です． 先日，博士論文の公聴会が終わりました． タイトルは「次数を制限したグラフと制約充足問題に対する定数時間アルゴリズムの研究」というものでした． また，博士課程での研究の成果が認められて，日本学術振興会から育志賞という賞を頂くことになりました． こちらは他の受賞者の研究内容が分からなさ過ぎて凄いですね． 今後もPreferred Infrastructureにはアドバイザーの様な形で勤めることになると思いますので宜しくお願い致します． ということで博士課程の終わりも近く，良い区切りですので， これまで専門に研究してきた定数時間アルゴリズムについて簡単に話をすることにします． 定数時間アルゴリズムは，その名のとおり入力長に依存しない計算時間で動作するアルゴリズムのことです． 普通に考えてそんなアルゴリズムはあり得ないように思えますが，どうすればそんなアルゴリズムが実現出来るでしょうか
大規模グラフアルゴリズムの最先端 - 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)
先週, 会社をさぼって システム性能評価と待ち行列理論 という講義を受けてきた. 待ち行列理論の入門講義で, 大学の学部でやるレベルの話らしい. 私は学部でも学部以外でも勉強したことがない話題だったので, とても興味深く聞いた. 受講後はすっかり盛り上り, 待ち行列で性能評価するぜ! という気分になったのだが, 実際は難しい. 性能評価一般の難しさはさておくとして, 待ち行列理論そのものがけっこう複雑. 数学が苦手な身には辛い. 理論の常として, 待ち行列の理論もまず解析対象の特性に様々な制限や前提を設けた上でモデルをたてる. そのモデルがうまく解析できたら, 少しずつ制限をとりはずしていく. 現実を扱えるモデルに至る道程は険しそうだ. 高価なツールを使えばそんな洗練されたモデルも扱えるのかもしれないけれど, もうちょっと庶民に優しい路線であってほしい. 解析に挫ける一方, 理論の成果が明
ラムダ計算の勉強のしかた、プログラム意味論 - きしだの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
分散ストレージに使えるかもしれないアルゴリズム
The document discusses EpiChord, an enhancement of the Chord distributed hash table. It presents EpiChord's lookup algorithm and its division of the address space to reduce routing table sizes while maintaining low diameter. Bloom filters are also summarized, including how they represent sets using bit vectors and can check for set membership with possible false positives. Techniques like vector c
知れば天国、知らねば地獄――「探索」虎の巻
いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました！ 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、本連載では
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
幅優先探索すら知らない素人がDevQuizで満点を取るまでの話
生物情報科学科 情報基礎実験 ３年生冬学期 10/26 – 11/5 （森下研究室担当）