タグ

algorithmとprogrammingに関するma_koのブックマーク (21)

  • プログラマのための文書推薦入門 (社内勉強会の発表資料) - y_uti のブログ

    勤務先の社内勉強会で、機械学習を用いた文書推薦*1に関する基的なことがらについて説明しました。その資料を公開します。 プログラマのための文書推薦入門 from y-uti 数学やコンピュータサイエンスを専門的に学んでいないエンジニアでも理解しやすいように、できるだけ数式を使わずに説明したつもりです。厳密性にはこだわっていないので、専門家からはあちこちツッコミを受ける内容かもしれません。 プログラマ向けということで、実際にコンピュータ上で動作を確認できるように、Wikipedia のデータを対象にして類似文書検索を行うスクリプトを作成しました。GitHub に置いてあります。 y-uti/document-recommendation · GitHub *1:推薦というより情報検索、類似文書検索という方が適切だったかもしれません。

    プログラマのための文書推薦入門 (社内勉強会の発表資料) - y_uti のブログ
  • 計算量のはなし - 赤い黒歴史を蓄積する

    どうも華麗なるキャッツパーです。キャットアッパーです。 この記事はCompetitive Programming Advent Calendar Div2013, 12/7の記事です。 私は過去に、暇に任せてこのようなスライドを作ってしまいました。 有名アルゴリズムとそれの計算量について列挙するのが楽しすぎて作ってしまいました。後悔しております。 記事では「計算量ってどうやって計算するの?」みたいな話を競プロの観点からします。 計算量とはなんぞやということについては上のスライドを読んでください。 計算量の種類 競技プログラミングで気にする計算量は2種類あります。最悪計算量と償却計算量です。 最悪計算量というのは、ある処理にどのような入力を与えても、それ以上に速い計算量になる、というもので、一種の上界です。競技プログラミングでは作問者が最悪計算量になるテストケースをかならず入れてきますから

    計算量のはなし - 赤い黒歴史を蓄積する
  • - サルでもわかる待ち行列

    (株)永和システムマネジメント   平鍋健児 作成日:初版 1999, 3/16 第2版 2002, 11/6 第3版 2004, 9/14 第4版 2008, 5/1 情報処理技術社試験の中で良く出て来る「待ち行列」理論を,直感的に覚えやすく解説してみました. 何度もトライしたけど待ち行列が理解できない人向けです. 正確な定義や論理展開は重視せず,いかに効率的にこの理論を覚えることができるかに焦点を絞ってみました.

  • 病みつきになる「動的計画法」、その深淵に迫る

    数回にわたって動的計画法・メモ化再帰について解説してきましたが、今回は実践編として、ナップサック問題への挑戦を足がかりに、その長所と短所の紹介、理解度チェックシートなどを用意しました。特に、動的計画法について深く掘り下げ、皆さんを動的計画法マスターの道にご案内します。 もしあなたが知ってしまったなら――病みつきになる動的計画法の集中講義 前回の『アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった』で動的計画法とメモ化再帰を説明しましたが、前回の説明ではまだ勘所をつかめていない方がほとんどでしょう。そこで、これらを完全にマスターするため、今回はもう1つ具体例を挙げながら練習したいと思います。 どういった問題を採用するかは悩みましたが、非常に有名な「ナップサック問題」を取り上げて説明します。 ナップサック問題とは以下のような問題です。 幾つかの品物があり、この品物にはそれぞ

    病みつきになる「動的計画法」、その深淵に迫る
  • 迷路の最短経路を求めるには? - ザリガニが見ていた...。

    相当、出遅れた感はあるが、以下の試験問題をやってみた。(Rubyで) さて試験問題です。 内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 たとえば、S:スタート G:ゴール *:壁 $:解答の経路 としたとき、 ************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************という入力に対し、 **************************

    迷路の最短経路を求めるには? - ザリガニが見ていた...。
  • 動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし(寅年)の日記

    組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP) コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各

    動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし(寅年)の日記
  • Quicksilverは如何にして鋭い検索を行っているのか? - ザリガニが見ていた...。

    Quicksilverの検索性能が、感性をくすぐってきた。 「apple」→「AppleScript Editor」 「ase」→「AppleScript Editor」 「prol」→「Property List Editor」 「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。 そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。 直近のユーザーの好みを学習してくれるのだ。 もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。 「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺

    Quicksilverは如何にして鋭い検索を行っているのか? - ザリガニが見ていた...。
    ma_ko
    ma_ko 2010/03/01
    QSは検索の一致をどうスコアリングしているのか?を掘り下げてObj-Cレベルでテストしてる。おもしろー。
  • Rubyで最短経路を探索しよう! - hp12c

    人生を書き換える者すらいた。: 人材獲得作戦・4 試験問題ほか 次に同じ質問がきたときに 「1時間いらないっしょ、こんなの」 と是非ともほざくために 今から勉強します ダイクストラ法による最短経路探索 図におけるS点からG点に到達するための最短経路を求めたい 各ノードを結ぶエッジを糸としてS点をゆっくりと持ち上げた場合 緊張する糸が変移しながら最終的にS−B−D−Gを結ぶ糸が緊張して これが最短経路と分かる*1 計算機上でこの現象をシミュレートしたものを ダイクストラ法というらしい 今各ノードとそこから伸びるエッジの情報(コストと接続先)を渡して その最短経路および総コストを出力するプログラムを考えてみよう data = { :s => [[5, :a], [4, :b], [2, :c]], :a => [[5, :s], [2, :b], [6, :g]], :b => [[4, :s

    Rubyで最短経路を探索しよう! - hp12c
  • 知れば天国、知らねば地獄――「探索」虎の巻

    いよいよ今回から、具体的なアルゴリズムの紹介に入っていきます。今回は、プログラミングにおける重要な概念である「探索」について考えます。グラフに変換し、探索する、という流れを知るとともに、そのグラフを効率よく探索する方法について紹介します。 今後紹介していくアルゴリズムについて お待たせしました! 「最強最速アルゴリズマー養成講座」という連載タイトルのとおり、今回の連載からいよいよ具体的なアルゴリズムの紹介に入っていきたいと思います。 しかし、それを読んでいただく前に、1つ注意してもらいたいことがあります。連載第3回でもお伝えしたように、「問題を、既存の適当なアルゴリズムに当てはめる」という考え方は、非常に危険である、ということです。 筆者の経験上、TopCoderでRedCoder以上を目指すのであれば、回答時間短縮のために、いままでのパターンを利用するのも方法の1つなのですが、連載では

    知れば天国、知らねば地獄――「探索」虎の巻
  • 人材獲得作戦の試験問題を解いてみた - 良いもの。悪いもの。はてな部屋

    出遅れた感があるけど、人材獲得作戦の試験問題をPythonで解いてみた。もちろん、調べたりググったりするの禁止で。というかググればコピペで終わりのような気がする。今回はゆるめの記事なので、メインのブログではなく、こちらに書いておく。 普通にダイクストラ法で書いたけど、何故か40分もかかった。途中でコードが気に入らなくて最初から書き直したり、ケアレスミスの修正をしたりしたからか。それにしてもすっきりしないコードだ。INFを100000で決め打ちしていたりとか、優先順位付きキューを用いていなかったりとか、周りに壁があること前提だとか。いろいろひどいなぁ。 これだけじゃ面白くないので、ダイクストラ法とA*アルゴリズムの違いを説明してみる。ダイクストラ法はスタート地点から順に隣接するノードの距離を足し合わせていき、常に最も距離の短いノードからそれに隣接するノードを調べていく方法で、A*は距離を足し

    人材獲得作戦の試験問題を解いてみた - 良いもの。悪いもの。はてな部屋
    ma_ko
    ma_ko 2010/01/13
    "ダイクストラ法とA*アルゴリズム"
  • 足し算引き算で10を作るゲームと部分和問題、DP - 素人がプログラミングを勉強していたブログ

    切符の問題 切符の裏に印刷してある4桁の数字を4つの数字と考えて、足し算と引き算だけで10を作るゲームの解き方。 例えば、1,2,3,4の場合は1+2+3+4=10。 プログラム的には、 prob([1,2,3,4]); // [{plus: [1,2,3,4], minus: []}] こんな感じに返ってくるようにしたい。 まず、2,4,5,7から10を作る場合。2+4+5+7=18であるので、上記の式のいくつかの符号を-にすればいいことが分かる。一つの数字を引くと、18を出す時に最初に足した分と、今引こうとしている分の2つ引かなければならないから、逆算して、(18-10)/2=4を引けばいいと分かる。 この場合、合計が4になる組合せは、4そのものしかないから、2-4+5+7=10、が答えと分かる。 (合計-10)/2が引く数の合計で、それ以外が足す数である。2で割っているので、全部の数

    足し算引き算で10を作るゲームと部分和問題、DP - 素人がプログラミングを勉強していたブログ
    ma_ko
    ma_ko 2009/12/25
    あとでなぞってみる
  • Blogopolisから学ぶ計算幾何 記事一覧 | gihyo.jp

    運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します⁠。個別にライセンスが設定されている記事等はそのライセンスに従います。

    Blogopolisから学ぶ計算幾何 記事一覧 | gihyo.jp
  • Rubyでもっとも重要なライブラリは何か?PageRankで計算してみた - aike’s blog

    最近、PageRankを計算するPHPソースコードを公開している人がいたので、Rubyで書き直してみました。 PHPからRubyへは移植というよりほとんど写経のような感じでそのままポーティングできます。 pagerank.rb #!/usr/bin/ruby # original PHP source http://phpir.com/pagerank-in-php def calculatePageRank(linkGraph, dampingFactor = 0.15) pageRank = Hash.new tempRank = Hash.new nodeCount = linkGraph.length linkGraph.each {|node, outbound| pageRank[node] = 1/nodeCount tempRank[node] = 0 } change =

    Rubyでもっとも重要なライブラリは何か?PageRankで計算してみた - aike’s blog
  • 404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)

    2007年12月04日08:30 カテゴリアルゴリズム百選Math アルゴリズム百選 - 二分探索(binary search) 今回は二分探索を取り上げます。 検索:コンピューターの最もよくある利用法 「二分探索って何?」「ググレカス」と言われないためにこの記事は存在するのですが、Webの検索に限らず、「目的のデータを見つけて取り出す」というのは、およそコンピューターの利用法で最もポピュラーなものです。 配列:コンピューターがデータを扱う根的な方法 そのデータはコンピューターのなかでどう置かれているかというと、非常に単純です。デジタル化されたデータ=数値が一定間隔で並んでいるだけです。こういうデータ構造を、配列(array)といい、この数値一個一個のことを要素(element)と言います。 現代のコンピューターでは、最小要素はバイト(byte)と呼ばれています。このバイトの中には0と1

    404 Blog Not Found:アルゴリズム百選 - 二分探索(binary search)
  • 計算物理のためのC/C++言語入門

    Last revised on May 25, 2000 UNIX & XWindow 環境における C/C++プログラミング言語の基礎とその計算物理への応用を解説します。 このホームページの古い版の偽ミラーサイトが存在するのでご注意ください。 物のサイトは http://www-cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/ です。 前書き 推奨図書一覧 C言語とC++言語の基礎文法の初心者向け解説 (プログラム初心者を対象としたC/C++言語の入門です) 第1章 C言語とC++言語の役割 第2章 簡単な計算 第3章 ループで繰り返し計算 第4章 配列で大量データ処理 第5章 関数で計算の分担 第6章 文字列の操作 第7章 ファイルの操作 第8章 グラフィック(XWindow System利用者向け) 高校物理の計算例 (高校生を対象として初歩的な物

  • Spaghetti Source - 各種アルゴリズムの C++ による実装

    ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基 テンプレート グラフ

  • ACM/ICPC国内予選突破の手引き

    ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日,アジア地区予選会津大会は2008年10月25日~27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。 ここではACM/ICPC(ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest)で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。 結局のところ,ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが,出題される問題の多くはいくつかのカテゴリ,例えば探索問題やグラフ問題,あるいは幾何問題などに分類することができます。 つまり,「傾向と対策」が存在します。

  • マルコフ連鎖で日本語をもっともらしく要約する - ザリガニが見ていた...。

    そもそも、マルコフ連鎖とは何なのか?全く聞いたこともなかった。そして、文章を要約するのはとっても高度なことだと思っていて、自分のレベルではその方法を、今まで思い付きもしなかった。 しかし、以下のようなシンプルなRubyコードでそれが出来てしまうと知った時、目から鱗である...。一体、何がどうなっているのだ?コードを追いながら、マルコフ連鎖を利用するという発想の素晴らしさを知った! 作業環境 MacBook OSX 10.5.7 ruby 1.8.6 (2008-08-11 patchlevel 287) [universal-darwin9.0] mecab utf8環境でインストール済み マルコフ連鎖に出逢う rssを流し読みしていると、以下の日記に目が止まった。(素晴らしい情報に感謝です!) MeCabを使ってマルコフ連鎖 一体何が出来るコードなのか、日記を読んだだけではピンと来なかっ

    マルコフ連鎖で日本語をもっともらしく要約する - ザリガニが見ていた...。
  • ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室

    ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ(http://ysfactory.nobody.jp/ys/prg/calculation_public.html) ダメージの計算式 エンカウントについて考えてみる エンカウント(マップでの敵との遭遇)の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の

    ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
    ma_ko
    ma_ko 2009/07/01
    オセロとかちょうど良い。最近iPhoneで遊んでたのでw
  • algorithm

    奥村晴彦さんの「C言語による最新アルゴリズム事典」技術評論社、1991年、の C 言語プログラムの Ruby への翻訳に挑戦します。プログラムの説明は同書を読んでください。変換はできるだけ逐語的に行っています。プログラムの動作は原作の C プログラムのそれと比較してチェックしていますが、うまく動作しないときは C から Ruby への変換のさいに起きたものです。バグレポートは tnomura@mnet.ne.jp までお願いします。 この Ruby 翻訳版はできるだけレイアウトも含めて原作の C プログラムを変更しないようにしたため、必ずしもRuby らしいコーディングスタイルとは言えないかもしれませんが、プログラムがきちんと動作することを優先しました。C から Ruby への翻訳の著作権に関しては Ruby のライセンスに準じます。配布、改変は自由です。ただし、プログラム体には原作者の