Ответы: Теория к экзамену

Теория к экзамену

• 1. Понятие множества. Способы задания множеств. Операции над множествами. Диаграммы Венна.
• 2. Равенство множеств. Основные тождества алгебры множеств.
• 3. Прямое произведение множеств. Отношения, бинарные отношения. Операции над отношениями.
• 4. Понятие функции. Инъективные, биективные, суръективные функции. Композиция и обращение функций.
• 5. Бинарные отношения на множестве Х. Рефлексивность, симметричность, транзитивность бинарных отношений на множестве Х.
• 6. Отношение эквивалентности. Класс эквивалентности.
• 7. Разбиение множества. Теорема о связи между отношением эквивалентности на множестве и разбиением множества.
• 8. Отношение порядка. Частичный и линейный порядок. Упорядоченные множества.
• 9. Мощность множества. Счётные множества. Несчётные множества. Теорема Кантора.
• 10. Понятие нечёткого множества. Виды и некоторые свойства нечётких множеств. Способы задания нечётких множеств.
• 11. Функции принадлежности нечётких множеств и методы их построения.
• 12. Равенство нечётких множеств. Нечёткое подмножество.
• 13. Операции с нечёткими множествами. Некоторые дополнительные операции над нечёткими множествами.
• 15. Определение нечёткого отношения. Виды нечётких отношений. Способы задания нечётких отношений.
• 16. Равенство нечётких отношений. Нечёткое доминирование. Операции с нечёткими отношениям.
• 17. Свойства бинарных нечётких отношений заданных на базисном множестве Х.
• 18. Высказывания. Логические операции. Язык логики высказываний. Формулы логики высказывания.
• 20. Формулы логики высказываний. Равносильность формул логики высказываний. Основные равносильности.
• 21. Двойственность. Закон двойственности. Пример.
• 22. Тождественно-истинные и тождественно-ложные формулы. Выполнимость и опровержимость формул. Пример. Правильные рассуждения.
• 23. Отношение логического следования. Правильные рассуждения. Примеры.
• 24. Нормальные формы формул. Приведение к ДНФ и КНФ.
• 25. Нормальные формы формул. Приведение к СДНФ и СКНФ.
• 26.Булевы функции. Теорема о представлении булевой функции формулой логики высказываний.
• 27. Булевы функции. Булевы функции двух переменных.
• 28. Представление булевых функций формулой логики высказываний в СДНФ и в СКНФ. Примеры.
• 29. Полные системы булевых функций. Теорема о сведении полноты одной системы булевых функцийк другой. Примеры полных систем.
• 30. Полнота системы {+, ∙ , 1}. Многочлены Жегалкины. Приведение любой булевой функции к многочлену жегалкина.
• 31. Функционально-замкнутые классы. Классы T0,T1,S,L,M. Теорема Поста(доказательство по необходимому признаку). док-ва нет
• 32. Описание переключательных схем с помощью формул логики высказываний. Анализ, упрощение и синтез переключательных схем.
• 33. Понятие о проблеме минимизации булевых функций в классе ДНФ.
• 34. Предикаты. Кванторы. Язык логики предикатов. Формулы логики предикатов. Равносильность и общезначимость формул логики предикатов. Основные равносильности.
• 35. Понятие интерпретации. Равносильность и общезначимость формул логики предикатов. Приведенная нормальная формула логики предикатов. Проблема разрешимости. Формулировка теоремы Черча.
• 36. Ориентированные и неориентированные графы. Основные понятия.
• 37. Матричное задание графа. Матрицы сложности и инциденций. Цикломатическая матрица.
• 38. Пути в графе. Цепи. Связные графы и компоненты связности.
• 39. Специальные пути в графе. Понятие о плоских графах.
• 40. Поиск путей в графе. Алгоритм Терри нахождения пути в графе. Алгоритм поиска пути минимальной длины(«фронта волны)
• 41. Алгоритм Форда и Форда-Беллмана нахождение минимального пути в нагруженном графе.
• Алгоритм Форда
• 42. Деревья. Свойства деревьев. Цикломатическое число. Остовные деревья графа. Алгоритм нахождения остовного дерева.
• 43. Вектор-циклы. Пространство вектор циклов. Независимые циклы. Цикломатическое число. Алгоритм нахождения базис вектор-циклов.
• 44. Цикломатическая (контурная) матрица и матрица инциденций. Законы Киргофа. Уравнение контурных токов. Примеры.
• 45. Транспортные сети. Поток в сети. Полный и максимальный поток. Алгоритмы нахождения полного и максимального потока.