Решебники для студентов » Высшая математика » Методические указания по Высшей математике » Методические указания к самостоятельной работе по дисциплине “Дискретная математика”

Методические указания к самостоятельной работе по дисциплине “Дискретная математика”

Автор: santa от 26-10-2011, 01:21
Нравится(+) 0 Не нравится(-)
Наш сайт тебе помог в решении задачи, сдачи курсовой или диплома?

В знак благодарности - Напиши отзыв и Расскажи друзьям о нас!



Методические указания  к самостоятельной работе по дисциплине   “Дискретная математика”
Дисциплина “Дискретная математика" является составной частью фундаментальной инженерной и специальной математической подготовки. Изучение дисциплины способствует овладению математическими основами профилирующих дисциплин и методами построения и реализации эффективных алгоритмов.

У процессе овладения учебной дисциплиной студенты получают навыки и опыт применения на практике разных математических аппаратов, разработки и внедрения в программах алгоритмов решения задач на графах, сетях.

Данные методические указания предназначены более углубленному самостоятельному изучению математических основ дисциплины.

Первый раздел методических указаний посвящен элементам теории графов. В дискретной математике, теоретической информатике, про-граммировании граф является важнейшим математическим понятием. На основе теории графов строятся модели разнообразных задач: маршрутизации, распределения ресурсов, дискретной оптимизации и управления, минимизации автоматов и алгоритмов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи.

Во втором разделе рассматриваются вопросы, связанные с кодированием информации.

Третий и пятый разделы посвящены вопросам исчисления: реляционного и ламбда-исчисления.

В четвертом разделе основное внимание уделено элементам теории чисел – модулярной арифметике и вычислениям в конечных полях.

Содержание:

ВВЕДЕНИЕ 6
I ТЕОРИЯ ГРАФОВ 7
1 ИСТОРИЯ ТЕОРИИ ГРАФОВ 7
2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 8
3 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ 10
3.1 Матрицей смежности 10
3.2 Матрицей инцидентности 11
3.3 Связные графы 11
3.4 Изоморфизм графов 13
3.5 Представление графов в памяти компьютера 13
3.5.1 Матрицей инциденций 14
3.5.2 Матрицей смежности 15
3.5.3 Списком пар 16
3.5.4 Списком инцидентности 17
4 ПУТИ В ГРАФАХ 18
4.1 Задача о кратчайшем пути 18
4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе 19
4.3 Пример решения задачи нахождения кратчайшего пути 19
5 ТРАНСПОРТНЫЕ СЕТИ 21
5.1 Потоки в транспортных сетях 21
5.2 Задача нахождения наибольшего потока в транспортной сети 24
5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети 24
5.4 Пример нахождения максимального потока 26
6 ТРАНСПОРТНАЯ ЗАДАЧА 28
6.1 Транспортная задача по критерию стоимости 28
6.2 Алгоритм метода частичных потоков 29
6.3 Пример решения транспортной задачи по критерию стоимости 30
6.4 Транспортная задача по критерию времени 33
7 ОБХОДЫ В ГРАФАХ 36
7.1 Эйлеровы графы 36
7.2 Алгоритм Флёри нахождения эйлерова цикла 39
7.3 Гамильтоновы циклы 41
7.4 Метод ветвей и границ. 43
7.5 Метод ветвей и границ в задаче о коммивояжёре 44
7.6 Алгоритм поиска гамильтонова цикла 45
7.7 Пример решения задачи о коммивояжёре 46
8 ДЕРЕВЬЯ 52
8.1 Определения 53
8.2 Соотношение между числом вершин и ребер 53
8.3 Ориентированные деревья 54
8.4 Свойства ориентированных деревьев 55
8.5 Эквивалентное определение ордерева 56
8.6 Упорядоченные деревья 56
8.7 Бинарные деревья 58
8.8 Представление в ЭВМ свободных, ориентированных и упорядоченных деревьев 59
8.9 Представление бинарных деревьев 60
8.10 Обходы бинарных деревьев 61
8.11 Выровненные деревья 61
8.12 Сбалансированные деревья 62
8.13 Построение экономического дерева 63
8.14 Остов минимального веса 63
8.15 Схема алгоритма построения кратчайшего остова 64
8.16 Алгоритм Краскала 64

II КОДИРОВАНИЕ ИНФОРМАЦИИ 66
1 ОПТИМАЛЬНОЕ КОДИРОВАНИЕ 66
2 ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК 72
2.1 Общие понятия 72
2.2 Линейные групповые коды 74
2.3 Код Хэмминга 80
3.4 Циклические коды 84

III РЕЛЯЦИОННОЕ ИСЧИСЛЕНИЕ 93
1 РАЗЛИЧИЯ МЕЖДУ РЕЛЯЦИОННОЙ АЛГЕБРОЙ 93
И РЕЛЯЦИОННЫМ ИСЧИСЛЕНИЕМ 93
2 ВИДЫ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ 94
2.1 Реляционное исчисление кортежей 95
2.1.1 Алфавит 95
2.1.2 Формулы 96
2.1.3 Соотношения между реляционной алгеброй и запросами реляционного исчисления кортежей 96
2.2 Реляционное исчисление доменов 97
2.2.1 Алфавит 97
2.2.2 Формулы 97
2.2.3 Соотношения между реляционной алгеброй и запросами реляционного исчисления доменов 97
3 ЯЗЫКИ РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ 98
3.1 Языки исчисления кортежей 98
3.1.1 QUEL (Query language) 98
3.1.2 SQL (Structured query language) 100
3.2 Языки исчисления доменов 101
3.2.1 QBE (Query – by – Example) 101
4 ПОЛНОТА РЕЛЯЦИОННОГО ИСЧИСЛЕНИЯ 102

IV ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ 103
1 МОДУЛЯРНАЯ АРИФМЕТИКА 103
1.1 Алгоритм Евклида для нахождения наибольшего общего делителя 106
1.2 Вычисление обратных величин 107
1.3 Основные способы нахождения обратных величин 111
1.4 Расширенный алгоритм Евклида 112
1.5 Китайская теорема об остатках 114
1.6 Квадратичные вычеты 116
2 ВЫЧИСЛЕНИЯ В КОНЕЧНЫХ ПОЛЯХ 118
2.1 Свойства многочленов в двоичном поле GF(2) 120
2.2 Достоинства вычислений в поле Галуа GF(2 n) 125

V ЛАМБДА – ИСЧИСЛЕНИЕ 128
1 ФУНКЦИИ И ИХ ОПРЕДЕЛЕНИЕ 128
1.1 Особенности функциональных языков 128
1.2 Функция как отображение множеств 129
1.2.1 Способы задания функций 129
1.2.2 Функция многих аргументов 131
1.2.3 Композиция функций (составной оператор) 131
1.2.4 Свойства композиции функций 132
2 АЛФАВИТ ЛАМБДА- ИСЧИСЛЕНИЯ 132
3 ЗАПИСЬ РЕКУРСИВНЫХ ОПРЕДЕЛЕНИЙ В ЛАМБДА-ОБОЗНАЧЕНИЯХ 134
3.1 Восходящая и нисходящая рекурсии 135
4 РЕКУРСИВНАЯ ОБРАБОТКА СПИСКОВ 136
4.1 Последовательный доступ с помощью рекурсии 137
4.2 Построение списков 137
4.3 Реализация 138
4.4 Типы рекурсивных функций 139
4.4.1 Как писать рекурсивные определения 140
РЕКОМЕНДОВАННАЯ ЛИТЕРАТУРА 142

Скачать:
Зарегистрируйтесь, чтобы иметь возможность скачивать с нашего сайта.



Теги: Дискретная математика, Методические указания

ВНИМАНИЕ! Регистрация возможна только по инвайтам.
Как получить инвайт-ключ написано на этой странице.

Комментарии:

Оставить комментарий