マッピングリダクション機能とは

Question

これは複雑な理論から簡単な問題です。

#Consider the language E over the binary alphabet 
#consisting of strings representing even non-negative 
#integers (with leading zeros allowed). 
#I.e. E = {x | x[-1] == '0'}. 
# 
#Reduce E to the language {'Even'} by implementing 
#the function R 
def R(x): 
    #Code 


def main(): 
    #test cases 
    assert(R('10010') in ['Even']) 
    assert(R('110011') not in ['Even']) 

if __name__ == '__main__': 
    main() 

デフマッピング削減によると：
「言語Aが計算可能関数fがある場合≤ヘクトパスカル、 を書かれた、言語Bに還元可能マッピングです：Σ* - →Σ*、すべてのワットのために、 w∈A⇐⇒f（w）∈B 関数fはAからBへの縮小と呼ばれます。
計算可能なマッピング関数はf（n）= 2n（またはPythonではx < <）ですが、そのようなアサーションはすべてのR（x）が{'Even' } ...？

Answer 1

したがって、基本的には整数のバイナリ表現として偶数のみのEがあります。これは、最後の数字（整数1）が0で示されます。他の桁はすべて2の倍数を表し、従って重要ではない。

ターゲットの「言語」は、文字列"Even"で構成されています。つまり、すべての偶数は、単語"Even"にマップする必要があります。

したがって、割り当ては実質的に次のとおりです。xが偶数の2進数を表す場合は、"Even"を返します。それ以外の場合は別の値を返します。

が

def R(x): # shortest/fastest option 
    return 'Even' if x[-1] == 0 else '' 

def Rdocs(x): 
    """ 
    Map any of {x | x[-1] == '0'} to {'Even'} 

    Uses the definition {x | x[-1] == '0'} 
    """ 
    if x[-1] == '0': # check that x satisfies definition of even binary 
     return 'Even' 
    return '' 

一つも明示的なマッピングでこれを行うことができます。また

translate = {'0': 'Even', '1': ''} 
def Rmap(x, default=''): 
    """ 
    Map any of {x | x[-1] == '0'} to {'Even'} 

    Uses a literal mapping of x[-1] 
    """ 
    return translate[x[-1]] 

、あなたはバイナリに変換することができます

最も簡単な方法は、さらに進数の定義をチェックすることです番号に。 Pythonのintタイプもバイナリリテラルを取る：私は技術的に推測

def Rbin(x): 
    """ 
    Map any of {x | x[-1] == '0'} to {'Even'} 

    Uses python builtin to evaluate binary 
    """ 
    return '' if int(x, 2) % 2 else 'Even' 

、R(x)あなたは空の単語が暗黙のうちにすべての言語に含まれていると仮定しない限りのみは、{x | x[-1] == '0'}内のすべてのxのために定義する必要があります。あなたのユニットテストは、何かを返さなければならないことを示唆しています。空の単語の代わりに'Odd'またはNoneを返すことができます。