計算量理論

ブログネタ：ノートは方眼？線？無地？ 参加中

線でいいです。
基本書ければ何でも構わないけど、無地だと歪みがｷﾆﾅﾙし、
方眼はマス目をはみ出せない、そんな性格です。

そして、ノートと言えば。

「計算量理論」という計算の複雑さの理論の概念や応用についての公開講座に
以前参加し、私なりにまとめた覚書が発掘されました(°∀°)b

数学のノ～ベル賞といわれるゲ～テル賞を受賞された、戸田　誠之助教授による
「解き易さと解き難さの境界を求めて」
これが講義のテ～マなのですが、これだけだとなんのことやらかなり引いてしまいます。
　
でも、出来るだけ専門用語を使わずに話されたので、
高校で数学リタイヤ組の私も安心して参加することが出来ました。

何だかワクワクする数学の話、
興味のある方はどうぞご覧になってください。
そして、もしこれ以降、研究が進んでいたら教えてください。

◆◇◆◇◆◇◆◇◆◇　　　　◆◇◆◇◆◇◆◇◆◇

「解き易さと解きにくさの境界を求めて」

　日大文理学部　戸田　誠之助教授

計算の複雑さの理論を「計算量理論」という
　
（目的）情報処理の問題に関して、解き易いものと解き難いものの違いを見つける

１．”解き難さ”を応用する

　＜計算の一方向性＞

　計算には解き易い方向と、解き難い方向がある
　例えば、ある計算式を例に出すと

　ーーーーーーーーーーーーーー→
　３７９×６４７＝２４５２１３
　←ーーーーーーーーーーーーーー

　この場合、左から右へは筆算や電卓を使えば容易に解けるが、
　逆に右から左へは因数分解を用いないと解けず、解き難いとされる

　このことを「計算の一方向性」という

　＜公開鍵暗号システム＞

　ある数は一通りの素数と素数の組み合わせで出来ているという事実と、
　上記の計算の一方向性を応用したシステム

　インタ～ネットのオンラインショッピングを利用する際に使われている
　電子印鑑・電子署名という電子認証システムのこと
　購入者と商品を提供する企業以外の者から、重要な内容を守るためのもの

　（原理イメ～ジ）3本の鍵と一つの箱があるとします

　　Ａ鍵　　　←　　　箱　　　←　　Ｂ鍵　　Ｃ鍵

　素数×素数+α　　因数分解+α　　素数　　素数
　

　この場合ＢとＣの鍵からＡ鍵は作り易いが、逆は難しくなります＜計算の一方向性＞

　さらに箱には3つの鍵穴のついた面が二つあり、それぞれ、

　■・Ａ鍵で閉められ、ＢとＣ鍵で開けられる面
　□・ＢとＣ鍵で閉められ、Ａ鍵で開けられる面

　また、Ａ鍵は誰でも使える鍵で（企業も持っている）
　ＢとＣ鍵は購入者しか持っていないとと仮定します

　企業がＡ鍵を持っている場合、情報を箱に入れ■面に鍵をかけ、購入者に送ります
　受け取った購入者は持っているＢとＣの鍵をふたつ使い、■面で開けます

　そして、また折り返し箱に情報を入れ、ＢとＣ鍵で□面に施錠し、企業へ返送します
　この□面を開けられるのはＡ鍵ですが、閉めることが出来ません

　これにより、万が一途中で第三者にＡ鍵で箱が開けられるようなことがあったとしても
　その鍵では一度開けた箱の□を閉める事が出来ない為、「箱が開けられた」ことがわかるのです

　

２・”解き難さ”の概念

　コンピュ～タ～の性能が大幅に向上してきたが、計算論の立場からいうと
　身近に発生する問題の多くはほとんど出来ていない状態であるとのこと

　例えば、
　・計画表、スケジュ～ル表
　・航路世界一周の巡回路決定
　・ＭＤの詰め込み、等など・・

　解き難さを表わす概念を＜ＮＰ完全概念＞と言います

　ＮＰ・・・Nondeterministic Polynomial Time（非決定性多項式時間）

　身近に発生する難しいとされる問題の多くは、実はある単純な性質を持っていて
　その答えを示されれば、合っているかを判断するのは易しいとされれいます

　例えば因数分解。答えから「これは何と何をかけたものか」と問題を聞かれたら難しいが
　正解を示されればその正否の判断は易しい

　例えば分割問題。１００の整数を並べられ、「これを総和が同じになるように分ける」よう
　言われたら難しいが、あらかじめ分けられた数字の総和を確かめるのは易しい

