andrey

Путь к Файлу: /вопросы к экзаменам 2011г / Дискретка экзамен.doc

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   0
Пользователь:   andrey
Добавлен:   07.01.2015
Размер:   63.0 КБ
СКАЧАТЬ

1. С.В. Судоплатов, Е.В. Овчинникова Элементы дискретной математики.

1. В.А. Горбатов Фундаментальные основы дискретной математики.

2. О.Е. Акимов Дискретная математика: логика, группы, графы.

3. О.П. Кузнецов, Г.М. Адельсон-Вельский Дискретная математика для инженера.

4. Ф.А. Новиков Дискретная математика для программистов.

5. Б.Н.Иванов Дискретная математика: алгоритмы и программы.

6. А. Кофман Введение в прикладную комбинаторику.

 

                      Вопросы к экзамену

Раздел 1. Теория множеств

1. Множество. Элемент множества. Подмножество: собственное и несобственное. Разбиение и покрытие множества.  Подмножества в программном коде. Способы задания множеств (перечисление, характеристический предикат, порождающая процедура). Операции над множествами: дополнение, пересечение, объединение, разность, кольцевая сумма – определения, диаграммы Эйлера, характеристические предикаты, программный код.

2. Свойства операций над множествами (идемпотентность, коммутативность, ассоциативность, дистрибутивность, поглощение, инволютивность, законы де Моргана, законы пустого множества и универсума) и их доказательство методами: взаимного включения, построения характеристических предикатов, на диаграммах Эйлера.

3. Мощность конечного множества. Булеан множества. Булеан в программном коде. Мощность булеана конечного множества.

4. Натуральный ряд чисел. Счетные множества. Теорема о несчетности отрезка [0,1] (доказательство).

5. Континуальные множества. Установление континуальности множества всех действительных чисел.

6. Декартово произведение множеств. Декартова степень множества. Мощность прямого произведения конечных множеств. N-местное отношение. Соответствие. Область прибытия соответствия, область отправления соответствия, график соответствия. Способы задания соответствий (графический, матричный). Тождественное, универсальное и пустое соответствия и их матрицы.

7. Операции над соответствиями (объединение, дополнение, пересечение, обращение, композиция) – определения, матричное представление, свойства.

8. Ограничение соответствия. Сужение соответствия. Сечение соответствия. Фактор-множество по соответствию.  Проекция отношения.

9. Свойства соответствий (рефлексивность, антирефлексивность, симметричность, антисимметричность, несимметричность, транзитивность) – определения, методы проверки (по определению и по матрице).

10. Классы соответствий: эквивалентность, порядок (строгий, нестрогий). Классы эквивалентности их свойства.

11. Отношение порядка. Строгий и нестрогий порядок. Полный и частичный порядок. Наибольший и наименьший элементы. Максимальный и минимальный элементы. Нижняя граница, инфимум, верхняя граница, супремум. Диаграмма Хассэ.

12. Реляционные базы данных. Атрибут, тип записи, первая нормальная форма. Операции: селекции, проекции, соединения по атрибуту.

13. Свойство функциональности, образ, прообраз, операции. Типы функций. Обратные функции. Теорема о связи типов функций с наличием обратных функций. Теорема о мощностях областей отправления и прибытия функций разных типов.

14. Функция естественной проекции в реляционных базах данных. Функциональная зависимость между атрибутами. Ключ.

15. Нечеткие множества. Операции над нечеткими множествами (объединение, пересечение, дополненине): максиминные, алгебраические, ограниченные. Диаграммы. Свойства операций разного типа.

16. Носитель нечеткого множества. Высота. Нормальное и субнормальное нечеткие множества. Нормализация. Множество уровня α. Точка перехода. Четкое множество, ближайшее к нечеткому.

17. Обобщение понятия нечеткого множества: A-нечеткие, L-нечеткие, S-нечеткие множества. Гетерогенные нечеткие множества.

18. Нечеткие отношения. Способы задания. Операция композиции (различные типы).

19. Свойства нечетких отношений: рефлексивность, слабая рефлексивность, сильная рефлексивность, антирефлексивность, слабая антирефлексивность, сильная антирефлексивность, симметричность, антисимметричность, асимметричность, сильная линейность, слабая линейность, транзитивность.

20. α-уровень нечеткого отношения. Теорема о связи свойств α-уровеней отношения с его свойствами. α- свойства отношения.

21. Транзитивное замыкание нечеткого отношения. Теорема о транзитивном замыкании. Свойства, сохраняющиеся при транзитивном замыкании.

22. Проекции нечетких отношений. Условные проекции первого и второго типов. Независимость проекций по первому и второму типам.

Раздел 2. Логические исчисления.

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. Теорема1 – о связи тавтологий алгебры высказываний и алгебры предикатов. Теорема 2 – о переносе отрицания через кванторы (доказательство методом конкретизации и на основе определений кванторов).

50. Теорема 3 – перенесение кванторов через конъюнкцию и дизъюнкцию (доказательство методом конкретизации и на основе определений кванторов).

51. Теорема 4 – правила перестановки кванторов (доказательство методом конкретизации и на основе определений кванторов)

52. Теорема 5 – перенесение кванторов через импликацию (доказательство методом конкретизации и на основе определений кванторов).

53. Приведенная форма формулы логики предикатов. Теорема о ее построении (алгоритм).

54. Предваренная нормальная форма формулы логики предикатов. Теорема о ее построении (алгоритм).

