Учебные материалы для студентов заочной формы обучения



Скачать 145.85 Kb.
Дата30.04.2019
Размер145.85 Kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Забайкальский государственный университет»

(ФГБОУ ВПО «ЗабГУ»)
Факультет энергетический

Кафедра информатики, вычислительной техники и прикладной математики



УЧЕБНЫЕ МАТЕРИАЛЫ

для студентов заочной формы обучения

по дисциплине «Дискретная математика»

для направления подготовки

09.03.01 Информатика и вычислительная техника

Общая трудоемкость дисциплины (модуля)


Виды занятий

Распределение по семестрам

в часах


Всего часов

1

семестр


----

семестр


----

семестр


1

2

3

4

5

Общая трудоемкость

144







144

Аудиторные занятия, в т.ч.:

16







16

лекционные (ЛК)

8







8

практические (семинарские) (ПЗ, СЗ)

8







8

лабораторные (ЛР)











Самостоятельная работа студентов (СРС)

92







92

Форма промежуточного контроля в семестре

36

(экзамен)









36

Курсовая работа (курсовой проект) (КР, КП)









Краткое содержание курса
1. Теория множеств.

2. Алгебраические системы.

3. Комбинаторика.

4. Теория графов.



Форма текущего контроля
Контрольная работа №1
Контрольная работа № 1 состоит из десяти заданий. Номер варианта определяется по последней цифре шифра зачетной книжки.

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

Контрольная работа выполняется в рукописном виде в тетради. Оформление письменной работы согласно МИ 4.2-5/47-01-2013 Общие требования к построению и оформлению учебной текстовой документации.
Контрольная работа 1

Элементы теории множеств
ВАРИАНТ 1


  1. Доказать, что

а) А  В < = > A  B = В

б) А \ (В \ С) = (А \ В)  (А  С)



  1. А = {1, 2, 3, 4, 5}. Является ли отношение Р рефлексивным, симметричным, транзитивным или антисимметричным, если Р = { (a,b) a,b A, a - b – четное}/

  1. f: A -> B и g: B -> C – отношения. Что является областью определения f • g, когда:

а) f и g – функции

б) f – функция, g – отображение.

4. Понятие функции и отображения. Виды функций.
ВАРИАНТ 2


  1. Доказать, что

а) А  В < = > A  B = А

б) (А \ В) \ С = (А \ С) \ (В \ С)



  1. f: A -> B и g: B -> C – отношения. Что является областью определения f • g, когда:

а) f – отображение, g – функция

б) f и g – отображения



  1. А = {1, 2, 3, 4, 5}. Является ли отношение Р рефлексивным, симметричным, транзитивным или антисимметричным, если Р = { (a,b) a,b A, a + b – четное}.

  1. Отношения. Основные понятия: n-местный предикат, бинарное отношение, обратное отношение, области определения и изменения отношения, образ и прообраз множества Х относительно отношения Р, графическое представление отношений.


ВАРИАНТ 3

  1. Доказать, что

а) А  В < = > A \ B = 

б) (А \ В)  С = (А  С) \ В



  1. Отношение на Р (множестве всех людей) определяется как Р = { (a,b) a и b имеют общего предка}.

Какими свойствами обладает это отношение?

  1. Доказать, что если функция f инъективна, то существует f -1 .

  1. Обратные функции и отображения.


ВАРИАНТ 4

  1. Доказать, что

а) А  В < = > A  B = U

б) (А  В) \ С = (А \ С)  (В \ С)



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение R2?


  1. Если функция f сюръективна, следует ли отсюда, что f -1 отображение?

  1. Отношения, свойства отношений.


ВАРИАНТ 5

  1. Доказать, что

а) А  В = В < = > A  B = А

б) (А  В) \ С = (А \ С)  (В \ С)



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение S2?


  1. А = {-10, -9, ..., 0, 1, ...,9, 10}. Какие из указанных отношений на множестве А являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией.

Если отношение является функцией, то дать характеристику этой функции.

а) Р1 = { (x,y) x,y A, x = y2}

б) Р2 = { (x,y) x,y A, x2 = y}

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


ВАРИАНТ 6

  1. Доказать, что

а) А  В = В < = > A \ B = 

