Вопросы по курсу (1075666)
Текст из файла
ВОПРОСЫ по курсу "Дискретная математика" /2009е ИЪ'-8, 2 курс, 4 сем. (Иванов А.О.) 1. Множества, равенство множеств, операции над множествами. 2. Графы, ориентированные графы, изоморфизмы графов, подграфы. 3. Основные свойства операций над множествами: ассоциативность, коммутативность, дистрибу- тивность, идемпотентность, законы поглощения и законы де Моргана. 4.
Графы, пути, пиклы, остовные подграфы. Связность графа, разложение графа на связные компо- ненты. 5. Отображения множеств, характеристическая функция множества. Свойства характеристических функций связь с операциями над множествами. 6. Графы и матрицы: матрица смежности, матрица Кирхгофа, матрица инцидентности, матрица ориентированной инцидентности,их свойства. 7. Понятие отображения множеств. Сюръективные, инъективные и биективные отображения. Операция суперпозиции отображений. Обратное отображение. Теорема существования обратного отображения. 8. Графы и матрицы: связь матрицы Кирхгофа и матрицы ориентированной инцидентности.
9. Бинарные отношения: отношения эквивалентности, теорема о разбиении на классы, фактор- множество, примеры. 10. Функция расстояния на множестве вершин связного графа. Диаметр графа. Теорема о связи ранга графа и его диаметра. 11. Бинарные отношения: отношение порядка. Линейный порядок. Наибольший и наименьший, максимальный и минимальный элементы. Точная верхняя (нижняя) грань множества. Примеры. 12. Диаметр связного графа.
Теорема о связи ранга графа и его диаметра. 13. Эквивалентность множества, равномощность. Счетные множества, их свойства. 14. Методы перечисления вершин и ребер графа. Поиск в ширину и поиск в глубину. 15. Теорема о мощности множества отображений из данного множества в двухэлементное. 16. Матричная теорема Кирхгофа. 17. Сравнение мощностей множества: счетные множества, мощность отрезка.
18. Количество остовных деревьев в полном графе. 19. Алгебраические системы: полугруппы, группы, единственность нейтрального и обратного эле- ментов. Примеры: группа перестановок, группа вычетов. 20. Графы с весами. Задача о поиске остовного дерева наименьшего веса.
Алгоритм Прима 1описа- ние). 21. Алгебраические системы: группы, группа перестановок, теорема Кэпи. 22. Алгоритм Краскала поиска остова наименьшего веса. Теорема о корректности этого алгоритма. 23. Алгебраические системы: группы, подгруппы, теорема Лагранжа. 24. Ориентированный граф. Задача о достижимости. Матрица достижимости и ее связь с матрицей смежности.
25. Алгебраические системы: полукольца, кольца, поля, делители нуля, поля вычетов. 26. Ориентированный граф. Задача о кратчайшем пути. Матрица весов кратчайших путей и ее связь с матрицей смежности. 27. Алгебраические системы: идемпотентные замкнутые полукольца. Решение уравнения х = ах+ 5. 28. Ориентированный граф. Задача о кратчайшем пути. Алгоритм Дейкстры. 29. Алгебраические системы: булевы кольца и булевы алгебры, теорема о соответствии между ними, примеры. 30.
Конечные детерминированные автоматы с выходом, способы задания. Покрытия. Задача о ми- нимальном автомате. 31. Булевы функции, способы задания, существенные и фиктивные переменные, отношение равен- ства. Конечные детерминированные автоматы с выходом. Покрытия и морфизмы. Булевы функции, их суперпозиция, формулы над базисом функций. 34. Конечные детерминированные автоматы: эквивалентные и г-эквивалентные состояния, проце- дура минимизации. Теорема о разложении булевой функции, СДНФ.
Алфавит, слово, язык, мощность множества языков над конечным алфавитом. Двойственная булева функция, принцип двойственности, СКНФ. 37. Операции над языками, регулярные операции, регулярные языки и регулярные выражения. Полиномы Жегалкина. Теорема о представлении булевой функции в виде полинома Жегалкина. Языки, порожденные грамматиками. Эквивалентные грамматики. Иерархия Хомского. 40. 41. Полиномы Жегалкина. Метод неопределенных коэффициентов.
Единственность полинома Же- галкина булевой функции. НК-грамматики. Языки, порожденные НК-грамматиками в иерархии Хомского. Полипом Жегалкина и существенные переменные булевой функции. Задача распознавания в НК-грамматиках. Оценка высоты дерева вывода. Меры сложности ДНФ, задача о минимизации ДНФ, сокращенные ДНФ, алгоритм Блейка. Праволинейные грамматики и автоматы-распознаватели. Задача о минимизации ДНФ, тупиковые ДНФ, карта Карно, функция Патрика. 47.
Регулярные языки и автоматы. Теорема Клини. Контактные схемы, метод каскадов. Геделевы нумерации. Мощность множества языков, порожденных грамматиками. Замкнутые классы; классы функций сохранян)щих константу, класс самодвойственных функций. Иерархия Хомского. Существование нерегулярных контекстно-свободных языков. 52 Замкнутые классы; класс монотонных функций, класс линейных функций. Понятие ранга графа. Независимость ранга от нумерации вершин. Теорема о ДНФ монотонной функции. Критерий монотонности. Пять эквивалентных определений дерева.
Теорема Поста о полноте. Лемма о разрастании для регулярных языков. Пример нерегулярного языка. Построение заданной функции из функций полной системы. 60. Детерминизация автоматов распознавателей. Регулярность языка, являющегося дополнением до регулярного. ЗАЛАь1И по курсу "Дискретная математика" ИЪ'-8, 2 курс, 4 сем. 1Иванов А.О.) 1.
Найти группу автоморфизмов неориентированного графа: 2. Минимизировать автомат с выходом, заданный таблицей (д1 --- входная вершина): 3. Пусть М --- некоторое множество. На множестве ЛХЯ определена операция о по правилу <х, у>о<г, 6> = <х, Х>. Является ли <ЛХ~, о> полугруппой? Существует ли нейтральный элемент? 4. Найти язык, допускаемый автоматом (А = 1а, 6), В = (дпдз,дз1, вход = (до дя1, выход = 1дз1, Х), Где,Х(й, и) = дя,,Х(чм 6) = д2,,Х(дз, 6) = Й,,Х(д2, и) = дз,,Х(дз, 6) = до 5. Какие из указанных множеств квадратных вещественных матриц образуют группу; (а) множество нсвырожденных матриц относительно умножения; (б) множество невырожденных матриц относительно сложения; (в) множество диагональных матриц относительно сложения? б.
Построить автомат, допускающий итерацию языка Х,, где В = (и, 6| аЬЬ~, ЬаЬ', к > 0; 1 > 01. 7. Пусть 1Х некоторое множество. Является ли группой <2м, Ь>? 8. Найти минимальную ДНФ булевой функции четырех переменных: Х = (1100 1101 0010 0011). 9. Найти язык, допускаемый автоматом (А = 1а, 6), В = (до д2,дз1, вход = (до д21, выход = 1дз1, Х), Где У(д1 и) д2 .Г(д2, 6) = д2 У(д2, 6) = дз У(д2 и) дз; У(дз, 6) = д1. 10. Найти минимальную ДНФ булевой функции четырех переменных: Х = (0010 1110 1111 0110). 11.
В поле Уя решить систсгиу уравнений: х+2д = 1 у+2' = 2 2х+з=1 12. Найти минимальную ДНФ булевой функции четырех переменных: Х = 11010 0110 1010 1110). 13. Используя метод двух включений, проверить тождество: А ~ (В Й С) = (А ~ В) й (А 0 С). 14. Для булевой функции Х(х.,у,г) = (х Н (у г)) — ~ ((х~у) з)) найти полипом Жегалкина и минимальные ДНФ. 15. Используя метод характеристических функций, доказать тождество; А П (В Хз С) = (А ~З В) Хз 1А Й С).
Х = 01100110; д = 01010100; й = 10001110. 17. На множестве натуральных чисел задано бинарное отношение р: числа т и и связаны бинарным отношением р, если ш делится нацело на п. 16. Является ли система булевых функций 1Х, д, 6) полной? Если существуют среди функций Х', д, 6 две, образующие полную систему, то найти все такие пары. 18. Исследовать свойства бинарного отношения р и установить, является ли оно отношением порядка или отношением эквивалентности? Как изменятся свойства бинарного отношения, если оно будет задано на множестве целых чисел? 19. Минимизировать автомат с выходом, заданный таблицей (д~ — — входная вершина): 20. Проверить тождество, используя метод характеристических функций: (А Ь В) Л С = А Л (В Л С). С использованием карты Карно минимизировать булеву функцию от четырех переменных: ~ = (1111 1100 10П 0101).
21. Минимизировать автомат с выходом, заданный таблицей (д~ --- входная вершина): 22. Используя метод двух включений, доказать тождество; (А г~ В) х (С г~П) = (А х С) П (В х В). 23. Какое максимальное возможное число элементов имеет полная система булевых функций, из которой ни одну функцию нельзя удалить без потери свойства полноты? 24. На множестве рациональных дробей вида а?'5, а Е Х, 6 Е 1з ~ 101 задано бинарное отношение т = ~(а/5, с/И> ад = с61. Исследовать свойства бинарного отношения т и установить, является ли оно отношением порядка или отношением эквивалентности? 25. Для булевой функции 1"(х,д,з) = ((х 0Э д) ~ (д 9 )) (х — + (д з)) найти полипом Жегалкина и минигиальные ДНФ. 26. Найти группу автоморфизмов неориентированного графа 27.
Найти язык, допускаемый автоматом 1А = 1а.,61, э" = ~увоз,дз1, вход= ~гй,уз~, выход= И:1:Л1,гдс7(дьп) =д Х(Ч 6) =В,7(Ч,в)=В, 1(Ч,6) =дз, 1(Чз.а) =дя, 28. На множестве целых чисел задано бинарное отношение р: числа т и п связаны бинарным отношением р, если гп делится нацело на и,. Исследовать свойства бинарного отношения р и установить, является ли оно отношением порядка или отношением эквивалентности. Как изменятся свойства бинарного отношения, если оно будет задано на множестве натуральных чисел? 29. В группе подстановок Бе решить уравнение; (123) о (245) о Х о (13)з о (164) = (135)э 30.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
