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

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

 

 

 

オープンコースウエア 大学名：MIT

講座名：6.00 Introduction to Computer Science and Programming
講義日：2008年11月18日（火曜日）　―　第12週・1回目 　

担当教授：Prof.  Guttag

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

配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：50分38秒
サブタイトル：有
キーワード：　シミュレーションモデリング、確率的シミュレーション、確定的シミュレーション、静的モデル　対　動的モデル、モンテカルロシミュレーション、円周率

ビデオ画像品質5段階評価：4
ビデオ音声品質5段階評価：4

講義コメント：　講義中に学生の携帯が鳴った。

グターグ教授、「君のお母さんからなら、遠慮しないで電話をとってもいいよ」とジョークで切り返しています。

今回の話は、dichotomy　 二分法 《物事を対立的な概念に二分する論法》を使い、
比較しながら分かりやすく、シミュレーションモデリングの講義を進めています。

確率的シミュレーション　対　確定的シミュレーション
確率的分析と確定的分析

静的モデル　対　動的モデル

　　　動的モデルは、時間軸との関連で考える。静的モデルにはその必要はない。

　　　これから見ていくのは、動的モデルである。

　　　動的モデルの例：Queing Network - Scheduling and planning

Discreteシミュレーション　対　Continuousシミュレーション

高速道路の交通状況　個々の車の流れ　対　車の流れを流体として捉える

これから見ていくのは、Discreteシミュレーション。

モンテカルロシミュレーション

酔っ払いのランダムウオークモデリングは、モンテカルロシミュレーションであった。

モンテカルロシミュレーションは、統計的推理（Inference Statistics）である。

Randomly chosen sample tends to exhibit same properties as population　To which it is drawn

コイン投げシミュレーション　－＞　表が出るか、裏が出るか
このコイン投げシュミレーションもモンテカルロシミュレーションとして扱うことができる。

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

Pythonのループ構文で、新しい構文が出てきました。

For i in xrange(  )

For i in range(  )　　今まで使ってきた　Range()は、リストを内部に作るため、Range()が大きくなると
メモリの浪費になる。グダーグ教授は、For i in xrange()をほとんどの場合使っているそうです。

講義の後半からは、円周率の計算となります。

１６５０BC  円周率　＝3.16

聖書　円周率　＝３

アルキメデス：　　　223/71  < Pi < 22/7　　　Pi = 3.1418

フランス人数学者　Buffon　Laplace　の円周率を求める方法を
モンテカルロシミュレーションで実行してみます。

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

Lecture 20 Hand out　補助教材 ダウンロード

Lecture 20  ホームワーク ダウンロード

MIT 6.00 講座のプログラムも含んだ資料のダウンロード
-------------------------------------------------

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

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

注－１！　あらかじめ　PylabとNumpy という数学・計算用および図表表示モジュールをインストールしておく必要があります。
個別モジュールをダウンロードするには、ソースフォージ（SourceForge)のサイトから次の2つの小さいパッケージをダウンロードしてインストールします。

１．　Numpy のパッケージ　--> http://sourceforge.net/projects/numpy/files/NumPy/
　　　ダウンロードするパッケージは、numpy-1.5.1-win32-superpack-python2.6.exe

２．　Pylab のパッケージ　--> http://sourceforge.net/projects/matplotlib/files/matplotlib/matplotlib-1.0.1/
　　　ダウンロードするパッケージは、matplotlib-1.0.1.win32-py2.6.exe

例－1  ソースコード


from pylab import *
import random, math

def flipTrial(numFlips):
    heads, tails = 0, 0
    for i in xrange(0, numFlips):
        coin = random.randint(0, 1)
        if coin == 0: heads += 1
        else: tails += 1
    return heads, tails

def simFlips(numFlips, numTrials):
    diffs = []
    for i in xrange(0, numTrials):
        heads, tails = flipTrial(numFlips)
        diffs.append(abs(heads - tails))
    diffs = array(diffs)
    diffMean = sum(diffs)/len(diffs)
    diffPercent = (diffs/float(numFlips))*100
    percentMean = sum(diffPercent)/len(diffPercent)
    hist(diffs) 
    axvline(diffMean, color = 'r', label = 'Mean')
    legend()
    titleString = str(numFlips) +  ' Flips, ' + str(numTrials) + ' Trials'
    title(titleString)
    xlabel('Difference between heads and tails')
    ylabel('Number of Trials')
    figure()
    plot(diffPercent)       
    axhline(percentMean, color = 'r', label = 'Mean')
    legend()
    title(titleString)
    xlabel('Trial Number')
    ylabel('Percent Difference between heads and tails')
simFlips(1000, 1000)
show()

例－１の実行結果

エディタから実行してPython Shell に出力

出力した画像の元ファイルをダウンロードしてみる。

SVG(Scalable Vector Graphics)ファイル

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

例－2  ソースコード


#Tell Python which local standard to use
import locale
locale.setlocale(locale.LC_ALL,'en_US.UTF-8')

#Format ints according to local standard
def formatInt(i):
    return locale.format('%d', i, grouping = True)

from pylab import *
import random, math
def throwDarts(numDarts, shouldPlot):
    inCircle = 0
    estimates = []
    for darts in xrange(1, numDarts + 1, 1):
        x = random.random()
        y = random.random()
        if math.sqrt(x*x + y*y) <= 1.0:
            inCircle += 1
        if shouldPlot:
            piGuess = 4*(inCircle/float(darts))
            estimates.append(piGuess)
        if darts%1000000 == 0: #So I know it's making progress
            piGuess = 4*(inCircle/float(darts))
            dartsStr = locale.format('%d', darts, True)
            print 'Estimate with', formatInt(darts), 'darts:', piGuess
    if shouldPlot:
        xAxis = arange(1, len(estimates)+1)
        semilogx(xAxis, estimates)
        titleString = 'Estimations of pi, final estimate: ' + str(piGuess)
        title(titleString)
        xlabel('Number of Darts Thrown')
        ylabel('Estimate of pi')
        axhline(3.14159)
    return 4*(inCircle/float(numDarts))

def findPi(numDarts, shouldPlot=False):
    piGuess = throwDarts(numDarts, shouldPlot)
    print 'Estimated value of pi with', formatInt(numDarts), 'darts:', piGuess
 
findPi(10000, True)
findPi(100000000)
show() 

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

Python コードのHTML表示には、Dan CederholmのSimpleCodeを使用しています。

Python コードの入出力は、Python IDLE から行っています。

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

講座第19回のリーディングアサイメント

1.　Random walks applet

2.　Chapter 13 of Matplotlib/pylab reference

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

テキスト（全てネット上で無償公開）
1. Getting Started: Python and IDLE
2. Python Programming
3. The Python Tutorial
4. How to Think Like a Computer Scientist: Learning with Python

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