Geum.ru

Вопросы к экзамену по курсу «Основы дискретной математики»

Вид материалаВопросы к экзамену
Подобный материал:
Вопросы к экзамену по курсу «Основы дискретной математики»

Лектор: С.Н. Селезнева;

Летняя сессия 2010-2011учебного года.


В билете два вопроса (один из части А и один из части В) и задача.


Часть А – ответ без подготовки по любым материалам (конспекты, книжки, распечатки лекций и т.д.), проверяется понимание доказательств; определения и теоремы формулируются без конспектов.

  1. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
  2. Формула включений-исключений.
  3. Частично упорядоченные множества. Цепь и антицепь, длина и ширина конечного частично упорядоченного множества. Булев куб. Его длина и ширина.
  4. Класс самодвойственных функций, его замкнутость.
  5. Лемма о нелинейной функции.
  6. Теорема Поста о полноте систем булевых функций.
  7. Предполный класс в P2. Теорема о предполных классах в P2.
  8. Графы. Связность, компонента связности. Леммы об удалении и добавлении ребер для связных графов. Теорема о числе компонент связности графа.
  9. Деревья. Теорема об эквивалентных определениях дерева.
  10. Упорядоченные корневые деревья, их коды и верхняя оценка их числа.
  11. Раскраски вершин графа. Теорема о раскраске планарных графов в пять цветов.
  12. Алфавитный код, его взаимная однозначность. Теорема Маркова о существовании алгоритма распознавания взаимной однозначности алфавитного кода.
  13. Алфавитный код. Неравенство Макмиллана.
  14. Префиксный код. Теорема о существовании префиксного кода с заданными длинами кодовых слов.
  15. Оптимальный код. Свойства оптимальных кодов. Теорема редукции. Метод Хаффмена построения оптимального кода.
  16. Коды, обнаруживающие и исправляющие t ошибок замещения, их критерии. Оценка функции Mt(n)
  17. Коды Хэмминга. Теорема об алгоритмах кодирования, исправления ошибки и декодирования кода Хэмминга. Оценка функции M1(n).
  18. N-разрядный умножитель, верхняя оценка Карацубы сложности n-разрядного умножителя.
  19. Схемы из функциональных элементов дизъюнкции, конъюнкции и отрицания и единичной задержки (СФЭз). Автоматность их отображений.
  20. Реализация автоматной функции СФЭз.
  21. Эксперименты с автоматами. Отличимые и неотличимые состояния автомата. Теорема Мура.


Часть В – ответ без конспектов и почти без подготовки.

  1. Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Свойства биномиальных коэффициентов.
  2. Отношение эквивалентности, примеры. Классы эквивалентности, теорема об их свойствах. Фактор-множество.
  3. Отношение частичного порядка, примеры. Сравнимые и несравнимые элементы. Линейный порядок. Минимальные и наименьший элементы, теорема о свойствах минимального элемента. Максимальные и наибольший элементы.
  4. Булевы функции. Существенная и фиктивная переменная функции, равенство и конгруэнтность функций. Формула, функция, реализуемая формулой. Эквивалентные формулы.
  5. Дизъюнктивные и конъюнктивные нормальные формы. Теоремы о совершенных ДНФ и КНФ булевой функции.
  6. Полиномы. Терема Жегалкина о задании булевой функции полиномом.
  7. Операция замыкания, ее свойства. Замкнутый класс и полная система. Примеры полных систем (с доказательствами их полноты).
  8. Классы функций, сохраняющих константу, и линейных функций. Их замкнутость.
  9. Класс монотонных функций, его замкнутость.
  10. Лемма о несамодвойственной функции.
  11. Лемма о немонотонной функции.
  12. Теорема о максимальном числе функций в базисе P2.
  13. Графы, изоморфизм графов. Формула Эйлера для степеней вершин в графе.
  14. Дерево, остовное дерево графа. Теорема об остовном дереве связного графа.
  15. Геометрическая реализация графов в n-мерном пространстве. Теорема о реализации графов в трехмерном пространстве.
  16. Планарные (плоские) графы. Формула Эйлера для планарных графов.
  17. Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
  18. Схемы из функциональных элементов дизъюнкции, конъюнкции и отрицания (СФЭ), их сложность. Реализация булевых функций ими.
  19. N-разрядный сумматор, верхняя оценка сложности реализации n-разрядного сумматора СФЭ.
  20. N-разрядный вычитатель, верхняя оценка сложности реализации n-разрядного вычитателя СФЭ.
  21. Конечный автомат, его функционирование. Автоматная функция. Задание автоматных функций диаграммами Мура и каноническими уравнениями. Функция единичной задержки.


Литература


1. Алексеев В.Б. Лекции по дискретной математике. М.: МГУ, 2002.

2. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.

3. Селезнева С.Н. Основы дискретной математики. М.: МАКС Пресс, 2010.

4. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.