僕は星野源が好きだ。フィルムがJwaveで繰り返し流れていた頃から好きだ。ライブには一度も行ったことはないが、CDの初回限定版を買うくらいは好きである。要するに熱狂的なファンではない。好きのレベルはそのくらいだが、先日本屋に行った時にこの本を見つ…

グラフの表現の理解を問う問題である． 隣接リスト表現から隣接行列表現へ変換する処理を実装する． 隣接リスト表現（Adjacency List) ・有限グラフを表現するためのリスト・1つのリストが1つの頂点に対応して，隣接するノードが接続 隣接行列表現（Adjacenc…

根付き木，二分木に続いて二分探索木を実装する． 二分探索木(Binary Search Tree) ・内部接点はが {キー，左部部分木， 右部分木} を持つような根付き木． ・二分探索木条件(Binary search tree property)を満たす木． 二分探索木条件: 左部分木の根 <= キ…

二分木を実装させる問題である． tooshitaka.hatenablog.com とほとんど同じだ． まず用語の整理からする． 二分木 ・ノードの子の数が最大でも2である木． ・子は左，右と区別される． ノードの高さ ・木の最下段からへのパスを考えたとき，通る辺の数． ノ…

入力を根付き木として保存する問題である． ノードの深さ，種類（根，内部ノード，葉），深さも答えさせるのでそれぞれの概念の定義をきちんと理解する必要がある． 木（Tree） ・連結で閉路をもたないグラフ． ・木について話すときは頂点（Vertex）をノー…

そらで書けないと恥ずかしいバブルソートを実装する． 特徴 ・「泡がぶくぶく．．．」という説明で有名 ・ 配列の要素数が大きい場合は計算量が大きくなるので非実用的 アルゴリズム Bubblesort(A) n = A.length for i = 0 to n - 1 for j = n - 1 downto 1 …

計数ソート（Counting sort）を実装する． 特徴 配列の要素をキーとするソートアルゴリズム キーを要素とする別の配列を用意して出現頻度と累積和を計算 累積和から任意のキー以下の要素数がわかり，正しい位置に要素を代入 アルゴリズム A: ソートする配列…

情報系の学生ならみんな知っているクイックソートを解く． 自分は学部時代にやったはずだが，まったく覚えていなかった． 特徴 配列を分割統治でソートするアルゴリズム 配列を2つに分割する際におおまかにソート（Partitionアルゴリズム） 分割した配列を引…

クイックソートで使うPartitionを実装する． 特徴 ・閾値以下か，それより大きかで配列を分割するアルゴリズム． ・閾値で分けるだけなので全体はソートされない． アルゴリズム Partition(A, l, r) threshold = A[r] i = l - 1 for j = l to r - 1 if A[j] …

AOJのマージソートを実装する問題です． 特徴 ・分割統治と再帰を上手く使ったソーティングアルゴリズム ・配列を1要素になるまで分割してくっつき直すときに比較． アルゴリズム Mergesort(array, left, right) 要素数が1ならソート済みなのでreturn．（実…

挿入ソートを実装する． 特徴 未ソート部とソート済み部に分けてソート トランプの手札を並べ替える感じ 挿入ソートの改良版がシェルソート アルゴリズム これ． www.youtube.com 二重ループの外側と内側の進む向きが違うので注意． 計算量 内側のループのた…

http://www.phontron.com/slides/neubig15nlptutorial.pdf グラムニュービック先生が書いたチュートリアルスライドである． とても良い． 最近は論文を読むときに，このスライド通りに書かれているか自分の頭の中でチェックしている．たまにチェック項目を忘…

http://hflab.k.u-tokyo.ac.jp/staff/hori/essay/kenkyuu.html を読んだ． 東京大学の堀先生という方のエッセイである． 博士課程の学生or目指している学生に向けた内容だが，修士の学生も読んでピンとくるものがあるだろう． 研究を（まじめに）する学生は…

物体検出や顔検出とかで必要になるSlidingWindowのメモ 参考 funvision.blogspot.jp 上のサイトを見れば問題なかった． StepSideを小さくするとちょっとずつパッチ切り取るようになる． あとはこのパッチから特徴抽出とかして分類器にぶち込めばいいのかな？…

巷ではディープラーニングが流行っていますがdlibを使ってサポートベクトルマシーンをやってみる話です． 結論からいうと 凄い使いやすかった． いい感じに抽象化されている． パラメータの調整も何をやっているのか分かりやすい． てな感じ． この記事では…