ПРИЛОЖЕНИЕ № 2. Перечень вопросов необходимого минимума для получения

положительной оценки на экзамене по курсу «Дискретная математика»

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. Теоремы о маршрутах и циклах.

1. Дерево (ордерево).
2. Теоремы о деревьях.
3. Планарный граф.
4. Хроматическое число графа.
5. Двухполюсная направленная сеть, поток.
6. Разрез.
7. Теорема Форда-Фалкерсона.
8. Алфавит, слово, код.
9. Схема алфавитного кодирования.
10. Префиксный код.
11. Однозначность кодирования.
12. Теорема Маркова.
13. Неравенство Макмиллана.
14. Избыточность кода.
15. Оптимальный код.
16. Теорема редукции.
17. Код Хаффмена.
18. Кодовое расстояние Хемминга.
19. Коды, обнаруживающие и исправляющие ошибки.
20. Код Хемминга, исправляющий одну ошибку.
21. Линейная комбинация двоичных векторов, линейная зависимость и независимость.

Примечание: для получения положительной оценки все теоремы из данного списка достаточно знать без доказательств.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА ДЛЯ ПРЕПОДАВАТЕЛЯ

1. Аляев, Ю.А. Дискретная математика и математическая логика / Ю.А. Аляев, С.Ф. Тюрин. М.: Финансы и статистика, 2006. 368 с.
2. Асеев, Г.Г. Дискретная математика / Г.Г. Асеев, О.М. Абрамов, Д.Э. Ситников. Ростов: Феникс, 2003. 144 с.
3. Берлекэмп, Э. Алгебраическая теория кодирования / Э. Берлекэмп. М.: Мир, 1971. 478 с.
4. Виленкин, Н.Я. Комбинаторика / Н.Я. Виленкин. М.: Наука, 1969. 328 с.
5. Виленкин, Н.Я. Комбинаторика / Н.Я. Виленкин, А.Н. Виленкин, П.А. Виленкин. М.: ФИМА – МНЦО, 2006. 400 с.
6. Вольфовиц, Д. Теоремы кодирования теории информации / Д. Вольфовиц. М.: Мир, 1967. 248 с.
7. Гаврилов, Г.П. Задачи и упражнения по дискретной математике / Г.П.Гаврилов, А.А.Сапоженко. М.: ФИЗМАТЛИТ, 2004. 416 с.
8. Горбатов, В.А. Дискретная математика / В.А. Горбатов, А.В. Горбатов, М.В. Горбатова. М.: АСТ, 2003, 448 с.
9. Емеличев, В.А. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990. 384 с.
10. Зыков, А.А. Теория конечных графов / А.А. Зыков. Новосибирск: Наука, 1969. 544 с.
11. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. М.: Мир, 1978. 432 с.
12. Касами, Т. Теория кодирования / Т. Касами, Н. Токура, Ё. Ивадари. М.: Мир, 1978. 576 с.
13. Кузнецов, А.В. Сборник задач и упражнений по высшей математике. Математическое программирование / А.В. Кузнецов, В.А. Сакович, Н.И. Холод, Л.Ф. Дежурко, Р.А. Рутковский, Н.М. Слукин. Минск: Вышэйшая школа, 1995. 382 с.
14. Кук, В. Компьютерная математика / В. Кук, Г. Бейз. М.: Наука, 1990. 384 с.
15. Куратовский, К. Теория множеств / К. Куратовский, А. Мостовский. М.: Мир, 1970. 416 с.
16. Марков, А.А. Введение в теорию кодирования / А.А. Марков. М.: Наука, 1982. 364 с.
17. Матросов, В.Л. Лекции по дискретной математике / В.Л. Матросов, В.Н. Стеценко. М.: МПГУ, 1997. 220 с.
18. Москинова, Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях / Г.И. Москинова. М.: Логос, 2004. 240 с.
19. Нефёдов, В.Н. Курс дискретной математики / В.Н. Нефёдов, В.А. Осипова. М.: МАИ, 1992. 264 с.
20. Нечаев, В.И. Элементы криптографии (Основы теории защиты информации): учебное пособие для университетов и педвузов / В.И. Нечаев, под ред. В.А.Садовничего. М.: Высшая школа, 1999. 256 с.
21. Оре, О. Теория графов / О. Оре. М.: Наука, 1980. 336 с.
22. Питерсон, У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон. М.: Мир, 1976. 593 с.
23. Риордан, Дж. Введение в комбинаторный анализ / Дж. Риордан. М.: Изд-во иностранной литературы, 1963. 287 с.
24. Риордан, Дж. Комбинаторные тождества / Дж. Риордан. М.: Наука, 1982. 255 с.
25. Рыбников, К.А. Введение в комбинаторный анализ / К.А. Рыбников. М.: Изд-во МГУ, 1985. 312 с.
26. Сачков, В.Н. Введение в комбинаторные методы дискретной математики / В.Н. Сачков. М.: МЦМНО, 2004. 424 с.
27. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. М.: Мир, 1984. 455 с.
28. Соболева, Т.С. Дискретная математика / Т.С. Соболева, А.В. Чечкин. М.: Академия, 2006. 255 с.
29. Стариченко, Б.Е. Теоретические основы информатики / Б.Е. Стариченко. М.: Горячая линия – Телеком, 2003. 312 с.
30. Судоплатов, С.В. Дискретная математика / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2007. 256 с.
31. Судоплатов, С.В. Элементы дискретной математики / С.В. Судоплатов, Е.В. Овчинникова. М: Инфра-М, 2002. 288 с.
32. Уилсон, Р. Введение в теорию графов / Р. Уилсон. М.: Мир, 1977. 208 с.
33. Фудзисава, Т. Математика для радиоинженеров. Теория дискретных структур / Т. Фудзисава, Т. Касами. М.: Радио и связь, 1984. 240 с.
34. Харари, Ф. Теория графов / Ф. Харари. М.:УРСС, 2006. 296 с.
35. Холл, М. Комбинаторика / М. Холл. М.: Мир, 1970. 424 с.
36. Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. М.: Высшая школа, 2003. 384 с.

Дата добавления: 2015-07-20