　戸田教授の経験的事実として、
　身近な問題の多くは「ＮＰ完全問題」であり、本当はＮＰで解き易い性質を持っているのに、
　ＮＰかどうか分からない問題と言えるそうです
　ちなみに将棋やチェスなどの「二人ゲ～ム」は例外で、コンピュ～タ～では
　何手かまでの先読みは出来ても、その答えが正しいのかどうかはわからないとのこと

　解き易い問題のほうが珍しい現象なんだって！

＜参考＞
　１９７０・解き難さの発見
　１９７６・公開鍵暗号の基本原理
　１９７９・因数分解に基づく暗号
　１９８０～・離散対問題・楕円曲線・符号理論
　１９９０～・実用化・実験システム

エリザベート橋がライトアップ！

今年は日本・ハンガリー外交関係開設140周年・再開50周年ということで
たくさんの文化・記念行事が開催されています。
その中のひとつが、この「エリザベート橋ライトアップ計画」

１７日火曜日の夕方。

この日だけ国旗のライトアップもあるということで
思い立って川沿いを歩いてきました。

この日は今から１３６年前、１８７３年にブダ・ペシュト・オーブダの
三つの街が合併し、ブダペストが誕生した日でもあります。

大使館のＨＰには、１８時３０分からとあったけど、
動きがあったのは、１９時近くなってから。

私が一人ポツンと川岸で点灯を待っていたこの時間、
記念事業実行委員会長の河野洋平前衆議院議長や
照明デザインをされた石井幹子さんを招いての式典が
ドナウ川に浮かぶ船の上で行われていた模様。
| 壁 |д･)ｼﾞｲｰｰｰ・・・・

ポツポツと灯りが点きはじめ・・・

段々と・・・

ぺか～♪
　
以上ｗ

これが本日限定、国旗のライトアップ。
ちなみに写真の向こう岸（ペスト側）は、赤・白・緑で
ハンガリーの国旗の照明になっています。

こっちのブダ側が、日本の国旗。
心の眼でみると、日の丸に見えます。
残念ながら、欄干には飾ってありませんでした。

ちなみに、使われたランプの数は３８０個。
かかった費用は１億１千２百万円。
うち、日本の負担は４千７百万円だったそうです。

YOUTUBEにも動画がUPされていました。
プロの映像をご堪能下さい。

　NHKニュース　ドナウ川の橋 ライトアップ　

ＺＯＩＤＳ

ブログネタ：歩くの早い？ 遅い？ 参加中

歩くの、すごーーく遅いです。
一緒に信号を渡った人が、しばらくすると遥か先にいることもしばしば。
ドイツの重戦車ティーガー、いや、ゾイドと良い勝負が出来ると言われてます。
一度勝負して、カタをつける必要がありそうです。

何だろう、右足出して左足出して、また右足でしょう？
普通にしてるつもりなんだけど、何が違うんだろう？

ダンスをやってた頃に、みぞおちの下から脚が生えてると思えって
言われたことがあったけど、みんなは普段からそうしてるんだろうか。
あと考えられるのは、歩幅か、後ろ足の蹴り出しか。

でも、この自分のペースは嫌いじゃない。
急いでいたら見えない色んな発見があって楽しいもの。

例えば、先週金曜日の通り道で見つけた景色。

街中にある教会の入り口。
ふわ～ってなっちゃう美しさ。
こういうのを見つけて浸って楽しむ時間が好き。

建築物の他にも、広告ポスター・お店のディスプレイなどなど
街には早く歩かせない誘惑がいっぱいなのです。




おまけのゾイド動画。バリゲーター。

あれ？いま見たら意外に早い・・・ホントに同じくらいかもｗ

ビーフストロガノフ

これも余ったきのこの簡単消費メニュー。

フライパンで、スライスしたタマネギ１個をバターで炒める。
キツネ色になったら端に寄せて、空いたところで牛肉ときのこを炒める。
色が変わったら、更にザク切りトマト１個と、微塵切りにしたにんにくを加える。
ここで味付け、醤油とソース、味を見てトマトケチャップ。
１カップの牛乳で少し煮込んだら、サワークリームを加えて完成！


きのこは、この間のマッシュルームがたくさん余ったのでそれを使いました。
牛肉は、仔牛肉（ボリュー）の角切りブロック。マムートの市場で３００ｇ３００円でした。
（スーパーで売ってる硬い牛肉（マルハ）は、年をとった乳牛らしいです）

フライパンひとつで簡単に作りましたが、
もうちょっと手を加えて、お肉をあらかじめ塩コショウして
小麦粉をまぶしてから先に炒めておくと、もっと柔らかくなりますね。
カレーを作る時はいつもそうやってます(´∀｀)

バターライスにしなかったのは・・・一応カロリーを気にしてｗ
ごはん大盛にした時点で、もはや無駄な抵抗ですが。