МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

Кафедра кибернетики

и вычислительной техники

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

по изучению дисциплины "Дискретная математика" для студентов заочной формы обучения специальности 7.091501 – «Компьютерные системы и сети»

Севастополь – 2009 Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ

1.1. Цель дисциплины - обучение студентов методам решения задач прикладной дискретной математики, являющейся математическим базисом образования бакалавра в области компьютерной инженерии.

Дискретная математика используется в качестве математического аппарата большинства курсов по специальностям, связанных с проектированием, программированием и применением ЦВМ. Курс включает в себя материалы по основным направлениям дискретной математики, что отражено в разбиении курса на разделы:

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

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

Результатами решений задач являются не столько числа, сколько оптимальные в некотором смысле подмножества, структуры, формы представления информации.

1.2. Задачи изучения дисциплины.

При изучении материала студенты приобретают следующие основные з н а н и я :

- осваивают понятия и модели дискретной математики;

- изучают постановки и методы решения задач дискретной математики;

- знакомятся с примерами приложения моделей дискретной математики в науке и технике.

В результате изучения дисциплины студент должен знать:

основные понятия и модели теории конечных множеств и отношений, комбинаторики, теории графов, булевой алгебры;

- формы представления данных и их преобразования;

- методы решения оптимизационных задач.

В результате изучения дисциплины студент должен уметь:

- решать классические задачи дискретной математики и выбора критериев их оптимальности, оценки объема перебора, построения приближенных решений.

Методические рекомендации опираются на учебное пособие и методические рекомендации /1-2/, содержащие теорию, примеры решения всех задач, в том числе и формы представления, там же приведены индивидуальные задания для контрольных работ. Индивидуальные задания Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) определяются по двум последним цифрам зачетки, полученное число делится на 30, остаток определяет номер варианта.

Настоящие рекомендации содержат ссылки на эти пособия, определяющие разбиение материала дисциплины на контрольные работы 1,2 3 и 4, вопросы и задачи к экзамену и список обязательной литературы.

2. УЧЕБНАЯ НАГРУЗКА ПО ДИСЦИПЛИНЕ

Курс 1 Семестр 1. Установочные лекции - (8 часов) 3. Выдача задания к контрольной работе № Курс 1 Семестр 1. Лекции - (8 часов).

2. Выдача задания к контрольной работе №2.

3. Лабораторные занятия №1 и №2 (4 часа ).

4. Защита контрольных работ.

5. Экзамен 6. Установочные лекции - (6 часов).

7. Выдача задания на курсовой проект.

Курс 2 Семестр На протяжении 7-го и 8-го семестров проводятся консультации каждую нечетную субботу в соответствии с расписанием.

3. СТРУКТУРА ДИСЦИПЛИНЫ

Раздел 1. Системы счисления - 2,8,10 и 16, перевод чисел из одной системы счисления в другую, выполнение арифметических операций над числами в формах фиксированной и плавающей точки.

Материал раздела излагается в часы установленных лекций первого Дополнительную информацию по разделу студент может получить из следующих источников:

