Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов»

Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов»

лектор: Михеев А. В., 4 семестр, 2016 г.

1. Предикаты: определение. Поле предиката. Множество истинности предиката.

2. Квантор существования: определение, примеры.

3. Квантор всеобщности: определение, примеры.

4. Построение таблицы истинности предикатов, содержащих кванторы существования и всеобщности. Свободные и связанные переменные.

5. Свойства кванторов существования и всеобщности.

6. Формулы логики предикатов.

7. Алфавитное кодирование. Схема кодирования.

8. Проблема взаимной однозначности кодирования.

9. Свойство префикса.

10. Ориентированные графы и пути в них. Циклы и петли.

11. Нетривиальные разложения элементарных кодов и их построение.

12. Критерий Маркова.

13. Кодирование Хемминга. Информационные и контрольные биты.

14. Заполнение битов при кодировании Хемминга.

15. Обнаружение ошибки в коде Хемминга и восстановление исходного кода.

16. Конечные автоматы: определение, описание работы. Функции переходов и выходов.

17. Задание автомата при помощи таблицы.

18. Задание автомата при помощи диаграммы (графа).

19. Приведение таблицы автомата к двоичной форме.

20. Система канонических уравнений автомата.

21. Три типа «простейших функций».

22. Оператор суперпозиции: определение, примеры.

23. Оператор примитивной рекурсии: определение, примеры.

24. Метод математической индукции для доказательства утверждения.

25. Примитивно-рекурсивные функции: определение.

26. Частично-рекурсивные функции: определение.

27. Нормальный алгоритм Маркова.

28. Машина Тьюринга.

29. Машина Поста.