MIT 6.00導論カリキュラムノート(三)

Lecture 09
にぶんほう
実はLecture 8の内容を繰り返しています.Lisp言語ストレージリストはbox pointer diagramを使用し、チェーンテーブルを使用しています.各ボックスには2つのポインタがあり、1つは次の位置を指し、1つは値オブジェクトを指します.このようにチェーンテーブルを格納する方法では、i番目のリスト要素を見つけるには、線形検索時間という順序で1つずつ来る必要があります.PythonとFortran言語はこの問題を改善し、リストを格納する別の方法を採用した.ブロック全体を使用してデータを格納します.各ブロックの各グリッドにはポインタがあり、ポインタは値オブジェクトを指します.
この2つの違いは、Pythonの方法が次のポインタを指さすことを省き、チェーンテーブルにメモリ全体を直接割り当てることです.この2つの方法にはそれぞれ優劣があり,いずれもアクセス時間と空間を比較した後の決定である.
二分法に隠された共通思想

Pick the mid point

Check to see if this is answer

If not, reduce to small problem repeat

私たちはsearchの前にsortすべきですか?
無秩序テーブルを検索する場合、複雑度はnです.秩序テーブルを検索する場合、複雑度はnlognが最も速い.しかし、もし私たちがk回検索するなら?無秩序テーブルの検索時、複雑度kn秩序テーブルの検索時、複雑度nlogn+klogn
コード#コード#

