１１月１７日
結果発表
優勝は先週の記録を守り通した小川さんに決定しました。
パチパチパチ
みなさんそれぞれ自分の手法で解を導き出せて良かったと思います。今日でゼミの勉強は終わりです。来週からは卒研のテーマ決めに入ります。途中でくじけないようなテーマが見つかるといいですね。
１１月１０日
来週、ついに最終発表なのだが大内君と小川さんははやまって今日発表した。大内君は１９６００ぐらいで首位の座を奪取した。八木沢くんは中間発表で１９８００をだしてきたので来週が楽しみだ。そしてノーマークだった小川さんがなんと１９４００マイルをだして大内君を瞬殺して首位にたった。そうそう忘れてはならないのが辻村くんである。彼は前の時間に訂正したにもかかわらずまたもや嘘を言っていたのだ。アーーチーーチーーアーーチである。大島くんはまだ途中だがパワーポイントを使ってきた。あなどれない。さー来週だれがチャンピオンになるんだろうか。アンディーこれを読んだら連絡下さい。
１０月２７日
２週間前に辻村君がだした。１４０００マイルという解が嘘だったということが発覚した。計算間違いだったらしい。島流しもんである。しかし間違えたのをなおしても１９０００の前半なので首位はキープした。ここで手で解いている三木田君も１９０００代といいう解をだしてきた。どうやら１８０００代をだせば優勝できそうだ。ちなみに私は２９８００マイルでみんなをつきはなしている。アンディーどこ行った。
１０月１３日
青山くん木村くん辻村くんが自分の解をだすことに成功した。特に辻村君は今の所新記録の約１４０００マイルというのをだした。誰かぬけるのだろうか。
１０月６日
今週は個人の進み具合と来週までにやってくることを発表した。青山君、木村君、大内君はいい進み具合でした。他の人もがんばりましょう。
９月２９日
今日から後期のゼミが始まりました。またがんばりましょう。
JASの航路についてこれからやっていきます。みなさん自分の手法でそれぞれ解を導きだしてください。
７月２８日
最適巡回路を求めて−BRANCH AND
CUT−（大内、大島、小川）
ついに最後の章にきました。ここでは巡回セールスマン問題を解くことにします。しかしこれを解くには問題が山積み、だからまず制約を減らし緩和問題にする。そして最大流問題を適用し、最後に２−マッチング不等式を使う。こういってしまうと簡単ですが、実際やってみると非常に難しいです。
７月２１日
(Joseph-Louis de
Lagrange)・・・・・ラグランジュについて（青山）
イタリアのトリノに生まれたが、デカルトと同じ家系でありフランス人の血をひいている。１８歳で陸軍の教官になりその後ベルリンの哲人王フリードリッヒ２世に世界一の数学者としてむかえられる。フリードリッヒの死後はマリーアントワネットやナポレオンにも気に入られる。彼の業績として・線形代数の基礎論・メートル法・Lagrange関数・解析力学がある。
ラグランジュ緩和（落合、三木田）
制約の１部を無視して解いたときの最適解の値は予算制約がついている問題の最適解の値よりも等しいか小さい値をとる。これが緩和問題である。その時得られた値を下界という。そして制約式を単に除くのではなく、なんらかの値を乗じてぺナルティ項として目的関数に組み込むことによって得られる緩和問題をラグランジュ緩和問題という。これを解く時に使われる算法の１つに劣勾配法というのがある。
７月１４日
最適巡回路を求めて−対称な問題−（木村、工藤、八木沢）
前回までの割当問題の答えではコストがＣijとＣｊｉで違う場合があった。しかし対称問題というのはコストのＣij＝Ｃjiが成り立つのである。そして対称問題を解くには緩和問題を使うのが効果的。その１つとしてHeldとKarpが提案した最小コストの１−木問題というのががあります。
７月７日
(Johann von
Neumann)・・・・・ノイマンについて（小川）
ハンガリーの首都ブタペストで生まれた。小さいころから神童と言われ２３才でベルリン大の講師になるが、ナチスを避けてアメリカに移住する。このとき名前をヨハンからジョンに変える。実績としては、チューリングの計算機を実現したプログラム内蔵機械ＥＮＩＡＣを生み出した。その他ゲームの理論の始祖となる本も出し、原爆、水爆の開発にも手を染めた。
最大流問題（辻村、田部井）
最大流問題の一般的な例としてネットワーク上に水を流してどれだけ効率よく流せるか、というのがあります。この応用がFordとFulkersonの算法です。その他にGoldbergとTarjanのPreflow-Push
Algorithm（水の押し出し・バケツの持ち上げ算法）というのもあります。確かにこの算法は最大流問題といっても水を流すというより押し出すといったほうがただしいと思いました。
６月２３日
最適巡回路を求めて−割当問題を用いて−（安藤、木村、三浦）
巡回セールスマン問題の最適解を求めるための方法として、まず巡回セールスマン問題を数理計画問題に定式化する。そして巡回セールスマン問題の緩和問題（元の問題の制約を適当に弛めた問題）である割当問題を使う。それで部分巡回路がいくつかできてしまった場合は分枝限定法を使う。そうすれば最適解が求められる。
６月１６日
近似算法（青山、大島、落合）
近似算法には、何も無いところから巡回路を作っていく構築法となんらかの巡回路があるときに、それをもっとコストの小さい巡回路に改良していく改善法とがある。ここでは最遠挿入法、ランダム挿入法、凸包、空間充填曲線法、バケット法、Karpの分割算法という６つの構築法と、２−OPT算法、３−OPT算法、LinとKernighanの算法の３つの改善法を紹介している。そして各算法の解の精度についてもグラフでしめされている。
(George
B.Dantzig)・・・・・ダンツィークについて（三木田）
アメリカで生まれたが父はロシア生まれだったのでロシア人の血も入っている。ダンツィークはアメリカの空軍に入り計画のプログラム化に従事した。日本軍の配置についても予測していたらしい。彼の線形計画は数学者より経済学者の影響を強く受けている。しかしその業績はあまりにも数学的すぎるためノーベル経済学賞を受賞できないでいる。しかしシンプレックス法を考え出したのは彼なのである。
組合せ多面体論入門（大内、八木沢）
６人の友人からできるだけ多くの人を連れてピクニックに行きたいが仲の悪い人同志ではどちらかしか連れて行けない。これが最大安定集合問題です。この問題を多面体にして最適化していくのが組合せ多面体論です。
５月１９日、２６日
精度保証のある近似算法(小川、田部井）
精度保証とは最適順回路のコストのある定数倍以下のコストを持つ順回路が得られること。そした最適性を譲るかわりに短い時間で良い解をだすのが近似算法。
(Leonhard
Euler)・・・・・オイラーについて（安藤）
スイスのバーゼル（根本先生が数年前男の人に体をさわられて目覚めてしまったところ）に生まれました。数学一家として名高く＜ベルヌーイの定理＞で有名なベルヌーイ家が君臨していた。実績としてオイラー積分やオイラー関数、多面体定理がある。このほかにもオイラーの名前を冠する公式は数えきれない。
握手の定理とEulerの定理（三浦）握手の定理とは、どんなグラフにおいても奇数の次数を持つ頂点の数は偶数であるということ。Eulerの定理とは、グラフがEuler閉路を持つための必要十分条件はグラフが連結でかつすべての頂点の次数が偶数であること。
５月１２日
計算量の理論とNP完全問題（大内、辻村）
計算量の理論の中心的な課題は問題を計算機で解くときどのくらいの時間がかかるかを評価すること。NPとは何か。ハミルトン閉路はＮＰ-完全である。巡回セールスマン問題はＮＰ困難である。
(Alan Mathison
Turing)・・・・チューリングについて（木村）
イギリスの数学者で数値解析及びコンピューターの基礎理論の分野で、多くの独創的な研究を行った。彼はコンピュータの知的能力を人間と比べてテストしてその結果コンピュータが人間のように考えていると定義した。また、彼はこんにち使われているＡＩ（人工知能）の開祖といわれている。
（累乗数と昔話）(工藤）累乗数が急激に大きくなることをネタにした昔話をいくつか紹介します。
”数学者ルカのハノイの塔””インドの王様のために将棋を発明した人への褒美でもらった、９Ｘ９の将棋盤の上に麦を２倍ずつ置いていくと・・・・。””曽呂利新左衛門の話”９連環(チャイニーズリング）”
４月２８日
巡回セールスマン問題の歴史（三浦、八木沢）
巡回セールスマン問題の起源はゲームやパズルに関連しています。ルジャンドル、ド・モアブル、オイラーという人たちが（８X８のチェス盤のすべての桝目を１回ずつ通るナイトの駒の巡回順を求める）というパズルを考えていました。この問題がパス型の巡回セールスマン問題となりました。その他にハミルトンのハミルトン閉路やカープの近似算法、楕円体法‥があります。
(William Rowan
hamilton)・・・ハミルトンについて（落合）
ハミルトンは本編ででてきたハミルトン閉路を考案した人であり、これは彼が晩年の研究（icosian
calculas）に関連して考案した世界１周ゲーム（icosian game）にちなんで付けられました。
線形計画について（田部井）
線形計画問題とは、何本かの線形不等式によって規定される空間の中で線形関数を最小化、または最大化する問題です。これを解く方法としてシンプレックス法と内点法があります。
４月２１日
今日１限で４年生の卒研のテーマの発表会がありました。みなさん僕には思い付かないような、するどいことをテーマにしていました。尊敬
２限で３年生のホームページの発表会がありました。全員のをみてわかったことは、人には個性というものがあり、それはこんなところでにじみでてくるものだということです。もう完成に近い人や、まだこれからという人も満足できるものを作ってもらいたいです。それがお父さんのお願いです。
４月１４日
今日から３年生になってのゼミが始まりました。
テキストとして”巡回セールスマン問題への招待”という本を使っていきます。
巡回セールスマン問題について（三木田、工藤）
飛行距離４万マイル以内で５つの都市をまわるには、どのような順番でまわればいいか（最適巡回路）を求めた。
(Giuseppe
Peano)・・・ペアノについて（大島）
ペアノという人は平面を埋め尽くす曲線（空間充填曲線）をあみだした。
アルゴリズムについて（青山）
アルゴリズムの語源はアル・クワーリズミからきています。この定義は”チューリングマシン上で実行できるもの”ということです。