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

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

Текст из файла

ДИСКРЕТНАЯ МАТЕМАТИКАРК-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..

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов вопросов/заданий