MIT 6.00 コンピュータサイエンスとプログラミング秋期講座第13回

MIT 6.00 コンピュータサイエンスとプログラミング秋期講座第13回
オープンコースウエア 大学名：MIT
講座名：6.00 Introduction to Computer Science and Programming
講義日：2008年10月21日（火曜日）　―　第8週・1回目


担当教授：Prof. John Guttag


全講義数：24コマ
各講義時間：60分


配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：49分47秒
サブタイトル：有
ジャンル：　オプティマゼーション、最適化の手法、Linear Programming, Integer Programming, ダイナミックプログラミング
ビデオ画像品質5段階評価：4
（解像度が480pあり、コンピュータ画面に表示されたソースコードを比較的はっきりと読み取ることができます。）
ビデオ音声品質5段階評価：4



講義コメント：
第１3回目の講義は、前回の講義でふれた最適化の手法、Linear Programming, Integer Programming, ダイナミックプログラミングを実際のプログラムに実装して見せて、解説しています。
最適化手法の導入部分として、以前の講義で学んだフィボナッチ数を復習して、プログラムを実行します。フィボナッチ数の関数を実装するのに、再帰法を使っています。
実行結果を分析してみると、すでに結果が出ている部分も重複して計算していることがわかりました。
そこで重複部分を取り除く手法として個々のF(n)の実行結果を「メモリーに入れることに」
「メモリーに入れることに」といってもPythonには、ARRAYがないので、ビルトイン機能のひとつ辞書機能を使います。実はこれが、ダイナミックプログラミングの手法です。
このページの下にある、例－1 フィボナッチ数 辞書機能で実装の改訂版－３がそうです。
この例－1改訂版－３プログラムで使った辞書機能は、Pythonで使える唯一のマッピング機能です。
形式は例えば、
　　　　　>>> Menu = {'rice':100, 'pasta':150, 'soup':150, 'curry_rice':500, 'vegetable':600, 'salad':400}
　　　　　>>> print Menu['salad']
　　　　　400
のように、鍵（Key)と値でペアになっています。


-------------------------------------------------

Lecture 13 Hand out　補助教材 ダウンロード
Lecture 13 ホームワーク ダウンロード
MIT 6.00 講座のプログラムも含んだ資料のダウンロード
-------------------------------------------------



-------------------------------------------------
講義で取り上げたPythonコードの例
例－1 フィボナッチ数

def fib(n):
    global numCalls
    numCalls += 1
    print 'fib called with', n
    if n <= 1:
        return n
    else:
        return fib(n-1) + fib(n-2)
numCalls = 0
n = 6
res = fib(n)
print '\n fib of', n, '=', res, ' : numCalls = ', numCalls

例－1 フィボナッチ数　の出力結果

>>>
fib called with 6
fib called with 5
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 2
fib called with 1
fib called with 0
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 2
fib called with 1
fib called with 0
fib of 6 = 8  : numCalls =  25
>>> 
-------------------------------------------------
例－1 フィボナッチ数 改訂版－１

def fib(n):
    global numCalls
    numCalls += 1
    print 'fib called with', n
    if n == 0: return 0  ## Fibonacci number F(0) = 0
    if n == 1: return 1  ## Fibonacci number F(1) = 1
    if n <= 2:
        return n
    else:
        return fib(n-1) + fib(n-2)
numCalls = 0
n = 6
res = fib(n)
print '\n fib of', n, '=', res, ' : numCalls = ', numCalls
例－1 フィボナッチ数 改訂版－１の実行結果

>>> ================================ RESTART ================================
>>>
fib called with 6
fib called with 5
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 2
fib called with 3
fib called with 2
fib called with 1
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 2
fib of 6 = 13  : numCalls =  15
>>> 
-------------------------------------------------
例－1 フィボナッチ数 改訂版－２

def fib(n):
    global numCalls
    numCalls += 1
    print 'fib called with', n
##    if n == 0: return 0  ## Fibonacci number F(0) = 0
##    if n == 1: return 1  ## Fibonacci number F(1) = 1
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
numCalls = 0
n = 6
res = fib(n)
print '\n fib of', n, '=', res, ' : numCalls = ', numCalls

例－1 フィボナッチ数 改訂版－２の実行結果

>>>
fib called with 6
fib called with 5
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 2
fib called with 1
fib called with 0
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 4
fib called with 3
fib called with 2
fib called with 1
fib called with 0
fib called with 1
fib called with 2
fib called with 1
fib called with 0
fib of 6 = 13  : numCalls =  25
>>> 
-------------------------------------------------
例－1 フィボナッチ数 辞書機能で実装の改訂版－３

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    return memo[n]
def fib1(n):
    memo = {0:0, 1:1}
    return fastFib(n, memo)
numCalls = 0
n = 30
res = fib1(n)
print 'fib of', n, ' = ', res, 'numCalls = ', numCalls
例－1 フィボナッチ数 辞書機能で実装の改訂版－３の実行結果

>>>
fib1 called with 30
fib1 called with 29
fib1 called with 28
fib1 called with 27
fib1 called with 26
fib1 called with 25
fib1 called with 24
fib1 called with 23
fib1 called with 22
fib1 called with 21
fib1 called with 20
fib1 called with 19
fib1 called with 18
fib1 called with 17
fib1 called with 16
fib1 called with 15
fib1 called with 14
fib1 called with 13
fib1 called with 12
fib1 called with 11
fib1 called with 10
fib1 called with 9
fib1 called with 8
fib1 called with 7
fib1 called with 6
fib1 called with 5
fib1 called with 4
fib1 called with 3
fib1 called with 2
fib1 called with 1
fib1 called with 0
fib1 called with 1
fib1 called with 2
fib1 called with 3
fib1 called with 4
fib1 called with 5
fib1 called with 6
fib1 called with 7
fib1 called with 8
fib1 called with 9
fib1 called with 10
fib1 called with 11
fib1 called with 12
fib1 called with 13
fib1 called with 14
fib1 called with 15
fib1 called with 16
fib1 called with 17
fib1 called with 18
fib1 called with 19
fib1 called with 20
fib1 called with 21
fib1 called with 22
fib1 called with 23
fib1 called with 24
fib1 called with 25
fib1 called with 26
fib1 called with 27
fib1 called with 28
fib of 30  =  832040 numCalls =  59
>>> 

-------------------------------------------------
例－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 から行っています。

-------------------------------------------------

講座第13回のリーディングアサイメント
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

-------------------------------------------------