б) Вытекает ли из А \ В = С, что А = В  С?



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение SR?


  1. А = {-10, -9, ..., 0, 1, ...,9, 10}. Какие из указанных отношений на множестве А являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией.

Если отношение является функцией, то дать характеристику этой функции.

а) Р1 = { (x,y) x,y A, x = -y}

б) Р2 = { (x,y) x,y A, x = 6}

4. Составные отношения.


ВАРИАНТ 7

  1. Доказать, что

а) А  В = В < = > A  B = U

б) Вытекает ли из А = В  С, что А \ В = С?



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение SR-1?


  1. А = {-10, -9, ..., 0, 1, ...,9, 10}. Какие из указанных отношений на множестве А являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией.

Если отношение является функцией, то дать характеристику этой функции.

а) Р1 = { (x,y) x,y A, x3 = y}

б) Р2 = { (x,y) x,y A, x = y3}

4. Понятия функции и отображения. Виды функций.


ВАРИАНТ 8

  1. Доказать, что

а) А  В = В < = > В \ А = 

б) Верно ли указанное равенство:

А  (В \ С) = (А  В ) \ С?

Если нет, то в какую сторону имеет место включение?



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является матерью y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение R-1 S?


  1. А = {-10, -9, ..., 0, 1, ...,9, 10}. Какие из указанных отношений на множестве А являются функциями? Дать противоречащие примеры в случаях, когда отношение не является функцией.

Если отношение является функцией, то дать характеристику этой функции.

а) Р1 = { (x,y) x,y A, x = y }

б) Р2 = { (x,y) x,y A, x2 = y}

4. Принцип математической индукции.


ВАРИАНТ 9

  1. Доказать, что

а) А \ В =  < = > A  B = U

б) (А  В) \ С = (А \ С)  (В \ С)



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение R-1  S-1?


  1. f : A -> B и g : B -> C – функции. Доказать, что если f и g инъективны, то f • g инъективна.

4. Матрица бинарного отношения. Ее свойства.
ВАРИАНТ 10

  1. Доказать, что

а) А  (В \ А) = 

б) (А  В) \ С = (А \ С)  (В \ С)



  1. Р – множество всех людей.

R = { (x,y) x,y  P и x является отцом y}.

S = { (x,y) x,y  P и x – дочь y}.

Описать явно отношение R  S-1?


  1. f : A -> B и g: B -> C – функции. Доказать, что если f и g сюръективны, то f • g сюръективна.

4. Отношения. Свойства отношений.
Теория графов
Условия к заданиям для всех вариантов общие:
1. В графах G1 и G2 пометить вершины и дуги ( в графе G2 ).

а) Построить матрицу смежностей графа G1;

б) Построить матрицу смежностей и инцидентностей мультиграфа G2;

в) Восстановить граф по матрице смежностей АG. Задать G с помощью списка дуг и с помощью структуры смежности.


2. Даны графы G1 и G2 . Построить:

G1  G2 , G1  G2 , G1  G2 ,G1 ,G2 , G1  G2 , G1 [G2]. Вершины пометить самим.


3. Построить:

а) граф гомоморфный функции;

б) изоморфный функции;

в) граф, являющийся афтоморфизмом данного.


4. Найти матрицу достижимости, контрдостижимости. Указать все сильные компоненты связности графа.
5. Определить диаметр, радиус и центр графа.
6. а) Пометить вершины. Из неорграфа получить контурный орграф. Расставить веса дуг. Найти кратчайшее расстояние от вершины 1 до всех остальных (вершин).

б) Из неорграфа получить бесконтурный орграф. Найти кратчайшее расстояние от вершины 1 до всех остальных во взвешенном бесконтурном орграфе.

в) Найти один из кратчайших маршрутов (любой).


Вариант 1

1.


а) б)

G1 G2

в)

2.


G1 G2
3. 4.

5. 6.




Вариант 2
1.

а) б)


G1 G2

в)


2.

G1 G2
3. 4.


5. 6.




Вариант 3

1.


а) б)

G1 G2

в)

2.


G1 G2

3. 4.



5. 6.



Вариант 4

1.


а) б)

G1 G2

в)

2.


G1 G2

3. 4.


5. 6.



Вариант 5

