Дискретная математика (1й курс) — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Часть А)
Строка 10: Строка 10:
 
'''Ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определение и формулировки — без конспектов.'''
 
'''Ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определение и формулировки — без конспектов.'''
 
<ol>
 
<ol>
−
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
+
<li> Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
−
<li> Лемма о нелинейной функции.
+
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
−
<li> Алгоритм построения вектора коэффициентов полинома Жегалкина по вектору значений булевой функции.
+
<li> Двойственность. Класс самодвойственных функций, его замкнутость.
−
<li> Теорема Поста о полноте системы функций алгебры логики.
+
<li> Лемма о нелинейной функции.
−
<li> Теорема о предполных классах.
+
<li> Теорема Поста о полноте системы функций алгебры логики.
−
<li> Деревья. Свойства деревьев.
+
<li> Теорема о предполных классах.
−
<li> Теорема о раскраске планарных графов в 5 цветов.
+
<li> Теоремы о представлении k-значных функций 2-й формой и полиномами.  
−
<li> Алфавитное кодирование. Теорема Маркова о взаимной однозначности (разделимости) алфавитного кодирования.
+
<li> Деревья. Свойства деревьев.
−
<li> Неравенство Макмиллана.
+
<li> Алгоритм построения кратчайшего остовного дерева (с обоснованием).
−
<li> Существование префиксного кода с заданными длинами кодовых слов.
+
<li> Теорема о раскраске планарных графов в 5 цветов.
−
<li> Теорема редукции.
+
<li> Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием). Теорема Маркова.
−
<li> Коды с исправлением r ошибок. Оценка функции M<sub>r</sub>(n).
+
<li> Неравенство Макмиллана.
−
<li> Коды Хэмминга. Оценка функции M<sub>1</sub>(n).
+
<li> Существование префиксного кода с заданными длинами кодовых слов.
−
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
+
<li> Теорема редукции.
−
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
+
<li> Коды с исправлением r ошибок. Оценка функции Mr(n).
−
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
+
<li> Коды Хэмминга. Оценка функции M1(n).
−
<li> Теорема Мура.  
+
<li> Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
−
</ol>
+
<li> Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
 +
<li> Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.  
 +
<li> Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
 +
 
 +
 
 +
 
 +
<li> Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
 +
<li> Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
 +
<li> Полные системы. Примеры полных систем (с доказательством полноты).
 +
<li> Теорема Жегалкина о представимости функции алгебры логики полиномом.
 +
<li> Понятие замкнутого класса. Замкнутость классов 
 +
<li> Класс монотонных функций, его замкнутость.
 +
<li> Лемма о несамодвойственной функции.
 +
<li> Лемма о немонотонной функции.
 +
<li> Теорема о максимальном числе функций в базисе в алгебре логики.
 +
<li> k-значные функции. Теорема о существовании конечной полной системы в Pk.
 +
<li> Основные понятия теории графов. Изоморфизм графов. Связность.
 +
<li> Корневые деревья. Верхняя оценка их числа.
 +
<li> Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
 +
<li> Планарные (плоские) графы. Формула Эйлера.
 +
<li> Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
 +
<li> Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
 +
<li> Оптимальные коды, их свойства.
 +
<li> Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
 +
<li> Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
 +
<li> Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
 +
<li> Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
 +
<li> Несуществование эксперимента, определяющего начальное состояние автомата.
  
 
=== Часть В ===  
 
=== Часть В ===  

Версия 22:08, 19 мая 2014

Лекторы

Вопросы к экзамену по курсу «Дискретная математика».

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

Часть А

Ответ без подготовки, по любым материалам (конспекты, книжки, распечатки лекций и т.д.). Проверяется, насколько осознаны все доказательства (основной вопрос – «почему?»). Определение и формулировки — без конспектов.

  1. Сокращенная дизъюнктивная нормальная форма. Метод ее построения по конъюнктивной нормальной форме (метод Нельсона).
  2. Алгоритм построения вектора коэффициентов полинома Жегалкина (с обоснованием).
  3. Двойственность. Класс самодвойственных функций, его замкнутость.
  4. Лемма о нелинейной функции.
  5. Теорема Поста о полноте системы функций алгебры логики.
  6. Теорема о предполных классах.
  7. Теоремы о представлении k-значных функций 2-й формой и полиномами.
  8. Деревья. Свойства деревьев.
  9. Алгоритм построения кратчайшего остовного дерева (с обоснованием).
  10. Теорема о раскраске планарных графов в 5 цветов.
  11. Алгоритм распознавания взаимной однозначности алфавитного кодирования (с обоснованием). Теорема Маркова.
  12. Неравенство Макмиллана.
  13. Существование префиксного кода с заданными длинами кодовых слов.
  14. Теорема редукции.
  15. Коды с исправлением r ошибок. Оценка функции Mr(n).
  16. Коды Хэмминга. Оценка функции M1(n).
  17. Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.
  18. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
  19. Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
  20. Теорема Мура. Пример автомата, на котором достигается оценка теоремы Мура.
  21. Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
  22. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
  23. Полные системы. Примеры полных систем (с доказательством полноты).
  24. Теорема Жегалкина о представимости функции алгебры логики полиномом.
  25. Понятие замкнутого класса. Замкнутость классов
  26. Класс монотонных функций, его замкнутость.
  27. Лемма о несамодвойственной функции.
  28. Лемма о немонотонной функции.
  29. Теорема о максимальном числе функций в базисе в алгебре логики.
  30. k-значные функции. Теорема о существовании конечной полной системы в Pk.
  31. Основные понятия теории графов. Изоморфизм графов. Связность.
  32. Корневые деревья. Верхняя оценка их числа.
  33. Геометрическая реализация графов. Теорема о реализации графов в трехмерном пространстве.
  34. Планарные (плоские) графы. Формула Эйлера.
  35. Доказательство непланарности графов K5 и K3,3. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
  36. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
  37. Оптимальные коды, их свойства.
  38. Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
  39. Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
  40. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
  41. Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
  42. Несуществование эксперимента, определяющего начальное состояние автомата.

    Часть В

    Ответ без конспектов и почти без подготовки (3-5 минут), с доказательствами (можно излагать устно).

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

    По результатам контрольных работ по каждой из четырех тем (алгебра логики, графы, коды, автоматы) у каждого студента должна стоять одна из трех оценок — 0, 1/2 или 1. Оценка 0 означает, что на экзамене студент должен решить дополнительную задачу по данной теме, оценка 1/2, — что студент решает задачу по данной теме только в случае, если она выпадает в билете. Оценка 1 означает, что на экзамене студент не должен решать по данной теме как дополнительные задачи, так и задачу из билета. Дополнительные задачи решаются до выбора билета. Студенты, не решившие достаточное количество дополнительных задач, удаляются с экзамена с оценкой «неудовлетворительно», количество решенных задач может ограничить сверху оценку, получаемую на экзамене.

    Задачи решаются без конспектов.

    После ответа на билет возможна прогонка по всему материалу (определения, формулировки, идеи доказательств) и добавочные задачи на любые темы (не путать с дополнительными!).
Источник — «https://mk.cs.msu.ru/index.php?title=Дискретная_математика_(1й_курс)&oldid=1100»