Студент должен быть готов по требованию преподавателя продемонстрировать и прокомментировать работу программного продукта и модели

Вопросы к зачёту ДМ – 2014

1. Основные понятия теории множеств. Антиномия Рассела.

2. Операции над множествами.

3. Соответствия, отображения и функции.

4. Отношения и их свойства. Применение отношений в базах данных.

5. Цифровое задание множеств. Конституенты I, Æ.

6. Операции на множествах, понятие алгебры. Основные типы алгебр.

7. Алгебра Кантора.

8. Размещения.

9. Перестановки.

10. Сочетания.

11. Треугольник Паскаля.

12. Бином Ньютона.

13. Латинские прямоугольники и квадраты.

14. Понятие о комбинаторных блок-схемах. Плоскость Фано.

15. Основные определения теории графов. Задание графов.

16. Свойства графов. Изоморфизм графов.

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. Сложность алгоритмов. Что такое P, NP, NP-complete?

51. Нечёткая логика.

Задачи к зачёту.

1. Выполнение операций над множествами

2. Задание множества десятичным кодом на универсуме.

3. Решение комбинаторных задач и уравнений.

4. Задание графов и определение их свойств.

5. Задача о Ханойской башне.

6. Задача определения кратчайшего пути в графе с ребрами произвольной длины.

7. Минимизация по кубу соседних чисел.

8. Минимизация по карте Карно

9. Синтез комбинационного автомата

10. Синтез последовательностного автомата

11. Кодирование по Хэммингу.

12. Кодирование с использованием математического аппарата умножения и деления полиномов.

13. Доказательство правильности силлогизмов с помощью диаграмм Эйлера.

14. Доказать или опровергнуть общезначимость формулы, используя законы алгебры логики и формулы равносильных преобразований, а также путем построения дерева доказательства.

15. Проверить аргумент методом резолюций.

16. Равносильные преобразования переключательных функций и формул логики высказываний.

17. Формализовать умозаключение по заданному модусу в логике предикатов. Доказать или опровергнуть умозаключение по заданному модусу методом резолюций.

18. Получить машину Тьюринга для вычисления переключательной функции.

19. Получить машину Поста для вычисления переключательной функции.

20. Написать программу на языке ПРОЛОГ для определения отношения родства.