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

オープンコースウエア 大学名：MIT
講座名：6.00 Introduction to Computer Science and Programming
講義日：2008年10月9日（木曜日）　―　第6週・2回目


担当教授：Prof. Eric Grimson


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


配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：46分19秒
サブタイトル：有
ジャンル：　マージソート（分割統治ソート）、ハッシュ関数、学習したアルゴリズムのまとめ、Python プログラムの例外処理　（Exception handling）
ビデオ画像品質5段階評価：4
（解像度が480pあり、コンピュータ画面に表示されたソースコードを比較的はっきりと読み取ることができます。）
ビデオ音声品質5段階評価：4



講義コメント：
第１０回目の講義は、前回に引き続き、代表的なソートアルゴリズムの解説とPythonでの実装、及び実行結果の分析となっています。
高速で効率のよいソートアルゴリズムとして知られる、マージソートを、分割統治型ソートして説明しています。
グリムソン先生が、手品師のようになれた手つきで、数字が書かれたカードをテーブルの上に並べて、マージソートを実物（？）でやって見せています。この部分のビデオ
何度か再生してみましたが、ちゃんと出来ています。
今回の講義の終わりの方でふれているPython プログラムの例外処理は（Exception handling)、とっても使える構文なのですが、グリムソン教授が講義で説明しているプログラム（例５としてこのページの下に掲載）、実行するとエラーが出ます。それで、例５のコード、少々手直ししてあります。

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

