オープンコースウエア 大学名：MIT
講座名：6.00 Introduction to Computer Science and Programming
講義日：2008年10月7日（火曜日） ― 第6週・1回目
担当教授：Prof. Eric Grimson
全講義数：24コマ
各講義時間：60分
配信開始日：2009年8月19日
講義ビデオソース：Youtube
講義ビデオ収録時間：47分30秒
サブタイトル：有
ジャンル： 効率の良いアルゴリズム、Linear, Logarithmic, Quadratic, Exponential, バイナリーサーチ、セレクション・ソート、バブル・ソート
ビデオ画像品質5段階評価：4
（解像度が480pあり、コンピュータ画面に表示されたソースコードを比較的はっきりと読み取ることができます。）
ビデオ音声品質5段階評価：4
講義コメント：
中間試験開後、はじめての講義。教鞭をとるグリムソン教授も、この講座をとっている学生たちも、本気モードです。 グリムソン教授の口癖 ”Fudge Knuckle” をこの講座でも連発しています。
しかし哀しいかな、年を重ねるごとに数学的閃きが鈍くなってきている私でも、Youtubeのストリームビデオがあれば、3回も4回も繰り返し見れるので、閃きの鈍さを根性で補っています。
さて9回目の当講座、前回の講座に続いてとうか前回の講座をちょっと復習。
効率の良いアルゴリズムの実例を、プログラムを実行して説明しています。説明しているアルゴリズムは、Linear, Logarithmic, Quadratic, Exponentialの４つの代表的なアルゴリズム。
それらの応用として、バイナリーサーチ 及び2種類のソーティングアルゴリズム（セレクション・ソート、バブル・ソート）を解説しています。
-------------------------------------------------
Lecture 9 Hand out 補助教材 (Python programming in IDE)ダウンロード
Lecture 9 ホームワーク Wordgames ダウンロード
MIT 6.00 講座のプログラムも含んだ資料のダウンロード
-------------------------------------------------
-------------------------------------------------
講義で取り上げたPythonコードの例
例－1 バイナリーサーチ
def bsearch(s, e, first, last, calls):
print first, last, calls
if (last - first) < 2: return s[first] == e or s[last] == e
mid = first + (last - first)/2
if s[mid] == e: return True
if s[mid] > e: return bsearch(s, e, first, mid - 1, calls+1)
return bsearch(s, e, mid + 1, last, calls + 1)
def search(s, e):
print bsearch(s, e, 0, len(s) - 1, 1)例－1 の実行結果
>>> s = range(10000000) ##この行手入力
>>> search(s, 345) ##この行手入力
0 9999999 1
0 4999998 2
0 2499998 3
0 1249998 4
0 624998 5
0 312498 6
0 156248 7
0 78123 8
0 39060 9
0 19529 10
0 9763 11
0 4880 12
0 2439 13
0 1218 14
0 608 15
305 608 16
305 455 17
305 379 18
343 379 19
343 360 20
343 350 21
343 345 22
345 345 23
True
>>> s = range(999999) ## s is a list
>>> search(s, 54456) ## here specify a number to search by b-search
0 999998 1
0 499998 2
0 249998 3
0 124998 4
0 62498 5
31250 62498 6
46875 62498 7
46875 54685 8
50781 54685 9
52734 54685 10
53710 54685 11
54198 54685 12
54442 54685 13
54442 54562 14
54442 54501 15
54442 54470 16
True
>>> -------------------------------------------------
例－2
def selSort(L):
for i in range(len(L) - 1):
print L
minIndx = i
minVal= L[i]
j = i + 1
while j < len(L):
if minVal > L[j]:
minIndx = j
minVal= L[j]
j = j + 1
temp = L[i]
L[i] = L[minIndx]
L[minIndx] = temp
def testSelSort():
test1 = [1,6,3,4,5,2]
raw_input('run selective test 1')
selSort(test1)
test2 = [6,1,2,3,4,5]
raw_input('run selective test 2')
selSort(test2)
test3 = [6,5,4,3,2,1]
raw_input('run selective test 3')
selSort(test3)
test4 = [1,2,3,4,5,6]
raw_input('run selective test 4')
selSort(test4)例－2 の実行結果
>>> L = [5,3,1,7,2]
>>> selSort(L)
[5, 3, 1, 7, 2]
[1, 3, 5, 7, 2]
[1, 2, 5, 7, 3]
[1, 2, 3, 7, 5]
>>>
>>> testSelSort()
run selective test 1
[1, 6, 3, 4, 5, 2]
[1, 6, 3, 4, 5, 2]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 2
[6, 1, 2, 3, 4, 5]
[1, 6, 2, 3, 4, 5]
[1, 2, 6, 3, 4, 5]
[1, 2, 3, 6, 4, 5]
[1, 2, 3, 4, 6, 5]
run selective test 3
[6, 5, 4, 3, 2, 1]
[1, 5, 4, 3, 2, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 4
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 5
[41, 12, 32, 44, 15, 61, 8, 3, 21]
[3, 12, 32, 44, 15, 61, 8, 41, 21]
[3, 8, 32, 44, 15, 61, 12, 41, 21]
[3, 8, 12, 44, 15, 61, 32, 41, 21]
[3, 8, 12, 15, 44, 61, 32, 41, 21]
[3, 8, 12, 15, 21, 61, 32, 41, 44]
[3, 8, 12, 15, 21, 32, 61, 41, 44]
[3, 8, 12, 15, 21, 32, 41, 61, 44]
>>> -------------------------------------------------
例－3 バブル・ソート
def bubbleSort(L):
for j in range(len(L)):
print L
for i in range(len(L) - 1):
if L[i] > L[i+1]:
temp = L[i]
L[i] = L[i+1]
L[i+1] = temp##def bubbleSort(L):
## swapped = True
## while swapped:
## swapped = False
## print L
## for i in range(len(L) - 1):
## if L[i] > L[i+1]:
## temp = L[i]
## L[i] = L[i+1]
## L[i+1] = temp
## swapped = True
>>> def bubbleSortSwp(L):
swapped = True
while swapped:
swapped = False
print L
for i in range(len(L) - 1):
if L[i] > L[i+1]:
temp = L[i]
L[i] = L[i+1]
L[i+1] = temp
swapped = True
def testBubbleSort():
test1 = [1,6,3,4,5,2]
raw_input('run bubble test 1')
bubbleSort(test1)
test2 = [6,1,2,3,4,5]
raw_input('run bubble test 2')
bubbleSort(test2)
test3 = [6,5,4,3,2,1]
raw_input('run bubble test 3')
bubbleSort(test3)
test4 = [1,2,3,4,5,6]
raw_input('run bubble test 4')
bubbleSort(test4) 例－3 バブル・ソートの実行結果
>>> testSelSort()
run selective test 1
[1, 6, 3, 4, 5, 2]
[1, 6, 3, 4, 5, 2]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 2
[6, 1, 2, 3, 4, 5]
[1, 6, 2, 3, 4, 5]
[1, 2, 6, 3, 4, 5]
[1, 2, 3, 6, 4, 5]
[1, 2, 3, 4, 6, 5]
run selective test 3
[6, 5, 4, 3, 2, 1]
[1, 5, 4, 3, 2, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 4
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
run selective test 5 ## オマケのテスト
[41, 12, 32, 44, 15, 61, 8, 3, 21]
[3, 12, 32, 44, 15, 61, 8, 41, 21]
[3, 8, 32, 44, 15, 61, 12, 41, 21]
[3, 8, 12, 44, 15, 61, 32, 41, 21]
[3, 8, 12, 15, 44, 61, 32, 41, 21]
[3, 8, 12, 15, 21, 61, 32, 41, 44]
[3, 8, 12, 15, 21, 32, 61, 41, 44]
[3, 8, 12, 15, 21, 32, 41, 61, 44]
>>>
>>> L = [41, 12, 32, 44, 15, 61, 8, 3, 21]
>>> print L
[41, 12, 32, 44, 15, 61, 8, 3, 21]
>>> bubbleSortSwp(L)
[41, 12, 32, 44, 15, 61, 8, 3, 21]
[12, 32, 41, 15, 44, 8, 3, 21, 61]
[12, 32, 15, 41, 8, 3, 21, 44, 61]
[12, 15, 32, 8, 3, 21, 41, 44, 61]
[12, 15, 8, 3, 21, 32, 41, 44, 61]
[12, 8, 3, 15, 21, 32, 41, 44, 61]
[8, 3, 12, 15, 21, 32, 41, 44, 61]
[3, 8, 12, 15, 21, 32, 41, 44, 61]
>>> print L
[3, 8, 12, 15, 21, 32, 41, 44, 61]
>>> Python コードのHTML表示には、Dan CederholmのSimpleCodeを使用しています。
Python コードの入出力は、Python IDLE から行っています。
-------------------------------------------------
講座第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
-------------------------------------------------
No comments:
Post a Comment