2014-05-01から1ヶ月間の記事一覧

今回は、主にゲームの勝率をあげる方法や、 パズルの解法についてあつかう。 The locker game 10名のチームが、1名の審判と対決する。10個のロッカーが設置された部屋がある。 そのロッカーの一つ、一つに、このゲームの参加者10名の氏名が1名書かれ…

wikipedia 通信複雑性(つうしんふくざつせい、Communication Complexity、CC)は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビット…

前回でapproximation algorithmや、online algorithmはひとまず終了。今回からは、communicationという場面を想定したalgorithmを学習する。というより,algorithmという言葉はひとまず、一度退場する。ここではprotocolという用語をつかう。具体的な事例 Int…

線形計画問題とは

最適化問題のひとつで、目的関数と制約条件がすべて線形関数で表せる問題を線形計画問題といいます。問1 製品A,Bを生産するためには原料a,b,cが必要です。売却利益はAが3、Bが2です。各製品の生産に必要な原料の量と在庫は図のとおりとします。このとき、売…

前回に引き続き、近似アルゴリズムいろいろな体積をもつ複数の荷物を 一定の体積のBinつまりコンテナーに格納するという場面。出来る限り、最小のコンテナーの数で、すべての荷物を格納することをめざす。この目的達成に対して、First Fitという戦略が、理想…

contemporary algorithm 07

先週の講義の続き。直線上に、サーバーを配置する。ランダムなリクエストに基づいて、サーバを、要求地点に移動させていく。 移動距離のコストを最小にする戦略を探求する。 double coverageという戦略をとった場合、それは、optimumなコストより、 どれくら…

漢字の変換にまつわるアルゴリズムのコスト計算について引き続き。一度、選択された漢字の変換パターンを、一番先頭に出てくるように、変換される熟語のパターンの順番を 変えるという戦略をとった場合のその後の話。そのパターンに対して、次の変換のリクエ…

contemporary algorhythm 05

いままで basic techniqueonline algorithmdifficulty computatation timelack of information 不完全な情報でも、うごくアルゴリズムの開発株式投資 1000株 A社 ある株式を買うかどうかをきめるには過去の情報しか参考にできない。 未来の情報はない。e…

contemporary algorhythm 04

座標平面に散らばった点と点の間の距離最小のものを求める。exponential speedupbacktracklocal searchexample 7 3-satisfiability 3cnf formulaconjunctive normal formlocal search random assignment local improvement

contemporary algorhythm 03

行列のかけ算3つの行列の積5つの行列の積かけ算をする順序によって、かけ算をする回数がかわってくる。樹形図で、かける順序の場合分けをする。 重複するかけ算の順序は、繰り返し、計算することをさけるようにする。3 55 22 44 66 3の行列縦横のテーブル…

contemporary algorhythm 02

closest pair probleminput n point on Euclid space ( 2dimension) p1(x1, y1) p2(x2,y2), 座標に、任意の点が散らばっている状態。output どの点とどの点が一番、距離が小さいのか。解法 片っ端から2点間の距離を計算する。もっと速い計算法はないのか?…