- •Введение
- •1 Общие организационно—методические указания по выполнению курсовой работы
- •2 Выполнение расчетно-графических работ
- •3 Оформление расчетно-графических работ и курсовой работы
- •4 График выполнения курсовой работы
- •5 Методические указания по выполнению расчетно-графической работы №1 на тему: «Расчет числовых характеристик графов»
- •Задание на расчетно-графическую работу №1
- •Расчет числа компонент связности æ(g)
- •Расчет цикломатического числа λ(g) графа g
- •Расчет хроматического числа γ(g) графа g
- •Расчет плотности (g) графа g
- •Расчет неплотности ε(g) графа g
- •5.2.9 Расчет внешней устойчивости ψ(g) графа g
- •5.2.10 Расчет числа внутренней устойчивости (g) графа g
- •6 Методические указания по выполнению расчетно-графической работы № 2 на тему: «Нахождение кратчайшего остова неориентированного графа по алгоритму Дейкстра»
- •6.1 Задание на расчетно-графическую работу № 2
- •6.2 Пример расчетов по алгоритму Дейкстра
- •6.2.1 Построение таблицы обозначений
- •6.2.2. Шаг «0» расчетов
- •6.2.3 Шаг «1» расчетов
- •6.2.4 Шаги «2 — 6» расчетов
- •6.2.5 Выводы
- •7 Методические указания по выполнению расчетно-графической работы №3 на тему: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда»
- •Задание на расчетно-графическую работу №3
- •7.2 Пример расчета кратчайших путей на неориентированном графе
- •7.2.1 Построение матрицы путей и матрицы переходов графа g
- •7.2.2 Шаг 0 расчетов по алгоритму Флойда
- •Шаг 1 расчетов по алгоритму Флойда
- •Шаг 2 расчетов по алгоритму Флойда
- •7.2.5 Шаг 3 расчетов по алгоритму Флойда
- •7.2.6 Шаг 4 расчетов по алгоритму Флойда
- •7.2.7 Шаг 5 расчетов по алгоритму Флойда
- •7.2.8. Шаг 6 расчетов по алгоритму Флойда
- •7.3 Проверка результатов расчетов по алгоритму Флойда
- •7.4 Использование результатов расчетов по алгоритму Флойда
- •8 Методические указания по выполнению расчетно-графической работы № 4 на тему: «Расчет максимального потока в сети с ограниченной пропускной способностью по алгоритму Форда-Фалкерсона»
- •8.1 Задания на выполнение расчетно-графической работы №4
- •8.2 Обозначения
- •Краткие теоретические сведения
- •8.4 Пример выполнению расчетов по алгоритму Форда-Фалкерсона
- •8.4.1 Итерация 1 расчетов по алгоритму Форда-Фалкерсона
- •8.4.2 Итерации 2—6 расчетов по алгоритму Форда-Фалкерсона
- •9 Методические указания по выполнению расчетно-графической работы № 5 на тему: «Расчеты по алгоритмам управления проектом»
- •9.1 Задание на расчетно-графическую работу № 5
- •9.2 Обозначения и краткие теоретические сведения
- •Пример расчетов по алгоритмам управления проектом
- •9.3.1 Выполним нумерацию вершин графа
- •9.3.2 Рассчитаем ранние моменты наступления событий
- •9.3.3 Рассчитаем поздние моменты наступления событий
- •9.3.4 Рассчитаем резерв времени событий
- •9.3.5 Расчет фиктивных работ
- •Рассчитаем полный резерв времени на работы и определим критический путь
- •Рассчитаем свободный, независимый и гарантированный резервы времени
- •Анализ полученных результатов
- •10 Методические указания по выполнению расчетно-графической работы № 6 на тему: «Логическое проектирование схемы, реализующей минимальную булеву функцию»
- •10. 1 Задание на расчетно-графическую работу № 6
- •10.2 Пример выполнения расчетов по конструированию схемы для минимизированной булевой функции
- •Функции четырех переменных
- •10.2.1 Совершенная дизъюнктивная нормальная форма функции,
- •10.2.2 Совершенная конъюнктивная нормальная форма функции, заданной
- •10.2.3. Минимизация булевой функцию методом Квайна
- •10.2.4 Минимизация булевой функции методом карт Карно
- •10.2.5 Сравнение результатов минимизации булевой функцию методами Квайна и карт Карно
- •10.2.6 Разработать схему, реализующую минимальную булеву функцию, используя элементы на два входа и один выход
- •10.2.8 Проверка правильности работы схемы устройства
- •11 Методические указания по выполнению расчетно-графической работы № 7 на тему: «Нахождение всех гамильтоновых циклов на ориентированном графе»
- •11.1 Задание на расчетно-графическую работу № 7
- •11.2 Краткие теоретические сведения
- •11.3 Пример выполнения расчетов по поиску всех гамильтоновых циклов
- •Литература
- •Содержание
Федеральное государственное образовательное учреждение
Высшего профессионального образования
«КАЛИНИНГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ»
Александр Васильевич Колесников
ДИСКРЕТНАЯ МАТЕМАТИКА
Индивидуальные задания и методические указания к курсовой работе для
студентов специальностей 230102.65 — «Автоматизированные системы
обработки информации и управления» и 230101.65 — «Вычислительные машины, комплексы, системы и сети»
Калининград
2007
УДК 519.45
Колесников А.В. Дискретная математика/ Задания и методические указания к курсовой работе для студентов специальностей 230102.65 —«Автоматизированные системы обработки информации и управления» и 230101.65 — «Вычислительные машины, комплексы, системы и сети».— Калининград: КГТУ, с……..
Приводятся задания для выполнения шести разделов курсовой работы по теории графов и основам математической логики. По каждому из разделов даны примеры расчетов с соответствующими методическими указаниями.
Методические указания отвечают требованиям учебной программы дисциплины «Дискретная математика» для подготовки инженеров по специальностям 230102.65 —«Автоматизированные системы обработки информации и управления» и 230101.65 — «Вычислительные машины, комплексы, системы и сети»
Ил. , табл……, список лит….. — названий.
Рецензент — Кафедра систем управления и вычислительной техники Калининградского государственного технического университета.
Калининградский государственный технический университет, 2007.
Введение
Курсовая работа по дискретной математике — один из видов самостоятельной работы студентов над двумя разделами учебной программы — «Теорией графов» и «Основами математической логики», имеющими практическую направленность. Знания, умения и навыки по методам и алгоритмам теории графов и математической логики широко используются при создании автоматизированных систем обработки информации и управления, при разработке, эксплуатации проектных решений по вычислительным машинам, комплексам, локальным и глобальным вычислительным сетям. Кроме этого, на указанных выше разделах базируются и другие дисциплины, которые студенты изучают на последующих курсах. Все это указывает на необходимость осознания студентами значимости и тщательности выполнения расчетов.
В настоящее пособие включены задания и методические указания по выполнению расчетов в соответствии с методами и алгоритмами дискретной математики.
Задания, в основном, сохранены аналогичными [4], за исключением шестого раздела курсовой работы по математической логике, по которому объем самостоятельной работы сокращен. Номер задания соответствует двум последним цифрам зачетной книжки. По номеру и таблице выбираются параметры и уточняется общая формулировка задачи на выполнение расчетов, представляющая для пяти частей курсовой работы по теории графов — исходный граф.
Методические указания в настоящем пособии оформлены в виде примеров расчетов по каждой части курсовой работы. В качестве исходных данных для расчетов взяты примеры из учебных пособий [4,5], что позволяет легко ориентироваться в необходимых для выполнения расчетов теоретических сведениях, если студенты выполняют курсовую роботу с опережением графика и еще не прослушали на лекциях необходимый для выполнения материал.
Приступая к выполнению курсовой работы, следует, прежде всего, внимательно познакомиться с разделами 1 — 4, а уже затем приступать к выбору, формулированию задачи и выполнению соответствующих расчетов.
1 Общие организационно—методические указания по выполнению курсовой работы
Курсовая работа состоит из шести частей называемых расчетно-графическими работами (РГР). Таким образом, для выполнения курсовой работы студент должен последовательно, в соответствии с приведенным ниже графиком учебного процесса выполнить шесть расчетно-графических работ. Выполненная часть курсовой работы оформляется в соответствии с приведенными ниже правилами и сдается на проверку. Зачтенная РГР возвращается студенту и хранится у него до момента защиты курсовой работы. Расчетно-графическая работа с ошибками возвращается студенту на доработку.
Резолюция «Устранить замечания» на титульном листе, проверенной преподавателем РГР, требует от студента следующего: 1. Внимательно ознакомиться с замечаниями преподавателя, которые даны по тексту РГР; 2. Дать исправления в специальном разделе в конце РГР «Работа над замечаниями». В этом разделе отмеченное преподавателем место в тексте должно быть дано верно, без ошибок; 3. Листы с ошибками не удалять, текст РГР заново не перепечатывать; 4. Сдать РГР на повторную проверку.
Резолюция на титульном листе РГР «Обратите внимание на мои замечания» требует от студента следующего: 1. Внимательно ознакомиться с замечаниями преподавателя, которые даны по тексту РГР; 2. Дать исправления в специальном разделе в конце РГР «Работа над замечаниями». В этом разделе отмеченное преподавателем место в тексте должно быть дано верно, без ошибок; 3. Листы с ошибками не удалять, текст РГР заново не перепечатывать; 4. На повторную проверку РГР не сдавать.
После того как все шесть частей курсовой работы будут выполнены и зачтены, они оформляются как разделы курсовой работы, добавляется титульный лист курсовой работы и студент может ее защищать. Защита курсовой работы проводится в последние две недели декабря текущего года.