Поиск по базе сайта:
Рабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика icon

Рабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика




Скачати 91.67 Kb.
НазваРабочая программа дисциплины дискретная математика направление подготовки 230700 Прикладная информатика
Дата конвертації07.02.2013
Розмір91.67 Kb.
ТипРабочая программа

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


Томский государственный университет


УТВЕРЖДАЮ


Зав кафедрой программной инженерии

д.ф.-м..н., профессор

О. А. Змеев


"_____"__________________2010 г.


Рабочая программа дисциплины


ДИСКРЕТНАЯ МАТЕМАТИКА


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


230700 Прикладная информатика


Квалификация выпускника


Бакалавр


Форма обучения


Очная


Томск

2010


1. Цели освоения дисциплины


Целями освоения дисциплины «Дискретная математика» являются получение теоретических знаний по основам дискретной математики.


^ 2. Место дисциплины в структуре ООП бакалавриата


Раздел образовательной программы: Б.2.9. Математический и естественно-научный цикл. Базовая часть.

Для изучения курса необходимо знание математики в объёме общеобразовательной средней школы.

Знания и умения, полученные в ходе освоения данной дисциплины, понадобятся при изучении таких последующих дисциплин ООП, как:

- математическая логика и теория алгоритмов;

- теория графов;

- алгоритмы и анализ сложности;

- основы программирования;

- базы данных;

- методы оптимизации и исследование операций;

- интеллектуальные системы;

- компьютерные сети;

- теория автоматов и формальных языков;

- теория систем и системный анализ.


^ 3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Дискретная математика»


Курс «Дискретная математика» способствует выработке у студента следующих компетенций:

- способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-4);

- способность профессионально владеть базовыми математическими знаниями (ПК-8);

- понимание концепций и абстракций, способность использовать на практике методы дискретной математики (ПК-15).


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

- знать основные понятия и методы дискретной математики;

- уметь применять на практике методы дискретной математики.


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


^ 4. Структура и содержание дисциплины «Дискретная математика»


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






п/п



Раздел

Дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах)

^ Формы текущего контроля успеваемости (по неделям семестра)

Форма промежуточной аттестации (по семестрам)













лекции

сем

самостоятельная работа




1

Введение в теорию множеств..

1

1-2

8

4

10




2

Булевы алгебры

1

3-4

8

4

10




3

Промежуточная аттестация

1

5










Тест

4

Элементы комбинаторики

1

6-9

8

4

20




5

Промежуточная аттестация

1

10










Тест

6

Бинарные отношения

1

11-14

12

10

20




7

Промежуточная аттестация

1

15










Тест

8

Булевы

функции

1

16-19

12

10

20




9

Промежуточная аттестация

1

20-21







20

Тест

Экзамен

ИТОГО










48

32

100






Лекционный курс

^

Тема 1. Введение в теорию множеств.


Понятие множества. Операции над множествами. Алгебра множеств.

Тема 2. Булевы алгебры.

Аксиомы булевой алгебры. Принцип двойственности. Булева алгебра и алгебра множеств.

Теоремы булевой алгебры и теоремы алгебры множеств.
^

Тема 3. Элементы комбинаторики.


Декартово произведение множеств. Кортежи, размещения, сочетания, перестановки. Основные правила комбинаторики. Введение в дискретную теорию вероятностей.
^

Тема 4. Бинарные отношения.


Определение отношения. Представления отношений. Операции над отношениями. Алгебраические свойства операций над отношениями. Свойства бинарных отношений – рефлексивность, симметричность, транзитивность. Транзитивное замыкание. Алгоритмы нахождения транзитивного замыкания. Отношения эквивалентности, толерантности, порядка и их свойства. Задача о наименьшем покрытии. Алгоритмы решения задачи о наименьшем покрытии. Анализ бинарных отношений. Отображения и функции.

Тема 5. Булевы функции.

Булевы функции. Способы задания булевых функций. Элементарные булевы функции. Фиктивные и существенные переменные. Представление булевой функции формулой. Равносильность формул. Двойственная функция и двойственная формула. Разложение булевой функции по переменным (разложение Шеннона). Совершенные нормальные формы. Минимизация булевых функций. Алгоритм Квайна, алгоритм Блейка-Порецкого. Нахождение минимальных и кратчайших покрытий. Полиномы Жегалкина. Классы линейных, самодвойственных, монотонных булевых функций. Теорема Поста о полноте системы булевых функций. Примеры функционально полных базисов.


.

Семинары.


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

  2. Алгебра множеств.

3.Аксиомы булевой алгебры. Принцип двойственности.

4. Теоремы булевой алгебры и теоремы алгебры множеств.

5. Декартово произведение множеств. Кортежи, размещения, сочетания, перестановки.

  1. Правило произведения. Нахождение числа кортежей, размещений, перестановок с помощью правила произведения.

  2. Определение отношения. Представления отношений. Операции над отношениями. Алгебраические свойства операций над отношениями

  3. Свойства бинарных отношений – рефлексивность, симметричность, транзитивность. Транзитивное замыкание. Алгоритмы нахождения транзитивного замыкания.

  4. Отношения эквивалентности, толерантности. Нахождение классов эквивалентности, классов толерантности.

  5. Отношения порядка. Древесный порядок, редукция древесного порядка.

  6. Булевы функции. Способы задания булевых функций. Элементарные булевы функции. Фиктивные и существенные переменные.

  7. Представление булевой функции формулой. Равносильность формул. Двойственная функция и двойственная формула.

  8. Разложение булевой функции по переменным (разложение Шеннона). Совершенные нормальные формы.

  9. Минимизация булевых функций. Алгоритм Квайна, алгоритм Блейка-Порецкого. Нахождение минимальных и кратчайших покрытий.

15. Полиномы Жегалкина. Классы линейных, самодвойственных, монотонных булевых функций. Теорема Поста о полноте системы булевых функций. Примеры функционально полных базисов.


^ 5. Образовательные технологии.


В ходе преподавания дисциплины используются следующие образовательные технологии:


- лекционный курс;

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


6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.


Самостоятельная работа студентов по дисциплине организуется в следующих формах:

- самостоятельное изучение основного теоретического материала, ознакомление с дополнительной литературой, Интернет-ресурсами;

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

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


^ 7. Учебно-методическое и информационное обеспечение дисциплины «Дискретная математика».


а) основная литература:


  1. Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000.

  2. Быкова С.В., Буркатовская Ю.Б. Булевы функции: Учебное пособие. – Томск, ТГУ, 2008.

  3. Шрейдер Ю.А. Равенство, сходство, порядок. – Наука, 1971.

  4. Кристофидес Н. Теория графов. Алгоритмический подход. – М., Мир, 1978.


б) дополнительная литература:

  1. Липский В. Комбинаторика для программистов. – М., Мир, 1977.

  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М., Наука, 1984.

  3. Свами М., Тхуласириман К. Графы, сети и алгоритмы. – М., Мир, 1984.




    ^ 8. Материально-техническое обеспечение дисциплины



Требуется обеспечение литературой, которую в достаточном объеме может предложить книжный фонд Научной библиотеки Томского госуниверситета и факультета информатики.


Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ООП ВПО по направлению подготовки 230700 Прикладная информатика.


Автор: ст. преподаватель В.В. Матушевский

Рецензент: д.ф.-м.н., профессор О. А. Змеев.


Программа одобрена на заседании кафедры программной инженерии


от ___________ года, протокол № ________.



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації