Подготовка к экзамену по МЛиТА

ПОДГОТОВКА К ЭКЗАМЕНУ ПО МЛиТА 2009-2010

Рекомендуемый порядок подготовки:

1. Переписать или дописать (если были пропуски лекций) конспект, попутно разбираясь в доказательствах (для тех, у кого конспект полон, этот этап можно пропустить).

2. Изучить все вопросы, обсужденные в курсе лекций, по учебнику С.Н. Позднякова и С.В. Рыбина "Дискретная математика" и решить предложенные там примеры и задачи (полезно один и тот же материал рассматривать с разных точек зрения). Примечание: учебник в электронной форме находится на этом сайте.

3. Попробовать самостоятельно сформулировать все определения, теоремы и объяснить их одному из своих друзей, которые готовятся к этому экзамену (будет обоюдная польза). Советую при этом привести примеры и контрпримеры, поясняющие особенности определений и теорем (объяснить "на пальцах").

4. Решить самостоятельно или совместно с кем-либо все задачи, сформулированные в курсе лекций.

5. Выбрать по одной из задач каждого раздела, помещенных ниже, и попробовать решить их за полтора часа (имитация письменного экзамена). Эту тренировку проделывать ежедневно (не менее трех раз за время подготовки к экзамену). Решения тех задач, за которые вы брались (решили их или нет) попросить лектора разобрать на консультации.

Булевы функции

1. Сколько существует булевых функций, сохраняющих ноль и единицу?

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

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

4. Постройте диаграмму Хассе для проверки монотонности функций от 4 переменных.

5. Выразите штрих Шеффера через стрелку Пирса и, наоборот. Объясните свои выкладки на основе теоремы Поста.

6. Сколько существует линейных булевых функций, сохраняющих ноль?

7. Сколько существует линейных булевых функций, сохраняющих единицу?

8. Постройте многочлен Жегалкина от пяти переменных (в канонической форме), который принимает значения «истина» тогда и только тогда, когда одна из переменных принимает значение «истина», а остальные – значения «ложно».

Исчисление высказываний и предикатов. Метод резолюций.

• 1. Даны утверждения A, B, C, D, из которых ровно одно ложно. Требуется выяснить, следует ли из них утверждение E. Перечислите высказывания, к которым нужно применить метод резолюций, чтобы получить ответ.

  2. До скольких кванторов можно уменьшить набор кванторов в следующем выражении, чтобы его смысл не изменился: (Ax)(Ay)(Az)P(x)R(y)S(z) (здесь A-квантор всеобщности, а предикаты соединены конъюнкцией).

  3. Укажите все логические связки, которые могут быть поставлены вместо # так, чтобы формула исчисления предикатов была истинна (здесь A-квантор всеобщности, а E-квантор существования):

     1. 1. (Ax)(P(x)#Q(x)) = (Ax)P(x)# (Ax)Q(x)

        2. (Ax)(P(x)#Q(x)) => (Ax)P(x)# (Ax)Q(x)

        3. (Ax)(P(x)#Q(x)) => (Ex)P(x)# (Ax)Q(x)

  4. Введем новый квантор Q, который определяется так (Qx)P(x)=(Ex)P(x)&(Ex)!P(x) (здесь E-квантор существования, & - конъюнкция, ! - отрицание). Будет ли верна следующая формула: (Qx)(Ey)P(x;y)=(Ey)(Qx) P(x;y). Проверьте другие формулы, аналогичные формулам, рассмотренным в курсе лекций. Указание. Проверьте формулу на множестве M={a; b}, выразив новый квантор через известные логические связки.

Языки и грамматики

1. Является ли автоматным язык, полученный симметричной разностью двух языков? Докажите.

2. Является ли язык палиндромов (слова, читающиеся справа налево и слева направо одинаково)

a. автоматным?

b. контекстно-свободным?

Математическая теория алгоритмов

• 1. Постройте конечный автомат для вычитания 1 из числа, заданного в двоичной системе (на вход подаются цифры исходного числа в обратном порядке, то есть, начиная с цифр младших разрядов).

  2. Постройте конечный автомат для возведения в куб степени двойки в двоичной системе (цифры подаются слева направо, например, на входе 100, на выходе 1000000).

  3. Можно ли построить конечный автомат для возведения в куб произвольного в двоичной системе? Ответ обоснуйте.

  4. Постройте машину Тьюринга для перевода числа из единичной системы в двоичную.

  5. Постройте нормальный алгорифм Маркова для перевода числа из единичной системы в двоичную.

  6. Опишите с помощью частично-рекурсивных функций алгоритм

     1. 1. определения четности числа (результат 0, если число чётное и 1, если нечётное);

        2. вычитания из большего числа m меньшего числа n;

        3. деления нацело m на n.

Прикладная теория алгоритмов

• 1. Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для пути с n вершинами?

     1. 1. Если источник совпадает с концом пути

        2. Если источник не совпадает с концом пути, но инцидентен ребру, инцидентному концу пути

        3. Если источник лежит ровно посередине пути (пути от источника до обоих концов имеют одинаковое число ребер)

  2. Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для бинарного дерева с 2ⁿ-1 вершинами?

• • • 1. Если источник находится в корнем дерева

      2. Если источник является листом дерева

      3. Если источник лежит на среднем уровне дерева (пути от источника до корня и до достижимого листа имеют одинаковое число ребер)

• 3. Неориентированный граф изображен многоугольником с n вершинами. Все ребра имеют вес 1. Сколько модификаций пометок будет сделано в процессе выполнения алгоритма Флойда?

  4. Неориентированный взвешенный граф изображен многоугольником с n вершинами. Какое наибольшее и наименьшее количество модификаций пометок будет сделано в процессе выполнения алгоритма Форда-Беллмана, если граф не имеет циклов отрицательной длины?

  5. Граф имеет n вершин и m ребер, причем имеется k ребер одинакового минимального веса, а остальные ребра имеют разные веса. Укажите значения k, для которых минимальное остовное дерево единственно.

  6. Взвешенный неориентированный связный граф имеет n вершин и m ребер, причем имеется k ребер одинакового максимального веса, а остальные ребра имеют разные веса. Укажите значения k, для которых минимальное остовное дерево единственно.

  7. Все ребра взвешенного неориентированного связного графа имеют разную длину. При каком условии алгоритмы Прима и Краскала будут генерировать одинаковую последовательность ребер отбираемых в остовное дерево (одинаковым должен быть не только набор ребер, но и порядок, в котором эти ребра выбираются).

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

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

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

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

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

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

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

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

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

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

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

Вариант 1.

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

2. Существует ли конечный автомат для сравнения двух чисел (можно считать, что они записаны в двоичной системе счисления и цифры одного разряда рассматриваются как единый символ ввода, таким образом символы алфавита: 00, 01, 10, 11, *0, *1, 0*, 1*, **, где звёздочка изображает отсутствие цифры). Если "да", то постройте его.

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. Оценить утверждение