タグ

algorithmに関するJxckのブックマーク (10)

  • 文字列アルゴリズムの学びかた - Hatena Developer Blog

    こんにちは!はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか? grep はどのように文字列を検索しているのか? MeCab はどうやって辞書を高速にルックアップしているのか? パーサやコンパイラを作りたいけど、何から始めればいいのか? 稿では、「文字列アルゴリズムとはどんなものなのか?」「なぜ重要なのか?」「何を知っておくべきか?」「どうやって勉強すればいいのか?」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに

    文字列アルゴリズムの学びかた - Hatena Developer Blog
  • 勾配降下法の最適化アルゴリズムを概観する | POSTD

    (編注:2020/10/01、2016/07/29、いただいたフィードバックをもとに記事を修正いたしました。) 目次: さまざまな勾配降下法 バッチ勾配降下法 確率的勾配降下法 ミニバッチ勾配降下法 課題 勾配降下法を最適化するアルゴリズム Momentum(慣性) Nesterovの加速勾配降下法 Adagrad Adadelta RMSprop Adam アルゴリズムの可視化 どのオプティマイザを選ぶべき? SGDの並列化と分散化 Hogwild! Downpour SGD SGDのための遅延耐性アルゴリズム TensorFlow Elastic Averaging SGD 最適化されたSGDに対する更なる戦略 シャッフル学習とカリキュラム学習 バッチ正規化 早期終了 勾配ノイズ 結論 参考文献 勾配降下法は、最適化のための最も知られたアルゴリズムの1つです。これまではニューラルネット

    勾配降下法の最適化アルゴリズムを概観する | POSTD
  • 計算量とBig-O記法 - 素人がプログラミングを勉強していたブログ

    プログラマであればアルゴリズムに関する話で、O(n)だとかO(log n)だとか、O(n2)だとか、そういった記号を目にすることはよくあると思う。 なんとなく、log n < n < n2の順に計算量が増加していくとかそういうことも知っていると思うが、計算量の増加とは何か説明しろと言われると、なかなか難しいと思う。この記事では高校数学レベルでわかるように考えていきたい。 まず、計算にかかる時間を、nを入力のサイズとしてf(n)を計算にかかる最大時間を返す関数とすると、計算量一般を、O(f(n))という、入力に対する計算時間の増加率として定義することができる(より厳密には、f:R+ -> R+ where R+=[0,∞)で、a>bであればf(a) >= f(b)であるとき)。 g(n) = n ^ 2 はn = 1に対して1を返す一方、より増加率の低い h(n) = n + 100 は、n

    計算量とBig-O記法 - 素人がプログラミングを勉強していたブログ
  • 動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング

    この記事は、Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83)の8日目の記事です。 動的計画法(Dynamic Programming, DP)についての記事です。 12/9 前編にサンプルプログラム(http://ideone.com/2B7f4v)を追加しました 12/11 前編の図2つを差し替えました。 はじめに まずは、やネットの資料で、動的計画法についてのすばらしい解説はいろいろありますので、まずはそれらを参考に。 プログラミングコンテストでの動的計画法 http://www.slideshare.net/iwiwi/ss-3578511 最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メ

    動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる - じじいのプログラミング
  • Basic Data Structures and Algorithms in the Linux Kernel - The Phrygian Cap

    Thanks to Vijay D'Silva's brilliant answer in cstheory.stackexchange.com I have been reading some of the famous data structures and algorithms used in the Linux Kernel. And so can you. Linked lists, doubly linked lists, lock-free linked lists.B+ Trees with comments telling you what you can't find in the textbooks.Priority sorted lists used for mutexes, drivers, etc.Red-Black trees are used are use

  • オンライン学習 2013 Q1 - As a Futurist...

    尊敬する mootoh さんに勧められて、僕もこの 6 週間アルゴリズムの勉強に取り組みました。錆びついたマシンガンどころか、そもそも竹槍しかもってない状態で飛び込んだにしては頑張ったほうじゃないかと思いますので、自分を褒めてあげたいと思います。 Algorithms, Part I | Coursera Kevin Wayne and Robert Sedgewick, Princeton University あわせて読みたい Motohiro Takayama • Coursera, 2013 Q1 所感 そもそもアルゴリズムとデータ構造、ちゃんと教科書で勉強したことなくて、大学の講義でチラッと聞いたのと情報処理の資格の勉強の時にかじった程度の僕に取っては、新鮮なことが多くて大変ためになりました。ちなみに、なぜかこれの直前にいきなり Ruby で B+Tree を実装してたのは何かの

    オンライン学習 2013 Q1 - As a Futurist...
    Jxck
    Jxck 2013/05/29
    アルゴリズム学習
  • Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

    Hi there!  This webpage covers the space and time Big-O complexities of common algorithms used in Computer Science.  When preparing for technical interviews in the past, I found myself spending hours crawling the internet putting together the best, average, and worst case complexities for search and sorting algorithms so that I wouldn't be stumped when asked about them.  Over the last few years, I

    Jxck
    Jxck 2013/05/06
    計算量チートシート
  • アルゴリズムを学ぼう

    関連サイト出版社による関連ページが公開されています。 アルゴリズムを学ぼう (KADOKAWA/アスキー・メディアワークス) 関連書籍書の続編『続・アルゴリズムを学ぼう』も好評発売中です。 内容紹介書のテーマは、ガチのアルゴリズムとデータ構造、そして計算量です。 いや、確かに書は女の子がいろいろでてきたり、小話が入っていたりと、ゆるふわなオーラが漂っています。しかし、あえていいましょう。それは、見かけだけである、と。 プログラミングを学ぶにあたって、アルゴリズムとデータ構造は、どの言語を用いるにしてもすべての基礎であり、避けて通ることはできない道です。アルゴリズムとデータ構造を知らずにプログラムを書くことは、無免許で車を運転するぐらいに危険な行為です。 しかし、アルゴリズムとデータ構造をきちんと理解せずに、プログラムを書いているプログラマーが多数いるのも事実です。それは、アルゴリズム

    アルゴリズムを学ぼう
    Jxck
    Jxck 2012/06/01
    ちょうど良いから、これ買って全部 haskell で実装するみたいなトレーニングありかも。
  • 頻出典型アルゴリズムの演習問題としてよさげなやつ - 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

  • プログラミングコンテストでの動的計画法

    2. はじめに • 「動的計画法」は英語で 「Dynamic Programming」 と言います. • 略して「DP」とよく呼ばれます. • スライドでも以後使います. 4. ナップサック問題とは? • n 個の品物がある • 品物 i は重さ wi, 価値 vi • 重さの合計が U を超えないように選ぶ – 1 つの品物は 1 つまで • この時の価値の合計の最大値は? 品物 1 品物 2 品物 n 重さ w1 重さ w2 ・・・ 重さ wn 価値 v1 価値 v2 価値 vn 5. ナップサック問題の例 品物 1 品物 2 品物 3 品物 4 U=5 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v2 = 2 v3 = 4 v4 = 2 品物 1 品物 2 品物 3 品物 4 答え 7 w1 = 2 w2 = 1 w3 = 3 w4 = 2 v1 = 3 v

    プログラミングコンテストでの動的計画法
  • 1