Главная

Контакты

Случайная статья

• Автоматизация
• Антропология
• Археология
• Архитектура
• Биология
• Ботаника
• Бухгалтерия
• Военная наука
• Генетика
• География
• Геология
• Демография
• Деревообработка
• Журналистика
• Зоология
• Изобретательство
• Информатика
• Искусство
• История
• Кинематография
• Компьютеризация
• Косметика
• Кулинария
• Культура
• Лексикология
• Лингвистика
• Литература
• Логика
• Маркетинг
• Математика
• Материаловедение
• Медицина
• Менеджмент
• Металлургия
• Метрология
• Механика
• Музыка
• Науковедение
• Образование
• Охрана Труда
• Педагогика
• Полиграфия
• Политология
• Право
• Предпринимательство
• Приборостроение
• Программирование
• Производство
• Промышленность
• Психология
• Радиосвязь
• Религия
• Риторика
• Социология
• Спорт
• Стандартизация
• Статистика
• Строительство
• Технологии
• Торговля
• Транспорт
• Фармакология
• Физика
• Физиология
• Философия
• Финансы
• Химия
• Хозяйство
• Черчение
• Экология
• Экономика
• Электроника
• Электротехника
• Энергетика

по дисциплине «Дискретная математика»

Список вопросов к экзамену

по дисциплине «Дискретная математика»

Составитель: Некрасов В.П.

Список теоретических вопросов

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. Логические элементы. Логические схемы.

30. Реализация логических функций в классическом базисе.

31. Реализация операции сложения в компьютере.

32. Основные понятия теории графов

33. Матрица смежности. Матрица инциденций

34. Связные графы. Деревья.

35. Остов. Минимальный остов.

36. Раскрашенный граф. Хроматическое число.

37. Понятие структуры данных в программировании.

38. Одномерный и двумерный массивы.

39. Стек. Очередь.

40. Дерево. Размещение дерева по уровням.

41. Представление графа в компьютере.

42. Реализация списков смежностей упакованным массивом.

43. Интуитивное понятие алгоритма. Свойства алгоритма.

44. Вычислительные и комбинаторные алгоритмы.

45. Временная эффективность алгоритмов.

46. Асимптотические оценки сложности.

47. Жадный алгоритм построения минимального остовного дерева. Жадный

48. Алгоритм Прима построения минимального остовного дерева..

49. Алгоритм Дейкстра поиска кратчайшего пути в графе между двумя заданными вершинами.

50. Алгоритм определения кратчайших путей Флойда – Уоршолла.

51.  Алгоритм Уоршолла построения транзитивного замыкания.

52. Эвристические алгоритмы. Алгоритм последовательной алгоритм раскраски графа в минимальное число цветов.

53. Алгоритм раскраски графа методом А.П. Ершова.

54. Внутренняя сортировка. Пузырьковые сортировки.

55. Сортировки выбором и вставкой. Быстрая сортировка.

56. Пирамидальная сортировка. Сортировка подсчетом.

57. Внешняя сортировка. Методы прямого и естественного слияния. Основная теорема сортировки.

58. Бинарный поиск. Поиск на графах в глубину и ширину.

59. Поиск связных компонент графа. Топологическая сортировка.

60. Поиск в строке текста заданного фрагмента. Последовательный поиск. Метод Боуэра и Мура.