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