Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис




Скачать 61.49 Kb.
НазваниеВопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис
Дата публикации09.09.2014
Размер61.49 Kb.
ТипВопросы к экзамену
shkolnie.ru > Математика > Вопросы к экзамену
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и МОиАИС.


  1. Понятие "множество", "подмножество", примеры множеств, способы задания множеств. Принцип объемности. Операции над множествами. Диаграммы Эйлера-Венна. Примеры.

  2. Способы доказательства равенства двух множеств. Примеры.

  3. Основные тождества алгебры множеств (с доказательством).

  4. Бинарное отношение, обратное отношение, композиция отношений. Способы задания бинарных отношений. Свойства обратных отношений (с доказательством). Примеры.

  5. Специальные бинарные отношения: отношение эквивалентности и отношение порядка.

  6. Разбиение множества. Свойства разбиения. Числа Стирлинга и числа Белла.

  7. Классы эквивалентности: определение, примеры и свойства (класс эквивалентности порождается любым своим элементом).

  8. Теорема о взаимосвязи между отношением эквивалентности и разбиением множества (с доказательством).

  9. Предмет комбинаторики. Основные правила комбинаторики. Основные комбинаторные объекты. Примеры. Система подмножеств некоторого множества. Алгоритм перечисления всех подмножеств. Примеры.

  10. Размещения элементов с повторениями. Число возможных размещений с повторениями. Доказательство утверждения о величине числа возможных размещений с повторениями.

  11. Размещения элементов без повторений. Число возможных размещений без повторений. Доказательство утверждения о величине числа возможных размещений без повторений.

  12. Перестановки. Оценки для n! (с доказательством).

  13. Сочетания элементов с повторениями. Число возможных сочетаний с повторениями. Доказательство утверждения о величине числа возможных сочетаний с повторениями.

  14. Сочетания элементов без повторений. Число возможных сочетаний без повторений. Доказательство утверждения о величине числа возможных сочетаний без повторений.

  15. Разбиение множества. Число возможных разбиений. Доказательство утверждения о величине числа возможных разбиений множества.

  16. Формула включений и исключений (с доказательством).

  17. Понятие графа. Типы графов. Способы задания графов.

  18. Изоморфизм графов. Свойства изоморфизма. Гомеоморфизм графов.

  19. Теоретико-множественные операции над графами.

  20. Понятия маршрута на графе, цепи и цикла. Алгоритм Тэрри поиска маршрута в связном графе.

  21. Минимальные пути. Алгоритм фронта волны определения минимальных путей на графе.

  22. Планарные графы. Критерий планарности Понтрягина. Критерий планарности Уитни.

  23. Деревья: определение и примеры. Свойства деревьев

  24. Понятие связности. Матрица сильной связности. Матрица достижимости.

  25. Алгоритм выделения компонент сильной связности.

  26. Предмет математической логики. Понятие и примеры парадоксов. Парадокс Рассела.

  27. Высказывания. Логические операции (определения и примеры).

  28. Двоичные наборы. Соседние и противоположные наборы. Отношение предшествования. Сравнимые наборы.

  29. Способы задания булевых функций. Примеры.

  30. Равносильность формул. Основные равносильности алгебры логики (с доказательством).

  31. Способы доказательства равносильности двух формул. Доказательство равносильности законов де Моргана.

  32. Двойственные и самодвойственные функции. Принцип двойственности. Алгоритм выявления самодвойственности. Доказательство замкнутости класса самодвойственных функций.

  33. Дизъюнктивная нормальная форма. Алгоритм построения ДНФ.

  34. Теорема о приведении к ДНФ (с доказательством).

  35. Конъюнктивная нормальная форма. Алгоритм построения КНФ.

  36. Теорема о приведении к КНФ (с доказательством).

  37. СДНФ: определение и примеры. Способы построения СДНФ.

  38. Теорема о единственности СДНФ (с доказательством).

  39. СКНФ: определение и примеры. Способы построения СДНФ.

  40. Теорема о единственности СКНФ (с доказательством).

  41. Полные системы функций. Определение и примеры. Суперпозиции функций.

  42. Способы выявления полноты системы.

  43. Теорема о выявлении полноты системы путем сведения ее к заведомо полной (с доказательством).

  44. Класс линейных функций. Доказательство замкнутости класса линейных функций.

  45. Полином Жегалкина. Способы построения полинома Жегалкина.

  46. Монотонные функции: определение и примеры. Способы выявления монотонности. Доказательство замкнутости класса М.

  47. Лемма о несамодвойственной функции.

  48. Лемма о немонотонной функции.

  49. Лемма о нелинейной функции.

  50. Теорема о функциональной полноте (с доказательством).

  51. Таблица Поста. Алгоритм выделения базиса в полной системе.

  52. Результаты Поста для булевых функций.

  53. Определение и способы задания функций k - значной логики. Элементарные функции k- значной логики и их свойства.

  54. Первая и вторая форма функций k- значной логики. Примеры построения 1 и 2 форм.

  55. Результаты Поста для k- значной логики.

  56. Понятие "детерминированные функции", "ограниченно-детерминированные функции". Определение. Примеры. Способы задания ограниченно-детерминированных функций.

  57. Диаграмма Мура: определение, правила построения. Примеры.

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

  59. Операции над детерминированными функциями.

  60. Определение машины Тьюринга. Составные части машины Тьюринга. Принципы работы машины Тьюринга.

  61. Понятие команды, программы машины Тьюринга. Порядок работы машины Тьюринга.

  62. Операции над машинами Тьюринга.

  63. Машинные коды. Виды машинных кодов. Примеры. Вычислимые функции.

  64. Операции суперпозиции и минимизации: определение и примеры

  65. Схема примитивной рекурсии.

  66. Неразрешимые алгоритмические проблемы.

  67. Формальная аксиоматическая теория.

  68. Аксиоматическая теория исчисления высказываний.

  69. Полнота и непротиворечивость исчисления высказываний.

  70. Теорема о дедукции (с доказательством).

  71. Следствия из - теоремы о дедукции (с доказательством).

  72. Доказательство утверждения ()

  73. Доказательство утверждения ()

  74. Аксиоматическая теория исчисления предикатов.

  75. Операции над предикатами.

  76. Понятие "интерпретации". Примеры. Равносильность формул исчисления предикатов.

  77. Основные равносильности логики предикатов.

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

  79. Истинность и общезначимость формул исчисления предикатов

  80. Теорема о приведении формулы к приведенной форме (с доказательством).

  81. Теорема о приведении формулы к нормальной приведенной форме ( с доказательством).