#    
def bubbleSort1(L):
    for j in range(len(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
            print L
        print '*******'

def bubbleSort(L):
    swapped = True
    while swapped:
        swapped = False
        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
                print L
        print '********'
#    
def selectionSort(L):
    for i in range(len(L)):
        minIndex = i
        minVal = L[i]
        for j in range(i,len(L)):       
            if L[j] < minVal:
                minIndex = j
                minVal = L[j]
        L[minIndex] = L[i]
        L[i] = minVal
        print L

Lecture 10
ぶんかつほう
分治アルゴリズムの概要手順

問題を同型のサブ問題

に分割する.

これらのサブ問題を単独で解決する

これらの解決策

と連携する
集計ソート
集計ソートは分治法の重要な例である.

リストを半分に分割

各リストに1つの要素があるまで分割を続ける

は、これらのサブリスト

を集計する

def merge(left, right):
    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):
    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

ハッシュ

ハッシュアルゴリズムは、リスト内の各要素に対応するインデックス値を与えることを意味する.

時間を空間

で与える

完全平均ハッシュアルゴリズムを作成することは困難である(完全平均は、リスト内の各要素が取得された時間が同じであることを意味する)コード例

.

#                 ，    small-large
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
#               ，        ascii  
def hashChar(e):
    return ord(e)
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

Exception異常
これはpythonのもう一つの構文メカニズムです.に分けることができます

Unhandled exception

Handled exception

コードの例

#try...except   tri-accept block
def readFloat(requestMsg,errMsg):
    '''test exception'''
    while True:
        val = raw_input(requestMsg)
        try:
            val = float(val)
            return val
        except:
            print errMsg

例外(Exception)とアサーション(Assert)を区別する私の理解は、アサーションはユーザーが要求に合わない値を出力することを防止するために強制的にチェックして終了することである.異常は、プログラムが本当に実行されているときにめちゃくちゃなエラーを防止することです.
Lecture 11
この授業はほとんど純粋な理論のもので、テストとデバッグを話しています.

検証(Validation):問題を隠し、自信を高めるプロセスであり、テスト(testing)とルックアップ(reasoning)の集合である.

デバッグ:プログラムが失敗した問題を特定して解決します.

防衛性プログラム設計Testing

テスト:主に入力/出力の表現

を考察する

は主にユニットテストと集積テスト

に分けられる.

テストセットの選択は合理的で、私たちに自信を与えることができるほど大きく、時間が合理的でなければならない.bugはbugについて2つの西洋式のでたらめがある

bugs crawl in programs

bugs breed
ジョンは2つの非常に良いデバッグツールがあると考えています.1つはprint文で、もう1つはコード読書です.

デバッグについては、もう一つの重要な考えがあります.システム化の考えです.どのようにシステム化しますか?

研究プログラムテキスト

を挽回する方法を検討する

このエラーを生成する最も簡単な入力

を探します.

二分法エラーが発生する可能性のある場所を検索

コードの例:

def silly():
    res=[]
    done=False
    while not done:
        elem = raw_input('Enter element, return when done')
        if elem == '':
            done = True
        else:
            res.append(elem)
    #      ：          ，       
    #print 'res ',res
    #    ，‘=’             
    tmp = res
    #        
    #tmp = res[:]
    tmp.reverse()
    print 'res ',res,' tmp ',tmp
    #   ，        print，    
    #  bug  ，bug    tmp res       
    isPal = (res == tmp)
    if isPal:
        print 'is palindrome'
    else:
        print 'not palindrome'

Lecture 12
デバッグについて
プログラマがよく犯す小さなエラーは、次のとおりです.

引数の順序エラー

スペルエラー

初期化エラー

Object vs Values

仮名エラー

副作用
私たちは自分のミスモデルを構築する必要があります.

ジョンのプログラマに対するアドバイスは次のとおりです.

あなたのすべての過去の試みを記録して、間違いを繰り返さないでください

コード構想を再考

注釈

ではなくデバッグコード

他者の助けを求める

休憩してから

を見に来ます

ゆっくりして、急いで

に達しません.

制御コードの行数

古いバージョンを保存する最適化の問題は、簡単に言えば、

の2つの部分です.

極値を求める関数

関数の制約

古典的な最適化問題には,最短経路問題,旅行者問題,シーケンス整列問題などがある.次に紹介するのはリュックサックの問題です.
リュックサック問題
泥棒を仮定すると、彼は8ポンドのリュックサックしかなく、3種類の貨物、4ポンドの金砂、3ポンドの銀砂、10ポンドのブドウの幹があります.もしこの泥棒が最も価値のある分配を手に入れたいなら、彼はどうすればいいですか?明らかな方法は、まず4ポンドの金砂を入れて、それから3ポンドの銀砂を入れて、最後に1ポンドのブドウの幹を入れます.なぜこの問題は連続リュックサックだと言いますか?金砂や銀砂は無限小と見なすことができるからです.この問題の数学的記述は
function=cg×pg+cs×ps+cr×pr
constraints=pg+ps+pr≤8
内
cg,cs,crはそれぞれ金砂の価値、銀砂の価値、ブドウの価値を代表している.
pg,ps,prはそれぞれ金砂の重量,銀砂の重量,ブドウ幹の重量を表す.
この問題は貪欲なアルゴリズムで解決できる.
でも、
ローカル最適化は、常にグローバル最適化を保証するものではありません.
不連続リュック問題
0/1 Knapsack Problem不連続リュックサック問題でアイテムの重さはこれ以上細分化できません.同じ泥棒で、彼は8ポンドの容量のリュックサックを持っていて、部屋の中の品物はあります

表、重さ0.5ポンド、価値A位、2枚

ラジオ、重さ2ポンド、価値Dビット、2枚

Tiffany花瓶、重さ5ポンド、価値B位、2つの

Velvet Evis、重さ6ポンド、価値Cビット、2枚

今は泥棒が3人います

貪欲な泥棒で、貪欲なアルゴリズム(greedy algorithm)を使って、彼の選択は先に最も高い、つまり表

心を込めて考えている慢性的な泥棒は、蛮力法(Bruce algorithm)を使って、彼の選択はすべての選択を試して、彼は最後に最適解を試していないで警察署に逮捕された.

には、私たちのような賢い泥棒が最後にいます.

数学の公式で上記の問題を説明します
function=∑i=1nPiXi
constraint=∑i=1nwiXi
ここで、
nは品物の総数であり、
wiは第
i個の品物の重量、
Piは第
i個の品物の価値、
Xはベクトルであり、例えば
(0,0,0,0,0,0,0,0)は、8つのアイテムのうちいずれも取っていないことを表します.
ダイナミックプログラミング
Dynamin Programming、ジョンはこの名前に何の意味もないと言った.
そのポイントは

overlapping subproblems(オーバーラップサブ問題)

optimal substructrure(サブ構造の最適化)