学類 講義ノート
学類 講義ノート
久野 誉人
takahito*cs.tsukuba.ac.jp (内線5540, 3F932; "*"は"@")
解析 I (H25)
- 10月1日: 高校積分の復習（教科書: p.1-20）
- 10月8日: 初等関数の微分法（教科書: p.21-40）
- 10月15日: 数列と関数の極限（教科書: p.41-48）
- 10月22日: 実数体の完備性（教科書: p.49-56）
- 10月29日: 微分の定義と性質（教科書: p.57-62）
- 11月12日: 高階導関数とテイラーの定理（教科書: p.63-77）
- 11月19日: テイラーの定理の応用，一様連続（教科書: p.78-88）
- 11月26日: 定積分の定義と性質（教科書: p.89-98）
- 12月3日: 定積分の諸定理，対数・指数関数（教科書: p.99-108）
- 12月10日: 広義積分，面積・長さ・体積（教科書: p.109-138）
フレッシュマンセミナー (H25)
スライド: スケジュール，プレゼンテーションのテーマなど
- 4月17日(7A105): ガイダンス，進路指導
- 4月24日(中央図書): 図書館フレッシュマンセミナー
- 10:20, 中央図書館エントランスに集合
- 5月1日(7A105): セーフティライフセミナー
- 5月8日(学術情報メディアセンター): 学術情報メディアセンター見学
- 10:10, 学情センターA203実習室に集合
- 5月15日(中央機械室): 共同溝等基幹施設見学
- 10:20, 中央機械室２階会議室
(キャンパスマップ中地区: "K5", 松美橋近く):
注意事項
- 5月22，29日(7A105): 担任自己紹介
- 5月29日～6月19日(1クラス7A101, 2クラス7A203): 自己紹介
- テーマはスライドを参照
システム数理 II
- パート１ (p.1 - 22)
- 線形計画問題
- シンプレックス法の基本アイデア
- パート２ (p.23 - 48)
- シンプレックス法の収束性と初期化
- 線形計画問題の双対性
- パート３ (p.49 - 62)
- 最短路問題とダイクストラ法
- ナップサック問題と動的計画法
- 付録A「数理計画法の参考書について」
- 付録B 「Blandのピボット選択規則の正当性」
- 付録C 「演習問題のヒント」
ソフトウェアサイエンス実験／情報メディア実験
--- メタヒューリスティクスと巡回セールスマン問題 ---
つくば市内にはコンビニエンス・ストアがいったい何件あるだろう？
大学のサークルに入ってきた新入生が先輩から，つくばセンターのローソンを出発し，市内のコンビニ一件一件を巡ってそのサークルのポスターを貼り，再び先輩の待つセンターのローソンに戻ってくるように頼まれたとしよう．
この新入生の移動距離を最小にするようなコンビニの巡回順序を決める問題が巡回セールスマン問題であり，答を求めることが困難な問題のチャンピオンである．
仮に市内のコンビニの数がたった20件しかないとしても，巡回順序は全部で
(20 - 1)! = 121645100408832000
通りもあるので，１秒間で1億通りの距離を計算できても，その新入生の在学中には最小距離の巡回順序を求めることはできない．
38年後，ようやく答の見つかるころには，新入生の息子が大学生になって父親と同じサークルに入部しているかもしれない．
そのときのコンビニの数が倍に増えていたとしたら，父親としてはサークルからの退部を勧めるだろう．
この例で，巡回セールスマン問題のセールスマン役を任されているのが新入生である．
こんなことを新入生に頼むのは先輩のイジメにも等しいが，実際には20件くらいの問題は短時間で厳密に解けるし，コンビニが数百件あっても近似解ならばパソコンで数秒とかからずに求めることができる．
その近似算法をいくつかプログラムし，計算時間や近似精度の点でどの算法がもっとも優れているかを明らかにするのが，この課題の目的である．
- テキスト１ (p.1 -- 8)
- 巡回セールスマン問題の定義と種類
- 単純な厳密算法
- 動的計画法による厳密算法
- ヒューリスティクス概観
- 実用的なヒューリスティクス
- テキスト２ (p.9 -- 15)
- 禁断探索法
- 焼き鈍し法
- 課題と参考
GNU Octave上でのコンテスト
MATLABクローンのGNU Octaveは，行列演算などには滅法便利だが，巡回セールスマン問題のように離散的な問題を解くには全くといって良いほど向いていない．
しかし，ランダムに問題を生成させたり，それをバイナリーコードで解いて統計を求めたりと，計算実験のための「作業台」と考えれば十分に役立てることができる．
例えば，C++のプログラム「tspenumerate.cc」とCのプログラム「enumerate.cc」(拡張子はC++だが，中身はC)をくっつけて
mkoctfile -o enumerate.oct tspenumerate.cc enumerate.cc
とコンパイルすれば，Octave上で実行できるユークリッド巡回セールスマン問題のための列挙法コード「enumerate.oct」を生成できる．
Octave上で都市の座標を縦に並べたn×2行列Cを
[v, t] = enumerate(C);
のように「enumerate.oct」に与えると，都市の数nが10程度なら，あっという間に最適な巡回路tとその長さvを返してくれるはずである．
この列挙法の本体はCでいい加減に書いた「enumerate.cc」なので，これさえもっと効率の良いヒューリスティク法に替えれば，はるかに大きな問題を処理することも可能だ．
そこで，課題で作成したプログラムを利用し，Octave上でTSPLIBのテスト問題やランダムに生成した問題を解き，CPU時間や解の精度を競うコンテストを予定している．
H25年度の実施に関する連絡事項
- 4月19日(金) 13:45～ 第1回(3C113) テーマの概要説明
線形代数 I (H24)
計画数学
- 線形計画問題
- 付録A「数理計画法の参考書について」
- シンプレックス法の基本的アイディア
- シンプレックス法の収束性と初期化
- 線形計画問題の双対性
- グラフとネットワーク流
- 最短路問題
- 最大流問題
- 組合せ最適化・整数計画問題
- 付録B 「Blandのピボット選択規則の正当性」
- 付録C 「演習問題のヒント」
計算幾何
- 計算幾何学とは
- 計算効率の評価
- ユークリッド空間の集合と性質（その１）
- ユークリッド空間の集合と性質（その２）
- 凸包問題
- ボロノイ図
ホーム