Экзаменационные вопросы по курсу дискретной математики



Скачать 20.67 Kb.
Дата08.11.2012
Размер20.67 Kb.
ТипЭкзаменационные вопросы
Экзаменационные вопросы по курсу дискретной математики


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

  2. Бесконечные множества.

  3. Понятие булевой функции. Элементарные функции.

  4. Существенные и фиктивные переменные, равные функции, эквивалентные формулы.

  5. Тождества булевой алгебры. Получение эквивалентных формул.

  6. Двойственные функции. Принцип двойственности.

  7. Разложение функции по подмножеству переменных (с доказательством теоремы).

  8. Частные случаи разложения (по одной переменной, по всем переменным, СДНФ, СКНФ).

  9. Замыкание множества. Свойства замыкания. Все определения полной системы. Теорема о полноте системы булевых функций.

  10. Первый замкнутый класс Т0 (с доказательством замкнутости), число всевозможных функций в нем. Второй замкнутый класс Т1 (с доказательством замкнутости), число всевозможных функций в нем.

  11. Класс самодвойственных функций S (с доказательством замкнутости), число всевозможных функций в нем.

  12. Класс монотонных функций.

  13. Полином Жегалкина (определение, теорема).

  14. Класс линейных функций, число всевозможных функций в нем.

  15. Теорема Поста (необходимое и достаточное условие полноты системы булевых функций). Теорема о выделении подсистемы.

  16. Геометрическое представление булевых функций. Понятие интервала.

  17. Покрытие. Кратчайшее покрытие. Минимальное покрытие. Связь между покрытием и ДНФ заданной функции.

  18. Понятие импликанты. Теорема Квайна. Троичные вектора. Алгоритм Квайна.

  19. Таблица Квайна и ее покрытия. Алгоритм поиска всех безызбыточных покрытий (алгоритм Петрика). Определение минимальной и кратчайшей ДНФ.

  20. Представление булевых функций с помощью карты Вейча. Минимизация функций по карте Вейча.

  21. Частично определенные булевы функции. СДНФ для частично определенных булевых функций. Минимизация частично определенных функций.

  22. Булевы функции и переключательные схемы.

  23. Бинарные отношения. Способы задания бинарных отношений. Композиция бинарных отношений.

  24. Свойства бинарных отношений. Отношения эквивалентности.

  25. Понятие конечного автомата. Способы задания конечных автоматов.

  26. Минимизация конечных автоматов.

  27. Комбинационные схемы. Логические элементы. Синтез комбинационных схем.

  28. Полный и неполный дешифратор, шифратор (с примером). Демультиплексор, мультиплексор (с примером).

  29. Правило произведения. Правило суммы.

  30. Выборки без повторений.

  31. Выборки с повторениями.

  32. Базовые понятия теории графов. Лемма о числе ребер в полном графе.

  33. Способы задания графов.


  34. Изоморфные графы. Двудольные графы. Маршруты, цепи, циклы.

  35. Эйлеровы графы. Теорема о существовании Эйлерова цикла в графе. Алгоритм построения эйлерова цикла. Гамильтоновы графы.

  36. Остов графа. Алгоритм нахождения минимального остова графа.

Похожие:

Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы по курсу "Прикладные вопросы математического анализа"
Экзаменационные вопросы по курсу "Прикладные вопросы математического анализа" (веч спец отд ф-та вмиК, 2005 2006 уч год)
Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы по курсу «Философия»
Экзаменационные вопросы по курсу «Философия» (С. Л. Катречко; Мехмат – 2009/10; II поток)
Экзаменационные вопросы по курсу дискретной математики iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
A. Вопросы, при ответе на которые, можно пользоваться конспектами (некоторое время, при этом ответ не состоит в чтении конспекта)....
Экзаменационные вопросы по курсу дискретной математики iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
Функции k-значной логики. Формулы, i-я и ii-я формы. Полные системы. Полнота системы Поста. Функция Вебба
Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы по курсу "Высшая математика"
Экзаменационные вопросы по курсу "Высшая математика" для потока Ф4 (лектор А. С. Леонов)
Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы и билеты по курсу всемирной истории 2011/2012 уч г. Экзаменационные вопросы и билеты
Период существования первых государств в древнем Китае – Яо, Шан-Инь и Чжоу (24-8 вв до н э.)
Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы по курсу «Современная философия и методология науки»
Экзаменационные вопросы по курсу «Современная философия и методология науки» для студентов магистратуры вмк 1г/о 2006-07 уч г. Лектор...
Экзаменационные вопросы по курсу дискретной математики iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Экзаменационные вопросы по курсу дискретной математики iconЭкзаменационные вопросы по лекционному курсу "История первобытного общества"
...
Экзаменационные вопросы по курсу дискретной математики iconВопросы к экзамену по курсу «Дополнительные главы дискретной математики»
В билете два теоретических вопроса: первый из части А, второй из части В. Задач в билете нет. Задачи могут быть предложены экзаменатором...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org