25. Доказать формулу общего решения линейного рекуррентного уравнения первой степени. Привести пример нахождения общего и частного решения линейного рекуррентного уравнения первой степени.
26. Дать определение числового ряда, степенного ряда, области сходимости. Привести примеры сходящихся и расходящихся числовых рядов. Привести примеры степенных рядов и указать области их сходимости.
27. Дать определение производящей функции и привести пример. Сформулировать свойства производящих функций.
28. Сформулировать и доказать теорему о свертке для производящих функций.
29. Привести примеры применения производящей функции для доказательства комбинаторных соотношений.
30. Записать асимптотические оценки (при больших значениях n) для n! и Cnk.
31. Описать метод математической индукции. Продемонстрировать его применение на примере.
32. Дать определение графа и основных его видов: ориентированный и неориентированный, мультиграф, взвешенный граф, граф с петлями, планарный граф.
33. Описать основные способы задания графов: матрица смежности, матрица инцидентности, список смежности. Степени вершин графа. Теоремы о свойствах степеней вершин.
34. Что называется маршрутом в графе? Основные виды маршрутов: определения и примеры. Нахождение кратчайших маршрутов.
35. Дать определение эйлеровых циклов и цепей, условия их существования в графе. Описать алгоритм построения эйлерова цикла.
36. Дать определение гамильтонова цикла и цепи.
37. Описать алгоритмы обхода графов в глубину и в ширину.
38. Описать алгоритм построения кратчайшего пути в графе.
39. Дать определение изоморфных графов, привести пример. Как проверить изоморфность графов?
40. Дать определение хроматического числа графа. В чем заключается «задача о раскраске». Описать алгоритм построения раскраски в k+1 цветов (k – максимальная степень вершины).
41. Дать определение и привести эквивалентные признаки дерева. Как построить каркас в дереве? Как построить минимальное соединение вершин во взвешенном графе?
42. Дать определение бинарного дерева, опивать алгоритмы нумерации бинарных деревьев. Как используются бинарные деревья для моделирования «калькулятора»
43. Дать определения двудольного графа и паросочетаний. Сформулировать признак двудольности. Привести примеры задач, которые моделируются двудольными графами и паросочетаниями.
44. Описать алгоритм нахождения компонент связности в графе.
2.5 Вопросы для подготовки к экзамену (3 семестр)
1. Дайте определение понятия «отношение». Приведите примеры унарных, бинарных и тернарных отношений на различных множествах.
2. Опишите основные свойства бинарных отношений : рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Приведите примеры отношений, обладающих и не обладающих этими свойствами.
3. Какими свойствами обладают отношения на числах: «больше», «больше или равно», равенство, «иметь одинаковый остаток от деления» ( на фиксированное число), «неравенство»?
4. Какими свойствами обладают отношения на множествах: «быть подмножеством», «иметь непустое пересечение», «не пересекаться», неравенства?
5. Дайте определение отношения «частичный нестрогий порядок» и приведите примеры таких отношений на числах.
6. Дайте определение отношения «частичный строгий порядок» и приведите примеры таких отношений на множествах.
7. Определите отношение «частичный нестрогий порядок» на векторах и продемонстрируйте выполнение его свойств.
8. Дайте определение отношения «эквивалентность». Приведите примеры отношения эквивалентности на основе заданного разбиения и проверьте выполнение требуемых свойств
9. Докажите теорему о связи отношения эквивалентности с разбиением множества на непересекающиеся классы. Приведите примеры построения разбиения по заданному отношению эквивалентности и определения отношения эквивалентности на основе заданного разбиения.
10. Дайте определение группы. Какой элемент называется единичным элементом в группе? Какие группы называются коммутативными (абелевыми)? Приведите примеры групп.
11. Дайте определение кольца. Приведите пример кольца, кажите в нем единичные элементы по отношению к каждой операции, проясните выполнение основных свойств.
12. Дайте определение поля. Приведите пример, укажите обратные элементы по отношению к каждой операции, поясните выполнение свойств поля.
13. Приведите пример поля, содержащего конечное число элементов.
14. Какие алгебраические системы называются решетками. Приведите пример решетки на множествах. Проверьте выполнение свойств решетки.
15. Какие алгебраические системы называются решетками? Приведите пример решетки на двоичных векторах. Проверьте выполнение свойств решетки.
16. Запишите определение основных операций алгебры логики. Дать определение функции алгебры логики.
17. Как задать функцию алгебры логики в виде таблицы истинности и формулы? Сколько существует логических функций от nпеременных?
18. Опишите понятие «булева алгебра логических функций». Опишите правила основные свойства операций, представленных в булевой алгебре. Примените эти правила для упрощения формул.
19. Дайте определения СДНФ и СКНФ. Как построить такие представления для произвольной логической функции, заданной таблицей истинности или формулой?
20. Какие функции называются монотонными, линейными, самодвойственными, сохраняющими ноль и сохраняющими единицу? Приведите примеры таких функций. Докажите замкнутость классов таких функций.
21. Дайте определение функционально полной системы. Приведите примеры. Сформулируйте и докажите признак функциональной полноты.
22. Что называется предикатом? Приведите пример записи выражений на языке логики предикатов. Каковы правила преобразования формул логики предикатов? Как привести формулу логики предикатов к предваренной нормальной форме?
23. Дайте определение формальной теории. Что такое аксиомы и правила вывода?
24. Опишите структур исчисления высказываний (ИВ). Приведите пример формального вывода в ИВ.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.