Типовые задачи.


  1. Доказать двумя способами (графически и с помощью метода взаимных включений) равенство двух множеств.

  2. Найти все элементы множества R, если R=Aх(В\С) при конкретных значениях А, В, С.

  3. Построить Композицию отношений .

  4. Построить матрицу смежности для неориентированного (ориентированного) графа, заданного графически.

  5. Построить неориентированный (ориентированной) граф с заданной матрицей смежности.

  6. Построить неориентированный (ориентированной) граф с заданной матрицей инцидентности.

  7. Построить матрицу инцидентности для неориентированного (ориентированного) графа, заданного графически.

  8. Построить матрицу сильной связности для ориентированного графа.

  9. Найти количество компонент сильной связности в ориентированном графе, заданном графически.

  10. Найти минимальный путь из вершины v в вершину w в ориентированном графе, заданном графически.

  11. Задачи по теме комбинаторика.

  12. Доказать равенство в k-значной логике.

  13. Построить ДНФ для функции.

  14. Построить КНФ для функции f(x,y,z), заданной с помощью формулы.

  15. Построить СДНФ для функции f(x,y,z), заданной с помощью вектора значений.

  16. Построить СКНФ для функции f(x,y,z), заданной с помощью формулы.

  17. Определить, является ли функция f самодвойственной.

  18. Определить, является ли функция f монотонной.

  19. Построить полином Жегалкина для функции f, заданной вектором значений.

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

  21. Выяснить полноту системы функций с помощью сведения ее к заведомо полной.

  22. Для функции построить первую и вторую формы.

  23. Определить, является ли функция f(х(1)х(2).....)=у(1)у(2)..... детерминированной.

  24. Определить вес функции f(х(1)х(2).....)=у(1)у(2).....

  25. Построить диаграмму Мура для функции f(х(1)х(2).....)=у(1)у(2).....

  26. Построить канонические уравнения f(x(1)x(2).....)=y(1)y(2).....

  27. Выяснить, применима ли машина Тьюринга, задаваемая программой П, к слову Р.

  28. По программе П машины Тьюринга Т написать аналитическое выражение для функции f(х), вычисляемой машиной Т.

  29. Используя в качестве исходных функций только константы и простейшие, построить примитивно-рекурсивную схему, описывающую функцию.

  30. Доказать, что формула исчисления высказываний является теоремой.

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


Рекомендуемая литература.

  1. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика - М.: Наука. Физматлит, 2000.

  2. Новиков Ф.А. Дискретная математика для программистов.- СПб: Питер, 2001.

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

  4. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения.- М.: Вузовская книга, 2001.

Похожие:

Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconМетодические указания к лабораторным работам для студентов III курса...
Методы оптимизации со студентами (направление 010500 – “Прикладная математика и информатика”) в терминальном классе. Они охватывают...
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconПримерный перечень вопросов к переаттестации (экзамену) по дисциплине...
Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля. Полиномиальная формула
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconРоссийской федерации
Рекомендовано методической комиссией факультета вмк для студентов ннгу, обучающихся по направлениям подготовки 010500 «Прикладная...
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconБаврин И. И., Высшая математика: Учеб пособие для студентов естественнонаучных...
В пособии рассматривается раздел математического анализа «Дифференциальные уравнения». Предназначается для студентов III курса очного...
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconРабочая программа дисциплины дискретная математика Направление
Программа составлена в соответствии с требованиями фгос впо по направлению подготовки 230700 Прикладная информатика в экономике
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconСписок рекомендуемой литературы по дисциплине «Дискретная математика»...
Ершов Ю. Л., Палютин Е. А. Математическая логика: Учебное пособие. 3-е изд., стер. – Спб.: Лань, 2004. – 336 с
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconКонтрольная работа по курсу «дискретная математика» Задание: выполнить указанные задания
Оформление: в соответствии с методическими рекомендациями по оформлению контрольной работы для студентов факультета дистанционных...
Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconВопросы к экзамену по дисциплине «Математика в экономике» для студентов фэу, 2-й курс

Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconВопросы к экзамену по дисциплине «Математика в экономике» для студентов фэу, 2-й курс

Вопросы к экзамену по курсу «Дискретная математика» для 1 курса специальностей Прикладная математика и моиаис iconВопросы к экзамену по дисциплине «Математика в экономике» для студентов...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
shkolnie.ru
Главная страница