コンピュータサイエンスの授業をします。 初心者に、計算量のオーダーについて教えたいのですが、 [1] ソート以外の、 [2] 面白く [3] 理解が簡単な問題で、 [4]…
コンピュータサイエンスの授業をします。 初心者に、計算量のオーダーについて教えたいのですが、 [1] ソート以外の、 [2] 面白く [3] 理解が簡単な問題で、 [4] 複数の解くアルゴリズム(4つ以上)があり、 [5] [4]の計算量のオーダーがそれぞれ違う(以下の内、4つ以上を含むのが望ましい) https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#.E4.B8.80.E8.88.AC.E7.9A.84.E3.81.AA.E3.82.AA.E3.83.BC.E3.83.80.E3.83.BC ような問題をご存じでしたら教えて下さい。 難しい注文かとは思いますが、よろしくお願いいたします。
Complexity Zoo - Qwiki
Introduction Welcome to the Complexity Zoo... There are now 493 classes and counting! Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z Lists of related classes: Communication Complexity - Hierarchies - Nonuniform This information was originally moved from http://www.complexityzoo.com/ in August 2005, and i
ゲームと困難性 - 186 @ hatenablog
前置き CiNii - ぷよぷよはNP完全 はてなブックマーク - CiNii - ぷよぷよはNP完全 全て頭に一般化が付きます. 色々結果はありますが, 問題の定式化によって当然難しさが変わりますのでご注意を. 定義は元論文を見て確認してください. 2人ゲーム オセロ PSPACE完全 (岩田, 笠井 1994) 将棋 EXPTIME完全 (安達, 亀川, 岩田 1987) 囲碁 EXPTIME完全 チェッカー EXPTIME完全 (Robson 1984) チェス EXPTIME完全 一般化しりとり PSPACE完全 マスターマインド NP完全 (de Bondt 2004, Stuckman and Zhang 2005) 一般化アマゾン PSPACE完全 (清見, 宇野 2005) シャノンのスイッチングゲーム PSPACE完全 1人ゲーム 一般化詰め将棋 EXPTIME完全 (横
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
