← Дискретная математика (курс 2)

Преподаватель

Лекции и практические занятия — ассистент Стефанова Татьяна Сергеевна

Экзамен

Вопросы к экзамену (в картинках или текстом)

Домашние работы

Сдача домашних работ осуществляется по пятницам в 15¹⁵

Cписок вариантов (в картинках)

Первое, второе, третье, четвертое, пятое и шестое домашние задания (в картинках)

Все домашние работы на этот момент 1, 2, 3, 4, 5, 6 и 7 части (в картинках)

Учебный план (проверочные и домашние работы) (формат Лексикона)

Дополнительная глава текстом (формат Лексикона) или картинками: 1, 2, 3, 4, 5, 6, 7 и 8 страницы

Варианты и рейтинги

Новый рейтинг за 12.12.2008, за 14.11.2008, за 19.09.2008

Вопросы к экзамену

Список вопросов по дисциплине "Дискретная математика" для специальности "Информационные системы" факультет "Информационных технологий" РГПУ им. А.И.Герцена, 2-й курс, осенний семестр, 2008/2009 учебный год
Автор: Татьяна Сергеевна Стефанова.

1. Понятие "множество", "подмножество ^{собственное подмножество, тривиальное подмножество). Равные множества.}
2. Способы образования множеств (интенсиональный, экстенсиональный и конструктивный способы). Теоретико-множественные операции (объединение, пересечение, разность, симметрическая разность, универсальное множество).
3. Понятие "упорядоченная пара", "кортеж". Декартово произведение.
4. Бинарные отношения. Операции над бинарными отношениями.
5. Отношение порядка (отношение порядка, отношение предпорядка, отношение строгого порядка, отношение линейного порядка).
6. Понятие "отображение". Образ и прообраз множества. Композиция двух функций.
7. Инъективное, сюръективное и биективное отображение.
8. Мощность множества.
9. Унарные и бинарные алгебраические операции.
10. Понятие "рекуррентные соотношения".
11. Решение линейного рекуррентного соотношения первого порядка.
12. Линейные однородные рекуррентные соотношения второго порядка с постоянными коэффициентами.
13. Линейные неоднородные рекуррентные соотношения второго порядка с постоянными коэффициентами. Линейные неоднородные рекуррентные соотношения порядка >2 с постоянными коэффициентами.
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. Распознающие формальные грамматики. Преобразующие формальные грамматики.

Варианты

Специальность: информационные системы. 2 курс, 2 группа. Дисциплина: "Дискретная математика".

• 1 — Зайцева Ксения
• 2 — Маркитанов Айат
• 3 — Маяк Иван
• 4 — Петренко Екатерина
• 5 — Рахматулина Диана
• 6 — Романцов Павел
• 7 — Рыжов Сергей
• 8 — Селиванова Елизавета
• 9 — Серебрянников Дмитрий
• 10 — Соловаров Алексей
• 1 — Тагунов Тихон
• 2 — Трифонова Татьяна
• 4 — Чернигов Дмитрий
• 5 — Щеголев Сергей
• ? — Великий Алексей

← Дискретная математика (курс 2)