Программа курса "Дискретная математика"



Скачать 112.06 Kb.
Дата08.10.2012
Размер112.06 Kb.
ТипПрограмма курса
Программа курса "Дискретная математика"
Теория дискретных множеств

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

Экзаменационные вопросы к учебному курсу "Дискретная математика"

(2 семестр 2001 г.)


  1. Множества. Операции над множествами. Примеры [1,2,3].

  2. Булеан. Свойства операций над подмножествами. Примеры [1,2,3].

  3. Представление множеств и реализация операций над ними в ЭВМ [1,2,3].

  4. Отображения, функции. Представление функций в ЭВМ [1,2,3].

  5. Операции. Примеры [1,2,3].

  6. Отношения и их свойства. Примеры [1,2,3].

  7. Представление отношений в ЭВМ [1,2,3].

  8. Отношения эквивалентности. Примеры [1,2,3].

  9. Отношения порядка. Примеры [1,2,3].

  10. Замыкание отношений. Примеры [1,2,3].

  11. Алгебры, подалгебры, морфизмы. Основные определения и свойства Примеры [1,2,3].

  12. Определение и основные свойства булевых алгебр. Примеры [1,2,3].

  13. Нормированные булевы алгебры [1,2,3].


  14. Алгебра логики. Элементарные булевы функции (функции алгебры логики) [1,2,3,4].

  15. Формулы. Реализация функций формулами. Примеры [1,2,3,4].

  16. Принцип двойственности. Примеры применения принципа [1,2,3,4].

  17. Нормальные формы. Примеры [1,2,3,4].

  18. Представление булевых функций полиномом Жигалкина И.И. Примеры [1,2,3,4].

  19. Замкнутые классы булевых функций. Примеры [1,2,3,4].

  20. Полнота множества булевых функций. Примеры [1,2,3,4].

  21. Минимизация булевых функций. Примеры [1,2,3,4].

  22. Упрощение дизъюнктивной нормальной формы (ДНФ), тупиковые ДНФ. Примеры [1,2,3,4].

  23. Синтез схем из функциональных элементов. Примеры [1,4].

  24. Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Пример [1,4].

  25. Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова). Пример [1,4].

  26. Графы. Виды графов. Изоморфизм графов. Примеры [1,3]

  27. Подграфы, маршруты, цепи, циклы. Примеры [1,3]

  28. Представление графов в ЭВМ. Матрицы смежностей, инциденций. Примеры [1,3]

  29. Связность графов. Компоненты связности. Примеры [1,3]

  30. Операции над графами. Примеры [1,3]

  31. Планарные графы. Критерии планарности. Примеры [1,3]

  32. Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Примеры [1,3]

  33. Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Пример [1,3]

  34. Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Примеры [1,3]

  35. Представления деревьев в ЭВМ. Примеры [1,3]

  36. Нахождение кратчайшего пути в графе. Примеры [1,3]

  37. Фундаментальные циклы и разрезы. Примеры [1,3]

  38. Эйлеровы циклы. Примеры [1,3]

  39. Гамильтоновы циклы. Примеры [1,3]

  40. Алфавитное кодирование. Неравенство Макмиллана. Примеры [1,3,4]

  41. Кодирование с минимальной избыточностью. Примеры [1,3,4]

  42. Помехоустойчивое кодирование. Примеры [1,3,4]

  43. Код Хемминга для исправления одного замещения. Пример [1,3,4]

  44. Сжатие данных. Алгоритм Лемпела-Зива. Примеры [1,3]


Литература

  1. Конспект лекций

  2. В.И. Городецкий "Прикладная алгебра и дискретная математика. ч.1 М., 1983 г.

  3. Новиков Ф.А. "Дискретная математика для программистов", СПб, 2000 г.

  4. C.В. Яблонский "Введение в дискретную математику" М., Наука, 1988 г.

Экзаменационные билеты к учебному курсу "Дискретная математика"

(2 семестр 2001 г.)
Билет № 1

1. Множества. Операции над множествами. Примеры.

