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

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


担当教授：Prof. Guttag


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


配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：50分38秒
サブタイトル：有
ジャンル：　乱数、ランダムウオーク、擬似乱数（Psudo Random）
ビデオ画像品質5段階評価：4
（解像度が480pあり、コンピュータ画面に表示されたソースコードを比較的はっきりと読み取ることができます。）
ビデオ音声品質5段階評価：4


講義コメント：
第1回から第１6回目の講義までが、基礎固めの講義でした。コンピューターサイエンス専攻の学生向けの入門コースとしては、普通の大学であればこの辺りまでがおそらく範囲なのでしょう。
しかしMITの入門コース、この第１7回目の講義から最終回にあたる24回目の講義まで、プログラミングの応用や、さらなる難問の挑戦に当てています。
問題を解くにあたって、コンピューターを問題解決のツールとして使えるか、
それとも紙と鉛筆（つまり数学的にもしくは、OR的に）で解くかにより、
問題解決のアプローチが異なっている。
ばらつき（ランダム）を処理する。
データの意味の整合性を検証する。
プログラムの実行結果の品質を検証する。
プログラムを書いていく前に、単純なシステムからモデリングを始める事。
ランダムウオークをシステム的にモデリングし、Pythonで実装する。
　　　1.　Location
　　　2.　CompassPT(Direction)
　　　3.　Field
　　　4.　Drunk（酔っ払い）
Youtubeでこの講義を見ていたら、お勧め動画（つまりこの17回目の講義を見ている人がこんな動画も見ている！）にアルゴリズム入門　－　MIT 6.046J/18.410J Fall 2005)とあるのを発見。
そこに書き込みしてある「学生達」のコメントが面白い。
コメントその１．真のプログラマーが生まれる瞬間がここにある。
コメントその2．黒板を使い倒している。すごい！パワーポイント（PowerPoint)なんてくそくらえだ。
コメントその3．（レイア姫の出身星）アルデロン星からケンブリッジまでどうやってたどり着くかのアルゴリズムだなんて、この先生スターウオーズオタクだね。



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

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


-------------------------------------------------
講義で取り上げたPythonコードの例
注！　今回のコード、実行する前にPylabという数学・計算用モジュールをインストールしておく必要があります。イギリス・サウザンプトン大学のサイトPython 教材ダウンロードを参照しても良いです。ここからダウンロードすると、すべて込みこみのサイズが２００M以上のパッケージをダウンロードすることになります。
個別モジュールをダウンロードするには、ソースフォージ（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


import math, random, pylab
class Location(object):
  def __init__(self, x, y):
    self.x = float(x)
    self.y = float(y)

  def move(self, xc, yc):
    return Location(self.x+float(xc), self.y+float(yc))
  def getCoords(self):
    return self.x, self.y
  def getDist(self, other):
    ox, oy = other.getCoords()
    xDist = self.x - ox
    yDist = self.y - oy
    return math.sqrt(xDist**2 + yDist**2)
class CompassPt(object):
  possibles = ('N', 'S', 'E', 'W')

  def __init__(self, pt):
    if pt in self.possibles: self.pt = pt
    else: raise ValueError('in CompassPt.__init__')

  def move(self, dist):
    if self.pt == 'N': return (0, dist)
    elif self.pt == 'S': return (0, -dist)
    elif self.pt == 'E': return (dist, 0)
    elif self.pt == 'W': return (-dist, 0)
    else: raise ValueError('in CompassPt.move')

class Field(object):

  def __init__(self, drunk, loc):
    self.drunk = drunk
    self.loc = loc

  def move(self, cp, dist):
    oldLoc = self.loc
    xc, yc = cp.move(dist)
    self.loc = oldLoc.move(xc, yc)

  def getLoc(self):
    return self.loc
  def getDrunk(self):
    return self.drunk
class Drunk(object):
  def __init__(self, name):
    self.name = name

  def move(self, field, time = 1):
    if field.getDrunk() != self:
      raise ValueError('Drunk.move called with drunk not in field')
    for i in range(time):
      pt = CompassPt(random.choice(CompassPt.possibles))
      field.move(pt, 1)
  
def performTrial(time, f):
  start = f.getLoc()
  distances = [0.0]
  for t in range(1, time + 1):
    f.getDrunk().move(f)
    newLoc = f.getLoc()
    distance = newLoc.getDist(start)
    distances.append(distance)
  return distances
drunk = Drunk('Homer Simpson')
for i in range(3):
  f = Field(drunk, Location(0, 0))
  distances = performTrial(500, f)
  pylab.plot(distances)

pylab.title('Homer\'s Random Walk')
pylab.xlabel('Time')
pylab.ylabel('Distance from Origin')
def performSim(time, numTrials):
  distLists = []
  for trial in range(numTrials):
    d = Drunk('Drunk' + str(trial))
    f = Field(d, Location(0, 0))
    distances = performTrial(time, f)
    distLists.append(distances)
  return distLists
def ansQuest(maxTime, numTrials):
  means = []
  distLists = performSim(maxTime, numTrials)
  for t in range(maxTime + 1):
    tot = 0.0
    for distL in distLists:
      tot += distL[t]
    means.append(tot/len(distL))
  pylab.figure()
  pylab.plot(means)
  pylab.ylabel('distance')
  pylab.xlabel('time')
  pylab.title('Average Distance vs. Time (' + str(len(distLists)) + ' trials)')

ansQuest(500, 300)
pylab.show()


例－１の実行結果
エディタから実行してPython Shell に出力


出力した画像の元ファイルをダウンロードしてみる。
１．　「Lec17_Average_Dist_vs_Time.svg」をダウンロード
２．　「Lec17_Homers_Random_Walk.svg」をダウンロード
SVG(Scalable Vector Graphics)ファイル


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



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

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

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

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