Lecture 10 Hand out　補助教材 ダウンロード
Lecture 10 ホームワーク Wordgames２ (前回のホームワークの発展形）ダウンロード
MIT 6.00 講座のプログラムも含んだ資料のダウンロード
-------------------------------------------------



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

def merge(left,right):
  """Assumes left and right are sorted lists.
Returns a new sorted list containing the same elements
as (left + right) would contain."""
  result = []
  i,j = 0, 0
  while i < len(left) and j < len(right):
      if left[i] <= right[j]:
         result.append(left[i])
         i = i + 1
      else:
         result.append(right[j])
         j = j + 1
  while (i < len(left)):
      result.append(left[i])
      i = i + 1
  while (j < len(right)):
      result.append(right[j])
      j = j + 1
  return result
       


def mergesort(L):
   """Returns a new sorted list with the same elements as L"""
   print L
   if len(L) < 2:
      return L[:]
   else:
      middle = len(L) / 2
      left = mergesort(L[:middle])
      right = mergesort(L[middle:])
      together = merge(left,right)
      print 'merged', together
      return together

例－1 マージソートの実行結果　その１

>>> L = [54,32,41,12,4,11,84,902,3,54,61]
>>> print L
[54, 32, 41, 12, 4, 11, 84, 902, 3, 54, 61]
>>> mergesort(L)
[54, 32, 41, 12, 4, 11, 84, 902, 3, 54, 61]
[54, 32, 41, 12, 4]
[54, 32]
[54]
[32]
merged [32, 54]
[41, 12, 4]
[41]
[12, 4]
[12]
[4]
merged [4, 12]
merged [4, 12, 41]
merged [4, 12, 32, 41, 54]
[11, 84, 902, 3, 54, 61]
[11, 84, 902]
[11]
[84, 902]
[84]
[902]
merged [84, 902]
merged [11, 84, 902]
[3, 54, 61]
[3]
[54, 61]
[54]
[61]
merged [54, 61]
merged [3, 54, 61]
merged [3, 11, 54, 61, 84, 902]
merged [3, 4, 11, 12, 32, 41, 54, 54, 61, 84, 902]
[3, 4, 11, 12, 32, 41, 54, 54, 61, 84, 902]



例－１　マージソート実行結果　その２


>>> L = [0]
>>> print L
[0]
>>> L = [19, 260, 366, 117, 302, 660, 831, 420, 479, 313, 554, 661, 574, 124, 130, 715, 882, 937, 461, 828, 722, 91, 248, 90, 684, 982, 634, 641, 4, 804, 204, 713, 791, 722, 464, 242, 997, 308, 40, 983, 113, 397, 537, 230, 54, 293, 465, 127, 798, 853, 710, 246, 366, 506, 903, 626, 159, 687, 497, 792, 266, 193, 589, 169, 860, 383, 199, 98, 397, 282, 362, 603, 144, 27, 594, 821, 338, 44, 744, 901, 873, 657, 587, 146, 116, 409, 859, 399, 895, 330, 175, 806, 29, 808, 173, 191, 11, 993, 141, 827, 642, 954, 286, 536, 412, 462]
>>>
>>>
>>> mergesort(L)
[19, 260, 366, 117, 302, 660, 831, 420, 479, 313, 554, 661, 574, 124, 130, 715, 882, 937, 461, 828, 722, 91, 248, 90, 684, 982, 634, 641, 4, 804, 204, 713, 791, 722, 464, 242, 997, 308, 40, 983, 113, 397, 537, 230, 54, 293, 465, 127, 798, 853, 710, 246, 366, 506, 903, 626, 159, 687, 497, 792, 266, 193, 589, 169, 860, 383, 199, 98, 397, 282, 362, 603, 144, 27, 594, 821, 338, 44, 744, 901, 873, 657, 587, 146, 116, 409, 859, 399, 895, 330, 175, 806, 29, 808, 173, 191, 11, 993, 141, 827, 642, 954, 286, 536, 412, 462]
[19, 260, 366, 117, 302, 660, 831, 420, 479, 313, 554, 661, 574, 124, 130, 715, 882, 937, 461, 828, 722, 91, 248, 90, 684, 982, 634, 641, 4, 804, 204, 713, 791, 722, 464, 242, 997, 308, 40, 983, 113, 397, 537, 230, 54, 293, 465, 127, 798, 853, 710, 246, 366]
[19, 260, 366, 117, 302, 660, 831, 420, 479, 313, 554, 661, 574, 124, 130, 715, 882, 937, 461, 828, 722, 91, 248, 90, 684, 982]
[19, 260, 366, 117, 302, 660, 831, 420, 479, 313, 554, 661, 574]
[19, 260, 366, 117, 302, 660]
[19, 260, 366]
[19]
[260, 366]
[260]
[366]
merged [260, 366]
merged [19, 260, 366]
[117, 302, 660]
[117]
[302, 660]
[302]
[660]
merged [302, 660]
merged [117, 302, 660]
merged [19, 117, 260, 302, 366, 660]
[831, 420, 479, 313, 554, 661, 574]
[831, 420, 479]
[831]
[420, 479]
[420]
[479]
merged [420, 479]
merged [420, 479, 831]
[313, 554, 661, 574]
[313, 554]
[313]
[554]
merged [313, 554]
[661, 574]
[661]
[574]
merged [574, 661]
merged [313, 554, 574, 661]
merged [313, 420, 479, 554, 574, 661, 831]
merged [19, 117, 260, 302, 313, 366, 420, 479, 554, 574, 660, 661, 831]
[124, 130, 715, 882, 937, 461, 828, 722, 91, 248, 90, 684, 982]
[124, 130, 715, 882, 937, 461]
[124, 130, 715]
[124]
[130, 715]
[130]
[715]
merged [130, 715]
merged [124, 130, 715]
[882, 937, 461]
[882]
[937, 461]
[937]
[461]
merged [461, 937]
merged [461, 882, 937]
merged [124, 130, 461, 715, 882, 937]
[828, 722, 91, 248, 90, 684, 982]
[828, 722, 91]
[828]
[722, 91]
[722]
[91]
merged [91, 722]
merged [91, 722, 828]
[248, 90, 684, 982]
[248, 90]
[248]
[90]
merged [90, 248]
[684, 982]
[684]
[982]
merged [684, 982]
merged [90, 248, 684, 982]
merged [90, 91, 248, 684, 722, 828, 982]
merged [90, 91, 124, 130, 248, 461, 684, 715, 722, 828, 882, 937, 982]
merged [19, 90, 91, 117, 124, 130, 248, 260, 302, 313, 366, 420, 461, 479, 554, 574, 660, 661, 684, 715, 722, 828, 831, 882, 937, 982]
[634, 641, 4, 804, 204, 713, 791, 722, 464, 242, 997, 308, 40, 983, 113, 397, 537, 230, 54, 293, 465, 127, 798, 853, 710, 246, 366]
[634, 641, 4, 804, 204, 713, 791, 722, 464, 242, 997, 308, 40]
[634, 641, 4, 804, 204, 713]
[634, 641, 4]
[634]
[641, 4]
[641]
[4]
merged [4, 641]
merged [4, 634, 641]
[804, 204, 713]
[804]
[204, 713]
[204]
[713]
merged [204, 713]
merged [204, 713, 804]
merged [4, 204, 634, 641, 713, 804]
[791, 722, 464, 242, 997, 308, 40]
[791, 722, 464]
[791]
[722, 464]
[722]
[464]
merged [464, 722]
merged [464, 722, 791]
[242, 997, 308, 40]
[242, 997]
[242]
[997]
merged [242, 997]
[308, 40]
[308]
[40]
merged [40, 308]
merged [40, 242, 308, 997]
merged [40, 242, 308, 464, 722, 791, 997]
merged [4, 40, 204, 242, 308, 464, 634, 641, 713, 722, 791, 804, 997]
[983, 113, 397, 537, 230, 54, 293, 465, 127, 798, 853, 710, 246, 366]
[983, 113, 397, 537, 230, 54, 293]
[983, 113, 397]
[983]
[113, 397]
[113]
[397]
merged [113, 397]
merged [113, 397, 983]
[537, 230, 54, 293]
[537, 230]
[537]
[230]
merged [230, 537]
[54, 293]
[54]
[293]
merged [54, 293]
merged [54, 230, 293, 537]
merged [54, 113, 230, 293, 397, 537, 983]
[465, 127, 798, 853, 710, 246, 366]
[465, 127, 798]
[465]
[127, 798]
[127]
[798]
merged [127, 798]
merged [127, 465, 798]
[853, 710, 246, 366]
[853, 710]
[853]
[710]
merged [710, 853]
[246, 366]
[246]
[366]
merged [246, 366]
merged [246, 366, 710, 853]
merged [127, 246, 366, 465, 710, 798, 853]
merged [54, 113, 127, 230, 246, 293, 366, 397, 465, 537, 710, 798, 853, 983]
merged [4, 40, 54, 113, 127, 204, 230, 242, 246, 293, 308, 366, 397, 464, 465, 537, 634, 641, 710, 713, 722, 791, 798, 804, 853, 983, 997]
merged [4, 19, 40, 54, 90, 91, 113, 117, 124, 127, 130, 204, 230, 242, 246, 248, 260, 293, 302, 308, 313, 366, 366, 397, 420, 461, 464, 465, 479, 537, 554, 574, 634, 641, 660, 661, 684, 710, 713, 715, 722, 722, 791, 798, 804, 828, 831, 853, 882, 937, 982, 983, 997]
[506, 903, 626, 159, 687, 497, 792, 266, 193, 589, 169, 860, 383, 199, 98, 397, 282, 362, 603, 144, 27, 594, 821, 338, 44, 744, 901, 873, 657, 587, 146, 116, 409, 859, 399, 895, 330, 175, 806, 29, 808, 173, 191, 11, 993, 141, 827, 642, 954, 286, 536, 412, 462]
[506, 903, 626, 159, 687, 497, 792, 266, 193, 589, 169, 860, 383, 199, 98, 397, 282, 362, 603, 144, 27, 594, 821, 338, 44, 744]
[506, 903, 626, 159, 687, 497, 792, 266, 193, 589, 169, 860, 383]
[506, 903, 626, 159, 687, 497]
[506, 903, 626]
[506]
[903, 626]
[903]
[626]
merged [626, 903]
merged [506, 626, 903]
[159, 687, 497]
[159]
[687, 497]
[687]
[497]
merged [497, 687]
merged [159, 497, 687]
merged [159, 497, 506, 626, 687, 903]
[792, 266, 193, 589, 169, 860, 383]
[792, 266, 193]
[792]
[266, 193]
[266]
[193]
merged [193, 266]
merged [193, 266, 792]
[589, 169, 860, 383]
[589, 169]
[589]
[169]
merged [169, 589]
[860, 383]
[860]
[383]
merged [383, 860]
merged [169, 383, 589, 860]
merged [169, 193, 266, 383, 589, 792, 860]
merged [159, 169, 193, 266, 383, 497, 506, 589, 626, 687, 792, 860, 903]
[199, 98, 397, 282, 362, 603, 144, 27, 594, 821, 338, 44, 744]
[199, 98, 397, 282, 362, 603]
[199, 98, 397]
[199]
[98, 397]
[98]
[397]
merged [98, 397]
merged [98, 199, 397]
[282, 362, 603]
[282]
[362, 603]
[362]
[603]
merged [362, 603]
merged [282, 362, 603]
merged [98, 199, 282, 362, 397, 603]
[144, 27, 594, 821, 338, 44, 744]
[144, 27, 594]
[144]
[27, 594]
[27]
[594]
merged [27, 594]
merged [27, 144, 594]
[821, 338, 44, 744]
[821, 338]
[821]
[338]
merged [338, 821]
[44, 744]
[44]
[744]
merged [44, 744]
merged [44, 338, 744, 821]
merged [27, 44, 144, 338, 594, 744, 821]
merged [27, 44, 98, 144, 199, 282, 338, 362, 397, 594, 603, 744, 821]
merged [27, 44, 98, 144, 159, 169, 193, 199, 266, 282, 338, 362, 383, 397, 497, 506, 589, 594, 603, 626, 687, 744, 792, 821, 860, 903]
[901, 873, 657, 587, 146, 116, 409, 859, 399, 895, 330, 175, 806, 29, 808, 173, 191, 11, 993, 141, 827, 642, 954, 286, 536, 412, 462]
[901, 873, 657, 587, 146, 116, 409, 859, 399, 895, 330, 175, 806]
[901, 873, 657, 587, 146, 116]
[901, 873, 657]
[901]
[873, 657]
[873]
[657]
merged [657, 873]
merged [657, 873, 901]
[587, 146, 116]
[587]
[146, 116]
[146]
[116]
merged [116, 146]
merged [116, 146, 587]
merged [116, 146, 587, 657, 873, 901]
[409, 859, 399, 895, 330, 175, 806]
[409, 859, 399]
[409]
[859, 399]
[859]
[399]
merged [399, 859]
merged [399, 409, 859]
[895, 330, 175, 806]
[895, 330]
[895]
[330]
merged [330, 895]
[175, 806]
[175]
[806]
merged [175, 806]
merged [175, 330, 806, 895]
merged [175, 330, 399, 409, 806, 859, 895]
merged [116, 146, 175, 330, 399, 409, 587, 657, 806, 859, 873, 895, 901]
[29, 808, 173, 191, 11, 993, 141, 827, 642, 954, 286, 536, 412, 462]
[29, 808, 173, 191, 11, 993, 141]
[29, 808, 173]
[29]
[808, 173]
[808]
[173]
merged [173, 808]
merged [29, 173, 808]
[191, 11, 993, 141]
[191, 11]
[191]
[11]
merged [11, 191]
[993, 141]
[993]
[141]
merged [141, 993]
merged [11, 141, 191, 993]
merged [11, 29, 141, 173, 191, 808, 993]
[827, 642, 954, 286, 536, 412, 462]
[827, 642, 954]
[827]
[642, 954]
[642]
[954]
merged [642, 954]
merged [642, 827, 954]
[286, 536, 412, 462]
[286, 536]
[286]
[536]
merged [286, 536]
[412, 462]
[412]
[462]
merged [412, 462]
merged [286, 412, 462, 536]
merged [286, 412, 462, 536, 642, 827, 954]
merged [11, 29, 141, 173, 191, 286, 412, 462, 536, 642, 808, 827, 954, 993]
merged [11, 29, 116, 141, 146, 173, 175, 191, 286, 330, 399, 409, 412, 462, 536, 587, 642, 657, 806, 808, 827, 859, 873, 895, 901, 954, 993]
merged [11, 27, 29, 44, 98, 116, 141, 144, 146, 159, 169, 173, 175, 191, 193, 199, 266, 282, 286, 330, 338, 362, 383, 397, 399, 409, 412, 462, 497, 506, 536, 587, 589, 594, 603, 626, 642, 657, 687, 744, 792, 806, 808, 821, 827, 859, 860, 873, 895, 901, 903, 954, 993]
merged [4, 11, 19, 27, 29, 40, 44, 54, 90, 91, 98, 113, 116, 117, 124, 127, 130, 141, 144, 146, 159, 169, 173, 175, 191, 193, 199, 204, 230, 242, 246, 248, 260, 266, 282, 286, 293, 302, 308, 313, 330, 338, 362, 366, 366, 383, 397, 397, 399, 409, 412, 420, 461, 462, 464, 465, 479, 497, 506, 536, 537, 554, 574, 587, 589, 594, 603, 626, 634, 641, 642, 657, 660, 661, 684, 687, 710, 713, 715, 722, 722, 744, 791, 792, 798, 804, 806, 808, 821, 827, 828, 831, 853, 859, 860, 873, 882, 895, 901, 903, 937, 954, 982, 983, 993, 997]
[4, 11, 19, 27, 29, 40, 44, 54, 90, 91, 98, 113, 116, 117, 124, 127, 130, 141, 144, 146, 159, 169, 173, 175, 191, 193, 199, 204, 230, 242, 246, 248, 260, 266, 282, 286, 293, 302, 308, 313, 330, 338, 362, 366, 366, 383, 397, 397, 399, 409, 412, 420, 461, 462, 464, 465, 479, 497, 506, 536, 537, 554, 574, 587, 589, 594, 603, 626, 634, 641, 642, 657, 660, 661, 684, 687, 710, 713, 715, 722, 722, 744, 791, 792, 798, 804, 806, 808, 821, 827, 828, 831, 853, 859, 860, 873, 882, 895, 901, 903, 937, 954, 982, 983, 993, 997]
>>> 
-------------------------------------------------
例－2 　

def create(smallest, largest):
    intSet = []
    for i in range(smallest, largest+1): intSet.append(None)
    return intSet


def insert(intSet, e):
    intSet[e] = 1


def member(intSet, e):
    return intSet[e] == 1
-------------------------------------------------
例－3　ハッシュ関数

def hashChar(c):
    # c is a char
    # function returns a different integer in the range 0-255
    # for each possible value of c
    return ord(c)

def cSetCreate():
    cSet = []
    for i in range(0, 255): cSet.append(None)
    return cSet

def cSetInsert(cSet, e):
    cSet[hashChar(e)] = 1


def cSetMember(cSet, e):
    return cSet[hashChar(e)] == 1 
-------------------------------------------------


例－4　Python プログラム：　例外処理　（Exception handling）

def readFloat(requestMsg, errorMsg):
    while True:
        val = raw_input(requestMsg)
        try:
            val = float(val)
            return val
        except:
            print(errorMsg)
print readFloat('Enter float: ', 'Not a float.') 　##　def readFloat 関数の外

def readVal(valType, requestMsg, errorMsg):
    while True:
        val = raw_input(requestMsg)
        try:
            val = valType(val)
            return val
        except:
            print(errorMsg)
print readVal(int, 'Enter int: ', 'Not an int.')　##　def readVal 関数の外
例－4　例外処理 プログラムの実行結果　（今回は、Python Shell上での実行ではなく、エディタから実行してPython Shell に出力しています。）

Python 2.6.6 (r266:84297, Aug 24 2010, 18:46:32) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
    ****************************************************************
    Personal firewall software may warn about the connection IDLE
    makes to its subprocess using this computer's internal loopback
    interface.  This connection is not visible on any external
    interface and no data is sent to or received from the Internet.
    ****************************************************************

IDLE 2.6.6
>>> ================================ RESTART ================================
>>>
Enter float: 5.0
5.0
>>> ================================ RESTART ================================
>>>
Enter float: fgb
Not a float.
Enter float: fds
Not a float.
Enter float: 3
3.0
>>> 
-------------------------------------------------


例－5　ファイルを読み込む例外処理プログラム　（配布資料には載っていない、講義中に実行したプログラム。今回は、Python Shell上での実行ではなく、エディタから実行してPython Shell に出力しています。）

def getGrades(fname):
    try:
        gradesFile = open(fname, 'r')
    except IOError:
        print 'Could not open', fname
        raise
    grades = []
    for line in gradesFile: grades.append(float(line))
    return grades
try:
    filename = raw_input('Please enter a filename --> ')
    print 'File Name is: ',filename
    grades = getGrades(filename)
    grades.sort()
    median = grades[len(grades)/2]
    print 'Median grade is',median
except IOError:
    print 'Whoops'
例－5　ファイルを読み込む例外処理プログラム　実行結果

>>> ================================ RESTART ================================
>>>
Please enter a filename --> etq.txt
File Name is:  etq.txt
Could not open etq.txt
Whoops
>>> 


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

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

講座第10回のリーディングアサイメント(第9回のリーディングアサイメントと同じ）

1. Selection sort: Wikipedia article on selection sort
2. Insertion sort: Wikipedia article on insertion sort
3. Merge sort: Wikipedia article on merge sort

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

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

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