NP - アンドロイドはしあわせか
よくある間違いをここに書くことがけっこうあるなぁ。「よくある間違い」カテゴリでも作ろうかな。 クラスNPについて。 とりあえず前置きだが P : (deterministic) Polynomial NP : Nondeterministic Polynomial である。 クラス P に属する問題とは、決定問題(decision problem: 答えがyes/noの問題)のうち、決定性計算（deterministic computation, 説明は後述）によって多項式時間(Polynomial time)で解が得られる問題のことである。 多項式時間とは、その問題の解を得るまでの計算時間が、問題サイズ(problem size)の多項式関数である、ということ。 ここでの（計算複雑性理論での）時間というのは、実際の物理的な時間をどうこう言うのではなく、問題サイズに相対的な計算ステップ数（
P, NP, NP完全, NP困難 - awakia-n's blog
NP完全とNP困難の違いがわかってない自分をようやく卒業できました。 ソースはWikipedia。適当にまとめるので、詳しく知りたい人は自分でWikipediaの記事見てください。 NP問題 まず、一番わかってないといけないのが、NPとは何かということで NP≠Non-Polynomial time (非多項式時間) NP＝Non-deterministic Polynomial time（非決定性多項式時間） であるということ。 つまり、NP問題は多項式では解けない問題ではなく、「非決定性チューリングマシンによって多項式時間で解ける問題である」ということ。 非決定性チューリングマシンとは、今いる状態から次の状態に行く選択肢が複数あった時に常に解に近づく選択肢を選べる機械だと思えば良い。ここら辺は正規表現の実装とかオートマトン思い出すしかない。 問題空間を探索木としてとらえると、神のような
PとNPとNP完全とNP困難 - 大人になってからの再学習
計算複雑性の話の中で、P、NP、NP完全、NP困難というキーワードが登場する。 それぞれの違いを、字面だけから判断するのは、少し無理そう。 それで、詳しい説明を Wikipedia に求めると・・・。 ・P（Wikipedai） ・NP（Wikipedai） ・NP完全（Wikipedai） ・NP困難（Wikipedai） 大学などで正確な定義を学習していない場合には、軽く絶望することになる。 そこで、厳密ではないことをあらかじめ断ったうえで、これらを簡単に説明してみる。 （証明されていないが、前提としてNP≠P とする。これが証明できたら100万ドルもらえる。） まず、それぞれの関係は下図のように表すことができる。 図では、上のものほど難しい問題で「P≦NP≦NP完全≦NP困難」と言うことができる。 さらに次のことが言える。 ・ P は現実的な時間で解を求めることができる問題。 ・ N
Data Structure Visualization
Currently, we have visualizations for the following data structures and algorithms: Basics Stack: Array Implementation Stack: Linked List Implementation Queues: Array Implementation Queues: Linked List Implementation Lists: Array Implementation (available in java version) Lists: Linked List Implementation (available in java version) Recursion Factorial Reversing a String N-Queens Problem Indexing
Magazine
Magazine 部員の執筆した記事を掲載しています。 主に各年の文化祭で作成されたものです。 なおこのページに掲載されている全てのコンテンツのご利用に関しましては、 利用規約 をご確認ください。
東京大学 講義 UT OpenCourseWare
東京大学の講義や公開講座の映像・音声をポッドキャストでもお楽しみいただけます。東京大学が誇る「世界の叡智」をいつでも、どこでも、より多くの方々に体験していただきたいと考えています。 MIMA Search とは、UT OCW、MIT OCWに公開されている各授業のシラバスの関係を構造的に見ることができる検索システムです。MIMA Searchは、シラバスに含まれている各種の情報をもとに、検索結果を「点」と「線」でネットワーク表現します。
cs-conference-ranking.org
cs-conference-ranking.org 2024 著作権. 不許複製 プライバシーポリシー
コンピュータ科学に背を向ける学生たち
マサチューセッツ工科大学（MIT）でも、 ほかの大学と同様に、コンピュータ科学関連の学部に在籍する学生の数が減少している。このような状況を鑑み、米国は将来も技術界のリーダーであり続けられるのかを疑問視する声が上がっている。 今秋、MITの電気工学／コンピュータ学科（Department of Electrical Engineering and Computer Science:EECS）に入学する学部生は200名を下回る。昨年の入学者数は約240名、3年前には385名だった。 ラドガーズ大学のコンピュータ学科では、今年の入学者数について、ピークを迎えた数年前の入学者数6500名と比較して何千名単位で減少するものと見込んでおり、複数の科目コースを中止している。学部生にコンピュータ科学関連の科目を講義するSaul Levy教授は、学生数の減少傾向について、学生の職業観を反映したものだと述べる
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://kaiunix.cs.shinshu-u.ac.jp/Lesson/ProgLangT/2011/
http://wfasim.dyndns.org/dokuwiki/doku.php
S. Muthu Muthukrishnan's homepage
Global Offset Tables
http://bottomupcs.sourceforge.net/csbu/x3866.htm