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

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

担当教授：Prof. John Guttag
全講義数：24コマ
各講義時間：60分

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

講義コメント：
第１4回目の講義は、前回でくわしく学習したダイナミックプログラミングの復習から始まります。
前回同様、ダイナミックプログラミングを実装したプログラムの、実行結果をくわしく分析しています。
学生から、「では実際に問題解決するためのプログラムを組むとなった時、どうしたらその問題解決に適切なアルゴリズムを選ぶことが
できるのでしょうか？」といった質問が飛びました。
おそらく通常は、その問題がNPとかNP Completeに属しているか分析して、さらに問題のパターンをつかんでからアルゴリズムを試してみるのではないでしょうか。
でもこの学生の質問に対するGuttagの答え、興味深いものがあります。
最適化の手法のまとめ
1. Trace time for space
2. Don't be intimidated by exponential problems
3. Dynamic programming is broadly useful -> for overlapping substructures
4. Problem reduction -> hugely important
最適化アルゴリズムに関する講義は、だいたいここまでで、後半のこり3分の1からオブジェクト指向の話にがらりと講義内容が変わります。
プログラムのモジュール化。
dot notationの復習

import set
import table
table.member(e,t) ## member（）がどちらのライブラリに属するか明確化するための”・”

Data Abstraction
Abstruct Data Types
オブジェクト指向プログラミング自体は約40年前からある。べつに新しい考え方ではない。
Javaの登場とそれ以降オブジェクト指向プログラミングが一般にも使われるようになった。
メッセージPassingパラダイム　-　便宜的なもので、別に深い意味はない。
クラス　-　Colletion of objects with characteristics in common
Python built-in タイプ（例　Dictionary)は、実はPython built-in クラス




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

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



-------------------------------------------------
講義で取り上げたPythonコードの例
例－1

def maxVal(w, v, i, aW):
    print 'maxVal called with:', i, aW
    global numCalls
    numCalls += 1
    if i == 0:
        if w[i] <= aW: return v[i]
        else: return 0
    without_i = maxVal(w, v, i-1, aW)
    if w[i] > aW: return without_i
    else: with_i = v[i] + maxVal(w, v, i-1, aW - w[i])
    return max(with_i, without_i)
def fastMaxVal(w, v, i, aW, m):
    global numCalls
    numCalls += 1
    try: return m[(i, aW)]
    except KeyError:
        if i == 0:
            if w[i] <= aW:
                m[(i, aW)] = v[i]
                return v[i]
            else:
                m[(i, aW)] = 0
                return 0
        without_i = fastMaxVal(w, v, i-1, aW, m)
        if w[i] > aW:
            m[(i, aW)] = without_i
            return without_i
        else: with_i = v[i] + fastMaxVal(w, v, i-1, aW - w[i], m)
        res = max(with_i, without_i)
        m[(i, aW)] = res
    return res
def maxVal0(w, v, i, aW):
    m = {}
    return fastMaxVal(w, v, i, aW, m)

Python コードのHTML表示には、Dan CederholmのSimpleCodeを使用しています。
Python コードの入出力は、Python IDLE から行っています。

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

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

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