Задание на контрольную работу № 1 состоит из задач, формулировка которых и исходные данные к ним приведены в [1]:

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) - Индивидуальные задания к параграфам 1.1 – 1.7 (стр. 10, 13, 15, 16, 20, Вопросы для самопроверки результатов изучения материалов раздела 1.

3. Особенности перевода 2 - 8 и 8 - 2, обоснование правила 5. Алгебраическое сложение, прямой, дополнительный и 6. Алгоритмы алгебраического сложения.

7. Представление чисел в форме с фиксированной точкой.

8. Представление чисел в форме с плавающей точкой.

9. Алгоритм сложения чисел в форме с плавающей точкой.

10. Алгоритм умножения чисел в форме плавающей точки.

11. Алгоритм деления чисел в форме плавающей точки.

Раздел 2. Задачи оптимизации на конечных множествах Материал раздела излагается во время лекционных занятий в первом семестре.

Дополнительную информацию по данному разделу можно получить из следующих источников:

Задание на контрольную работу № 2 состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:

- Вопросы и задачи к параграфу 1.2.4 стр. 18 (задание Г) - Вопросы и задачи к параграфу 1.2.6 стр. 24 (задание В) - Вопросы и задачи к параграфу 1.2.8 стр. 31 (задания В, Г, Д) - Вопросы и задачи к параграфу 1.3 стр. 40 (задание Б) - Вопросы и задачи к параграфу 1.4 стр. 44 (задание В) - Вопросы и задачи к параграфу 1.5 стр.55 (задание В, Г) 2. Отношение эквивалентности. Отношение толерантности.

9. Задача о покрытии. Минимальные и кратчайшие покрытия.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 13. Совместимые подмножества. Метод граничного перебора.

15. Комбинаторные вычисления. Производящие функции.

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

Задание на контрольную работу № 3 состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:

- Вопросы и задачи к параграфу 2.2 стр. 66 (задание В, Г) - Вопросы и задачи к параграфу 2.3 стр. 69 (задание В) - Вопросы и задачи к параграфу 2.4 стр. 77 (задания А, Б, В) - Вопросы и задачи к параграфу 2.5 стр. 81 (задание Б, В) - Вопросы и задачи к параграфу 2.7.4 стр. - Вопросы и задачи к параграфу 2.8 стр. 1. Пути в графе. Кратчайший путь. Волновой алгоритм в не взвешенном и во взвешенном графе.

2. Алгоритм Дейкстры построения кратчайшего пути.

3. Понятие связности. Построение компоненты связности в ненаправленном и направленном графах.

4. Циклы в графе. Понятие системы независимых циклов.

5. Цикломатическое число. Построение фундаментальной системы циклов на основе остова.

6. Алгоритм построения остова. Алгоритм Краскала построения минимального остова.

7. Гамильтонов контур. Метод ветвей и границ. Основные свойства. Идея оценки в задаче о построении Гамильтонова контура.

8. Гамильтонов контур. Идея ветвления в задаче о гамильтоновом 9. Задача о раскраске графа. Хроматическое число. Алгоритм решения задачи кратчайшей раскраски графа.

10. Определение потока в сети. Задача о максимальном потоке.

11. Алгоритм Форда-Фалкерсона.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 12. Определение потока в сети. Задача о минимальном потоке.

13. Планарные графы. Теорема о четырех красках и системе циклов.

14. Алгоритм построения плоского изображения графа.

Раздел 4. Булевы функции и алгоритмические преобразования Материал раздела излагается во время лекционных занятий в третьем семестре. Дополнительную информацию по данному разделу можно получить из следующих источников:

Задание на контрольную работу № 4 состоит из задач, формулировка которых и исходные данные к ним приведены в [2]:

- Вопросы и задачи к параграфу 2.2 стр. 66 (задание В, Г) - Вопросы и задачи к параграфу 2.3 стр. 69 (задание В) - Вопросы и задачи к параграфу 2.4 стр. 77 (задания А, Б, В) - Вопросы и задачи к параграфу 2.5 стр. 81 (задание Б, В) - Вопросы и задачи к параграфу 2.7.4 стр. - Вопросы и задачи к параграфу 2.8 стр. 6. Метод Квайна-Мак-Класки минимизации булевых функций.

Необходимым условием допуска к экзамену по предмету является качественно выполненные и защищенные контрольные работы № 1,2,3 и № 4, а также защищенная курсовая работа.

Варианты заданий и краткие методические указания по выполнению курсового проекта определены в [2] (стр. 84-108).

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) Консультации по всем видам работ, предусмотренных рабочей программой дисциплины, проводит преподаватель по нечетным субботам. Время консультаций определяется, исходя из расписания занятий ведущего дисциплину преподавателя.

4. СПИСОК ВОПРОСОВ ДЛЯ ПОДГОТОВКИ К ЭКЗАМЕНУ

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

1. Особенности перевода 2 - 8 и 8 - 2, обоснование правил перевода, правила перевода 16 - 2 и 2 -16, 2 - 10-ная система.

2. Алгебраическое сложение, прямой, дополнительный и обратный коды, алгоритмы алгебраического сложения.

3. Представление чисел в формах фиксированной и плавающей точки, алгоритм сложения чисел в форме плавающей точки.

4. Алгоритмы умножения и деления чисел в форме плавающей точки.

5. Задача о покрытии. Сокращение таблицы покрытий. Минимальные и кратчайшие покрытия.

6. Разложение таблицы покрытий по столбцу.

8. Совместимые подмножества. Метод граничного перебора.

9. Комбинаторика. Основные виды наборов.

10. Алгоритм Дейкстры построения кратчайшего пути. Примеры для задачи кратчайшего пути.

11. Волновой алгоритм построения длиннейшего пути. Примеры для задачи длиннейшего пути.

ненаправленном и направленном графах.

13. Циклы в графе. Понятие системы независимых циклов.

Цикломатическое число. Построение фундаментальной системы циклов на основе 14. Остов. Алгоритм построения остова. Алгоритм Краскала построения минимального остова.

15. Задача о раскраске графа. Хроматическое число. Алгоритм решения задачи кратчайшей раскраске графа.

16. Определение потока в сети. Задача о максимальном потоке. Алгоритм Форда-Фалкерсона.

17. Задача о минимальном потоке.

18. Планарные графы. Алгоритм построения плоского изображения графа.

19. Булевы функции. Совершенная дизъюнктивная нормальная форма.

Упрощение д.н.ф. Основные операции и их определения.

20. Совершенная дизъюнктивная и конъюнктивная нормальная 21. Метод Квайна-Мак-Класки минимизации булевых функций.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 22. Упрощение д.н.ф. Основные операции и их определения.

9. Упрощение д.н.ф. алгебраическими преобразованиями 11. Метод Квайна-Мак-Класки минимизации булевых функций.

1. Новоселов В.Г. Дискретная математика в задачах и примерах. Часть 2. /Учебное пособие/ Новоселов В.Г., Пластун Т.В., Скатков А.В. – Севастополь: Изд-во СевГТУ, 2002. – 345 с.

2. Новоселов В.Г. Прикладная математика для инженеров системотехников. Дискретная математика в задачах и примерах.

/Учебное пособие/ Новоселов В.Г., Скатков А.В. – К: УМК ВО, Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)