1.


а) б)

G1 G2

в)


2.


G1 G2

3. 4.


5. 6.



Вариант 6

1.


а) б)

G1 G2

в)

2.


G1 G2

3. 4.


5. 6.




Вариант 7

1.


а) б)

G1 G2

в)

2.


G1 G2

3. 4.



5. 6.


Вариант 8
1.

а) б)


G1 G2

в)

2.


G1 G2
3. 4.


5. 6.



Вариант 9
а) б)

G1 G2
в)


1 0 1 0

0 1 0 0


Ав = 0 0 1 0

1 0 0 0


2.

G1 G2
3.


4.

1 2


3

8 7 6



5 4

5.

2 3


1 4

5

6



6.

1

Вариант 10


1. а) б)

G1 G2


в)

0 1 0 0 1

1 0 1 0 1

Ав= 0 0 1 0 0

0 1 0 0 0

1 0 0 1 0

2.

G1 G2


3.

4.
1

2
6

5
3

4
5.
3

2 6 4


1 5

6.
1



Вопросы к защите Контрольной работы № 1


  1. Понятие множества, подмножества. Виды множеств. Способы задания. Диаграммы Эйлера-Венна.

  2. Операции над множествами: объединение, пересечение, разность, симметрическая разность (кольцевая сумма), дополнение множества, декартово произведение, отношение между множествами, формирование булеана множества. Основные законы операций пересечения, объединения и дополнения.

  3. Отношения на множествах. Бинарное отношение, его область определения и область значения. Обратное отношение. Образ и прообраз множества X относительно отношения P. Графическое представление отношений, составные отношения (произведение бинарных отношений).

  4. Понятие функции и отображения. Сюрьективные, инъективные, биективные, функции. Обратные функции и отображения.

  5. Мощность множества. Конечные и бесконечные множества. Теорема Кантора-Бернштейна. Операции на кардинальных числах.

  6. Матрица бинарного отношения и ее свойства. Свойства бинарных отношений: рефлексивность, симметричность, антисимметричность, транзитивность. Отношения эквивалентности и разбиения. Фактор-множества. Отношения порядка.

  7. Виды и способы задания графов. Морфизмы в графах. Матрицы смежности и инцидентности. Пометки в графах. Матрица весов. Подграфы и части графа.

  8. Операции над графами: добавление и удаление вершины, добавление и удаление дуги, отождествление вершин, дополнение вершин, дополнение графа, объединение, пересечение, кольцевая сумма, соединение, произведение, композиция графов. N-мерные кубы.

  9. Маршруты, пути. Достижимость в графах. Связность. Компоненты связности.

  10. Расстояния в графах. Кратчайшие расстояния. Алгоритмы Форда-Беллмана, Дейкстры. Восстановление маршрута по кратчайшему расстоянию.


Форма промежуточного контроля
Экзамен:

Экзаменационный билет включает в себя четыре задания:



  1. два теоретических вопроса;

  2. два практических задания.


Перечень примерных вопросов для подготовки к экзамену


  1. Множества. Основные понятия. Диаграммы Эйлера-Венна.

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

  3. Отношения. Графическое представление бинарных отношений. Понятие функции и отображения. Виды функций. Обратные функции и отображения. Натуральные числа. Принцип математической индукции.

  4. Мощность множества. Матрица бинарного отношения. Свойства отношений.

  5. Отношение эквивалентности и разбиения. Фактор – множества. Отношение порядка.

  6. Алгебраические системы. Основные понятия. Фундаментальные алгебры.

  7. Морфизмы в алгебраических системах. Алгебры отношений и реляционные алгебры.

  8. Основные комбинаторные конфигурации: перестановки, сочетания, размещения.

  9. Разбиения.

  10. Виды и способы задания графов.

  11. Подграфы и части графа. Операции над графами.

  12. Маршруты, достижимость, связность. Расстояния в графах.

  13. Расстояния в графах. Алгоритмы Форда-Беллмана, Дейкстры.

  14. Степени вершин. Эйлеровы графы. Гамильтоновы графы.

  15. Остовы графов. Обходы графа по ширине и глубине.

  16. Фундаментальные циклы.

  17. Разрезы. Сети. Связь разрезов и циклов.

  18. Раскраска графа.


