Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Вопроспо курсу Дм и МЛ (Прикладная математика)
Высказывания и предикаты
1.Высказывания,операции над ними и их основные союзы .
2.Формулы логики высказываний,тавтологии.
3.Равносильные формулы.Логическое следствие.Теорема о логическом следствии.
4.Логика предикатов.Операции над предикатами. Формулы логики предикатов.
5.Теорема о равносильных предикатах.Интерпретации.
6.Общезначимость и выполнимость формул.Приведенная и нормальная формы.
Исчисление высказываний
7.Исчисление высказываний.Формальные аксиоматические теории.Формулы и аксиомы исчисления высказываний.Примеры выводимых формул.
8.Аксиомы и правило вывода ИВ. Вывод и выводимая формула. Основные правила и свойства.
9. Вывод из гипотез. Теорема Дедукции и следствия из нее.
10. Полнота и непротиворечивость ИВ.
Комбинаторный анализ
11.Множества и операции над ними.
12.Конечные и бесконечные множества и их мощности .Счетные множества
13.Покрытия и разбиения множеств.Правило суммы и принцип Дирихле.
14. Декартово произведение множеств ,правило произведения.
15. Бинарные отношения и их свойства.Отношение эквивалентности и его связь с разбиением множеств.
16.Размещения и размещения с повторениями.N-перестановки.
17.Сочетания с повторениями и без.Бином Ньютона. Некоторые применения формулы бином Ньютона. Биномиальная теорема. Свойства биномиальных коэффициентов.
18.Полиномиальные коэффициенты. Полиномиальная теорема. Разбиения множеств и чисел.
19.Квазиразбиения, полиномиальная теорема. Метод включения и исключения. Применение метода включения и исключения: беспорядки, формула Эйлера, число сюръективных отображений.
20.Производящие функции. Экспоненциальные ПФ.
21.Рекуррентные соотношения и их решения
Функциональные системы с операциями
22.Понятие булевой функции.Элементарные булевы функции.
Существенные и фиктивные переменные. Способы задания функций.
23.Формулы.Основные равносильности.Операцисуперпозиции.
24. Двойственные булевы функции. Принцип двойственности.
25.Дизъюнктивное разложение булевых
функций,СДНФ.СКНФ Алгоритм преобразования формулы в СДНФ (СКНФ).
26. Полиномиальные нормальные формы булевых функций. Полином Жегалкина. Единственность полинома Жегалкина. Методы построения полинома Жегалкина.
27.Полнота систем булевых функций. Лемма одвух системах.
28.Замкнутость и замкнутый класс .Важнейшие замкнутые классы.
29. Классы функций –линейных,монотонных, самодвойственных,сохраняющих константы и их мощность.
30.Критерий функциональной полноты. Теорема о минимальном базисе.
31.Проблема минимизации ДНФ.Тривиальный алгоритм минимизации.СкДНФ, алгоритмы ее построения.
32Сокращенная ДНФ.Тупиковая ДНФ.Алгоритм построения всех тупиковых ДНФ.
33.Геометрическая интерпретация проблемы минимизации ДНФ.
34 Метод минимизации Квайна. Метод минимизации Блейка– Порецкого
35.Понятие о функциях к-значной логики.
36.Реализация функций к-значной логики формулами. Основные эквивалентности. Аналоги СДНФ и СКНФ.
37.Примеры полных систем. Полнота систем ФкЗЛ.
Элементы теории графов.
38. Графы.Способы задания графов.Изоморфизм и гомеоморфизм графов.Плоские и планарные графы.Теорема Понтрягина-Куратовского , теорема Эйлера.
39. Задача раскраски графа. Проблема четырех красок. Хроматическое число и хроматический многочлен.
40. Эйлеровы и Гамильтоновы графы.Теорема об эйлеровом графе.
41. Двудольные графы.Теорема Кенига-критерий двудольности графа.
42. Связность,компоненты связности графа. Покрытие множеств и неорграфы. Оценка числа графов.
43. Сети.Изоморфизм сетей.Операции над ними.
44. Деревья. Кодирование деревьев. Лемма о числе неизоморфных корневых деревьев.
45.Код Прюфера. Теорема Кэли о числе помеченных деревьев.
Алгортимы, Машины Тьюринга. Классы вычислимых и рекурсивных функций.
46. Понятие «алгоритм» и необходимость его уточнения. Понятие машины Тьюринга(одноленточная детерминированная).
47. Классы числовых функций.Понятие вычислимой функции.Тезис Тьюринга.
48. Проблема самоприменимости машин Тьюринга. Простейшие числовые функции и их вычислимость.
49. Операции суперпозиции, примитивной рекурсии , минимизации.
50. Классы рекурсивных функций,соотношение между ними и классом вычислимых функций.
51. К-ленточные ДМТ и НМТ.
52.Понятие сложности алгоритма и сложности вычислений.
Классы Р и NP.
Грамматики и автоматы.
53. Основные понятия.А-грамматики и конечные автоматы. Некоторые свойства грамматик.
54. Иерархия языков. Грамматический разбор.
55. КС-языки и синтез языков программирования.
Кодирование
56. Основные понятия. Примеры кодов.Алфавитное кодирование. Разделимый код.