MIT6.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

講義コメント:

第13回目の講義は、前回の講義でふれた最適化の手法、Linear Programming, Integer Programming, ダイナミックプログラミングを実際のプログラムに実装して見せて、解説しています。

最適化手法の導入部分として、以前の講義で学んだフィボナッチ数を復習して、プログラムを実行します。フィボナッチ数の関数を実装するのに、再帰法を使っています。

実行結果を分析してみると、すでに結果が出ている部分も重複して計算していることがわかりました。

そこで重複部分を取り除く手法として個々のF(n)の実行結果を「メモリーに入れることに」

「メモリーに入れることに」といってもPythonには、ARRAYがないので、ビルトイン機能のひとつ辞書機能を使います。実はこれが、ダイナミックプログラミングの手法です。

このページの下にある、例−1 フィボナッチ数 辞書機能で実装の改訂版−3がそうです。

この例−1改訂版−3プログラムで使った辞書機能は、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 フィボナッチ数 改訂版−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 フィボナッチ数 改訂版−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 フィボナッチ数 改訂版−2

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 フィボナッチ数 改訂版−2の実行結果

>>>

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 フィボナッチ数 辞書機能で実装の改訂版−3

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 フィボナッチ数 辞書機能で実装の改訂版−3の実行結果

>>>

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

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