Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Пусть задана логическая схема S=(V, E) : V= {a (X), b(Y), c(Z), d(V), e(?), f(¬),g(¬),h(?), i(?), k(¬), m(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция), E= { (a, e), (b, f), (c, g), (d, e), (d, i), (e, k), (f, h), (g,, h), (h, i),(i, m), (k, m) }. Какие из следующих линейных программ вычисляют в переменной Z ту же функцию F(X,Y,Z,V), что и схема S в вершине m?
P1: P2: P3:V = X ? V; f = ¬Y; Y = ¬Y;V = ¬V; g = ¬Z; Z = ¬Z;Y = ¬Y; e = X ? V; Z = Y ?Z;Z = ¬Z; k = ¬e; Z = Z ?V;Y = Y ? Z; h = f ? g; V = X ? V;Z = Y ? V; i = h ? V; V = ¬V;Z = V ? Z . Z = h ? k. Z = Z ? V.- только P3
- (Правильный ответ) только P2 и P3
- только P2
- только P1
- только P1 и P3
- только P1 и P2
- P1, P2 и P3
Чему равна глубина схемы S3, реализующей функцию сложения трехбитовых чисел?
- (Правильный ответ) 11
- 17
- 12
- 15
- 14
Пусть задана логическая схема S=(V, E) : V= {a (X1), b(X2), c(X3), d(¬),e(¬), f(?),g(?),h(?), i(?), k(?) } (после имени вершины в скобках указана ее метка — переменная или булева функция), E= { (a, d), (a, g), (b, e), (b, f), (c, f), (c, h), (d, h), (e, g), (f,k), (g, i), (i, k) }. Какую булеву функцию реализует схема S=(V, E) в вершине k? (В ответах функции заданы последовательностями 8 нулей и единиц — их значениями на лексикографически упорядоченных наборах значений аргументов X1, X2 и X3)
- (00011101)
- (Правильный ответ) (01011101)
- (01010101)
- (01110101)
- (01011001)
Пусть задана линейная программа P со входными переменными X1, X2, X3:
- Y = ¬X1;
- Z = ¬X2;
- U = ¬X3;
- V = X1 ? X2;
- Z = Y ? Z;
- W= Y ? X2;
- Z = Z ? W ;
- V = V ? U ;
- Z = Z ? V.
- (Правильный ответ) 4
- 6
- 5
- 2
- 3
Какие из следующих схем реализуют в вершине a функцию, заданную формулой A = ((a ? ¬b) ? ¬b) ? ¬ (b? c) ?
- только S2
- только S1
- только S3
- ни одна
- S2 и S3
- (Правильный ответ) S1 и S3
- S1 и S2
Пусть задана линейная программа P со входными переменными X1, X2, X3:
- Y = X1 ? X2;
- Z = X1 ? X3;
- U = ¬X3;
- Y = Y ? Z;
- W = X2 ? X3;
- U = X2 ? U;
- Z = W ? Y ;
- Z = U ? Y.
- 5
- (Правильный ответ) 3
- 4
- 2
- 6
Какие из следующих схем реализуют в вершине a функцию, заданную формулой
A = ¬ (a ? ¬b) ? ((b? c) ? (a ? ¬b)) ?
![]()
- ни одна
- S1 и S2
- S1 и S3
- только S2
- только S1
- (Правильный ответ) только S3
- S2 и S3
![]()
Какая из следующих формул задает булеву функцию, которую реализует эта диаграмма?
- (X1 ? X3) ? (X2 ?¬X3)
- (X1 ? X3) ? (X2? X3)
- (X1 ? ¬X2 ? X3) ? (X2 ? X3))
- (X1 ? X2) ?(X2 ?X3)
- X2 ? ¬X3
- (Правильный ответ) (X2 ? ¬X3) ? (X1 ?¬X2 ? X3)
Какие из следующих УБДР являются сокращенными?
![]()
- только D1
- только D2
- D1 и D2
- (Правильный ответ) D2 и D3
- D1 и D3
- только D3
- все
Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T5,3 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- 10
- 8
- 11
- (Правильный ответ) 9
- 7
- (Правильный ответ) (01010111)
- (01011011)
- (01011101)
- (01011101)
- (01000111)
Пороговая функция Tn,k от n переменных с порогом k равна 1, если во входном наборе (x1, … , xn) имеется не менее k единиц. Постройте минимальную УБДР для пороговой функции T4,2 относительно стандартного порядка переменных: x1 < x2 < x3< x4< x5. Какова сложность этой схемы?
- 10
- 7
- (Правильный ответ) 6
- 8
- 9
- (01011101)
- (00011101)
- (Правильный ответ) (01010001)
- (01011001)
- (01010101)
Пусть задана УБДР D=(V,E): V={v1(x), v2(y), v3(y), v4(z), v5(z), v6(z), v7(w), v8(w), , 0, 1} (в скобках после имени вершины указана переменная, которой она помечена), E = { (v1, v2; 1), (v1, v3; 0), (v2, v4; 0), (v2, v5; 1), (v3, v5; 1), (v3, v6; 0), (v4, v7; 0), (v4, v8; 1), (v5, v7; 0), (v5, v8; 1), (v6, v8; 1), (v6, v7; 0), (v7, 0; 1), (v7, 1; 0), (v8, 0; 0), (v8, 1; 1)} ( для каждого ребра третий параметр после ; — его метка 0 или 1). Постройте по D эквивалентную ей сокращенную УБДР и укажите ее сложность.
- (Правильный ответ) 3
- 1
- 4
- 5
- 6
- A2 и A3
- только A2
- A1 и A2
- только A1
- (Правильный ответ) только A3
- A1 и A3
- только A3
- (Правильный ответ) только A1
- только A2
- A2 и A3
- A1 и A2
- A1 и A3
- W и V
- только U
- V и U
- только W
- только V
- (Правильный ответ) все
- W и U
- все слова вида (aba)na при n= 1, 2, 3, …
- все слова вида (ab)na при n=0, 1, 2, 3, …
- (Правильный ответ) все слова вида (ab)naa при n=0, 1, 2, 3, …
- все слова, начинающиеся на a и заканчивающиеся на a
- все слова, начинающиеся на ab и заканчивающиеся на a
- C, LC = LA ? LB
- D, LD = LA ? LB
- D, LD = LA ? LB
- C, LC = LA \ LB
- (Правильный ответ) D, LD = LA \ LB
- C, LC = LB \ LA
Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, ?> с программой ?: q 0 >? p, q 0 >? s, p 0 >? q, p 0 >? s, p 1 >? p, s 1 >? p Какие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, p, ps, qs}, q, F1={p, ps}, ?1> с программой ?1: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, ps 0 >? qs, ps 1 >? p, qs 0 >? ps, qs 1 >? p M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ?}, q, F2={p, ps, pq, qps}, ?2> с программой ?2: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, s 0>? ?, s 1>? p, ps 0 >? qs, ps 1 >? p, qs 0 >? ps, qs 1 >? p, qp 0 >? ps, qp 1 >? p, qps 0 >? qps, qps 1 >? p, ? 0 >??, ? 1 >??. M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ?}, q, F3={ p, ps, pq, qps }, ?3> с программой ?3: q 0 >? ps, q 1 >? p, p 0 >? qs, p 1 >? p, s 1>? p, ps 0 >? qs, ps 1 >? p, qs 0 >? qps, qs 1 >?qps, qp 0 >? ps, qp 1 >? p, qps 0 >? qps, qps 1 >? p. ? 0 >??, ? 1 >? ?- M1 и M3
- только M2
- M2 и M3
- только M3
- ни один
- (Правильный ответ) M1 и M2
- только M1
Пусть задан недетерминированный конечный автомат (без пустых переходов) M = < {0, 1}, {q, p, s}, q, F={p}, ?> с программой ?: q 0 >? p, q 0 >? s, q 1>? q, p 0 >? q, p 0 >? p, s 1 >? q, s 1 >? p Какие из следующих трех ДКА эквивалентны M?
M1 = < {0, 1}, {q, ps, pq, pqs}, q, F1={ ps, pq, pqs }, ?1> с программой ?1: q 0 >? ps, q 1 >? q, ps 0 >? pq, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q, pqs 0 >? pqs, pqs 1 >? pq M2 = < {0, 1}, {q, p, s, ps, qs, pq, qps, ?}, q, F2={p, ps, pq, pqs }, ?2> с программой ?2: q 0 >? ps, q 1 >? q, p 0 >? pq, p 1 >? q, ps 0 >? qs, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q, qs 0 >? ps, qs 1 >?q, pqs 0 >? pqs, pqs 1 >? pq, ? 0 >??, ? 1 >?? M3 = < {0, 1}, { q, p, s, ps, qs, pq, qps, ?}, q, F3={ p, ps, pq, pqs }, ?3> с программой ?3: q 0 >? ps, q 1 >? q, p 0 >? pq, p 1 >? q, s 0 >??, s 1 >?pq, ps 0 >? pq, ps 1 >? pq, pq 0 >? pqs, pq 1 >? q, qs 0 >? ps, qs 1 >?q, pqs 0 >? pqs, pqs 1 >? pq, ? 0 >??, ? 1 >??- M1 и M2
- только M1
- ни один
- (Правильный ответ) M1 и M3
- только M2
- M2 и M3
- только M3
- C, LC = LA \ LB
- D, LD = LA \ LB
- D, LD = LA ? LB
- (Правильный ответ) D, LD = LA ? LB
- C, LC = LB \ LA
- C, LC = LA ? LB
- D, LD = LA ? LB
- (Правильный ответ) D, LD = LA ? LB
- D, LD = LA \ LB
- C, LC = LA ? LB
- C, LC = LB \ LA
- C, LC = LA \ LB
- D, LD = LA ? LB
- D, LD = LA \ LB
- C, LC = LA ? LB
- D, LD = LA ? LB
- (Правильный ответ) C, LC = LB \ LA
- C, LC = LA \ LB
Заданы два НКА:
A =< {a, b}, {0, 1, 2, 3}, 0, {2}, ?A > с программой ?A: 0 a >? 1, 0 b >? 3, 1 a >? 3 1 b >? 2, 2 a >? 3, 2 b >? 2, 3 a >? 3, 3b >? 3 и B =< {a, b}, {q0, q1, q2}, q0, {q2}, ?B > с программой ?B: q0 a >? q0, q0 b >? q1, q1 a >? q1, q1 a >? q2 Какие из следующих трех НКА С1 , С2 , С3 распознают конкатенацию LA? LB языков, распознаваемых автоматами A и B? С1 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F1={ q2}, ?1>, С2 = < {a,b}, {0, 1, 2, 3, q0, q1, q2}, 0, F2={ q2}, ?2>, С3 = < {a,b}, {0, 1, 2, 3, q1, q2}, 0, F3={ q2}, ?3>, где программы заданы в следующих таблицах (? означает отсутствие соответствующего перехода).- C2 и C3
- только C2
- только C1
- все
- C1 и C3
- (Правильный ответ) C1 и C2
- только C3
Какой язык L является конкатенацией двух языков: L1= {?, b, ab, ba} и L2= {?, a, b, ba}?
- L = {?, a, b, ba, bb, ab, bab, aba, abba, abb, abba, abbb}
- L = {?, a, b, ba, bb, bba, aba, abbaa, ab, abb, abbab, abbaba}
- L = {a, b, ba, bb, bba, aba, abb, abba, abba, abab}
- (Правильный ответ) L = {?, a, b, ba, bb, bba, ab, aba, abba , baa, bab, baba}
- L = {a, ab, abba, aa, aba, abbaa, abb, abbab, abbaba}
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 2. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих «специальных» слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- cbn+2
- banbn+4aaa
- (Правильный ответ) bn+2canc
- bncanbbb
- cnbbbaaabb
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, в которых количество букв b превосходит количество букв a не менее чем на 3. Предположим, что L автоматный язык и что n – это константа, которая существует для него по утверждению теоремы о разрастании. Какое из следующих «специальных» слов позволяет опровергнуть это предположение, т.е. для какого из них не выполнено утверждение 3 теоремы о разрастании?
- canbn+3c
- bbbcnaabb
- bcbn+4anaca
- bn+2canc
- (Правильный ответ) ancbn+3c
Пусть язык L в алфавите {a, b, c}, состоит из всех слов, которые заканчиваются на bcc и содержат подслово aca Какая из следующих фраз определяет язык h(L), являющийся образом L при гомоморфизме h: {a, b, c}* >? {0, 1}* где h(a) = 00, h(b) = 10, h(c) = ? ?
- все слова четной длины в алфавите {0, 1}, содержащие подслово 0000
- все слова четной длины в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули
- все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на нечетных местах стоят нули и которые содержат подслово 0000
- все слова в алфавите {0, 1}, заканчивающиеся на 10, с длиной > 5
- (Правильный ответ) все слова в алфавите {0, 1}, заканчивающиеся на 10, в которых на четных местах стоят нули и которые содержат подслово 0000
Какие из следующих трех последовательностей операторов являются синтаксически правильными структурированными программами?
- P1: x := y+1; z:= x + 1; если x +1 < z то y := z иначе y:=x конец
- P2: x := y+1; z:= x +1; если x = z то y := z иначе y:=x конец
- P3: x := y+1; u:= z +1; пока u = z +1 делай y := z; u := u+1 все
- (Правильный ответ) только P2
- только P3
- P2 и P3
- P1 и P3
- все
- P1 и P2
- только P1
Пусть П+ — это построенная в лекции программа, которая вычисляет функцию Ф+(x,y) = x+y в переменной x, используя одну рабочую переменную zКакие из следующих структурированных программ П1, П2, П3 вычисляют в переменной x квадратный трехчлен p(x)= x2 +2x +2 ?
![]()
- П1 и П3
- только П1
- только П2
- (Правильный ответ) все
- П1 и П2
- П2 и П3
- только П3
Пусть структурированная программа P: x:= y+1; z := x+1; y := z+1; y:= y+1; z:= y; z := z +1 ; x := x+1 начинает работу в состоянии ? : ?(x) = 2, ?(y) =3, ?(z) =2В каком из следующих состояний ?1 она завершит свою работу?
- ?1(x) = 6, ?1(y) = 7, ?1(z) = 8
- ?1(x) = 5, ?1(y) = 6, ?1(z) = 7
- ?1(x) = 5, ?1(y) = 7, ?1(z) = 7
- ни в одном из вышеуказанных
- (Правильный ответ) ?1(x) = 5, ?1(y) = 7, ?1(z) = 8
Какое из следующих выражений задает примитивно рекурсивное описание функции f(x) = (x+1)2 ?
- ни одно из выше перечисленных
- (Правильный ответ) R( 1, [+; [s1 ;[ s1 ;[ s1 ;[+; I21, I21]]]], I22 ])
- <s
О сайте
Поделитесь в соцсетях: