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

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


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

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

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

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

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

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

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

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

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

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

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

5.      Прочитайте работу Левоневского по классам замкнутых функций, загрузите тренажер и решите 10 задач (файл приложен к странице).

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

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

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

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

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

  1. Даны утверждения A, B, C, D, из которых ровно одно ложно. Требуется выяснить, следует ли из них утверждение E. Перечислите высказывания, к которым нужно применить метод резолюций, чтобы получить ответ.
  2. До скольких кванторов можно уменьшить набор кванторов в следующем выражении, чтобы его смысл не изменился: (Ax)(Ay)(Az)P(x)R(y)S(z) (здесь A-квантор всеобщности, а предикаты соединены конъюнкцией).
  3. Укажите все логические связки, которые могут быть поставлены вместо # так, чтобы формула исчисления предикатов была истинна (здесь A-квантор всеобщности, а E-квантор существования):
    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. определения четности числа (результат 0, если число чётное и 1, если нечётное);
    2. вычитания из большего числа  m  меньшего числа  n;
    3. деления нацело  m  на  n.

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

  1. Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для пути с  n  вершинами?
    1. Если источник совпадает с концом пути
    2. Если источник не совпадает с концом пути, но инцидентен ребру, инцидентному концу пути
    3. Если источник лежит ровно посередине пути (пути от источника до обоих концов имеют одинаковое число ребер)
  2. Сколько модификаций пометок будет сделано при реализации алгоритма Дейкстры для бинарного дерева с  2n-1  вершинами?
    1. Если источник находится в корнем дерева
    2. Если источник является листом дерева
    3. Если источник лежит на среднем уровне дерева (пути от источника до корня и до достижимого листа имеют одинаковое число ребер)
  3. Неориентированный граф изображен многоугольником с  n  вершинами. Все ребра имеют вес  1. Сколько модификаций пометок будет сделано в процессе выполнения алгоритма Флойда?
  4. Неориентированный взвешенный граф изображен многоугольником с  n  вершинами. Какое наибольшее и наименьшее количество модификаций пометок будет сделано в процессе выполнения алгоритма Форда-Беллмана, если граф не имеет циклов отрицательной длины?
  5. Граф имеет  n  вершин и  m  ребер, причем имеется  k  ребер одинакового минимального веса, а остальные ребра имеют разные веса. Укажите значения  k,  для которых минимальное остовное дерево единственно.
  6. Взвешенный неориентированный связный граф имеет  n  вершин и  m  ребер, причем имеется  k  ребер одинакового максимального веса, а остальные ребра имеют разные веса. Укажите значения  k,  для которых минимальное остовное дерево единственно.
  7. Все ребра взвешенного неориентированного связного графа имеют разную длину. При каком условии алгоритмы Прима и Краскала будут генерировать одинаковую последовательность ребер отбираемых в остовное  дерево (одинаковым должен быть не только набор ребер, но и порядок, в котором эти ребра выбираются).
ċ
Levonevsky_Post_classes_training.rar
(1409k)
Сергей Поздняков,
7 янв. 2010 г., 9:28
Comments