前期の復習がてらついでに Tel Aviv UnivのDana RonのLecture Noteも見ています。 Topics in Algorithms – Sublinear Algorithms 0510.7410 http://www.eng.tau.ac.il/~danar/TOP06/index.htmこちらに載っていることも時間があればちょいちょい書いていこう…

結局、Extremal Combinatoricsを読もうかと思います。あとは時間があれば http://www-sop.inria.fr/mascotte/seminaires/AGAPE/notes のFPTに関するところと http://www.cs.huji.ac.il/~analyt/ http://www.cs.princeton.edu/courses/archive/fall07/cos597D…

とりあえず院試の結果次第だとは思うんですが。 研究室の本を色々漁ってて院試後に読めたらなと思うもののリストをさらっと。 アルゴリズムイントロダクション1〜3巻 パラパラ見た感じでは結構基本的なことかも？数学的基礎とデータ構造 (アルゴリズムイント…

Maximal Matching Matching グラフG(V,E)においてマッチングMとは隣り合うエッジの組を求めることどの2つのエッジも頂点を共有しない。 Maximal Matching Maximal Matchingとは集合Mに対して現状では集合Vの中でで集合Mの補集合からもはや選ぶエッジが存在し…

(α,ε)近似の定義 がyの(α,ε)近似とはα>1,ε をみたすこと。 考える問題の前提(この部分がDistributed computingの使用) 入力 コミュニケーションネットワーク 定義 各頂点はプロセッサー 各エッジはコミュニケーションのライン グラフは同期しており各ラウン…

Distributed computing vs. sublinear time A reduction and a distributed algorithm. Approximating vertex cover and maximal matching in sublinear time. Introduction sparse graphs(疎グラフ)EがVに対して比較的少ないグラフ dense graphs(密グラフ)E…

Estimating the Weight of the Minimum Spanning Tree Spanning Tree(以下st) あるグラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと 問題設定 入力 無向グラフG(V,E) 制限d 各エッジ(i,j)は整数の重みをもつ隣接知ると出グラフ…

Estimating the Number of Connected Components Connected Components(連結成分,以下c.cと書く) c.c内の任意の二点間を結ぶパスが存在する。 異なるc.c間にはいかなるパスも存在しない。 問題設定 入力 無向グラフG(V,E) 制限d 目標 c.cの数をcとしたとき、…

Sublinear Time Algorithms Lecture2 やる内容 Chernoff bound Estimating the number of connected components Estimating the weight of the minimum spanning tree Chernoff bound Let be m independent identically distributed random variables such t…

Graph connectivity 入力： G = (V,E), n = |V| , m = |E| , bounded degree d*1 グラフはn×dの隣接行列で与えられる 目的： グラフが連結グラフか？ 目的を以下のように変更する Gが連結性にε-closeとは、Gを連結するのに高々εdn本の枝を足せばよいことを言…

Point-set diameter distance matrix -> 距離行列について 配列iと配列jの距離を記述（iとjの距離がDij） >対称行列である（iとjの距離＝jとiの距離） 以下を満たす 入力： m×m距離行列d 目的： 直径 を求める。アルゴリズム を適当に取る d(x,y) が最大とな…

これまでの常識： 問題を解くのに入力すべてを見なければ話にならないとされていた。しかし、一部を見るだけで判断できないか？（モチベーションとしては、生体情報やネットワークグラフのようにそれ自体が巨大な量を持つ問題を解きたい） そんなことが出来…

おおざっぱに言うと、n の増大に対して計算量がどの割合で膨張するのかを示すもの。 計算式の中では一番強いものに引っ張られる。↓は代表的なもの 名前 早さ 概要 数式 例 factorial time slower nのn乗に比例した時間を費やす 巡回セールスマン問題の総当た…

スペクトルと信号処理 フーリエ変換の性質 線形性 対称性 相似性 周波数推移 周波数変換 ベースバンド信号→無限周波数へ 時間推移 共役対称性 パーセバルの定理 ここで、 を代入すると たたみ込み積分 ―――――――＞―――――――＞ インパルス h(t) 伝達関数とインパ…

今回のテーマ フーリエ変換 フーリエ逆変換 たたみこみ積分 フーリエ変換 周期関数はフーリエ級数で対応をとれた。 ではこの考えを非周期関数に適用させたものは？ →フーリエ変換周期関数の周期Tを∞にもっていけば非周期関数もフーリエ解析できるのでは？？ …

友人からNP完全とNP困難について分かりやすく説明してくれと言われたので、頑張ってまとめました。 時間計算量に関しては↓のエントリ参照。 時間計算量に関して-- http://d.hatena.ne.jp/nsasaki/20110426/1303807572そもそもNPって何？って話から。 Wikiped…

パタヘネ下巻の内容をやる授業をとったので、そちらのまとめでも。。 Chapter6 --パイプラインを用いた性能向上 6.1パイプライン処理の概要 プロセッサにおける命令の処理 例 MIPS R形式 命令のフェッチ 命令の解読 オペランド（レジスタ）の読み出し 演算 …

授業名でググると上位に出てきたので名前変更。。 この授業をとるかは分からないんだけど、授業の内容も軽くまとめようかと。使用する教科書は、オーム社の「情報通信工学」 範囲は三章と四章大学過程 情報通信工学 (大学課程)作者: 寺田浩詔,吉田進,佐藤亨,…

第四章 貴族政治、民主政治、そしてシステムデザイン この偉大な境界は比類のない芸術作品です。そこに示された協議には、無味乾燥なところも混迷したところもありません… これは様式の極致、先達らの成功のすべてを理解し、吸収した芸術家たちの作品です。…

第三章 外科手術チーム 以上の研究から、優秀な者とそうでない者との間には、格段に大きな個人差がたいていの場合あるということが分かった。 サックマン、エリソン、およびグラントより 少数精鋭が望ましい。 人によって生産性が10倍近く違うのはザラ。 コ…

Chpter3--命令:マシンの言葉 ハードウェアの設計に関する四つの基本原則 単純性は規則性につながる。 小さければ小さいほど高速になる。 優れた設計には適度な妥協が必要である。 一般的な場合を高速化せよ。 3.4 コンピューター内での命令の表現 p.105 数の…

第2章 人月の神話 おいしい料理には時間がかかります。当店がお客様をお待たせしてしまうとしたら、 それはより良いサービスでご満足していただくためなのです。 ニューオーリンズのレストラン「アントワーヌ」のメニューから プロジェクト失敗の要因 失敗し…

大学の本屋で偶然「人月の神話」を見つけた。 タイトルに引かれたので図書館から借りて、ちょびちょび読んでみた。ついでだから、2章までまとめてみた。人月の神話―狼人間を撃つ銀の弾はない (Professional computing series (別巻3))作者: Jr.,フレデリック…

Chapter 2 :確率分布 Gaussian distribution 最尤推定 minimize 不偏推定ではない！ 逐次推定 オンライン分野、データを処理ごとに捨てる。 N-1個のデータ: を追加:を加えて修正 一般化 Robbins-Monro algorithm θ , z : r.v.s with p(z , θ) z:観測値 θ:デ…

Chapter 2 :確率分布 Gaussian distribution 基本事項 X 〜 N() D次元に拡張すると… 平均 共集合 ; 対称, 正定値(実数固有値を持ち、それらが正。二次形式は楕円体になる。→p.82) パラメーターの数 … そのまま 1/2 D(D+1) 斜め楕円 対角 D 楕円 1 円 μ… D 並…

Chapter 2 :確率分布 Machine Learning unsdupervised density estimation perametric non-parametric parametric(代表的なもの) binary dist normal dist 指数型分布族 non-parametric histgram kernel K-nearest neighber 特にGaussian distributionを見て…

Chapter 2 :確率分布 プチ測度論(確率論で使える範囲) 面積を測るとは集合を測る。より一般化したもの。 Index の分解 Random variable, distribution Independent, Conditional probability sp:スペース (1)の分解 : Probability sp : sample sp 連続有無 :…

Chapter 2 :確率分布 復習 MLの流れ inference decision losss function Generative model inference 観測 仮定→ or のモデル化 discriminatative model inference: 識別関数f(x)をつくる (xからみつける) 下二つは手間がかかる。 posterior distribution が…

On Lisp読書会 第一回 一度Schemeを学んでいるので基本的な事項は結構はしょってます。 結構忘れていましたが…せっかくだからと関数型言語の利点欠点を調べたら、 関数型言語の利点 計算に本質的ではない副作用が起こらないことと。 再帰呼び出しを容易に記…

Chpter3--命令:マシンの言葉 3.1 はじめに p.96 コンピューターハードウェアに命令を伝えるには、コンピューターの言葉で話さなければならない。 コンピューター言語の言葉を命令(instruction)と呼び、 コンピューターの語彙を命令セット(instruction set)と…