巨人の肩の上に登る

先人の積み重ねた発見に基づいて、なにかを発見しようとすることを指す。

Algorithm

Clojureでナップサック問題を動的計画法で解く

ナップサック問題とは ある容量Cのナップサックと,n個の品物が与えられたとする.n個の品物は,それぞれ異なる容量Ciと価値piだとする.このとき,ナップサックの容量Cを超えない範囲で,品物の価値の総和を最大にする組み合わせを求める. 詳しくは,ナッ…

Scala でロジスティック回帰

サイボウズ・ラボの @shuyo さんの連載でロジスティック回帰を Python で実装されていたので,Scalaでも実装してみた.第18回 ロジスティック回帰 ロジスティック回帰とは ロジスティック回帰は,基本的にはパーセプトロンと同様に分類器です.パーセプトロ…

遺伝的アルゴリズムをやってみた

遺伝的アルゴリズムを Cython で実装してみたGithub. 遺伝的アルゴリズムとは ざっくりと説明すると, 初期値として,N個の個体を無作為に生成する 評価関数を用いて,上位のM個の個体を選ぶ(エリート主義) 一定の確率に従い,交差や突然変異を行い,N個…

Scala でパーセプトロン

久しぶりにScalaを使うことになったので,練習がてらに Scala でパーセプトロンを書いてみた. 二次元データを対象とし,シンプルに実装してみた.(GitHubで公開) テスト 今回は Scalatest のFlatSpecを使ってみた. sbt 環境での使い方は,公式のUsing Sc…

挿入ソート

単純なソートアルゴリズム. 計算量は O(n2). 空リストは整列されているものとする 整列しているリストに対して,1つの要素を正しい場所に挿入する insert :: Ord a => a -> [a] -> [a] insert x [ ] = [x] insert x (y:ys) | x <= y = x : y : ys | other…

マージソート

ボトムアップの分割統治法を用いたソートアルゴリズム. データを分割する 各々をソートする マージする 以下 haskell の実装(安定ソートではない) merge :: Ord a => [a] -> [a] -> [a] merge [ ] [ ] = [ ] merge xs [ ] = xs merge [ ] ys = ys merge (…

ユークリッドの互除法

ユークリッドの互除法は,2つの自然数または整数の最大公約数(Greatest Common Divisor)を求めるアルゴリズムです. 入力を m, n (m ≧ n) とする。 n = 0 なら、 m を出力してアルゴリズムを終了する。 m を n で割った余りを新たに n とし、更に 元のnを…