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形式 命令のフェッチ 命令の解読 オペランド（レジスタ）の読み出し 演算 …

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