Энгельсский технологический институт (филиал)
федерального государственного бюджетного образовательного учреждения высшего профессионального образования
«Саратовский государственный технический университет имени »
______________________________________________________________________
Кафедра "Высшая математика и механика"
"УТВЕРЖДАЮ"
Председатель УМКН
«Информатика и вычислительная техника»
________________ ()
"___ " __________ 2011 г.
РАБОЧАЯ УЧЕБНАЯ ПРОГРАММА
по дисциплине Б.2.2.1 «Дискретная математика»
(шифр и наименование дисциплины по УП)
Направление подготовки 230100.62 – «Информатика и вычислительная техника»
Профиль подготовки – все профили
Форма обучения – очная
Цикл дисциплин: МиЕН, часть цикла – вариативная
Вид учебной работы | Всего | Курс, семестр (часы) | ||||||||
З. е. | Часы | 1 | 2 | 3 | 4 | |||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |||
Аудиторные занятия (АЗ): всего в том числе: | 2 | 72 | 72 | |||||||
Лекции (ЛК) | 0,78 | 28 | 28 | |||||||
Доля лекционных часов от АЗ по дисциплине, % | 39 | |||||||||
Коллоквиумы (КЛ) | 0,22 | 8 | 8 | |||||||
Лабораторные работы (ЛР) | ||||||||||
Практические занятия: (ПЗ) | 1 | 36 | 36 | |||||||
Доля интерактивных форм обучения от АЗ по дисциплине, % | ||||||||||
Самостоятельная работа (СР), всего в том числе: | 2 | 72 | ||||||||
Курсовая работа (КР) | ||||||||||
Курсовой проект (КП) | ||||||||||
Расчетно-графическая работа (РГР) | ||||||||||
Другие виды самостоятельной работы | 1 | 36 | ||||||||
Вид промежуточной аттестации (экзамен): | 1 | 36 | ||||||||
Общая трудоемкость дисциплины и трудоемкость по семестрам: | 4 | 144 |
1. Цели и задачи освоения дисциплины
Целью освоения дисциплины «Дискретная математика» является приобретение студентами знаний и навыков, позволяющих применять их при освоении других дисциплин образовательного цикла и последующей профессиональной деятельности.
Для достижения этой цели преподавание дисциплины предполагает:
1.1 ознакомить студентов с основными понятиями и методами дискретной математики;
1.2 способствовать формированию у студента обобщенных приемов исследовательской деятельности, научного взгляда на мир в целом;
1.3 развить у студентов математическое мышление, чтобы будущий бакалавр смог переносить общие методы научной работы в работу по специальности;
1.4 обеспечить возможность овладения студентами совокупностью математических знаний и умений, соответствующих уровню бакалавра по соответствующему профилю.
Теоретическая часть дисциплины излагается в лекционном курсе. Полученные знания закрепляются на практических занятиях. Самостоятельная работа предусматривает использование ресурсов сети Интернет, работу с учебниками и учебными пособиями, подготовку к практическим занятиям, выполнение домашних заданий, подготовку к контрольным работам.
2. Место дисциплины в структуре ООП ВПО
«Дискретная математика» представляет собой дисциплину вариативной части математического и естественнонаучного цикла (Б.2.2.1) основной образовательной программы бакалавриата по направлению 230100.62 – «Информатика и вычислительная техника»
3. Требования к результатам освоения дисциплины
В процессе освоения данной дисциплины студент формирует и демонстрирует следующие общекультурные и профессиональные компетенции:
- способность использовать основные законы естественнонаучных дисциплин профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);
- способность применять навыки работы с компьютером как средством управления информацией (ОК-12);
- способность осваивать методики использования программных средств для решения практических задач (ПК-2).
В результате изучения дисциплины «Дискретная математика» вариативной части математического и естественнонаучного цикла (Б.2.2.1) основной образовательной программы бакалавриата студент должен:
3.1. Знать основные понятия и методы решения в следующих разделах:
- множества, отношения, функции и отображения;
- переключательные функции;
- схемы потоков данных.
3.2. Уметь:
- строить математические модели;
- ставить прикладные задачи для математического моделирования;
- подбирать подходящий метод и алгоритм для решения задач;
- применять качественные математические методы исследования;
- вырабатывать практические рекомендации на основе проведенного математического исследования.
3.3. Владеть навыками:
- употребления математической символики для выражения количественных и качественных отношений объектов;
- исследования моделей с учетом их иерархической структуры и оценки пределов
применимости полученных результатов.
4. Структура и содержание дисциплины
4.1. Разделы дисциплины, виды занятий и работ
№ п/п | Наименование раздела дисциплины (модуля) | ЛК* | КЛ | ПЗ | ЛР | КП (КР, РГР) | СРС |
1. | Множества, отношения, функции и отображения | + | + | + | |||
2. | Переключательные функции | + | + | + | |||
3. | Теория графов | + | + | + | |||
4. | Схемы потоков данных | + | + | + |
*Используемый вид занятий при прохождении данного раздела помечается знаком “+”
4.2. Содержание разделов дисциплин
№ п/п | Наименование раздела дисциплины (модуля) | Содержание раздела (модуля) | Трудоемкость, з. е./часы |
1. | Множества, отношения, функции и отображения | Множества и операции над ними. Соответствия между множествами, функции. Бинарные отношения. | 1/36* |
2. | Переключательные функции | Логические функции. Основные функции двузначной логики. Дизъюнктивная нормальная форма логической функции. Минимизация логической функции. | 1/36* |
3. | Теория графов | Граф, орграф. Деревья. Взвешенные графы. Построение кратчайших путей. Обходы на графах. | 1/36* |
4. | Схемы потоков данных | Транспортная сеть. Задача о максимальном потоке по сети. | 1/36* |
* Включая СРС
5. Практические занятия
№ п/п | Наименование раздела дисциплины (модуля) | Темы практических занятий. Вопросы, отрабатываемые на практическом занятии | Трудоемкость (з. е./ часы) |
1. | Множества, отношения, функции и отображения | Множества и операции над ними. Соответствия между множествами, функции. Бинарные отношения | /9 |
2. | Переключательные функции | Логические функции. Основные функции двузначной логики. Дизъюнктивная нормальная форма логической функции. Минимизация логической функции | /9 |
3. | Теория графов | Граф, орграф. Матрицы смежности и инцидентности. Связность графа, компоненты графа. Деревья. Взвешенные графы, построение кратчайших путей, алгоритмы Дейкстры, Форда, Флойда. Эйлеровы и гамильтоновы графы. Построение обходов на графах | /9 |
4. | Схемы потоков данных | Транспортная сеть. Пропускная способность. Поток по сети. Разрез на сети. Теорема Форда-Фалкерсона Алгоритм построения максимального потока по сети. | /9 |
6. Лабораторный практикум
Лабораторный практикум не предусмотрен учебным планом.
7. Примерная тематика курсовых проектов (работ)
Курсовые проекты (работы) не предусмотрены учебным планом.
8. Образовательные технологии
Предусмотрено чтение лекций с применением мультимедийных технологий, проведение интерактивных практикумов (в совокупности – не менее 20% аудиторных занятий).
Внеаудиторная самостоятельная работа студентов проводится с использованием ресурсов сети Интернет и локальных сетевых ресурсов ЭТИ СГТУ.
9. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов
Примеры контрольных вопросов и заданий для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины, а также для контроля самостоятельной работы обучающегося по отдельным разделам дисциплин.
1. Используя определения операций над множествами, доказать данное тождество теории множеств 
Проиллюстрировать доказательство с помощью диаграмм Венна.
2. Проверить, является ли данное бинарное отношение ρÎR2: 
рефлексивным, симметричным, транзитивным.
3. Дана логическая функция 
. Требуется:
1) Представить 
в СДНФ.
2) Представить в СКНФ.
3) Разложить по переменной 
, используя представления логических функций двух переменных.
4. Орграф без контуров задан матрицей смежности вершин.
Требуется:
1) Упорядочить вершины данного орграфа матричным способом.
2) Перенумеровать вершины в соответствии с упорядочением и построить орграф, изоморфный данному.
3) Для орграфа, полученного в пункте 2, составить матрицу смежности вершин.
5. Для данного взвешенного орграфа с 
вершинами, без кратных дуг и петель, приведена матрица весов.
Требуется построить с помощью алгоритма Дейкстры кратчайший путь от вершины 
до вершины 
.
10. Перечень вопросов к экзамену
1. Понятия множества и элемента множества, примеры. Подмножество, собственное подмножество: определения, примеры. Универсальное множество: определение, пример
2. Равные множества: определение, пример. Мощность конечного множества, пустое множество: определение, примеры
3. Способы задания множества
4. Объединение и пересечение множеств: определения и примеры
5. Разность множеств, дополнение множества: определения и примеры
6. Основные тождества теории множеств. Привести пример доказательства для одного из тождеств
7. Прямое (декартово) произведение множеств: определение и пример
8. Мощность декартова произведения конечных множеств
9. Соответствие между множествами: определение, пример. Область определения и область значений соответствия
10. Всюду определенное соответствие, сюръективное соответствие: определения, примеры
11. Образ элемента при соответствии, прообраз элемента при соответствии: определения, примеры. Функциональное соответствие (функция): определение, пример
12. Взаимно однозначное соответствие: определение, пример
13. Отображение множества в (на) множество: определения, примеры
14. Обратное соответствие: определение, пример
15. Композиция функций: определение, пример
16. Бинарное отношение на множестве: определение и пример
17. Свойства бинарного отношения: рефлексивность, симметричность, транзитивность
18. Отношение эквивалентности, разбиение множества на классы эквивалентности
19. Антирефлексивность и антисимметричность; отношения строгого и нестрогого порядков
20. Определение и пример логической функции
21. Логические функции: отрицание, дизъюнкция, конъюнкция
22. Логические функции: сложение по модулю 2, импликация, эквивалентность
23. Суперпозиция логических функций; логические формулы; равносильные логические формулы
24. Теорема о дизъюнктивной нормальной форме логической функции
25. Булевы операции и их основные свойства. Привести доказательство одного из свойств
26. Функционально полная система логических функций: определение, пример
27. Граф, вершина графа, ребро графа: определения, примеры
28. Орграф, вершина орграфа, дуга графа: определения, примеры
29. Смежные вершины, матрица смежности для графа и орграфа: определения, примеры
30. Инцидентные вершина и ребро, матрица инцидентности для графа и орграфа: определения, примеры
31. Диаграмма графа, изоморфизм графов
32. Плоские графы. Формула Эйлера
33. Мультиграф и псевдограф: определения и примеры
34. Степень вершины, вычисление степени вершины по элементам матрицы смежности. Изолированная и висячая вершины: определения, примеры
35. Полустепени захода и исхода вершины орграфа, вычисление полустепеней по элементам матрицы смежности
36. Матрицы смежности и инцидентности изоморфных графов
37. Маршрут, цепь, простая цепь, цикл: определения и примеры
38. Ориентированный маршрут, цепь, путь, контур: определения и примеры
39. Подграф, остовный подграф: определения и примеры
40. Связный граф, компонента графа: определения и примеры. Точка сочленения и мост: определения и примеры
41. Числа реберной и вершинной связности: определения и примеры
42. Объединение, произведение, композиция графов: определения и примеры
43. Дерево: дать равносильные определения понятию, привести пример
44. Ориентация графа, определить число всех возможных ориентаций для графа с заданным числом ребер
45. Остовное дерево: определение и пример. Алгоритм построения остовного дерева
46. Взвешенный граф, минимальное остовное дерево: определения и примеры
47. Обоснование алгоритма построения минимального остовного дерева
48. Путь, контур, полупуть, полуконтур в орграфе: определения и примеры. Сильный, односторонний, слабый орграф: определения и примеры
49. Сильная, односторонняя и слабая компоненты орграфа: определения и примеры. Конденсация графа: определение и пример
50. База орграфа: определение и пример. Доказать теорему о базе орграфа
51. Алгоритм Дейкстры поиска кратчайшего пути между двумя выделенными вершинами орграфа
52. Алгоритм Форда поиска кратчайшего пути между двумя выделенными вершинами орграфа
53. Алгоритм Флойда поиска кратчайших путей между всеми парами вершин орграфа. Встроенный и внешний способы восстановления пути
54. Эйлеров граф: определение и пример. Доказать критерий существования в графе эйлерова цикла.
55. Алгоритм Флёри построения эйлерова цикла. Обоснование алгоритма Флёри
56. Гамильтонов цикл. Достаточные условия наличия в графе гамильтонова цикла
57. Сеть, пропускная способность ребра, поток по ребру, поток на сети: определения и примеры. Разрез на сети, пропускная способность разреза, поток через разрез: определения и примеры
58. Постановка задачи о максимальном потоке на сети. Теорема Форда-Фалкерсона. Алгоритм построения максимального потока на сети
59. Конечный автомат, таблица переходов и диаграмма переходов, условия полноты и непротиворечивости для диаграммы переходов
60. Инициальный автомат, расширенные функции переходов и выходов. Автоматное отображение и его свойства
61. Эквивалентные автоматы, понятие о минимальном автомате
11. Учебно-методическое и информационное обеспечение дисциплины (модуля)
11.1. Основная литература:
1. Серебряков курс математической логики: учеб. пособие. – Саратов: Сарат. гос. техн. ун-т, 2011.
2. Серебряков в теорию графов: учеб. пособие. – Саратов: Сарат. гос. техн. ун-т, 2009.
3. , , Ерусалимский . Общий курс – СПб: Лань, 2006.
11.2. Дополнительная литература:
1. Элементы дискретной математики: Учебник для вузов / , . – Новосибирск: изд-во НГТУ Инфра-М – 2005.
2. Шапорев логика. Курс лекций и практических занятий. – СПб: БХВ-Петербург, 2005.
11.3. Программное обеспечение и Интернет-ресурсы
Имеются лицензионные пакеты прикладных программ Mathcad.
Рекомендуется использование Интернет-библиотек свободного доступа
http://eqworld. *****
http://*****/
В свободном доступе для студентов, обучающихся в вузе, находятся электронные версии учебных пособий.
Текущий контроль проводится с использованием тестов в адаптивной среде тестирования (АСТ) и Интернет-тестирования на сайте http://*****/
Промежуточная аттестация в сессию проводится с использованием тестов в адаптивной среде тестирования.
12. Материально-техническое обеспечение дисциплины (модуля):
Кафедра ВММ располагает лабораторией для проведения учебно-исследовательской работы. Лаборатория оснащена современной компьютерной и оргтехникой. Все рабочие места имеют подключение к локальной сети ЭТИ СГТУ и сети Интернет.
13. Методические рекомендации по организации изучения дисциплины (методические рекомендации преподавателю):
Учебным управлениям (отделам) вузов и кафедрам, ведущим образовательный процесс по дисциплине необходимо: сформировать вариативное расписание проведения обучения по отдельным учебно образовательным модулям дисциплины различными преподавателями; обеспечить углубленную научную, практическую и методическую подготовку преподавателей, специализирующихся на проведении занятий по отдельным модулям. Студенты перед началом изучения дисциплины должны быть ознакомлены с системами и балльно-рейтинговой оценки, которые должны быть опубликованы и размещены на сайте вуза или кафедры. В учебном процесс рекомендуется внедрение субъект-субъектной педагогической технологии, при которой в расписании каждого преподавателя определяется время консультаций студентов по закрепленному за ним модулю дисциплины.
Практикумы, тренинги и обучающие игры являются формой индивидуально-группового и практико-ориентированного обучения на основе реальных или модельных ситуаций применительно к виду и профилю профессиональной деятельности обучающегося.
Самостоятельная работа студентов составляет не менее 50% от общей трудоемкости дисциплины, является важнейшим компонентом образовательного процесса, формирующим личность студента, его мировоззрение и культуру безопасности, развивающим его способности к самообучению и повышению своего профессионального уровня.
Цели самостоятельной работы.
Формирование способностей к самостоятельному познанию и обучению, поиску литературы, обобщению, оформлению и представлению полученных результатов, их критическому анализу, поиску новых и неординарных решений, аргументированному отстаиванию своих предложений, умений подготовки выступлений и ведения дискуссий.
Организация самостоятельной работы.
Самостоятельная работа заключается в изучении отдельных тем курса по заданию преподавателя по рекомендуемой им учебной литературе, в подготовке к практическим занятиям, к рубежным контролям, экзамену, в выполнении домашнего задания.
Рабочая программа по дисциплине Б.2.2.1 «Дискретная математика» составлена в соответствии с требованиями Федерального Государственного образовательного стандарта ВПО по направлению 230100.62 – «Информатика и вычислительная техника»
Автор ___________________ ()
Согласовано: зав. библиотекой ________________ ()
Рабочая программа рассмотрена на заседании кафедры ВММ
(протокол №___ от “___ “ ________ 2011 г.) и признана соответствующей требованиям ФГОС и учебного плана по направлению 230100.62 – «Информатика и вычислительная техника»
Зав. кафедрой ______________________ ()
Рабочая программа рассмотрена на заседании учебно-методической комиссии по направлению ИВЧТ
(протокол № ___ от “___ “ ________ 2011 г.) и признана соответствующей требованиям ФГОС и учебного плана по направлению 230100.62 – «Информатика и вычислительная техника»
Председатель УМКН ИВЧТ __________ ()
