algorithmに関するcou929のブックマーク (55)

  • 大規模ネットワークの性質と先端グラフアルゴリズム - iwiwiの日記

    日,PFI セミナーにて「大規模ネットワークの性質と先端グラフアルゴリズム」というタイトルで発表をさせてもらいました.スライドは以下になります. 大規模ネットワークの性質と先端グラフアルゴリズム View more presentations from iwiwi Ustream の録画もあります. http://www.ustream.tv/recorded/27531606 内容としては,以下のようになっています. 現実世界のネットワークの特徴量と性質 次数分布 平均距離 クラスター係数 その他の特徴量 木っぽさ それらの性質を活用したグラフアルゴリズム セオリー方面 近接中心性の近似 コンパクトルーティング 支配集合問題の近似 プラクティカル方面 最短路 密部分グラフ列挙 可視化 タイトルは 1 年前にやった PFI セミナーと似ていますが,内容はあまりかぶっていません.今回は,グ

    大規模ネットワークの性質と先端グラフアルゴリズム - iwiwiの日記
  • あなたの知らないハッシュテーブルの世界

    Please select the category that most closely reflects your concern about the presentation, so that we can review it and determine whether it violates our Terms of Use or isn't appropriate for all viewers.

  • 汎用ソート殺し - d.y.d.

    00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した!!」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買ったがどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと棚アプリから画面外にがはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる

  • Amazon.co.jp: 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド: 高橋直大: 本

    Amazon.co.jp: 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド: 高橋直大: 本
  • http://atnd.org/events/29479

    http://atnd.org/events/29479
    cou929
    cou929 2012/06/12
    "「りんご、キウイ、うなぎ(パイ)」を提供する予定です。"
  • solution.dvi

  • 競技プログラミング Wiki*

    このwikiについて 競技プログラミングに関心を持ってみたものの、何をすれば良いか分からないという人が、このWiki(の特に基ページ)を読めば入門を果たせる事を目標とし、競技プログラミングの敷居を下げる目的で作られたwikiです。 編集者募集中です 内容が薄く、特に編集者を募集しているページはこちらです。内容が不十分なページ 競技プログラミングとは 簡単に言うと、「問題で与えられた条件に従って、早く正確にプログラムを書く競技」です。 プログラムと言っても、(GUIなどの)ウインドウを表示したりするような物ではなく、 数字や文字を受け取り、それを条件を満たすように計算して、結果を出力するような物です。 説明の代わりとして、例題を挙げておきます。 例題:A+B problem また、難しい問題になってくると、条件を満たせるような計算過程を考えるにあたって、「アルゴリズム」や「データ構造」と呼

    競技プログラミング Wiki*
  • DO++ : 乱択アルゴリズム

    「乱択アルゴリズム」が共立出版から出ているので読んでいます 乱択アルゴリズム(wikipedia)(ランダマイズドアルゴリズムの方が一般的かもしれない)はアルゴリズムの中に(擬似)乱数が含まれており、動作が決定的ではなく、乱数に依存して動きます。 有名な例では、クイックソートのアルゴリズム中にピボットを選択するところがあるのですが、そこを決定的に最初や真ん中の値ではなく、適当に乱数でランダムに選んだ場合がそれに当たります。 クイックソートは最悪計算量が要素数がnの時、O(n^2)かかってしまう問題点がありますが、ランダムにピボットを選んだ場合、かなり高い確率でO(nlogn)で動作することが言えます。もっとはっきりいうと、比較の回数がαnlogn(αは5よりちょっと大きいぐらい)より大きくなる確率は1/(n^2)以下だということが言えます。つまりnが大きい場合は殆ど間違いなくO(nlogn

    DO++ : 乱択アルゴリズム
  • http://www.cse.yorku.ca/~oz/hash.html

  • 頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏

    効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car

  • Magical Circle Engine つくりました! - inajob's blog

    http://inajob.no-ip.org:10080/mce/data/tw%3Aina_ani%3Awelcome.html 魔法陣言語の実行環境+保存環境です。 これであなたも魔法陣を作れます! 作りたてにつき変なところがあるかもですが、ぜひぜひ遊んでみてください。 チュートリアル なんとなく魔法陣の作り方をまとめてみました。 簡単な図形 キャンバス属性 プログラミング補助 制御構文 文字 演算 基図形2 include

    Magical Circle Engine つくりました! - inajob's blog
    cou929
    cou929 2011/06/12
    魔方陣!!
  • Code Jam Statistics (2011)

    Code Jam Language Stats This website presents information about programming languages used to solve the Google Code Jam problems in 2008 – 2017. Find solutions: find solutions for a specific problem in a specific language. Language popularity: lists languages used to solve Code Jam problems. Represented countries: lists the number of advancing participants by represented country. Contestants using

  • Languages used (2011) — Code Jam Statistics

    Language statisticsNumber of contestants using specific language. LanguageQualification RoundRound 1ARound 1BRound 1CRound 2Round 3Final

  • d.y.d. 初Bitsの出:解答編

    17:35 11/02/14 TLE '11 変則コードゴルフ大会 TLE に参加していました。 7位でした。無念…。終了1時間前には3位だったんですよ!(言い訳) 問題はこちら です。 自分のソースコードは sub/TLE11 こんな感じでした。 以下、ネタバレ感想など。 短いコードが知りたい方は 優勝者の解説 をご覧あれ。 COUNTI 自然数 i が入力されたら、「自分のソースコードの i バイト目に出てくる文字は、 自分のソースコードの中に、何回出現するか」を出力しよう。できるだけ短いコードで。 基的にゴルフ大会なので、どの問題も短く書ければ短いほど点数が高いです。 main(){...いつでも4を表示するコード...}//どの文字も4文字ずつになるよう足りない字をここで補充 というのを即座に思いついて、submit 開始直後に投入。 したら、主催者さんがこれでは面白くないなーと

  • TLE 優勝 - 兼雑記

    最初から最後まで全力でがんばりました。8問あって、1問は誰も解けなかったので全7問で、そのうち6問がトップなので割と文句なく1位です。最初の方は期間が2日しか無い予定だったのでとりあえず問題を全部解くのを重視してやってて、後の方は3日に期限がのびたのでゆっくりと一問一問よく見る感じでやりました。 どうでもいいコード群 http://shinh.skr.jp/dat_dir/tle2011/ ARRNG 数字の列をなんか特定の法則に従って並べる。 submit 可能になるまでには解いてたはずなんだけど、何故か通らない。 output の spec とか説明が詳しくなったりして、よく見るとフォーマット違うなーとかいう感じだったけどまだ通らない。しばらく放置してたんだけど、 tanakh さんも通らないとおっしゃってるのを見て、とりあえず ruby で解くかーと解いてみて、どうも C 的なバグは

    TLE 優勝 - 兼雑記
  • Free Dynamic DNS(DDNS) by POP3,IMAP4,FTP,HTTP-BASIC for Home Server, VPS | MyDNS.JP

    yambi.mydns.jp is not accessible... Sorry. I do not know why this site is not working. If you know Administrator of this site, please contact directly. You may be able to see it in Google cache. For administrator ... MyDNS.JP did not received IP address from you over One week. Please check your notify system. If you restart notification of IP address, MyDNS.JP will apply your IP address to DNS inf

    cou929
    cou929 2011/04/26
    bogo sort がうける
  • Link Analysis and Related Topics - Home

    2008年度 先端情報科学特論 II & IV リンク解析と周辺の話題 担当 新保 仁 shimbo@is.naist.jp 日時 2008/11/10, 11/17, 12/1, 12/8 (全 4 回) - 4限 15:10-16:40 場所 情報棟 L3 講義室 リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です. この講義ではまず, リンク解析が取り扱う 2 種類の尺度 (重要度と関連度) について述べ, それぞれの代表的な計算手法を紹介します. 後半では, 近年機械学習分野で盛んに研究されているカーネルのうち, グラフ上の節点に対して定義されたカーネル (グラフカーネル) と, そのリンク解析への応用について紹介します. 第1回 11月10日 スライド 第2回 11月17日 スライド 第3回 12月1日

    cou929
    cou929 2011/03/01
    "リンク解析は, グラフ (ネットワーク) データの構造から有用な情報を抽出するための, データマイニングの一研究分野です"
  • 情報オリンピック参加者の皆さんへ - 簡潔なQ

    情報オリンピックに参加した皆さんこんにちは。僕はqnighyです。一応すごい人です。 予選で終わってしまった人も、選で終わってしまった人も、これから合宿に行けるという人もいると思いますが、これ以降も競技プログラミングに精進したい!という人のために、いち競技者としての経験から、ちょっとアドヴァイスを書いていきたいと思います。(僕自身実践できていないものもあります。) いろいろな大会に参加しましょう。 情報オリンピック以外にも、さまざまな競技プログラミングの大会が存在します。その一例を挙げますから、ぜひとも臆せず参加してみてください。 大会に参加したり、練習したりしないと、競技プログラミングの腕は上がらないようです。 SuperCon 東工大と阪大が主催する高校生向けのコンテストです。このコンテストの最大の特徴は、大学のスーパーコンピューターを借りてコンテストを行うということです。 Supe

    情報オリンピック参加者の皆さんへ - 簡潔なQ
  • 最短路問題でよく見かける話題 - 最適化問題に対する超高速&安定計算

    最短路問題に関してアルゴリズムの教科書や授業や講演等で使用されている資料に以下のように書いてあるのを見かけることが多い。 1:ダイクストラ法においてはポテンシャル最小の点を見つける際に優先キュー(ヒープ、特に2-ヒープ)などを使用すると実行時間が速くなるが、フィボナッチヒープを使うとさらに速くなる。 ○点数を n, 枝数を m とする。2-ヒープでは計算量が O(m log n)、 フィボナッチヒープを使うと O(m + n log n) になるのだが、実際にはフィボナッチヒープを使うと実行があまり速くならない(むしろ遅い)。実用的に高速なのは ヒープ(heap)、バケット(bucket)、マルチレベルバケット(MLB)あたりのデータ構造である。 2:全対全最短路問題に対しては、1対全最短路問題に対するダイクストラ法を点の数だけ繰り返すよりもワーシャル・フロイド法(Warshall-Flo

    最短路問題でよく見かける話題 - 最適化問題に対する超高速&安定計算
  • 開発メモ: トップNソートの検討

    上位N件をソートした状態で取り出すという、いわゆる「トップNソート」の効率的な実装について検討してみた。 背景 データベースに対して、ある順序でソートした時の最初の何件かが欲しいというクエリを投げることはよくあるだろう。SNSで言えば、誰かのコンテンツの最新10件を表示するとかいう場合だ。SQLだと "ORDER BY xxx LIMIT yyy" とかいう感じ。同じような操作は全文検索システムのスコアリングでも定番である。俺もよく自分で実装するわけだが、その度に適当な試行錯誤をして時間がもったいないので、今回は入念に調べて決定版を出そうじゃないか。 全体をソートして上位を取り出せば目的は満たせるのだが、それだと無駄な計算が多い。100万件の中から上位10件だけ欲しい場合に、残りの99万9990件まで律儀にソートする必要はない。ということで、上位N件をソートして取り出すという「トップNソー