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

Тренировочные варианты 2008

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

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

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

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

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

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

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

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

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

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

Вариант 1.

1.      Даны две машины Тьюринга, одна из которых копирует натуральное число в единичной системе счисления, другая умножает два числа в этой системе (Q1…1––> Q1…1*1…1; Q1…1*1…1––> Q1…..1). Постройте машину Тьюринга, вычисляющую значение выражения x2+x+1 на основе двух заданных машин. Построение обоснуйте.

2.      Верно ли, что следующая функция является примитивно-рекурсивной: функция

F(n; m) = ЕСЛИ  n<m  ТО  0  ИНАЧЕ  1.

3.      Сколько существует различных булевых функций от n переменных, у которых нет фиктивных переменных?

4.      Класс А получен замыканием набора {1; XOR}. Класс B получен замыканием набора {AND; XOR}. Оценить утверждение

 

Вариант 2.

1.      Рассмотрим класс булевых функций, задаваемых формулами, в состав которых входят только операции XOR и AND. Постройте алгоритм минимизации для данного класса и обоснуйте его корректность.

2.      В построение регулярных выражением введём новую операцию – возведение в квадрат, которая будет означать конкатенацию каждого слова, определяемого возводимым в квадрат выражением, с самим собой. Верна ли для получившихся выражений теорема Клини? А если операцию итерации заменить возведением в степень  n, которое воспринимать как конкатенацию каждого слова возводимого выражения с самим собой  n-1  раз?

3.      Связный граф с n вершинами и m ребрами имеет ровно два простых цикла по k рёбер в каждом, которые имеют одно общее ребро. Общих ребер для всех трех циклов нет. Вес каждого ребра, входящего в первый цикл,  равен 1. Вес остальных ребер – 2. Как связаны числа  n, m  и  k? Каков вес минимального остовного дерева? Сколько различных минимальных остовных деревьев имеет граф?

4.      Оценить утверждение


 

 

Решение задачи «Верно ли, что следующая функция является примитивно-рекурсивной: функция

F(n; m) = ЕСЛИ  n<m  ТО  0  ИНАЧЕ  1»:

P(0)=0

P(x+1)=x

-функция вычитания 1 для всех чисел, для которых это возможно, а иначе равная 0

 

Sub(x;0)=x

Sub(x;y+1)=P(Sub(x;y))

- положительная часть разности  x  и  y

 

Sign(0)=0

Sign(x+1)=S(0)=1

- сигнум всех неотрицательных целых чисел

 

If(x;y)=Sign(Sub(x;y))=if x>y then 1 else 0

- оператор ветвления

 

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