55. Сколемовская стандартная форма формулы логики предикатов. Правила ее построения.

56. Унификация множества литералов. Бинарная резольвента. Алгоритм метода резолюций в логике предикатов.

Раздел 3. Комбинаторика.

57. Комбинаторные конфигурации. Модели комбинаторных конфигураций. Правило суммы. Правило произведения. Формула включений и исключений.

58. Наиболее встречающиеся комбинаторные конфигурации и методы их подсчета: размещения с повторениями, размещения без повторений, перестановки без повторений, перестановки внутри мультимножества, сочетания без повторений, сочетания с повторениями.

59. Алгебра перестановок: композиция, единичная и обратная подстановка. Таблица инверсий. Восстановление перестановки по таблице инверсий. Теорема о представлении перестановки в виде суперпозиции транспозиций соседних элементов (доказательство).

60. Упорядоченные разбиения множеств. Подсчет их количества. Числа Стирлинга второго рода и их свойства.

61. Полиномиальная формула. Бином Ньютона (вывод).

62. Свойства биномиальных коэффициентов: Дискретка экзамен, Дискретка экзамен, Дискретка экзамен, Дискретка экзамен, Дискретка экзамен, Дискретка экзамен (с выводом).

63. Производящие функции. z-преобразование. Операции над z-преобразованиями: линейные, сдвиги начала влево и вправо, частичные суммы, дополнительные частичные суммы, изменение масштаба, свертка (с выводом).

64. Применение производящих функций в перечислительной комбинаторике: энумераторы и денумераторы множеств.

65. Рекуррентные соотношения. Решение рекуррентного соотношения. Линейные соотношения. Решение линейных однородных и неоднородных соотношений.

Раздел 4. Теория графов.

66. Граф. Вершина графа, ребро графа, геометрическая реализация графа. Теорема о реализации графа в трехмерном пространстве (доказательство).

67. Смежные вершины, смежные ребра, инцидентность, кратные ребра, мультиграф. Орграф, Путь, цепь, простая цепь, простой цикл, петля, псевдограф. Связный граф, компонента связности, изоморфные графы.

68. Способы задания графов: структура смежности, матрица смежности, матрица инцидентности их особенности для орграфов и мультиграфов.

69. Степень вершины графа, полустепени захода и исхода. Лемма о рукопожатиях. Вектор степеней, регулярный граф. Расстояние между вершинами графа, матрица расстояний. Эксцентриситет вершины, диаметр и радиус графа. Центр графа, периферийные вершины графа.

70. Операции над графами (добавление вершины, удаление вершины, добавление ребра, удаление ребра, подразделение ребра, дополнение графа, объединение графов, пересечение графов, кольцевая сумма, соединение, произведение, композиция графов, часть графа и подграф). Клика в графе.

71. Дерево. Лес. Остов графа. Ветви, хорды. Цикломатическое число графа. Алгоритмы поиска в глубину и в ширину. Матричная формула Кирхгофа.

72. Реберно-взвешенные графы. Матрица весов. Вес маршрута. Алгоритмы поиска остова минимального веса: Краскала, Прима.

73. Планарный граф. Грани. Эйлерова характеристика. Теорема о эйлеровой характеристике (доказательство). Следствия о непланарности графов K5 и K3,3 (доказательство).

74. Теорема Куратовского-Понтрягина. Число планарности. Толщина графа. Алгоритм плоской укладки графа.

75. Эйлеров граф. Критерий эйлеровости (доказательство).

76. Алгоритм Флёри – построения эйлерова цикла. Эйлерова цепь. Полуйлеров граф. Критерий полуэйлеровости. Эйлеровость и полуэйлеровость в орграфах.

77. Гамильтонов граф. Полугамильтонов граф. Достаточные условия гамильтоновости. Задача коммивояжера и алгоритм ее решения.

78. Фундаментальное множество циклов. Матрица фундаментальных циклов. Разрез. Простой разрез. Коцикл. Коцикломатическое число графа. Кодерево. Фундаментальное множество разрезов и алгоритм его построения. Матрица фундаментальных коциклов.

79. k-раскраска вершин графа. Правильная раскраска. Хроматическое число. Алгоритм последовательного раскрашивания. Задача составления оптимального расписания. Теорема о хроматическом числе (доказательство). Гипотеза четырех красок. Теорема о 5-раскрашивании любого планарного графа. Реберная раскраска.

80. Связность в графе: вершинная связность, точка сочленения, блок, реберная связность, мост, k-связность, реберная k-связность. Теорема соотношении вершинной и реберной связности в графе. Алгоритм нахождения блоков графа.

81. Связность в орграфе: сильная, односторонняя, слабая. Сильная компонента связности. Матрицы достижимости, контрдостижимости, сильных компонент. База графа.

82. Исследование маршрутов определенной длины.

83.Числа вершинного и реберного покрытия. Числа вершинной и реберной независимости. Теорема о соотношении этих чисел. Совершенное паросочетание. Кликовое число графа. Паросочетания в двудольном графе.

84. Задача о покрытии единиц в бинарной матрице.

85. Алгоритм нахождения наибольшего паросочетания в двудольном графе.

86. Нахождение кратчайшего маршрута в графе: алгоритм Форда-Беллмана и алгоритм Дейкстры.

87. Транспортная сеть. Потоки в сетях. Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

 

Наверх страницы

Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика