Программа подготовки к экзаменам по курсу «Дискретная математика»



Скачать 43.33 Kb.
Дата23.12.2012
Размер43.33 Kb.
ТипПрограмма
Программа подготовки к экзаменам по курсу «Дискретная математика»

(очная форма обучения)

1. Элементы теории множеств

1.1 Понятие множества.

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

1.2. Операции над множествами.

Объединение множеств. Пересечение множеств. Разность множеств. Симметрическая разность. универсальное множество. дополнение множества. Принцип двойственности в алгебре множеств. Тождества алгебры множеств. Разбиение множества. Упорядоченное множество. Прямое произведение множеств. Проекция.

1.3 Соответствия.

Обратное соответствие. Композиция соответствий. Отображения и функции. Сюръекция. Инъекция. Биекция. Основные свойства отображений. Функция. Способы задания функции. Сужение функции. Обратная функция. Функция времени. Понятие функционала. Понятие оператора.

1.4 Отношения.

Задание бинарных отношений. Свойства бинарных отношений (теоремы). Примеры отношений: отношение тождества, рефлексивные отношения, иррефлексивные отношения, симметричные отношения, транзитивные отношения, антисимметричные отношения. Отношение эквивалентности. Лемма о разбиении множества на классы. Свойства отношения эквивалентности. Отношение порядка.

1.5. Конечные и бесконечные множества.

Счетные и несчетные множества. Свойства счетных множеств. Эквивалентность множеств. Теорема Г. Кантора. Теорема Кантора-Бернштейна. Верхняя и нижняя границы множества. Теорема о верхних и нижних границах подмножества. Понятие мощности множества. Аксиоматика Цермелло-Френкеля
2. Основные положения теории графов.

2.1. Определение графа.

Граф. Ориентированный, неориентированный графы. Регулярные графы. Нуль-граф. Полный граф. Платоновы графы. Двудольные графы. Изоморфизм графов. Подграф. Частичный граф.

2.2. Операции в графе.

Операция удаления ребра. Операция удаления вершины. Операция введения ребра. Операция введения вершины. Операция объединения графов. Произведение графов. Слияние вершин. Операция стягивания ребра. Операция расщепления вершины. Операция соединения графов. Операция дополнения графа. Теорема о сумме степеней вершин графа.

2.3. Свойства графов.

Маршруты, циклы, связность. Свойства регулярных графов. Свойства двудольных графов. Свойства связных графов. Метрические характеристики связных графов. Свойства эйлеровых графов. Свойства гамильтоновых графов. Множества внутренней и внешней устойчивости графа.

2.4 Матричные представления графа.

Матрица смежности графа. Теорема об изоморфизме графов. Теорема о числе маршрутов длины k. Матрица инциденций. Достижимость. Матрица достижимостей графа. Матрица контрдостижимостей графа. Матрица Кирхгофа.

2.5. Характеристики графов.

Раскраска графов. Хроматическое число.
Правильная раскраска. Практические задачи, сводящиеся к задаче раскраски.

2.6. Деревья.

Определение дерева. Свойства деревьев. Теорема о представлении графа как дерева.

Теорема о сумме степеней графа. Связность графа. Дерево. Изоморфизм графов. Отношение порядка и отношение эквивалентности на графе.

2.7. Ориентированные графы и деревья.

Орграф. Характеристики орграфа. Теорема о сумме степеней вершин орграфа. Ориентированное дерево. Определение путей экстремальной длины в орграфе.


3. Элементы комбинаторики.

3.1 Правило суммы. Правило прямого произведения. Размещения с повторениями. Размещения без повторений. Перестановки. Сочетания. Сочетания с повторениями. Полиноминальная формула. Бином Ньютона. Свойства биноминальных коэффициентов. Метод рекуррентных соотношений. Метод включений и исключений.
4 Элементы алгебры

4.1 Понятие алгебраической структуры. n-местные операции на множестве. Нульарная операция. Нейтральный элемент. Алгебра. Носитель, сигнатура алгебры. Отношение конгруэтности. Группоид. Полугруппа. Моноид. Полурешетка. Группа. Абелевы группы. Примеры групп. Левый и правый законы сокращения (теорема). Единственность решений уравнений (теорема). Степень элемента а. Образующий элемент полугруппы (группы). Кольцо. Примеры кольца. Тело. Поле. Модуль. Подгруппы и подкольца. Гомоморфизм, эпиморфизм, изоморфизм групп.
5. Элементы теории кодирования.

5.1 Дискретные сообщения. Коды и кодирование. Двоичное кодирование. Двоично-десятичные коды.

5.2 Систематический код. Корректирующая способность кода. Кодовое расстояние. Методы эффективного кодирования информации. Код Шеннона-Фано. Код Д. Хаффмена. Кодирование по методу четности-нечетности. Коды Хемминга.
6. Элементы теории информации.

Определение информации. Информационные меры. Структурная мера. Аддитивная мера. Статистическая мера информации. Понятие энтропии. Основные свойства энтропии. Количество информации. Объем информации. Основные информационные характеристики.

7. Представление числовой информации в цифровых устройствах


7.1 Системы счисления

Системы счисления. Позиционные и непозиционные системы счисления. Диапазон представления чисел в заданной системе счисления. Перевод числовой информации из одной позиционной системы счисления в другую. Способы (методы) перевода.

7.2. Формы представления чисел.

Естественная и нормальные формы представления чисел. Представление чисел в формате с плавающей и фиксированной точкой. Нормализованная форма представления чисел. Формы представления отрицательных чисел. Прямой, обратный и дополнительный коды чисел. Погрешности представления чисел.

7. 3. Основы двоичной арифметики.

Сложение чисел в формате с фиксированной и плавающей точкой на двоичных сумматорах прямого, обратного и дополнительного кодах. Операция нормализации. Признаки нарушения нормализации числа. Оценка точности выполнения арифметических операций. Погрешности выполнения арифметических операций. Погрешности округления.
Рекомендуемая литература: 1. С.В. Яблонский. Введение в дискретную математику. М., В.ш., 2001 г. 2. Я.М. Ерусалимский. Дискретная математика., М, Вузовская книга, 2001. 3. Б.Н. Иванов. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2002. 4.С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики. М.-Новосибирск, ИНФРА-М, НГТУ, 2002. 5. Г.П. Гаврилов, А.А. Сапоженко. Задачи и упражнения по дискретной математике. М., Физматлит, 2004. 6. В.А. Горбатов, А.В. Горбатов, М.В. Горбатова. Дискретная математика. М., АСТ Астрель, 2003. 7. Н.К. Верещагин, А. Шень. Начала теории множеств. МЦНМО, 2002


Программу составил профессор кафедры ВИТ В.В. Алексеев

Похожие:

Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма подготовки к экзаменам по курсу «Дискретная математика»
Основные определения. Способы задания множеств. Равенство множеств. Подмножество
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины «Дискретная математика»
...
Программа подготовки к экзаменам по курсу «Дискретная математика» iconРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика Квалификация выпускника
Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 Социология подготовки бакалавра
Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета...
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины Дискретная математика для социологов для направления 040200. 62 «Социология» подготовки бакалавра Автор: Дагаев Д. А
Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является...
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Программа подготовки к экзаменам по курсу «Дискретная математика» iconПрограмма дисциплины «Дискретная математика и теория алгоритмов»
Рабочая программа дисциплины «Дискретная математика» [Текст]/Сост. Артамкин И. В., Ландо С. К.; Гу-вшэ.–Москва.–2009.–11 с
Разместите кнопку на своём сайте:
ru.convdocs.org


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