Подготовка к МЛиТА-2007

Тренировочные задачи 2007 года

Оцените следующие высказывания, используя обозначения:

    +     для "утверждение всегда верно"

         для "утверждение всегда неверно"

    ?     для "утверждение может быть верно, а может быть неверно"

    !      для "вопрос поставлен некорректно, в условии есть внутренние противоречия"

    0     для "не знаю"

Первые два ответа означают, что утверждения или противоположные к ним, являются теоремами и поэтому требуют доказательства.

Для третьего варианта ответа достаточно привести два примера: один, подтверждающий высказывание, другой - опровергающий.

Для четвёртого варианта надо объяснить, в чём заключается внутренняя противоречивость условия.

Последний ответ позволяет отвечающему честно оценить уровень своих знаний на момент сдачи экзамена.

1.  Введём операцию инверсии всех слов языка I(L): I(a1 a2an) = an an-1a1

Является ли автоматным язык

а) I(L), если язык L – автоматный?

б) I(L)+L, где L= (a+bc)*?

в) I(L)*L, где L= (a+bc)*?

г) {w*I(w)| где w слово автоматного языка L}?

д) {w*I(w)| где w слово языка (a+b)*}?

2.  Рассмотрим множество булевых функций

а) образуют ли они замкнутый класс (приведите примеры функций обладающих и не обладающих этим свойством)?

б) каким из постовских классов замкнутости принадлежат функции класса R: To, T1, L, M, S?

3.  Верно ли равенство:

     а)

где P* - двойственная к P?

б)

4.  Рассмотрим множество всех возможных элементарных дизъюнкций от n переменных, каждая из которых содержит k переменных. Какое наибольшее и наименьшее число различных переменных будет содержать резольвента двух из них?

5.  Язык L автоматный, бесконечный. Оцените утверждения:

а) существует алгоритм, преобразующий грамматику этого языка в грамматику с однозначностью ветвления по первому символу;

б) язык L2 автоматный;

в) язык

автоматный;

г) существует единственный грамматический разбор каждого слова языка;

д) если грамматический разбор получен применением n правил, то слово содержит n символов.

6.      Рассмотрим множество булевых функций

Оцените утверждения:

а) функции образуют замкнутый класс;

б) функции сохраняют 0;

в) функции сохраняют 1;

г) самодвойственны;

д) монотонны;

е) линейны.

7.      Оцените утверждение:

8.      Каждая из дизъюнкций имеет вид

. Оцените необходимое и достаточное условие того, что, применяя метод резолюций, выведем xk :

а) найдутся две дизъюнкции вида

б) найдутся три дизъюнкции вида

9.      Модифицируйте алгоритм Краскала так, чтобы он определял:

а) связность графа;

б) является ли граф деревом.

10.  Имеются две унарные операции ( )2 и sin( ). Постройте алгоритм перевода выражений с этими операциями в постфиксную запись.

 

ĉ
Сергей Поздняков,
6 окт. 2009 г., 7:14
Comments