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

Lecture 13
動的プログラミング,オーバーラップサブ問題,最適化サブ構造は一般に,再帰型問題は,以前に述べたペポナッチ数列のようなオーバーラップサブ問題(overlapping sub−problem)を有する.

def fib2(x):
    global numCalls
    numCalls += 1
    print 'fib called with: ',n,' numCalls: ',numCalls
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1)+fib(x-2)

この関数には実行時間の問題があり、実行時には以前に実行した内容を繰り返し実行し、問題の規模が大きくなるにつれて、この劣勢がますます明らかになった.そのため、ジョンは記憶化の方法(Memorization)を提案した.
Memorization
ユーザは1つの辞書を自作し,1回目に実行した価値のある結果を記録し,その値を再実行すると,まず辞書で検索(hashアルゴリズム)し,実行しなかった.この方法にはTable-lookupという統一された名前があり,その特例はMemorizationである.Memorization化されたペポナッチコードは以下の通りである.

def FastFib(n, memo):
    global numCalls 
    numCalls += 1
    print 'fib called with ',n
    if not n in memo:
        memo[n] = FastFib(n-1,memo) + FastFib(n-2, memo)
    return memo[n]

def fib(n):
    memo = {0:1,1:1}
    return FastFib(n,memo)

0/1バックパック問題
まず、「最適サブ構造」という概念を明確にし、英語では以下のように説明します.
Global optimal solution can be constructed from optimal solution to sub-problems.
一つの問題の最適解はサブ問題の優解から構成できることを意味する.不連続リュックサックの問題を再説明します.
We have a collection of objects called ‘A’, for each object in A we have found the subject of A that has the maximum value subject to the weight constraint.
を選択して、制約条件で最大値を取得したAのサブセットを探します.Aにn個のオブジェクト,|A|=nがあると仮定すると,可能なサブセット数は2 nであり,これは指数型の問題である.この問題を決定ツリーで分析します
n=3,maxWeight=5
w=[5,3,2]
v=[9,7,8]
depth first/left firstを用いた解析を行った.
コードは次のとおりです.

def maxValue(w,v,i,aW):
    '''w:=weight v:=value,i:=index,aW:=available weight return:=total value'''
    print 'call ',i,' ',aW
    global numCalls
    numCalls += 1
    if i == 0:
        if w[i] <= aW:
            return v[i]
        else:
            return 0
    #dont't take branch
    without_i = maxValue(w,v,i-1,aW)
    if w[i] > aW:
        return without_i
    else:
        with_i = v[i] + maxValue(w,v,i-1,aW-w[i])
    return max(with_i,without_i)

ここでは依然としてMemorizationメソッドを使用しています

def fastMaxVal(w,v,i,aW,m):
    global numCalls
    numCalls += 1
    try:
        return m[(i,aW)]
    except KeyError:
        if i == 0:
            if w[i] <= aW:
                m[(i,aW)] = v[i]
                return v[i]
            else:
                m[(i,aW)] = 0
                return 0
        without_i =fastMaxVal(w,v,i-1,aW,m)
        if w[i] > aW:
            m[(i,aW)] = without_i
            return without_i
        else:
            with_i = v[i] + fastMaxVal(w,v,i-1,aW-w[i],m)
        m[(i,aW)] = max(with_i,without_i)
        return m[(i,aW)]


def maxVal0(w,v,i,aW):
    m = {}
    return fastMaxVal(w,v,i,aW,m)

Lecture 14
リュックの問題の分析、対象に向かってプログラミングして紹介します実はこれからリュックの問題の分析に対して私はあまり理解していませんまず、Memorization化の決定の木の解法の複雑さに対して分析を行います.分析によると、この解法の時間的複雑度はO(ns)であり、空間的複雑度もO(ns)であり、そのうちnは物品の数を指し、sはリュックサックの容積を指し、次は分からないものである.

この問題の複雑さは問題の規模+解法の規模(size of problem+size of solution)

に依存する.

擬似多項式アルゴリズム(Pseudo-polynomialgorithm)

数値入力多項式(polynomial in numeric value of input)

コンストレイント条件を総重量+総容積制限に変更すると?では、数学の表現は?
func=∑inPiXi
Cons:=∑i=1nWiXi≤C,∑i=1nViXi≤K
Cはリュックの総重量で、
Kはリュックの総容量
まとめ:

時空トレードオフ

指数型問題

を恐れないでください.

動的プログラミングは有用な

である.

問題降格

モジュール化
次に、オブジェクト向けの知識を紹介します.まず、モジュール(Module/Modularity)

は相関関数の集合である

関数(refer to functions using notation)

を呼び出すには、
例:

math.sqrt(n)

Classes

オブジェクト(object):データと関数の集合(a collectio of data and functions)

クラス(classes):共通の特徴を持つオブジェクトの集合(a collectio of objects with characteristics in common)

コアコンセプトは、ユーザー定義のタイプを生成することです.
Lecture 15
abstract data type,classes and methodsはクラスの例を挙げます.

#           ？
#     ：    
def addPoint(p1,p2):
    r = []
    r.append(p1[0]+p2[0])
    r.append(p1[1]+p2[1])
    return r

#p = [1,2]
#q = [3,1]
#r = addPoint(p,q)
#print r

'''point as classes'''
class cartesianPoint():
    pass
cp1 = cartesianPoint()
cp2 = cartesianPoint()
cp1.x = 1.0
cp1.y = 2.0
cp2.x = 3.0
cp2.y = 1.0

def samePoint(p1,p2):
    return (p1.x == p2.x) and (p1.y == p2.y)
def printPoint(p):
    print '['+str(p.x)+', '+str(p.y)+']'

class polarPoint():
    pass
pp1 = polarPoint()
pp2 = polarPoint()
pp1.radius = 1.0
pp1.angle = 0
pp2.radius = 2.0
pp2.angle = math.pi/4.0
#                          
class cPoint:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        self.radius = math.sqrt(self.x*self.x+self.y*self.y)
        self.angle = math.atan2(self.y,self.x)
    def cartesian(self):
        return (self.x,self.y)
    def polar(self):
        return (self.radius,self.angle)
    def __str__(self):
        return '('+str(self.x)+','+str(self.y)+')'
    def __cmp__(self,other):
        return (self.x > other.x) and (self.y > other.y)
#    
class Segment:
    def __init__(self,start,end):
        self.start = start
        self.end = end
    def length(self):
        #          
        return math.sqrt((self.start.x-self.end.x)*(self.start.x-self.end.x)+(self.start.y-self.end.y)*(self.start.y-self.end.y))

クラス(Class):オブジェクトにインスタンスを作成するテンプレートの浅い等しい:同じメモリ領域を指す深い等しい:ユーザーがselfを等しくする方法を定義できる:selfを使用して特定のインスタンスデータを非表示にする(Data hiding):定義された方法からインスタンスの値しか取得できません.
しかしpythonにはこのような絶対的なメカニズムはありません.
Lecture 16
カプセル化、継承、マッピングコードの例

class Person(object):
    def __init__(self,family_name,first_name):
        self.family_name = family_name
        self.first_name = first_name
    def familyName(self):
        return self.family_name
    def firstName(self):
        return self.first_name
    def __cmp__(self,other):
        return cmp((self.family_name,self.first_name),(other.family_name,other.first_name))
    def __str__(self):
        return '<Person: %s %s>'%(self.first_name,self.family_name)
    def say(self,toWhom,something):
        return self.first_name+' '+self.family_name+' says to '+toWhom.firstName()+' '+toWhom.familyName()+': '+something
    def sing(self,toWhom,something):
        return self.say(toWhom,something+' tra la la')


class MITPerson(Person):
    '''subclass can inherit Person's attribute'''
    nextIDNum = 0
    def __init__(self,family_name,first_name):
        Person.__init__(self,family_name,first_name)
        self.idNum = MITPerson.nextIDNum
        MITPerson.nextIDNum += 1
    def getIdNum(self):
        return self.idNum
    def __str__(self):
        return '<MIT Person: %s %s>'%(self.first_name, self.family_name)
    def __cmp__(self,other):
        return cmp(self.idNum, other.idNum)

#p1 = MITPerson('Smith','Fred') 
#p2 = MITPerson('Foobar','Jane') 
#print p1.getIdNum() 
#print p2.getIdNum()

class UG(MITPerson):
    def __init__(self,family_name,first_name):
        MITPerson.__init__(self,family_name,first_name)
        self.year = None
    def setYear(self,year):
        if year > 5:
            raise OverflowError('Too many')
        self.year = year
    def getYear(self):
        return self.year
    def say(self,toWhom,something):
        return MITPerson.say(self,toWhom,'Excuse me, but '+something)

class Prof(MITPerson):
    def __init__(self,family_name,first_name,rank):
        MITPerson.__init__(self,family_name,first_name)
        self.rank = rank
        self.teaching = {}
    def addTeaching(self,term,subj):
        try:
            self.teaching[term].append(subj)
        except KeyError:
            self.teaching[term] = [subj]
    def getTeaching(self,term):
        try:
            return self.teaching[term]
        except KeyError:
            return None
    def lecture(self,toWhom,something):
        return self.say(toWhom,something+' as it is obvious')
    def say(self,toWhom,something):
        if type(toWhom) == UG:
            return MITPerson.say(self,toWhom,'i do not understand why you say '+something)
        elif type(toWhom) == Prof:
            return MITPerson.say(self,toWhom,'i really liked your paper on '+something)
        else:
            return self.lecture(toWhom,something)

class Faculty(object):
    def __init__(self):
        self.names = []
        self.IDs = []
        self.members = []
        self.place = None
    def add(self,who):
        if type(who) != Prof:
            raise TypeError('not a professor!')
        if who.getIdNum() in self.IDs:
            raise ValueError('duplicate ID')
        self.names.append(who.familyName())
        self.IDs.append(who.getIdNum())
        self.members.append(who)
    def __iter__(self):
        self.place = 0
        return self
    def next(self):
        if self.place >= len(self.names):
            raise StopIteration
        self.place += 1
        return self.members[self.place-1]

唯一また言うのは反復器です:iterとnextの方法は共にfor循環を創造しました