Кухаренко Е. В.

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМ. М. КОЗЫБАЕВА

КУХАРЕНКО Е.В.

Материалы по контролю и оценке учебных достижений студентов

Специальность: 5В011100 «Информатика»

г. Петропавловск

2015 г.

Материалы по контролю и оценке учебных достижений студентов рассмотрены и рекомендованы к утверждению на заседании кафедры " Информационные системы"

протокол №10 от 10.04.2015г.

Заведующий кафедрой ___________________________ Е. Шевчук

Экзаменационные вопросы:

1. Основные понятия теории множеств. Множество. Элементы множества. Способы задания множеств. Примеры.

2. Основные понятия теории множеств. Конечное, бесконечное, упорядоченное, универсальное, пустое множество. Примеры.

3. Операции над множествами. Объединение, пересечение множеств. Примеры.

4. Основные понятия теории множеств. Эквивалентные, равномощные, счетные, несчетные множества. Взаимно-однозначное соответствие, биекция. Примеры.

5. Отношения и их свойства. Кортеж, упорядоченная пара. N-арное отношение. Декартово произведение. Примеры.

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. Логика высказываний. Дедуктивный вывод. Правило контрапозиции импликации. Правило отделения (Modus Ponens). Отрицательная форма правила отделения. Гипотетический силлогизм.

42. Логика высказываний. Дедуктивный вывод. Правило отделения (Modus Ponens). Отрицательная форма правила отделения. Гипотетический силлогизм.

43. Логика первого порядка. Предикат. Нульместный, n-местный предикат. Функциональный символ.

44. Логика первого порядка. Кванторы. Квантор всеобщности, существования. Примеры.

45. Правильно построенные формулы логики первого порядка. Интерпретация формулы.

46. Предваренная нормальная форма. Преобразование выражений произвольной формы в ПНФ.

47. Теория графов. Граф. Вершины. Концевые вершины. Петли. Изолированная вершина.

48. Теория графов. Подграф. Простой граф. Неориентированный, ориентированный граф.

49. Теория графов. Способы задания графов. Примеры.

50. Теория графов. Маршрут. Открытый, замкнутый маршрут. Цепь, простая, замкнутая.

51. Теория графов. Свойства путей и циклов.

52. Деревья. Основные понятия.

53. Деревья. Виды деревьев.

54. Деревья. Алгоритм кодирования деревьев.

55. Деревья. Алгоритм декодирования деревьев.

56. Основы комбинаторики. Размещение. Размещения с повторениями. Размещения без повторений.

57. Основы комбинаторики. Перестановки. Сочетания.

58. Основы комбинаторики. Правила комбинаторики.

59. Ряды. Ряд. Сходящийся, расходящийся ряд. Примеры.

60. Ряды. Сумма ряда. Сходящиеся и расходящиеся ряды. Примеры.

61. Ряды. Простейшие свойства рядов. Ряд сумм. Умножение ряда на число. (Теоремы 1 и 2)

62. Ряды. Простейшие свойства рядов. Почленное сложение рядов. Свойства ряда и его остатка. (Теоремы 3 и 4)

63. Ряды. Простейшие свойства рядов. Сумма остатка сходящегося ряда. Общий член сходящегося ряда. (Теоремы 5 и 6)