Критерии формирования оценок экзамена
Экзамен проводится в устной форме: обсуждается теоретический материал и приводится решение практических заданий с объяснением.

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

Оценка «отлично» – полный, развернутый ответ на все вопросы билета.

Оценка «хорошо» – полный ответ на любые три вопроса билета.

Оценка «удовлетворительно» – дан ответ на любые два вопроса.

Оценка «неудовлетворительно» – ставится в случае, если студент не выполнил ни одного практического задания или ответил только на один теоретический и один практический вопрос из четырех предложенных.


Учебно-методическое и информационное обеспечение дисциплины
Основная литература

1. Белоусов А.И. Дискретная математика: учебник / под ред. В.С. Зарубина, А.П. Крищенко. – 3-е изд., стер. – М.: МГТУ, 2004. – 744 с.: ил.

2. Гаврилов Г.П. Задачи и упражнения по дискретной математике: учеб. пособие. / Г.П. Гаврилов, А.А. Сапоженко. – 3-е изд., перераб. – М.: ФИЗМАТЛИТ, 2006. – 416 с.

3. Кузнецов О.П. Дискретная математика для инженера: учеб. пособие. / О.П. Кузнецов. – 5-е изд., стер. – СПб.: Лань, 2007. – 400 с.: ил.

4. Макоха А.Н. Дискретная математика: учеб. пособие. / А.Н. Макоха, П.А. Сахнюк, Н.И. Червяков. – М.: ФИЗМАТЛИТ, 2005. – 368 с.

5. Новиков Ф.А. Дискретная математика для программистов: учебник. / Ф. А. Новиков. – 3-е изд. – СПб.: Питер, 2009. – 384 с.: ил.

6. Соболева Т.С. Дискретная математика: учебник. / Т.С. Соболева, А.В. Чечкин. / Под ред. А.В. Чечкина. – М.: Академия, 2006. – 256 с.

7. Спирина М.С. Дискретная математика: учебник. / М.С. Спирина, А.А. Спирин. – 4-е изд., испр. – М.: Академия, 2007. – 368 с.


Дополнительная литература
8. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Полный курс. / Б.Н. Иванов. – М.: ФИЗМАТЛИТ, 2007. – 408 с.

9. Хаггарти Р. Дискретная математика для программистов: учеб. пособие. / Под ред. С.А. Кулешова. – 2-е изд., доп. – М.: Техносфера, 2005. – 400 с.

10. Яблонский С.В. Введение в дискретную математику: учебное пособие. / под ред. В.А. Садовничего. – 3-е изд., стереотип. – М.: Высш. школа, 2002. – 384 с.
Собственные учебные пособия
11. Розова Н.В. Дискретная математика. Курс лекций. 2001. электронный вариант.

12. Розова Н.В. Дискретная математика. Линейная алгебра и геометрия: метод. / Н.В. Розова, Г.Н. Линькова. – Чита: ЧитГУ, 1998.


Базы данных, информационно-справочные и

поисковые системы


  1. http://window.edu.ru/Единый образовательный портал.

  2. http://library.zabgu.ru/Библиотека ЗабГУ.

Ведущий преподаватель:



к. ф.-м. н., доцент, доцент кафедры информатики, вычислительной техники и прикладной математики Розова Надежда Ворфоломеевна
Заведующий кафедрой ИВТ и ПМ к. ф.-м. н., доцент Дубровина Татьяна Владимировна


Каталог: files -> html document -> documents -> fixed -> Programnoe obespechenie vy'cheslitel'noj texniki i avtomatizirovanny'x sistem
fixed -> И. А. Мосичева, Н. В. Скибитский, В. П. Шестак
fixed -> Самостоятельная работа студентов
fixed -> Учебные материалы для студентов заочной формы обучения
fixed -> По дисциплине «Ремонт и утилизация подъемно-транспортных, строительных, дорожных средств и оборудования»
fixed -> Учебные материалы для студентов заочной формы обучения
Programnoe obespechenie vy'cheslitel'noj texniki i avtomatizirovanny'x sistem -> Учебные материалы для студентов заочной формы обучения
fixed -> Самостоятельная работа студентов


Поделитесь с Вашими друзьями:


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

    Главная страница