【SFC授業ノート】第7回『最適化の数理』(青野 真士)「計算複雑性」11/12(月)5限

役に立ったらどんどんシェアしてね!

この記事は 816 文字約 2 分で読めます。




 

 

スポンサードサーチ





授業概要

 

 

今日は課題が出るんだけど、これが結構むずい。

 

 

授業ノート

 

 

なんかよくわからないけど、マスマティカにはいろんな情報が入ってるらしく、

 

日本の都市の人口とか、緯度経度とか、会社の株価とか、

 

そしてそれを一瞬でグラフ化できるらしい。

 

かなり便利だけど、使い方むずい。

 

今日は時間計算量

 

ランダウ記法

 

空間計算量

 

時間と空間の最大の違いは、

再利用可能かどうか。

 

時間は戻れない。

が、空間は何度でも使える。

 

決定性チューリングマシン

道筋が1つに決まる。

時間は道筋の長さ。

 

非決定性チューリングマシン

分岐がある。

時間は、最初に到達したゴールまでの長さ。

 

複雑性クラスP

決定性チューリングマシンの場合。

手に負える問題。

そこまで時間がかからない。

 

最短経路問題や、最小スパニングツリー問題なこれに当たる。

 

複雑性クラスNP

非決定性チューリングマシンの場合。

答えは簡単に見つかるけど、それを検証するのに時間がかかる問題。

 

P≠NP問題

充足可能性問題

 

 

ロボネコヤマト

自動運転の配達。

 

藤沢市はロボット開発特区。

都内とかではできないこともできる。

タンパク質フォールディング問題

 

タンパク質はアミノ酸が折りたたまれている=フォールディング

 

自然界はNP完全問題よりも難しい問題を一瞬で解いてる!



スポンサードサーチ



役に立ったらどんどんシェアしてね!

コメントを残す