2. Оптимальный по порядку метод синтеза схем из функциональных элементов (метод К. Шеннона). Пример.
Билет № 2

1. Булеан. Свойства операций над подмножествами. Примеры

2. Асимптотически наилучший метод синтеза схем из функциональных элементов (метод О.Б.Лупанова). Пример.
Билет № 3

1. Представление множеств и реализация операций над ними в ЭВМ. Пример.

2. Алфавитное кодирование. Неравенство Макмиллана. Примеры.
Билет № 4

1. Отображения, функции. Представление функций в ЭВМ. Примеры.

2. Кодирование с минимальной избыточностью. Примеры.
Билет № 5

1. Операции. Примеры.

2. Код Хемминга для исправления одного замещения. Пример.
Билет № 6

1. Отношения и их свойства. Примеры.

2. Сжатие данных. Алгоритм Лемпела-Зива. Примеры.
Билет № 7

1. Представление отношений в ЭВМ. Примеры.

2. Планарные графы. Критерии планарности. Примеры.
Билет № 8

1. Отношения эквивалентности. Примеры.

2. Помехоустойчивое кодирование. Примеры.
Билет № 9

1. Отношения порядка. Примеры.

2. Синтез схем из функциональных элементов. Примеры.
Билет № 10

1. Замыкание отношений. Примеры.

2. Представление графов в ЭВМ. Матрицы смежностей, инциденций. Примеры.
Билет № 11

1. Алгебры, подалгебры, морфизмы. Основные определения и свойства Примеры.

2. Представления деревьев в ЭВМ. Примеры.
Билет № 12

1. Определение и основные свойства булевых алгебр. Примеры.

2. Связность графов. Компоненты связности. Примеры.
Билет № 13

1. Нормированные булевы алгебры. Примеры.

2. Операции над графами. Примеры.
Билет № 14

1. Алгебра логики. Элементарные булевы функции (функции алгебры логики).

2. Сети. Потоки в сетях. Теорема Форда и Фалкерсона. Примеры.

Билет № 15

1. Формулы. Реализация функций формулами. Примеры.

2. Алгоритм нахождения максимального потока, основанный на теореме Форда и Фалкерсона. Пример.
Билет № 16

1. Принцип двойственности. Примеры применения принципа.

2. Деревья. Ориентированные, упорядоченные и бинарные деревья. Свойства деревьев. Примеры.

Билет № 17

1. Нормальные формы. Примеры.

2. Нахождение кратчайшего пути в графе. Примеры.
Билет № 18

1. Представление булевых функций полиномом Жигалкина И.И. Примеры.

2. Фундаментальные циклы и разрезы. Примеры.
Билет № 19

1. Замкнутые классы булевых функций. Примеры.

2. Гамильтоновы циклы. Примеры.
Билет № 20

1. Полнота множества булевых функций. Примеры.

2. Эйлеровы циклы. Примеры.
Билет № 21

1. Минимизация булевых функций. Примеры.

2. Подграфы, маршруты, цепи, циклы. Примеры.
Билет № 22

1. Упрощение дизъюнктивной нормальной формы (ДНФ), тупиковые ДНФ. Примеры.

2. Графы. Виды графов. Изоморфизм графов. Примеры.

Похожие:

Программа курса \"Дискретная математика\" iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Программа курса \"Дискретная математика\" iconПрограмма дисциплины «Дискретная математика»
...
Программа курса \"Дискретная математика\" iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 «Социология» подготовки бакалавра Автор: Дагаев Д. А
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Программа курса \"Дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"Дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"Дискретная математика\" iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа курса \"Дискретная математика\" iconРабочей программы дисциплины дискретная математика
Дискретная математика и математическая логика входят в цикл профессиональных дисциплин в базовой части. Для их успешного изучения...
Программа курса \"Дискретная математика\" iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Программа курса \"Дискретная математика\" iconУчебная программа Дисциплины б2 «Дискретная математика» по направлению 010300 «Фундаментальная информатика и информационные технологии»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Программа курса \"Дискретная математика\" iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org