Что такое функция уменьшения отображения

Это (я думаю) простая задача из теории сложности.

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

Согласно Mapping Reduction def:
«Язык A сводится к языку B, записанному A ≤ mB, если существует вычислимая функция f : Σ ∗ −→ Σ ∗ , где для каждого w, w ∈ A ⇐⇒ f (w) ∈ B. Функция f называется редукцией из A в B."
Вычислимой функцией отображения будет f(n) = 2n (или x ‹‹ y в Python), но в этом случае эти утверждения не имеют смысла, потому что каждый R(x) должен быть в {'Even'}...?


python complexity-theory turing-machines
person Community    schedule 22.09.2016    source источник
comment
Это (я думаю) простая задача из домашнего задания.   -  person MisterMiyagi    schedule 22.09.2016

Ответы (1)


arrow_upward
0
arrow_downward

Итак, в основном у вас есть E как двоичное представление целых чисел, только четных чисел. На это указывает последняя цифра (целое число 1), равное 0. Все остальные цифры представляют собой числа, кратные 2, и поэтому не имеют значения.

Целевой «язык» состоит только из строки "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 | x[-1] == '0'}, если только вы не предполагаете, что пустое слово неявно содержится в каждом языке. Однако ваши модульные тесты предполагают, что он должен что-то возвращать. Вы можете вернуть 'Odd' или None вместо пустого слова.

person MisterMiyagi    schedule 22.09.2016
comment
Спасибо, я принимаю это, мне нужно немного изменить свое мышление, делая это, и да - это домашнее задание;) - person ; 22.09.2016
comment
@T.Madry Рад быть полезным. Мне тоже пришлось немного покопаться, чтобы понять ваше задание, но в основном оно сводится к переводу тарабарщины на человеческий язык. Это освежающее изменение по сравнению с обычным домашним заданием на SO. ;) - person MisterMiyagi; 22.09.2016