サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
ノーベル賞
edu.net.c.dendai.ac.jp
第 10 回 NP完全問題 本日の内容 10-1. Cook の定理 10-2. 巡回セールスマン問題は NP 完全問題 10-1. Cook の定理 論理式の充足可能性問題は NP 完全である。 論理式の充足可能性問題(SAT: Satisfiability) とは与えられた 論理式を真にするような変数の割当が存在するかどうかを判定する問題です。 これは、変数の割当を非決定的に guess して、実際に論理式に代入して真か どうかを判定できますので、 NP に含まれる問題です。 これが NP 完全問題であることを示すには、NP に含まれるあらゆる問題が SAT に reducible であることを示さなければなりません。 そこで、 素朴な NP 完全問題である CNP を SAT に変換することを考えま す。 つまり、NP に含まれるある問題の入力 x が与えられた時、その問題を解く非
アルゴリズム入門 このドキュメントは http://edu.net.c.dendai.ac.jp/introduction/algorithm.html から入手できます。 今日の問題 本日の講義内容の要約をA4用紙の表面にまとめなさい。 なお、気が向いたら講義の感想を裏面に書いていただけるとありがたいです。 自己紹介 ネットワークシステム研究室 坂本直志 専門分野 分散アルゴリズム 乱数を使った計算 計算量理論 ネットワークシステムの評価 マイコン 通信行動工学 研究室の紹介 分散アルゴリズム 複数のコンピュータで同じプログラムを動かし、ネットワーク上で協調させて動かすようなシステムの開発 クライアント/サーバー WWW などのクライアント/サーバーシステムの評価や改良 ネットワークの評価 Ethernet などのネットワークシステムの評価 コンピュータによるネットワークの管理 コンピュ
第 8 回 TCP(2) 本日の内容 8-1. TCP のフロー制御 8-2. ソケット このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。 8-1. TCP のフロー制御 受信者のウィンドウ制御 送信者が通信量を制限しない場合、どのようなことが起こるでしょうか。 ここでは送信者、受信者とも 1Gbps のネットワークにつながっており、中間 に 10 Mbps のネットワークがあったとしましょう。 TCP の接続の時、受信者は 1Gbit を同時に受信可能と送信者に報 告したとします。 このとき、送信者がその値を真に受けて、1Gbit まで同時に送るとどのような ことが起きるでしょうか? 前回のセルフクロックではルータに理想的なバッファがあることを仮定してま した。 このような仮定では、セルフクロックによりもっとも遅いネッ トワークであ
第 6 回 ソーティングネットワーク 本日の内容 6-1. 前回の復習 6-2. 並列計算 6-3. ソーティングネットワーク 6-4. O(nlog n) Sorting Network このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。 6-1. 前回の復習 6-2. 並列計算 並列計算とは複数のプロセッサを使って問題を解く計算モデルです。 モデルには大きく分けて二つがあります。 PRAM(Parallel Random Access Machine) RAM とは通常のコンピュータと同様、メモリにランダムアクセスできる計算機 モデルです。 複数の RAM が共有メモリによりメッセージ交換を行いながら計算を行うのが PRAM です。 回路 入力、出力の幅が定数長で、定数時間で一定の計算を行うゲート と呼びます。 このゲートの出力を他
講義資料 EC科 1 年 情報通信メディア基礎, NC科 1 年情報通信基礎 「アルゴリズム入門」 EC科 3 年前期 情報ネットワーク NC科 2 年前期 データ構造とアルゴリズム EC 科 2 年情報通信基礎実験 WEB 演習 EC科 3 年後期 データ構造とアルゴリズムII EC科 2年後期ハードウェア演習A / 3 年後期 マイコン基礎及び実習 大学院 アルゴリズム論 AD科 2 年後期 通信とネットワーク(2019) NC科実践知重点課程 情報の安全・安心工学(2019) EC科 4 年 情報通信プロジェクトモバイルゲーム班(2019) EC科 1 年 情報通信メディア基礎「携帯電話のつながる仕組み」(2018) EC科 3 年後期 特別プログラミング演習(2018) EC科 4 年 情報通信プロジェクト3Dプリンタ班(2018) グループスタディ(2015) EC科 2 年後期
講義資料 第 1 回 Turing 機械 第 2 回 Turing 機械のプログラミング 第 3 回 計算量理論 第 4 回 万能 Turing 機械 第 5 回 停止問題 第 6 回 線形加速定理、階層定理(2003.5.27 改訂、2003.6.3 三訂) 第 7 回 下限 第 8 回 非決定性(1),オートマトン 第 9 回 非決定性(2)、完全問題 第 10 回 NP完全問題 レポート 同じ問題を解く計算量の異なる二つのプログラムを書き、計算量を評価しなさい。 締切 2003 年 7 月 8 日 参考文献 坂本直志 <sakamoto@c.dendai.ac.jp> 東京電機大学工学部情報通信工学科
このページを最初にブックマークしてみませんか?
『Resources of lectures of Naoshi SAKAMOTO』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く