オープンコースウエア 大学名：MIT
講座名：6.00 Introduction to Computer Science and Programming
講義日：2008年10月16日（木曜日） ― 第7週・2回目
担当教授：Prof. Eric Grimson
全講義数：24コマ
各講義時間：60分
配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：49分47秒
サブタイトル：有
ジャンル： 前半 －＞ 検証、デバッグ、防御的プログラミング、単体テスト、テストスイート、科学的検証方法
後半 －＞ オプティマゼーションのカノニカル形式 、最適化の手法、代表的なORの手法、Linear Programming,Integer Programming,ダイナミックプログラミング
ビデオ画像品質5段階評価：4
（解像度が480pあり、コンピュータ画面に表示されたソースコードを比較的はっきりと読み取ることができます。）
ビデオ音声品質5段階評価：4
講義コメント：
第１2回目の講義の前半は、前回の講義に引き続き、プログラムのデバグに関する手法がメインテーマとなっています。
後半からは、代表的なORの問題を解説する内容となっています。 さらっと、「代表的なORの問題を解説する内容」と書きましたが、これは大変なことです。コンピューターサイエンスの一番最初の入門講座で、これだけ代表的なORの問題を、学ぶことになるとは。ある意味エリート教育ですね。
１．オプティマゼーションのカノニカル形式 （標準形式）
すべての最適化問題は、ひとつのカノニカル形式 （標準形式）で表すことができる。
２．最適化の手法
３．代表的なORの問題
３．１ Shortest Path - 最短距離問題
３．２ Traveling Salesman - トラベリングセールスマン
３．３ Bin Packing - 積荷の最適化問題
３．４ Sequence Alignment - シーケンス問題
３．５ Knapsack - ナップサック問題
４．Linear Programming問題
数学とか、ORの授業だと 紙と鉛筆で、「Linear Programming問題を解け」 となるところですが、コンピューターサイエンスなので、当然プログラムを書いて問題をとくことになります。
５．Integer Programming問題
紙と鉛筆でInteger Programming問題を解くのは、すでに大学院レベルの話なのですが、これをプログラム的に解くと「どうなるか？」
６．ダイナミックプログラミング
1950年代に、Richard Ernest Bellmanが開発した問題解決方法。いまではMBAコースでも教えている、代表的な最適化手法の一つです。
一説によると、米国軍から研究費をもらっていたBellmanは、印象に残るようなネーミングにしようということで、実際の開発した手法とは何の関連もないカッコイイ名前「ダイナミックプログラミング」にしたということです。
面白いことにいろいろ調べてみると、ダイナミック（Dynamic)ってどうも50年代にアメリカで流行ったネーミングらしい。 軍産複合体の知る人ぞ知るゼネラル・ダイナミクスも、元々の社名はエレクトリックボート（電気船 転じて潜水艦）だったのが、いまの社名に変えたのが1950年代だそうです。 ゼネラル・ダイナミクスの前身エレクトリックボートは、日露戦争で敵対している当時の日本とロシア両方に潜水艦を売りつけた、武器の商人。ユダヤ商人の上を行くオランダ商人です。
-------------------------------------------------
Lecture 12 Hand out 補助教材 ダウンロード
Lecture 12 ホームワーク ダウンロード
MIT 6.00 講座のプログラムも含んだ資料のダウンロード
-------------------------------------------------
-------------------------------------------------
講義で取り上げたPythonコードの例
例－1
def fib(n):
global numCalls
numCalls += 1
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
numCalls = 0
n = 5
print 'fib of', n, '=', fib1(n)例－1 Modified
def fib(n):
global numCalls
numCalls += 1
if n <= 1:
return n
else:
print 'n=',n,' : fib(n-1) + fib(n-2) = \n',fib(n-1),' + ',fib(n-2)
return fib(n-1) + fib(n-2)
numCalls = 0
n = 5
print fib(n)
print 'fib of', n, '=', fib(n)例－1 Modified の出力結果
>>> ================================ RESTART ================================
>>>
n= 5 : fib(n-1) + fib(n-2) =
n= 4 : fib(n-1) + fib(n-2) =
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2 + n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
3 + n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2
n= 4 : fib(n-1) + fib(n-2) =
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2 + n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
5
fib of 5 = n= 5 : fib(n-1) + fib(n-2) =
n= 4 : fib(n-1) + fib(n-2) =
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2 + n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
3 + n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2
n= 4 : fib(n-1) + fib(n-2) =
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
2 + n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
n= 3 : fib(n-1) + fib(n-2) =
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
1 + 1
n= 2 : fib(n-1) + fib(n-2) =
1 + 0
5
>>> -------------------------------------------------
例－2
def fib1(n):
global memo
global numCalls
numCalls += 1
if not n in memo:
memo[n] = fib1(n-1) + fib1(n-2)
return memo[n]
memo = {0:0, 1:1}Python コードのHTML表示には、Dan CederholmのSimpleCodeを使用しています。
Python コードの入出力は、Python IDLE から行っています。
-------------------------------------------------
講座第12回のリーディングアサイメント
1. 20bits by Jesse Farmer: Introduction to Dynamic Programming
-------------------------------------------------
テキスト（全てネット上で無償公開）
1. Getting Started: Python and IDLE
2. Python Programming
3. The Python Tutorial
4. How to Think Like a Computer Scientist: Learning with Python
-------------------------------------------------
No comments:
Post a Comment