Главная /
Введение в схемы, автоматы и алгоритмы /
Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5
Пороговая функция Tn,k
от n переменных с порогом k
равна 1, если во входном наборе (x1, … , xn
) имеется не менее k
единиц. Постройте минимальную УБДР для пороговой функции T4,2
относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5
. Какова сложность этой схемы?
вопрос
Правильный ответ:
10
8
9
7
6
Сложность вопроса
15
Сложность курса: Введение в схемы, автоматы и алгоритмы
92
Оценить вопрос
Комментарии:
Аноним
Я сотрудник деканата! Незамедлительно сотрите сайт vtone.ru с ответами интуит. Пожалуйста
20 сен 2017
Аноним
Это очень простецкий решебник интуит.
15 авг 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # Используя теорему о разрастании, установите, какие из следующих трех языков в алфавите {a, b} не являются автоматными. L1 = { ww | w = b2anb , n > 0 }, L2 = { b2anb | n > 0 }, L3 = { (ab)nanb | n > 0 }.
- # Пусть заданы три функции: f(x,y,z) = xy +z, g(x,y) = 2x + y, h(x) =2x2 Какую функцию F(x1,x2) задает выражение [f; [h; I21 ] [g; [h; I22 ], I22], I22] ?
- # Пусть функция rm(x, y) = y mod x равна остатку от деления y на x ( rm(0,y)=y), а функция p(n) принимает значение 1, если число n простое, и равна 0 для составных n (p(0)=p(1)=0, p(2)=p(3)=1, …). Какое из следующих выражений определяет число dp(x) различных простых делителей числа x?
- # Пусть машина Тьюринга M имеет алфавит ленты Σ={ ∧, 0, 1}, алфавит состояний Q= {q, p, r, !}, начальное состояние q, заключительное состояние ! и программу Ф: \begin{array}{lll} q\ 0 \rightarrow q\ 0\ П & p\ 0 \rightarrow p\ 1\ Л & r\ 0 \rightarrow r\ 0\ Л q\ 1 \rightarrow q\ 1\ П & p\ 1 \rightarrow r\ 0\ Л & r\ 1 \rightarrow r\ 1\ Л q \wedge \rightarrow p \wedge Л & p \wedge \rightarrow ! \wedge П & r \wedge \rightarrow ! \wedge П \end{array} В какую из следующих заключительных конфигураций она перейдет, начав работу в конфигурации q 1100 ?
- # Предположим, что в некоторой конфигурации машины Тьюринга M на ленте записано слово w в алфавите Σ, не содержащем символов ∧ и *, но головка "заблудилась" – она наблюдает символ ∧ и не знает левее или правее слова w находится. Какие из следующих программ помогут найти начало слова w, т.е. любую конфигурацию вида q ∧k w или w∧k q ∧ (k > 0) переведут в конфигурацию q'w ? (В текстах программ a – это произвольный символ из Σ, используемые состояния: q, q', l, r, l1, r1 , l2 , r2, l3, r3, l4) P1: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 a→ l2 a Л, l2 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н. P2: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ q'a Н, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н. P3: q ∧ → l1 * Л, l1∧→ r * П, l1a→ l2a П, l2 ∧→ l2∧ П, l2 *→ l3∧ Л, l3 ∧→ l3∧ Л, l3 a→ l4 a Л, l4 a→ l4 a Л, l4 ∧→ q'∧ П, r∧ → r ∧ П, r *→ r1 ∧ П, r1 ∧→ l * Л, l ∧→ l ∧ Л, l *→ l1 ∧ Л, r1 a→ r2a Л, r2 ∧→ r2∧ Л, r2 *→ r3∧ П, r3∧→ r3∧ П, r3 a→ q'a Н.