什么是映射缩减函数

这是（我认为）来自复杂性理论的简单问题。什么是映射缩减函数

#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()

根据映射还原DEF：
“语言A是映射还原为语言B，写入A≤的mB，如果有一个可计算的函数f：Σ* - →Σ*，其中每瓦特， w∈A⇐⇒f（w）∈B。函数f被称为从A到B的减少。一个可计算的映射函数将是f（n）= 2n（或Python中的x），但在这种情况下，那些断言没有意义，因为每个R（x）应该在{'Even' } ...？

来源

2016-09-22 Tomasz Madry

这是（我认为）从作业容易的问题。 – MisterMiyagi

所以基本上你只有E作为整数的二进制表示，只有偶数。这由最后一位数字（整数1）表示为0。所有其他数字代表2的倍数，因此无关紧要。

目标“language”只包含字符串"Even"。也就是说，每个偶数必须映射到"Even"这个词。

所以赋值实际上是：如果x表示一个偶数的二进制数，则返回"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而不是空白字。

来源

2016-09-22 12:29:23 MisterMiyagi

谢谢，我接受这一点，我需要改变我的想法做一点这样做，是的 - 这是从作业;） –

什么是映射缩减函数

回答

相关问题