Вопросы к экзамену по дискретной математике для РК-6

ДИСКРЕТНАЯ МАТЕМАТИКАРК-6, 3-й семестр 2011-2012.ВОПРОСЫ К ЭКЗАМЕНУМодуль 1. Графы1. Понятия графа; вершины, ребра, степени вершин. Изоморфизм двух графов. Способы задания графа(матрица смежности, список смежности).2. Путь в графе; связные графы, компонента связности, дерево.3. Взвешенные графы. Диаметр, радиус и центр взвешенного графа. Построение дерева кратчайшихпутей; построение остовного дерева наименьшего веса.4. Сложение циклов по модулю 2; пространство циклов; построение фундаментальной системыциклов.

Эйлеровы и гамильтоновы циклы.5. Раскраска графа; построение хроматического многочлена; способ экономной раскраски графа.6. Ориентированные графы (орграфы). Матрица смежности орграфа. Множество достижимости;конденсация графа.7. Бинарные отношения на множестве: рефлексивные, симметричные и транзитивные.

Отношения.Отношения эквивалентности, разбиение множества на классы эквивалентности.Модуль 2. Формальные языки и автоматы8. Понятия формального языка; операции над языками; регулярные языки и регулярные выражения.9. Понятие источника и порождаемого им языка. Построение источника по регулярному выражению.Построение регулярного выражения по данному источнику.10. Детерминирование источника.11. Автомат, его представление посредством таблицы и ориентированного графа. Отображениеязыков, производимое автоматом.12. Эквивалентность автоматов. Построение минимального автомата, эквивалентному данному.Построение муровского автомата (т.е.

автомата Мура), эквивалентного данному.13. Грамматика и порождаемый ею язык. Построение источника по грамматике и грамматики поисточнику.Модуль 3. Булевы функции и комбинаторика14. Булевы векторы и их нумерация; булев куб.15. Табличный и векторный способы задания булевой функции. Таблицы основных булевых функций.16. Дизъюнктивная и конъюнктивная нормальные формы (ДНФ и КНФ).

Носитель булевой функции.Носитель элементарной конъюнкции и ДНФ.17. Понятие сложности ДНФ и минимальной ДНФ. Импликанты и простые импликанты. Построениевсех простых импликант путем последовательного объединения граней булева куба. Методыпостроения минимальной ДНФ. Совершенная ДНФ.18. Многочлены Жегалкина. Представление булевой функции в виде многочлена Жегалкина.19. Операции переименования и суперпозиции. Понятие полноты функционального класса. КлассыПоста. Теорема Поста о полноте функционального класса.20.

Контактные схемы. Нахождение функции проводимости контактной схемы. Схемы изфункциональных элементов21. Декартово произведение множеств; формула произведения. Написать и вывести формулы длячисла различных выборок, перестановок и сочетаний. Написать и вывести формулу для количества:(а) всех функций вида f : {1; 2; ,,,. m} → {1; 2; ,,,. n} ; (б) всех монотонных функций указанного вида.22. Написать и вывести Формулу для Бинома Ньютона.23. Написать, вывести и пояснить формулу включений – исключений.24. Решение линейных рекуррентных соотношений. Последовательность Фибоначчи.Дополнительные вопросы и задачи (сверх обязательной программы)Студенты могут подготовить по своему желанию.1.

Матрица инцидентности графа.2. Методы обхода вершин графа: поиск в ширину и в глубину.3. Нарисовать все попарно не изоморфные деревья с четырьмя вершинами.4. Дан связный граф с пятью вершинами. Какое наименьшее число рёбер он может иметь?5. Отношения частичного и полного порядка на множестве.6. Найдите булеву функции, образующую полный класс.7. Язык в алфавите {a; b} состоит из все слов, в которых правее любой буквы а стоит выражение b2 .Запишите регулярное выражение для этого языка.8.

Определение функции Эйлера ϕ (n ) . Вывести формулу для неё.9. Построить автомат, который перевел бы слово abba в слово yyyx. Желательно, чтобы числовершин (состояний ) было как можно меньше.10. Найти количество чисел из множества {2; 3; ...; 59; 60} , делящихся хотя бы на одно из чисел:4, 5, 24, 30..